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