llvm/Analysis/LoopNestAnalysis.h

0001 //===- llvm/Analysis/LoopNestAnalysis.h -------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the interface for the loop nest analysis.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ANALYSIS_LOOPNESTANALYSIS_H
0015 #define LLVM_ANALYSIS_LOOPNESTANALYSIS_H
0016
0017 #include "llvm/ADT/STLExtras.h"
0018 #include "llvm/Analysis/LoopAnalysisManager.h"
0019 #include "llvm/Analysis/LoopInfo.h"
0020
0021 namespace llvm {
0022
0023 using LoopVectorTy = SmallVector<Loop *, 8>;
0024
0025 class LPMUpdater;
0026
0027 /// This class represents a loop nest and can be used to query its properties.
0028 class LLVM_ABI LoopNest {
0029 public:
0030   using InstrVectorTy = SmallVector<const Instruction *>;
0031
0032   /// Construct a loop nest rooted by loop \p Root.
0033   LoopNest(Loop &Root, ScalarEvolution &SE);
0034
0035   LoopNest() = delete;
0036
0037   /// Construct a LoopNest object.
0038   static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE);
0039
0040   /// Return true if the given loops \p OuterLoop and \p InnerLoop are
0041   /// perfectly nested with respect to each other, and false otherwise.
0042   /// Example:
0043   /// \code
0044   ///   for(i)
0045   ///     for(j)
0046   ///       for(k)
0047   /// \endcode
0048   /// arePerfectlyNested(loop_i, loop_j, SE) would return true.
0049   /// arePerfectlyNested(loop_j, loop_k, SE) would return true.
0050   /// arePerfectlyNested(loop_i, loop_k, SE) would return false.
0051   static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
0052                                  ScalarEvolution &SE);
0053
0054   /// Return a vector of instructions that prevent the LoopNest given
0055   /// by loops \p OuterLoop and \p InnerLoop from being perfect.
0056   static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop,
0057                                                   const Loop &InnerLoop,
0058                                                   ScalarEvolution &SE);
0059
0060   /// Return the maximum nesting depth of the loop nest rooted by loop \p Root.
0061   /// For example given the loop nest:
0062   /// \code
0063   ///   for(i)     // loop at level 1 and Root of the nest
0064   ///     for(j)   // loop at level 2
0065   ///       <code>
0066   ///       for(k) // loop at level 3
0067   /// \endcode
0068   /// getMaxPerfectDepth(Loop_i) would return 2.
0069   static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
0070
0071   /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
0072   /// (if there are any). When \p CheckUniquePred is set to true, check if
0073   /// each of the empty single successors has a unique predecessor. Return
0074   /// the last basic block found or \p End if it was reached during the search.
0075   static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
0076                                                const BasicBlock *End,
0077                                                bool CheckUniquePred = false);
0078
0079   /// Return the outermost loop in the loop nest.
0080   Loop &getOutermostLoop() const { return *Loops.front(); }
0081
0082   /// Return the innermost loop in the loop nest if the nest has only one
0083   /// innermost loop, and a nullptr otherwise.
0084   /// Note: the innermost loop returned is not necessarily perfectly nested.
0085   Loop *getInnermostLoop() const {
0086     if (Loops.size() == 1)
0087       return Loops.back();
0088
0089     // The loops in the 'Loops' vector have been collected in breadth first
0090     // order, therefore if the last 2 loops in it have the same nesting depth
0091     // there isn't a unique innermost loop in the nest.
0092     Loop *LastLoop = Loops.back();
0093     auto SecondLastLoopIter = ++Loops.rbegin();
0094     return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
0095                ? nullptr
0096                : LastLoop;
0097   }
0098
0099   /// Return the loop at the given \p Index.
0100   Loop *getLoop(unsigned Index) const {
0101     assert(Index < Loops.size() && "Index is out of bounds");
0102     return Loops[Index];
0103   }
0104
0105   /// Get the loop index of the given loop \p L.
0106   unsigned getLoopIndex(const Loop &L) const {
0107     for (unsigned I = 0; I < getNumLoops(); ++I)
0108       if (getLoop(I) == &L)
0109         return I;
0110     llvm_unreachable("Loop not in the loop nest");
0111   }
0112
0113   /// Return the number of loops in the nest.
0114   size_t getNumLoops() const { return Loops.size(); }
0115
0116   /// Get the loops in the nest.
0117   ArrayRef<Loop *> getLoops() const { return Loops; }
0118
0119   /// Get the loops in the nest at the given \p Depth.
0120   LoopVectorTy getLoopsAtDepth(unsigned Depth) const {
0121     assert(Depth >= Loops.front()->getLoopDepth() &&
0122            Depth <= Loops.back()->getLoopDepth() && "Invalid depth");
0123     LoopVectorTy Result;
0124     for (unsigned I = 0; I < getNumLoops(); ++I) {
0125       Loop *L = getLoop(I);
0126       if (L->getLoopDepth() == Depth)
0127         Result.push_back(L);
0128       else if (L->getLoopDepth() > Depth)
0129         break;
0130     }
0131     return Result;
0132   }
0133
0134   /// Retrieve a vector of perfect loop nests contained in the current loop
0135   /// nest. For example, given the following  nest containing 4 loops, this
0136   /// member function would return {{L1,L2},{L3,L4}}.
0137   /// \code
0138   ///   for(i) // L1
0139   ///     for(j) // L2
0140   ///       <code>
0141   ///       for(k) // L3
0142   ///         for(l) // L4
0143   /// \endcode
0144   SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const;
0145
0146   /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
0147   /// For example given the loop nest:
0148   /// \code
0149   ///   for(i)      // loop at level 1 and Root of the nest
0150   ///     for(j1)   // loop at level 2
0151   ///       for(k)  // loop at level 3
0152   ///     for(j2)   // loop at level 2
0153   /// \endcode
0154   /// getNestDepth() would return 3.
0155   unsigned getNestDepth() const {
0156     int NestDepth =
0157         Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
0158     assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
0159     return NestDepth;
0160   }
0161
0162   /// Return the maximum perfect nesting depth.
0163   unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
0164
0165   /// Return true if all loops in the loop nest are in simplify form.
0166   bool areAllLoopsSimplifyForm() const {
0167     return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
0168   }
0169
0170   /// Return true if all loops in the loop nest are in rotated form.
0171   bool areAllLoopsRotatedForm() const {
0172     return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
0173   }
0174
0175   /// Return the function to which the loop-nest belongs.
0176   Function *getParent() const {
0177     return Loops.front()->getHeader()->getParent();
0178   }
0179
0180   StringRef getName() const { return Loops.front()->getName(); }
0181
0182 protected:
0183   const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
0184   LoopVectorTy Loops; // the loops in the nest (in breadth first order).
0185
0186 private:
0187   enum LoopNestEnum {
0188     PerfectLoopNest,
0189     ImperfectLoopNest,
0190     InvalidLoopStructure,
0191     OuterLoopLowerBoundUnknown
0192   };
0193   static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop,
0194                                                     const Loop &InnerLoop,
0195                                                     ScalarEvolution &SE);
0196 };
0197
0198 raw_ostream &operator<<(raw_ostream &, const LoopNest &);
0199
0200 /// This analysis provides information for a loop nest. The analysis runs on
0201 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
0202 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
0203   friend AnalysisInfoMixin<LoopNestAnalysis>;
0204   static AnalysisKey Key;
0205
0206 public:
0207   using Result = LoopNest;
0208   Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
0209 };
0210
0211 /// Printer pass for the \c LoopNest results.
0212 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
0213   raw_ostream &OS;
0214
0215 public:
0216   explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
0217
0218   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
0219                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
0220
0221   static bool isRequired() { return true; }
0222 };
0223
0224 } // namespace llvm
0225
0226 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H