contrib/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

   1 //===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 ///
  11 /// This header provides classes for managing a pipeline of passes over loops
  12 /// in LLVM IR.
  13 ///
  14 /// The primary loop pass pipeline is managed in a very particular way to
  15 /// provide a set of core guarantees:
  16 /// 1) Loops are, where possible, in simplified form.
  17 /// 2) Loops are *always* in LCSSA form.
  18 /// 3) A collection of Loop-specific analysis results are available:
  19 ///    - LoopInfo
  20 ///    - DominatorTree
  21 ///    - ScalarEvolution
  22 ///    - AAManager
  23 /// 4) All loop passes preserve #1 (where possible), #2, and #3.
  24 /// 5) Loop passes run over each loop in the loop nest from the innermost to
  25 ///    the outermost. Specifically, all inner loops are processed before
  26 ///    passes run over outer loops. When running the pipeline across an inner
  27 ///    loop creates new inner loops, those are added and processed in this
  28 ///    order as well.
  29 ///
  30 /// This process is designed to facilitate transformations which simplify,
  31 /// reduce, and remove loops. For passes which are more oriented towards
  32 /// optimizing loops, especially optimizing loop *nests* instead of single
  33 /// loops in isolation, this framework is less interesting.
  34 ///
  35 //===----------------------------------------------------------------------===//
  36
  37 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
  38 #define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
  39
  40 #include "llvm/ADT/PostOrderIterator.h"
  41 #include "llvm/ADT/PriorityWorklist.h"
  42 #include "llvm/ADT/STLExtras.h"
  43 #include "llvm/Analysis/AliasAnalysis.h"
  44 #include "llvm/Analysis/BasicAliasAnalysis.h"
  45 #include "llvm/Analysis/GlobalsModRef.h"
  46 #include "llvm/Analysis/LoopAnalysisManager.h"
  47 #include "llvm/Analysis/LoopInfo.h"
  48 #include "llvm/Analysis/ScalarEvolution.h"
  49 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  50 #include "llvm/Analysis/TargetLibraryInfo.h"
  51 #include "llvm/Analysis/TargetTransformInfo.h"
  52 #include "llvm/IR/Dominators.h"
  53 #include "llvm/IR/PassManager.h"
  54 #include "llvm/Transforms/Utils/LCSSA.h"
  55 #include "llvm/Transforms/Utils/LoopSimplify.h"
  56
  57 namespace llvm {
  58
  59 // Forward declarations of an update tracking API used in the pass manager.
  60 class LPMUpdater;
  61
  62 // Explicit specialization and instantiation declarations for the pass manager.
  63 // See the comments on the definition of the specialization for details on how
  64 // it differs from the primary template.
  65 template <>
  66 PreservedAnalyses
  67 PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
  68             LPMUpdater &>::run(Loop &InitialL, LoopAnalysisManager &AM,
  69                                LoopStandardAnalysisResults &AnalysisResults,
  70                                LPMUpdater &U);
  71 extern template class PassManager<Loop, LoopAnalysisManager,
  72                                   LoopStandardAnalysisResults &, LPMUpdater &>;
  73
  74 /// The Loop pass manager.
  75 ///
  76 /// See the documentation for the PassManager template for details. It runs
  77 /// a sequence of Loop passes over each Loop that the manager is run over. This
  78 /// typedef serves as a convenient way to refer to this construct.
  79 typedef PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
  80                     LPMUpdater &>
  81     LoopPassManager;
  82
  83 /// A partial specialization of the require analysis template pass to forward
  84 /// the extra parameters from a transformation's run method to the
  85 /// AnalysisManager's getResult.
  86 template <typename AnalysisT>
  87 struct RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
  88                            LoopStandardAnalysisResults &, LPMUpdater &>
  89     : PassInfoMixin<
  90           RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
  91                               LoopStandardAnalysisResults &, LPMUpdater &>> {
  92   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
  93                         LoopStandardAnalysisResults &AR, LPMUpdater &) {
  94     (void)AM.template getResult<AnalysisT>(L, AR);
  95     return PreservedAnalyses::all();
  96   }
  97 };
  98
  99 /// An alias template to easily name a require analysis loop pass.
 100 template <typename AnalysisT>
 101 using RequireAnalysisLoopPass =
 102     RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
 103                         LoopStandardAnalysisResults &, LPMUpdater &>;
 104
 105 namespace internal {
 106 /// Helper to implement appending of loops onto a worklist.
 107 ///
 108 /// We want to process loops in postorder, but the worklist is a LIFO data
 109 /// structure, so we append to it in *reverse* postorder.
 110 ///
 111 /// For trees, a preorder traversal is a viable reverse postorder, so we
 112 /// actually append using a preorder walk algorithm.
 113 template <typename RangeT>
 114 inline void appendLoopsToWorklist(RangeT &&Loops,
 115                                   SmallPriorityWorklist<Loop *, 4> &Worklist) {
 116   // We use an internal worklist to build up the preorder traversal without
 117   // recursion.
 118   SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
 119
 120   // We walk the initial sequence of loops in reverse because we generally want
 121   // to visit defs before uses and the worklist is LIFO.
 122   for (Loop *RootL : reverse(Loops)) {
 123     assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
 124     assert(PreOrderWorklist.empty() &&
 125            "Must start with an empty preorder walk worklist.");
 126     PreOrderWorklist.push_back(RootL);
 127     do {
 128       Loop *L = PreOrderWorklist.pop_back_val();
 129       PreOrderWorklist.append(L->begin(), L->end());
 130       PreOrderLoops.push_back(L);
 131     } while (!PreOrderWorklist.empty());
 132
 133     Worklist.insert(std::move(PreOrderLoops));
 134     PreOrderLoops.clear();
 135   }
 136 }
 137 }
 138
 139 template <typename LoopPassT> class FunctionToLoopPassAdaptor;
 140
 141 /// This class provides an interface for updating the loop pass manager based
 142 /// on mutations to the loop nest.
 143 ///
 144 /// A reference to an instance of this class is passed as an argument to each
 145 /// Loop pass, and Loop passes should use it to update LPM infrastructure if
 146 /// they modify the loop nest structure.
 147 class LPMUpdater {
 148 public:
 149   /// This can be queried by loop passes which run other loop passes (like pass
 150   /// managers) to know whether the loop needs to be skipped due to updates to
 151   /// the loop nest.
 152   ///
 153   /// If this returns true, the loop object may have been deleted, so passes
 154   /// should take care not to touch the object.
 155   bool skipCurrentLoop() const { return SkipCurrentLoop; }
 156
 157   /// Loop passes should use this method to indicate they have deleted a loop
 158   /// from the nest.
 159   ///
 160   /// Note that this loop must either be the current loop or a subloop of the
 161   /// current loop. This routine must be called prior to removing the loop from
 162   /// the loop nest.
 163   ///
 164   /// If this is called for the current loop, in addition to clearing any
 165   /// state, this routine will mark that the current loop should be skipped by
 166   /// the rest of the pass management infrastructure.
 167   void markLoopAsDeleted(Loop &L, llvm::StringRef Name) {
 168     LAM.clear(L, Name);
 169     assert((&L == CurrentL || CurrentL->contains(&L)) &&
 170            "Cannot delete a loop outside of the "
 171            "subloop tree currently being processed.");
 172     if (&L == CurrentL)
 173       SkipCurrentLoop = true;
 174   }
 175
 176   /// Loop passes should use this method to indicate they have added new child
 177   /// loops of the current loop.
 178   ///
 179   /// \p NewChildLoops must contain only the immediate children. Any nested
 180   /// loops within them will be visited in postorder as usual for the loop pass
 181   /// manager.
 182   void addChildLoops(ArrayRef<Loop *> NewChildLoops) {
 183     // Insert ourselves back into the worklist first, as this loop should be
 184     // revisited after all the children have been processed.
 185     Worklist.insert(CurrentL);
 186
 187 #ifndef NDEBUG
 188     for (Loop *NewL : NewChildLoops)
 189       assert(NewL->getParentLoop() == CurrentL && "All of the new loops must "
 190                                                   "be immediate children of "
 191                                                   "the current loop!");
 192 #endif
 193
 194     internal::appendLoopsToWorklist(NewChildLoops, Worklist);
 195
 196     // Also skip further processing of the current loop--it will be revisited
 197     // after all of its newly added children are accounted for.
 198     SkipCurrentLoop = true;
 199   }
 200
 201   /// Loop passes should use this method to indicate they have added new
 202   /// sibling loops to the current loop.
 203   ///
 204   /// \p NewSibLoops must only contain the immediate sibling loops. Any nested
 205   /// loops within them will be visited in postorder as usual for the loop pass
 206   /// manager.
 207   void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {
 208 #ifndef NDEBUG
 209     for (Loop *NewL : NewSibLoops)
 210       assert(NewL->getParentLoop() == ParentL &&
 211              "All of the new loops must be siblings of the current loop!");
 212 #endif
 213
 214     internal::appendLoopsToWorklist(NewSibLoops, Worklist);
 215
 216     // No need to skip the current loop or revisit it, as sibling loops
 217     // shouldn't impact anything.
 218   }
 219
 220   /// Restart the current loop.
 221   ///
 222   /// Loop passes should call this method to indicate the current loop has been
 223   /// sufficiently changed that it should be re-visited from the begining of
 224   /// the loop pass pipeline rather than continuing.
 225   void revisitCurrentLoop() {
 226     // Tell the currently in-flight pipeline to stop running.
 227     SkipCurrentLoop = true;
 228
 229     // And insert ourselves back into the worklist.
 230     Worklist.insert(CurrentL);
 231   }
 232
 233 private:
 234   template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor;
 235
 236   /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.
 237   SmallPriorityWorklist<Loop *, 4> &Worklist;
 238
 239   /// The analysis manager for use in the current loop nest.
 240   LoopAnalysisManager &LAM;
 241
 242   Loop *CurrentL;
 243   bool SkipCurrentLoop;
 244
 245 #ifndef NDEBUG
 246   // In debug builds we also track the parent loop to implement asserts even in
 247   // the face of loop deletion.
 248   Loop *ParentL;
 249 #endif
 250
 251   LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
 252              LoopAnalysisManager &LAM)
 253       : Worklist(Worklist), LAM(LAM) {}
 254 };
 255
 256 /// Adaptor that maps from a function to its loops.
 257 ///
 258 /// Designed to allow composition of a LoopPass(Manager) and a
 259 /// FunctionPassManager. Note that if this pass is constructed with a \c
 260 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
 261 /// analysis prior to running the loop passes over the function to enable a \c
 262 /// LoopAnalysisManager to be used within this run safely.
 263 template <typename LoopPassT>
 264 class FunctionToLoopPassAdaptor
 265     : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
 266 public:
 267   explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false)
 268       : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging) {
 269     LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
 270     LoopCanonicalizationFPM.addPass(LCSSAPass());
 271   }
 272
 273   /// Runs the loop passes across every loop in the function.
 274   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
 275     // Before we even compute any loop analyses, first run a miniature function
 276     // pass pipeline to put loops into their canonical form. Note that we can
 277     // directly build up function analyses after this as the function pass
 278     // manager handles all the invalidation at that layer.
 279     PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM);
 280
 281     // Get the loop structure for this function
 282     LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 283
 284     // If there are no loops, there is nothing to do here.
 285     if (LI.empty())
 286       return PA;
 287
 288     // Get the analysis results needed by loop passes.
 289     MemorySSA *MSSA = EnableMSSALoopDependency
 290                           ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
 291                           : nullptr;
 292     LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
 293                                        AM.getResult<AssumptionAnalysis>(F),
 294                                        AM.getResult<DominatorTreeAnalysis>(F),
 295                                        AM.getResult<LoopAnalysis>(F),
 296                                        AM.getResult<ScalarEvolutionAnalysis>(F),
 297                                        AM.getResult<TargetLibraryAnalysis>(F),
 298                                        AM.getResult<TargetIRAnalysis>(F),
 299                                        MSSA};
 300
 301     // Setup the loop analysis manager from its proxy. It is important that
 302     // this is only done when there are loops to process and we have built the
 303     // LoopStandardAnalysisResults object. The loop analyses cached in this
 304     // manager have access to those analysis results and so it must invalidate
 305     // itself when they go away.
 306     LoopAnalysisManager &LAM =
 307         AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
 308
 309     // A postorder worklist of loops to process.
 310     SmallPriorityWorklist<Loop *, 4> Worklist;
 311
 312     // Register the worklist and loop analysis manager so that loop passes can
 313     // update them when they mutate the loop nest structure.
 314     LPMUpdater Updater(Worklist, LAM);
 315
 316     // Add the loop nests in the reverse order of LoopInfo. For some reason,
 317     // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
 318     // the purpose of unrolling, loop deletion, and LICM, we largely want to
 319     // work forward across the CFG so that we visit defs before uses and can
 320     // propagate simplifications from one loop nest into the next.
 321     // FIXME: Consider changing the order in LoopInfo.
 322     internal::appendLoopsToWorklist(reverse(LI), Worklist);
 323
 324     do {
 325       Loop *L = Worklist.pop_back_val();
 326
 327       // Reset the update structure for this loop.
 328       Updater.CurrentL = L;
 329       Updater.SkipCurrentLoop = false;
 330
 331 #ifndef NDEBUG
 332       // Save a parent loop pointer for asserts.
 333       Updater.ParentL = L->getParentLoop();
 334
 335       // Verify the loop structure and LCSSA form before visiting the loop.
 336       L->verifyLoop();
 337       assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
 338              "Loops must remain in LCSSA form!");
 339 #endif
 340
 341       PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
 342       // FIXME: We should verify the set of analyses relevant to Loop passes
 343       // are preserved.
 344
 345       // If the loop hasn't been deleted, we need to handle invalidation here.
 346       if (!Updater.skipCurrentLoop())
 347         // We know that the loop pass couldn't have invalidated any other
 348         // loop's analyses (that's the contract of a loop pass), so directly
 349         // handle the loop analysis manager's invalidation here.
 350         LAM.invalidate(*L, PassPA);
 351
 352       // Then intersect the preserved set so that invalidation of module
 353       // analyses will eventually occur when the module pass completes.
 354       PA.intersect(std::move(PassPA));
 355     } while (!Worklist.empty());
 356
 357     // By definition we preserve the proxy. We also preserve all analyses on
 358     // Loops. This precludes *any* invalidation of loop analyses by the proxy,
 359     // but that's OK because we've taken care to invalidate analyses in the
 360     // loop analysis manager incrementally above.
 361     PA.preserveSet<AllAnalysesOn<Loop>>();
 362     PA.preserve<LoopAnalysisManagerFunctionProxy>();
 363     // We also preserve the set of standard analyses.
 364     PA.preserve<DominatorTreeAnalysis>();
 365     PA.preserve<LoopAnalysis>();
 366     PA.preserve<ScalarEvolutionAnalysis>();
 367     // FIXME: Uncomment this when all loop passes preserve MemorySSA
 368     // PA.preserve<MemorySSAAnalysis>();
 369     // FIXME: What we really want to do here is preserve an AA category, but
 370     // that concept doesn't exist yet.
 371     PA.preserve<AAManager>();
 372     PA.preserve<BasicAA>();
 373     PA.preserve<GlobalsAA>();
 374     PA.preserve<SCEVAA>();
 375     return PA;
 376   }
 377
 378 private:
 379   LoopPassT Pass;
 380
 381   FunctionPassManager LoopCanonicalizationFPM;
 382 };
 383
 384 /// A function to deduce a loop pass type and wrap it in the templated
 385 /// adaptor.
 386 template <typename LoopPassT>
 387 FunctionToLoopPassAdaptor<LoopPassT>
 388 createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) {
 389   return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), DebugLogging);
 390 }
 391
 392 /// Pass for printing a loop's contents as textual IR.
 393 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
 394   raw_ostream &OS;
 395   std::string Banner;
 396
 397 public:
 398   PrintLoopPass();
 399   PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
 400
 401   PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
 402                         LoopStandardAnalysisResults &, LPMUpdater &);
 403 };
 404 }
 405
 406 #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H