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  LoopNest &operator=(const LoopNest &) = delete;
34 
35  /// Construct a LoopNest object.
36  static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE);
37 
38  /// Return true if the given loops \p OuterLoop and \p InnerLoop are
39  /// perfectly nested with respect to each other, and false otherwise.
40  /// Example:
41  /// \code
42  /// for(i)
43  /// for(j)
44  /// for(k)
45  /// \endcode
46  /// arePerfectlyNested(loop_i, loop_j, SE) would return true.
47  /// arePerfectlyNested(loop_j, loop_k, SE) would return true.
48  /// arePerfectlyNested(loop_i, loop_k, SE) would return false.
49  static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
50  ScalarEvolution &SE);
51 
52  /// Return the maximum nesting depth of the loop nest rooted by loop \p Root.
53  /// For example given the loop nest:
54  /// \code
55  /// for(i) // loop at level 1 and Root of the nest
56  /// for(j) // loop at level 2
57  /// <code>
58  /// for(k) // loop at level 3
59  /// \endcode
60  /// getMaxPerfectDepth(Loop_i) would return 2.
61  static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
62 
63  /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
64  /// (if there are any). When \p CheckUniquePred is set to true, check if
65  /// each of the empty single successors has a unique predecessor. Return
66  /// the last basic block found or \p End if it was reached during the search.
67  static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
68  const BasicBlock *End,
69  bool CheckUniquePred = false);
70 
71  /// Return the outermost loop in the loop nest.
72  Loop &getOutermostLoop() const { return *Loops.front(); }
73 
74  /// Return the innermost loop in the loop nest if the nest has only one
75  /// innermost loop, and a nullptr otherwise.
76  /// Note: the innermost loop returned is not necessarily perfectly nested.
78  if (Loops.size() == 1)
79  return Loops.back();
80 
81  // The loops in the 'Loops' vector have been collected in breadth first
82  // order, therefore if the last 2 loops in it have the same nesting depth
83  // there isn't a unique innermost loop in the nest.
84  Loop *LastLoop = Loops.back();
85  auto SecondLastLoopIter = ++Loops.rbegin();
86  return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
87  ? nullptr
88  : LastLoop;
89  }
90 
91  /// Return the loop at the given \p Index.
92  Loop *getLoop(unsigned Index) const {
93  assert(Index < Loops.size() && "Index is out of bounds");
94  return Loops[Index];
95  }
96 
97  /// Return the number of loops in the nest.
98  size_t getNumLoops() const { return Loops.size(); }
99 
100  /// Get the loops in the nest.
101  ArrayRef<Loop *> getLoops() const { return Loops; }
102 
103  /// Retrieve a vector of perfect loop nests contained in the current loop
104  /// nest. For example, given the following nest containing 4 loops, this
105  /// member function would return {{L1,L2},{L3,L4}}.
106  /// \code
107  /// for(i) // L1
108  /// for(j) // L2
109  /// <code>
110  /// for(k) // L3
111  /// for(l) // L4
112  /// \endcode
114 
115  /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
116  /// For example given the loop nest:
117  /// \code
118  /// for(i) // loop at level 1 and Root of the nest
119  /// for(j1) // loop at level 2
120  /// for(k) // loop at level 3
121  /// for(j2) // loop at level 2
122  /// \endcode
123  /// getNestDepth() would return 3.
124  unsigned getNestDepth() const {
125  int NestDepth =
126  Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
127  assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
128  return NestDepth;
129  }
130 
131  /// Return the maximum perfect nesting depth.
132  unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
133 
134  /// Return true if all loops in the loop nest are in simplify form.
135  bool areAllLoopsSimplifyForm() const {
136  return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
137  }
138 
139  /// Return true if all loops in the loop nest are in rotated form.
140  bool areAllLoopsRotatedForm() const {
141  return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
142  }
143 
144  /// Return the function to which the loop-nest belongs.
145  Function *getParent() const {
146  return Loops.front()->getHeader()->getParent();
147  }
148 
149  StringRef getName() const { return Loops.front()->getName(); }
150 
151 protected:
152  const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
153  LoopVectorTy Loops; // the loops in the nest (in breadth first order).
154 };
155 
157 
158 /// This analysis provides information for a loop nest. The analysis runs on
159 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
160 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
162  static AnalysisKey Key;
163 
164 public:
165  using Result = LoopNest;
167 };
168 
169 /// Printer pass for the \c LoopNest results.
170 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
171  raw_ostream &OS;
172 
173 public:
174  explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
175 
178 };
179 
180 } // namespace llvm
181 
182 #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
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:1167
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:1482
llvm::LoopNest::getLoop
Loop * getLoop(unsigned Index) const
Return the loop at the given Index.
Definition: LoopNestAnalysis.h:92
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:77
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
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:160
LoopInfo.h
llvm::LoopNestPrinterPass
Printer pass for the LoopNest results.
Definition: LoopNestAnalysis.h:170
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:152
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:140
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:240
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:72
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::operator=
LoopNest & operator=(const LoopNest &)=delete
llvm::LoopNest::getParent
Function * getParent() const
Return the function to which the loop-nest belongs.
Definition: LoopNestAnalysis.h:145
llvm::LoopNest::getNumLoops
size_t getNumLoops() const
Return the number of loops in the nest.
Definition: LoopNestAnalysis.h:98
llvm::LoopNest::getLoops
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Definition: LoopNestAnalysis.h:101
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:124
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:153
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:132
llvm::LoopNestPrinterPass::LoopNestPrinterPass
LoopNestPrinterPass(raw_ostream &OS)
Definition: LoopNestAnalysis.h:174
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:785
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:135
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:149
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