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/IR/PassManagerInternal.h"
  47 #include "llvm/Support/CommandLine.h"
  48 #include "llvm/Support/Debug.h"
  49 #include "llvm/Support/raw_ostream.h"
  50 #include "llvm/Support/type_traits.h"
  51 #include <list>
  52 #include <memory>
  53 #include <vector>
  54
  55 namespace llvm {
  56
  57 class Module;
  58 class Function;
  59
  60 /// \brief An abstract set of preserved analyses following a transformation pass
  61 /// run.
  62 ///
  63 /// When a transformation pass is run, it can return a set of analyses whose
  64 /// results were preserved by that transformation. The default set is "none",
  65 /// and preserving analyses must be done explicitly.
  66 ///
  67 /// There is also an explicit all state which can be used (for example) when
  68 /// the IR is not mutated at all.
  69 class PreservedAnalyses {
  70 public:
  71   // We have to explicitly define all the special member functions because MSVC
  72   // refuses to generate them.
  73   PreservedAnalyses() {}
  74   PreservedAnalyses(const PreservedAnalyses &Arg)
  75       : PreservedPassIDs(Arg.PreservedPassIDs) {}
  76   PreservedAnalyses(PreservedAnalyses &&Arg)
  77       : PreservedPassIDs(std::move(Arg.PreservedPassIDs)) {}
  78   friend void swap(PreservedAnalyses &LHS, PreservedAnalyses &RHS) {
  79     using std::swap;
  80     swap(LHS.PreservedPassIDs, RHS.PreservedPassIDs);
  81   }
  82   PreservedAnalyses &operator=(PreservedAnalyses RHS) {
  83     swap(*this, RHS);
  84     return *this;
  85   }
  86
  87   /// \brief Convenience factory function for the empty preserved set.
  88   static PreservedAnalyses none() { return PreservedAnalyses(); }
  89
  90   /// \brief Construct a special preserved set that preserves all passes.
  91   static PreservedAnalyses all() {
  92     PreservedAnalyses PA;
  93     PA.PreservedPassIDs.insert((void *)AllPassesID);
  94     return PA;
  95   }
  96
  97   /// \brief Mark a particular pass as preserved, adding it to the set.
  98   template <typename PassT> void preserve() { preserve(PassT::ID()); }
  99
 100   /// \brief Mark an abstract PassID as preserved, adding it to the set.
 101   void preserve(void *PassID) {
 102     if (!areAllPreserved())
 103       PreservedPassIDs.insert(PassID);
 104   }
 105
 106   /// \brief Intersect this set with another in place.
 107   ///
 108   /// This is a mutating operation on this preserved set, removing all
 109   /// preserved passes which are not also preserved in the argument.
 110   void intersect(const PreservedAnalyses &Arg) {
 111     if (Arg.areAllPreserved())
 112       return;
 113     if (areAllPreserved()) {
 114       PreservedPassIDs = Arg.PreservedPassIDs;
 115       return;
 116     }
 117     for (void *P : PreservedPassIDs)
 118       if (!Arg.PreservedPassIDs.count(P))
 119         PreservedPassIDs.erase(P);
 120   }
 121
 122   /// \brief Intersect this set with a temporary other set in place.
 123   ///
 124   /// This is a mutating operation on this preserved set, removing all
 125   /// preserved passes which are not also preserved in the argument.
 126   void intersect(PreservedAnalyses &&Arg) {
 127     if (Arg.areAllPreserved())
 128       return;
 129     if (areAllPreserved()) {
 130       PreservedPassIDs = std::move(Arg.PreservedPassIDs);
 131       return;
 132     }
 133     for (void *P : PreservedPassIDs)
 134       if (!Arg.PreservedPassIDs.count(P))
 135         PreservedPassIDs.erase(P);
 136   }
 137
 138   /// \brief Query whether a pass is marked as preserved by this set.
 139   template <typename PassT> bool preserved() const {
 140     return preserved(PassT::ID());
 141   }
 142
 143   /// \brief Query whether an abstract pass ID is marked as preserved by this
 144   /// set.
 145   bool preserved(void *PassID) const {
 146     return PreservedPassIDs.count((void *)AllPassesID) ||
 147            PreservedPassIDs.count(PassID);
 148   }
 149
 150   /// \brief Test whether all passes are preserved.
 151   ///
 152   /// This is used primarily to optimize for the case of no changes which will
 153   /// common in many scenarios.
 154   bool areAllPreserved() const {
 155     return PreservedPassIDs.count((void *)AllPassesID);
 156   }
 157
 158 private:
 159   // Note that this must not be -1 or -2 as those are already used by the
 160   // SmallPtrSet.
 161   static const uintptr_t AllPassesID = (intptr_t)(-3);
 162
 163   SmallPtrSet<void *, 2> PreservedPassIDs;
 164 };
 165
 166 // Forward declare the analysis manager template.
 167 template <typename IRUnitT> class AnalysisManager;
 168
 169 /// \brief Manages a sequence of passes over units of IR.
 170 ///
 171 /// A pass manager contains a sequence of passes to run over units of IR. It is
 172 /// itself a valid pass over that unit of IR, and when over some given IR will
 173 /// run each pass in sequence. This is the primary and most basic building
 174 /// block of a pass pipeline.
 175 ///
 176 /// If it is run with an \c AnalysisManager<IRUnitT> argument, it will propagate
 177 /// that analysis manager to each pass it runs, as well as calling the analysis
 178 /// manager's invalidation routine with the PreservedAnalyses of each pass it
 179 /// runs.
 180 template <typename IRUnitT> class PassManager {
 181 public:
 182   /// \brief Construct a pass manager.
 183   ///
 184   /// It can be passed a flag to get debug logging as the passes are run.
 185   PassManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
 186   // We have to explicitly define all the special member functions because MSVC
 187   // refuses to generate them.
 188   PassManager(PassManager &&Arg)
 189       : Passes(std::move(Arg.Passes)),
 190         DebugLogging(std::move(Arg.DebugLogging)) {}
 191   PassManager &operator=(PassManager &&RHS) {
 192     Passes = std::move(RHS.Passes);
 193     DebugLogging = std::move(RHS.DebugLogging);
 194     return *this;
 195   }
 196
 197   /// \brief Run all of the passes in this manager over the IR.
 198   PreservedAnalyses run(IRUnitT &IR, AnalysisManager<IRUnitT> *AM = nullptr) {
 199     PreservedAnalyses PA = PreservedAnalyses::all();
 200
 201     if (DebugLogging)
 202       dbgs() << "Starting pass manager run.\n";
 203
 204     for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
 205       if (DebugLogging)
 206         dbgs() << "Running pass: " << Passes[Idx]->name() << " on "
 207                << IR.getName() << "\n";
 208
 209       PreservedAnalyses PassPA = Passes[Idx]->run(IR, AM);
 210
 211       // If we have an active analysis manager at this level we want to ensure
 212       // we update it as each pass runs and potentially invalidates analyses.
 213       // We also update the preserved set of analyses based on what analyses we
 214       // have already handled the invalidation for here and don't need to
 215       // invalidate when finished.
 216       if (AM)
 217         PassPA = AM->invalidate(IR, std::move(PassPA));
 218
 219       // Finally, we intersect the final preserved analyses to compute the
 220       // aggregate preserved set for this pass manager.
 221       PA.intersect(std::move(PassPA));
 222
 223       // FIXME: Historically, the pass managers all called the LLVM context's
 224       // yield function here. We don't have a generic way to acquire the
 225       // context and it isn't yet clear what the right pattern is for yielding
 226       // in the new pass manager so it is currently omitted.
 227       //IR.getContext().yield();
 228     }
 229
 230     if (DebugLogging)
 231       dbgs() << "Finished pass manager run.\n";
 232
 233     return PA;
 234   }
 235
 236   template <typename PassT> void addPass(PassT Pass) {
 237     typedef detail::PassModel<IRUnitT, PassT> PassModelT;
 238     Passes.emplace_back(new PassModelT(std::move(Pass)));
 239   }
 240
 241   static StringRef name() { return "PassManager"; }
 242
 243 private:
 244   typedef detail::PassConcept<IRUnitT> PassConceptT;
 245
 246   PassManager(const PassManager &) = delete;
 247   PassManager &operator=(const PassManager &) = delete;
 248
 249   std::vector<std::unique_ptr<PassConceptT>> Passes;
 250
 251   /// \brief Flag indicating whether we should do debug logging.
 252   bool DebugLogging;
 253 };
 254
 255 /// \brief Convenience typedef for a pass manager over modules.
 256 typedef PassManager<Module> ModulePassManager;
 257
 258 /// \brief Convenience typedef for a pass manager over functions.
 259 typedef PassManager<Function> FunctionPassManager;
 260
 261 namespace detail {
 262
 263 /// \brief A CRTP base used to implement analysis managers.
 264 ///
 265 /// This class template serves as the boiler plate of an analysis manager. Any
 266 /// analysis manager can be implemented on top of this base class. Any
 267 /// implementation will be required to provide specific hooks:
 268 ///
 269 /// - getResultImpl
 270 /// - getCachedResultImpl
 271 /// - invalidateImpl
 272 ///
 273 /// The details of the call pattern are within.
 274 ///
 275 /// Note that there is also a generic analysis manager template which implements
 276 /// the above required functions along with common datastructures used for
 277 /// managing analyses. This base class is factored so that if you need to
 278 /// customize the handling of a specific IR unit, you can do so without
 279 /// replicating *all* of the boilerplate.
 280 template <typename DerivedT, typename IRUnitT> class AnalysisManagerBase {
 281   DerivedT *derived_this() { return static_cast<DerivedT *>(this); }
 282   const DerivedT *derived_this() const {
 283     return static_cast<const DerivedT *>(this);
 284   }
 285
 286   AnalysisManagerBase(const AnalysisManagerBase &) = delete;
 287   AnalysisManagerBase &
 288   operator=(const AnalysisManagerBase &) = delete;
 289
 290 protected:
 291   typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT;
 292   typedef detail::AnalysisPassConcept<IRUnitT> PassConceptT;
 293
 294   // FIXME: Provide template aliases for the models when we're using C++11 in
 295   // a mode supporting them.
 296
 297   // We have to explicitly define all the special member functions because MSVC
 298   // refuses to generate them.
 299   AnalysisManagerBase() {}
 300   AnalysisManagerBase(AnalysisManagerBase &&Arg)
 301       : AnalysisPasses(std::move(Arg.AnalysisPasses)) {}
 302   AnalysisManagerBase &operator=(AnalysisManagerBase &&RHS) {
 303     AnalysisPasses = std::move(RHS.AnalysisPasses);
 304     return *this;
 305   }
 306
 307 public:
 308   /// \brief Get the result of an analysis pass for this module.
 309   ///
 310   /// If there is not a valid cached result in the manager already, this will
 311   /// re-run the analysis to produce a valid result.
 312   template <typename PassT> typename PassT::Result &getResult(IRUnitT &IR) {
 313     assert(AnalysisPasses.count(PassT::ID()) &&
 314            "This analysis pass was not registered prior to being queried");
 315
 316     ResultConceptT &ResultConcept =
 317         derived_this()->getResultImpl(PassT::ID(), IR);
 318     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
 319         ResultModelT;
 320     return static_cast<ResultModelT &>(ResultConcept).Result;
 321   }
 322
 323   /// \brief Get the cached result of an analysis pass for this module.
 324   ///
 325   /// This method never runs the analysis.
 326   ///
 327   /// \returns null if there is no cached result.
 328   template <typename PassT>
 329   typename PassT::Result *getCachedResult(IRUnitT &IR) const {
 330     assert(AnalysisPasses.count(PassT::ID()) &&
 331            "This analysis pass was not registered prior to being queried");
 332
 333     ResultConceptT *ResultConcept =
 334         derived_this()->getCachedResultImpl(PassT::ID(), IR);
 335     if (!ResultConcept)
 336       return nullptr;
 337
 338     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
 339         ResultModelT;
 340     return &static_cast<ResultModelT *>(ResultConcept)->Result;
 341   }
 342
 343   /// \brief Register an analysis pass with the manager.
 344   ///
 345   /// This provides an initialized and set-up analysis pass to the analysis
 346   /// manager. Whomever is setting up analysis passes must use this to populate
 347   /// the manager with all of the analysis passes available.
 348   template <typename PassT> void registerPass(PassT Pass) {
 349     assert(!AnalysisPasses.count(PassT::ID()) &&
 350            "Registered the same analysis pass twice!");
 351     typedef detail::AnalysisPassModel<IRUnitT, PassT> PassModelT;
 352     AnalysisPasses[PassT::ID()].reset(new PassModelT(std::move(Pass)));
 353   }
 354
 355   /// \brief Invalidate a specific analysis pass for an IR module.
 356   ///
 357   /// Note that the analysis result can disregard invalidation.
 358   template <typename PassT> void invalidate(IRUnitT &IR) {
 359     assert(AnalysisPasses.count(PassT::ID()) &&
 360            "This analysis pass was not registered prior to being invalidated");
 361     derived_this()->invalidateImpl(PassT::ID(), IR);
 362   }
 363
 364   /// \brief Invalidate analyses cached for an IR unit.
 365   ///
 366   /// Walk through all of the analyses pertaining to this unit of IR and
 367   /// invalidate them unless they are preserved by the PreservedAnalyses set.
 368   /// We accept the PreservedAnalyses set by value and update it with each
 369   /// analyis pass which has been successfully invalidated and thus can be
 370   /// preserved going forward. The updated set is returned.
 371   PreservedAnalyses invalidate(IRUnitT &IR, PreservedAnalyses PA) {
 372     return derived_this()->invalidateImpl(IR, std::move(PA));
 373   }
 374
 375 protected:
 376   /// \brief Lookup a registered analysis pass.
 377   PassConceptT &lookupPass(void *PassID) {
 378     typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(PassID);
 379     assert(PI != AnalysisPasses.end() &&
 380            "Analysis passes must be registered prior to being queried!");
 381     return *PI->second;
 382   }
 383
 384   /// \brief Lookup a registered analysis pass.
 385   const PassConceptT &lookupPass(void *PassID) const {
 386     typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(PassID);
 387     assert(PI != AnalysisPasses.end() &&
 388            "Analysis passes must be registered prior to being queried!");
 389     return *PI->second;
 390   }
 391
 392 private:
 393   /// \brief Map type from module analysis pass ID to pass concept pointer.
 394   typedef DenseMap<void *, std::unique_ptr<PassConceptT>> AnalysisPassMapT;
 395
 396   /// \brief Collection of module analysis passes, indexed by ID.
 397   AnalysisPassMapT AnalysisPasses;
 398 };
 399
 400 } // End namespace detail
 401
 402 /// \brief A generic analysis pass manager with lazy running and caching of
 403 /// results.
 404 ///
 405 /// This analysis manager can be used for any IR unit where the address of the
 406 /// IR unit sufficies as its identity. It manages the cache for a unit of IR via
 407 /// the address of each unit of IR cached.
 408 template <typename IRUnitT>
 409 class AnalysisManager
 410     : public detail::AnalysisManagerBase<AnalysisManager<IRUnitT>, IRUnitT> {
 411   friend class detail::AnalysisManagerBase<AnalysisManager<IRUnitT>, IRUnitT>;
 412   typedef detail::AnalysisManagerBase<AnalysisManager<IRUnitT>, IRUnitT> BaseT;
 413   typedef typename BaseT::ResultConceptT ResultConceptT;
 414   typedef typename BaseT::PassConceptT PassConceptT;
 415
 416 public:
 417   // Most public APIs are inherited from the CRTP base class.
 418
 419   /// \brief Construct an empty analysis manager.
 420   ///
 421   /// A flag can be passed to indicate that the manager should perform debug
 422   /// logging.
 423   AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
 424
 425   // We have to explicitly define all the special member functions because MSVC
 426   // refuses to generate them.
 427   AnalysisManager(AnalysisManager &&Arg)
 428       : BaseT(std::move(static_cast<BaseT &>(Arg))),
 429         AnalysisResults(std::move(Arg.AnalysisResults)),
 430         DebugLogging(std::move(Arg.DebugLogging)) {}
 431   AnalysisManager &operator=(AnalysisManager &&RHS) {
 432     BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
 433     AnalysisResults = std::move(RHS.AnalysisResults);
 434     DebugLogging = std::move(RHS.DebugLogging);
 435     return *this;
 436   }
 437
 438   /// \brief Returns true if the analysis manager has an empty results cache.
 439   bool empty() const {
 440     assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&
 441            "The storage and index of analysis results disagree on how many "
 442            "there are!");
 443     return AnalysisResults.empty();
 444   }
 445
 446   /// \brief Clear the analysis result cache.
 447   ///
 448   /// This routine allows cleaning up when the set of IR units itself has
 449   /// potentially changed, and thus we can't even look up a a result and
 450   /// invalidate it directly. Notably, this does *not* call invalidate functions
 451   /// as there is nothing to be done for them.
 452   void clear() {
 453     AnalysisResults.clear();
 454     AnalysisResultLists.clear();
 455   }
 456
 457 private:
 458   AnalysisManager(const AnalysisManager &) = delete;
 459   AnalysisManager &operator=(const AnalysisManager &) = delete;
 460
 461   /// \brief Get an analysis result, running the pass if necessary.
 462   ResultConceptT &getResultImpl(void *PassID, IRUnitT &IR) {
 463     typename AnalysisResultMapT::iterator RI;
 464     bool Inserted;
 465     std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair(
 466         std::make_pair(PassID, &IR), typename AnalysisResultListT::iterator()));
 467
 468     // If we don't have a cached result for this function, look up the pass and
 469     // run it to produce a result, which we then add to the cache.
 470     if (Inserted) {
 471       auto &P = this->lookupPass(PassID);
 472       if (DebugLogging)
 473         dbgs() << "Running analysis: " << P.name() << "\n";
 474       AnalysisResultListT &ResultList = AnalysisResultLists[&IR];
 475       ResultList.emplace_back(PassID, P.run(IR, this));
 476
 477       // P.run may have inserted elements into AnalysisResults and invalidated
 478       // RI.
 479       RI = AnalysisResults.find(std::make_pair(PassID, &IR));
 480       assert(RI != AnalysisResults.end() && "we just inserted it!");
 481
 482       RI->second = std::prev(ResultList.end());
 483     }
 484
 485     return *RI->second->second;
 486   }
 487
 488   /// \brief Get a cached analysis result or return null.
 489   ResultConceptT *getCachedResultImpl(void *PassID, IRUnitT &IR) const {
 490     typename AnalysisResultMapT::const_iterator RI =
 491         AnalysisResults.find(std::make_pair(PassID, &IR));
 492     return RI == AnalysisResults.end() ? nullptr : &*RI->second->second;
 493   }
 494
 495   /// \brief Invalidate a function pass result.
 496   void invalidateImpl(void *PassID, IRUnitT &IR) {
 497     typename AnalysisResultMapT::iterator RI =
 498         AnalysisResults.find(std::make_pair(PassID, &IR));
 499     if (RI == AnalysisResults.end())
 500       return;
 501
 502     if (DebugLogging)
 503       dbgs() << "Invalidating analysis: " << this->lookupPass(PassID).name()
 504              << "\n";
 505     AnalysisResultLists[&IR].erase(RI->second);
 506     AnalysisResults.erase(RI);
 507   }
 508
 509   /// \brief Invalidate the results for a function..
 510   PreservedAnalyses invalidateImpl(IRUnitT &IR, PreservedAnalyses PA) {
 511     // Short circuit for a common case of all analyses being preserved.
 512     if (PA.areAllPreserved())
 513       return PA;
 514
 515     if (DebugLogging)
 516       dbgs() << "Invalidating all non-preserved analyses for: "
 517              << IR.getName() << "\n";
 518
 519     // Clear all the invalidated results associated specifically with this
 520     // function.
 521     SmallVector<void *, 8> InvalidatedPassIDs;
 522     AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
 523     for (typename AnalysisResultListT::iterator I = ResultsList.begin(),
 524                                                 E = ResultsList.end();
 525          I != E;) {
 526       void *PassID = I->first;
 527
 528       // Pass the invalidation down to the pass itself to see if it thinks it is
 529       // necessary. The analysis pass can return false if no action on the part
 530       // of the analysis manager is required for this invalidation event.
 531       if (I->second->invalidate(IR, PA)) {
 532         if (DebugLogging)
 533           dbgs() << "Invalidating analysis: " << this->lookupPass(PassID).name()
 534                  << "\n";
 535
 536         InvalidatedPassIDs.push_back(I->first);
 537         I = ResultsList.erase(I);
 538       } else {
 539         ++I;
 540       }
 541
 542       // After handling each pass, we mark it as preserved. Once we've
 543       // invalidated any stale results, the rest of the system is allowed to
 544       // start preserving this analysis again.
 545       PA.preserve(PassID);
 546     }
 547     while (!InvalidatedPassIDs.empty())
 548       AnalysisResults.erase(
 549           std::make_pair(InvalidatedPassIDs.pop_back_val(), &IR));
 550     if (ResultsList.empty())
 551       AnalysisResultLists.erase(&IR);
 552
 553     return PA;
 554   }
 555
 556   /// \brief List of function analysis pass IDs and associated concept pointers.
 557   ///
 558   /// Requires iterators to be valid across appending new entries and arbitrary
 559   /// erases. Provides both the pass ID and concept pointer such that it is
 560   /// half of a bijection and provides storage for the actual result concept.
 561   typedef std::list<std::pair<
 562       void *, std::unique_ptr<detail::AnalysisResultConcept<IRUnitT>>>>
 563       AnalysisResultListT;
 564
 565   /// \brief Map type from function pointer to our custom list type.
 566   typedef DenseMap<IRUnitT *, AnalysisResultListT> AnalysisResultListMapT;
 567
 568   /// \brief Map from function to a list of function analysis results.
 569   ///
 570   /// Provides linear time removal of all analysis results for a function and
 571   /// the ultimate storage for a particular cached analysis result.
 572   AnalysisResultListMapT AnalysisResultLists;
 573
 574   /// \brief Map type from a pair of analysis ID and function pointer to an
 575   /// iterator into a particular result list.
 576   typedef DenseMap<std::pair<void *, IRUnitT *>,
 577                    typename AnalysisResultListT::iterator> AnalysisResultMapT;
 578
 579   /// \brief Map from an analysis ID and function to a particular cached
 580   /// analysis result.
 581   AnalysisResultMapT AnalysisResults;
 582
 583   /// \brief A flag indicating whether debug logging is enabled.
 584   bool DebugLogging;
 585 };
 586
 587 /// \brief Convenience typedef for the Module analysis manager.
 588 typedef AnalysisManager<Module> ModuleAnalysisManager;
 589
 590 /// \brief Convenience typedef for the Function analysis manager.
 591 typedef AnalysisManager<Function> FunctionAnalysisManager;
 592
 593 /// \brief A module analysis which acts as a proxy for a function analysis
 594 /// manager.
 595 ///
 596 /// This primarily proxies invalidation information from the module analysis
 597 /// manager and module pass manager to a function analysis manager. You should
 598 /// never use a function analysis manager from within (transitively) a module
 599 /// pass manager unless your parent module pass has received a proxy result
 600 /// object for it.
 601 class FunctionAnalysisManagerModuleProxy {
 602 public:
 603   class Result;
 604
 605   static void *ID() { return (void *)&PassID; }
 606
 607   static StringRef name() { return "FunctionAnalysisManagerModuleProxy"; }
 608
 609   explicit FunctionAnalysisManagerModuleProxy(FunctionAnalysisManager &FAM)
 610       : FAM(&FAM) {}
 611   // We have to explicitly define all the special member functions because MSVC
 612   // refuses to generate them.
 613   FunctionAnalysisManagerModuleProxy(
 614       const FunctionAnalysisManagerModuleProxy &Arg)
 615       : FAM(Arg.FAM) {}
 616   FunctionAnalysisManagerModuleProxy(FunctionAnalysisManagerModuleProxy &&Arg)
 617       : FAM(std::move(Arg.FAM)) {}
 618   FunctionAnalysisManagerModuleProxy &
 619   operator=(FunctionAnalysisManagerModuleProxy RHS) {
 620     std::swap(FAM, RHS.FAM);
 621     return *this;
 622   }
 623
 624   /// \brief Run the analysis pass and create our proxy result object.
 625   ///
 626   /// This doesn't do any interesting work, it is primarily used to insert our
 627   /// proxy result object into the module analysis cache so that we can proxy
 628   /// invalidation to the function analysis manager.
 629   ///
 630   /// In debug builds, it will also assert that the analysis manager is empty
 631   /// as no queries should arrive at the function analysis manager prior to
 632   /// this analysis being requested.
 633   Result run(Module &M);
 634
 635 private:
 636   static char PassID;
 637
 638   FunctionAnalysisManager *FAM;
 639 };
 640
 641 /// \brief The result proxy object for the
 642 /// \c FunctionAnalysisManagerModuleProxy.
 643 ///
 644 /// See its documentation for more information.
 645 class FunctionAnalysisManagerModuleProxy::Result {
 646 public:
 647   explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
 648   // We have to explicitly define all the special member functions because MSVC
 649   // refuses to generate them.
 650   Result(const Result &Arg) : FAM(Arg.FAM) {}
 651   Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
 652   Result &operator=(Result RHS) {
 653     std::swap(FAM, RHS.FAM);
 654     return *this;
 655   }
 656   ~Result();
 657
 658   /// \brief Accessor for the \c FunctionAnalysisManager.
 659   FunctionAnalysisManager &getManager() { return *FAM; }
 660
 661   /// \brief Handler for invalidation of the module.
 662   ///
 663   /// If this analysis itself is preserved, then we assume that the set of \c
 664   /// Function objects in the \c Module hasn't changed and thus we don't need
 665   /// to invalidate *all* cached data associated with a \c Function* in the \c
 666   /// FunctionAnalysisManager.
 667   ///
 668   /// Regardless of whether this analysis is marked as preserved, all of the
 669   /// analyses in the \c FunctionAnalysisManager are potentially invalidated
 670   /// based on the set of preserved analyses.
 671   bool invalidate(Module &M, const PreservedAnalyses &PA);
 672
 673 private:
 674   FunctionAnalysisManager *FAM;
 675 };
 676
 677 /// \brief A function analysis which acts as a proxy for a module analysis
 678 /// manager.
 679 ///
 680 /// This primarily provides an accessor to a parent module analysis manager to
 681 /// function passes. Only the const interface of the module analysis manager is
 682 /// provided to indicate that once inside of a function analysis pass you
 683 /// cannot request a module analysis to actually run. Instead, the user must
 684 /// rely on the \c getCachedResult API.
 685 ///
 686 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
 687 /// the recursive return path of each layer of the pass manager and the
 688 /// returned PreservedAnalysis set.
 689 class ModuleAnalysisManagerFunctionProxy {
 690 public:
 691   /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
 692   class Result {
 693   public:
 694     explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
 695     // We have to explicitly define all the special member functions because
 696     // MSVC refuses to generate them.
 697     Result(const Result &Arg) : MAM(Arg.MAM) {}
 698     Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
 699     Result &operator=(Result RHS) {
 700       std::swap(MAM, RHS.MAM);
 701       return *this;
 702     }
 703
 704     const ModuleAnalysisManager &getManager() const { return *MAM; }
 705
 706     /// \brief Handle invalidation by ignoring it, this pass is immutable.
 707     bool invalidate(Function &) { return false; }
 708
 709   private:
 710     const ModuleAnalysisManager *MAM;
 711   };
 712
 713   static void *ID() { return (void *)&PassID; }
 714
 715   static StringRef name() { return "ModuleAnalysisManagerFunctionProxy"; }
 716
 717   ModuleAnalysisManagerFunctionProxy(const ModuleAnalysisManager &MAM)
 718       : MAM(&MAM) {}
 719   // We have to explicitly define all the special member functions because MSVC
 720   // refuses to generate them.
 721   ModuleAnalysisManagerFunctionProxy(
 722       const ModuleAnalysisManagerFunctionProxy &Arg)
 723       : MAM(Arg.MAM) {}
 724   ModuleAnalysisManagerFunctionProxy(ModuleAnalysisManagerFunctionProxy &&Arg)
 725       : MAM(std::move(Arg.MAM)) {}
 726   ModuleAnalysisManagerFunctionProxy &
 727   operator=(ModuleAnalysisManagerFunctionProxy RHS) {
 728     std::swap(MAM, RHS.MAM);
 729     return *this;
 730   }
 731
 732   /// \brief Run the analysis pass and create our proxy result object.
 733   /// Nothing to see here, it just forwards the \c MAM reference into the
 734   /// result.
 735   Result run(Function &) { return Result(*MAM); }
 736
 737 private:
 738   static char PassID;
 739
 740   const ModuleAnalysisManager *MAM;
 741 };
 742
 743 /// \brief Trivial adaptor that maps from a module to its functions.
 744 ///
 745 /// Designed to allow composition of a FunctionPass(Manager) and
 746 /// a ModulePassManager. Note that if this pass is constructed with a pointer
 747 /// to a \c ModuleAnalysisManager it will run the
 748 /// \c FunctionAnalysisManagerModuleProxy analysis prior to running the function
 749 /// pass over the module to enable a \c FunctionAnalysisManager to be used
 750 /// within this run safely.
 751 ///
 752 /// Function passes run within this adaptor can rely on having exclusive access
 753 /// to the function they are run over. They should not read or modify any other
 754 /// functions! Other threads or systems may be manipulating other functions in
 755 /// the module, and so their state should never be relied on.
 756 /// FIXME: Make the above true for all of LLVM's actual passes, some still
 757 /// violate this principle.
 758 ///
 759 /// Function passes can also read the module containing the function, but they
 760 /// should not modify that module outside of the use lists of various globals.
 761 /// For example, a function pass is not permitted to add functions to the
 762 /// module.
 763 /// FIXME: Make the above true for all of LLVM's actual passes, some still
 764 /// violate this principle.
 765 template <typename FunctionPassT> class ModuleToFunctionPassAdaptor {
 766 public:
 767   explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
 768       : Pass(std::move(Pass)) {}
 769   // We have to explicitly define all the special member functions because MSVC
 770   // refuses to generate them.
 771   ModuleToFunctionPassAdaptor(const ModuleToFunctionPassAdaptor &Arg)
 772       : Pass(Arg.Pass) {}
 773   ModuleToFunctionPassAdaptor(ModuleToFunctionPassAdaptor &&Arg)
 774       : Pass(std::move(Arg.Pass)) {}
 775   friend void swap(ModuleToFunctionPassAdaptor &LHS,
 776                    ModuleToFunctionPassAdaptor &RHS) {
 777     using std::swap;
 778     swap(LHS.Pass, RHS.Pass);
 779   }
 780   ModuleToFunctionPassAdaptor &operator=(ModuleToFunctionPassAdaptor RHS) {
 781     swap(*this, RHS);
 782     return *this;
 783   }
 784
 785   /// \brief Runs the function pass across every function in the module.
 786   PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) {
 787     FunctionAnalysisManager *FAM = nullptr;
 788     if (AM)
 789       // Setup the function analysis manager from its proxy.
 790       FAM = &AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 791
 792     PreservedAnalyses PA = PreservedAnalyses::all();
 793     for (Function &F : M) {
 794       if (F.isDeclaration())
 795         continue;
 796
 797       PreservedAnalyses PassPA = Pass.run(F, FAM);
 798
 799       // We know that the function pass couldn't have invalidated any other
 800       // function's analyses (that's the contract of a function pass), so
 801       // directly handle the function analysis manager's invalidation here and
 802       // update our preserved set to reflect that these have already been
 803       // handled.
 804       if (FAM)
 805         PassPA = FAM->invalidate(F, std::move(PassPA));
 806
 807       // Then intersect the preserved set so that invalidation of module
 808       // analyses will eventually occur when the module pass completes.
 809       PA.intersect(std::move(PassPA));
 810     }
 811
 812     // By definition we preserve the proxy. This precludes *any* invalidation
 813     // of function analyses by the proxy, but that's OK because we've taken
 814     // care to invalidate analyses in the function analysis manager
 815     // incrementally above.
 816     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 817     return PA;
 818   }
 819
 820   static StringRef name() { return "ModuleToFunctionPassAdaptor"; }
 821
 822 private:
 823   FunctionPassT Pass;
 824 };
 825
 826 /// \brief A function to deduce a function pass type and wrap it in the
 827 /// templated adaptor.
 828 template <typename FunctionPassT>
 829 ModuleToFunctionPassAdaptor<FunctionPassT>
 830 createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
 831   return ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
 832 }
 833
 834 /// \brief A template utility pass to force an analysis result to be available.
 835 ///
 836 /// This is a no-op pass which simply forces a specific analysis pass's result
 837 /// to be available when it is run.
 838 template <typename AnalysisT> struct RequireAnalysisPass {
 839   /// \brief Run this pass over some unit of IR.
 840   ///
 841   /// This pass can be run over any unit of IR and use any analysis manager
 842   /// provided they satisfy the basic API requirements. When this pass is
 843   /// created, these methods can be instantiated to satisfy whatever the
 844   /// context requires.
 845   template <typename IRUnitT>
 846   PreservedAnalyses run(IRUnitT &Arg, AnalysisManager<IRUnitT> *AM) {
 847     if (AM)
 848       (void)AM->template getResult<AnalysisT>(Arg);
 849
 850     return PreservedAnalyses::all();
 851   }
 852
 853   static StringRef name() { return "RequireAnalysisPass"; }
 854 };
 855
 856 /// \brief A template utility pass to force an analysis result to be
 857 /// invalidated.
 858 ///
 859 /// This is a no-op pass which simply forces a specific analysis result to be
 860 /// invalidated when it is run.
 861 template <typename AnalysisT> struct InvalidateAnalysisPass {
 862   /// \brief Run this pass over some unit of IR.
 863   ///
 864   /// This pass can be run over any unit of IR and use any analysis manager
 865   /// provided they satisfy the basic API requirements. When this pass is
 866   /// created, these methods can be instantiated to satisfy whatever the
 867   /// context requires.
 868   template <typename IRUnitT>
 869   PreservedAnalyses run(IRUnitT &Arg, AnalysisManager<IRUnitT> *AM) {
 870     if (AM)
 871       // We have to directly invalidate the analysis result as we can't
 872       // enumerate all other analyses and use the preserved set to control it.
 873       (void)AM->template invalidate<AnalysisT>(Arg);
 874
 875     return PreservedAnalyses::all();
 876   }
 877
 878   static StringRef name() { return "InvalidateAnalysisPass"; }
 879 };
 880
 881 /// \brief A utility pass that does nothing but preserves no analyses.
 882 ///
 883 /// As a consequence fo not preserving any analyses, this pass will force all
 884 /// analysis passes to be re-run to produce fresh results if any are needed.
 885 struct InvalidateAllAnalysesPass {
 886   /// \brief Run this pass over some unit of IR.
 887   template <typename IRUnitT> PreservedAnalyses run(IRUnitT &Arg) {
 888     return PreservedAnalyses::none();
 889   }
 890
 891   static StringRef name() { return "InvalidateAllAnalysesPass"; }
 892 };
 893
 894 }
 895
 896 #endif