diff options
Diffstat (limited to 'include/llvm/Analysis/CGSCCPassManager.h')
| -rw-r--r-- | include/llvm/Analysis/CGSCCPassManager.h | 591 |
1 files changed, 591 insertions, 0 deletions
diff --git a/include/llvm/Analysis/CGSCCPassManager.h b/include/llvm/Analysis/CGSCCPassManager.h new file mode 100644 index 0000000000..618fee153c --- /dev/null +++ b/include/llvm/Analysis/CGSCCPassManager.h @@ -0,0 +1,591 @@ +//===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \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 +/// wtraverse the graph in post order, they can effectively do pair-wise +/// interprocedural optimizations for all call edges in the program. 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. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CGSCC_PASS_MANAGER_H +#define LLVM_ANALYSIS_CGSCC_PASS_MANAGER_H + +#include "llvm/IR/PassManager.h" +#include "llvm/Analysis/LazyCallGraph.h" + +namespace llvm { + +class CGSCCAnalysisManager; + +class CGSCCPassManager { +public: + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + CGSCCPassManager() {} + CGSCCPassManager(CGSCCPassManager &&Arg) : Passes(std::move(Arg.Passes)) {} + CGSCCPassManager &operator=(CGSCCPassManager &&RHS) { + Passes = std::move(RHS.Passes); + return *this; + } + + /// \brief Run all of the CGSCC passes in this pass manager over a SCC. + PreservedAnalyses run(LazyCallGraph::SCC *C, + CGSCCAnalysisManager *AM = nullptr); + + template <typename CGSCCPassT> void addPass(CGSCCPassT Pass) { + Passes.emplace_back(new CGSCCPassModel<CGSCCPassT>(std::move(Pass))); + } + + static StringRef name() { return "CGSCCPassManager"; } + +private: + // Pull in the concept type and model template specialized for SCCs. + typedef detail::PassConcept<LazyCallGraph::SCC *, CGSCCAnalysisManager> + CGSCCPassConcept; + template <typename PassT> + struct CGSCCPassModel + : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT> { + CGSCCPassModel(PassT Pass) + : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT>( + std::move(Pass)) {} + }; + + CGSCCPassManager(const CGSCCPassManager &) LLVM_DELETED_FUNCTION; + CGSCCPassManager &operator=(const CGSCCPassManager &) LLVM_DELETED_FUNCTION; + + std::vector<std::unique_ptr<CGSCCPassConcept>> Passes; +}; + +/// \brief A function analysis manager to coordinate and cache analyses run over +/// a module. +class CGSCCAnalysisManager : public detail::AnalysisManagerBase< + CGSCCAnalysisManager, LazyCallGraph::SCC *> { + friend class detail::AnalysisManagerBase<CGSCCAnalysisManager, + LazyCallGraph::SCC *>; + typedef detail::AnalysisManagerBase<CGSCCAnalysisManager, + LazyCallGraph::SCC *> BaseT; + typedef BaseT::ResultConceptT ResultConceptT; + typedef BaseT::PassConceptT PassConceptT; + +public: + // Most public APIs are inherited from the CRTP base class. + + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + CGSCCAnalysisManager() {} + CGSCCAnalysisManager(CGSCCAnalysisManager &&Arg) + : BaseT(std::move(static_cast<BaseT &>(Arg))), + CGSCCAnalysisResults(std::move(Arg.CGSCCAnalysisResults)) {} + CGSCCAnalysisManager &operator=(CGSCCAnalysisManager &&RHS) { + BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); + CGSCCAnalysisResults = std::move(RHS.CGSCCAnalysisResults); + return *this; + } + + /// \brief Returns true if the analysis manager has an empty results cache. + bool empty() const; + + /// \brief Clear the function analysis result cache. + /// + /// This routine allows cleaning up when the set of functions itself has + /// potentially changed, and thus we can't even look up a a result and + /// invalidate it directly. Notably, this does *not* call invalidate + /// functions as there is nothing to be done for them. + void clear(); + +private: + CGSCCAnalysisManager(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION; + CGSCCAnalysisManager & + operator=(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION; + + /// \brief Get a function pass result, running the pass if necessary. + ResultConceptT &getResultImpl(void *PassID, LazyCallGraph::SCC *C); + + /// \brief Get a cached function pass result or return null. + ResultConceptT *getCachedResultImpl(void *PassID, + LazyCallGraph::SCC *C) const; + + /// \brief Invalidate a function pass result. + void invalidateImpl(void *PassID, LazyCallGraph::SCC *C); + + /// \brief Invalidate the results for a function.. + void invalidateImpl(LazyCallGraph::SCC *C, const PreservedAnalyses &PA); + + /// \brief List of function analysis pass IDs and associated concept pointers. + /// + /// Requires iterators to be valid across appending new entries and arbitrary + /// erases. Provides both the pass ID and concept pointer such that it is + /// half of a bijection and provides storage for the actual result concept. + typedef std::list< + std::pair<void *, std::unique_ptr<detail::AnalysisResultConcept< + LazyCallGraph::SCC *>>>> CGSCCAnalysisResultListT; + + /// \brief Map type from function pointer to our custom list type. + typedef DenseMap<LazyCallGraph::SCC *, CGSCCAnalysisResultListT> + CGSCCAnalysisResultListMapT; + + /// \brief Map from function to a list of function analysis results. + /// + /// Provides linear time removal of all analysis results for a function and + /// the ultimate storage for a particular cached analysis result. + CGSCCAnalysisResultListMapT CGSCCAnalysisResultLists; + + /// \brief Map type from a pair of analysis ID and function pointer to an + /// iterator into a particular result list. + typedef DenseMap<std::pair<void *, LazyCallGraph::SCC *>, + CGSCCAnalysisResultListT::iterator> CGSCCAnalysisResultMapT; + + /// \brief Map from an analysis ID and function to a particular cached + /// analysis result. + CGSCCAnalysisResultMapT CGSCCAnalysisResults; +}; + +/// \brief A module analysis which acts as a proxy for a CGSCC analysis +/// manager. +/// +/// This primarily proxies invalidation information from the module analysis +/// manager and module pass manager to a CGSCC analysis manager. You should +/// never use a CGSCC analysis manager from within (transitively) a module +/// pass manager unless your parent module pass has received a proxy result +/// object for it. +class CGSCCAnalysisManagerModuleProxy { +public: + class Result { + public: + explicit Result(CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {} + // We have to explicitly define all the special member functions because + // MSVC refuses to generate them. + Result(const Result &Arg) : CGAM(Arg.CGAM) {} + Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {} + Result &operator=(Result RHS) { + std::swap(CGAM, RHS.CGAM); + return *this; + } + ~Result(); + + /// \brief Accessor for the \c CGSCCAnalysisManager. + CGSCCAnalysisManager &getManager() { return *CGAM; } + + /// \brief Handler for invalidation of the module. + /// + /// If this analysis itself is preserved, then we assume that the call + /// graph of the module hasn't changed and thus we don't need to invalidate + /// *all* cached data associated with a \c SCC* in the \c + /// 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); + + private: + CGSCCAnalysisManager *CGAM; + }; + + static void *ID() { return (void *)&PassID; } + + explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM) + : CGAM(&CGAM) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + CGSCCAnalysisManagerModuleProxy( + const CGSCCAnalysisManagerModuleProxy &Arg) + : CGAM(Arg.CGAM) {} + CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg) + : CGAM(std::move(Arg.CGAM)) {} + CGSCCAnalysisManagerModuleProxy & + operator=(CGSCCAnalysisManagerModuleProxy RHS) { + std::swap(CGAM, RHS.CGAM); + return *this; + } + + /// \brief Run the analysis pass and create our proxy result object. + /// + /// This doesn't do any interesting work, it is primarily used to insert our + /// proxy result object into the module analysis cache so that we can proxy + /// invalidation to the CGSCC analysis manager. + /// + /// In debug builds, it will also assert that the analysis manager is empty + /// as no queries should arrive at the CGSCC analysis manager prior to + /// this analysis being requested. + Result run(Module *M); + +private: + static char PassID; + + CGSCCAnalysisManager *CGAM; +}; + +/// \brief A CGSCC analysis which acts as a proxy for a module analysis +/// manager. +/// +/// This primarily provides an accessor to a parent module analysis manager to +/// CGSCC passes. Only the const interface of the module analysis manager is +/// provided to indicate that once inside of a CGSCC analysis pass you +/// cannot request a module analysis to actually run. Instead, the user must +/// rely on the \c getCachedResult API. +/// +/// This proxy *doesn't* manage the invalidation in any way. That is handled by +/// the recursive return path of each layer of the pass manager and the +/// returned PreservedAnalysis set. +class ModuleAnalysisManagerCGSCCProxy { +public: + /// \brief Result proxy object for \c ModuleAnalysisManagerCGSCCProxy. + class Result { + public: + explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {} + // We have to explicitly define all the special member functions because + // MSVC refuses to generate them. + Result(const Result &Arg) : MAM(Arg.MAM) {} + Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {} + Result &operator=(Result RHS) { + std::swap(MAM, RHS.MAM); + return *this; + } + + const ModuleAnalysisManager &getManager() const { return *MAM; } + + /// \brief Handle invalidation by ignoring it, this pass is immutable. + bool invalidate(LazyCallGraph::SCC *) { return false; } + + private: + const ModuleAnalysisManager *MAM; + }; + + static void *ID() { return (void *)&PassID; } + + ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM) + : MAM(&MAM) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + ModuleAnalysisManagerCGSCCProxy( + const ModuleAnalysisManagerCGSCCProxy &Arg) + : MAM(Arg.MAM) {} + ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg) + : MAM(std::move(Arg.MAM)) {} + ModuleAnalysisManagerCGSCCProxy & + operator=(ModuleAnalysisManagerCGSCCProxy RHS) { + std::swap(MAM, RHS.MAM); + return *this; + } + + /// \brief Run the analysis pass and create our proxy result object. + /// Nothing to see here, it just forwards the \c MAM reference into the + /// result. + Result run(LazyCallGraph::SCC *) { return Result(*MAM); } + +private: + static char PassID; + + const ModuleAnalysisManager *MAM; +}; + +/// \brief 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: + 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) { + using std::swap; + swap(LHS.Pass, RHS.Pass); + } + ModuleToPostOrderCGSCCPassAdaptor & + operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) { + swap(*this, RHS); + return *this; + } + + /// \brief Runs the CGSCC pass across every SCC in the module. + PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) { + assert(AM && "We need analyses to compute the call graph!"); + + // 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); + + PreservedAnalyses PA = PreservedAnalyses::all(); + for (LazyCallGraph::SCC *C : CG.postorder_sccs()) { + PreservedAnalyses PassPA = Pass.run(C, &CGAM); + + // We know that the CGSCC pass couldn't have invalidated any other + // SCC's analyses (that's the contract of a CGSCC pass), so + // directly handle the CGSCC analysis manager's invalidation here. + // FIXME: This isn't quite correct. We need to handle the case where the + // pass updated the CG, particularly some child of the current SCC, and + // invalidate its analyses. + CGAM.invalidate(C, 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)); + } + + // By definition we preserve the proxy. This precludes *any* invalidation + // of CGSCC analyses by the proxy, but that's OK because we've taken + // care to invalidate analyses in the CGSCC analysis manager + // incrementally above. + PA.preserve<CGSCCAnalysisManagerModuleProxy>(); + return PA; + } + + static StringRef name() { return "ModuleToPostOrderCGSCCPassAdaptor"; } + +private: + CGSCCPassT Pass; +}; + +/// \brief A function to deduce a function pass type and wrap it in the +/// templated adaptor. +template <typename CGSCCPassT> +ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT> +createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) { + return std::move( + ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass))); +} + +/// \brief A CGSCC analysis which acts as a proxy for a function analysis +/// manager. +/// +/// This primarily proxies invalidation information from the CGSCC analysis +/// manager and CGSCC pass manager to a function analysis manager. You should +/// never use a function analysis manager from within (transitively) a CGSCC +/// pass manager unless your parent CGSCC pass has received a proxy result +/// object for it. +class FunctionAnalysisManagerCGSCCProxy { +public: + class Result { + public: + explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {} + // We have to explicitly define all the special member functions because + // MSVC refuses to generate them. + Result(const Result &Arg) : FAM(Arg.FAM) {} + Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {} + Result &operator=(Result RHS) { + std::swap(FAM, RHS.FAM); + return *this; + } + ~Result(); + + /// \brief Accessor for the \c FunctionAnalysisManager. + FunctionAnalysisManager &getManager() { return *FAM; } + + /// \brief Handler for invalidation of the SCC. + /// + /// If this analysis itself is preserved, then we assume that the set of \c + /// Function objects in the \c SCC hasn't changed and thus we don't need + /// to invalidate *all* cached data associated with a \c Function* in the \c + /// FunctionAnalysisManager. + /// + /// Regardless of whether this analysis is marked as preserved, all of the + /// analyses in the \c FunctionAnalysisManager are potentially invalidated + /// based on the set of preserved analyses. + bool invalidate(LazyCallGraph::SCC *C, const PreservedAnalyses &PA); + + private: + FunctionAnalysisManager *FAM; + }; + + static void *ID() { return (void *)&PassID; } + + explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM) + : FAM(&FAM) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + FunctionAnalysisManagerCGSCCProxy( + const FunctionAnalysisManagerCGSCCProxy &Arg) + : FAM(Arg.FAM) {} + FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManagerCGSCCProxy &&Arg) + : FAM(std::move(Arg.FAM)) {} + FunctionAnalysisManagerCGSCCProxy & + operator=(FunctionAnalysisManagerCGSCCProxy RHS) { + std::swap(FAM, RHS.FAM); + return *this; + } + + /// \brief Run the analysis pass and create our proxy result object. + /// + /// This doesn't do any interesting work, it is primarily used to insert our + /// proxy result object into the module analysis cache so that we can proxy + /// invalidation to the function analysis manager. + /// + /// In debug builds, it will also assert that the analysis manager is empty + /// as no queries should arrive at the function analysis manager prior to + /// this analysis being requested. + Result run(LazyCallGraph::SCC *C); + +private: + static char PassID; + + FunctionAnalysisManager *FAM; +}; + +/// \brief A function analysis which acts as a proxy for a CGSCC analysis +/// manager. +/// +/// This primarily provides an accessor to a parent CGSCC analysis manager to +/// function passes. Only the const interface of the CGSCC analysis manager is +/// provided to indicate that once inside of a function analysis pass you +/// cannot request a CGSCC analysis to actually run. Instead, the user must +/// rely on the \c getCachedResult API. +/// +/// This proxy *doesn't* manage the invalidation in any way. That is handled by +/// the recursive return path of each layer of the pass manager and the +/// returned PreservedAnalysis set. +class CGSCCAnalysisManagerFunctionProxy { +public: + /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy. + class Result { + public: + explicit Result(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {} + // We have to explicitly define all the special member functions because + // MSVC refuses to generate them. + Result(const Result &Arg) : CGAM(Arg.CGAM) {} + Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {} + Result &operator=(Result RHS) { + std::swap(CGAM, RHS.CGAM); + return *this; + } + + const CGSCCAnalysisManager &getManager() const { return *CGAM; } + + /// \brief Handle invalidation by ignoring it, this pass is immutable. + bool invalidate(Function *) { return false; } + + private: + const CGSCCAnalysisManager *CGAM; + }; + + static void *ID() { return (void *)&PassID; } + + CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM) + : CGAM(&CGAM) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + CGSCCAnalysisManagerFunctionProxy( + const CGSCCAnalysisManagerFunctionProxy &Arg) + : CGAM(Arg.CGAM) {} + CGSCCAnalysisManagerFunctionProxy(CGSCCAnalysisManagerFunctionProxy &&Arg) + : CGAM(std::move(Arg.CGAM)) {} + CGSCCAnalysisManagerFunctionProxy & + operator=(CGSCCAnalysisManagerFunctionProxy RHS) { + std::swap(CGAM, RHS.CGAM); + return *this; + } + + /// \brief Run the analysis pass and create our proxy result object. + /// Nothing to see here, it just forwards the \c CGAM reference into the + /// result. + Result run(Function *) { return Result(*CGAM); } + +private: + static char PassID; + + const CGSCCAnalysisManager *CGAM; +}; + +/// \brief 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: + 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) { + using std::swap; + swap(LHS.Pass, RHS.Pass); + } + CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) { + swap(*this, RHS); + return *this; + } + + /// \brief Runs the function pass across every function in the module. + PreservedAnalyses run(LazyCallGraph::SCC *C, CGSCCAnalysisManager *AM) { + FunctionAnalysisManager *FAM = nullptr; + if (AM) + // Setup the function analysis manager from its proxy. + FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); + + PreservedAnalyses PA = PreservedAnalyses::all(); + for (LazyCallGraph::Node *N : *C) { + PreservedAnalyses PassPA = Pass.run(&N->getFunction(), FAM); + + // 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. + if (FAM) + FAM->invalidate(&N->getFunction(), 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)); + } + + // By definition we preserve the proxy. 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. + // FIXME: We need to update the call graph here to account for any deleted + // edges! + PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); + return PA; + } + + static StringRef name() { return "CGSCCToFunctionPassAdaptor"; } + +private: + FunctionPassT Pass; +}; + +/// \brief A function to deduce a function pass type and wrap it in the +/// templated adaptor. +template <typename FunctionPassT> +CGSCCToFunctionPassAdaptor<FunctionPassT> +createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) { + return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass))); +} + +} + +#endif |