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