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
21namespace llvm {
22
23using LoopVectorTy = SmallVector<Loop *, 8>;
24
25class LPMUpdater;
26
27/// This class represents a loop nest and can be used to query its properties.
28class LLVM_EXTERNAL_VISIBILITY LoopNest {
29public:
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
182protected:
183 const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
184 LoopVectorTy Loops; // the loops in the nest (in breadth first order).
185
186private:
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
198raw_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>.
202class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
203 friend AnalysisInfoMixin<LoopNestAnalysis>;
204 static AnalysisKey Key;
205
206public:
207 using Result = LoopNest;
208 Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
209};
210
211/// Printer pass for the \c LoopNest results.
212class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
213 raw_ostream &OS;
214
215public:
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

source code of llvm/include/llvm/Analysis/LoopNestAnalysis.h