Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- PassManager.h - Pass management infrastructure -----------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

/// \file

///

/// This header defines various interfaces for pass management in LLVM. There

/// is no "pass" interface in LLVM per se. Instead, an instance of any class

/// which supports a method to 'run' it over a unit of IR can be used as

/// a pass. A pass manager is generally a tool to collect a sequence of passes

/// which run over a particular IR construct, and run each of them in sequence

/// over each such construct in the containing IR construct. As there is no

/// containing IR construct for a Module, a manager for passes over modules

/// forms the base case which runs its managed passes in sequence over the

/// single module provided.

///

/// The core IR library provides managers for running passes over

/// modules and functions.

///

/// * FunctionPassManager can run over a Module, runs each pass over

///   a Function.

/// * ModulePassManager must be directly run, runs each pass over the Module.

///

/// Note that the implementations of the pass managers use concept-based

/// polymorphism as outlined in the "Value Semantics and Concept-based

/// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base

/// Class of Evil") by Sean Parent:

/// * http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations

/// * http://www.youtube.com/watch?v=_BpMYeUFXv8

/// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_IR_PASSMANAGER_H

#define LLVM_IR_PASSMANAGER_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/TinyPtrVector.h"

#include "llvm/IR/Function.h"

#include "llvm/IR/Module.h"

#include "llvm/IR/PassInstrumentation.h"

#include "llvm/IR/PassManagerInternal.h"

#include "llvm/Support/TimeProfiler.h"

#include "llvm/Support/TypeName.h"

#include <cassert>

#include <cstring>

#include <iterator>

#include <list>

#include <memory>

#include <tuple>

#include <type_traits>

#include <utility>

#include <vector>

namespace llvm {

/// A special type used by analysis passes to provide an address that

/// identifies that particular analysis pass type.

///

/// Analysis passes should have a static data member of this type and derive

/// from the \c AnalysisInfoMixin to get a static ID method used to identify

/// the analysis in the pass management infrastructure.

struct alignas(8) AnalysisKey {};

/// A special type used to provide an address that identifies a set of related

/// analyses.  These sets are primarily used below to mark sets of analyses as

/// preserved.

///

/// For example, a transformation can indicate that it preserves the CFG of a

/// function by preserving the appropriate AnalysisSetKey.  An analysis that

/// depends only on the CFG can then check if that AnalysisSetKey is preserved;

/// if it is, the analysis knows that it itself is preserved.

struct alignas(8) AnalysisSetKey {};

/// This templated class represents "all analyses that operate over \<a

/// particular IR unit\>" (e.g. a Function or a Module) in instances of

/// PreservedAnalysis.

///

/// This lets a transformation say e.g. "I preserved all function analyses".

///

/// Note that you must provide an explicit instantiation declaration and

/// definition for this template in order to get the correct behavior on

/// Windows. Otherwise, the address of SetKey will not be stable.

template <typename IRUnitT> class AllAnalysesOn {

public:

  static AnalysisSetKey *ID() { return &SetKey; }

private:

  static AnalysisSetKey SetKey;

};

template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;

extern template class AllAnalysesOn<Module>;

extern template class AllAnalysesOn<Function>;

/// Represents analyses that only rely on functions' control flow.

///

/// This can be used with \c PreservedAnalyses to mark the CFG as preserved and

/// to query whether it has been preserved.

///

/// The CFG of a function is defined as the set of basic blocks and the edges

/// between them. Changing the set of basic blocks in a function is enough to

/// mutate the CFG. Mutating the condition of a branch or argument of an

/// invoked function does not mutate the CFG, but changing the successor labels

/// of those instructions does.

class CFGAnalyses {

public:

  static AnalysisSetKey *ID() { return &SetKey; }

private:

