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/Analysis/LoopAnalysisManager.h" 18 #include "llvm/Analysis/LoopInfo.h" 19 20 namespace llvm { 21 22 using LoopVectorTy = SmallVector<Loop *, 8>; 23 class LPMUpdater; 24 25 /// This class represents a loop nest and can be used to query its properties. 26 class LoopNest { 27 public: 28 /// Construct a loop nest rooted by loop \p Root. 29 LoopNest(Loop &Root, ScalarEvolution &SE); 30 31 LoopNest() = delete; 32 LoopNest &operator=(const LoopNest &) = delete; 33 34 /// Construct a LoopNest object. 35 static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE); 36 37 /// Return true if the given loops \p OuterLoop and \p InnerLoop are 38 /// perfectly nested with respect to each other, and false otherwise. 39 /// Example: 40 /// \code 41 /// for(i) 42 /// for(j) 43 /// for(k) 44 /// \endcode 45 /// arePerfectlyNested(loop_i, loop_j, SE) would return true. 46 /// arePerfectlyNested(loop_j, loop_k, SE) would return true. 47 /// arePerfectlyNested(loop_i, loop_k, SE) would return false. 48 static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, 49 ScalarEvolution &SE); 50 51 /// Return the maximum nesting depth of the loop nest rooted by loop \p Root. 52 /// For example given the loop nest: 53 /// \code 54 /// for(i) // loop at level 1 and Root of the nest 55 /// for(j) // loop at level 2 56 /// <code> 57 /// for(k) // loop at level 3 58 /// \endcode 59 /// getMaxPerfectDepth(Loop_i) would return 2. 60 static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE); 61 62 /// Return the outermost loop in the loop nest. getOutermostLoop()63 Loop &getOutermostLoop() const { return *Loops.front(); } 64 65 /// Return the innermost loop in the loop nest if the nest has only one 66 /// innermost loop, and a nullptr otherwise. 67 /// Note: the innermost loop returned is not necessarily perfectly nested. getInnermostLoop()68 Loop *getInnermostLoop() const { 69 if (Loops.size() == 1) 70 return Loops.back(); 71 72 // The loops in the 'Loops' vector have been collected in breadth first 73 // order, therefore if the last 2 loops in it have the same nesting depth 74 // there isn't a unique innermost loop in the nest. 75 Loop *LastLoop = Loops.back(); 76 auto SecondLastLoopIter = ++Loops.rbegin(); 77 return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth()) 78 ? nullptr 79 : LastLoop; 80 } 81 82 /// Return the loop at the given \p Index. getLoop(unsigned Index)83 Loop *getLoop(unsigned Index) const { 84 assert(Index < Loops.size() && "Index is out of bounds"); 85 return Loops[Index]; 86 } 87 88 /// Return the number of loops in the nest. getNumLoops()89 size_t getNumLoops() const { return Loops.size(); } 90 91 /// Get the loops in the nest. getLoops()92 ArrayRef<Loop *> getLoops() const { return Loops; } 93 94 /// Retrieve a vector of perfect loop nests contained in the current loop 95 /// nest. For example, given the following nest containing 4 loops, this 96 /// member function would return {{L1,L2},{L3,L4}}. 97 /// \code 98 /// for(i) // L1 99 /// for(j) // L2 100 /// <code> 101 /// for(k) // L3 102 /// for(l) // L4 103 /// \endcode 104 SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const; 105 106 /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop) 107 /// For example given the loop nest: 108 /// \code 109 /// for(i) // loop at level 1 and Root of the nest 110 /// for(j1) // loop at level 2 111 /// for(k) // loop at level 3 112 /// for(j2) // loop at level 2 113 /// \endcode 114 /// getNestDepth() would return 3. getNestDepth()115 unsigned getNestDepth() const { 116 int NestDepth = 117 Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1; 118 assert(NestDepth > 0 && "Expecting NestDepth to be at least 1"); 119 return NestDepth; 120 } 121 122 /// Return the maximum perfect nesting depth. getMaxPerfectDepth()123 unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; } 124 125 /// Return true if all loops in the loop nest are in simplify form. areAllLoopsSimplifyForm()126 bool areAllLoopsSimplifyForm() const { 127 return llvm::all_of(Loops, 128 [](const Loop *L) { return L->isLoopSimplifyForm(); }); 129 } 130 131 protected: 132 const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. 133 LoopVectorTy Loops; // the loops in the nest (in breadth first order). 134 }; 135 136 raw_ostream &operator<<(raw_ostream &, const LoopNest &); 137 138 /// This analysis provides information for a loop nest. The analysis runs on 139 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>. 140 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> { 141 friend AnalysisInfoMixin<LoopNestAnalysis>; 142 static AnalysisKey Key; 143 144 public: 145 using Result = LoopNest; 146 Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); 147 }; 148 149 /// Printer pass for the \c LoopNest results. 150 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> { 151 raw_ostream &OS; 152 153 public: LoopNestPrinterPass(raw_ostream & OS)154 explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {} 155 156 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 157 LoopStandardAnalysisResults &AR, LPMUpdater &U); 158 }; 159 160 } // namespace llvm 161 162 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H 163