include/llvm/IR/PassManager.h

   1 //===- PassManager.h - Pass management infrastructure -----------*- 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://www.youtube.com/watch?v=_BpMYeUFXv8
  34 /// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil
  35 ///
  36 //===----------------------------------------------------------------------===//
  37
  38 #ifndef LLVM_IR_PASS_MANAGER_H
  39 #define LLVM_IR_PASS_MANAGER_H
  40
  41 #include "llvm/ADT/DenseMap.h"
  42 #include "llvm/ADT/SmallPtrSet.h"
  43 #include "llvm/ADT/polymorphic_ptr.h"
  44 #include "llvm/IR/Function.h"
  45 #include "llvm/IR/Module.h"
  46 #include "llvm/Support/type_traits.h"
  47 #include <list>
  48 #include <vector>
  49
  50 namespace llvm {
  51
  52 class Module;
  53 class Function;
  54
  55 /// \brief An abstract set of preserved analyses following a transformation pass
  56 /// run.
  57 ///
  58 /// When a transformation pass is run, it can return a set of analyses whose
  59 /// results were preserved by that transformation. The default set is "none",
  60 /// and preserving analyses must be done explicitly.
  61 ///
  62 /// There is also an explicit all state which can be used (for example) when
  63 /// the IR is not mutated at all.
  64 class PreservedAnalyses {
  65 public:
  66   /// \brief Convenience factory function for the empty preserved set.
  67   static PreservedAnalyses none() { return PreservedAnalyses(); }
  68
  69   /// \brief Construct a special preserved set that preserves all passes.
  70   static PreservedAnalyses all() {
  71     PreservedAnalyses PA;
  72     PA.PreservedPassIDs.insert((void *)AllPassesID);
  73     return PA;
  74   }
  75
  76   PreservedAnalyses &operator=(PreservedAnalyses Arg) {
  77     swap(Arg);
  78     return *this;
  79   }
  80
  81   void swap(PreservedAnalyses &Arg) {
  82     PreservedPassIDs.swap(Arg.PreservedPassIDs);
  83   }
  84
  85   /// \brief Mark a particular pass as preserved, adding it to the set.
  86   template <typename PassT> void preserve() {
  87     if (!areAllPreserved())
  88       PreservedPassIDs.insert(PassT::ID());
  89   }
  90
  91   /// \brief Intersect this set with another in place.
  92   ///
  93   /// This is a mutating operation on this preserved set, removing all
  94   /// preserved passes which are not also preserved in the argument.
  95   void intersect(const PreservedAnalyses &Arg) {
  96     if (Arg.areAllPreserved())
  97       return;
  98     if (areAllPreserved()) {
  99       PreservedPassIDs = Arg.PreservedPassIDs;
 100       return;
 101     }
 102     for (SmallPtrSet<void *, 2>::const_iterator I = PreservedPassIDs.begin(),
 103                                                 E = PreservedPassIDs.end();
 104          I != E; ++I)
 105       if (!Arg.PreservedPassIDs.count(*I))
 106         PreservedPassIDs.erase(*I);
 107   }
 108
 109 #if LLVM_HAS_RVALUE_REFERENCES
 110   /// \brief Intersect this set with a temporary other set in place.
 111   ///
 112   /// This is a mutating operation on this preserved set, removing all
 113   /// preserved passes which are not also preserved in the argument.
 114   void intersect(PreservedAnalyses &&Arg) {
 115     if (Arg.areAllPreserved())
 116       return;
 117     if (areAllPreserved()) {
 118       PreservedPassIDs = std::move(Arg.PreservedPassIDs);
 119       return;
 120     }
 121     for (SmallPtrSet<void *, 2>::const_iterator I = PreservedPassIDs.begin(),
 122                                                 E = PreservedPassIDs.end();
 123          I != E; ++I)
 124       if (!Arg.PreservedPassIDs.count(*I))
 125         PreservedPassIDs.erase(*I);
 126   }
 127 #endif
 128
 129   /// \brief Query whether a pass is marked as preserved by this set.
 130   template <typename PassT> bool preserved() const {
 131     return preserved(PassT::ID());
 132   }
 133
 134   /// \brief Query whether an abstract pass ID is marked as preserved by this
 135   /// set.
 136   bool preserved(void *PassID) const {
 137     return PreservedPassIDs.count((void *)AllPassesID) ||
 138            PreservedPassIDs.count(PassID);
 139   }
 140
 141 private:
 142   // Note that this must not be -1 or -2 as those are already used by the
 143   // SmallPtrSet.
 144   static const uintptr_t AllPassesID = (intptr_t)-3;
 145
 146   bool areAllPreserved() const { return PreservedPassIDs.count((void *)AllPassesID); }
 147
 148   SmallPtrSet<void *, 2> PreservedPassIDs;
 149 };
 150
 151 inline void swap(PreservedAnalyses &LHS, PreservedAnalyses &RHS) {
 152   LHS.swap(RHS);
 153 }
 154
 155 /// \brief Implementation details of the pass manager interfaces.
 156 namespace detail {
 157
 158 /// \brief Template for the abstract base class used to dispatch
 159 /// polymorphically over pass objects.
 160 template <typename IRUnitT, typename AnalysisManagerT> struct PassConcept {
 161   // Boiler plate necessary for the container of derived classes.
 162   virtual ~PassConcept() {}
 163   virtual PassConcept *clone() = 0;
 164
 165   /// \brief The polymorphic API which runs the pass over a given IR entity.
 166   ///
 167   /// Note that actual pass object can omit the analysis manager argument if
 168   /// desired. Also that the analysis manager may be null if there is no
 169   /// analysis manager in the pass pipeline.
 170   virtual PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) = 0;
 171
 172   /// \brief Polymorphic method to access the name of a pass.
 173   virtual StringRef name() = 0;
 174 };
 175
 176 /// \brief SFINAE metafunction for computing whether \c PassT has a run method
 177 /// accepting an \c AnalysisManagerT.
 178 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
 179           typename ResultT>
 180 class PassRunAcceptsAnalysisManager {
 181   typedef char SmallType;
 182   struct BigType { char a, b; };
 183
 184   template <typename T, ResultT (T::*)(IRUnitT, AnalysisManagerT *)>
 185   struct Checker;
 186
 187   template <typename T> static SmallType f(Checker<T, &T::run> *);
 188   template <typename T> static BigType f(...);
 189
 190 public:
 191   enum { Value = sizeof(f<PassT>(0)) == sizeof(SmallType) };
 192 };
 193
 194 /// \brief A template wrapper used to implement the polymorphic API.
 195 ///
 196 /// Can be instantiated for any object which provides a \c run method accepting
 197 /// an \c IRUnitT. It requires the pass to be a copyable object. When the
 198 /// \c run method also accepts an \c AnalysisManagerT*, we pass it along.
 199 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
 200           bool AcceptsAnalysisManager = PassRunAcceptsAnalysisManager<
 201               IRUnitT, AnalysisManagerT, PassT, PreservedAnalyses>::Value>
 202 struct PassModel;
 203
 204 /// \brief Specialization of \c PassModel for passes that accept an analyis
 205 /// manager.
 206 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
 207 struct PassModel<IRUnitT, AnalysisManagerT, PassT,
 208                  true> : PassConcept<IRUnitT, AnalysisManagerT> {
 209   PassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
 210   virtual PassModel *clone() { return new PassModel(Pass); }
 211   virtual PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) {
 212     return Pass.run(IR, AM);
 213   }
 214   virtual StringRef name() { return PassT::name(); }
 215   PassT Pass;
 216 };
 217
 218 /// \brief Specialization of \c PassModel for passes that accept an analyis
 219 /// manager.
 220 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
 221 struct PassModel<IRUnitT, AnalysisManagerT, PassT,
 222                  false> : PassConcept<IRUnitT, AnalysisManagerT> {
 223   PassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
 224   virtual PassModel *clone() { return new PassModel(Pass); }
 225   virtual PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) {
 226     return Pass.run(IR);
 227   }
 228   virtual StringRef name() { return PassT::name(); }
 229   PassT Pass;
 230 };
 231
 232 /// \brief Abstract concept of an analysis result.
 233 ///
 234 /// This concept is parameterized over the IR unit that this result pertains
 235 /// to.
 236 template <typename IRUnitT> struct AnalysisResultConcept {
 237   virtual ~AnalysisResultConcept() {}
 238   virtual AnalysisResultConcept *clone() = 0;
 239
 240   /// \brief Method to try and mark a result as invalid.
 241   ///
 242   /// When the outer analysis manager detects a change in some underlying
 243   /// unit of the IR, it will call this method on all of the results cached.
 244   ///
 245   /// This method also receives a set of preserved analyses which can be used
 246   /// to avoid invalidation because the pass which changed the underlying IR
 247   /// took care to update or preserve the analysis result in some way.
 248   ///
 249   /// \returns true if the result is indeed invalid (the default).
 250   virtual bool invalidate(IRUnitT IR, const PreservedAnalyses &PA) = 0;
 251 };
 252
 253 /// \brief SFINAE metafunction for computing whether \c ResultT provides an
 254 /// \c invalidate member function.
 255 template <typename IRUnitT, typename ResultT> class ResultHasInvalidateMethod {
 256   typedef char SmallType;
 257   struct BigType { char a, b; };
 258
 259   template <typename T, bool (T::*)(IRUnitT, const PreservedAnalyses &)>
 260   struct Checker;
 261
 262   template <typename T> static SmallType f(Checker<T, &T::invalidate> *);
 263   template <typename T> static BigType f(...);
 264
 265 public:
 266   enum { Value = sizeof(f<ResultT>(0)) == sizeof(SmallType) };
 267 };
 268
 269 /// \brief Wrapper to model the analysis result concept.
 270 ///
 271 /// By default, this will implement the invalidate method with a trivial
 272 /// implementation so that the actual analysis result doesn't need to provide
 273 /// an invalidation handler. It is only selected when the invalidation handler
 274 /// is not part of the ResultT's interface.
 275 template <typename IRUnitT, typename PassT, typename ResultT,
 276           bool HasInvalidateHandler =
 277               ResultHasInvalidateMethod<IRUnitT, ResultT>::Value>
 278 struct AnalysisResultModel;
 279
 280 /// \brief Specialization of \c AnalysisResultModel which provides the default
 281 /// invalidate functionality.
 282 template <typename IRUnitT, typename PassT, typename ResultT>
 283 struct AnalysisResultModel<IRUnitT, PassT, ResultT,
 284                            false> : AnalysisResultConcept<IRUnitT> {
 285   AnalysisResultModel(ResultT Result) : Result(llvm_move(Result)) {}
 286   virtual AnalysisResultModel *clone() {
 287     return new AnalysisResultModel(Result);
 288   }
 289
 290   /// \brief The model bases invalidation solely on being in the preserved set.
 291   //
 292   // FIXME: We should actually use two different concepts for analysis results
 293   // rather than two different models, and avoid the indirect function call for
 294   // ones that use the trivial behavior.
 295   virtual bool invalidate(IRUnitT, const PreservedAnalyses &PA) {
 296     return !PA.preserved(PassT::ID());
 297   }
 298
 299   ResultT Result;
 300 };
 301
 302 /// \brief Specialization of \c AnalysisResultModel which delegates invalidate
 303 /// handling to \c ResultT.
 304 template <typename IRUnitT, typename PassT, typename ResultT>
 305 struct AnalysisResultModel<IRUnitT, PassT, ResultT,
 306                            true> : AnalysisResultConcept<IRUnitT> {
 307   AnalysisResultModel(ResultT Result) : Result(llvm_move(Result)) {}
 308   virtual AnalysisResultModel *clone() {
 309     return new AnalysisResultModel(Result);
 310   }
 311
 312   /// \brief The model delegates to the \c ResultT method.
 313   virtual bool invalidate(IRUnitT IR, const PreservedAnalyses &PA) {
 314     return Result.invalidate(IR, PA);
 315   }
 316
 317   ResultT Result;
 318 };
 319
 320 /// \brief Abstract concept of an analysis pass.
 321 ///
 322 /// This concept is parameterized over the IR unit that it can run over and
 323 /// produce an analysis result.
 324 template <typename IRUnitT, typename AnalysisManagerT>
 325 struct AnalysisPassConcept {
 326   virtual ~AnalysisPassConcept() {}
 327   virtual AnalysisPassConcept *clone() = 0;
 328
 329   /// \brief Method to run this analysis over a unit of IR.
 330   /// \returns The analysis result object to be queried by users, the caller
 331   /// takes ownership.
 332   virtual AnalysisResultConcept<IRUnitT> *run(IRUnitT IR,
 333                                               AnalysisManagerT *AM) = 0;
 334 };
 335
 336 /// \brief Wrapper to model the analysis pass concept.
 337 ///
 338 /// Can wrap any type which implements a suitable \c run method. The method
 339 /// must accept the IRUnitT as an argument and produce an object which can be
 340 /// wrapped in a \c AnalysisResultModel.
 341 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
 342           bool AcceptsAnalysisManager = PassRunAcceptsAnalysisManager<
 343               IRUnitT, AnalysisManagerT, PassT,
 344               typename PassT::Result>::Value> struct AnalysisPassModel;
 345
 346 /// \brief Specialization of \c AnalysisPassModel which passes an
 347 /// \c AnalysisManager to PassT's run method.
 348 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
 349 struct AnalysisPassModel<IRUnitT, AnalysisManagerT, PassT,
 350                          true> : AnalysisPassConcept<IRUnitT,
 351                                                      AnalysisManagerT> {
 352   AnalysisPassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
 353   virtual AnalysisPassModel *clone() { return new AnalysisPassModel(Pass); }
 354
 355   // FIXME: Replace PassT::Result with type traits when we use C++11.
 356   typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
 357       ResultModelT;
 358
 359   /// \brief The model delegates to the \c PassT::run method.
 360   ///
 361   /// The return is wrapped in an \c AnalysisResultModel.
 362   virtual ResultModelT *run(IRUnitT IR, AnalysisManagerT *AM) {
 363     return new ResultModelT(Pass.run(IR, AM));
 364   }
 365
 366   PassT Pass;
 367 };
 368
 369 /// \brief Specialization of \c AnalysisPassModel which does not pass an
 370 /// \c AnalysisManager to PassT's run method.
 371 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
 372 struct AnalysisPassModel<IRUnitT, AnalysisManagerT, PassT,
 373                          false> : AnalysisPassConcept<IRUnitT,
 374                                                      AnalysisManagerT> {
 375   AnalysisPassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
 376   virtual AnalysisPassModel *clone() { return new AnalysisPassModel(Pass); }
 377
 378   // FIXME: Replace PassT::Result with type traits when we use C++11.
 379   typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
 380       ResultModelT;
 381
 382   /// \brief The model delegates to the \c PassT::run method.
 383   ///
 384   /// The return is wrapped in an \c AnalysisResultModel.
 385   virtual ResultModelT *run(IRUnitT IR, AnalysisManagerT *) {
 386     return new ResultModelT(Pass.run(IR));
 387   }
 388
 389   PassT Pass;
 390 };
 391
 392 }
 393
 394 class ModuleAnalysisManager;
 395
 396 class ModulePassManager {
 397 public:
 398   explicit ModulePassManager() {}
 399
 400   /// \brief Run all of the module passes in this module pass manager over
 401   /// a module.
 402   ///
 403   /// This method should only be called for a single module as there is the
 404   /// expectation that the lifetime of a pass is bounded to that of a module.
 405   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM = 0);
 406
 407   template <typename ModulePassT> void addPass(ModulePassT Pass) {
 408     Passes.push_back(new ModulePassModel<ModulePassT>(llvm_move(Pass)));
 409   }
 410
 411   static StringRef name() { return "ModulePassManager"; }
 412
 413 private:
 414   // Pull in the concept type and model template specialized for modules.
 415   typedef detail::PassConcept<Module *, ModuleAnalysisManager> ModulePassConcept;
 416   template <typename PassT>
 417   struct ModulePassModel
 418       : detail::PassModel<Module *, ModuleAnalysisManager, PassT> {
 419     ModulePassModel(PassT Pass)
 420         : detail::PassModel<Module *, ModuleAnalysisManager, PassT>(Pass) {}
 421   };
 422
 423   std::vector<polymorphic_ptr<ModulePassConcept> > Passes;
 424 };
 425
 426 class FunctionAnalysisManager;
 427
 428 class FunctionPassManager {
 429 public:
 430   explicit FunctionPassManager() {}
 431
 432   template <typename FunctionPassT> void addPass(FunctionPassT Pass) {
 433     Passes.push_back(new FunctionPassModel<FunctionPassT>(llvm_move(Pass)));
 434   }
 435
 436   PreservedAnalyses run(Function *F, FunctionAnalysisManager *AM = 0);
 437
 438   static StringRef name() { return "FunctionPassManager"; }
 439
 440 private:
 441   // Pull in the concept type and model template specialized for functions.
 442   typedef detail::PassConcept<Function *, FunctionAnalysisManager>
 443       FunctionPassConcept;
 444   template <typename PassT>
 445   struct FunctionPassModel
 446       : detail::PassModel<Function *, FunctionAnalysisManager, PassT> {
 447     FunctionPassModel(PassT Pass)
 448         : detail::PassModel<Function *, FunctionAnalysisManager, PassT>(Pass) {}
 449   };
 450
 451   std::vector<polymorphic_ptr<FunctionPassConcept> > Passes;
 452 };
 453
 454 namespace detail {
 455
 456 /// \brief A CRTP base used to implement analysis managers.
 457 ///
 458 /// This class template serves as the boiler plate of an analysis manager. Any
 459 /// analysis manager can be implemented on top of this base class. Any
 460 /// implementation will be required to provide specific hooks:
 461 ///
 462 /// - getResultImpl
 463 /// - getCachedResultImpl
 464 /// - invalidateImpl
 465 ///
 466 /// The details of the call pattern are within.
 467 template <typename DerivedT, typename IRUnitT>
 468 class AnalysisManagerBase {
 469   DerivedT *derived_this() { return static_cast<DerivedT *>(this); }
 470   const DerivedT *derived_this() const { return static_cast<const DerivedT *>(this); }
 471
 472 protected:
 473   typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT;
 474   typedef detail::AnalysisPassConcept<IRUnitT, DerivedT> PassConceptT;
 475
 476   // FIXME: Provide template aliases for the models when we're using C++11 in
 477   // a mode supporting them.
 478
 479 public:
 480   /// \brief Get the result of an analysis pass for this module.
 481   ///
 482   /// If there is not a valid cached result in the manager already, this will
 483   /// re-run the analysis to produce a valid result.
 484   template <typename PassT> const typename PassT::Result &getResult(IRUnitT IR) {
 485     assert(AnalysisPasses.count(PassT::ID()) &&
 486            "This analysis pass was not registered prior to being queried");
 487
 488     const ResultConceptT &ResultConcept =
 489         derived_this()->getResultImpl(PassT::ID(), IR);
 490     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
 491         ResultModelT;
 492     return static_cast<const ResultModelT &>(ResultConcept).Result;
 493   }
 494
 495   /// \brief Get the cached result of an analysis pass for this module.
 496   ///
 497   /// This method never runs the analysis.
 498   ///
 499   /// \returns null if there is no cached result.
 500   template <typename PassT>
 501   const typename PassT::Result *getCachedResult(IRUnitT IR) const {
 502     assert(AnalysisPasses.count(PassT::ID()) &&
 503            "This analysis pass was not registered prior to being queried");
 504
 505     const ResultConceptT *ResultConcept =
 506         derived_this()->getCachedResultImpl(PassT::ID(), IR);
 507     if (!ResultConcept)
 508       return 0;
 509
 510     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
 511         ResultModelT;
 512     return &static_cast<const ResultModelT *>(ResultConcept)->Result;
 513   }
 514
 515   /// \brief Register an analysis pass with the manager.
 516   ///
 517   /// This provides an initialized and set-up analysis pass to the analysis
 518   /// manager. Whomever is setting up analysis passes must use this to populate
 519   /// the manager with all of the analysis passes available.
 520   template <typename PassT> void registerPass(PassT Pass) {
 521     assert(!AnalysisPasses.count(PassT::ID()) &&
 522            "Registered the same analysis pass twice!");
 523     typedef detail::AnalysisPassModel<IRUnitT, DerivedT, PassT> PassModelT;
 524     AnalysisPasses[PassT::ID()] = new PassModelT(llvm_move(Pass));
 525   }
 526
 527   /// \brief Invalidate a specific analysis pass for an IR module.
 528   ///
 529   /// Note that the analysis result can disregard invalidation.
 530   template <typename PassT> void invalidate(Module *M) {
 531     assert(AnalysisPasses.count(PassT::ID()) &&
 532            "This analysis pass was not registered prior to being invalidated");
 533     derived_this()->invalidateImpl(PassT::ID(), M);
 534   }
 535
 536   /// \brief Invalidate analyses cached for an IR unit.
 537   ///
 538   /// Walk through all of the analyses pertaining to this unit of IR and
 539   /// invalidate them unless they are preserved by the PreservedAnalyses set.
 540   void invalidate(IRUnitT IR, const PreservedAnalyses &PA) {
 541     derived_this()->invalidateImpl(IR, PA);
 542   }
 543
 544 protected:
 545   /// \brief Lookup a registered analysis pass.
 546   PassConceptT &lookupPass(void *PassID) {
 547     typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(PassID);
 548     assert(PI != AnalysisPasses.end() &&
 549            "Analysis passes must be registered prior to being queried!");
 550     return *PI->second;
 551   }
 552
 553   /// \brief Lookup a registered analysis pass.
 554   const PassConceptT &lookupPass(void *PassID) const {
 555     typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(PassID);
 556     assert(PI != AnalysisPasses.end() &&
 557            "Analysis passes must be registered prior to being queried!");
 558     return *PI->second;
 559   }
 560
 561 private:
 562   /// \brief Map type from module analysis pass ID to pass concept pointer.
 563   typedef DenseMap<void *, polymorphic_ptr<PassConceptT> > AnalysisPassMapT;
 564
 565   /// \brief Collection of module analysis passes, indexed by ID.
 566   AnalysisPassMapT AnalysisPasses;
 567 };
 568
 569 }
 570
 571 /// \brief A module analysis pass manager with lazy running and caching of
 572 /// results.
 573 class ModuleAnalysisManager
 574     : public detail::AnalysisManagerBase<ModuleAnalysisManager, Module *> {
 575   friend class detail::AnalysisManagerBase<ModuleAnalysisManager, Module *>;
 576   typedef detail::AnalysisManagerBase<ModuleAnalysisManager, Module *> BaseT;
 577   typedef BaseT::ResultConceptT ResultConceptT;
 578   typedef BaseT::PassConceptT PassConceptT;
 579
 580 public:
 581   // Public methods provided by the base class.
 582
 583 private:
 584   /// \brief Get a module pass result, running the pass if necessary.
 585   const ResultConceptT &getResultImpl(void *PassID, Module *M);
 586
 587   /// \brief Get a cached module pass result or return null.
 588   const ResultConceptT *getCachedResultImpl(void *PassID, Module *M) const;
 589
 590   /// \brief Invalidate a module pass result.
 591   void invalidateImpl(void *PassID, Module *M);
 592
 593   /// \brief Invalidate results across a module.
 594   void invalidateImpl(Module *M, const PreservedAnalyses &PA);
 595
 596   /// \brief Map type from module analysis pass ID to pass result concept pointer.
 597   typedef DenseMap<void *,
 598                    polymorphic_ptr<detail::AnalysisResultConcept<Module *> > >
 599       ModuleAnalysisResultMapT;
 600
 601   /// \brief Cache of computed module analysis results for this module.
 602   ModuleAnalysisResultMapT ModuleAnalysisResults;
 603 };
 604
 605 /// \brief A function analysis manager to coordinate and cache analyses run over
 606 /// a module.
 607 class FunctionAnalysisManager
 608     : public detail::AnalysisManagerBase<FunctionAnalysisManager, Function *> {
 609   friend class detail::AnalysisManagerBase<FunctionAnalysisManager, Function *>;
 610   typedef detail::AnalysisManagerBase<FunctionAnalysisManager, Function *> BaseT;
 611   typedef BaseT::ResultConceptT ResultConceptT;
 612   typedef BaseT::PassConceptT PassConceptT;
 613
 614 public:
 615   // Most public APIs are inherited from the CRTP base class.
 616
 617   /// \brief Returns true if the analysis manager has an empty results cache.
 618   bool empty() const;
 619
 620   /// \brief Clear the function analysis result cache.
 621   ///
 622   /// This routine allows cleaning up when the set of functions itself has
 623   /// potentially changed, and thus we can't even look up a a result and
 624   /// invalidate it directly. Notably, this does *not* call invalidate
 625   /// functions as there is nothing to be done for them.
 626   void clear();
 627
 628 private:
 629   /// \brief Get a function pass result, running the pass if necessary.
 630   const ResultConceptT &getResultImpl(void *PassID, Function *F);
 631
 632   /// \brief Get a cached function pass result or return null.
 633   const ResultConceptT *getCachedResultImpl(void *PassID, Function *F) const;
 634
 635   /// \brief Invalidate a function pass result.
 636   void invalidateImpl(void *PassID, Function *F);
 637
 638   /// \brief Invalidate the results for a function..
 639   void invalidateImpl(Function *F, const PreservedAnalyses &PA);
 640
 641   /// \brief List of function analysis pass IDs and associated concept pointers.
 642   ///
 643   /// Requires iterators to be valid across appending new entries and arbitrary
 644   /// erases. Provides both the pass ID and concept pointer such that it is
 645   /// half of a bijection and provides storage for the actual result concept.
 646   typedef std::list<std::pair<
 647       void *, polymorphic_ptr<detail::AnalysisResultConcept<Function *> > > >
 648       FunctionAnalysisResultListT;
 649
 650   /// \brief Map type from function pointer to our custom list type.
 651   typedef DenseMap<Function *, FunctionAnalysisResultListT>
 652   FunctionAnalysisResultListMapT;
 653
 654   /// \brief Map from function to a list of function analysis results.
 655   ///
 656   /// Provides linear time removal of all analysis results for a function and
 657   /// the ultimate storage for a particular cached analysis result.
 658   FunctionAnalysisResultListMapT FunctionAnalysisResultLists;
 659
 660   /// \brief Map type from a pair of analysis ID and function pointer to an
 661   /// iterator into a particular result list.
 662   typedef DenseMap<std::pair<void *, Function *>,
 663                    FunctionAnalysisResultListT::iterator>
 664       FunctionAnalysisResultMapT;
 665
 666   /// \brief Map from an analysis ID and function to a particular cached
 667   /// analysis result.
 668   FunctionAnalysisResultMapT FunctionAnalysisResults;
 669 };
 670
 671 /// \brief A module analysis which acts as a proxy for a function analysis
 672 /// manager.
 673 ///
 674 /// This primarily proxies invalidation information from the module analysis
 675 /// manager and module pass manager to a function analysis manager. You should
 676 /// never use a function analysis manager from within (transitively) a module
 677 /// pass manager unless your parent module pass has received a proxy result
 678 /// object for it.
 679 class FunctionAnalysisManagerModuleProxy {
 680 public:
 681   class Result;
 682
 683   static void *ID() { return (void *)&PassID; }
 684
 685   FunctionAnalysisManagerModuleProxy(FunctionAnalysisManager &FAM) : FAM(FAM) {}
 686
 687   /// \brief Run the analysis pass and create our proxy result object.
 688   ///
 689   /// This doesn't do any interesting work, it is primarily used to insert our
 690   /// proxy result object into the module analysis cache so that we can proxy
 691   /// invalidation to the function analysis manager.
 692   ///
 693   /// In debug builds, it will also assert that the analysis manager is empty
 694   /// as no queries should arrive at the function analysis manager prior to
 695   /// this analysis being requested.
 696   Result run(Module *M);
 697
 698 private:
 699   static char PassID;
 700
 701   FunctionAnalysisManager &FAM;
 702 };
 703
 704 /// \brief The result proxy object for the
 705 /// \c FunctionAnalysisManagerModuleProxy.
 706 ///
 707 /// See its documentation for more information.
 708 class FunctionAnalysisManagerModuleProxy::Result {
 709 public:
 710   Result(FunctionAnalysisManager &FAM) : FAM(FAM) {}
 711   ~Result();
 712
 713   /// \brief Accessor for the \c FunctionAnalysisManager.
 714   FunctionAnalysisManager &getManager() const { return FAM; }
 715
 716   /// \brief Handler for invalidation of the module.
 717   ///
 718   /// If this analysis itself is preserved, then we assume that the set of \c
 719   /// Function objects in the \c Module hasn't changed and thus we don't need
 720   /// to invalidate *all* cached data associated with a \c Function* in the \c
 721   /// FunctionAnalysisManager.
 722   ///
 723   /// Regardless of whether this analysis is marked as preserved, all of the
 724   /// analyses in the \c FunctionAnalysisManager are potentially invalidated
 725   /// based on the set of preserved analyses.
 726   bool invalidate(Module *M, const PreservedAnalyses &PA);
 727
 728 private:
 729   FunctionAnalysisManager &FAM;
 730 };
 731
 732 /// \brief A function analysis which acts as a proxy for a module analysis
 733 /// manager.
 734 ///
 735 /// This primarily provides an accessor to a parent module analysis manager to
 736 /// function passes. Only the const interface of the module analysis manager is
 737 /// provided to indicate that once inside of a function analysis pass you
 738 /// cannot request a module analysis to actually run. Instead, the user must
 739 /// rely on the \c getCachedResult API.
 740 ///
 741 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
 742 /// the recursive return path of each layer of the pass manager and the
 743 /// returned PreservedAnalysis set.
 744 class ModuleAnalysisManagerFunctionProxy {
 745 public:
 746   /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
 747   class Result {
 748   public:
 749     Result(const ModuleAnalysisManager &MAM) : MAM(MAM) {}
 750
 751     const ModuleAnalysisManager &getManager() const { return MAM; }
 752
 753     /// \brief Handle invalidation by ignoring it, this pass is immutable.
 754     bool invalidate(Function *) { return false; }
 755
 756   private:
 757     const ModuleAnalysisManager &MAM;
 758   };
 759
 760   static void *ID() { return (void *)&PassID; }
 761
 762   ModuleAnalysisManagerFunctionProxy(const ModuleAnalysisManager &MAM)
 763       : MAM(MAM) {}
 764
 765   /// \brief Run the analysis pass and create our proxy result object.
 766   /// Nothing to see here, it just forwards the \c MAM reference into the
 767   /// result.
 768   Result run(Function *) { return Result(MAM); }
 769
 770 private:
 771   static char PassID;
 772
 773   const ModuleAnalysisManager &MAM;
 774 };
 775
 776 /// \brief Trivial adaptor that maps from a module to its functions.
 777 ///
 778 /// Designed to allow composition of a FunctionPass(Manager) and
 779 /// a ModulePassManager. Note that if this pass is constructed with a pointer
 780 /// to a \c ModuleAnalysisManager it will run the
 781 /// \c FunctionAnalysisManagerModuleProxy analysis prior to running the function
 782 /// pass over the module to enable a \c FunctionAnalysisManager to be used
 783 /// within this run safely.
 784 template <typename FunctionPassT>
 785 class ModuleToFunctionPassAdaptor {
 786 public:
 787   explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
 788       : Pass(llvm_move(Pass)) {}
 789
 790   /// \brief Runs the function pass across every function in the module.
 791   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) {
 792     FunctionAnalysisManager *FAM = 0;
 793     if (AM)
 794       // Setup the function analysis manager from its proxy.
 795       FAM = &AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 796
 797     PreservedAnalyses PA = PreservedAnalyses::all();
 798     for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
 799       PreservedAnalyses PassPA = Pass.run(I, FAM);
 800
 801       // We know that the function pass couldn't have invalidated any other
 802       // function's analyses (that's the contract of a function pass), so
 803       // directly handle the function analysis manager's invalidation here.
 804       if (FAM)
 805         FAM->invalidate(I, PassPA);
 806
 807       // Then intersect the preserved set so that invalidation of module
 808       // analyses will eventually occur when the module pass completes.
 809       PA.intersect(llvm_move(PassPA));
 810     }
 811
 812     // By definition we preserve the proxy. This precludes *any* invalidation
 813     // of function analyses by the proxy, but that's OK because we've taken
 814     // care to invalidate analyses in the function analysis manager
 815     // incrementally above.
 816     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 817     return PA;
 818   }
 819
 820   static StringRef name() { return "ModuleToFunctionPassAdaptor"; }
 821
 822 private:
 823   FunctionPassT Pass;
 824 };
 825
 826 /// \brief A function to deduce a function pass type and wrap it in the
 827 /// templated adaptor.
 828 template <typename FunctionPassT>
 829 ModuleToFunctionPassAdaptor<FunctionPassT>
 830 createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
 831   return ModuleToFunctionPassAdaptor<FunctionPassT>(llvm_move(Pass));
 832 }
 833
 834 }
 835
 836 #endif