  static AnalysisSetKey SetKey;

};

/// A set of analyses that are preserved following a run of a transformation

/// pass.

///

/// Transformation passes build and return these objects to communicate which

/// analyses are still valid after the transformation. For most passes this is

/// fairly simple: if they don't change anything all analyses are preserved,

/// otherwise only a short list of analyses that have been explicitly updated

/// are preserved.

///

/// This class also lets transformation passes mark abstract *sets* of analyses

/// as preserved. A transformation that (say) does not alter the CFG can

/// indicate such by marking a particular AnalysisSetKey as preserved, and

/// then analyses can query whether that AnalysisSetKey is preserved.

///

/// Finally, this class can represent an "abandoned" analysis, which is

/// not preserved even if it would be covered by some abstract set of analyses.

///

/// Given a `PreservedAnalyses` object, an analysis will typically want to

/// figure out whether it is preserved. In the example below, MyAnalysisType is

/// preserved if it's not abandoned, and (a) it's explicitly marked as

/// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both

/// AnalysisSetA and AnalysisSetB are preserved.

///

/// ```

///   auto PAC = PA.getChecker<MyAnalysisType>();

///   if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() ||

///       (PAC.preservedSet<AnalysisSetA>() &&

///        PAC.preservedSet<AnalysisSetB>())) {

///     // The analysis has been successfully preserved ...

///   }

/// ```

class PreservedAnalyses {

public:

  /// Convenience factory function for the empty preserved set.

  static PreservedAnalyses none() { return PreservedAnalyses(); }

  /// Construct a special preserved set that preserves all passes.

  static PreservedAnalyses all() {

    PreservedAnalyses PA;

    PA.PreservedIDs.insert(&AllAnalysesKey);

    return PA;

  }

  /// Construct a preserved analyses object with a single preserved set.

  template <typename AnalysisSetT>

  static PreservedAnalyses allInSet() {

    PreservedAnalyses PA;

    PA.preserveSet<AnalysisSetT>();

    return PA;

  }

  /// Mark an analysis as preserved.

