diff options
-rw-r--r-- | include/llvm/Analysis/CGSCCPassManager.h | 591 | ||||
-rw-r--r-- | lib/Analysis/CGSCCPassManager.cpp | 167 | ||||
-rw-r--r-- | lib/Analysis/CMakeLists.txt | 1 | ||||
-rw-r--r-- | test/Other/pass-pipeline-parsing.ll | 36 | ||||
-rw-r--r-- | tools/opt/NewPMDriver.cpp | 10 | ||||
-rw-r--r-- | tools/opt/PassRegistry.def | 10 | ||||
-rw-r--r-- | tools/opt/Passes.cpp | 114 |
7 files changed, 929 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 diff --git a/lib/Analysis/CGSCCPassManager.cpp b/lib/Analysis/CGSCCPassManager.cpp new file mode 100644 index 0000000000..5d1d8a9c6e --- /dev/null +++ b/lib/Analysis/CGSCCPassManager.cpp @@ -0,0 +1,167 @@ +//===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +static cl::opt<bool> +DebugPM("debug-cgscc-pass-manager", cl::Hidden, + cl::desc("Print CGSCC pass management debugging information")); + +PreservedAnalyses CGSCCPassManager::run(LazyCallGraph::SCC *C, + CGSCCAnalysisManager *AM) { + PreservedAnalyses PA = PreservedAnalyses::all(); + + if (DebugPM) + dbgs() << "Starting CGSCC pass manager run.\n"; + + for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) { + if (DebugPM) + dbgs() << "Running CGSCC pass: " << Passes[Idx]->name() << "\n"; + + PreservedAnalyses PassPA = Passes[Idx]->run(C, AM); + if (AM) + AM->invalidate(C, PassPA); + PA.intersect(std::move(PassPA)); + } + + if (DebugPM) + dbgs() << "Finished CGSCC pass manager run.\n"; + + return PA; +} + +bool CGSCCAnalysisManager::empty() const { + assert(CGSCCAnalysisResults.empty() == CGSCCAnalysisResultLists.empty() && + "The storage and index of analysis results disagree on how many there " + "are!"); + return CGSCCAnalysisResults.empty(); +} + +void CGSCCAnalysisManager::clear() { + CGSCCAnalysisResults.clear(); + CGSCCAnalysisResultLists.clear(); +} + +CGSCCAnalysisManager::ResultConceptT & +CGSCCAnalysisManager::getResultImpl(void *PassID, LazyCallGraph::SCC *C) { + CGSCCAnalysisResultMapT::iterator RI; + bool Inserted; + std::tie(RI, Inserted) = CGSCCAnalysisResults.insert(std::make_pair( + std::make_pair(PassID, C), CGSCCAnalysisResultListT::iterator())); + + // If we don't have a cached result for this function, look up the pass and + // run it to produce a result, which we then add to the cache. + if (Inserted) { + CGSCCAnalysisResultListT &ResultList = CGSCCAnalysisResultLists[C]; + ResultList.emplace_back(PassID, lookupPass(PassID).run(C, this)); + RI->second = std::prev(ResultList.end()); + } + + return *RI->second->second; +} + +CGSCCAnalysisManager::ResultConceptT * +CGSCCAnalysisManager::getCachedResultImpl(void *PassID, + LazyCallGraph::SCC *C) const { + CGSCCAnalysisResultMapT::const_iterator RI = + CGSCCAnalysisResults.find(std::make_pair(PassID, C)); + return RI == CGSCCAnalysisResults.end() ? nullptr : &*RI->second->second; +} + +void CGSCCAnalysisManager::invalidateImpl(void *PassID, LazyCallGraph::SCC *C) { + CGSCCAnalysisResultMapT::iterator RI = + CGSCCAnalysisResults.find(std::make_pair(PassID, C)); + if (RI == CGSCCAnalysisResults.end()) + return; + + CGSCCAnalysisResultLists[C].erase(RI->second); +} + +void CGSCCAnalysisManager::invalidateImpl(LazyCallGraph::SCC *C, + const PreservedAnalyses &PA) { + // Clear all the invalidated results associated specifically with this + // function. + SmallVector<void *, 8> InvalidatedPassIDs; + CGSCCAnalysisResultListT &ResultsList = CGSCCAnalysisResultLists[C]; + for (CGSCCAnalysisResultListT::iterator I = ResultsList.begin(), + E = ResultsList.end(); + I != E;) + if (I->second->invalidate(C, PA)) { + InvalidatedPassIDs.push_back(I->first); + I = ResultsList.erase(I); + } else { + ++I; + } + while (!InvalidatedPassIDs.empty()) + CGSCCAnalysisResults.erase( + std::make_pair(InvalidatedPassIDs.pop_back_val(), C)); + CGSCCAnalysisResultLists.erase(C); +} + +char CGSCCAnalysisManagerModuleProxy::PassID; + +CGSCCAnalysisManagerModuleProxy::Result +CGSCCAnalysisManagerModuleProxy::run(Module *M) { + assert(CGAM->empty() && "CGSCC analyses ran prior to the module proxy!"); + return Result(*CGAM); +} + +CGSCCAnalysisManagerModuleProxy::Result::~Result() { + // Clear out the analysis manager if we're being destroyed -- it means we + // didn't even see an invalidate call when we got invalidated. + CGAM->clear(); +} + +bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( + Module *M, const PreservedAnalyses &PA) { + // If this proxy isn't marked as preserved, then we can't even invalidate + // individual CGSCC analyses, there may be an invalid set of SCC objects in + // the cache making it impossible to incrementally preserve them. + // Just clear the entire manager. + if (!PA.preserved(ID())) + CGAM->clear(); + + // Return false to indicate that this result is still a valid proxy. + return false; +} + +char ModuleAnalysisManagerCGSCCProxy::PassID; + +char FunctionAnalysisManagerCGSCCProxy::PassID; + +FunctionAnalysisManagerCGSCCProxy::Result +FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC *C) { + assert(FAM->empty() && "Function analyses ran prior to the CGSCC proxy!"); + return Result(*FAM); +} + +FunctionAnalysisManagerCGSCCProxy::Result::~Result() { + // Clear out the analysis manager if we're being destroyed -- it means we + // didn't even see an invalidate call when we got invalidated. + FAM->clear(); +} + +bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate( + LazyCallGraph::SCC *C, const PreservedAnalyses &PA) { + // If this proxy isn't marked as preserved, then we can't even invalidate + // individual function analyses, there may be an invalid set of Function + // objects in the cache making it impossible to incrementally preserve them. + // Just clear the entire manager. + if (!PA.preserved(ID())) + FAM->clear(); + + // Return false to indicate that this result is still a valid proxy. + return false; +} + +char CGSCCAnalysisManagerFunctionProxy::PassID; diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index c6d4573885..7c38be149b 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -10,6 +10,7 @@ add_llvm_library(LLVMAnalysis BranchProbabilityInfo.cpp CFG.cpp CFGPrinter.cpp + CGSCCPassManager.cpp CaptureTracking.cpp CostModel.cpp CodeMetrics.cpp diff --git a/test/Other/pass-pipeline-parsing.ll b/test/Other/pass-pipeline-parsing.ll index ba336108c9..4ec4162cd4 100644 --- a/test/Other/pass-pipeline-parsing.ll +++ b/test/Other/pass-pipeline-parsing.ll @@ -105,6 +105,42 @@ ; RUN: | FileCheck %s --check-prefix=CHECK-UNBALANCED10 ; CHECK-UNBALANCED10: unable to parse pass pipeline description +; RUN: opt -disable-output -debug-pass-manager -debug-cgscc-pass-manager \ +; RUN: -passes=no-op-cgscc,no-op-cgscc %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-TWO-NOOP-CG +; CHECK-TWO-NOOP-CG: Starting module pass manager +; CHECK-TWO-NOOP-CG: Running module pass: ModuleToPostOrderCGSCCPassAdaptor +; CHECK-TWO-NOOP-CG: Starting CGSCC pass manager +; CHECK-TWO-NOOP-CG: Running CGSCC pass: NoOpCGSCCPass +; CHECK-TWO-NOOP-CG: Running CGSCC pass: NoOpCGSCCPass +; CHECK-TWO-NOOP-CG: Finished CGSCC pass manager +; CHECK-TWO-NOOP-CG: Finished module pass manager + +; RUN: opt -disable-output -debug-pass-manager -debug-cgscc-pass-manager \ +; RUN: -passes='module(function(no-op-function),cgscc(no-op-cgscc,function(no-op-function),no-op-cgscc),function(no-op-function))' %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-NESTED-MP-CG-FP +; CHECK-NESTED-MP-CG-FP: Starting module pass manager +; CHECK-NESTED-MP-CG-FP: Starting module pass manager +; CHECK-NESTED-MP-CG-FP: Running module pass: ModuleToFunctionPassAdaptor +; CHECK-NESTED-MP-CG-FP: Starting function pass manager +; CHECK-NESTED-MP-CG-FP: Running function pass: NoOpFunctionPass +; CHECK-NESTED-MP-CG-FP: Finished function pass manager +; CHECK-NESTED-MP-CG-FP: Running module pass: ModuleToPostOrderCGSCCPassAdaptor +; CHECK-NESTED-MP-CG-FP: Starting CGSCC pass manager +; CHECK-NESTED-MP-CG-FP: Running CGSCC pass: NoOpCGSCCPass +; CHECK-NESTED-MP-CG-FP: Running CGSCC pass: CGSCCToFunctionPassAdaptor +; CHECK-NESTED-MP-CG-FP: Starting function pass manager +; CHECK-NESTED-MP-CG-FP: Running function pass: NoOpFunctionPass +; CHECK-NESTED-MP-CG-FP: Finished function pass manager +; CHECK-NESTED-MP-CG-FP: Running CGSCC pass: NoOpCGSCCPass +; CHECK-NESTED-MP-CG-FP: Finished CGSCC pass manager +; CHECK-NESTED-MP-CG-FP: Running module pass: ModuleToFunctionPassAdaptor +; CHECK-NESTED-MP-CG-FP: Starting function pass manager +; CHECK-NESTED-MP-CG-FP: Running function pass: NoOpFunctionPass +; CHECK-NESTED-MP-CG-FP: Finished function pass manager +; CHECK-NESTED-MP-CG-FP: Finished module pass manager +; CHECK-NESTED-MP-CG-FP: Finished module pass manager + define void @f() { ret void } diff --git a/tools/opt/NewPMDriver.cpp b/tools/opt/NewPMDriver.cpp index 39a6579356..8076ff4487 100644 --- a/tools/opt/NewPMDriver.cpp +++ b/tools/opt/NewPMDriver.cpp @@ -16,6 +16,7 @@ #include "NewPMDriver.h" #include "Passes.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Bitcode/BitcodeWriterPass.h" #include "llvm/IR/IRPrintingPasses.h" @@ -34,18 +35,27 @@ bool llvm::runPassPipeline(StringRef Arg0, LLVMContext &Context, Module &M, tool_output_file *Out, StringRef PassPipeline, OutputKind OK, VerifierKind VK) { FunctionAnalysisManager FAM; + CGSCCAnalysisManager CGAM; ModuleAnalysisManager MAM; #define MODULE_ANALYSIS(NAME, CREATE_PASS) \ MAM.registerPass(CREATE_PASS); #include "PassRegistry.def" +#define CGSCC_ANALYSIS(NAME, CREATE_PASS) \ + CGAM.registerPass(CREATE_PASS); +#include "PassRegistry.def" + #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \ FAM.registerPass(CREATE_PASS); #include "PassRegistry.def" // Cross register the analysis managers through their proxies. MAM.registerPass(FunctionAnalysisManagerModuleProxy(FAM)); + MAM.registerPass(CGSCCAnalysisManagerModuleProxy(CGAM)); + CGAM.registerPass(FunctionAnalysisManagerCGSCCProxy(FAM)); + CGAM.registerPass(ModuleAnalysisManagerCGSCCProxy(MAM)); + FAM.registerPass(CGSCCAnalysisManagerFunctionProxy(CGAM)); FAM.registerPass(ModuleAnalysisManagerFunctionProxy(MAM)); ModulePassManager MPM; diff --git a/tools/opt/PassRegistry.def b/tools/opt/PassRegistry.def index 92ab2d932f..e1e49004c7 100644 --- a/tools/opt/PassRegistry.def +++ b/tools/opt/PassRegistry.def @@ -29,6 +29,16 @@ MODULE_PASS("print", PrintModulePass(dbgs())) MODULE_PASS("print-cg", LazyCallGraphPrinterPass(dbgs())) #undef MODULE_PASS +#ifndef CGSCC_ANALYSIS +#define CGSCC_ANALYSIS(NAME, CREATE_PASS) +#endif +#undef CGSCC_ANALYSIS + +#ifndef CGSCC_PASS +#define CGSCC_PASS(NAME, CREATE_PASS) +#endif +#undef CGSCC_PASS + #ifndef FUNCTION_ANALYSIS #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) #endif diff --git a/tools/opt/Passes.cpp b/tools/opt/Passes.cpp index e4791b8ac8..a171f42691 100644 --- a/tools/opt/Passes.cpp +++ b/tools/opt/Passes.cpp @@ -15,6 +15,7 @@ //===----------------------------------------------------------------------===// #include "Passes.h" +#include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/IR/IRPrintingPasses.h" #include "llvm/IR/PassManager.h" @@ -31,6 +32,14 @@ struct NoOpModulePass { static StringRef name() { return "NoOpModulePass"; } }; +/// \brief No-op CGSCC pass which does nothing. +struct NoOpCGSCCPass { + PreservedAnalyses run(LazyCallGraph::SCC *C) { + return PreservedAnalyses::all(); + } + static StringRef name() { return "NoOpCGSCCPass"; } +}; + /// \brief No-op function pass which does nothing. struct NoOpFunctionPass { PreservedAnalyses run(Function *F) { return PreservedAnalyses::all(); } @@ -48,6 +57,15 @@ static bool isModulePassName(StringRef Name) { return false; } +static bool isCGSCCPassName(StringRef Name) { + if (Name == "no-op-cgscc") return true; + +#define CGSCC_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; +#include "PassRegistry.def" + + return false; +} + static bool isFunctionPassName(StringRef Name) { if (Name == "no-op-function") return true; @@ -73,6 +91,22 @@ static bool parseModulePassName(ModulePassManager &MPM, StringRef Name) { return false; } +static bool parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name) { + if (Name == "no-op-cgscc") { + CGPM.addPass(NoOpCGSCCPass()); + return true; + } + +#define CGSCC_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) { \ + CGPM.addPass(CREATE_PASS); \ + return true; \ + } +#include "PassRegistry.def" + + return false; +} + static bool parseFunctionPassName(FunctionPassManager &FPM, StringRef Name) { if (Name == "no-op-function") { FPM.addPass(NoOpFunctionPass()); @@ -126,6 +160,55 @@ static bool parseFunctionPassPipeline(FunctionPassManager &FPM, } } +static bool parseCGSCCPassPipeline(CGSCCPassManager &CGPM, + StringRef &PipelineText, + bool VerifyEachPass) { + for (;;) { + // Parse nested pass managers by recursing. + if (PipelineText.startswith("cgscc(")) { + CGSCCPassManager NestedCGPM; + + // Parse the inner pipeline into the nested manager. + PipelineText = PipelineText.substr(strlen("cgscc(")); + if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass) || + PipelineText.empty()) + return false; + assert(PipelineText[0] == ')'); + PipelineText = PipelineText.substr(1); + + // Add the nested pass manager with the appropriate adaptor. + CGPM.addPass(std::move(NestedCGPM)); + } else if (PipelineText.startswith("function(")) { + FunctionPassManager NestedFPM; + + // Parse the inner pipeline inte the nested manager. + PipelineText = PipelineText.substr(strlen("function(")); + if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass) || + PipelineText.empty()) + return false; + assert(PipelineText[0] == ')'); + PipelineText = PipelineText.substr(1); + + // Add the nested pass manager with the appropriate adaptor. + CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(NestedFPM))); + } else { + // Otherwise try to parse a pass name. + size_t End = PipelineText.find_first_of(",)"); + if (!parseCGSCCPassName(CGPM, PipelineText.substr(0, End))) + return false; + // FIXME: No verifier support for CGSCC passes! + + PipelineText = PipelineText.substr(End); + } + + if (PipelineText.empty() || PipelineText[0] == ')') + return true; + + assert(PipelineText[0] == ','); + PipelineText = PipelineText.substr(1); + } +} + static bool parseModulePassPipeline(ModulePassManager &MPM, StringRef &PipelineText, bool VerifyEachPass) { @@ -144,6 +227,20 @@ static bool parseModulePassPipeline(ModulePassManager &MPM, // Now add the nested manager as a module pass. MPM.addPass(std::move(NestedMPM)); + } else if (PipelineText.startswith("cgscc(")) { + CGSCCPassManager NestedCGPM; + + // Parse the inner pipeline inte the nested manager. + PipelineText = PipelineText.substr(strlen("cgscc(")); + if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass) || + PipelineText.empty()) + return false; + assert(PipelineText[0] == ')'); + PipelineText = PipelineText.substr(1); + + // Add the nested pass manager with the appropriate adaptor. + MPM.addPass( + createModuleToPostOrderCGSCCPassAdaptor(std::move(NestedCGPM))); } else if (PipelineText.startswith("function(")) { FunctionPassManager NestedFPM; @@ -185,6 +282,14 @@ bool llvm::parsePassPipeline(ModulePassManager &MPM, StringRef PipelineText, if (PipelineText.startswith("module(")) return parseModulePassPipeline(MPM, PipelineText, VerifyEachPass) && PipelineText.empty(); + if (PipelineText.startswith("cgscc(")) { + CGSCCPassManager CGPM; + if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass) || + !PipelineText.empty()) + return false; + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + return true; + } if (PipelineText.startswith("function(")) { FunctionPassManager FPM; if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass) || @@ -201,6 +306,15 @@ bool llvm::parsePassPipeline(ModulePassManager &MPM, StringRef PipelineText, return parseModulePassPipeline(MPM, PipelineText, VerifyEachPass) && PipelineText.empty(); + if (isCGSCCPassName(FirstName)) { + CGSCCPassManager CGPM; + if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass) || + !PipelineText.empty()) + return false; + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + return true; + } + if (isFunctionPassName(FirstName)) { FunctionPassManager FPM; if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass) || |