Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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 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