  template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); }

  /// Given an analysis's ID, mark the analysis as preserved, adding it

  /// to the set.

  void preserve(AnalysisKey *ID) {

    // Clear this ID from the explicit not-preserved set if present.

    NotPreservedAnalysisIDs.erase(ID);

    // If we're not already preserving all analyses (other than those in

    // NotPreservedAnalysisIDs).

    if (!areAllPreserved())

      PreservedIDs.insert(ID);

  }

  /// Mark an analysis set as preserved.

  template <typename AnalysisSetT> void preserveSet() {

    preserveSet(AnalysisSetT::ID());

  }

  /// Mark an analysis set as preserved using its ID.

  void preserveSet(AnalysisSetKey *ID) {

    // If we're not already in the saturated 'all' state, add this set.

    if (!areAllPreserved())

      PreservedIDs.insert(ID);

  }

  /// Mark an analysis as abandoned.

  ///

  /// An abandoned analysis is not preserved, even if it is nominally covered

  /// by some other set or was previously explicitly marked as preserved.

  ///

  /// Note that you can only abandon a specific analysis, not a *set* of

  /// analyses.

  template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); }

  /// Mark an analysis as abandoned using its ID.

  ///

  /// An abandoned analysis is not preserved, even if it is nominally covered

  /// by some other set or was previously explicitly marked as preserved.

  ///

  /// Note that you can only abandon a specific analysis, not a *set* of

  /// analyses.

  void abandon(AnalysisKey *ID) {

    PreservedIDs.erase(ID);

    NotPreservedAnalysisIDs.insert(ID);

  }

  /// Intersect this set with another in place.

  ///

  /// This is a mutating operation on this preserved set, removing all

  /// preserved passes which are not also preserved in the argument.

  void intersect(const PreservedAnalyses &Arg) {

    if (Arg.areAllPreserved())

      return;

    if (areAllPreserved()) {

      *this = Arg;

      return;

    }

    // The intersection requires the *union* of the explicitly not-preserved

    // IDs and the *intersection* of the preserved IDs.

    for (auto *ID : Arg.NotPreservedAnalysisIDs) {

      PreservedIDs.erase(ID);

      NotPreservedAnalysisIDs.insert(ID);

    }

    for (auto *ID : PreservedIDs)

      if (!Arg.PreservedIDs.count(ID))

        PreservedIDs.erase(ID);

  }

  /// Intersect this set with a temporary other set in place.

  ///

  /// This is a mutating operation on this preserved set, removing all

  /// preserved passes which are not also preserved in the argument.

  void intersect(PreservedAnalyses &&Arg) {

    if (Arg.areAllPreserved())

      return;

    if (areAllPreserved()) {

      *this = std::move(Arg);

      return;

    }

    // The intersection requires the *union* of the explicitly not-preserved

    // IDs and the *intersection* of the preserved IDs.

    for (auto *ID : Arg.NotPreservedAnalysisIDs) {

      PreservedIDs.erase(ID);

      NotPreservedAnalysisIDs.insert(ID);

    }

    for (auto *ID : PreservedIDs)

      if (!Arg.PreservedIDs.count(ID))

        PreservedIDs.erase(ID);

  }

  /// A checker object that makes it easy to query for whether an analysis or

  /// some set covering it is preserved.

  class PreservedAnalysisChecker {

    friend class PreservedAnalyses;

    const PreservedAnalyses &PA;

    AnalysisKey *const ID;

    const bool IsAbandoned;

    /// A PreservedAnalysisChecker is tied to a particular Analysis because

    /// `preserved()` and `preservedSet()` both return false if the Analysis

    /// was abandoned.

    PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID)

        : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(ID)) {}

  public:

    /// Returns true if the checker's analysis was not abandoned and either

    ///  - the analysis is explicitly preserved or

    ///  - all analyses are preserved.

    bool preserved() {

      return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||

                              PA.PreservedIDs.count(ID));

    }

    /// Return true if the checker's analysis was not abandoned, i.e. it was not

    /// explicitly invalidated. Even if the analysis is not explicitly

    /// preserved, if the analysis is known stateless, then it is preserved.

    bool preservedWhenStateless() {

      return !IsAbandoned;

    }

    /// Returns true if the checker's analysis was not abandoned and either

    ///  - \p AnalysisSetT is explicitly preserved or

    ///  - all analyses are preserved.

    template <typename AnalysisSetT> bool preservedSet() {

      AnalysisSetKey *SetID = AnalysisSetT::ID();

      return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||

                              PA.PreservedIDs.count(SetID));

    }

  };

  /// Build a checker for this `PreservedAnalyses` and the specified analysis

  /// type.

  ///

  /// You can use the returned object to query whether an analysis was

  /// preserved. See the example in the comment on `PreservedAnalysis`.

  template <typename AnalysisT> PreservedAnalysisChecker getChecker() const {

    return PreservedAnalysisChecker(*this, AnalysisT::ID());

  }

  /// Build a checker for this `PreservedAnalyses` and the specified analysis

  /// ID.

  ///

  /// You can use the returned object to query whether an analysis was

  /// preserved. See the example in the comment on `PreservedAnalysis`.

  PreservedAnalysisChecker getChecker(AnalysisKey *ID) const {

    return PreservedAnalysisChecker(*this, ID);

  }

  /// Test whether all analyses are preserved (and none are abandoned).

  ///

  /// This is used primarily to optimize for the common case of a transformation

  /// which makes no changes to the IR.

  bool areAllPreserved() const {

    return NotPreservedAnalysisIDs.empty() &&

           PreservedIDs.count(&AllAnalysesKey);

  }

  /// Directly test whether a set of analyses is preserved.

  ///

  /// This is only true when no analyses have been explicitly abandoned.

  template <typename AnalysisSetT> bool allAnalysesInSetPreserved() const {

    return allAnalysesInSetPreserved(AnalysisSetT::ID());

  }

  /// Directly test whether a set of analyses is preserved.

  ///

  /// This is only true when no analyses have been explicitly abandoned.

  bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const {

    return NotPreservedAnalysisIDs.empty() &&

           (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(SetID));

  }

private:

  /// A special key used to indicate all analyses.

  static AnalysisSetKey AllAnalysesKey;

  /// The IDs of analyses and analysis sets that are preserved.

  SmallPtrSet<void *, 2> PreservedIDs;

  /// The IDs of explicitly not-preserved analyses.

  ///

  /// If an analysis in this set is covered by a set in `PreservedIDs`, we

  /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always

  /// "wins" over analysis sets in `PreservedIDs`.

  ///

  /// Also, a given ID should never occur both here and in `PreservedIDs`.

  SmallPtrSet<AnalysisKey *, 2> NotPreservedAnalysisIDs;

};

// Forward declare the analysis manager template.

template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;

/// A CRTP mix-in to automatically provide informational APIs needed for

/// passes.

///

/// This provides some boilerplate for types that are passes.

