LLVM  13.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 class LPMUpdater;
25 
26 /// This class represents a loop nest and can be used to query its properties.
27 class LoopNest {
28 public:
29  /// Construct a loop nest rooted by loop \p Root.
30  LoopNest(Loop &Root, ScalarEvolution &SE);
31 
32  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  /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
63  /// (if there are any). When \p CheckUniquePred is set to true, check if
64  /// each of the empty single successors has a unique predecessor. Return
65  /// the last basic block found or \p End if it was reached during the search.
66  static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
67  const BasicBlock *End,
68  bool CheckUniquePred = false);
69 
70  /// Return the outermost loop in the loop nest.
71  Loop &getOutermostLoop() const { return *Loops.front(); }
72 
73  /// Return the innermost loop in the loop nest if the nest has only one
74  /// innermost loop, and a nullptr otherwise.
75  /// Note: the innermost loop returned is not necessarily perfectly nested.
77  if (Loops.size() == 1)
78  return Loops.back();
79 
80  // The loops in the 'Loops' vector have been collected in breadth first
81  // order, therefore if the last 2 loops in it have the same nesting depth
82  // there isn't a unique innermost loop in the nest.
83  Loop *LastLoop = Loops.back();
84  auto SecondLastLoopIter = ++Loops.rbegin();
85  return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
86  ? nullptr
87  : LastLoop;
88  }
89 
90  /// Return the loop at the given \p Index.
91  Loop *getLoop(unsigned Index) const {
92  assert(Index < Loops.size() && "Index is out of bounds");
93  return Loops[Index];
94  }
95 
96  /// Return the number of loops in the nest.
97  size_t getNumLoops() const { return Loops.size(); }
98 
99  /// Get the loops in the nest.
100  ArrayRef<Loop *> getLoops() const { return Loops; }
101 
102  /// Retrieve a vector of perfect loop nests contained in the current loop
103  /// nest. For example, given the following nest containing 4 loops, this
104  /// member function would return {{L1,L2},{L3,L4}}.
105  /// \code
106  /// for(i) // L1
107  /// for(j) // L2
108  /// <code>
109  /// for(k) // L3
110  /// for(l) // L4
111  /// \endcode
113 
114  /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
115  /// For example given the loop nest:
116  /// \code
117  /// for(i) // loop at level 1 and Root of the nest
118  /// for(j1) // loop at level 2
119  /// for(k) // loop at level 3
120  /// for(j2) // loop at level 2
121  /// \endcode
122  /// getNestDepth() would return 3.
123  unsigned getNestDepth() const {
124  int NestDepth =
125  Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
126  assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
127  return NestDepth;
128  }
129 
130  /// Return the maximum perfect nesting depth.
131  unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
132 
133  /// Return true if all loops in the loop nest are in simplify form.
134  bool areAllLoopsSimplifyForm() const {
135  return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
136  }
137 
138  /// Return true if all loops in the loop nest are in rotated form.
139  bool areAllLoopsRotatedForm() const {
140  return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
141  }
142 
143  /// Return the function to which the loop-nest belongs.
144  Function *getParent() const {
145  return Loops.front()->getHeader()->getParent();
146  }
147 
148  StringRef getName() const { return Loops.front()->getName(); }
149 
150 protected:
151  const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
152  LoopVectorTy Loops; // the loops in the nest (in breadth first order).
153 };
154 
156 
157 /// This analysis provides information for a loop nest. The analysis runs on
158 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
159 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
161  static AnalysisKey Key;
162 
163 public:
164  using Result = LoopNest;
166 };
167 
168 /// Printer pass for the \c LoopNest results.
169 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
170  raw_ostream &OS;
171 
172 public:
173  explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
174 
177 };
178 
179 } // namespace llvm
180 
181 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:374
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LoopNest::arePerfectlyNested
static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)
Return true if the given loops OuterLoop and InnerLoop are perfectly nested with respect to each othe...
Definition: LoopNestAnalysis.cpp:53
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
STLExtras.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:1534
llvm::LoopNest::getLoop
Loop * getLoop(unsigned Index) const
Return the loop at the given Index.
Definition: LoopNestAnalysis.h:91
llvm::LoopVectorTy
SmallVector< Loop *, 8 > LoopVectorTy
Definition: LoopCacheAnalysis.h:32
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:76
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:230
llvm::LoopNestAnalysis
This analysis provides information for a loop nest.
Definition: LoopNestAnalysis.h:159
LoopInfo.h
llvm::LoopNestPrinterPass
Printer pass for the LoopNest results.
Definition: LoopNestAnalysis.h:169
llvm::LoopNestPrinterPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopNestAnalysis.cpp:377
llvm::LoopNest::MaxPerfectDepth
const unsigned MaxPerfectDepth
Definition: LoopNestAnalysis.h:151
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:478
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::LoopNest::areAllLoopsRotatedForm
bool areAllLoopsRotatedForm() const
Return true if all loops in the loop nest are in rotated form.
Definition: LoopNestAnalysis.h:139
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:241
llvm::LoopNest::skipEmptyBlockUntil
static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)
Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).
Definition: LoopNestAnalysis.cpp:208
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:96
llvm::LoopNest::getOutermostLoop
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
Definition: LoopNestAnalysis.h:71
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:391
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopNest::LoopNest
LoopNest()=delete
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::LoopNest::getParent
Function * getParent() const
Return the function to which the loop-nest belongs.
Definition: LoopNestAnalysis.h:144
llvm::LoopNest::getNumLoops
size_t getNumLoops() const
Return the number of loops in the nest.
Definition: LoopNestAnalysis.h:97
llvm::LoopNest::getLoops
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Definition: LoopNestAnalysis.h:100
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:123
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:152
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:131
llvm::LoopNestPrinterPass::LoopNestPrinterPass
LoopNestPrinterPass(raw_ostream &OS)
Definition: LoopNestAnalysis.h:173
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:788
llvm::LoopNest::getLoopNest
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
Definition: LoopNestAnalysis.cpp:48
llvm::LoopNest::areAllLoopsSimplifyForm
bool areAllLoopsSimplifyForm() const
Return true if all loops in the loop nest are in simplify form.
Definition: LoopNestAnalysis.h:134
llvm::LoopNest
This class represents a loop nest and can be used to query its properties.
Definition: LoopNestAnalysis.h:27
llvm::LoopNest::getName
StringRef getName() const
Definition: LoopNestAnalysis.h:148
llvm::LoopNest::getPerfectLoops
SmallVector< LoopVectorTy, 4 > getPerfectLoops(ScalarEvolution &SE) const
Retrieve a vector of perfect loop nests contained in the current loop nest.
Definition: LoopNestAnalysis.cpp:161