LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - LoopPassManager.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 209 255 82.0 %
Date: 2018-10-20 13:21:21 Functions: 10 20 50.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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           0 :   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
      93             :                         LoopStandardAnalysisResults &AR, LPMUpdater &) {
      94             :     (void)AM.template getResult<AnalysisT>(L, AR);
      95           0 :     return PreservedAnalyses::all();
      96             :   }
      97           0 : };
      98             : 
      99             : /// An alias template to easily name a require analysis loop pass.
     100           0 : template <typename AnalysisT>
     101             : using RequireAnalysisLoopPass =
     102           0 :     RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
     103             :                         LoopStandardAnalysisResults &, LPMUpdater &>;
     104             : 
     105           0 : namespace internal {
     106             : /// Helper to implement appending of loops onto a worklist.
     107           0 : ///
     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           0 : ///
     111             : /// For trees, a preorder traversal is a viable reverse postorder, so we
     112           0 : /// actually append using a preorder walk algorithm.
     113             : template <typename RangeT>
     114         150 : inline void appendLoopsToWorklist(RangeT &&Loops,
     115           0 :                                   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         305 :   for (Loop *RootL : reverse(Loops)) {
     123             :     assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
     124          63 :     assert(PreOrderWorklist.empty() &&
     125             :            "Must start with an empty preorder walk worklist.");
     126         155 :     PreOrderWorklist.push_back(RootL);
     127             :     do {
     128         167 :       Loop *L = PreOrderWorklist.pop_back_val();
     129         167 :       PreOrderWorklist.append(L->begin(), L->end());
     130         167 :       PreOrderLoops.push_back(L);
     131         167 :     } while (!PreOrderWorklist.empty());
     132         128 : 
     133         155 :     Worklist.insert(std::move(PreOrderLoops));
     134         755 :     PreOrderLoops.clear();
     135             :   }
     136         215 : }
     137             : }
     138         132 : 
     139         132 : template <typename LoopPassT> class FunctionToLoopPassAdaptor;
     140         132 : 
     141         132 : /// This class provides an interface for updating the loop pass manager based
     142        1517 : /// on mutations to the loop nest.
     143          65 : ///
     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         825 : /// they modify the loop nest structure.
     147          57 : class LPMUpdater {
     148         897 : public:
     149         897 :   /// This can be queried by loop passes which run other loop passes (like pass
     150         897 :   /// managers) to know whether the loop needs to be skipped due to updates to
     151         897 :   /// the loop nest.
     152             :   ///
     153         762 :   /// If this returns true, the loop object may have been deleted, so passes
     154             :   /// should take care not to touch the object.
     155         115 :   bool skipCurrentLoop() const { return SkipCurrentLoop; }
     156         755 : 
     157             :   /// Loop passes should use this method to indicate they have deleted a loop
     158             :   /// from the nest.
     159          58 :   ///
     160             :   /// Note that this loop must either be the current loop or a subloop of the
     161         124 :   /// current loop. This routine must be called prior to removing the loop from
     162         124 :   /// the loop nest.
     163         124 :   ///
     164         124 :   /// 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          58 :   /// the rest of the pass management infrastructure.
     167             :   void markLoopAsDeleted(Loop &L, llvm::StringRef Name) {
     168          24 :     LAM.clear(L, Name);
     169          57 :     assert((&L == CurrentL || CurrentL->contains(&L)) &&
     170           6 :            "Cannot delete a loop outside of the "
     171             :            "subloop tree currently being processed.");
     172          24 :     if (&L == CurrentL)
     173          24 :       SkipCurrentLoop = true;
     174             :   }
     175           0 : 
     176             :   /// Loop passes should use this method to indicate they have added new child
     177             :   /// loops of the current loop.
     178          13 :   ///
     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           8 :   void addChildLoops(ArrayRef<Loop *> NewChildLoops) {
     183             :     // Insert ourselves back into the worklist first, as this loop should be
     184           8 :     // revisited after all the children have been processed.
     185           9 :     Worklist.insert(CurrentL);
     186           8 : 
     187           8 : #ifndef NDEBUG
     188             :     for (Loop *NewL : NewChildLoops)
     189           7 :       assert(NewL->getParentLoop() == CurrentL && "All of the new loops must "
     190             :                                                   "be immediate children of "
     191             :                                                   "the current loop!");
     192           6 : #endif
     193             : 
     194           1 :     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           1 :     SkipCurrentLoop = true;
     199           1 :   }
     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           0 :   void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {
     208             : #ifndef NDEBUG
     209             :     for (Loop *NewL : NewSibLoops)
     210             :       assert(NewL->getParentLoop() == ParentL &&
     211           0 :              "All of the new loops must be siblings of the current loop!");
     212             : #endif
     213             : 
     214         106 :     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           0 :   }
     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           2 : 
     239             :   /// The analysis manager for use in the current loop nest.
     240             :   LoopAnalysisManager &LAM;
     241           2 : 
     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           2 : 
     251             :   LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
     252             :              LoopAnalysisManager &LAM)
     253             :       : Worklist(Worklist), LAM(LAM) {}
     254           2 : };
     255           2 : 
     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           0 : 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           0 :     LoopCanonicalizationFPM.addPass(LCSSAPass());
     271             :   }
     272             : 
     273         755 :   /// Runs the loop passes across every loop in the function.
     274           0 :   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         499 :     if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
     285             :       PA = LoopCanonicalizationFPM.run(F, AM);
     286             :       PI.runAfterPass<Function>(LoopCanonicalizationFPM, F);
     287         309 :     }
     288         368 : 
     289         499 :     // Get the loop structure for this function
     290         499 :     LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
     291         309 : 
     292             :     // If there are no loops, there is nothing to do here.
     293             :     if (LI.empty())
     294        1207 :       return PA;
     295             : 
     296             :     // Get the analysis results needed by loop passes.
     297             :     MemorySSA *MSSA = EnableMSSALoopDependency
     298             :                           ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
     299        1207 :                           : nullptr;
     300             :     LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
     301             :                                        AM.getResult<AssumptionAnalysis>(F),
     302             :                                        AM.getResult<DominatorTreeAnalysis>(F),
     303             :                                        AM.getResult<LoopAnalysis>(F),
     304        1207 :                                        AM.getResult<ScalarEvolutionAnalysis>(F),
     305        1207 :                                        AM.getResult<TargetLibraryAnalysis>(F),
     306        1207 :                                        AM.getResult<TargetIRAnalysis>(F),
     307             :                                        MSSA};
     308             : 
     309          11 :     // 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        1207 :     // itself when they go away.
     314             :     LoopAnalysisManager &LAM =
     315             :         AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
     316             : 
     317         755 :     // A postorder worklist of loops to process.
     318             :     SmallPriorityWorklist<Loop *, 4> Worklist;
     319             : 
     320         794 :     // 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           8 : 
     324           8 :     // Add the loop nests in the reverse order of LoopInfo. For some reason,
     325          31 :     // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
     326          31 :     // the purpose of unrolling, loop deletion, and LICM, we largely want to
     327           8 :     // 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          57 :     internal::appendLoopsToWorklist(reverse(LI), Worklist);
     331             : 
     332             :     do {
     333             :       Loop *L = Worklist.pop_back_val();
     334             : 
     335         812 :       // Reset the update structure for this loop.
     336             :       Updater.CurrentL = L;
     337             :       Updater.SkipCurrentLoop = false;
     338             : 
     339             : #ifndef NDEBUG
     340          57 :       // Save a parent loop pointer for asserts.
     341          57 :       Updater.ParentL = L->getParentLoop();
     342          57 : 
     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          57 :       // pass, skip its execution completely if asked to (callback returns
     350         755 :       // false).
     351             :       if (!PI.runBeforePass<Loop>(Pass, *L))
     352             :         continue;
     353          57 :       PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
     354             : 
     355             :       PI.runAfterPass<Loop>(Pass, *L);
     356        1202 : 
     357        1145 :       // FIXME: We should verify the set of analyses relevant to Loop passes
     358             :       // are preserved.
     359             : 
     360             :       // If the loop hasn't been deleted, we need to handle invalidation here.
     361             :       if (!Updater.skipCurrentLoop())
     362             :         // We know that the loop pass couldn't have invalidated any other
     363             :         // loop's analyses (that's the contract of a loop pass), so directly
     364             :         // handle the loop analysis manager's invalidation here.
     365             :         LAM.invalidate(*L, PassPA);
     366             : 
     367             :       // Then intersect the preserved set so that invalidation of module
     368             :       // analyses will eventually occur when the module pass completes.
     369             :       PA.intersect(std::move(PassPA));
     370             :     } while (!Worklist.empty());
     371        1202 : 
     372           0 :     // By definition we preserve the proxy. We also preserve all analyses on
     373        2290 :     // Loops. This precludes *any* invalidation of loop analyses by the proxy,
     374             :     // but that's OK because we've taken care to invalidate analyses in the
     375        1145 :     // loop analysis manager incrementally above.
     376             :     PA.preserveSet<AllAnalysesOn<Loop>>();
     377             :     PA.preserve<LoopAnalysisManagerFunctionProxy>();
     378             :     // We also preserve the set of standard analyses.
     379             :     PA.preserve<DominatorTreeAnalysis>();
     380             :     PA.preserve<LoopAnalysis>();
     381        1145 :     PA.preserve<ScalarEvolutionAnalysis>();
     382             :     if (EnableMSSALoopDependency)
     383             :       PA.preserve<MemorySSAAnalysis>();
     384             :     // FIXME: What we really want to do here is preserve an AA category, but
     385        1029 :     // that concept doesn't exist yet.
     386          57 :     PA.preserve<AAManager>();
     387             :     PA.preserve<BasicAA>();
     388             :     PA.preserve<GlobalsAA>();
     389        1145 :     PA.preserve<SCEVAA>();
     390        1145 :     return PA;
     391             :   }
     392          42 : 
     393          42 : private:
     394             :   LoopPassT Pass;
     395             : 
     396             :   FunctionPassManager LoopCanonicalizationFPM;
     397             : };
     398             : 
     399             : /// A function to deduce a loop pass type and wrap it in the templated
     400             : /// adaptor.
     401             : template <typename LoopPassT>
     402         755 : FunctionToLoopPassAdaptor<LoopPassT>
     403             : createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) {
     404             :   return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), DebugLogging);
     405             : }
     406             : 
     407         134 : /// Pass for printing a loop's contents as textual IR.
     408           0 : class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
     409         268 :   raw_ostream &OS;
     410             :   std::string Banner;
     411         134 : 
     412         878 : public:
     413             :   PrintLoopPass();
     414             :   PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
     415             : 
     416             :   PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
     417         920 :                         LoopStandardAnalysisResults &, LPMUpdater &);
     418             : };
     419             : }
     420             : 
     421         127 : #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H

Generated by: LCOV version 1.13