text: //===- CGSCCPassManager.h - Call graph pass management ----------*- 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 provides classes for managing passes over SCCs of the call
  /// graph. These passes form an important component of LLVM's interprocedural
  /// optimizations. Because they operate on the SCCs of the call graph, and they
  /// traverse the graph in post-order, they can effectively do pair-wise
  /// interprocedural optimizations for all call edges in the program while
  /// incrementally refining it and improving the context of these pair-wise
  /// optimizations. At each call site edge, the callee has already been
  /// optimized as much as is possible. This in turn allows very accurate
  /// analysis of it for IPO.
  ///
  /// A secondary more general goal is to be able to isolate optimization on
  /// unrelated parts of the IR module. This is useful to ensure our
  /// optimizations are principled and don't miss oportunities where refinement
  /// of one part of the module influences transformations in another part of the
  /// module. But this is also useful if we want to parallelize the optimizations
  /// across common large module graph shapes which tend to be very wide and have
  /// large regions of unrelated cliques.
  ///
  /// To satisfy these goals, we use the LazyCallGraph which provides two graphs
  /// nested inside each other (and built lazily from the bottom-up): the call
  /// graph proper, and a reference graph. The reference graph is super set of
  /// the call graph and is a conservative approximation of what could through
  /// scalar or CGSCC transforms *become* the call graph. Using this allows us to
  /// ensure we optimize functions prior to them being introduced into the call
  /// graph by devirtualization or other technique, and thus ensures that
  /// subsequent pair-wise interprocedural optimizations observe the optimized
  /// form of these functions. The (potentially transitive) reference
  /// reachability used by the reference graph is a conservative approximation
  /// that still allows us to have independent regions of the graph.
  ///
  /// FIXME: There is one major drawback of the reference graph: in its naive
  /// form it is quadratic because it contains a distinct edge for each
  /// (potentially indirect) reference, even if are all through some common
  /// global table of function pointers. This can be fixed in a number of ways
  /// that essentially preserve enough of the normalization. While it isn't
  /// expected to completely preclude the usability of this, it will need to be
  /// addressed.
  ///
  ///
  /// All of these issues are made substantially more complex in the face of
  /// mutations to the call graph while optimization passes are being run. When
  /// mutations to the call graph occur we want to achieve two different things:
  ///
  /// - We need to update the call graph in-flight and invalidate analyses
  ///   cached on entities in the graph. Because of the cache-based analysis
  ///   design of the pass manager, it is essential to have stable identities for
  ///   the elements of the IR that passes traverse, and to invalidate any
  ///   analyses cached on these elements as the mutations take place.
  ///
  /// - We want to preserve the incremental and post-order traversal of the
  ///   graph even as it is refined and mutated. This means we want optimization
  ///   to observe the most refined form of the call graph and to do so in
  ///   post-order.
  ///
  /// To address this, the CGSCC manager uses both worklists that can be expanded
  /// by passes which transform the IR, and provides invalidation tests to skip
  /// entries that become dead. This extra data is provided to every SCC pass so
  /// that it can carefully update the manager's traversal as the call graph
  /// mutates.
  ///
  /// We also provide support for running function passes within the CGSCC walk,
  /// and there we provide automatic update of the call graph including of the
  /// pass manager to reflect call graph changes that fall out naturally as part
  /// of scalar transformations.
  ///
  /// The patterns used to ensure the goals of post-order visitation of the fully
  /// refined graph:
  ///
  /// 1) Sink toward the "bottom" as the graph is refined. This means that any
  ///    iteration continues in some valid post-order sequence after the mutation
  ///    has altered the structure.
  ///
  /// 2) Enqueue in post-order, including the current entity. If the current
  ///    entity's shape changes, it and everything after it in post-order needs
  ///    to be visited to observe that shape.
  ///
  //===----------------------------------------------------------------------===//
  
  #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  
  #include "llvm/ADT/MapVector.h"
  #include "llvm/Analysis/LazyCallGraph.h"
  #include "llvm/IR/PassManager.h"
  #include "llvm/IR/ValueHandle.h"
  #include "llvm/Support/raw_ostream.h"
  #include <cassert>
  #include <utility>
  
  namespace llvm {
  
  class Function;
  class Value;
  template <typename T, unsigned int N> class SmallPriorityWorklist;
  struct CGSCCUpdateResult;
  
  class Module;
  
  // Allow debug logging in this inline function.
  #define DEBUG_TYPE "cgscc"
  
  /// Extern template declaration for the analysis set for this IR unit.
  extern template class AllAnalysesOn<LazyCallGraph::SCC>;
  
  extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
  
  /// The CGSCC analysis manager.
  ///
  /// See the documentation for the AnalysisManager template for detail
  /// documentation. This type serves as a convenient way to refer to this
  /// construct in the adaptors and proxies used to integrate this into the larger
  /// pass manager infrastructure.
  using CGSCCAnalysisManager =
      AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
  
  // Explicit specialization and instantiation declarations for the pass manager.
  // See the comments on the definition of the specialization for details on how
  // it differs from the primary template.
  template <>
  PreservedAnalyses
  PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
              CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
                                        CGSCCAnalysisManager &AM,
                                        LazyCallGraph &G, CGSCCUpdateResult &UR);
  extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
                                    LazyCallGraph &, CGSCCUpdateResult &>;
  
  /// The CGSCC pass manager.
  ///
  /// See the documentation for the PassManager template for details. It runs
  /// a sequence of SCC passes over each SCC that the manager is run over. This
  /// type serves as a convenient way to refer to this construct.
  using CGSCCPassManager =
      PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
                  CGSCCUpdateResult &>;
  
  /// An explicit specialization of the require analysis template pass.
  template <typename AnalysisT>
  struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
                             LazyCallGraph &, CGSCCUpdateResult &>
      : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
                                          CGSCCAnalysisManager, LazyCallGraph &,
                                          CGSCCUpdateResult &>> {
    PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                          LazyCallGraph &CG, CGSCCUpdateResult &) {
      (void)AM.template getResult<AnalysisT>(C, CG);
      return PreservedAnalyses::all();
    }
    void printPipeline(raw_ostream &OS,
                       function_ref<StringRef(StringRef)> MapClassName2PassName) {
      auto ClassName = AnalysisT::name();
      auto PassName = MapClassName2PassName(ClassName);
      OS << "require<" << PassName << ">";
    }
  };
  
  /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
  using CGSCCAnalysisManagerModuleProxy =
      InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
  
  /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
  /// it can have access to the call graph in order to walk all the SCCs when
  /// invalidating things.
  template <> class CGSCCAnalysisManagerModuleProxy::Result {
  public:
    explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
        : InnerAM(&InnerAM), G(&G) {}
  
    /// Accessor for the analysis manager.
    CGSCCAnalysisManager &getManager() { return *InnerAM; }
  
    /// Handler for invalidation of the Module.
    ///
    /// If the proxy analysis itself is preserved, then we assume that the set of
    /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
    /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
    /// on the CGSCCAnalysisManager.
    ///
    /// Regardless of whether this analysis is marked as preserved, all of the
    /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
    /// on the set of preserved analyses.
    bool invalidate(Module &M, const PreservedAnalyses &PA,
                    ModuleAnalysisManager::Invalidator &Inv);
  
  private:
    CGSCCAnalysisManager *InnerAM;
    LazyCallGraph *G;
  };
  
  /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
  /// so it can pass the lazy call graph to the result.
  template <>
  CGSCCAnalysisManagerModuleProxy::Result
  CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
  
  // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
  // template.
  extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
  
  extern template class OuterAnalysisManagerProxy<
      ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
  
  /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
  using ModuleAnalysisManagerCGSCCProxy =
      OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
                                LazyCallGraph &>;
  
  /// Support structure for SCC passes to communicate updates the call graph back
  /// to the CGSCC pass manager infrastructure.
  ///
  /// The CGSCC pass manager runs SCC passes which are allowed to update the call
  /// graph and SCC structures. This means the structure the pass manager works
  /// on is mutating underneath it. In order to support that, there needs to be
  /// careful communication about the precise nature and ramifications of these
  /// updates to the pass management infrastructure.
  ///
  /// All SCC passes will have to accept a reference to the management layer's
  /// update result struct and use it to reflect the results of any CG updates
  /// performed.
  ///
  /// Passes which do not change the call graph structure in any way can just
  /// ignore this argument to their run method.
  struct CGSCCUpdateResult {
    /// Worklist of the RefSCCs queued for processing.
    ///
    /// When a pass refines the graph and creates new RefSCCs or causes them to
    /// have a different shape or set of component SCCs it should add the RefSCCs
    /// to this worklist so that we visit them in the refined form.
    ///
    /// This worklist is in reverse post-order, as we pop off the back in order
    /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
    /// them in reverse post-order.
    SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;
  
    /// Worklist of the SCCs queued for processing.
    ///
    /// When a pass refines the graph and creates new SCCs or causes them to have
    /// a different shape or set of component functions it should add the SCCs to
    /// this worklist so that we visit them in the refined form.
    ///
    /// Note that if the SCCs are part of a RefSCC that is added to the \c
    /// RCWorklist, they don't need to be added here as visiting the RefSCC will
    /// be sufficient to re-visit the SCCs within it.
    ///
    /// This worklist is in reverse post-order, as we pop off the back in order
    /// to observe SCCs in post-order. When adding SCCs, clients should add them
    /// in reverse post-order.
    SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;
  
    /// The set of invalidated RefSCCs which should be skipped if they are found
    /// in \c RCWorklist.
    ///
    /// This is used to quickly prune out RefSCCs when they get deleted and
    /// happen to already be on the worklist. We use this primarily to avoid
    /// scanning the list and removing entries from it.
    SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
  
    /// The set of invalidated SCCs which should be skipped if they are found
    /// in \c CWorklist.
    ///
    /// This is used to quickly prune out SCCs when they get deleted and happen
    /// to already be on the worklist. We use this primarily to avoid scanning
    /// the list and removing entries from it.
    SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
  
    /// If non-null, the updated current \c RefSCC being processed.
    ///
    /// This is set when a graph refinement takes place and the "current" point
    /// in the graph moves "down" or earlier in the post-order walk. This will
    /// often cause the "current" RefSCC to be a newly created RefSCC object and
    /// the old one to be added to the above worklist. When that happens, this
    /// pointer is non-null and can be used to continue processing the "top" of
    /// the post-order walk.
    LazyCallGraph::RefSCC *UpdatedRC;
  
    /// If non-null, the updated current \c SCC being processed.
    ///
    /// This is set when a graph refinement takes place and the "current" point
    /// in the graph moves "down" or earlier in the post-order walk. This will
    /// often cause the "current" SCC to be a newly created SCC object and the
    /// old one to be added to the above worklist. When that happens, this
    /// pointer is non-null and can be used to continue processing the "top" of
    /// the post-order walk.
    LazyCallGraph::SCC *UpdatedC;
  
    /// Preserved analyses across SCCs.
    ///
    /// We specifically want to allow CGSCC passes to mutate ancestor IR
    /// (changing both the CG structure and the function IR itself). However,
    /// this means we need to take special care to correctly mark what analyses
    /// are preserved *across* SCCs. We have to track this out-of-band here
    /// because within the main `PassManager` infrastructure we need to mark
    /// everything within an SCC as preserved in order to avoid repeatedly
    /// invalidating the same analyses as we unnest pass managers and adaptors.
    /// So we track the cross-SCC version of the preserved analyses here from any
    /// code that does direct invalidation of SCC analyses, and then use it
    /// whenever we move forward in the post-order walk of SCCs before running
    /// passes over the new SCC.
    PreservedAnalyses CrossSCCPA;
  
    /// A hacky area where the inliner can retain history about inlining
    /// decisions that mutated the call graph's SCC structure in order to avoid
    /// infinite inlining. See the comments in the inliner's CG update logic.
    ///
    /// FIXME: Keeping this here seems like a big layering issue, we should look
    /// for a better technique.
    SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
        &InlinedInternalEdges;
  
    /// Weak VHs to keep track of indirect calls for the purposes of detecting
    /// devirtualization.
    ///
    /// This is a map to avoid having duplicate entries. If a Value is
    /// deallocated, its corresponding WeakTrackingVH will be nulled out. When
    /// checking if a Value is in the map or not, also check if the corresponding
    /// WeakTrackingVH is null to avoid issues with a new Value sharing the same
    /// address as a deallocated one.
    SmallMapVector<Value *, WeakTrackingVH, 16> IndirectVHs;
  };
  
  /// The core module pass which does a post-order walk of the SCCs and
  /// runs a CGSCC pass over each one.
  ///
  /// Designed to allow composition of a CGSCCPass(Manager) and
  /// a ModulePassManager. Note that this pass must be run with a module analysis
  /// manager as it uses the LazyCallGraph analysis. It will also run the
  /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
  /// pass over the module to enable a \c FunctionAnalysisManager to be used
  /// within this run safely.
  class ModuleToPostOrderCGSCCPassAdaptor
      : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor> {
  public:
    using PassConceptT =
        detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
                            LazyCallGraph &, CGSCCUpdateResult &>;
  
    explicit ModuleToPostOrderCGSCCPassAdaptor(std::unique_ptr<PassConceptT> Pass)
        : Pass(std::move(Pass)) {}
  
    ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
        : Pass(std::move(Arg.Pass)) {}
  
    friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
                     ModuleToPostOrderCGSCCPassAdaptor &RHS) {
      std::swap(LHS.Pass, RHS.Pass);
    }
  
    ModuleToPostOrderCGSCCPassAdaptor &
    operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
      swap(*this, RHS);
      return *this;
    }
  
    /// Runs the CGSCC pass across every SCC in the module.
    PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
  
    void printPipeline(raw_ostream &OS,
                       function_ref<StringRef(StringRef)> MapClassName2PassName) {
      OS << "cgscc(";
      Pass->printPipeline(OS, MapClassName2PassName);
      OS << ")";
    }
  
    static bool isRequired() { return true; }
  
  private:
    std::unique_ptr<PassConceptT> Pass;
  };
  
  /// A function to deduce a function pass type and wrap it in the
  /// templated adaptor.
  template <typename CGSCCPassT>
  ModuleToPostOrderCGSCCPassAdaptor
  createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT &&Pass) {
    using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
                                         PreservedAnalyses, CGSCCAnalysisManager,
                                         LazyCallGraph &, CGSCCUpdateResult &>;
    // Do not use make_unique, it causes too many template instantiations,
    // causing terrible compile times.
    return ModuleToPostOrderCGSCCPassAdaptor(
        std::unique_ptr<ModuleToPostOrderCGSCCPassAdaptor::PassConceptT>(
            new PassModelT(std::forward<CGSCCPassT>(Pass))));
  }
  
  /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
  ///
  /// When a module pass runs and triggers invalidation, both the CGSCC and
  /// Function analysis manager proxies on the module get an invalidation event.
  /// We don't want to fully duplicate responsibility for most of the
  /// invalidation logic. Instead, this layer is only responsible for SCC-local
  /// invalidation events. We work with the module's FunctionAnalysisManager to
  /// invalidate function analyses.
  class FunctionAnalysisManagerCGSCCProxy
      : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
  public:
    class Result {
    public:
      explicit Result() : FAM(nullptr) {}
      explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
  
      void updateFAM(FunctionAnalysisManager &FAM) { this->FAM = &FAM; }
      /// Accessor for the analysis manager.
      FunctionAnalysisManager &getManager() {
        assert(FAM);
        return *FAM;
      }
  
      bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
                      CGSCCAnalysisManager::Invalidator &Inv);
  
    private:
      FunctionAnalysisManager *FAM;
    };
  
    /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
    Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
  
  private:
    friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
  
    static AnalysisKey Key;
  };
  
  extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
  
  /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
  using CGSCCAnalysisManagerFunctionProxy =
      OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
  
  /// Helper to update the call graph after running a function pass.
  ///
  /// Function passes can only mutate the call graph in specific ways. This
  /// routine provides a helper that updates the call graph in those ways
  /// including returning whether any changes were made and populating a CG
  /// update result struct for the overall CGSCC walk.
  LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
      LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
      CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
      FunctionAnalysisManager &FAM);
  
  /// Helper to update the call graph after running a CGSCC pass.
  ///
  /// CGSCC passes can only mutate the call graph in specific ways. This
  /// routine provides a helper that updates the call graph in those ways
  /// including returning whether any changes were made and populating a CG
  /// update result struct for the overall CGSCC walk.
  LazyCallGraph::SCC &updateCGAndAnalysisManagerForCGSCCPass(
      LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
      CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
      FunctionAnalysisManager &FAM);
  
  /// Adaptor that maps from a SCC to its functions.
  ///
  /// Designed to allow composition of a FunctionPass(Manager) and
  /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
  /// to a \c CGSCCAnalysisManager it will run the
  /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
  /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
  /// within this run safely.
  class CGSCCToFunctionPassAdaptor
      : public PassInfoMixin<CGSCCToFunctionPassAdaptor> {
  public:
    using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
  
    explicit CGSCCToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass,
                                        bool EagerlyInvalidate, bool NoRerun)
        : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate),
          NoRerun(NoRerun) {}
  
    CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
        : Pass(std::move(Arg.Pass)), EagerlyInvalidate(Arg.EagerlyInvalidate),
          NoRerun(Arg.NoRerun) {}
  
    friend void swap(CGSCCToFunctionPassAdaptor &LHS,
                     CGSCCToFunctionPassAdaptor &RHS) {
      std::swap(LHS.Pass, RHS.Pass);
    }
  
    CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
      swap(*this, RHS);
      return *this;
    }
  
    /// Runs the function pass across every function in the module.
    PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                          LazyCallGraph &CG, CGSCCUpdateResult &UR);
  
    void printPipeline(raw_ostream &OS,
                       function_ref<StringRef(StringRef)> MapClassName2PassName) {
      OS << "function";
      if (EagerlyInvalidate)
        OS << "<eager-inv>";
      OS << "(";
      Pass->printPipeline(OS, MapClassName2PassName);
      OS << ")";
    }
  
    static bool isRequired() { return true; }
  
  private:
    std::unique_ptr<PassConceptT> Pass;
    bool EagerlyInvalidate;
    bool NoRerun;
  };
  
  /// A function to deduce a function pass type and wrap it in the
  /// templated adaptor.
  template <typename FunctionPassT>
  CGSCCToFunctionPassAdaptor
  createCGSCCToFunctionPassAdaptor(FunctionPassT &&Pass,
                                   bool EagerlyInvalidate = false,
                                   bool NoRerun = false) {
    using PassModelT =
        detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
                          FunctionAnalysisManager>;
    // Do not use make_unique, it causes too many template instantiations,
    // causing terrible compile times.
    return CGSCCToFunctionPassAdaptor(
        std::unique_ptr<CGSCCToFunctionPassAdaptor::PassConceptT>(
            new PassModelT(std::forward<FunctionPassT>(Pass))),
        EagerlyInvalidate, NoRerun);
  }
  
  // A marker to determine if function passes should be run on a function within a
  // CGSCCToFunctionPassAdaptor. This is used to prevent running an expensive
  // function pass (manager) on a function multiple times if SCC mutations cause a
  // function to be visited multiple times and the function is not modified by
  // other SCC passes.
  class ShouldNotRunFunctionPassesAnalysis
      : public AnalysisInfoMixin<ShouldNotRunFunctionPassesAnalysis> {
  public:
    static AnalysisKey Key;
    struct Result {};
  
    Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); }
  };
  
  /// A helper that repeats an SCC pass each time an indirect call is refined to
  /// a direct call by that pass.
  ///
  /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
  /// change shape, we may also want to repeat an SCC pass if it simply refines
  /// an indirect call to a direct call, even if doing so does not alter the
  /// shape of the graph. Note that this only pertains to direct calls to
  /// functions where IPO across the SCC may be able to compute more precise
  /// results. For intrinsics, we assume scalar optimizations already can fully
  /// reason about them.
  ///
  /// This repetition has the potential to be very large however, as each one
  /// might refine a single call site. As a consequence, in practice we use an
  /// upper bound on the number of repetitions to limit things.
  class DevirtSCCRepeatedPass : public PassInfoMixin<DevirtSCCRepeatedPass> {
  public:
    using PassConceptT =
        detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
                            LazyCallGraph &, CGSCCUpdateResult &>;
  
    explicit DevirtSCCRepeatedPass(std::unique_ptr<PassConceptT> Pass,
                                   int MaxIterations)
        : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
  
    /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
    /// whenever an indirect call is refined.
    PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
                          LazyCallGraph &CG, CGSCCUpdateResult &UR);
  
    void printPipeline(raw_ostream &OS,
                       function_ref<StringRef(StringRef)> MapClassName2PassName) {
      OS << "devirt<" << MaxIterations << ">(";
      Pass->printPipeline(OS, MapClassName2PassName);
      OS << ")";
    }
  
  private:
    std::unique_ptr<PassConceptT> Pass;
    int MaxIterations;
  };
  
  /// A function to deduce a function pass type and wrap it in the
  /// templated adaptor.
  template <typename CGSCCPassT>
  DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT &&Pass,
                                                    int MaxIterations) {
    using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
                                         PreservedAnalyses, CGSCCAnalysisManager,
                                         LazyCallGraph &, CGSCCUpdateResult &>;
    // Do not use make_unique, it causes too many template instantiations,
    // causing terrible compile times.
    return DevirtSCCRepeatedPass(
        std::unique_ptr<DevirtSCCRepeatedPass::PassConceptT>(
            new PassModelT(std::forward<CGSCCPassT>(Pass))),
        MaxIterations);
  }
  
  // Clear out the debug logging macro.
  #undef DEBUG_TYPE
  
  } // end namespace llvm
  
  #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  