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     PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
 280
 281     PreservedAnalyses PA = PreservedAnalyses::all();
 282     // Check the PassInstrumentation's BeforePass callbacks before running the
 283     // canonicalization pipeline.
 284     if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
 285       PA = LoopCanonicalizationFPM.run(F, AM);
 286       PI.runAfterPass<Function>(LoopCanonicalizationFPM, F);
 287     }
 288
 289     // Get the loop structure for this function
 290     LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 291
 292     // If there are no loops, there is nothing to do here.
 293     if (LI.empty())
 294       return PA;
 295
 296     // Get the analysis results needed by loop passes.
 297     MemorySSA *MSSA = EnableMSSALoopDependency
 298                           ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
 299                           : nullptr;
 300     LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
 301                                        AM.getResult<AssumptionAnalysis>(F),
 302                                        AM.getResult<DominatorTreeAnalysis>(F),
 303                                        AM.getResult<LoopAnalysis>(F),
 304                                        AM.getResult<ScalarEvolutionAnalysis>(F),
 305                                        AM.getResult<TargetLibraryAnalysis>(F),
 306                                        AM.getResult<TargetIRAnalysis>(F),
 307                                        MSSA};
 308
 309     // Setup the loop analysis manager from its proxy. It is important that
 310     // this is only done when there are loops to process and we have built the
 311     // LoopStandardAnalysisResults object. The loop analyses cached in this
 312     // manager have access to those analysis results and so it must invalidate
 313     // itself when they go away.
 314     LoopAnalysisManager &LAM =
 315         AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
 316
 317     // A postorder worklist of loops to process.
 318     SmallPriorityWorklist<Loop *, 4> Worklist;
 319
 320     // Register the worklist and loop analysis manager so that loop passes can
 321     // update them when they mutate the loop nest structure.
 322     LPMUpdater Updater(Worklist, LAM);
 323
 324     // Add the loop nests in the reverse order of LoopInfo. For some reason,
 325     // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
 326     // the purpose of unrolling, loop deletion, and LICM, we largely want to
 327     // work forward across the CFG so that we visit defs before uses and can
 328     // propagate simplifications from one loop nest into the next.
 329     // FIXME: Consider changing the order in LoopInfo.
 330     internal::appendLoopsToWorklist(reverse(LI), Worklist);
 331
 332     do {
 333       Loop *L = Worklist.pop_back_val();
 334
 335       // Reset the update structure for this loop.
 336       Updater.CurrentL = L;
 337       Updater.SkipCurrentLoop = false;
 338
 339 #ifndef NDEBUG
 340       // Save a parent loop pointer for asserts.
 341       Updater.ParentL = L->getParentLoop();
 342
 343       // Verify the loop structure and LCSSA form before visiting the loop.
 344       L->verifyLoop();
 345       assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
 346              "Loops must remain in LCSSA form!");
 347 #endif
 348       // Check the PassInstrumentation's BeforePass callbacks before running the
 349       // pass, skip its execution completely if asked to (callback returns
 350       // false).
 351       if (!PI.runBeforePass<Loop>(Pass, *L))
 352         continue;
 353       PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
 354
 355       // Do not pass deleted Loop into the instrumentation.
 356       if (Updater.skipCurrentLoop())
 357         PI.runAfterPassInvalidated<Loop>(Pass);
 358       else
 359         PI.runAfterPass<Loop>(Pass, *L);
 360
 361       // FIXME: We should verify the set of analyses relevant to Loop passes
 362       // are preserved.
 363
 364       // If the loop hasn't been deleted, we need to handle invalidation here.
 365       if (!Updater.skipCurrentLoop())
 366         // We know that the loop pass couldn't have invalidated any other
 367         // loop's analyses (that's the contract of a loop pass), so directly
 368         // handle the loop analysis manager's invalidation here.
 369         LAM.invalidate(*L, PassPA);
 370
 371       // Then intersect the preserved set so that invalidation of module
 372       // analyses will eventually occur when the module pass completes.
 373       PA.intersect(std::move(PassPA));
 374     } while (!Worklist.empty());
 375
 376     // By definition we preserve the proxy. We also preserve all analyses on
 377     // Loops. This precludes *any* invalidation of loop analyses by the proxy,
 378     // but that's OK because we've taken care to invalidate analyses in the
 379     // loop analysis manager incrementally above.
 380     PA.preserveSet<AllAnalysesOn<Loop>>();
 381     PA.preserve<LoopAnalysisManagerFunctionProxy>();
 382     // We also preserve the set of standard analyses.
 383     PA.preserve<DominatorTreeAnalysis>();
 384     PA.preserve<LoopAnalysis>();
 385     PA.preserve<ScalarEvolutionAnalysis>();
 386     if (EnableMSSALoopDependency)
 387       PA.preserve<MemorySSAAnalysis>();
 388     // FIXME: What we really want to do here is preserve an AA category, but
 389     // that concept doesn't exist yet.
 390     PA.preserve<AAManager>();
 391     PA.preserve<BasicAA>();
 392     PA.preserve<GlobalsAA>();
 393     PA.preserve<SCEVAA>();
 394     return PA;
 395   }
 396
 397 private:
 398   LoopPassT Pass;
 399
 400   FunctionPassManager LoopCanonicalizationFPM;
 401 };
 402
 403 /// A function to deduce a loop pass type and wrap it in the templated
 404 /// adaptor.
 405 template <typename LoopPassT>
 406 FunctionToLoopPassAdaptor<LoopPassT>
 407 createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) {
 408   return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), DebugLogging);
 409 }
 410
 411 /// Pass for printing a loop's contents as textual IR.
 412 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
 413   raw_ostream &OS;
 414   std::string Banner;
 415
 416 public:
 417   PrintLoopPass();
 418   PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
 419
 420   PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
 421                         LoopStandardAnalysisResults &, LPMUpdater &);
 422 };
 423 }
 424
 425 #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H