template <typename DerivedT> struct PassInfoMixin {

  /// Gets the name of the pass we are mixed into.

  static StringRef name() {

    static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value,

                  "Must pass the derived type as the template argument!");

    StringRef Name = getTypeName<DerivedT>();

    Name.consume_front("llvm::");

    return Name;

  }

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName) {

    StringRef ClassName = DerivedT::name();

    auto PassName = MapClassName2PassName(ClassName);

    OS << PassName;

  }

};

/// A CRTP mix-in that provides informational APIs needed for analysis passes.

///

/// This provides some boilerplate for types that are analysis passes. It

/// automatically mixes in \c PassInfoMixin.

template <typename DerivedT>

struct AnalysisInfoMixin : PassInfoMixin<DerivedT> {

  /// Returns an opaque, unique ID for this analysis type.

  ///

  /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus

  /// suitable for use in sets, maps, and other data structures that use the low

  /// bits of pointers.

  ///

  /// Note that this requires the derived type provide a static \c AnalysisKey

  /// member called \c Key.

  ///

  /// FIXME: The only reason the mixin type itself can't declare the Key value

  /// is that some compilers cannot correctly unique a templated static variable

  /// so it has the same addresses in each instantiation. The only currently

  /// known platform with this limitation is Windows DLL builds, specifically

  /// building each part of LLVM as a DLL. If we ever remove that build

  /// configuration, this mixin can provide the static key as well.

  static AnalysisKey *ID() {

    static_assert(std::is_base_of<AnalysisInfoMixin, DerivedT>::value,

                  "Must pass the derived type as the template argument!");

    return &DerivedT::Key;

  }

};

namespace detail {

/// Actual unpacker of extra arguments in getAnalysisResult,

/// passes only those tuple arguments that are mentioned in index_sequence.

template <typename PassT, typename IRUnitT, typename AnalysisManagerT,

          typename... ArgTs, size_t... Ns>

typename PassT::Result

getAnalysisResultUnpackTuple(AnalysisManagerT &AM, IRUnitT &IR,

                             std::tuple<ArgTs...> Args,

                             std::index_sequence<Ns...>) {

  (void)Args;

  return AM.template getResult<PassT>(IR, std::get<Ns>(Args)...);

}

/// Helper for *partial* unpacking of extra arguments in getAnalysisResult.

///

/// Arguments passed in tuple come from PassManager, so they might have extra

/// arguments after those AnalysisManager's ExtraArgTs ones that we need to

/// pass to getResult.

template <typename PassT, typename IRUnitT, typename... AnalysisArgTs,

          typename... MainArgTs>

typename PassT::Result

getAnalysisResult(AnalysisManager<IRUnitT, AnalysisArgTs...> &AM, IRUnitT &IR,

                  std::tuple<MainArgTs...> Args) {

  return (getAnalysisResultUnpackTuple<

          PassT, IRUnitT>)(AM, IR, Args,

                           std::index_sequence_for<AnalysisArgTs...>{});

}

} // namespace detail

// Forward declare the pass instrumentation analysis explicitly queried in

// generic PassManager code.

// FIXME: figure out a way to move PassInstrumentationAnalysis into its own

// header.

class PassInstrumentationAnalysis;

/// Manages a sequence of passes over a particular unit of IR.

///

/// A pass manager contains a sequence of passes to run over a particular unit

/// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of

/// IR, and when run over some given IR will run each of its contained passes in

/// sequence. Pass managers are the primary and most basic building block of a

/// pass pipeline.

///

/// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT>

/// argument. The pass manager will propagate that analysis manager to each

/// pass it runs, and will call the analysis manager's invalidation routine with

/// the PreservedAnalyses of each pass it runs.

template <typename IRUnitT,

          typename AnalysisManagerT = AnalysisManager<IRUnitT>,

          typename... ExtraArgTs>

