LLVM  14.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  /// Return the number of loops in the nest.
106  size_t getNumLoops() const { return Loops.size(); }
107 
108  /// Get the loops in the nest.
109  ArrayRef<Loop *> getLoops() const { return Loops; }
110 
111  /// Retrieve a vector of perfect loop nests contained in the current loop
112  /// nest. For example, given the following nest containing 4 loops, this
113  /// member function would return {{L1,L2},{L3,L4}}.
114  /// \code
115  /// for(i) // L1
116  /// for(j) // L2
117  /// <code>
118  /// for(k) // L3
119  /// for(l) // L4
120  /// \endcode
121  SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const;
122 
123  /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
124  /// For example given the loop nest:
125  /// \code
126  /// for(i) // loop at level 1 and Root of the nest
127  /// for(j1) // loop at level 2
128  /// for(k) // loop at level 3
129  /// for(j2) // loop at level 2
130  /// \endcode
131  /// getNestDepth() would return 3.
132  unsigned getNestDepth() const {
133  int NestDepth =
134  Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
135  assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
136  return NestDepth;
137  }
138 
139  /// Return the maximum perfect nesting depth.
140  unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
141 
142  /// Return true if all loops in the loop nest are in simplify form.
143  bool areAllLoopsSimplifyForm() const {
144  return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
145  }
146 
147  /// Return true if all loops in the loop nest are in rotated form.
148  bool areAllLoopsRotatedForm() const {
149  return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
150  }
151 
152  /// Return the function to which the loop-nest belongs.
153  Function *getParent() const {
154  return Loops.front()->getHeader()->getParent();
155  }
156 
157  StringRef getName() const { return Loops.front()->getName(); }
158 
159 protected:
160  const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
161  LoopVectorTy Loops; // the loops in the nest (in breadth first order).
162 
163 private:
164  enum LoopNestEnum {
165  PerfectLoopNest,
166  ImperfectLoopNest,
167  InvalidLoopStructure,
168  OuterLoopLowerBoundUnknown
169  };
170  static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop,
171  const Loop &InnerLoop,
172  ScalarEvolution &SE);
173 };
174 
175 raw_ostream &operator<<(raw_ostream &, const LoopNest &);
176 
177 /// This analysis provides information for a loop nest. The analysis runs on
178 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
179 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
181  static AnalysisKey Key;
182 
183 public:
184  using Result = LoopNest;
186 };
187 
188 /// Printer pass for the \c LoopNest results.
189 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
190  raw_ostream &OS;
191 
192 public:
193  explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
194 
197 };
198 
199 } // namespace llvm
200 
201 #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
This file implements support for optimizing divisions by a constant.
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:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
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::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
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:1551
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: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: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:230
llvm::LoopNestAnalysis
This analysis provides information for a loop nest.
Definition: LoopNestAnalysis.h:179
LoopInfo.h
llvm::LoopNestPrinterPass
Printer pass for the LoopNest results.
Definition: LoopNestAnalysis.h:189
llvm::LoopNestPrinterPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopNestAnalysis.cpp:458
llvm::LoopNest::MaxPerfectDepth
const unsigned MaxPerfectDepth
Definition: LoopNestAnalysis.h:160
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:148
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
LLVM_EXTERNAL_VISIBILITY
#define LLVM_EXTERNAL_VISIBILITY
Definition: Compiler.h:132
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:80
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
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:58
llvm::LoopNest::getParent
Function * getParent() const
Return the function to which the loop-nest belongs.
Definition: LoopNestAnalysis.h:153
llvm::LoopNest::getNumLoops
size_t getNumLoops() const
Return the number of loops in the nest.
Definition: LoopNestAnalysis.h:106
llvm::LoopNest::getLoops
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Definition: LoopNestAnalysis.h:109
llvm::LoopNest::getNestDepth
unsigned getNestDepth() const
Return the loop nest depth (i.e.
Definition: LoopNestAnalysis.h:132
llvm::LoopNest::Loops
LoopVectorTy Loops
Definition: LoopNestAnalysis.h:161
llvm::LoopNest::getMaxPerfectDepth
unsigned getMaxPerfectDepth() const
Return the maximum perfect nesting depth.
Definition: LoopNestAnalysis.h:140
llvm::LoopNestPrinterPass::LoopNestPrinterPass
LoopNestPrinterPass(raw_ostream &OS)
Definition: LoopNestAnalysis.h:193
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::areAllLoopsSimplifyForm
bool areAllLoopsSimplifyForm() const
Return true if all loops in the loop nest are in simplify form.
Definition: LoopNestAnalysis.h:143
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:157