contrib/llvm/include/llvm/Analysis/CGSCCPassManager.h

   1 //===- CGSCCPassManager.h - Call graph 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 passes over SCCs of the call
  12 /// graph. These passes form an important component of LLVM's interprocedural
  13 /// optimizations. Because they operate on the SCCs of the call graph, and they
  14 /// traverse the graph in post order, they can effectively do pair-wise
  15 /// interprocedural optimizations for all call edges in the program. At each
  16 /// call site edge, the callee has already been optimized as much as is
  17 /// possible. This in turn allows very accurate analysis of it for IPO.
  18 ///
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  22 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  23
  24 #include "llvm/Analysis/LazyCallGraph.h"
  25 #include "llvm/IR/PassManager.h"
  26
  27 namespace llvm {
  28
  29 extern template class PassManager<LazyCallGraph::SCC>;
  30 /// \brief The CGSCC pass manager.
  31 ///
  32 /// See the documentation for the PassManager template for details. It runs
  33 /// a sequency of SCC passes over each SCC that the manager is run over. This
  34 /// typedef serves as a convenient way to refer to this construct.
  35 typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager;
  36
  37 extern template class AnalysisManager<LazyCallGraph::SCC>;
  38 /// \brief The CGSCC analysis manager.
  39 ///
  40 /// See the documentation for the AnalysisManager template for detail
  41 /// documentation. This typedef serves as a convenient way to refer to this
  42 /// construct in the adaptors and proxies used to integrate this into the larger
  43 /// pass manager infrastructure.
  44 typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager;
  45
  46 extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
  47 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
  48 typedef InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>
  49     CGSCCAnalysisManagerModuleProxy;
  50
  51 extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
  52                                                 LazyCallGraph::SCC>;
  53 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
  54 typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC>
  55     ModuleAnalysisManagerCGSCCProxy;
  56
  57 /// \brief The core module pass which does a post-order walk of the SCCs and
  58 /// runs a CGSCC pass over each one.
  59 ///
  60 /// Designed to allow composition of a CGSCCPass(Manager) and
  61 /// a ModulePassManager. Note that this pass must be run with a module analysis
  62 /// manager as it uses the LazyCallGraph analysis. It will also run the
  63 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
  64 /// pass over the module to enable a \c FunctionAnalysisManager to be used
  65 /// within this run safely.
  66 template <typename CGSCCPassT>
  67 class ModuleToPostOrderCGSCCPassAdaptor
  68     : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
  69 public:
  70   explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false)
  71       : Pass(std::move(Pass)), DebugLogging(DebugLogging) {}
  72   // We have to explicitly define all the special member functions because MSVC
  73   // refuses to generate them.
  74   ModuleToPostOrderCGSCCPassAdaptor(
  75       const ModuleToPostOrderCGSCCPassAdaptor &Arg)
  76       : Pass(Arg.Pass), DebugLogging(Arg.DebugLogging) {}
  77   ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
  78       : Pass(std::move(Arg.Pass)), DebugLogging(Arg.DebugLogging) {}
  79   friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
  80                    ModuleToPostOrderCGSCCPassAdaptor &RHS) {
  81     using std::swap;
  82     swap(LHS.Pass, RHS.Pass);
  83     swap(LHS.DebugLogging, RHS.DebugLogging);
  84   }
  85   ModuleToPostOrderCGSCCPassAdaptor &
  86   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
  87     swap(*this, RHS);
  88     return *this;
  89   }
  90
  91   /// \brief Runs the CGSCC pass across every SCC in the module.
  92   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
  93     // Setup the CGSCC analysis manager from its proxy.
  94     CGSCCAnalysisManager &CGAM =
  95         AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
  96
  97     // Get the call graph for this module.
  98     LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
  99
 100     PreservedAnalyses PA = PreservedAnalyses::all();
 101     for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
 102       if (DebugLogging)
 103         dbgs() << "Running an SCC pass across the RefSCC: " << RC << "\n";
 104
 105       for (LazyCallGraph::SCC &C : RC) {
 106         PreservedAnalyses PassPA = Pass.run(C, CGAM);
 107
 108         // We know that the CGSCC pass couldn't have invalidated any other
 109         // SCC's analyses (that's the contract of a CGSCC pass), so
 110         // directly handle the CGSCC analysis manager's invalidation here. We
 111         // also update the preserved set of analyses to reflect that invalidated
 112         // analyses are now safe to preserve.
 113         // FIXME: This isn't quite correct. We need to handle the case where the
 114         // pass updated the CG, particularly some child of the current SCC, and
 115         // invalidate its analyses.
 116         PassPA = CGAM.invalidate(C, std::move(PassPA));
 117
 118         // Then intersect the preserved set so that invalidation of module
 119         // analyses will eventually occur when the module pass completes.
 120         PA.intersect(std::move(PassPA));
 121       }
 122     }
 123
 124     // By definition we preserve the proxy. This precludes *any* invalidation
 125     // of CGSCC analyses by the proxy, but that's OK because we've taken
 126     // care to invalidate analyses in the CGSCC analysis manager
 127     // incrementally above.
 128     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 129     return PA;
 130   }
 131
 132 private:
 133   CGSCCPassT Pass;
 134   bool DebugLogging;
 135 };
 136
 137 /// \brief A function to deduce a function pass type and wrap it in the
 138 /// templated adaptor.
 139 template <typename CGSCCPassT>
 140 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
 141 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false) {
 142   return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass), DebugLogging);
 143 }
 144
 145 extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
 146                                                 LazyCallGraph::SCC>;
 147 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
 148 typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, LazyCallGraph::SCC>
 149     FunctionAnalysisManagerCGSCCProxy;
 150
 151 extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
 152 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
 153 typedef OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>
 154     CGSCCAnalysisManagerFunctionProxy;
 155
 156 /// \brief Adaptor that maps from a SCC to its functions.
 157 ///
 158 /// Designed to allow composition of a FunctionPass(Manager) and
 159 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 160 /// to a \c CGSCCAnalysisManager it will run the
 161 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 162 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 163 /// within this run safely.
 164 template <typename FunctionPassT>
 165 class CGSCCToFunctionPassAdaptor
 166     : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
 167 public:
 168   explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false)
 169       : Pass(std::move(Pass)), DebugLogging(DebugLogging) {}
 170   // We have to explicitly define all the special member functions because MSVC
 171   // refuses to generate them.
 172   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
 173       : Pass(Arg.Pass), DebugLogging(Arg.DebugLogging) {}
 174   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
 175       : Pass(std::move(Arg.Pass)), DebugLogging(Arg.DebugLogging) {}
 176   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
 177                    CGSCCToFunctionPassAdaptor &RHS) {
 178     using std::swap;
 179     swap(LHS.Pass, RHS.Pass);
 180     swap(LHS.DebugLogging, RHS.DebugLogging);
 181   }
 182   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
 183     swap(*this, RHS);
 184     return *this;
 185   }
 186
 187   /// \brief Runs the function pass across every function in the module.
 188   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) {
 189     // Setup the function analysis manager from its proxy.
 190     FunctionAnalysisManager &FAM =
 191         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
 192
 193     if (DebugLogging)
 194       dbgs() << "Running function passes across an SCC: " << C << "\n";
 195
 196     PreservedAnalyses PA = PreservedAnalyses::all();
 197     for (LazyCallGraph::Node &N : C) {
 198       PreservedAnalyses PassPA = Pass.run(N.getFunction(), FAM);
 199
 200       // We know that the function pass couldn't have invalidated any other
 201       // function's analyses (that's the contract of a function pass), so
 202       // directly handle the function analysis manager's invalidation here.
 203       // Also, update the preserved analyses to reflect that once invalidated
 204       // these can again be preserved.
 205       PassPA = FAM.invalidate(N.getFunction(), std::move(PassPA));
 206
 207       // Then intersect the preserved set so that invalidation of module
 208       // analyses will eventually occur when the module pass completes.
 209       PA.intersect(std::move(PassPA));
 210     }
 211
 212     // By definition we preserve the proxy. This precludes *any* invalidation
 213     // of function analyses by the proxy, but that's OK because we've taken
 214     // care to invalidate analyses in the function analysis manager
 215     // incrementally above.
 216     // FIXME: We need to update the call graph here to account for any deleted
 217     // edges!
 218     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 219     return PA;
 220   }
 221
 222 private:
 223   FunctionPassT Pass;
 224   bool DebugLogging;
 225 };
 226
 227 /// \brief A function to deduce a function pass type and wrap it in the
 228 /// templated adaptor.
 229 template <typename FunctionPassT>
 230 CGSCCToFunctionPassAdaptor<FunctionPassT>
 231 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false) {
 232   return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass),
 233                                                    DebugLogging);
 234 }
 235 }
 236
 237 #endif