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

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