| //===- 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 influence 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/DenseMap.h" |
| #include "llvm/ADT/DenseSet.h" |
| #include "llvm/ADT/PriorityWorklist.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Analysis/LazyCallGraph.h" |
| #include "llvm/IR/CallSite.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/InstIterator.h" |
| #include "llvm/IR/PassManager.h" |
| #include "llvm/IR/ValueHandle.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <utility> |
| |
| namespace llvm { |
| |
| 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(); |
| } |
| }; |
| |
| /// 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 infrsatructure. |
| /// |
| /// 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 an 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 an 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 `PassManeger` 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; |
| }; |
| |
| /// 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. |
| template <typename CGSCCPassT> |
| class ModuleToPostOrderCGSCCPassAdaptor |
| : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> { |
| public: |
| explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) |
| : Pass(std::move(Pass)) {} |
| |
| // We have to explicitly define all the special member functions because MSVC |
| // refuses to generate them. |
| ModuleToPostOrderCGSCCPassAdaptor( |
| const ModuleToPostOrderCGSCCPassAdaptor &Arg) |
| : Pass(Arg.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); |
| |
| private: |
| CGSCCPassT Pass; |
| }; |
| |
| /// A function to deduce a function pass type and wrap it in the |
| /// templated adaptor. |
| template <typename CGSCCPassT> |
| ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT> |
| createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) { |
| return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(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(FunctionAnalysisManager &FAM) : FAM(&FAM) {} |
| |
| /// Accessor for the analysis manager. |
| FunctionAnalysisManager &getManager() { 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); |
| |
| /// 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. |
| template <typename FunctionPassT> |
| class CGSCCToFunctionPassAdaptor |
| : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> { |
| public: |
| explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass) |
| : Pass(std::move(Pass)) {} |
| |
| // We have to explicitly define all the special member functions because MSVC |
| // refuses to generate them. |
| CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg) |
| : Pass(Arg.Pass) {} |
| |
| CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg) |
| : Pass(std::move(Arg.Pass)) {} |
| |
| 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) { |
| // Setup the function analysis manager from its proxy. |
| FunctionAnalysisManager &FAM = |
| AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager(); |
| |
| SmallVector<LazyCallGraph::Node *, 4> Nodes; |
| for (LazyCallGraph::Node &N : C) |
| Nodes.push_back(&N); |
| |
| // The SCC may get split while we are optimizing functions due to deleting |
| // edges. If this happens, the current SCC can shift, so keep track of |
| // a pointer we can overwrite. |
| LazyCallGraph::SCC *CurrentC = &C; |
| |
| LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C |
| << "\n"); |
| |
| PreservedAnalyses PA = PreservedAnalyses::all(); |
| for (LazyCallGraph::Node *N : Nodes) { |
| // Skip nodes from other SCCs. These may have been split out during |
| // processing. We'll eventually visit those SCCs and pick up the nodes |
| // there. |
| if (CG.lookupSCC(*N) != CurrentC) |
| continue; |
| |
| Function &F = N->getFunction(); |
| |
| PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F); |
| if (!PI.runBeforePass<Function>(Pass, F)) |
| continue; |
| |
| PreservedAnalyses PassPA = Pass.run(F, FAM); |
| |
| PI.runAfterPass<Function>(Pass, F); |
| |
| // We know that the function pass couldn't have invalidated any other |
| // function's analyses (that's the contract of a function pass), so |
| // directly handle the function analysis manager's invalidation here. |
| FAM.invalidate(F, PassPA); |
| |
| // Then intersect the preserved set so that invalidation of module |
| // analyses will eventually occur when the module pass completes. |
| PA.intersect(std::move(PassPA)); |
| |
| // If the call graph hasn't been preserved, update it based on this |
| // function pass. This may also update the current SCC to point to |
| // a smaller, more refined SCC. |
| auto PAC = PA.getChecker<LazyCallGraphAnalysis>(); |
| if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) { |
| CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N, |
| AM, UR); |
| assert( |
| CG.lookupSCC(*N) == CurrentC && |
| "Current SCC not updated to the SCC containing the current node!"); |
| } |
| } |
| |
| // By definition we preserve the proxy. And we preserve all analyses on |
| // Functions. This precludes *any* invalidation of function analyses by the |
| // proxy, but that's OK because we've taken care to invalidate analyses in |
| // the function analysis manager incrementally above. |
| PA.preserveSet<AllAnalysesOn<Function>>(); |
| PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); |
| |
| // We've also ensured that we updated the call graph along the way. |
| PA.preserve<LazyCallGraphAnalysis>(); |
| |
| return PA; |
| } |
| |
| private: |
| FunctionPassT Pass; |
| }; |
| |
| /// A function to deduce a function pass type and wrap it in the |
| /// templated adaptor. |
| template <typename FunctionPassT> |
| CGSCCToFunctionPassAdaptor<FunctionPassT> |
| createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) { |
| return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)); |
| } |
| |
| /// 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. |
| template <typename PassT> |
| class DevirtSCCRepeatedPass |
| : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> { |
| public: |
| explicit DevirtSCCRepeatedPass(PassT 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) { |
| PreservedAnalyses PA = PreservedAnalyses::all(); |
| PassInstrumentation PI = |
| AM.getResult<PassInstrumentationAnalysis>(InitialC, CG); |
| |
| // The SCC may be refined while we are running passes over it, so set up |
| // a pointer that we can update. |
| LazyCallGraph::SCC *C = &InitialC; |
| |
| // Collect value handles for all of the indirect call sites. |
| SmallVector<WeakTrackingVH, 8> CallHandles; |
| |
| // Struct to track the counts of direct and indirect calls in each function |
| // of the SCC. |
| struct CallCount { |
| int Direct; |
| int Indirect; |
| }; |
| |
| // Put value handles on all of the indirect calls and return the number of |
| // direct calls for each function in the SCC. |
| auto ScanSCC = [](LazyCallGraph::SCC &C, |
| SmallVectorImpl<WeakTrackingVH> &CallHandles) { |
| assert(CallHandles.empty() && "Must start with a clear set of handles."); |
| |
| SmallDenseMap<Function *, CallCount> CallCounts; |
| CallCount CountLocal = {0, 0}; |
| for (LazyCallGraph::Node &N : C) { |
| CallCount &Count = |
| CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal)) |
| .first->second; |
| for (Instruction &I : instructions(N.getFunction())) |
| if (auto CS = CallSite(&I)) { |
| if (CS.getCalledFunction()) { |
| ++Count.Direct; |
| } else { |
| ++Count.Indirect; |
| CallHandles.push_back(WeakTrackingVH(&I)); |
| } |
| } |
| } |
| |
| return CallCounts; |
| }; |
| |
| // Populate the initial call handles and get the initial call counts. |
| auto CallCounts = ScanSCC(*C, CallHandles); |
| |
| for (int Iteration = 0;; ++Iteration) { |
| |
| if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C)) |
| continue; |
| |
| PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR); |
| |
| if (UR.InvalidatedSCCs.count(C)) |
| PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass); |
| else |
| PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C); |
| |
| // If the SCC structure has changed, bail immediately and let the outer |
| // CGSCC layer handle any iteration to reflect the refined structure. |
| if (UR.UpdatedC && UR.UpdatedC != C) { |
| PA.intersect(std::move(PassPA)); |
| break; |
| } |
| |
| // Check that we didn't miss any update scenario. |
| assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!"); |
| assert(C->begin() != C->end() && "Cannot have an empty SCC!"); |
| |
| // Check whether any of the handles were devirtualized. |
| auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) { |
| if (!CallH) |
| return false; |
| auto CS = CallSite(CallH); |
| if (!CS) |
| return false; |
| |
| // If the call is still indirect, leave it alone. |
| Function *F = CS.getCalledFunction(); |
| if (!F) |
| return false; |
| |
| LLVM_DEBUG(dbgs() << "Found devirtualized call from " |
| << CS.getParent()->getParent()->getName() << " to " |
| << F->getName() << "\n"); |
| |
| // We now have a direct call where previously we had an indirect call, |
| // so iterate to process this devirtualization site. |
| return true; |
| }; |
| bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle); |
| |
| // Rescan to build up a new set of handles and count how many direct |
| // calls remain. If we decide to iterate, this also sets up the input to |
| // the next iteration. |
| CallHandles.clear(); |
| auto NewCallCounts = ScanSCC(*C, CallHandles); |
| |
| // If we haven't found an explicit devirtualization already see if we |
| // have decreased the number of indirect calls and increased the number |
| // of direct calls for any function in the SCC. This can be fooled by all |
| // manner of transformations such as DCE and other things, but seems to |
| // work well in practice. |
| if (!Devirt) |
| // Iterate over the keys in NewCallCounts, if Function also exists in |
| // CallCounts, make the check below. |
| for (auto &Pair : NewCallCounts) { |
| auto &CallCountNew = Pair.second; |
| auto CountIt = CallCounts.find(Pair.first); |
| if (CountIt != CallCounts.end()) { |
| const auto &CallCountOld = CountIt->second; |
| if (CallCountOld.Indirect > CallCountNew.Indirect && |
| CallCountOld.Direct < CallCountNew.Direct) { |
| Devirt = true; |
| break; |
| } |
| } |
| } |
| |
| if (!Devirt) { |
| PA.intersect(std::move(PassPA)); |
| break; |
| } |
| |
| // Otherwise, if we've already hit our max, we're done. |
| if (Iteration >= MaxIterations) { |
| LLVM_DEBUG( |
| dbgs() << "Found another devirtualization after hitting the max " |
| "number of repetitions (" |
| << MaxIterations << ") on SCC: " << *C << "\n"); |
| PA.intersect(std::move(PassPA)); |
| break; |
| } |
| |
| LLVM_DEBUG( |
| dbgs() |
| << "Repeating an SCC pass after finding a devirtualization in: " << *C |
| << "\n"); |
| |
| // Move over the new call counts in preparation for iterating. |
| CallCounts = std::move(NewCallCounts); |
| |
| // Update the analysis manager with each run and intersect the total set |
| // of preserved analyses so we're ready to iterate. |
| AM.invalidate(*C, PassPA); |
| PA.intersect(std::move(PassPA)); |
| } |
| |
| // Note that we don't add any preserved entries here unlike a more normal |
| // "pass manager" because we only handle invalidation *between* iterations, |
| // not after the last iteration. |
| return PA; |
| } |
| |
| private: |
| PassT Pass; |
| int MaxIterations; |
| }; |
| |
| /// A function to deduce a function pass type and wrap it in the |
| /// templated adaptor. |
| template <typename PassT> |
| DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass, |
| int MaxIterations) { |
| return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations); |
| } |
| |
| // Out-of-line implementation details for templates below this point. |
| |
| template <typename CGSCCPassT> |
| PreservedAnalyses |
| ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::run(Module &M, |
| ModuleAnalysisManager &AM) { |
| // Setup the CGSCC analysis manager from its proxy. |
| CGSCCAnalysisManager &CGAM = |
| AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager(); |
| |
| // Get the call graph for this module. |
| LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M); |
| |
| // We keep worklists to allow us to push more work onto the pass manager as |
| // the passes are run. |
| SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist; |
| SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist; |
| |
| // Keep sets for invalidated SCCs and RefSCCs that should be skipped when |
| // iterating off the worklists. |
| SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet; |
| SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet; |
| |
| SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4> |
| InlinedInternalEdges; |
| |
| CGSCCUpdateResult UR = { |
| RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet, |
| nullptr, nullptr, PreservedAnalyses::all(), InlinedInternalEdges}; |
| |
| // Request PassInstrumentation from analysis manager, will use it to run |
| // instrumenting callbacks for the passes later. |
| PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M); |
| |
| PreservedAnalyses PA = PreservedAnalyses::all(); |
| CG.buildRefSCCs(); |
| for (auto RCI = CG.postorder_ref_scc_begin(), |
| RCE = CG.postorder_ref_scc_end(); |
| RCI != RCE;) { |
| assert(RCWorklist.empty() && |
| "Should always start with an empty RefSCC worklist"); |
| // The postorder_ref_sccs range we are walking is lazily constructed, so |
| // we only push the first one onto the worklist. The worklist allows us |
| // to capture *new* RefSCCs created during transformations. |
| // |
| // We really want to form RefSCCs lazily because that makes them cheaper |
| // to update as the program is simplified and allows us to have greater |
| // cache locality as forming a RefSCC touches all the parts of all the |
| // functions within that RefSCC. |
| // |
| // We also eagerly increment the iterator to the next position because |
| // the CGSCC passes below may delete the current RefSCC. |
| RCWorklist.insert(&*RCI++); |
| |
| do { |
| LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val(); |
| if (InvalidRefSCCSet.count(RC)) { |
| LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n"); |
| continue; |
| } |
| |
| assert(CWorklist.empty() && |
| "Should always start with an empty SCC worklist"); |
| |
| LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC |
| << "\n"); |
| |
| // Push the initial SCCs in reverse post-order as we'll pop off the |
| // back and so see this in post-order. |
| for (LazyCallGraph::SCC &C : llvm::reverse(*RC)) |
| CWorklist.insert(&C); |
| |
| do { |
| LazyCallGraph::SCC *C = CWorklist.pop_back_val(); |
| // Due to call graph mutations, we may have invalid SCCs or SCCs from |
| // other RefSCCs in the worklist. The invalid ones are dead and the |
| // other RefSCCs should be queued above, so we just need to skip both |
| // scenarios here. |
| if (InvalidSCCSet.count(C)) { |
| LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n"); |
| continue; |
| } |
| if (&C->getOuterRefSCC() != RC) { |
| LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other " |
| "RefSCC...\n"); |
| continue; |
| } |
| |
| // Ensure we can proxy analysis updates from from the CGSCC analysis |
| // manager into the Function analysis manager by getting a proxy here. |
| // FIXME: This seems like a bit of a hack. We should find a cleaner |
| // or more costructive way to ensure this happens. |
| (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG); |
| |
| // Each time we visit a new SCC pulled off the worklist, |
| // a transformation of a child SCC may have also modified this parent |
| // and invalidated analyses. So we invalidate using the update record's |
| // cross-SCC preserved set. This preserved set is intersected by any |
| // CGSCC pass that handles invalidation (primarily pass managers) prior |
| // to marking its SCC as preserved. That lets us track everything that |
| // might need invalidation across SCCs without excessive invalidations |
| // on a single SCC. |
| // |
| // This essentially allows SCC passes to freely invalidate analyses |
| // of any ancestor SCC. If this becomes detrimental to successfully |
| // caching analyses, we could force each SCC pass to manually |
| // invalidate the analyses for any SCCs other than themselves which |
| // are mutated. However, that seems to lose the robustness of the |
| // pass-manager driven invalidation scheme. |
| // |
| // FIXME: This is redundant in one case -- the top of the worklist may |
| // *also* be the same SCC we just ran over (and invalidated for). In |
| // that case, we'll end up doing a redundant invalidation here as |
| // a consequence. |
| CGAM.invalidate(*C, UR.CrossSCCPA); |
| |
| do { |
| // Check that we didn't miss any update scenario. |
| assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!"); |
| assert(C->begin() != C->end() && "Cannot have an empty SCC!"); |
| assert(&C->getOuterRefSCC() == RC && |
| "Processing an SCC in a different RefSCC!"); |
| |
| UR.UpdatedRC = nullptr; |
| UR.UpdatedC = nullptr; |
| |
| // Check the PassInstrumentation's BeforePass callbacks before |
| // running the pass, skip its execution completely if asked to |
| // (callback returns false). |
| if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C)) |
| continue; |
| |
| PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR); |
| |
| if (UR.InvalidatedSCCs.count(C)) |
| PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass); |
| else |
| PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C); |
| |
| // Update the SCC and RefSCC if necessary. |
| C = UR.UpdatedC ? UR.UpdatedC : C; |
| RC = UR.UpdatedRC ? UR.UpdatedRC : RC; |
| |
| // If the CGSCC pass wasn't able to provide a valid updated SCC, |
| // the current SCC may simply need to be skipped if invalid. |
| if (UR.InvalidatedSCCs.count(C)) { |
| LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n"); |
| break; |
| } |
| // Check that we didn't miss any update scenario. |
| assert(C->begin() != C->end() && "Cannot have an empty SCC!"); |
| |
| // We handle invalidating the CGSCC analysis manager's information |
| // for the (potentially updated) SCC here. Note that any other SCCs |
| // whose structure has changed should have been invalidated by |
| // whatever was updating the call graph. This SCC gets invalidated |
| // late as it contains the nodes that were actively being |
| // processed. |
| CGAM.invalidate(*C, PassPA); |
| |
| // Then intersect the preserved set so that invalidation of module |
| // analyses will eventually occur when the module pass completes. |
| // Also intersect with the cross-SCC preserved set to capture any |
| // cross-SCC invalidation. |
| UR.CrossSCCPA.intersect(PassPA); |
| PA.intersect(std::move(PassPA)); |
| |
| // The pass may have restructured the call graph and refined the |
| // current SCC and/or RefSCC. We need to update our current SCC and |
| // RefSCC pointers to follow these. Also, when the current SCC is |
| // refined, re-run the SCC pass over the newly refined SCC in order |
| // to observe the most precise SCC model available. This inherently |
| // cannot cycle excessively as it only happens when we split SCCs |
| // apart, at most converging on a DAG of single nodes. |
| // FIXME: If we ever start having RefSCC passes, we'll want to |
| // iterate there too. |
| if (UR.UpdatedC) |
| LLVM_DEBUG(dbgs() |
| << "Re-running SCC passes after a refinement of the " |
| "current SCC: " |
| << *UR.UpdatedC << "\n"); |
| |
| // Note that both `C` and `RC` may at this point refer to deleted, |
| // invalid SCC and RefSCCs respectively. But we will short circuit |
| // the processing when we check them in the loop above. |
| } while (UR.UpdatedC); |
| } while (!CWorklist.empty()); |
| |
| // We only need to keep internal inlined edge information within |
| // a RefSCC, clear it to save on space and let the next time we visit |
| // any of these functions have a fresh start. |
| InlinedInternalEdges.clear(); |
| } while (!RCWorklist.empty()); |
| } |
| |
| // By definition we preserve the call garph, all SCC analyses, and the |
| // analysis proxies by handling them above and in any nested pass managers. |
| PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>(); |
| PA.preserve<LazyCallGraphAnalysis>(); |
| PA.preserve<CGSCCAnalysisManagerModuleProxy>(); |
| PA.preserve<FunctionAnalysisManagerModuleProxy>(); |
| return PA; |
| } |
| |
| // Clear out the debug logging macro. |
| #undef DEBUG_TYPE |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H |