include/llvm/IR/PassManager.h

   1 //===- PassManager.h - LegacyContainer for Passes --------------*- 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 defines various interfaces for pass management in LLVM. There
  12 /// is no "pass" interface in LLVM per se. Instead, an instance of any class
  13 /// which supports a method to 'run' it over a unit of IR can be used as
  14 /// a pass. A pass manager is generally a tool to collect a sequence of passes
  15 /// which run over a particular IR construct, and run each of them in sequence
  16 /// over each such construct in the containing IR construct. As there is no
  17 /// containing IR construct for a Module, a manager for passes over modules
  18 /// forms the base case which runs its managed passes in sequence over the
  19 /// single module provided.
  20 ///
  21 /// The core IR library provides managers for running passes over
  22 /// modules and functions.
  23 ///
  24 /// * FunctionPassManager can run over a Module, runs each pass over
  25 ///   a Function.
  26 /// * ModulePassManager must be directly run, runs each pass over the Module.
  27 ///
  28 /// Note that the implementations of the pass managers use concept-based
  29 /// polymorphism as outlined in the "Value Semantics and Concept-based
  30 /// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base
  31 /// Class of Evil") by Sean Parent:
  32 /// * http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations
  33 /// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil
  34 ///
  35 //===----------------------------------------------------------------------===//
  36
  37 #include "llvm/ADT/DenseMap.h"
  38 #include "llvm/ADT/polymorphic_ptr.h"
  39 #include "llvm/Support/type_traits.h"
  40 #include "llvm/IR/Function.h"
  41 #include "llvm/IR/Module.h"
  42 #include <list>
  43 #include <vector>
  44
  45 namespace llvm {
  46
  47 class Module;
  48 class Function;
  49
  50 /// \brief Implementation details of the pass manager interfaces.
  51 namespace detail {
  52
  53 /// \brief Template for the abstract base class used to dispatch
  54 /// polymorphically over pass objects.
  55 template <typename T> struct PassConcept {
  56   // Boiler plate necessary for the container of derived classes.
  57   virtual ~PassConcept() {}
  58   virtual PassConcept *clone() = 0;
  59
  60   /// \brief The polymorphic API which runs the pass over a given IR entity.
  61   virtual bool run(T Arg) = 0;
  62 };
  63
  64 /// \brief A template wrapper used to implement the polymorphic API.
  65 ///
  66 /// Can be instantiated for any object which provides a \c run method
  67 /// accepting a \c T. It requires the pass to be a copyable
  68 /// object.
  69 template <typename T, typename PassT> struct PassModel : PassConcept<T> {
  70   PassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
  71   virtual PassModel *clone() { return new PassModel(Pass); }
  72   virtual bool run(T Arg) { return Pass.run(Arg); }
  73   PassT Pass;
  74 };
  75
  76 }
  77
  78 class AnalysisManager;
  79
  80 class ModulePassManager {
  81 public:
  82   ModulePassManager(Module *M, AnalysisManager *AM = 0) : M(M), AM(AM) {}
  83
  84   template <typename ModulePassT> void addPass(ModulePassT Pass) {
  85     Passes.push_back(new ModulePassModel<ModulePassT>(llvm_move(Pass)));
  86   }
  87
  88   void run();
  89
  90 private:
  91   // Pull in the concept type and model template specialized for modules.
  92   typedef detail::PassConcept<Module *> ModulePassConcept;
  93   template <typename PassT>
  94   struct ModulePassModel : detail::PassModel<Module *, PassT> {
  95     ModulePassModel(PassT Pass) : detail::PassModel<Module *, PassT>(Pass) {}
  96   };
  97
  98   Module *M;
  99   AnalysisManager *AM;
 100   std::vector<polymorphic_ptr<ModulePassConcept> > Passes;
 101 };
 102
 103 class FunctionPassManager {
 104 public:
 105   FunctionPassManager(AnalysisManager *AM = 0) : AM(AM) {}
 106
 107   template <typename FunctionPassT> void addPass(FunctionPassT Pass) {
 108     Passes.push_back(new FunctionPassModel<FunctionPassT>(llvm_move(Pass)));
 109   }
 110
 111   bool run(Module *M);
 112
 113 private:
 114   // Pull in the concept type and model template specialized for functions.
 115   typedef detail::PassConcept<Function *> FunctionPassConcept;
 116   template <typename PassT>
 117   struct FunctionPassModel : detail::PassModel<Function *, PassT> {
 118     FunctionPassModel(PassT Pass)
 119         : detail::PassModel<Function *, PassT>(Pass) {}
 120   };
 121
 122   AnalysisManager *AM;
 123   std::vector<polymorphic_ptr<FunctionPassConcept> > Passes;
 124 };
 125
 126
 127 /// \brief An analysis manager to coordinate and cache analyses run over
 128 /// a module.
 129 ///
 130 /// The analysis manager is typically used by passes in a pass pipeline
 131 /// (consisting potentially of several individual pass managers) over a module
 132 /// of IR. It provides registration of available analyses, declaring
 133 /// requirements on support for specific analyses, running of an specific
 134 /// analysis over a specific unit of IR to compute an analysis result, and
 135 /// caching of the analysis results to reuse them across multiple passes.
 136 ///
 137 /// It is the responsibility of callers to use the invalidation API to
 138 /// invalidate analysis results when the IR they correspond to changes. The
 139 /// \c ModulePassManager and \c FunctionPassManager do this automatically.
 140 class AnalysisManager {
 141 public:
 142   AnalysisManager(Module *M) : M(M) {}
 143
 144   /// \brief Get the result of an analysis pass for this module.
 145   ///
 146   /// If there is not a valid cached result in the manager already, this will
 147   /// re-run the analysis to produce a valid result.
 148   ///
 149   /// The module passed in must be the same module as the analysis manager was
 150   /// constructed around.
 151   template <typename PassT>
 152   const typename PassT::Result &getResult(Module *M) {
 153     const AnalysisResultConcept<Module> &ResultConcept =
 154         getResultImpl(PassT::ID(), M);
 155     typedef AnalysisResultModel<Module, typename PassT::Result> ResultModelT;
 156     return static_cast<const ResultModelT &>(ResultConcept).Result;
 157   }
 158
 159   /// \brief Get the result of an analysis pass for a function.
 160   ///
 161   /// If there is not a valid cached result in the manager already, this will
 162   /// re-run the analysis to produce a valid result.
 163   template <typename PassT>
 164   const typename PassT::Result &getResult(Function *F) {
 165     const AnalysisResultConcept<Function> &ResultConcept =
 166         getResultImpl(PassT::ID(), F);
 167     typedef AnalysisResultModel<Function, typename PassT::Result> ResultModelT;
 168     return static_cast<const ResultModelT &>(ResultConcept).Result;
 169   }
 170
 171   /// \brief Register an analysis pass with the manager.
 172   ///
 173   /// This provides an initialized and set-up analysis pass to the
 174   /// analysis
 175   /// manager. Whomever is setting up analysis passes must use this to
 176   /// populate
 177   /// the manager with all of the analysis passes available.
 178   template <typename PassT> void registerAnalysisPass(PassT Pass) {
 179     registerAnalysisPassImpl<PassT>(llvm_move(Pass));
 180   }
 181
 182   /// \brief Require that a particular analysis pass is provided by the manager.
 183   ///
 184   /// This allows transform passes to assert ther requirements during
 185   /// construction and fail fast if the analysis manager doesn't provide the
 186   /// needed facilities.
 187   ///
 188   /// We force the analysis manager to have these passes explicitly registered
 189   /// first to ensure that there is exactly one place in the code responsible
 190   /// for adding an analysis pass to the manager as all transforms will share
 191   /// a single pass within the manager and each may not be the canonical place
 192   /// to initialize such a pass.
 193   template <typename PassT> void requireAnalysisPass() {
 194     requireAnalysisPassImpl<PassT>();
 195   }
 196
 197   /// \brief Invalidate a specific analysis pass for an IR module.
 198   ///
 199   /// Note that the analysis result can disregard invalidation.
 200   template <typename PassT> void invalidate(Module *M) {
 201     invalidateImpl(PassT::ID(), M);
 202   }
 203
 204   /// \brief Invalidate a specific analysis pass for an IR function.
 205   ///
 206   /// Note that the analysis result can disregard invalidation.
 207   template <typename PassT> void invalidate(Function *F) {
 208     invalidateImpl(PassT::ID(), F);
 209   }
 210
 211   /// \brief Invalidate analyses cached for an IR Module.
 212   ///
 213   /// Note that specific analysis results can disregard invalidation by
 214   /// overriding their invalidate method.
 215   ///
 216   /// The module must be the module this analysis manager was constructed
 217   /// around.
 218   void invalidateAll(Module *M);
 219
 220   /// \brief Invalidate analyses cached for an IR Function.
 221   ///
 222   /// Note that specific analysis results can disregard invalidation by
 223   /// overriding the invalidate method.
 224   void invalidateAll(Function *F);
 225
 226 private:
 227   /// \brief Abstract concept of an analysis result.
 228   ///
 229   /// This concept is parameterized over the IR unit that this result pertains
 230   /// to.
 231   template <typename IRUnitT> struct AnalysisResultConcept {
 232     virtual ~AnalysisResultConcept() {}
 233     virtual AnalysisResultConcept *clone() = 0;
 234
 235     /// \brief Method to try and mark a result as invalid.
 236     ///
 237     /// When the outer \c AnalysisManager detects a change in some underlying
 238     /// unit of the IR, it will call this method on all of the results cached.
 239     ///
 240     /// \returns true if the result should indeed be invalidated (the default).
 241     virtual bool invalidate(IRUnitT *IR) = 0;
 242   };
 243
 244   /// \brief Wrapper to model the analysis result concept.
 245   ///
 246   /// Can wrap any type which implements a suitable invalidate member and model
 247   /// the AnalysisResultConcept for the AnalysisManager.
 248   template <typename IRUnitT, typename ResultT>
 249   struct AnalysisResultModel : AnalysisResultConcept<IRUnitT> {
 250     AnalysisResultModel(ResultT Result) : Result(llvm_move(Result)) {}
 251     virtual AnalysisResultModel *clone() {
 252       return new AnalysisResultModel(Result);
 253     }
 254
 255     /// \brief The model delegates to the \c ResultT method.
 256     virtual bool invalidate(IRUnitT *IR) { return Result.invalidate(IR); }
 257
 258     ResultT Result;
 259   };
 260
 261   /// \brief Abstract concept of an analysis pass.
 262   ///
 263   /// This concept is parameterized over the IR unit that it can run over and
 264   /// produce an analysis result.
 265   template <typename IRUnitT> struct AnalysisPassConcept {
 266     virtual ~AnalysisPassConcept() {}
 267     virtual AnalysisPassConcept *clone() = 0;
 268
 269     /// \brief Method to run this analysis over a unit of IR.
 270     /// \returns The analysis result object to be queried by users, the caller
 271     /// takes ownership.
 272     virtual AnalysisResultConcept<IRUnitT> *run(IRUnitT *IR) = 0;
 273   };
 274
 275   /// \brief Wrapper to model the analysis pass concept.
 276   ///
 277   /// Can wrap any type which implements a suitable \c run method. The method
 278   /// must accept the IRUnitT as an argument and produce an object which can be
 279   /// wrapped in a \c AnalysisResultModel.
 280   template <typename PassT>
 281   struct AnalysisPassModel : AnalysisPassConcept<typename PassT::IRUnitT> {
 282     AnalysisPassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
 283     virtual AnalysisPassModel *clone() { return new AnalysisPassModel(Pass); }
 284
 285     // FIXME: Replace PassT::IRUnitT with type traits when we use C++11.
 286     typedef typename PassT::IRUnitT IRUnitT;
 287
 288     // FIXME: Replace PassT::Result with type traits when we use C++11.
 289     typedef AnalysisResultModel<IRUnitT, typename PassT::Result> ResultModelT;
 290
 291     /// \brief The model delegates to the \c PassT::run method.
 292     ///
 293     /// The return is wrapped in an \c AnalysisResultModel.
 294     virtual ResultModelT *run(IRUnitT *IR) {
 295       return new ResultModelT(Pass.run(IR));
 296     }
 297
 298     PassT Pass;
 299   };
 300
 301
 302   /// \brief Get a module pass result, running the pass if necessary.
 303   const AnalysisResultConcept<Module> &getResultImpl(void *PassID, Module *M);
 304
 305   /// \brief Get a function pass result, running the pass if necessary.
 306   const AnalysisResultConcept<Function> &getResultImpl(void *PassID,
 307                                                        Function *F);
 308
 309   /// \brief Invalidate a module pass result.
 310   void invalidateImpl(void *PassID, Module *M);
 311
 312   /// \brief Invalidate a function pass result.
 313   void invalidateImpl(void *PassID, Function *F);
 314
 315
 316   /// \brief Module pass specific implementation of registration.
 317   template <typename PassT>
 318   typename enable_if<is_same<typename PassT::IRUnitT, Module> >::type
 319   registerAnalysisPassImpl(PassT Pass) {
 320     assert(!ModuleAnalysisPasses.count(PassT::ID()) &&
 321            "Registered the same analysis pass twice!");
 322     ModuleAnalysisPasses[PassT::ID()] =
 323         new AnalysisPassModel<PassT>(llvm_move(Pass));
 324   }
 325
 326   /// \brief Function pass specific implementation of registration.
 327   template <typename PassT>
 328   typename enable_if<is_same<typename PassT::IRUnitT, Function> >::type
 329   registerAnalysisPassImpl(PassT Pass) {
 330     assert(!FunctionAnalysisPasses.count(PassT::ID()) &&
 331            "Registered the same analysis pass twice!");
 332     FunctionAnalysisPasses[PassT::ID()] =
 333         new AnalysisPassModel<PassT>(llvm_move(Pass));
 334   }
 335
 336   /// \brief Module pass specific implementation of requirement declaration.
 337   template <typename PassT>
 338   typename enable_if<is_same<typename PassT::IRUnitT, Module> >::type
 339   requireAnalysisPassImpl() {
 340     assert(ModuleAnalysisPasses.count(PassT::ID()) &&
 341            "This analysis pass was not registered prior to being required");
 342   }
 343
 344   /// \brief Function pass specific implementation of requirement declaration.
 345   template <typename PassT>
 346   typename enable_if<is_same<typename PassT::IRUnitT, Function> >::type
 347   requireAnalysisPassImpl() {
 348     assert(FunctionAnalysisPasses.count(PassT::ID()) &&
 349            "This analysis pass was not registered prior to being required");
 350   }
 351
 352
 353   /// \brief Map type from module analysis pass ID to pass concept pointer.
 354   typedef DenseMap<void *, polymorphic_ptr<AnalysisPassConcept<Module> > >
 355   ModuleAnalysisPassMapT;
 356
 357   /// \brief Collection of module analysis passes, indexed by ID.
 358   ModuleAnalysisPassMapT ModuleAnalysisPasses;
 359
 360   /// \brief Map type from module analysis pass ID to pass result concept pointer.
 361   typedef DenseMap<void *, polymorphic_ptr<AnalysisResultConcept<Module> > >
 362   ModuleAnalysisResultMapT;
 363
 364   /// \brief Cache of computed module analysis results for this module.
 365   ModuleAnalysisResultMapT ModuleAnalysisResults;
 366
 367
 368   /// \brief Map type from function analysis pass ID to pass concept pointer.
 369   typedef DenseMap<void *, polymorphic_ptr<AnalysisPassConcept<Function> > >
 370   FunctionAnalysisPassMapT;
 371
 372   /// \brief Collection of function analysis passes, indexed by ID.
 373   FunctionAnalysisPassMapT FunctionAnalysisPasses;
 374
 375   /// \brief List of function analysis pass IDs and associated concept pointers.
 376   ///
 377   /// Requires iterators to be valid across appending new entries and arbitrary
 378   /// erases. Provides both the pass ID and concept pointer such that it is
 379   /// half of a bijection and provides storage for the actual result concept.
 380   typedef std::list<
 381       std::pair<void *, polymorphic_ptr<AnalysisResultConcept<Function> > > >
 382   FunctionAnalysisResultListT;
 383
 384   /// \brief Map type from function pointer to our custom list type.
 385   typedef DenseMap<Function *, FunctionAnalysisResultListT> FunctionAnalysisResultListMapT;
 386
 387   /// \brief Map from function to a list of function analysis results.
 388   ///
 389   /// Provides linear time removal of all analysis results for a function and
 390   /// the ultimate storage for a particular cached analysis result.
 391   FunctionAnalysisResultListMapT FunctionAnalysisResultLists;
 392
 393   /// \brief Map type from a pair of analysis ID and function pointer to an
 394   /// iterator into a particular result list.
 395   typedef DenseMap<std::pair<void *, Function *>,
 396                    FunctionAnalysisResultListT::iterator>
 397   FunctionAnalysisResultMapT;
 398
 399   /// \brief Map from an analysis ID and function to a particular cached
 400   /// analysis result.
 401   FunctionAnalysisResultMapT FunctionAnalysisResults;
 402
 403   /// \brief Module handle for the \c AnalysisManager.
 404   Module *M;
 405 };
 406
 407 }