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