LLVM  16.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"
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.
29 public:
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.
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.
166  bool areAllLoopsSimplifyForm() const {
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.
171  bool areAllLoopsRotatedForm() const {
172  return all_of(Loops, [](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> {
204  static AnalysisKey Key;
205 
206 public:
207  using Result = LoopNest;
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 
220 };
221 
222 } // namespace llvm
223 
224 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopNestAnalysis::run
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:374
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::LoopNest::getLoopsAtDepth
LoopVectorTy getLoopsAtDepth(unsigned Depth) const
Get the loops in the nest at the given Depth.
Definition: LoopNestAnalysis.h:120
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
STLExtras.h
llvm::LoopNest::getLoopIndex
unsigned getLoopIndex(const Loop &L) const
Get the loop index of the given loop L.
Definition: LoopNestAnalysis.h:106
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
LoopAnalysisManager.h
llvm::all_of
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:1709
llvm::LoopNest::getLoop
Loop * getLoop(unsigned Index) const
Return the loop at the given Index.
Definition: LoopNestAnalysis.h:100
llvm::LoopVectorTy
SmallVector< Loop *, 8 > LoopVectorTy
Definition: LoopCacheAnalysis.h:35
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::LoopNest::getInnermostLoop
Loop * getInnermostLoop() const
Return the innermost loop in the loop nest if the nest has only one innermost loop,...
Definition: LoopNestAnalysis.h:85
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:291
llvm::LoopNestAnalysis
This analysis provides information for a loop nest.
Definition: LoopNestAnalysis.h:202
LoopInfo.h
llvm::LoopNestPrinterPass
Printer pass for the LoopNest results.
Definition: LoopNestAnalysis.h:212
llvm::LoopNestPrinterPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopNestAnalysis.cpp:457
llvm::LoopNest::MaxPerfectDepth
const unsigned MaxPerfectDepth
Definition: LoopNestAnalysis.h:183
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
llvm::LoopNest::areAllLoopsRotatedForm
bool areAllLoopsRotatedForm() const
Return true if all loops in the loop nest are in rotated form.
Definition: LoopNestAnalysis.h:171
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
LLVM_EXTERNAL_VISIBILITY
#define LLVM_EXTERNAL_VISIBILITY
Definition: Compiler.h:127
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:97
llvm::LoopNest::getOutermostLoop
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Definition: LoopNestAnalysis.h:80
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::LoopNest::getParent
Function * getParent() const
Return the function to which the loop-nest belongs.
Definition: LoopNestAnalysis.h:176
llvm::LoopNest::getNumLoops
size_t getNumLoops() const
Return the number of loops in the nest.
Definition: LoopNestAnalysis.h:114
llvm::LoopNest::getLoops
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Definition: LoopNestAnalysis.h:117
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:155
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:184
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:163
llvm::LoopNestPrinterPass::LoopNestPrinterPass
LoopNestPrinterPass(raw_ostream &OS)
Definition: LoopNestAnalysis.h:216
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::Loop::isRotatedForm
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:810
llvm::LoopNest::areAllLoopsSimplifyForm
bool areAllLoopsSimplifyForm() const
Return true if all loops in the loop nest are in simplify form.
Definition: LoopNestAnalysis.h:166
llvm::LoopNest
This class represents a loop nest and can be used to query its properties.
Definition: LoopNestAnalysis.h:28
llvm::LoopNest::getName
StringRef getName() const
Definition: LoopNestAnalysis.h:180