1//===- llvm/Analysis/LoopNestAnalysis.h -------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines the interface for the loop nest analysis.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_LOOPNESTANALYSIS_H
15#define LLVM_ANALYSIS_LOOPNESTANALYSIS_H
16
17#include "llvm/Analysis/LoopAnalysisManager.h"
18#include "llvm/Analysis/LoopInfo.h"
19
20namespace llvm {
21
22using LoopVectorTy = SmallVector<Loop *, 8>;
23class LPMUpdater;
24
25/// This class represents a loop nest and can be used to query its properties.
26class LoopNest {
27public:
28  /// Construct a loop nest rooted by loop \p Root.
29  LoopNest(Loop &Root, ScalarEvolution &SE);
30
31  LoopNest() = delete;
32  LoopNest &operator=(const LoopNest &) = delete;
33
34  /// Construct a LoopNest object.
35  static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE);
36
37  /// Return true if the given loops \p OuterLoop and \p InnerLoop are
38  /// perfectly nested with respect to each other, and false otherwise.
39  /// Example:
40  /// \code
41  ///   for(i)
42  ///     for(j)
43  ///       for(k)
44  /// \endcode
45  /// arePerfectlyNested(loop_i, loop_j, SE) would return true.
46  /// arePerfectlyNested(loop_j, loop_k, SE) would return true.
47  /// arePerfectlyNested(loop_i, loop_k, SE) would return false.
48  static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
49                                 ScalarEvolution &SE);
50
51  /// Return the maximum nesting depth of the loop nest rooted by loop \p Root.
52  /// For example given the loop nest:
53  /// \code
54  ///   for(i)     // loop at level 1 and Root of the nest
55  ///     for(j)   // loop at level 2
56  ///       <code>
57  ///       for(k) // loop at level 3
58  /// \endcode
59  /// getMaxPerfectDepth(Loop_i) would return 2.
60  static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
61
62  /// Return the outermost loop in the loop nest.
63  Loop &getOutermostLoop() const { return *Loops.front(); }
64
65  /// Return the innermost loop in the loop nest if the nest has only one
66  /// innermost loop, and a nullptr otherwise.
67  /// Note: the innermost loop returned is not necessarily perfectly nested.
68  Loop *getInnermostLoop() const {
69    if (Loops.size() == 1)
70      return Loops.back();
71
72    // The loops in the 'Loops' vector have been collected in breadth first
73    // order, therefore if the last 2 loops in it have the same nesting depth
74    // there isn't a unique innermost loop in the nest.
75    Loop *LastLoop = Loops.back();
76    auto SecondLastLoopIter = ++Loops.rbegin();
77    return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
78               ? nullptr
79               : LastLoop;
80  }
81
82  /// Return the loop at the given \p Index.
83  Loop *getLoop(unsigned Index) const {
84    assert(Index < Loops.size() && "Index is out of bounds");
85    return Loops[Index];
86  }
87
88  /// Return the number of loops in the nest.
89  size_t getNumLoops() const { return Loops.size(); }
90
91  /// Get the loops in the nest.
92  ArrayRef<Loop *> getLoops() const { return Loops; }
93
94  /// Retrieve a vector of perfect loop nests contained in the current loop
95  /// nest. For example, given the following  nest containing 4 loops, this
96  /// member function would return {{L1,L2},{L3,L4}}.
97  /// \code
98  ///   for(i) // L1
99  ///     for(j) // L2
100  ///       <code>
101  ///       for(k) // L3
102  ///         for(l) // L4
103  /// \endcode
104  SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const;
105
106  /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
107  /// For example given the loop nest:
108  /// \code
109  ///   for(i)      // loop at level 1 and Root of the nest
110  ///     for(j1)   // loop at level 2
111  ///       for(k)  // loop at level 3
112  ///     for(j2)   // loop at level 2
113  /// \endcode
114  /// getNestDepth() would return 3.
115  unsigned getNestDepth() const {
116    int NestDepth =
117        Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
118    assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
119    return NestDepth;
120  }
121
122  /// Return the maximum perfect nesting depth.
123  unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
124
125  /// Return true if all loops in the loop nest are in simplify form.
126  bool areAllLoopsSimplifyForm() const {
127    return llvm::all_of(Loops,
128                        [](const Loop *L) { return L->isLoopSimplifyForm(); });
129  }
130
131protected:
132  const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
133  LoopVectorTy Loops; // the loops in the nest (in breadth first order).
134};
135
136raw_ostream &operator<<(raw_ostream &, const LoopNest &);
137
138/// This analysis provides information for a loop nest. The analysis runs on
139/// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
140class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
141  friend AnalysisInfoMixin<LoopNestAnalysis>;
142  static AnalysisKey Key;
143
144public:
145  using Result = LoopNest;
146  Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
147};
148
149/// Printer pass for the \c LoopNest results.
150class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
151  raw_ostream &OS;
152
153public:
154  explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
155
156  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
157                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
158};
159
160} // namespace llvm
161
162#endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H
163