class PassManager : public PassInfoMixin<

                        PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {

public:

  /// Construct a pass manager.

  explicit PassManager() = default;

  // FIXME: These are equivalent to the default move constructor/move

  // assignment. However, using = default triggers linker errors due to the

  // explicit instantiations below. Find away to use the default and remove the

  // duplicated code here.

  PassManager(PassManager &&Arg) : Passes(std::move(Arg.Passes)) {}

  PassManager &operator=(PassManager &&RHS) {

    Passes = std::move(RHS.Passes);

    return *this;

  }

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName) {

    for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {

      auto *P = Passes[Idx].get();

      P->printPipeline(OS, MapClassName2PassName);

      if (Idx + 1 < Size)

        OS << ",";

    }

  }

  /// Run all of the passes in this manager over the given unit of IR.

  /// ExtraArgs are passed to each pass.

  PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,

                        ExtraArgTs... ExtraArgs) {

    PreservedAnalyses PA = PreservedAnalyses::all();

    // Request PassInstrumentation from analysis manager, will use it to run

    // instrumenting callbacks for the passes later.

    // Here we use std::tuple wrapper over getResult which helps to extract

    // AnalysisManager's arguments out of the whole ExtraArgs set.

    PassInstrumentation PI =

        detail::getAnalysisResult<PassInstrumentationAnalysis>(

            AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));

    for (auto &Pass : Passes) {

      // Check the PassInstrumentation's BeforePass callbacks before running the

      // pass, skip its execution completely if asked to (callback returns

      // false).

      if (!PI.runBeforePass<IRUnitT>(*Pass, IR))

        continue;

      PreservedAnalyses PassPA = Pass->run(IR, AM, ExtraArgs...);

      // Call onto PassInstrumentation's AfterPass callbacks immediately after

      // running the pass.

      PI.runAfterPass<IRUnitT>(*Pass, IR, PassPA);

      // Update the analysis manager as each pass runs and potentially

      // invalidates analyses.

      AM.invalidate(IR, PassPA);

      // Finally, intersect the preserved analyses to compute the aggregate

      // preserved set for this pass manager.

      PA.intersect(std::move(PassPA));

    }

    // Invalidation was handled after each pass in the above loop for the

    // current unit of IR. Therefore, the remaining analysis results in the

    // AnalysisManager are preserved. We mark this with a set so that we don't

    // need to inspect each one individually.

    PA.preserveSet<AllAnalysesOn<IRUnitT>>();

    return PA;

  }

  template <typename PassT>

  LLVM_ATTRIBUTE_MINSIZE

      std::enable_if_t<!std::is_same<PassT, PassManager>::value>

      addPass(PassT &&Pass) {

    using PassModelT =

        detail::PassModel<IRUnitT, PassT, PreservedAnalyses, AnalysisManagerT,

                          ExtraArgTs...>;

    // Do not use make_unique or emplace_back, they cause too many template

    // instantiations, causing terrible compile times.

    Passes.push_back(std::unique_ptr<PassConceptT>(

        new PassModelT(std::forward<PassT>(Pass))));

  }

  /// When adding a pass manager pass that has the same type as this pass

  /// manager, simply move the passes over. This is because we don't have use

  /// cases rely on executing nested pass managers. Doing this could reduce

  /// implementation complexity and avoid potential invalidation issues that may

  /// happen with nested pass managers of the same type.

  template <typename PassT>

  LLVM_ATTRIBUTE_MINSIZE

      std::enable_if_t<std::is_same<PassT, PassManager>::value>

      addPass(PassT &&Pass) {

    for (auto &P : Pass.Passes)

      Passes.push_back(std::move(P));

  }

  /// Returns if the pass manager contains any passes.

  bool isEmpty() const { return Passes.empty(); }

  static bool isRequired() { return true; }

protected:

  using PassConceptT =

      detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;

  std::vector<std::unique_ptr<PassConceptT>> Passes;

};

extern template class PassManager<Module>;

/// Convenience typedef for a pass manager over modules.

using ModulePassManager = PassManager<Module>;

extern template class PassManager<Function>;

/// Convenience typedef for a pass manager over functions.

using FunctionPassManager = PassManager<Function>;

/// Pseudo-analysis pass that exposes the \c PassInstrumentation to pass

/// managers. Goes before AnalysisManager definition to provide its

/// internals (e.g PassInstrumentationAnalysis::ID) for use there if needed.

/// FIXME: figure out a way to move PassInstrumentationAnalysis into its own

/// header.

class PassInstrumentationAnalysis

    : public AnalysisInfoMixin<PassInstrumentationAnalysis> {

  friend AnalysisInfoMixin<PassInstrumentationAnalysis>;

  static AnalysisKey Key;

  PassInstrumentationCallbacks *Callbacks;

public:

  /// PassInstrumentationCallbacks object is shared, owned by something else,

  /// not this analysis.

  PassInstrumentationAnalysis(PassInstrumentationCallbacks *Callbacks = nullptr)

      : Callbacks(Callbacks) {}

  using Result = PassInstrumentation;

  template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>

  Result run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {

    return PassInstrumentation(Callbacks);

  }

};

