LLVM 17.0.0git
LoopNestAnalysis.h
Go to the documentation of this file.
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"
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.
29public:
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.
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(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(I);
126 if (L->getLoopDepth() == Depth)
127 Result.push_back(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.
167 return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
168 }
169
170 /// Return true if all loops in the loop nest are in rotated form.
172 return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
173 }
174
175 /// Return the function to which the loop-nest belongs.
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> {
204 static AnalysisKey Key;
205
206public:
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
220};
221
222} // namespace llvm
223
224#endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H
BlockVerifier::State From
#define LLVM_EXTERNAL_VISIBILITY
Definition: Compiler.h:127
uint32_t Index
Hexagon Hardware Loops
This header provides classes for managing per-loop analyses.
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
This analysis provides information for a loop nest.
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
Printer pass for the LoopNest results.
LoopNestPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
This class represents a loop nest and can be used to query its properties.
StringRef getName() const
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
unsigned getNestDepth() const
Return the loop nest depth (i.e.
LoopVectorTy Loops
LoopNest()=delete
const unsigned MaxPerfectDepth
LoopVectorTy getLoopsAtDepth(unsigned Depth) const
Get the loops in the nest at the given Depth.
Loop * getLoop(unsigned Index) const
Return the loop at the given Index.
bool areAllLoopsRotatedForm() const
Return true if all loops in the loop nest are in rotated form.
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Function * getParent() const
Return the function to which the loop-nest belongs.
unsigned getLoopIndex(const Loop &L) const
Get the loop index of the given loop L.
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
bool areAllLoopsSimplifyForm() const
Return true if all loops in the loop nest are in simplify form.
size_t getNumLoops() const
Return the number of loops in the nest.
Loop * getInnermostLoop() const
Return the innermost loop in the loop nest if the nest has only one innermost loop,...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:810
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
The main scalar evolution driver.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1735
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
SmallVector< Loop *, 8 > LoopVectorTy
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371