Pirama Arumuga Nainar | d285ad0 | 2022-02-08 09:26:56 -0800 | [diff] [blame] | 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 | /// 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> { |
| 180 | friend AnalysisInfoMixin<LoopNestAnalysis>; |
| 181 | static AnalysisKey Key; |
| 182 | |
| 183 | public: |
| 184 | using Result = LoopNest; |
| 185 | Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); |
| 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 | |
| 195 | PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, |
| 196 | LoopStandardAnalysisResults &AR, LPMUpdater &U); |
| 197 | }; |
| 198 | |
| 199 | } // namespace llvm |
| 200 | |
| 201 | #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H |