/// A container for analyses that lazily runs them and caches their

/// results.

///

/// This class can manage analyses for any IR unit where the address of the IR

/// unit sufficies as its identity.

template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager {

public:

  class Invalidator;

private:

  // Now that we've defined our invalidator, we can define the concept types.

  using ResultConceptT =

      detail::AnalysisResultConcept<IRUnitT, PreservedAnalyses, Invalidator>;

  using PassConceptT =

      detail::AnalysisPassConcept<IRUnitT, PreservedAnalyses, Invalidator,

                                  ExtraArgTs...>;

  /// List of analysis pass IDs and associated concept pointers.

  ///

  /// Requires iterators to be valid across appending new entries and arbitrary

  /// erases. Provides the analysis ID to enable finding iterators to a given

  /// entry in maps below, and provides the storage for the actual result

  /// concept.

  using AnalysisResultListT =

      std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>;

  /// Map type from IRUnitT pointer to our custom list type.

  using AnalysisResultListMapT = DenseMap<IRUnitT *, AnalysisResultListT>;

  /// Map type from a pair of analysis ID and IRUnitT pointer to an

  /// iterator into a particular result list (which is where the actual analysis

  /// result is stored).

  using AnalysisResultMapT =

      DenseMap<std::pair<AnalysisKey *, IRUnitT *>,

               typename AnalysisResultListT::iterator>;

public:

  /// API to communicate dependencies between analyses during invalidation.

  ///

  /// When an analysis result embeds handles to other analysis results, it

  /// needs to be invalidated both when its own information isn't preserved and

  /// when any of its embedded analysis results end up invalidated. We pass an

  /// \c Invalidator object as an argument to \c invalidate() in order to let

  /// the analysis results themselves define the dependency graph on the fly.

  /// This lets us avoid building an explicit representation of the

  /// dependencies between analysis results.

  class Invalidator {

  public:

    /// Trigger the invalidation of some other analysis pass if not already

    /// handled and return whether it was in fact invalidated.

    ///

    /// This is expected to be called from within a given analysis result's \c

    /// invalidate method to trigger a depth-first walk of all inter-analysis

    /// dependencies. The same \p IR unit and \p PA passed to that result's \c

    /// invalidate method should in turn be provided to this routine.

    ///

    /// The first time this is called for a given analysis pass, it will call

    /// the corresponding result's \c invalidate method.  Subsequent calls will

    /// use a cache of the results of that initial call.  It is an error to form

    /// cyclic dependencies between analysis results.

    ///

    /// This returns true if the given analysis's result is invalid. Any

    /// dependecies on it will become invalid as a result.

    template <typename PassT>

    bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {

      using ResultModelT =

          detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,

                                      PreservedAnalyses, Invalidator>;

      return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);

    }

    /// A type-erased variant of the above invalidate method with the same core

    /// API other than passing an analysis ID rather than an analysis type

    /// parameter.

    ///

    /// This is sadly less efficient than the above routine, which leverages

    /// the type parameter to avoid the type erasure overhead.

    bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {

      return invalidateImpl<>(ID, IR, PA);

    }

  private:

    friend class AnalysisManager;

    template <typename ResultT = ResultConceptT>

    bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,

                        const PreservedAnalyses &PA) {

      // If we've already visited this pass, return true if it was invalidated

      // and false otherwise.

      auto IMapI = IsResultInvalidated.find(ID);

      if (IMapI != IsResultInvalidated.end())

        return IMapI->second;

      // Otherwise look up the result object.

      auto RI = Results.find({ID, &IR});

      assert(RI != Results.end() &&

             "Trying to invalidate a dependent result that isn't in the "

             "manager's cache is always an error, likely due to a stale result "

             "handle!");

      auto &Result = static_cast<ResultT &>(*RI->second->second);

      // Insert into the map whether the result should be invalidated and return

      // that. Note that we cannot reuse IMapI and must do a fresh insert here,

      // as calling invalidate could (recursively) insert things into the map,

      // making any iterator or reference invalid.

      bool Inserted;

      std::tie(IMapI, Inserted) =

          IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});

      (void)Inserted;

      assert(Inserted && "Should not have already inserted this ID, likely "

                         "indicates a dependency cycle!");

      return IMapI->second;

    }

    Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated,

                const AnalysisResultMapT &Results)

        : IsResultInvalidated(IsResultInvalidated), Results(Results) {}

    SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;

    const AnalysisResultMapT &Results;

  };

  /// Construct an empty analysis manager.

  AnalysisManager();

  AnalysisManager(AnalysisManager &&);

  AnalysisManager &operator=(AnalysisManager &&);

  /// Returns true if the analysis manager has an empty results cache.

  bool empty() const {

    assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&

           "The storage and index of analysis results disagree on how many "

           "there are!");

    return AnalysisResults.empty();

  }

  /// Clear any cached analysis results for a single unit of IR.

  ///

  /// This doesn't invalidate, but instead simply deletes, the relevant results.

  /// It is useful when the IR is being removed and we want to clear out all the

  /// memory pinned for it.

  void clear(IRUnitT &IR, llvm::StringRef Name);

  /// Clear all analysis results cached by this AnalysisManager.

  ///

  /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply

  /// deletes them.  This lets you clean up the AnalysisManager when the set of

  /// IR units itself has potentially changed, and thus we can't even look up a

  /// a result and invalidate/clear it directly.

  void clear() {

    AnalysisResults.clear();

    AnalysisResultLists.clear();

  }

  /// Get the result of an analysis pass for a given IR unit.

  ///

  /// Runs the analysis if a cached result is not available.

  template <typename PassT>

  typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) {

    assert(AnalysisPasses.count(PassT::ID()) &&

           "This analysis pass was not registered prior to being queried");

    ResultConceptT &ResultConcept =

        getResultImpl(PassT::ID(), IR, ExtraArgs...);

    using ResultModelT =

        detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,

                                    PreservedAnalyses, Invalidator>;

    return static_cast<ResultModelT &>(ResultConcept).Result;

  }

  /// Get the cached result of an analysis pass for a given IR unit.

  ///

  /// This method never runs the analysis.

  ///

  /// \returns null if there is no cached result.

  template <typename PassT>

  typename PassT::Result *getCachedResult(IRUnitT &IR) const {

    assert(AnalysisPasses.count(PassT::ID()) &&

           "This analysis pass was not registered prior to being queried");

    ResultConceptT *ResultConcept = getCachedResultImpl(PassT::ID(), IR);

    if (!ResultConcept)

      return nullptr;

    using ResultModelT =

        detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,

                                    PreservedAnalyses, Invalidator>;

    return &static_cast<ResultModelT *>(ResultConcept)->Result;

  }

  /// Verify that the given Result cannot be invalidated, assert otherwise.

  template <typename PassT>

  void verifyNotInvalidated(IRUnitT &IR, typename PassT::Result *Result) const {

    PreservedAnalyses PA = PreservedAnalyses::none();

    SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;

    Invalidator Inv(IsResultInvalidated, AnalysisResults);

    assert(!Result->invalidate(IR, PA, Inv) &&

           "Cached result cannot be invalidated");

  }

  /// Register an analysis pass with the manager.

  ///

  /// The parameter is a callable whose result is an analysis pass. This allows

  /// passing in a lambda to construct the analysis.

  ///

  /// The analysis type to register is the type returned by calling the \c

  /// PassBuilder argument. If that type has already been registered, then the

  /// argument will not be called and this function will return false.

  /// Otherwise, we register the analysis returned by calling \c PassBuilder(),

  /// and this function returns true.

  ///

  /// (Note: Although the return value of this function indicates whether or not

  /// an analysis was previously registered, there intentionally isn't a way to

  /// query this directly.  Instead, you should just register all the analyses

  /// you might want and let this class run them lazily.  This idiom lets us

  /// minimize the number of times we have to look up analyses in our

  /// hashtable.)

  template <typename PassBuilderT>

  bool registerPass(PassBuilderT &&PassBuilder) {

    using PassT = decltype(PassBuilder());

    using PassModelT =

        detail::AnalysisPassModel<IRUnitT, PassT, PreservedAnalyses,

                                  Invalidator, ExtraArgTs...>;

    auto &PassPtr = AnalysisPasses[PassT::ID()];

    if (PassPtr)

      // Already registered this pass type!