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