LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - LoopPassManager.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 64 65 98.5 %
Date: 2017-09-14 15:23:50 Functions: 15 16 93.8 %
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             : /// \brief 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         103 :   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
      93             :                         LoopStandardAnalysisResults &AR, LPMUpdater &) {
      94         103 :     (void)AM.template getResult<AnalysisT>(L, AR);
      95         103 :     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         520 : 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        2080 :   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        3124 :   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         522 :     PreOrderWorklist.push_back(RootL);
     127             :     do {
     128         637 :       Loop *L = PreOrderWorklist.pop_back_val();
     129        1911 :       PreOrderWorklist.append(L->begin(), L->end());
     130         637 :       PreOrderLoops.push_back(L);
     131         637 :     } while (!PreOrderWorklist.empty());
     132             : 
     133         522 :     Worklist.insert(std::move(PreOrderLoops));
     134         522 :     PreOrderLoops.clear();
     135             :   }
     136         520 : }
     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) {
     168          28 :     LAM.clear(L);
     169             :     assert(CurrentL->contains(&L) && "Cannot delete a loop outside of the "
     170             :                                      "subloop tree currently being processed.");
     171          28 :     if (&L == CurrentL)
     172          27 :       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           3 :   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           3 :     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           3 :     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           3 :     SkipCurrentLoop = true;
     198           3 :   }
     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          22 :     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             : private:
     220             :   template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor;
     221             : 
     222             :   /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.
     223             :   SmallPriorityWorklist<Loop *, 4> &Worklist;
     224             : 
     225             :   /// The analysis manager for use in the current loop nest.
     226             :   LoopAnalysisManager &LAM;
     227             : 
     228             :   Loop *CurrentL;
     229             :   bool SkipCurrentLoop;
     230             : 
     231             : #ifndef NDEBUG
     232             :   // In debug builds we also track the parent loop to implement asserts even in
     233             :   // the face of loop deletion.
     234             :   Loop *ParentL;
     235             : #endif
     236             : 
     237             :   LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
     238             :              LoopAnalysisManager &LAM)
     239         495 :       : Worklist(Worklist), LAM(LAM) {}
     240             : };
     241             : 
     242             : /// \brief Adaptor that maps from a function to its loops.
     243             : ///
     244             : /// Designed to allow composition of a LoopPass(Manager) and a
     245             : /// FunctionPassManager. Note that if this pass is constructed with a \c
     246             : /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
     247             : /// analysis prior to running the loop passes over the function to enable a \c
     248             : /// LoopAnalysisManager to be used within this run safely.
     249             : template <typename LoopPassT>
     250        4994 : class FunctionToLoopPassAdaptor
     251             :     : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
     252             : public:
     253         986 :   explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {
     254         381 :     LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
     255         381 :     LoopCanonicalizationFPM.addPass(LCSSAPass());
     256         224 :   }
     257             : 
     258             :   /// \brief Runs the loop passes across every loop in the function.
     259         828 :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     260             :     // Before we even compute any loop analyses, first run a miniature function
     261             :     // pass pipeline to put loops into their canonical form. Note that we can
     262             :     // directly build up function analyses after this as the function pass
     263             :     // manager handles all the invalidation at that layer.
     264         828 :     PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM);
     265             : 
     266             :     // Get the loop structure for this function
     267         828 :     LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
     268             : 
     269             :     // If there are no loops, there is nothing to do here.
     270        1656 :     if (LI.empty())
     271             :       return PA;
     272             : 
     273             :     // Get the analysis results needed by loop passes.
     274        3465 :     LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
     275         495 :                                        AM.getResult<AssumptionAnalysis>(F),
     276         495 :                                        AM.getResult<DominatorTreeAnalysis>(F),
     277         495 :                                        AM.getResult<LoopAnalysis>(F),
     278         495 :                                        AM.getResult<ScalarEvolutionAnalysis>(F),
     279         495 :                                        AM.getResult<TargetLibraryAnalysis>(F),
     280         495 :                                        AM.getResult<TargetIRAnalysis>(F)};
     281             : 
     282             :     // Setup the loop analysis manager from its proxy. It is important that
     283             :     // this is only done when there are loops to process and we have built the
     284             :     // LoopStandardAnalysisResults object. The loop analyses cached in this
     285             :     // manager have access to those analysis results and so it must invalidate
     286             :     // itself when they go away.
     287         495 :     LoopAnalysisManager &LAM =
     288         495 :         AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
     289             : 
     290             :     // A postorder worklist of loops to process.
     291         495 :     SmallPriorityWorklist<Loop *, 4> Worklist;
     292             : 
     293             :     // Register the worklist and loop analysis manager so that loop passes can
     294             :     // update them when they mutate the loop nest structure.
     295         495 :     LPMUpdater Updater(Worklist, LAM);
     296             : 
     297             :     // Add the loop nests in the reverse order of LoopInfo. For some reason,
     298             :     // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
     299             :     // the purpose of unrolling, loop deletion, and LICM, we largely want to
     300             :     // work forward across the CFG so that we visit defs before uses and can
     301             :     // propagate simplifications from one loop nest into the next.
     302             :     // FIXME: Consider changing the order in LoopInfo.
     303         990 :     internal::appendLoopsToWorklist(reverse(LI), Worklist);
     304             : 
     305             :     do {
     306         640 :       Loop *L = Worklist.pop_back_val();
     307             : 
     308             :       // Reset the update structure for this loop.
     309         640 :       Updater.CurrentL = L;
     310         640 :       Updater.SkipCurrentLoop = false;
     311             : 
     312             : #ifndef NDEBUG
     313             :       // Save a parent loop pointer for asserts.
     314             :       Updater.ParentL = L->getParentLoop();
     315             : 
     316             :       // Verify the loop structure and LCSSA form before visiting the loop.
     317             :       L->verifyLoop();
     318             :       assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
     319             :              "Loops must remain in LCSSA form!");
     320             : #endif
     321             : 
     322        1280 :       PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
     323             :       // FIXME: We should verify the set of analyses relevant to Loop passes
     324             :       // are preserved.
     325             : 
     326             :       // If the loop hasn't been deleted, we need to handle invalidation here.
     327         640 :       if (!Updater.skipCurrentLoop())
     328             :         // We know that the loop pass couldn't have invalidated any other
     329             :         // loop's analyses (that's the contract of a loop pass), so directly
     330             :         // handle the loop analysis manager's invalidation here.
     331         610 :         LAM.invalidate(*L, PassPA);
     332             : 
     333             :       // Then intersect the preserved set so that invalidation of module
     334             :       // analyses will eventually occur when the module pass completes.
     335         640 :       PA.intersect(std::move(PassPA));
     336         640 :     } while (!Worklist.empty());
     337             : 
     338             :     // By definition we preserve the proxy. We also preserve all analyses on
     339             :     // Loops. This precludes *any* invalidation of loop analyses by the proxy,
     340             :     // but that's OK because we've taken care to invalidate analyses in the
     341             :     // loop analysis manager incrementally above.
     342         495 :     PA.preserveSet<AllAnalysesOn<Loop>>();
     343         495 :     PA.preserve<LoopAnalysisManagerFunctionProxy>();
     344             :     // We also preserve the set of standard analyses.
     345         495 :     PA.preserve<DominatorTreeAnalysis>();
     346         495 :     PA.preserve<LoopAnalysis>();
     347         495 :     PA.preserve<ScalarEvolutionAnalysis>();
     348             :     // FIXME: What we really want to do here is preserve an AA category, but
     349             :     // that concept doesn't exist yet.
     350         495 :     PA.preserve<AAManager>();
     351         495 :     PA.preserve<BasicAA>();
     352         495 :     PA.preserve<GlobalsAA>();
     353         495 :     PA.preserve<SCEVAA>();
     354             :     return PA;
     355             :   }
     356             : 
     357             : private:
     358             :   LoopPassT Pass;
     359             : 
     360             :   FunctionPassManager LoopCanonicalizationFPM;
     361             : };
     362             : 
     363             : /// \brief A function to deduce a loop pass type and wrap it in the templated
     364             : /// adaptor.
     365             : template <typename LoopPassT>
     366             : FunctionToLoopPassAdaptor<LoopPassT>
     367         224 : createFunctionToLoopPassAdaptor(LoopPassT Pass) {
     368         986 :   return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass));
     369             : }
     370             : 
     371             : /// \brief Pass for printing a loop's contents as textual IR.
     372           0 : class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
     373             :   raw_ostream &OS;
     374             :   std::string Banner;
     375             : 
     376             : public:
     377             :   PrintLoopPass();
     378             :   PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
     379             : 
     380             :   PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
     381             :                         LoopStandardAnalysisResults &, LPMUpdater &);
     382             : };
     383             : }
     384             : 
     385             : #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H

Generated by: LCOV version 1.13