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/ADT/STLExtras.h" |
18 | #include "llvm/Analysis/LoopAnalysisManager.h" |
19 | #include "llvm/Analysis/LoopInfo.h" |
20 | |
21 | namespace llvm { |
22 | |
23 | using LoopVectorTy = SmallVector<Loop *, 8>; |
24 | |
25 | class LPMUpdater; |
26 | |
27 | /// This class represents a loop nest and can be used to query its properties. |
28 | class LLVM_EXTERNAL_VISIBILITY LoopNest { |
29 | public: |
30 | using InstrVectorTy = SmallVector<const Instruction *>; |
31 | |
32 | /// Construct a loop nest rooted by loop \p Root. |
33 | LoopNest(Loop &Root, ScalarEvolution &SE); |
34 | |
35 | LoopNest() = delete; |
36 | |
37 | /// Construct a LoopNest object. |
38 | static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE); |
39 | |
40 | /// Return true if the given loops \p OuterLoop and \p InnerLoop are |
41 | /// perfectly nested with respect to each other, and false otherwise. |
42 | /// Example: |
43 | /// \code |
44 | /// for(i) |
45 | /// for(j) |
46 | /// for(k) |
47 | /// \endcode |
48 | /// arePerfectlyNested(loop_i, loop_j, SE) would return true. |
49 | /// arePerfectlyNested(loop_j, loop_k, SE) would return true. |
50 | /// arePerfectlyNested(loop_i, loop_k, SE) would return false. |
51 | static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, |
52 | ScalarEvolution &SE); |
53 | |
54 | /// Return a vector of instructions that prevent the LoopNest given |
55 | /// by loops \p OuterLoop and \p InnerLoop from being perfect. |
56 | static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, |
57 | const Loop &InnerLoop, |
58 | ScalarEvolution &SE); |
59 | |
60 | /// Return the maximum nesting depth of the loop nest rooted by loop \p Root. |
61 | /// For example given the loop nest: |
62 | /// \code |
63 | /// for(i) // loop at level 1 and Root of the nest |
64 | /// for(j) // loop at level 2 |
65 | /// <code> |
66 | /// for(k) // loop at level 3 |
67 | /// \endcode |
68 | /// getMaxPerfectDepth(Loop_i) would return 2. |
69 | static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE); |
70 | |
71 | /// Recursivelly traverse all empty 'single successor' basic blocks of \p From |
72 | /// (if there are any). When \p CheckUniquePred is set to true, check if |
73 | /// each of the empty single successors has a unique predecessor. Return |
74 | /// the last basic block found or \p End if it was reached during the search. |
75 | static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From, |
76 | const BasicBlock *End, |
77 | bool CheckUniquePred = false); |
78 | |
79 | /// Return the outermost loop in the loop nest. |
80 | Loop &getOutermostLoop() const { return *Loops.front(); } |
81 | |
82 | /// Return the innermost loop in the loop nest if the nest has only one |
83 | /// innermost loop, and a nullptr otherwise. |
84 | /// Note: the innermost loop returned is not necessarily perfectly nested. |
85 | Loop *getInnermostLoop() const { |
86 | if (Loops.size() == 1) |
87 | return Loops.back(); |
88 | |
89 | // The loops in the 'Loops' vector have been collected in breadth first |
90 | // order, therefore if the last 2 loops in it have the same nesting depth |
91 | // there isn't a unique innermost loop in the nest. |
92 | Loop *LastLoop = Loops.back(); |
93 | auto SecondLastLoopIter = ++Loops.rbegin(); |
94 | return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth()) |
95 | ? nullptr |
96 | : LastLoop; |
97 | } |
98 | |
99 | /// Return the loop at the given \p Index. |
100 | Loop *getLoop(unsigned Index) const { |
101 | assert(Index < Loops.size() && "Index is out of bounds" ); |
102 | return Loops[Index]; |
103 | } |
104 | |
105 | /// Get the loop index of the given loop \p L. |
106 | unsigned getLoopIndex(const Loop &L) const { |
107 | for (unsigned I = 0; I < getNumLoops(); ++I) |
108 | if (getLoop(Index: I) == &L) |
109 | return I; |
110 | llvm_unreachable("Loop not in the loop nest" ); |
111 | } |
112 | |
113 | /// Return the number of loops in the nest. |
114 | size_t getNumLoops() const { return Loops.size(); } |
115 | |
116 | /// Get the loops in the nest. |
117 | ArrayRef<Loop *> getLoops() const { return Loops; } |
118 | |
119 | /// Get the loops in the nest at the given \p Depth. |
120 | LoopVectorTy getLoopsAtDepth(unsigned Depth) const { |
121 | assert(Depth >= Loops.front()->getLoopDepth() && |
122 | Depth <= Loops.back()->getLoopDepth() && "Invalid depth" ); |
123 | LoopVectorTy Result; |
124 | for (unsigned I = 0; I < getNumLoops(); ++I) { |
125 | Loop *L = getLoop(Index: I); |
126 | if (L->getLoopDepth() == Depth) |
127 | Result.push_back(Elt: L); |
128 | else if (L->getLoopDepth() > Depth) |
129 | break; |
130 | } |
131 | return Result; |
132 | } |
133 | |
134 | /// Retrieve a vector of perfect loop nests contained in the current loop |
135 | /// nest. For example, given the following nest containing 4 loops, this |
136 | /// member function would return {{L1,L2},{L3,L4}}. |
137 | /// \code |
138 | /// for(i) // L1 |
139 | /// for(j) // L2 |
140 | /// <code> |
141 | /// for(k) // L3 |
142 | /// for(l) // L4 |
143 | /// \endcode |
144 | SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const; |
145 | |
146 | /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop) |
147 | /// For example given the loop nest: |
148 | /// \code |
149 | /// for(i) // loop at level 1 and Root of the nest |
150 | /// for(j1) // loop at level 2 |
151 | /// for(k) // loop at level 3 |
152 | /// for(j2) // loop at level 2 |
153 | /// \endcode |
154 | /// getNestDepth() would return 3. |
155 | unsigned getNestDepth() const { |
156 | int NestDepth = |
157 | Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1; |
158 | assert(NestDepth > 0 && "Expecting NestDepth to be at least 1" ); |
159 | return NestDepth; |
160 | } |
161 | |
162 | /// Return the maximum perfect nesting depth. |
163 | unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; } |
164 | |
165 | /// Return true if all loops in the loop nest are in simplify form. |
166 | bool areAllLoopsSimplifyForm() const { |
167 | return all_of(Range: Loops, P: [](const Loop *L) { return L->isLoopSimplifyForm(); }); |
168 | } |
169 | |
170 | /// Return true if all loops in the loop nest are in rotated form. |
171 | bool areAllLoopsRotatedForm() const { |
172 | return all_of(Range: Loops, P: [](const Loop *L) { return L->isRotatedForm(); }); |
173 | } |
174 | |
175 | /// Return the function to which the loop-nest belongs. |
176 | Function *getParent() const { |
177 | return Loops.front()->getHeader()->getParent(); |
178 | } |
179 | |
180 | StringRef getName() const { return Loops.front()->getName(); } |
181 | |
182 | protected: |
183 | const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. |
184 | LoopVectorTy Loops; // the loops in the nest (in breadth first order). |
185 | |
186 | private: |
187 | enum LoopNestEnum { |
188 | PerfectLoopNest, |
189 | ImperfectLoopNest, |
190 | InvalidLoopStructure, |
191 | OuterLoopLowerBoundUnknown |
192 | }; |
193 | static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop, |
194 | const Loop &InnerLoop, |
195 | ScalarEvolution &SE); |
196 | }; |
197 | |
198 | raw_ostream &operator<<(raw_ostream &, const LoopNest &); |
199 | |
200 | /// This analysis provides information for a loop nest. The analysis runs on |
201 | /// demand and can be initiated via AM.getResult<LoopNestAnalysis>. |
202 | class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> { |
203 | friend AnalysisInfoMixin<LoopNestAnalysis>; |
204 | static AnalysisKey Key; |
205 | |
206 | public: |
207 | using Result = LoopNest; |
208 | Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); |
209 | }; |
210 | |
211 | /// Printer pass for the \c LoopNest results. |
212 | class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> { |
213 | raw_ostream &OS; |
214 | |
215 | public: |
216 | explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {} |
217 | |
218 | PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, |
219 | LoopStandardAnalysisResults &AR, LPMUpdater &U); |
220 | |
221 | static bool isRequired() { return true; } |
222 | }; |
223 | |
224 | } // namespace llvm |
225 | |
226 | #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H |
227 | |