Home | History | Annotate | Download | only in Analysis 
      1 //===- LoopAnalysisManager.h - Loop analysis 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 per-loop analyses. These are
     12 /// typically used as part of a loop pass pipeline over the loop nests of
     13 /// a function.
     14 ///
     15 /// Loop analyses are allowed to make some simplifying assumptions:
     16 /// 1) Loops are, where possible, in simplified form.
     17 /// 2) Loops are *always* in LCSSA form.
     18 /// 3) A collection of analysis results are available:
     19 ///    - LoopInfo
     20 ///    - DominatorTree
     21 ///    - ScalarEvolution
     22 ///    - AAManager
     23 ///
     24 /// The primary mechanism to provide these invariants is the loop pass manager,
     25 /// but they can also be manually provided in order to reason about a loop from
     26 /// outside of a dedicated pass manager.
     27 ///
     28 //===----------------------------------------------------------------------===//
     29 
     30 #ifndef LLVM_ANALYSIS_LOOPANALYSISMANAGER_H
     31 #define LLVM_ANALYSIS_LOOPANALYSISMANAGER_H
     32 
     33 #include "llvm/ADT/PostOrderIterator.h"
     34 #include "llvm/ADT/PriorityWorklist.h"
     35 #include "llvm/ADT/STLExtras.h"
     36 #include "llvm/Analysis/AliasAnalysis.h"
     37 #include "llvm/Analysis/BasicAliasAnalysis.h"
     38 #include "llvm/Analysis/GlobalsModRef.h"
     39 #include "llvm/Analysis/LoopInfo.h"
     40 #include "llvm/Analysis/ScalarEvolution.h"
     41 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
     42 #include "llvm/Analysis/TargetLibraryInfo.h"
     43 #include "llvm/Analysis/TargetTransformInfo.h"
     44 #include "llvm/IR/Dominators.h"
     45 #include "llvm/IR/PassManager.h"
     46 
     47 namespace llvm {
     48 
     49 /// The adaptor from a function pass to a loop pass computes these analyses and
     50 /// makes them available to the loop passes "for free". Each loop pass is
     51 /// expected expected to update these analyses if necessary to ensure they're
     52 /// valid after it runs.
     53 struct LoopStandardAnalysisResults {
     54   AAResults &AA;
     55   AssumptionCache ∾
     56   DominatorTree &DT;
     57   LoopInfo &LI;
     58   ScalarEvolution &SE;
     59   TargetLibraryInfo &TLI;
     60   TargetTransformInfo &TTI;
     61 };
     62 
     63 /// Extern template declaration for the analysis set for this IR unit.
     64 extern template class AllAnalysesOn<Loop>;
     65 
     66 extern template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
     67 /// \brief The loop analysis manager.
     68 ///
     69 /// See the documentation for the AnalysisManager template for detail
     70 /// documentation. This typedef serves as a convenient way to refer to this
     71 /// construct in the adaptors and proxies used to integrate this into the larger
     72 /// pass manager infrastructure.
     73 typedef AnalysisManager<Loop, LoopStandardAnalysisResults &>
     74     LoopAnalysisManager;
     75 
     76 /// A proxy from a \c LoopAnalysisManager to a \c Function.
     77 typedef InnerAnalysisManagerProxy<LoopAnalysisManager, Function>
     78     LoopAnalysisManagerFunctionProxy;
     79 
     80 /// A specialized result for the \c LoopAnalysisManagerFunctionProxy which
     81 /// retains a \c LoopInfo reference.
     82 ///
     83 /// This allows it to collect loop objects for which analysis results may be
     84 /// cached in the \c LoopAnalysisManager.
     85 template <> class LoopAnalysisManagerFunctionProxy::Result {
     86 public:
     87   explicit Result(LoopAnalysisManager &InnerAM, LoopInfo &LI)
     88       : InnerAM(&InnerAM), LI(&LI) {}
     89   Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)), LI(Arg.LI) {
     90     // We have to null out the analysis manager in the moved-from state
     91     // because we are taking ownership of the responsibilty to clear the
     92     // analysis state.
     93     Arg.InnerAM = nullptr;
     94   }
     95   Result &operator=(Result &&RHS) {
     96     InnerAM = RHS.InnerAM;
     97     LI = RHS.LI;
     98     // We have to null out the analysis manager in the moved-from state
     99     // because we are taking ownership of the responsibilty to clear the
    100     // analysis state.
    101     RHS.InnerAM = nullptr;
    102     return *this;
    103   }
    104   ~Result() {
    105     // InnerAM is cleared in a moved from state where there is nothing to do.
    106     if (!InnerAM)
    107       return;
    108 
    109     // Clear out the analysis manager if we're being destroyed -- it means we
    110     // didn't even see an invalidate call when we got invalidated.
    111     InnerAM->clear();
    112   }
    113 
    114   /// Accessor for the analysis manager.
    115   LoopAnalysisManager &getManager() { return *InnerAM; }
    116 
    117   /// Handler for invalidation of the proxy for a particular function.
    118   ///
    119   /// If the proxy, \c LoopInfo, and associated analyses are preserved, this
    120   /// will merely forward the invalidation event to any cached loop analysis
    121   /// results for loops within this function.
    122   ///
    123   /// If the necessary loop infrastructure is not preserved, this will forcibly
    124   /// clear all of the cached analysis results that are keyed on the \c
    125   /// LoopInfo for this function.
    126   bool invalidate(Function &F, const PreservedAnalyses &PA,
    127                   FunctionAnalysisManager::Invalidator &Inv);
    128 
    129 private:
    130   LoopAnalysisManager *InnerAM;
    131   LoopInfo *LI;
    132 };
    133 
    134 /// Provide a specialized run method for the \c LoopAnalysisManagerFunctionProxy
    135 /// so it can pass the \c LoopInfo to the result.
    136 template <>
    137 LoopAnalysisManagerFunctionProxy::Result
    138 LoopAnalysisManagerFunctionProxy::run(Function &F, FunctionAnalysisManager &AM);
    139 
    140 // Ensure the \c LoopAnalysisManagerFunctionProxy is provided as an extern
    141 // template.
    142 extern template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
    143 
    144 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
    145                                                 LoopStandardAnalysisResults &>;
    146 /// A proxy from a \c FunctionAnalysisManager to a \c Loop.
    147 typedef OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
    148                                   LoopStandardAnalysisResults &>
    149     FunctionAnalysisManagerLoopProxy;
    150 
    151 /// Returns the minimum set of Analyses that all loop passes must preserve.
    152 PreservedAnalyses getLoopPassPreservedAnalyses();
    153 }
    154 
    155 #endif // LLVM_ANALYSIS_LOOPANALYSISMANAGER_H
    156