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" 18 #include "llvm/Analysis/LoopAnalysisManager.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Support/Compiler.h" 21 22 namespace llvm { 23 24 using LoopVectorTy = SmallVector<Loop *, 8>; 25 26 class LPMUpdater; 27 28 /// This class represents a loop nest and can be used to query its properties. 29 class LLVM_ABI LoopNest { 30 public: 31 using InstrVectorTy = SmallVector<const Instruction *>; 32 33 /// Construct a loop nest rooted by loop \p Root. 34 LoopNest(Loop &Root, ScalarEvolution &SE); 35 36 LoopNest() = delete; 37 38 /// Construct a LoopNest object. 39 static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE); 40 41 /// Return true if the given loops \p OuterLoop and \p InnerLoop are 42 /// perfectly nested with respect to each other, and false otherwise. 43 /// Example: 44 /// \code 45 /// for(i) 46 /// for(j) 47 /// for(k) 48 /// \endcode 49 /// arePerfectlyNested(loop_i, loop_j, SE) would return true. 50 /// arePerfectlyNested(loop_j, loop_k, SE) would return true. 51 /// arePerfectlyNested(loop_i, loop_k, SE) would return false. 52 static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, 53 ScalarEvolution &SE); 54 55 /// Return a vector of instructions that prevent the LoopNest given 56 /// by loops \p OuterLoop and \p InnerLoop from being perfect. 57 static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, 58 const Loop &InnerLoop, 59 ScalarEvolution &SE); 60 61 /// Return the maximum nesting depth of the loop nest rooted by loop \p Root. 62 /// For example given the loop nest: 63 /// \code 64 /// for(i) // loop at level 1 and Root of the nest 65 /// for(j) // loop at level 2 66 /// <code> 67 /// for(k) // loop at level 3 68 /// \endcode 69 /// getMaxPerfectDepth(Loop_i) would return 2. 70 static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE); 71 72 /// Recursivelly traverse all empty 'single successor' basic blocks of \p From 73 /// (if there are any). When \p CheckUniquePred is set to true, check if 74 /// each of the empty single successors has a unique predecessor. Return 75 /// the last basic block found or \p End if it was reached during the search. 76 static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From, 77 const BasicBlock *End, 78 bool CheckUniquePred = false); 79 80 /// Return the outermost loop in the loop nest. getOutermostLoop()81 Loop &getOutermostLoop() const { return *Loops.front(); } 82 83 /// Return the innermost loop in the loop nest if the nest has only one 84 /// innermost loop, and a nullptr otherwise. 85 /// Note: the innermost loop returned is not necessarily perfectly nested. getInnermostLoop()86 Loop *getInnermostLoop() const { 87 if (Loops.size() == 1) 88 return Loops.back(); 89 90 // The loops in the 'Loops' vector have been collected in breadth first 91 // order, therefore if the last 2 loops in it have the same nesting depth 92 // there isn't a unique innermost loop in the nest. 93 Loop *LastLoop = Loops.back(); 94 auto SecondLastLoopIter = ++Loops.rbegin(); 95 return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth()) 96 ? nullptr 97 : LastLoop; 98 } 99 100 /// Return the loop at the given \p Index. getLoop(unsigned Index)101 Loop *getLoop(unsigned Index) const { 102 assert(Index < Loops.size() && "Index is out of bounds"); 103 return Loops[Index]; 104 } 105 106 /// Get the loop index of the given loop \p L. getLoopIndex(const Loop & L)107 unsigned getLoopIndex(const Loop &L) const { 108 for (unsigned I = 0; I < getNumLoops(); ++I) 109 if (getLoop(I) == &L) 110 return I; 111 llvm_unreachable("Loop not in the loop nest"); 112 } 113 114 /// Return the number of loops in the nest. getNumLoops()115 size_t getNumLoops() const { return Loops.size(); } 116 117 /// Get the loops in the nest. getLoops()118 ArrayRef<Loop *> getLoops() const { return Loops; } 119 120 /// Get the loops in the nest at the given \p Depth. getLoopsAtDepth(unsigned Depth)121 LoopVectorTy getLoopsAtDepth(unsigned Depth) const { 122 assert(Depth >= Loops.front()->getLoopDepth() && 123 Depth <= Loops.back()->getLoopDepth() && "Invalid depth"); 124 LoopVectorTy Result; 125 for (unsigned I = 0; I < getNumLoops(); ++I) { 126 Loop *L = getLoop(I); 127 if (L->getLoopDepth() == Depth) 128 Result.push_back(L); 129 else if (L->getLoopDepth() > Depth) 130 break; 131 } 132 return Result; 133 } 134 135 /// Retrieve a vector of perfect loop nests contained in the current loop 136 /// nest. For example, given the following nest containing 4 loops, this 137 /// member function would return {{L1,L2},{L3,L4}}. 138 /// \code 139 /// for(i) // L1 140 /// for(j) // L2 141 /// <code> 142 /// for(k) // L3 143 /// for(l) // L4 144 /// \endcode 145 SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const; 146 147 /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop) 148 /// For example given the loop nest: 149 /// \code 150 /// for(i) // loop at level 1 and Root of the nest 151 /// for(j1) // loop at level 2 152 /// for(k) // loop at level 3 153 /// for(j2) // loop at level 2 154 /// \endcode 155 /// getNestDepth() would return 3. getNestDepth()156 unsigned getNestDepth() const { 157 int NestDepth = 158 Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1; 159 assert(NestDepth > 0 && "Expecting NestDepth to be at least 1"); 160 return NestDepth; 161 } 162 163 /// Return the maximum perfect nesting depth. getMaxPerfectDepth()164 unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; } 165 166 /// Return true if all loops in the loop nest are in simplify form. areAllLoopsSimplifyForm()167 bool areAllLoopsSimplifyForm() const { 168 return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); }); 169 } 170 171 /// Return true if all loops in the loop nest are in rotated form. areAllLoopsRotatedForm()172 bool areAllLoopsRotatedForm() const { 173 return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); }); 174 } 175 176 /// Return the function to which the loop-nest belongs. getParent()177 Function *getParent() const { 178 return Loops.front()->getHeader()->getParent(); 179 } 180 getName()181 StringRef getName() const { return Loops.front()->getName(); } 182 183 protected: 184 const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. 185 LoopVectorTy Loops; // the loops in the nest (in breadth first order). 186 187 private: 188 enum LoopNestEnum { 189 PerfectLoopNest, 190 ImperfectLoopNest, 191 InvalidLoopStructure, 192 OuterLoopLowerBoundUnknown 193 }; 194 static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop, 195 const Loop &InnerLoop, 196 ScalarEvolution &SE); 197 }; 198 199 LLVM_ABI raw_ostream &operator<<(raw_ostream &, const LoopNest &); 200 201 /// This analysis provides information for a loop nest. The analysis runs on 202 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>. 203 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> { 204 friend AnalysisInfoMixin<LoopNestAnalysis>; 205 LLVM_ABI static AnalysisKey Key; 206 207 public: 208 using Result = LoopNest; 209 LLVM_ABI Result run(Loop &L, LoopAnalysisManager &AM, 210 LoopStandardAnalysisResults &AR); 211 }; 212 213 /// Printer pass for the \c LoopNest results. 214 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> { 215 raw_ostream &OS; 216 217 public: LoopNestPrinterPass(raw_ostream & OS)218 explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {} 219 220 LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 221 LoopStandardAnalysisResults &AR, 222 LPMUpdater &U); 223 isRequired()224 static bool isRequired() { return true; } 225 }; 226 227 } // namespace llvm 228 229 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H 230