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 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. 28 class LLVM_EXTERNAL_VISIBILITY LoopNest { 29 public: 30 using InstrVectorTy = SmallVector<const Instruction *>; 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. 85 Loop *getInnermostLoop() const { 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 /// Get the loop index of the given loop \p L. 106 unsigned getLoopIndex(const Loop &L) const { 107 for (unsigned I = 0; I < getNumLoops(); ++I) 108 if (getLoop(I) == &L) 109 return I; 110 llvm_unreachable("Loop not in the loop nest"); 111 } 112 113 /// Return the number of loops in the nest. 114 size_t getNumLoops() const { return Loops.size(); } 115 116 /// Get the loops in the nest. 117 ArrayRef<Loop *> getLoops() const { return Loops; } 118 119 /// Get the loops in the nest at the given \p Depth. 120 LoopVectorTy getLoopsAtDepth(unsigned Depth) const { 121 assert(Depth >= Loops.front()->getLoopDepth() && 122 Depth <= Loops.back()->getLoopDepth() && "Invalid depth"); 123 LoopVectorTy Result; 124 for (unsigned I = 0; I < getNumLoops(); ++I) { 125 Loop *L = getLoop(I); 126 if (L->getLoopDepth() == Depth) 127 Result.push_back(L); 128 else if (L->getLoopDepth() > Depth) 129 break; 130 } 131 return Result; 132 } 133 134 /// Retrieve a vector of perfect loop nests contained in the current loop 135 /// nest. For example, given the following nest containing 4 loops, this 136 /// member function would return {{L1,L2},{L3,L4}}. 137 /// \code 138 /// for(i) // L1 139 /// for(j) // L2 140 /// <code> 141 /// for(k) // L3 142 /// for(l) // L4 143 /// \endcode 144 SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const; 145 146 /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop) 147 /// For example given the loop nest: 148 /// \code 149 /// for(i) // loop at level 1 and Root of the nest 150 /// for(j1) // loop at level 2 151 /// for(k) // loop at level 3 152 /// for(j2) // loop at level 2 153 /// \endcode 154 /// getNestDepth() would return 3. 155 unsigned getNestDepth() const { 156 int NestDepth = 157 Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1; 158 assert(NestDepth > 0 && "Expecting NestDepth to be at least 1"); 159 return NestDepth; 160 } 161 162 /// Return the maximum perfect nesting depth. 163 unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; } 164 165 /// Return true if all loops in the loop nest are in simplify form. 166 bool areAllLoopsSimplifyForm() const { 167 return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); }); 168 } 169 170 /// Return true if all loops in the loop nest are in rotated form. 171 bool areAllLoopsRotatedForm() const { 172 return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); }); 173 } 174 175 /// Return the function to which the loop-nest belongs. 176 Function *getParent() const { 177 return Loops.front()->getHeader()->getParent(); 178 } 179 180 StringRef getName() const { return Loops.front()->getName(); } 181 182 protected: 183 const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. 184 LoopVectorTy Loops; // the loops in the nest (in breadth first order). 185 186 private: 187 enum LoopNestEnum { 188 PerfectLoopNest, 189 ImperfectLoopNest, 190 InvalidLoopStructure, 191 OuterLoopLowerBoundUnknown 192 }; 193 static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop, 194 const Loop &InnerLoop, 195 ScalarEvolution &SE); 196 }; 197 198 raw_ostream &operator<<(raw_ostream &, const LoopNest &); 199 200 /// This analysis provides information for a loop nest. The analysis runs on 201 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>. 202 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> { 203 friend AnalysisInfoMixin<LoopNestAnalysis>; 204 static AnalysisKey Key; 205 206 public: 207 using Result = LoopNest; 208 Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); 209 }; 210 211 /// Printer pass for the \c LoopNest results. 212 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> { 213 raw_ostream &OS; 214 215 public: 216 explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {} 217 218 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 219 LoopStandardAnalysisResults &AR, LPMUpdater &U); 220 }; 221 222 } // namespace llvm 223 224 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H 225