LCOV - code coverage report
Current view: top level - include/llvm/IR - PassManager.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1867 3291 56.7 %
Date: 2018-09-23 13:06:45 Functions: 442 1092 40.5 %
Legend: Lines: hit not hit

          Line data    Source code
       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/SmallPtrSet.h"
      43             : #include "llvm/ADT/StringRef.h"
      44             : #include "llvm/ADT/TinyPtrVector.h"
      45             : #include "llvm/IR/Function.h"
      46             : #include "llvm/IR/Module.h"
      47             : #include "llvm/IR/PassInstrumentation.h"
      48             : #include "llvm/IR/PassManagerInternal.h"
      49             : #include "llvm/Support/Debug.h"
      50             : #include "llvm/Support/TypeName.h"
      51             : #include "llvm/Support/raw_ostream.h"
      52             : #include <algorithm>
      53             : #include <cassert>
      54             : #include <cstring>
      55             : #include <iterator>
      56             : #include <list>
      57             : #include <memory>
      58             : #include <tuple>
      59             : #include <type_traits>
      60             : #include <utility>
      61             : #include <vector>
      62             : 
      63             : namespace llvm {
      64             : 
      65             : /// A special type used by analysis passes to provide an address that
      66             : /// identifies that particular analysis pass type.
      67             : ///
      68             : /// Analysis passes should have a static data member of this type and derive
      69             : /// from the \c AnalysisInfoMixin to get a static ID method used to identify
      70             : /// the analysis in the pass management infrastructure.
      71             : struct alignas(8) AnalysisKey {};
      72             : 
      73             : /// A special type used to provide an address that identifies a set of related
      74             : /// analyses.  These sets are primarily used below to mark sets of analyses as
      75             : /// preserved.
      76             : ///
      77             : /// For example, a transformation can indicate that it preserves the CFG of a
      78             : /// function by preserving the appropriate AnalysisSetKey.  An analysis that
      79             : /// depends only on the CFG can then check if that AnalysisSetKey is preserved;
      80             : /// if it is, the analysis knows that it itself is preserved.
      81             : struct alignas(8) AnalysisSetKey {};
      82             : 
      83             : /// This templated class represents "all analyses that operate over \<a
      84             : /// particular IR unit\>" (e.g. a Function or a Module) in instances of
      85             : /// PreservedAnalysis.
      86             : ///
      87             : /// This lets a transformation say e.g. "I preserved all function analyses".
      88             : ///
      89             : /// Note that you must provide an explicit instantiation declaration and
      90             : /// definition for this template in order to get the correct behavior on
      91             : /// Windows. Otherwise, the address of SetKey will not be stable.
      92             : template <typename IRUnitT> class AllAnalysesOn {
      93             : public:
      94           0 :   static AnalysisSetKey *ID() { return &SetKey; }
      95             : 
      96             : private:
      97             :   static AnalysisSetKey SetKey;
      98             : };
      99             : 
     100             : template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
     101             : 
     102             : extern template class AllAnalysesOn<Module>;
     103             : extern template class AllAnalysesOn<Function>;
     104             : 
     105             : /// Represents analyses that only rely on functions' control flow.
     106             : ///
     107             : /// This can be used with \c PreservedAnalyses to mark the CFG as preserved and
     108             : /// to query whether it has been preserved.
     109             : ///
     110             : /// The CFG of a function is defined as the set of basic blocks and the edges
     111             : /// between them. Changing the set of basic blocks in a function is enough to
     112             : /// mutate the CFG. Mutating the condition of a branch or argument of an
     113             : /// invoked function does not mutate the CFG, but changing the successor labels
     114             : /// of those instructions does.
     115             : class CFGAnalyses {
     116             : public:
     117             :   static AnalysisSetKey *ID() { return &SetKey; }
     118             : 
     119             : private:
     120             :   static AnalysisSetKey SetKey;
     121             : };
     122             : 
     123             : /// A set of analyses that are preserved following a run of a transformation
     124             : /// pass.
     125             : ///
     126             : /// Transformation passes build and return these objects to communicate which
     127             : /// analyses are still valid after the transformation. For most passes this is
     128             : /// fairly simple: if they don't change anything all analyses are preserved,
     129             : /// otherwise only a short list of analyses that have been explicitly updated
     130             : /// are preserved.
     131             : ///
     132             : /// This class also lets transformation passes mark abstract *sets* of analyses
     133             : /// as preserved. A transformation that (say) does not alter the CFG can
     134             : /// indicate such by marking a particular AnalysisSetKey as preserved, and
     135             : /// then analyses can query whether that AnalysisSetKey is preserved.
     136             : ///
     137             : /// Finally, this class can represent an "abandoned" analysis, which is
     138             : /// not preserved even if it would be covered by some abstract set of analyses.
     139             : ///
     140             : /// Given a `PreservedAnalyses` object, an analysis will typically want to
     141             : /// figure out whether it is preserved. In the example below, MyAnalysisType is
     142             : /// preserved if it's not abandoned, and (a) it's explicitly marked as
     143             : /// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both
     144             : /// AnalysisSetA and AnalysisSetB are preserved.
     145             : ///
     146             : /// ```
     147             : ///   auto PAC = PA.getChecker<MyAnalysisType>();
     148             : ///   if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() ||
     149             : ///       (PAC.preservedSet<AnalysisSetA>() &&
     150             : ///        PAC.preservedSet<AnalysisSetB>())) {
     151             : ///     // The analysis has been successfully preserved ...
     152             : ///   }
     153             : /// ```
     154             : class PreservedAnalyses {
     155             : public:
     156             :   /// Convenience factory function for the empty preserved set.
     157         845 :   static PreservedAnalyses none() { return PreservedAnalyses(); }
     158             : 
     159             :   /// Construct a special preserved set that preserves all passes.
     160             :   static PreservedAnalyses all() {
     161             :     PreservedAnalyses PA;
     162      147805 :     PA.PreservedIDs.insert(&AllAnalysesKey);
     163             :     return PA;
     164             :   }
     165             : 
     166             :   /// Construct a preserved analyses object with a single preserved set.
     167             :   template <typename AnalysisSetT>
     168             :   static PreservedAnalyses allInSet() {
     169             :     PreservedAnalyses PA;
     170             :     PA.preserveSet<AnalysisSetT>();
     171             :     return PA;
     172             :   }
     173             : 
     174             :   /// Mark an analysis as preserved.
     175       52606 :   template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); }
     176             : 
     177             :   /// Given an analysis's ID, mark the analysis as preserved, adding it
     178             :   /// to the set.
     179       63383 :   void preserve(AnalysisKey *ID) {
     180             :     // Clear this ID from the explicit not-preserved set if present.
     181             :     NotPreservedAnalysisIDs.erase(ID);
     182             : 
     183             :     // If we're not already preserving all analyses (other than those in
     184             :     // NotPreservedAnalysisIDs).
     185             :     if (!areAllPreserved())
     186       59101 :       PreservedIDs.insert(ID);
     187       63383 :   }
     188             : 
     189             :   /// Mark an analysis set as preserved.
     190             :   template <typename AnalysisSetT> void preserveSet() {
     191       56456 :     preserveSet(AnalysisSetT::ID());
     192             :   }
     193             : 
     194             :   /// Mark an analysis set as preserved using its ID.
     195       57412 :   void preserveSet(AnalysisSetKey *ID) {
     196             :     // If we're not already in the saturated 'all' state, add this set.
     197             :     if (!areAllPreserved())
     198       52335 :       PreservedIDs.insert(ID);
     199       57412 :   }
     200             : 
     201             :   /// Mark an analysis as abandoned.
     202             :   ///
     203             :   /// An abandoned analysis is not preserved, even if it is nominally covered
     204             :   /// by some other set or was previously explicitly marked as preserved.
     205             :   ///
     206             :   /// Note that you can only abandon a specific analysis, not a *set* of
     207             :   /// analyses.
     208           3 :   template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); }
     209             : 
     210             :   /// Mark an analysis as abandoned using its ID.
     211             :   ///
     212             :   /// An abandoned analysis is not preserved, even if it is nominally covered
     213             :   /// by some other set or was previously explicitly marked as preserved.
     214             :   ///
     215             :   /// Note that you can only abandon a specific analysis, not a *set* of
     216             :   /// analyses.
     217         148 :   void abandon(AnalysisKey *ID) {
     218             :     PreservedIDs.erase(ID);
     219         148 :     NotPreservedAnalysisIDs.insert(ID);
     220         148 :   }
     221             : 
     222             :   /// Intersect this set with another in place.
     223             :   ///
     224             :   /// This is a mutating operation on this preserved set, removing all
     225             :   /// preserved passes which are not also preserved in the argument.
     226           4 :   void intersect(const PreservedAnalyses &Arg) {
     227             :     if (Arg.areAllPreserved())
     228             :       return;
     229             :     if (areAllPreserved()) {
     230           0 :       *this = Arg;
     231           0 :       return;
     232             :     }
     233             :     // The intersection requires the *union* of the explicitly not-preserved
     234             :     // IDs and the *intersection* of the preserved IDs.
     235           4 :     for (auto ID : Arg.NotPreservedAnalysisIDs) {
     236             :       PreservedIDs.erase(ID);
     237           0 :       NotPreservedAnalysisIDs.insert(ID);
     238             :     }
     239          14 :     for (auto ID : PreservedIDs)
     240          10 :       if (!Arg.PreservedIDs.count(ID))
     241             :         PreservedIDs.erase(ID);
     242             :   }
     243             : 
     244             :   /// Intersect this set with a temporary other set in place.
     245             :   ///
     246             :   /// This is a mutating operation on this preserved set, removing all
     247             :   /// preserved passes which are not also preserved in the argument.
     248       26427 :   void intersect(PreservedAnalyses &&Arg) {
     249             :     if (Arg.areAllPreserved())
     250             :       return;
     251             :     if (areAllPreserved()) {
     252        4326 :       *this = std::move(Arg);
     253        4326 :       return;
     254             :     }
     255             :     // The intersection requires the *union* of the explicitly not-preserved
     256             :     // IDs and the *intersection* of the preserved IDs.
     257        1964 :     for (auto ID : Arg.NotPreservedAnalysisIDs) {
     258             :       PreservedIDs.erase(ID);
     259          12 :       NotPreservedAnalysisIDs.insert(ID);
     260             :     }
     261        9717 :     for (auto ID : PreservedIDs)
     262        7765 :       if (!Arg.PreservedIDs.count(ID))
     263             :         PreservedIDs.erase(ID);
     264             :   }
     265             : 
     266             :   /// A checker object that makes it easy to query for whether an analysis or
     267             :   /// some set covering it is preserved.
     268             :   class PreservedAnalysisChecker {
     269             :     friend class PreservedAnalyses;
     270             : 
     271             :     const PreservedAnalyses &PA;
     272             :     AnalysisKey *const ID;
     273             :     const bool IsAbandoned;
     274             : 
     275             :     /// A PreservedAnalysisChecker is tied to a particular Analysis because
     276             :     /// `preserved()` and `preservedSet()` both return false if the Analysis
     277             :     /// was abandoned.
     278             :     PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID)
     279       11718 :         : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(ID)) {}
     280             : 
     281             :   public:
     282             :     /// Returns true if the checker's analysis was not abandoned and either
     283             :     ///  - the analysis is explicitly preserved or
     284             :     ///  - all analyses are preserved.
     285       11832 :     bool preserved() {
     286       22974 :       return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||
     287       11142 :                               PA.PreservedIDs.count(ID));
     288             :     }
     289             : 
     290             :     /// Returns true if the checker's analysis was not abandoned and either
     291             :     ///  - \p AnalysisSetT is explicitly preserved or
     292             :     ///  - all analyses are preserved.
     293           0 :     template <typename AnalysisSetT> bool preservedSet() {
     294             :       AnalysisSetKey *SetID = AnalysisSetT::ID();
     295           0 :       return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||
     296           0 :                               PA.PreservedIDs.count(SetID));
     297             :     }
     298           0 :   };
     299             : 
     300           0 :   /// Build a checker for this `PreservedAnalyses` and the specified analysis
     301           0 :   /// type.
     302             :   ///
     303           0 :   /// You can use the returned object to query whether an analysis was
     304             :   /// preserved. See the example in the comment on `PreservedAnalysis`.
     305           0 :   template <typename AnalysisT> PreservedAnalysisChecker getChecker() const {
     306           0 :     return PreservedAnalysisChecker(*this, AnalysisT::ID());
     307             :   }
     308           0 : 
     309             :   /// Build a checker for this `PreservedAnalyses` and the specified analysis
     310           0 :   /// ID.
     311           0 :   ///
     312             :   /// You can use the returned object to query whether an analysis was
     313           0 :   /// preserved. See the example in the comment on `PreservedAnalysis`.
     314             :   PreservedAnalysisChecker getChecker(AnalysisKey *ID) const {
     315           0 :     return PreservedAnalysisChecker(*this, ID);
     316           0 :   }
     317             : 
     318             :   /// Test whether all analyses are preserved (and none are abandoned).
     319             :   ///
     320             :   /// This is used primarily to optimize for the common case of a transformation
     321             :   /// which makes no changes to the IR.
     322             :   bool areAllPreserved() const {
     323     1394465 :     return NotPreservedAnalysisIDs.empty() &&
     324      700242 :            PreservedIDs.count(&AllAnalysesKey);
     325             :   }
     326             : 
     327             :   /// Directly test whether a set of analyses is preserved.
     328             :   ///
     329             :   /// This is only true when no analyses have been explicitly abandoned.
     330             :   template <typename AnalysisSetT> bool allAnalysesInSetPreserved() const {
     331         900 :     return allAnalysesInSetPreserved(AnalysisSetT::ID());
     332             :   }
     333        6228 : 
     334        3099 :   /// Directly test whether a set of analyses is preserved.
     335             :   ///
     336             :   /// This is only true when no analyses have been explicitly abandoned.
     337       25394 :   bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const {
     338       51883 :     return NotPreservedAnalysisIDs.empty() &&
     339       32417 :            (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(SetID));
     340             :   }
     341         719 : 
     342             : private:
     343           0 :   /// A special key used to indicate all analyses.
     344           0 :   static AnalysisSetKey AllAnalysesKey;
     345             : 
     346             :   /// The IDs of analyses and analysis sets that are preserved.
     347        4029 :   SmallPtrSet<void *, 2> PreservedIDs;
     348        8013 : 
     349        6415 :   /// The IDs of explicitly not-preserved analyses.
     350             :   ///
     351             :   /// If an analysis in this set is covered by a set in `PreservedIDs`, we
     352           0 :   /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always
     353           0 :   /// "wins" over analysis sets in `PreservedIDs`.
     354           0 :   ///
     355             :   /// Also, a given ID should never occur both here and in `PreservedIDs`.
     356             :   SmallPtrSet<AnalysisKey *, 2> NotPreservedAnalysisIDs;
     357           0 : };
     358           0 : 
     359           0 : // Forward declare the analysis manager template.
     360             : template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
     361             : 
     362             : /// A CRTP mix-in to automatically provide informational APIs needed for
     363             : /// passes.
     364             : ///
     365             : /// This provides some boilerplate for types that are passes.
     366             : template <typename DerivedT> struct PassInfoMixin {
     367             :   /// Gets the name of the pass we are mixed into.
     368         963 :   static StringRef name() {
     369             :     static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value,
     370             :                   "Must pass the derived type as the template argument!");
     371         963 :     StringRef Name = getTypeName<DerivedT>();
     372             :     if (Name.startswith("llvm::"))
     373         963 :       Name = Name.drop_front(strlen("llvm::"));
     374         963 :     return Name;
     375             :   }
     376          77 : };
     377             : 
     378         982 : /// A CRTP mix-in that provides informational APIs needed for analysis passes.
     379          77 : ///
     380             : /// This provides some boilerplate for types that are analysis passes. It
     381        1059 : /// automatically mixes in \c PassInfoMixin.
     382          77 : template <typename DerivedT>
     383        1622 : struct AnalysisInfoMixin : PassInfoMixin<DerivedT> {
     384        1203 :   /// Returns an opaque, unique ID for this analysis type.
     385             :   ///
     386         964 :   /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus
     387         221 :   /// suitable for use in sets, maps, and other data structures that use the low
     388        8589 :   /// bits of pointers.
     389        1185 :   ///
     390         221 :   /// Note that this requires the derived type provide a static \c AnalysisKey
     391        8099 :   /// member called \c Key.
     392         335 :   ///
     393        8032 :   /// FIXME: The only reason the mixin type itself can't declare the Key value
     394        8100 :   /// is that some compilers cannot correctly unique a templated static variable
     395         323 :   /// so it has the same addresses in each instantiation. The only currently
     396           7 :   /// known platform with this limitation is Windows DLL builds, specifically
     397         349 :   /// building each part of LLVM as a DLL. If we ever remove that build
     398         323 :   /// configuration, this mixin can provide the static key as well.
     399          37 :   static AnalysisKey *ID() {
     400         114 :     static_assert(std::is_base_of<AnalysisInfoMixin, DerivedT>::value,
     401           0 :                   "Must pass the derived type as the template argument!");
     402          52 :     return &DerivedT::Key;
     403         102 :   }
     404          38 : };
     405         147 : 
     406         102 : namespace detail {
     407          50 : 
     408          22 : /// Actual unpacker of extra arguments in getAnalysisResult,
     409           0 : /// passes only those tuple arguments that are mentioned in index_sequence.
     410          70 : template <typename PassT, typename IRUnitT, typename AnalysisManagerT,
     411           7 :           typename... ArgTs, size_t... Ns>
     412          49 : typename PassT::Result
     413          69 : getAnalysisResultUnpackTuple(AnalysisManagerT &AM, IRUnitT &IR,
     414           7 :                              std::tuple<ArgTs...> Args,
     415          82 :                              llvm::index_sequence<Ns...>) {
     416          34 :   (void)Args;
     417        4034 :   return AM.template getResult<PassT>(IR, std::get<Ns>(Args)...);
     418          82 : }
     419          14 : 
     420          14 : /// Helper for *partial* unpacking of extra arguments in getAnalysisResult.
     421          89 : ///
     422          14 : /// Arguments passed in tuple come from PassManager, so they might have extra
     423          71 : /// arguments after those AnalysisManager's ExtraArgTs ones that we need to
     424           5 : /// pass to getResult.
     425          11 : template <typename PassT, typename IRUnitT, typename... AnalysisArgTs,
     426         104 :           typename... MainArgTs>
     427           0 : typename PassT::Result
     428           6 : getAnalysisResult(AnalysisManager<IRUnitT, AnalysisArgTs...> &AM, IRUnitT &IR,
     429          90 :                   std::tuple<MainArgTs...> Args) {
     430           0 :   return (getAnalysisResultUnpackTuple<
     431          94 :           PassT, IRUnitT>)(AM, IR, Args,
     432          44 :                            llvm::index_sequence_for<AnalysisArgTs...>{});
     433           0 : }
     434          60 : 
     435           6 : } // namespace detail
     436           3 : 
     437          60 : // Forward declare the pass instrumentation analysis explicitly queried in
     438           6 : // generic PassManager code.
     439          45 : // FIXME: figure out a way to move PassInstrumentationAnalysis into its own
     440          10 : // header.
     441           0 : class PassInstrumentationAnalysis;
     442          52 : 
     443           8 : /// Manages a sequence of passes over a particular unit of IR.
     444          47 : ///
     445          57 : /// A pass manager contains a sequence of passes to run over a particular unit
     446           8 : /// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of
     447          16 : /// IR, and when run over some given IR will run each of its contained passes in
     448           9 : /// sequence. Pass managers are the primary and most basic building block of a
     449           1 : /// pass pipeline.
     450          25 : ///
     451             : /// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT>
     452           4 : /// argument. The pass manager will propagate that analysis manager to each
     453          18 : /// pass it runs, and will call the analysis manager's invalidation routine with
     454             : /// the PreservedAnalyses of each pass it runs.
     455          28 : template <typename IRUnitT,
     456          12 :           typename AnalysisManagerT = AnalysisManager<IRUnitT>,
     457           1 :           typename... ExtraArgTs>
     458          45 : class PassManager : public PassInfoMixin<
     459             :                         PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
     460          26 : public:
     461          35 :   /// Construct a pass manager.
     462             :   ///
     463          11 :   /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs().
     464          25 :   explicit PassManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
     465           2 : 
     466          12 :   // FIXME: These are equivalent to the default move constructor/move
     467             :   // assignment. However, using = default triggers linker errors due to the
     468           4 :   // explicit instantiations below. Find away to use the default and remove the
     469          10 :   // duplicated code here.
     470           0 :   PassManager(PassManager &&Arg)
     471          38 :       : Passes(std::move(Arg.Passes)),
     472           9 :         DebugLogging(std::move(Arg.DebugLogging)) {}
     473           3 : 
     474         105 :   PassManager &operator=(PassManager &&RHS) {
     475           0 :     Passes = std::move(RHS.Passes);
     476          27 :     DebugLogging = std::move(RHS.DebugLogging);
     477          72 :     return *this;
     478             :   }
     479          72 : 
     480         109 :   /// Run all of the passes in this manager over the given unit of IR.
     481           0 :   /// ExtraArgs are passed to each pass.
     482         283 :   PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
     483             :                         ExtraArgTs... ExtraArgs) {
     484           5 :     PreservedAnalyses PA = PreservedAnalyses::all();
     485         282 : 
     486           0 :     // Request PassInstrumentation from analysis manager, will use it to run
     487         276 :     // instrumenting callbacks for the passes later.
     488         237 :     // Here we use std::tuple wrapper over getResult which helps to extract
     489           5 :     // AnalysisManager's arguments out of the whole ExtraArgs set.
     490          71 :     PassInstrumentation PI =
     491             :         detail::getAnalysisResult<PassInstrumentationAnalysis>(
     492          69 :             AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));
     493          66 : 
     494           0 :     if (DebugLogging)
     495          54 :       dbgs() << "Starting " << getTypeName<IRUnitT>() << " pass manager run.\n";
     496          18 : 
     497           0 :     for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
     498          75 :       auto *P = Passes[Idx].get();
     499           0 :       if (DebugLogging)
     500           0 :         dbgs() << "Running pass: " << P->name() << " on " << IR.getName()
     501          75 :                << "\n";
     502           0 : 
     503          48 :       // Check the PassInstrumentation's BeforePass callbacks before running the
     504          39 :       // pass, skip its execution completely if asked to (callback returns
     505           0 :       // false).
     506        1022 :       if (!PI.runBeforePass<IRUnitT>(*P, IR))
     507           0 :         continue;
     508          10 : 
     509         117 :       PreservedAnalyses PassPA = P->run(IR, AM, ExtraArgs...);
     510           0 : 
     511           1 :       // Call onto PassInstrumentation's AfterPass callbacks immediately after
     512        1936 :       // running the pass.
     513           1 :       PI.runAfterPass<IRUnitT>(*P, IR);
     514          23 : 
     515           0 :       // Update the analysis manager as each pass runs and potentially
     516           4 :       // invalidates analyses.
     517          16 :       AM.invalidate(IR, PassPA);
     518             : 
     519          58 :       // Finally, intersect the preserved analyses to compute the aggregate
     520          28 :       // preserved set for this pass manager.
     521           4 :       PA.intersect(std::move(PassPA));
     522        4091 : 
     523             :       // FIXME: Historically, the pass managers all called the LLVM context's
     524           6 :       // yield function here. We don't have a generic way to acquire the
     525          54 :       // context and it isn't yet clear what the right pattern is for yielding
     526           6 :       // in the new pass manager so it is currently omitted.
     527          12 :       //IR.getContext().yield();
     528           6 :     }
     529           6 : 
     530          79 :     // Invalidation was handled after each pass in the above loop for the
     531        4033 :     // current unit of IR. Therefore, the remaining analysis results in the
     532           1 :     // AnalysisManager are preserved. We mark this with a set so that we don't
     533          39 :     // need to inspect each one individually.
     534        4033 :     PA.preserveSet<AllAnalysesOn<IRUnitT>>();
     535        1003 : 
     536         101 :     if (DebugLogging)
     537       22760 :       dbgs() << "Finished " << getTypeName<IRUnitT>() << " pass manager run.\n";
     538       14798 : 
     539       14693 :     return PA;
     540        5021 :   }
     541        5125 : 
     542           0 :   template <typename PassT> void addPass(PassT Pass) {
     543          22 :     using PassModelT =
     544           4 :         detail::PassModel<IRUnitT, PassT, PreservedAnalyses, AnalysisManagerT,
     545           0 :                           ExtraArgTs...>;
     546       14806 : 
     547           2 :     Passes.emplace_back(new PassModelT(std::move(Pass)));
     548          39 :   }
     549       29495 : 
     550             : private:
     551         107 :   using PassConceptT =
     552          95 :       detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
     553       14691 : 
     554          29 :   std::vector<std::unique_ptr<PassConceptT>> Passes;
     555             : 
     556          12 :   /// Flag indicating whether we should do debug logging.
     557       14720 :   bool DebugLogging;
     558          16 : };
     559          57 : 
     560          17 : extern template class PassManager<Module>;
     561       14691 : 
     562          57 : /// Convenience typedef for a pass manager over modules.
     563          19 : using ModulePassManager = PassManager<Module>;
     564          56 : 
     565          57 : extern template class PassManager<Function>;
     566           0 : 
     567          55 : /// Convenience typedef for a pass manager over functions.
     568          17 : using FunctionPassManager = PassManager<Function>;
     569           0 : 
     570          67 : /// Pseudo-analysis pass that exposes the \c PassInstrumentation to pass
     571           0 : /// managers. Goes before AnalysisManager definition to provide its
     572          38 : /// internals (e.g PassInstrumentationAnalysis::ID) for use there if needed.
     573          67 : /// FIXME: figure out a way to move PassInstrumentationAnalysis into its own
     574             : /// header.
     575          47 : class PassInstrumentationAnalysis
     576        4062 :     : public AnalysisInfoMixin<PassInstrumentationAnalysis> {
     577         869 :   friend AnalysisInfoMixin<PassInstrumentationAnalysis>;
     578          35 :   static AnalysisKey Key;
     579        4033 : 
     580          18 :   PassInstrumentationCallbacks *Callbacks;
     581        3790 : 
     582             : public:
     583         137 :   /// PassInstrumentationCallbacks object is shared, owned by something else,
     584          17 :   /// not this analysis.
     585           0 :   PassInstrumentationAnalysis(PassInstrumentationCallbacks *Callbacks = nullptr)
     586         145 :       : Callbacks(Callbacks) {}
     587             : 
     588         120 :   using Result = PassInstrumentation;
     589         145 : 
     590        6042 :   template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
     591          42 :   Result run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {
     592          25 :     return PassInstrumentation(Callbacks);
     593        3755 :   }
     594         712 : };
     595        3541 : 
     596       22357 : /// A container for analyses that lazily runs them and caches their
     597       12587 : /// results.
     598       12549 : ///
     599        3537 : /// This class can manage analyses for any IR unit where the address of the IR
     600        3519 : /// unit sufficies as its identity.
     601           0 : template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager {
     602          45 : public:
     603          10 :   class Invalidator;
     604          25 : 
     605       12588 : private:
     606           1 :   // Now that we've defined our invalidator, we can define the concept types.
     607          39 :   using ResultConceptT =
     608       25109 :       detail::AnalysisResultConcept<IRUnitT, PreservedAnalyses, Invalidator>;
     609           1 :   using PassConceptT =
     610         107 :       detail::AnalysisPassConcept<IRUnitT, PreservedAnalyses, Invalidator,
     611         629 :                                   ExtraArgTs...>;
     612       12591 : 
     613         102 :   /// List of analysis pass IDs and associated concept pointers.
     614          29 :   ///
     615           0 :   /// Requires iterators to be valid across appending new entries and arbitrary
     616       14512 :   /// erases. Provides the analysis ID to enable finding iterators to a given
     617         629 :   /// entry in maps below, and provides the storage for the actual result
     618        1660 :   /// concept.
     619          55 :   using AnalysisResultListT =
     620       12571 :       std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>;
     621          12 : 
     622             :   /// Map type from IRUnitT pointer to our custom list type.
     623        1658 :   using AnalysisResultListMapT = DenseMap<IRUnitT *, AnalysisResultListT>;
     624        1660 : 
     625           2 :   /// Map type from a pair of analysis ID and IRUnitT pointer to an
     626          36 :   /// iterator into a particular result list (which is where the actual analysis
     627          12 :   /// result is stored).
     628           0 :   using AnalysisResultMapT =
     629           0 :       DenseMap<std::pair<AnalysisKey *, IRUnitT *>,
     630           0 :                typename AnalysisResultListT::iterator>;
     631           0 : 
     632           0 : public:
     633           0 :   /// API to communicate dependencies between analyses during invalidation.
     634          11 :   ///
     635        3763 :   /// When an analysis result embeds handles to other analysis results, it
     636         670 :   /// needs to be invalidated both when its own information isn't preserved and
     637           0 :   /// when any of its embedded analysis results end up invalidated. We pass an
     638        3755 :   /// \c Invalidator object as an argument to \c invalidate() in order to let
     639           0 :   /// the analysis results themselves define the dependency graph on the fly.
     640         307 :   /// This lets us avoid building building an explicit representation of the
     641           8 :   /// dependencies between analysis results.
     642           0 :   class Invalidator {
     643             :   public:
     644           2 :     /// Trigger the invalidation of some other analysis pass if not already
     645             :     /// handled and return whether it was in fact invalidated.
     646           7 :     ///
     647           2 :     /// This is expected to be called from within a given analysis result's \c
     648          38 :     /// invalidate method to trigger a depth-first walk of all inter-analysis
     649         280 :     /// dependencies. The same \p IR unit and \p PA passed to that result's \c
     650           2 :     /// invalidate method should in turn be provided to this routine.
     651           0 :     ///
     652         280 :     /// The first time this is called for a given analysis pass, it will call
     653         199 :     /// the corresponding result's \c invalidate method.  Subsequent calls will
     654           0 :     /// use a cache of the results of that initial call.  It is an error to form
     655        2706 :     /// cyclic dependencies between analysis results.
     656        2150 :     ///
     657        2150 :     /// This returns true if the given analysis's result is invalid. Any
     658        1530 :     /// dependecies on it will become invalid as a result.
     659        1527 :     template <typename PassT>
     660           0 :     bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
     661           0 :       using ResultModelT =
     662           0 :           detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
     663           7 :                                       PreservedAnalyses, Invalidator>;
     664        2150 : 
     665        5002 :       return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);
     666           0 :     }
     667        4301 : 
     668          15 :     /// A type-erased variant of the above invalidate method with the same core
     669           7 :     /// API other than passing an analysis ID rather than an analysis type
     670           5 :     /// parameter.
     671        2157 :     ///
     672           0 :     /// This is sadly less efficient than the above routine, which leverages
     673          17 :     /// the type parameter to avoid the type erasure overhead.
     674          11 :     bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
     675        2905 :       return invalidateImpl<>(ID, IR, PA);
     676           2 :     }
     677           0 : 
     678           0 :   private:
     679        2149 :     friend class AnalysisManager;
     680           0 : 
     681           0 :     template <typename ResultT = ResultConceptT>
     682        5010 :     bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,
     683           0 :                         const PreservedAnalyses &PA) {
     684           0 :       // If we've already visited this pass, return true if it was invalidated
     685          52 :       // and false otherwise.
     686        5007 :       auto IMapI = IsResultInvalidated.find(ID);
     687       10014 :       if (IMapI != IsResultInvalidated.end())
     688        4982 :         return IMapI->second;
     689           3 : 
     690          25 :       // Otherwise look up the result object.
     691          50 :       auto RI = Results.find({ID, &IR});
     692         438 :       assert(RI != Results.end() &&
     693           3 :              "Trying to invalidate a dependent result that isn't in the "
     694         278 :              "manager's cache is always an error, likely due to a stale result "
     695         224 :              "handle!");
     696         461 : 
     697        1178 :       auto &Result = static_cast<ResultT &>(*RI->second->second);
     698         415 : 
     699           0 :       // Insert into the map whether the result should be invalidated and return
     700           0 :       // that. Note that we cannot reuse IMapI and must do a fresh insert here,
     701          50 :       // as calling invalidate could (recursively) insert things into the map,
     702           0 :       // making any iterator or reference invalid.
     703           0 :       bool Inserted;
     704          56 :       std::tie(IMapI, Inserted) =
     705          25 :           IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});
     706           6 :       (void)Inserted;
     707          25 :       assert(Inserted && "Should not have already inserted this ID, likely "
     708           1 :                          "indicates a dependency cycle!");
     709          25 :       return IMapI->second;
     710           0 :     }
     711         554 : 
     712           3 :     Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated,
     713           1 :                 const AnalysisResultMapT &Results)
     714          51 :         : IsResultInvalidated(IsResultInvalidated), Results(Results) {}
     715         581 : 
     716        1115 :     SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;
     717         553 :     const AnalysisResultMapT &Results;
     718          15 :   };
     719          34 : 
     720           0 :   /// Construct an empty analysis manager.
     721           9 :   ///
     722           9 :   /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs().
     723          20 :   AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
     724          15 :   AnalysisManager(AnalysisManager &&) = default;
     725           4 :   AnalysisManager &operator=(AnalysisManager &&) = default;
     726           0 : 
     727           0 :   /// Returns true if the analysis manager has an empty results cache.
     728             :   bool empty() const {
     729           0 :     assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&
     730           8 :            "The storage and index of analysis results disagree on how many "
     731           4 :            "there are!");
     732           2 :     return AnalysisResults.empty();
     733           0 :   }
     734           0 : 
     735           1 :   /// Clear any cached analysis results for a single unit of IR.
     736           0 :   ///
     737          59 :   /// This doesn't invalidate, but instead simply deletes, the relevant results.
     738           2 :   /// It is useful when the IR is being removed and we want to clear out all the
     739           0 :   /// memory pinned for it.
     740        1004 :   void clear(IRUnitT &IR, llvm::StringRef Name) {
     741           0 :     if (DebugLogging)
     742           0 :       dbgs() << "Clearing all analysis results for: " << Name << "\n";
     743          82 : 
     744        1000 :     auto ResultsListI = AnalysisResultLists.find(&IR);
     745        2004 :     if (ResultsListI == AnalysisResultLists.end())
     746        1003 :       return;
     747             :     // Delete the map entries that point into the results list.
     748          66 :     for (auto &IDAndResult : ResultsListI->second)
     749         133 :       AnalysisResults.erase({IDAndResult.first, &IR});
     750          14 : 
     751         136 :     // And actually destroy and erase the results associated with this IR.
     752           2 :     AnalysisResultLists.erase(ResultsListI);
     753          10 :   }
     754          90 : 
     755          31 :   /// Clear all analysis results cached by this AnalysisManager.
     756          14 :   ///
     757             :   /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply
     758           6 :   /// deletes them.  This lets you clean up the AnalysisManager when the set of
     759           6 :   /// IR units itself has potentially changed, and thus we can't even look up a
     760          76 :   /// a result and invalidate/clear it directly.
     761           0 :   void clear() {
     762          78 :     AnalysisResults.clear();
     763           3 :     AnalysisResultLists.clear();
     764           0 :   }
     765           7 : 
     766           7 :   /// Get the result of an analysis pass for a given IR unit.
     767          16 :   ///
     768           0 :   /// Runs the analysis if a cached result is not available.
     769        1553 :   template <typename PassT>
     770        2211 :   typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) {
     771             :     assert(AnalysisPasses.count(PassT::ID()) &&
     772          13 :            "This analysis pass was not registered prior to being queried");
     773       28437 :     ResultConceptT &ResultConcept =
     774        3113 :         getResultImpl(PassT::ID(), IR, ExtraArgs...);
     775        1534 : 
     776           4 :     using ResultModelT =
     777           0 :         detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
     778          38 :                                     PreservedAnalyses, Invalidator>;
     779         202 : 
     780       17337 :     return static_cast<ResultModelT &>(ResultConcept).Result;
     781           6 :   }
     782           4 : 
     783        3162 :   /// Get the cached result of an analysis pass for a given IR unit.
     784         409 :   ///
     785         195 :   /// This method never runs the analysis.
     786           0 :   ///
     787             :   /// \returns null if there is no cached result.
     788           0 :   template <typename PassT>
     789          24 :   typename PassT::Result *getCachedResult(IRUnitT &IR) const {
     790         964 :     assert(AnalysisPasses.count(PassT::ID()) &&
     791          38 :            "This analysis pass was not registered prior to being queried");
     792          19 : 
     793        6169 :     ResultConceptT *ResultConcept = getCachedResultImpl(PassT::ID(), IR);
     794        6169 :     if (!ResultConcept)
     795           0 :       return nullptr;
     796          39 : 
     797           0 :     using ResultModelT =
     798        1043 :         detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
     799           0 :                                     PreservedAnalyses, Invalidator>;
     800           6 : 
     801        3829 :     return &static_cast<ResultModelT *>(ResultConcept)->Result;
     802        1043 :   }
     803        2086 : 
     804        1043 :   /// Register an analysis pass with the manager.
     805             :   ///
     806           0 :   /// The parameter is a callable whose result is an analysis pass. This allows
     807           0 :   /// passing in a lambda to construct the analysis.
     808         195 :   ///
     809           0 :   /// The analysis type to register is the type returned by calling the \c
     810           0 :   /// PassBuilder argument. If that type has already been registered, then the
     811           2 :   /// argument will not be called and this function will return false.
     812         195 :   /// Otherwise, we register the analysis returned by calling \c PassBuilder(),
     813         390 :   /// and this function returns true.
     814         195 :   ///
     815           0 :   /// (Note: Although the return value of this function indicates whether or not
     816           4 :   /// an analysis was previously registered, there intentionally isn't a way to
     817        1072 :   /// query this directly.  Instead, you should just register all the analyses
     818        1070 :   /// you might want and let this class run them lazily.  This idiom lets us
     819             :   /// minimize the number of times we have to look up analyses in our
     820           0 :   /// hashtable.)
     821          67 :   template <typename PassBuilderT>
     822        3707 :   bool registerPass(PassBuilderT &&PassBuilder) {
     823           0 :     using PassT = decltype(PassBuilder());
     824           0 :     using PassModelT =
     825         449 :         detail::AnalysisPassModel<IRUnitT, PassT, PreservedAnalyses,
     826         133 :                                   Invalidator, ExtraArgTs...>;
     827         468 : 
     828        3707 :     auto &PassPtr = AnalysisPasses[PassT::ID()];
     829        3707 :     if (PassPtr)
     830           0 :       // Already registered this pass type!
     831         401 :       return false;
     832         875 : 
     833         673 :     // Construct a new model around the instance returned by the builder.
     834        3707 :     PassPtr.reset(new PassModelT(PassBuilder()));
     835           0 :     return true;
     836           0 :   }
     837         136 : 
     838          73 :   /// Invalidate a specific analysis pass for an IR module.
     839           0 :   ///
     840           0 :   /// Note that the analysis result can disregard invalidation, if it determines
     841          32 :   /// it is in fact still valid.
     842          64 :   template <typename PassT> void invalidate(IRUnitT &IR) {
     843           7 :     assert(AnalysisPasses.count(PassT::ID()) &&
     844           0 :            "This analysis pass was not registered prior to being invalidated");
     845           0 :     invalidateImpl(PassT::ID(), IR);
     846         679 :   }
     847           0 : 
     848           0 :   /// Invalidate cached analyses for an IR unit.
     849           6 :   ///
     850         627 :   /// Walk through all of the analyses pertaining to this unit of IR and
     851        1254 :   /// invalidate them, unless they are preserved by the PreservedAnalyses set.
     852         428 :   void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
     853           4 :     // We're done if all analyses on this IR unit are preserved.
     854          12 :     if (PA.allAnalysesInSetPreserved<AllAnalysesOn<IRUnitT>>())
     855         458 :       return;
     856         402 : 
     857           0 :     if (DebugLogging)
     858           4 :       dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName()
     859          54 :              << "\n";
     860        1343 : 
     861        1030 :     // Track whether each analysis's result is invalidated in
     862         430 :     // IsResultInvalidated.
     863        1489 :     SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
     864          25 :     Invalidator Inv(IsResultInvalidated, AnalysisResults);
     865           6 :     AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
     866           6 :     for (auto &AnalysisResultPair : ResultsList) {
     867        1706 :       // This is basically the same thing as Invalidator::invalidate, but we
     868         485 :       // can't call it here because we're operating on the type-erased result.
     869        1050 :       // Moreover if we instead called invalidate() directly, it would do an
     870        1509 :       // unnecessary look up in ResultsList.
     871           4 :       AnalysisKey *ID = AnalysisResultPair.first;
     872           2 :       auto &Result = *AnalysisResultPair.second;
     873         231 : 
     874          58 :       auto IMapI = IsResultInvalidated.find(ID);
     875         617 :       if (IMapI != IsResultInvalidated.end())
     876          27 :         // This result was already handled via the Invalidator.
     877          12 :         continue;
     878           0 : 
     879         538 :       // Try to invalidate the result, giving it the Invalidator so it can
     880        1073 :       // recursively query for any dependencies it has and record the result.
     881         344 :       // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as
     882          24 :       // Result.invalidate may insert things into the map, invalidating our
     883          12 :       // iterator.
     884         413 :       bool Inserted =
     885           4 :           IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)})
     886          16 :               .second;
     887           8 :       (void)Inserted;
     888          10 :       assert(Inserted && "Should never have already inserted this ID, likely "
     889        1204 :                          "indicates a cycle!");
     890         222 :     }
     891          10 : 
     892           2 :     // Now erase the results that were marked above as invalidated.
     893          10 :     if (!IsResultInvalidated.empty()) {
     894          10 :       for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) {
     895         103 :         AnalysisKey *ID = I->first;
     896        1269 :         if (!IsResultInvalidated.lookup(ID)) {
     897         410 :           ++I;
     898         201 :           continue;
     899          99 :         }
     900         115 : 
     901         297 :         if (DebugLogging)
     902         208 :           dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name()
     903         348 :                  << " on " << IR.getName() << "\n";
     904         614 : 
     905          12 :         I = ResultsList.erase(I);
     906          12 :         AnalysisResults.erase({ID, &IR});
     907           9 :       }
     908         384 :     }
     909        1770 : 
     910        1643 :     if (ResultsList.empty())
     911          24 :       AnalysisResultLists.erase(&IR);
     912           0 :   }
     913          54 : 
     914          25 : private:
     915           8 :   /// Look up a registered analysis pass.
     916          26 :   PassConceptT &lookUpPass(AnalysisKey *ID) {
     917         170 :     typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(ID);
     918          37 :     assert(PI != AnalysisPasses.end() &&
     919          33 :            "Analysis passes must be registered prior to being queried!");
     920           6 :     return *PI->second;
     921          26 :   }
     922          20 : 
     923          16 :   /// Look up a registered analysis pass.
     924           2 :   const PassConceptT &lookUpPass(AnalysisKey *ID) const {
     925        2153 :     typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(ID);
     926          66 :     assert(PI != AnalysisPasses.end() &&
     927          39 :            "Analysis passes must be registered prior to being queried!");
     928        4740 :     return *PI->second;
     929          15 :   }
     930           2 : 
     931          27 :   /// Get an analysis result, running the pass if necessary.
     932          21 :   ResultConceptT &getResultImpl(AnalysisKey *ID, IRUnitT &IR,
     933             :                                 ExtraArgTs... ExtraArgs) {
     934        4248 :     typename AnalysisResultMapT::iterator RI;
     935        2455 :     bool Inserted;
     936        5163 :     std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair(
     937          12 :         std::make_pair(ID, &IR), typename AnalysisResultListT::iterator()));
     938          15 : 
     939           0 :     // If we don't have a cached result for this function, look up the pass and
     940           1 :     // run it to produce a result, which we then add to the cache.
     941          15 :     if (Inserted) {
     942         903 :       auto &P = this->lookUpPass(ID);
     943         904 :       if (DebugLogging)
     944          23 :         dbgs() << "Running analysis: " << P.name() << " on " << IR.getName()
     945          13 :                << "\n";
     946          30 : 
     947           4 :       PassInstrumentation PI;
     948        1046 :       if (ID != PassInstrumentationAnalysis::ID()) {
     949        3056 :         PI = getResult<PassInstrumentationAnalysis>(IR, ExtraArgs...);
     950           6 :         PI.runBeforeAnalysis(P, IR);
     951           0 :       }
     952        2159 : 
     953           0 :       AnalysisResultListT &ResultList = AnalysisResultLists[&IR];
     954           4 :       ResultList.emplace_back(ID, P.run(IR, *this, ExtraArgs...));
     955           0 : 
     956           6 :       PI.runAfterAnalysis(P, IR);
     957          12 : 
     958           0 :       // P.run may have inserted elements into AnalysisResults and invalidated
     959        2153 :       // RI.
     960           0 :       RI = AnalysisResults.find({ID, &IR});
     961          12 :       assert(RI != AnalysisResults.end() && "we just inserted it!");
     962           0 : 
     963           0 :       RI->second = std::prev(ResultList.end());
     964           0 :     }
     965           0 : 
     966           0 :     return *RI->second->second;
     967           6 :   }
     968           0 : 
     969           0 :   /// Get a cached analysis result or return null.
     970           0 :   ResultConceptT *getCachedResultImpl(AnalysisKey *ID, IRUnitT &IR) const {
     971           0 :     typename AnalysisResultMapT::const_iterator RI =
     972        2858 :         AnalysisResults.find({ID, &IR});
     973        2858 :     return RI == AnalysisResults.end() ? nullptr : &*RI->second->second;
     974         165 :   }
     975           6 : 
     976         129 :   /// Invalidate a function pass result.
     977         129 :   void invalidateImpl(AnalysisKey *ID, IRUnitT &IR) {
     978           9 :     typename AnalysisResultMapT::iterator RI =
     979           6 :         AnalysisResults.find({ID, &IR});
     980        1922 :     if (RI == AnalysisResults.end())
     981         898 :       return;
     982          25 : 
     983           3 :     if (DebugLogging)
     984         361 :       dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name()
     985         367 :              << " on " << IR.getName() << "\n";
     986         190 :     AnalysisResultLists[&IR].erase(RI->second);
     987         105 :     AnalysisResults.erase(RI);
     988        2947 :   }
     989        5228 : 
     990           0 :   /// Map type from module analysis pass ID to pass concept pointer.
     991           0 :   using AnalysisPassMapT =
     992           0 :       DenseMap<AnalysisKey *, std::unique_ptr<PassConceptT>>;
     993           0 : 
     994         361 :   /// Collection of module analysis passes, indexed by ID.
     995         395 :   AnalysisPassMapT AnalysisPasses;
     996          59 : 
     997             :   /// Map from function to a list of function analysis results.
     998         361 :   ///
     999         361 :   /// Provides linear time removal of all analysis results for a function and
    1000          11 :   /// the ultimate storage for a particular cached analysis result.
    1001          68 :   AnalysisResultListMapT AnalysisResultLists;
    1002        3657 : 
    1003        5194 :   /// Map from an analysis ID and function to a particular cached
    1004          35 :   /// analysis result.
    1005        1446 :   AnalysisResultMapT AnalysisResults;
    1006             : 
    1007           1 :   /// Indicates whether we log to \c llvm::dbgs().
    1008           0 :   bool DebugLogging;
    1009           1 : };
    1010          36 : 
    1011          34 : extern template class AnalysisManager<Module>;
    1012        1441 : 
    1013           0 : /// Convenience typedef for the Module analysis manager.
    1014           1 : using ModuleAnalysisManager = AnalysisManager<Module>;
    1015           6 : 
    1016          69 : extern template class AnalysisManager<Function>;
    1017          38 : 
    1018           4 : /// Convenience typedef for the Function analysis manager.
    1019          34 : using FunctionAnalysisManager = AnalysisManager<Function>;
    1020           0 : 
    1021             : /// An analysis over an "outer" IR unit that provides access to an
    1022             : /// analysis manager over an "inner" IR unit.  The inner unit must be contained
    1023           0 : /// in the outer unit.
    1024           0 : ///
    1025          34 : /// For example, InnerAnalysisManagerProxy<FunctionAnalysisManager, Module> is
    1026         710 : /// an analysis over Modules (the "outer" unit) that provides access to a
    1027             : /// Function analysis manager.  The FunctionAnalysisManager is the "inner"
    1028           0 : /// manager being proxied, and Functions are the "inner" unit.  The inner/outer
    1029         676 : /// relationship is valid because each Function is contained in one Module.
    1030         247 : ///
    1031        3208 : /// If you're (transitively) within a pass manager for an IR unit U that
    1032          34 : /// contains IR unit V, you should never use an analysis manager over V, except
    1033        2927 : /// via one of these proxies.
    1034        2132 : ///
    1035           0 : /// Note that the proxy's result is a move-only RAII object.  The validity of
    1036        1471 : /// the analyses in the inner analysis manager is tied to its lifetime.
    1037         204 : template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
    1038         102 : class InnerAnalysisManagerProxy
    1039           0 :     : public AnalysisInfoMixin<
    1040          61 :           InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> {
    1041           0 : public:
    1042           3 :   class Result {
    1043         795 :   public:
    1044        1754 :     explicit Result(AnalysisManagerT &InnerAM) : InnerAM(&InnerAM) {}
    1045        3229 : 
    1046       25298 :     Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)) {
    1047          73 :       // We have to null out the analysis manager in the moved-from state
    1048           0 :       // because we are taking ownership of the responsibilty to clear the
    1049       28039 :       // analysis state.
    1050        4019 :       Arg.InnerAM = nullptr;
    1051          74 :     }
    1052         146 : 
    1053        2478 :     ~Result() {
    1054        2434 :       // InnerAM is cleared in a moved from state where there is nothing to do.
    1055           0 :       if (!InnerAM)
    1056       23463 :         return;
    1057         372 : 
    1058       19734 :       // Clear out the analysis manager if we're being destroyed -- it means we
    1059             :       // didn't even see an invalidate call when we got invalidated.
    1060          11 :       InnerAM->clear();
    1061       19734 :     }
    1062          29 : 
    1063          11 :     Result &operator=(Result &&RHS) {
    1064             :       InnerAM = RHS.InnerAM;
    1065        4830 :       // We have to null out the analysis manager in the moved-from state
    1066          11 :       // because we are taking ownership of the responsibilty to clear the
    1067           0 :       // analysis state.
    1068       19742 :       RHS.InnerAM = nullptr;
    1069          59 :       return *this;
    1070        3677 :     }
    1071           9 : 
    1072         795 :     /// Accessor for the analysis manager.
    1073        6883 :     AnalysisManagerT &getManager() { return *InnerAM; }
    1074        2471 : 
    1075        2434 :     /// Handler for invalidation of the outer IR unit, \c IRUnitT.
    1076           0 :     ///
    1077           0 :     /// If the proxy analysis itself is not preserved, we assume that the set of
    1078             :     /// inner IR objects contained in IRUnit may have changed.  In this case,
    1079           0 :     /// we have to call \c clear() on the inner analysis manager, as it may now
    1080        3964 :     /// have stale pointers to its inner IR objects.
    1081         168 :     ///
    1082         252 :     /// Regardless of whether the proxy analysis is marked as preserved, all of
    1083             :     /// the analyses in the inner analysis manager are potentially invalidated
    1084           0 :     /// based on the set of preserved analyses.
    1085         318 :     bool invalidate(
    1086             :         IRUnitT &IR, const PreservedAnalyses &PA,
    1087           0 :         typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv);
    1088           0 : 
    1089         795 :   private:
    1090           0 :     AnalysisManagerT *InnerAM;
    1091           0 :   };
    1092           0 : 
    1093        3297 :   explicit InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM)
    1094        3297 :       : InnerAM(&InnerAM) {}
    1095           0 : 
    1096          84 :   /// Run the analysis pass and create our proxy result object.
    1097           0 :   ///
    1098           3 :   /// This doesn't do any interesting work; it is primarily used to insert our
    1099        3245 :   /// proxy result object into the outer analysis cache so that we can proxy
    1100          56 :   /// invalidation to the inner analysis manager.
    1101         285 :   Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
    1102          17 :              ExtraArgTs...) {
    1103          56 :     return Result(*InnerAM);
    1104           0 :   }
    1105         114 : 
    1106          56 : private:
    1107           0 :   friend AnalysisInfoMixin<
    1108        1296 :       InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>;
    1109          75 : 
    1110        1274 :   static AnalysisKey Key;
    1111        8807 : 
    1112             :   AnalysisManagerT *InnerAM;
    1113         129 : };
    1114         221 : 
    1115       15097 : template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
    1116        7603 : AnalysisKey
    1117           4 :     InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
    1118             : 
    1119          66 : /// Provide the \c FunctionAnalysisManager to \c Module proxy.
    1120        7589 : using FunctionAnalysisManagerModuleProxy =
    1121        3250 :     InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>;
    1122        3296 : 
    1123         982 : /// Specialization of the invalidate method for the \c
    1124         493 : /// FunctionAnalysisManagerModuleProxy's result.
    1125         906 : template <>
    1126        1806 : bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
    1127        3262 :     Module &M, const PreservedAnalyses &PA,
    1128        2182 :     ModuleAnalysisManager::Invalidator &Inv);
    1129        2161 : 
    1130          43 : // Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern
    1131          43 : // template.
    1132        3271 : extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
    1133        3164 :                                                 Module>;
    1134           0 : 
    1135        3235 : /// An analysis over an "inner" IR unit that provides access to an
    1136             : /// analysis manager over a "outer" IR unit.  The inner unit must be contained
    1137          74 : /// in the outer unit.
    1138          78 : ///
    1139        3165 : /// For example OuterAnalysisManagerProxy<ModuleAnalysisManager, Function> is an
    1140          99 : /// analysis over Functions (the "inner" unit) which provides access to a Module
    1141             : /// analysis manager.  The ModuleAnalysisManager is the "outer" manager being
    1142        6402 : /// proxied, and Modules are the "outer" IR unit.  The inner/outer relationship
    1143          99 : /// is valid because each Function is contained in one Module.
    1144           8 : ///
    1145       15173 : /// This proxy only exposes the const interface of the outer analysis manager,
    1146          99 : /// to indicate that you cannot cause an outer analysis to run from within an
    1147           4 : /// inner pass.  Instead, you must rely on the \c getCachedResult API.
    1148           0 : ///
    1149         886 : /// This proxy doesn't manage invalidation in any way -- that is handled by the
    1150         928 : /// recursive return path of each layer of the pass manager.  A consequence of
    1151         906 : /// this is the outer analyses may be stale.  We invalidate the outer analyses
    1152       23273 : /// only when we're done running passes over the inner IR units.
    1153           4 : template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
    1154       22370 : class OuterAnalysisManagerProxy
    1155       18118 :     : public AnalysisInfoMixin<
    1156           1 :           OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>> {
    1157        4280 : public:
    1158         529 :   /// Result proxy object for \c OuterAnalysisManagerProxy.
    1159         506 :   class Result {
    1160           0 :   public:
    1161           0 :     explicit Result(const AnalysisManagerT &AM) : AM(&AM) {}
    1162          17 : 
    1163          14 :     const AnalysisManagerT &getManager() const { return *AM; }
    1164        4250 : 
    1165        4256 :     /// When invalidation occurs, remove any registered invalidation events.
    1166       28202 :     bool invalidate(
    1167          17 :         IRUnitT &IRUnit, const PreservedAnalyses &PA,
    1168          33 :         typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv) {
    1169          21 :       // Loop over the set of registered outer invalidation mappings and if any
    1170           2 :       // of them map to an analysis that is now invalid, clear it out.
    1171       23931 :       SmallVector<AnalysisKey *, 4> DeadKeys;
    1172           2 :       for (auto &KeyValuePair : OuterAnalysisInvalidationMap) {
    1173          12 :         AnalysisKey *OuterID = KeyValuePair.first;
    1174       23941 :         auto &InnerIDs = KeyValuePair.second;
    1175       23935 :         InnerIDs.erase(llvm::remove_if(InnerIDs, [&](AnalysisKey *InnerID) {
    1176         778 :           return Inv.invalidate(InnerID, IRUnit, PA); }),
    1177         283 :                        InnerIDs.end());
    1178           2 :         if (InnerIDs.empty())
    1179           0 :           DeadKeys.push_back(OuterID);
    1180           0 :       }
    1181           0 : 
    1182           2 :       for (auto OuterID : DeadKeys)
    1183           0 :         OuterAnalysisInvalidationMap.erase(OuterID);
    1184           0 : 
    1185           0 :       // The proxy itself remains valid regardless of anything else.
    1186       47313 :       return false;
    1187           0 :     }
    1188        1538 : 
    1189             :     /// Register a deferred invalidation event for when the outer analysis
    1190           0 :     /// manager processes its invalidations.
    1191           0 :     template <typename OuterAnalysisT, typename InvalidatedAnalysisT>
    1192        3090 :     void registerOuterAnalysisInvalidation() {
    1193        5799 :       AnalysisKey *OuterID = OuterAnalysisT::ID();
    1194       27659 :       AnalysisKey *InvalidatedID = InvalidatedAnalysisT::ID();
    1195       23931 : 
    1196       23932 :       auto &InvalidatedIDList = OuterAnalysisInvalidationMap[OuterID];
    1197        1540 :       // Note, this is a linear scan. If we end up with large numbers of
    1198         780 :       // analyses that all trigger invalidation on the same outer analysis,
    1199         766 :       // this entire system should be changed to some other deterministic
    1200         217 :       // data structure such as a `SetVector` of a pair of pointers.
    1201        5962 :       auto InvalidatedIt = std::find(InvalidatedIDList.begin(),
    1202        1334 :                                      InvalidatedIDList.end(), InvalidatedID);
    1203         667 :       if (InvalidatedIt == InvalidatedIDList.end())
    1204         766 :         InvalidatedIDList.push_back(InvalidatedID);
    1205         676 :     }
    1206        6420 : 
    1207           1 :     /// Access the map from outer analyses to deferred invalidation requiring
    1208           1 :     /// analyses.
    1209         766 :     const SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2> &
    1210        5014 :     getOuterInvalidations() const {
    1211         520 :       return OuterAnalysisInvalidationMap;
    1212         770 :     }
    1213       16953 : 
    1214           0 :   private:
    1215       16956 :     const AnalysisManagerT *AM;
    1216       14296 : 
    1217           4 :     /// A map from an outer analysis ID to the set of this IR-unit's analyses
    1218        3427 :     /// which need to be invalidated.
    1219        1888 :     SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2>
    1220         356 :         OuterAnalysisInvalidationMap;
    1221             :   };
    1222        3077 : 
    1223           1 :   OuterAnalysisManagerProxy(const AnalysisManagerT &AM) : AM(&AM) {}
    1224             : 
    1225        3423 :   /// Run the analysis pass and create our proxy result object.
    1226        4049 :   /// Nothing to see here, it just forwards the \c AM reference into the
    1227       24706 :   /// result.
    1228         627 :   Result run(IRUnitT &, AnalysisManager<IRUnitT, ExtraArgTs...> &,
    1229         626 :              ExtraArgTs...) {
    1230             :     return Result(*AM);
    1231           1 :   }
    1232       20674 : 
    1233          17 : private:
    1234           0 :   friend AnalysisInfoMixin<
    1235       20657 :       OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>>;
    1236       20931 : 
    1237           1 :   static AnalysisKey Key;
    1238         255 : 
    1239         274 :   const AnalysisManagerT *AM;
    1240           0 : };
    1241         274 : 
    1242         274 : template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
    1243         279 : AnalysisKey
    1244           0 :     OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
    1245             : 
    1246           1 : extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
    1247       40806 :                                                 Function>;
    1248             : /// Provide the \c ModuleAnalysisManager to \c Function proxy.
    1249           0 : using ModuleAnalysisManagerFunctionProxy =
    1250          78 :     OuterAnalysisManagerProxy<ModuleAnalysisManager, Function>;
    1251             : 
    1252           1 : /// Trivial adaptor that maps from a module to its functions.
    1253           1 : ///
    1254        3423 : /// Designed to allow composition of a FunctionPass(Manager) and
    1255       23560 : /// a ModulePassManager, by running the FunctionPass(Manager) over every
    1256       20657 : /// function in the module.
    1257       20657 : ///
    1258           1 : /// Function passes run within this adaptor can rely on having exclusive access
    1259             : /// to the function they are run over. They should not read or modify any other
    1260        1806 : /// functions! Other threads or systems may be manipulating other functions in
    1261           1 : /// the module, and so their state should never be relied on.
    1262        4745 : /// FIXME: Make the above true for all of LLVM's actual passes, some still
    1263        1046 : /// violate this principle.
    1264         523 : ///
    1265           0 : /// Function passes can also read the module containing the function, but they
    1266        1806 : /// should not modify that module outside of the use lists of various globals.
    1267        6552 : /// For example, a function pass is not permitted to add functions to the
    1268           1 : /// module.
    1269           0 : /// FIXME: Make the above true for all of LLVM's actual passes, some still
    1270             : /// violate this principle.
    1271        3423 : ///
    1272        2326 : /// Note that although function passes can access module analyses, module
    1273         904 : /// analyses are not invalidated while the function passes are running, so they
    1274        5414 : /// may be stale.  Function analyses will not be stale.
    1275         903 : template <typename FunctionPassT>
    1276        5415 : class ModuleToFunctionPassAdaptor
    1277        4589 :     : public PassInfoMixin<ModuleToFunctionPassAdaptor<FunctionPassT>> {
    1278             : public:
    1279         825 :   explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
    1280         130 :       : Pass(std::move(Pass)) {}
    1281        1033 : 
    1282         904 :   /// Runs the function pass across every function in the module.
    1283         218 :   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
    1284           0 :     FunctionAnalysisManager &FAM =
    1285             :         AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
    1286         825 : 
    1287        1728 :     // Request PassInstrumentation from analysis manager, will use it to run
    1288        5003 :     // instrumenting callbacks for the passes later.
    1289           0 :     PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
    1290          72 : 
    1291           1 :     PreservedAnalyses PA = PreservedAnalyses::all();
    1292           0 :     for (Function &F : M) {
    1293        3274 :       if (F.isDeclaration())
    1294             :         continue;
    1295           0 : 
    1296        3274 :       // Check the PassInstrumentation's BeforePass callbacks before running the
    1297        3275 :       // pass, skip its execution completely if asked to (callback returns
    1298           1 :       // false).
    1299          27 :       if (!PI.runBeforePass<Function>(Pass, F))
    1300           0 :         continue;
    1301             :       PreservedAnalyses PassPA = Pass.run(F, FAM);
    1302           0 : 
    1303           1 :       PI.runAfterPass(Pass, F);
    1304           0 : 
    1305           0 :       // We know that the function pass couldn't have invalidated any other
    1306           1 :       // function's analyses (that's the contract of a function pass), so
    1307           0 :       // directly handle the function analysis manager's invalidation here.
    1308        6494 :       FAM.invalidate(F, PassPA);
    1309             : 
    1310             :       // Then intersect the preserved set so that invalidation of module
    1311           0 :       // analyses will eventually occur when the module pass completes.
    1312           1 :       PA.intersect(std::move(PassPA));
    1313           1 :     }
    1314           0 : 
    1315         825 :     // The FunctionAnalysisManagerModuleProxy is preserved because (we assume)
    1316        4099 :     // the function passes we ran didn't add or remove any functions.
    1317        3274 :     //
    1318        3275 :     // We also preserve all analyses on Functions, because we did all the
    1319           0 :     // invalidation we needed to do above.
    1320         903 :     PA.preserveSet<AllAnalysesOn<Function>>();
    1321           1 :     PA.preserve<FunctionAnalysisManagerModuleProxy>();
    1322           0 :     return PA;
    1323         999 :   }
    1324         288 : 
    1325         144 : private:
    1326         903 :   FunctionPassT Pass;
    1327         904 : };
    1328        1048 : 
    1329           0 : /// A function to deduce a function pass type and wrap it in the
    1330           0 : /// templated adaptor.
    1331             : template <typename FunctionPassT>
    1332        1733 : ModuleToFunctionPassAdaptor<FunctionPassT>
    1333           1 : createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
    1334          48 :   return ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
    1335          53 : }
    1336           0 : 
    1337           5 : /// A utility pass template to force an analysis result to be available.
    1338           5 : ///
    1339         667 : /// If there are extra arguments at the pass's run level there may also be
    1340          93 : /// extra arguments to the analysis manager's \c getResult routine. We can't
    1341           0 : /// guess how to effectively map the arguments from one to the other, and so
    1342       29066 : /// this specialization just ignores them.
    1343           0 : ///
    1344           0 : /// Specific patterns of run-method extra arguments and analysis manager extra
    1345          53 : /// arguments will have to be defined as appropriate specializations.
    1346           0 : template <typename AnalysisT, typename IRUnitT,
    1347           0 :           typename AnalysisManagerT = AnalysisManager<IRUnitT>,
    1348           0 :           typename... ExtraArgTs>
    1349           0 : struct RequireAnalysisPass
    1350           0 :     : PassInfoMixin<RequireAnalysisPass<AnalysisT, IRUnitT, AnalysisManagerT,
    1351         128 :                                         ExtraArgTs...>> {
    1352          22 :   /// Run this pass over some unit of IR.
    1353          22 :   ///
    1354          22 :   /// This pass can be run over any unit of IR and use any analysis manager
    1355           0 :   /// provided they satisfy the basic API requirements. When this pass is
    1356           0 :   /// created, these methods can be instantiated to satisfy whatever the
    1357           0 :   /// context requires.
    1358          31 :   PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM,
    1359           0 :                         ExtraArgTs &&... Args) {
    1360           0 :     (void)AM.template getResult<AnalysisT>(Arg,
    1361          75 :                                            std::forward<ExtraArgTs>(Args)...);
    1362          22 : 
    1363           0 :     return PreservedAnalyses::all();
    1364           9 :   }
    1365          62 : };
    1366           0 : 
    1367           0 : /// A no-op pass template which simply forces a specific analysis result
    1368          91 : /// to be invalidated.
    1369           0 : template <typename AnalysisT>
    1370          18 : struct InvalidateAnalysisPass
    1371           0 :     : PassInfoMixin<InvalidateAnalysisPass<AnalysisT>> {
    1372           0 :   /// Run this pass over some unit of IR.
    1373           0 :   ///
    1374          91 :   /// This pass can be run over any unit of IR and use any analysis manager,
    1375          91 :   /// provided they satisfy the basic API requirements. When this pass is
    1376           0 :   /// created, these methods can be instantiated to satisfy whatever the
    1377           0 :   /// context requires.
    1378       92904 :   template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
    1379           0 :   PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&...) {
    1380         156 :     auto PA = PreservedAnalyses::all();
    1381           1 :     PA.abandon<AnalysisT>();
    1382      185808 :     return PA;
    1383       92917 :   }
    1384           0 : };
    1385           0 : 
    1386           0 : /// A utility pass that does nothing, but preserves no analyses.
    1387       92905 : ///
    1388       27282 : /// Because this preserves no analyses, any analysis passes queried after this
    1389       27347 : /// pass runs will recompute fresh results.
    1390        3255 : struct InvalidateAllAnalysesPass : PassInfoMixin<InvalidateAllAnalysesPass> {
    1391        3242 :   /// Run this pass over some unit of IR.
    1392           0 :   template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
    1393           1 :   PreservedAnalyses run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {
    1394       27281 :     return PreservedAnalyses::none();
    1395       23534 :   }
    1396       23403 : };
    1397          22 : 
    1398          23 : /// A utility pass template that simply runs another pass multiple times.
    1399       27281 : ///
    1400       27281 : /// This can be useful when debugging or testing passes. It also serves as an
    1401           0 : /// example of how to extend the pass manager in ways beyond composition.
    1402       27304 : template <typename PassT>
    1403           1 : class RepeatedPass : public PassInfoMixin<RepeatedPass<PassT>> {
    1404           1 : public:
    1405          76 :   RepeatedPass(int Count, PassT P) : Count(Count), P(std::move(P)) {}
    1406       27303 : 
    1407           0 :   template <typename IRUnitT, typename AnalysisManagerT, typename... Ts>
    1408           1 :   PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, Ts &&... Args) {
    1409       54615 : 
    1410           1 :     // Request PassInstrumentation from analysis manager, will use it to run
    1411           1 :     // instrumenting callbacks for the passes later.
    1412      185808 :     // Here we use std::tuple wrapper over getResult which helps to extract
    1413           1 :     // AnalysisManager's arguments out of the whole Args set.
    1414       81458 :     PassInstrumentation PI =
    1415           0 :         detail::getAnalysisResult<PassInstrumentationAnalysis>(
    1416           0 :             AM, IR, std::tuple<Ts...>(Args...));
    1417           1 : 
    1418      162917 :     auto PA = PreservedAnalyses::all();
    1419       81459 :     for (int i = 0; i < Count; ++i) {
    1420           1 :       // Check the PassInstrumentation's BeforePass callbacks before running the
    1421           0 :       // pass, skip its execution completely if asked to (callback returns
    1422           3 :       // false).
    1423       81459 :       if (!PI.runBeforePass<IRUnitT>(P, IR))
    1424       22643 :         continue;
    1425       22644 :       PA.intersect(P.run(IR, AM, std::forward<Ts>(Args)...));
    1426        2304 :       PI.runAfterPass(P, IR);
    1427        2303 :     }
    1428          10 :     return PA;
    1429           3 :   }
    1430       22646 : 
    1431       19737 : private:
    1432       19735 :   int Count;
    1433           1 :   PassT P;
    1434         836 : };
    1435       22647 : 
    1436       22649 : template <typename PassT>
    1437           0 : RepeatedPass<PassT> createRepeatedPass(int Count, PassT P) {
    1438       22650 :   return RepeatedPass<PassT>(Count, std::move(P));
    1439           9 : }
    1440           1 : 
    1441           6 : } // end namespace llvm
    1442       22652 : 
    1443           1 : #endif // LLVM_IR_PASSMANAGER_H

Generated by: LCOV version 1.13