From f348c9782c5c31309dfd2d04e3dbee21fefe07ff Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 13 Nov 2013 01:12:08 +0000 Subject: Introduce an AnalysisManager which is like a pass manager but with a lot more smarts in it. This is where most of the interesting logic that used to live in the implicit-scheduling-hackery of the old pass manager will live. Like the previous commits, note that this is a very early prototype! I expect substantial changes before this is ready to use. The core of the design is the following: - We have an AnalysisManager which can be used across a series of passes over a module. - The code setting up a pass pipeline registers the analyses available with the manager. - Individual transform passes can check than an analysis manager provides the analyses they require in order to fail-fast. - There is *no* implicit registration or scheduling. - Analysis passes are different from other passes: they produce an analysis result that is cached and made available via the analysis manager. - Cached results are invalidated automatically by the pass managers. - When a transform pass requests an analysis result, either the analysis is run to produce the result or a cached result is provided. There are a few aspects of this design that I *know* will change in subsequent commits: - Currently there is no "preservation" system, that needs to be added. - All of the analysis management should move up to the analysis library. - The analysis management needs to support at least SCC passes. Maybe loop passes. Living in the analysis library will facilitate this. - Need support for analyses which are *both* module and function passes. - Need support for pro-actively running module analyses to have cached results within a function pass manager. - Need a clear design for "immutable" passes. - Need support for requesting cached results when available and not re-running the pass even if that would be necessary. - Need more thorough testing of all of this infrastructure. There are other aspects that I view as open questions I'm hoping to resolve as I iterate a bit on the infrastructure, and especially as I start writing actual passes against this. - Should we have separate management layers for function, module, and SCC analyses? I think "yes", but I'm not yet ready to switch the code. Adding SCC support will likely resolve this definitively. - How should the 'require' functionality work? Should *that* be the only way to request results to ensure that passes always require things? - How should preservation work? - Probably some other things I'm forgetting. =] Look forward to more patches in shorter order now that this is in place. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194538 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/PassManager.h | 306 +++++++++++++++++++++++++++++++++++++-- lib/IR/CMakeLists.txt | 1 + lib/IR/PassManager.cpp | 155 ++++++++++++++++++++ unittests/IR/PassManagerTest.cpp | 52 ++++++- 4 files changed, 498 insertions(+), 16 deletions(-) create mode 100644 lib/IR/PassManager.cpp diff --git a/include/llvm/IR/PassManager.h b/include/llvm/IR/PassManager.h index aeadd41..5800e35 100644 --- a/include/llvm/IR/PassManager.h +++ b/include/llvm/IR/PassManager.h @@ -27,8 +27,12 @@ /// //===----------------------------------------------------------------------===// +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/polymorphic_ptr.h" +#include "llvm/Support/type_traits.h" +#include "llvm/IR/Function.h" #include "llvm/IR/Module.h" +#include #include namespace llvm { @@ -64,18 +68,17 @@ template struct PassModel : PassConcept { } +class AnalysisManager; + class ModulePassManager { public: - ModulePassManager(Module *M) : M(M) {} + ModulePassManager(Module *M, AnalysisManager *AM = 0) : M(M), AM(AM) {} template void addPass(ModulePassT Pass) { Passes.push_back(new ModulePassModel(llvm_move(Pass))); } - void run() { - for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) - Passes[Idx]->run(M); - } + void run(); private: // Pull in the concept type and model template specialized for modules. @@ -86,22 +89,19 @@ private: }; Module *M; + AnalysisManager *AM; std::vector > Passes; }; class FunctionPassManager { public: + FunctionPassManager(AnalysisManager *AM = 0) : AM(AM) {} + template void addPass(FunctionPassT Pass) { Passes.push_back(new FunctionPassModel(llvm_move(Pass))); } - bool run(Module *M) { - bool Changed = false; - for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) - for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) - Changed |= Passes[Idx]->run(I); - return Changed; - } + bool run(Module *M); private: // Pull in the concept type and model template specialized for functions. @@ -112,7 +112,289 @@ private: : detail::PassModel(Pass) {} }; + AnalysisManager *AM; std::vector > Passes; }; + +/// \brief An analysis manager to coordinate and cache analyses run over +/// a module. +/// +/// The analysis manager is typically used by passes in a pass pipeline +/// (consisting potentially of several individual pass managers) over a module +/// of IR. It provides registration of available analyses, declaring +/// requirements on support for specific analyses, running of an specific +/// analysis over a specific unit of IR to compute an analysis result, and +/// caching of the analysis results to reuse them across multiple passes. +/// +/// It is the responsibility of callers to use the invalidation API to +/// invalidate analysis results when the IR they correspond to changes. The +/// \c ModulePassManager and \c FunctionPassManager do this automatically. +class AnalysisManager { +public: + AnalysisManager(Module *M) : M(M) {} + + /// \brief Get the result of an analysis pass for this module. + /// + /// If there is not a valid cached result in the manager already, this will + /// re-run the analysis to produce a valid result. + /// + /// The module passed in must be the same module as the analysis manager was + /// constructed around. + template + const typename PassT::Result &getResult(Module *M) { + const AnalysisResultConcept &ResultConcept = + getResultImpl(PassT::ID(), M); + typedef AnalysisResultModel ResultModelT; + return static_cast(ResultConcept).Result; + } + + /// \brief Get the result of an analysis pass for a function. + /// + /// If there is not a valid cached result in the manager already, this will + /// re-run the analysis to produce a valid result. + template + const typename PassT::Result &getResult(Function *F) { + const AnalysisResultConcept &ResultConcept = + getResultImpl(PassT::ID(), F); + typedef AnalysisResultModel ResultModelT; + return static_cast(ResultConcept).Result; + } + + /// \brief Register an analysis pass with the manager. + /// + /// This provides an initialized and set-up analysis pass to the + /// analysis + /// manager. Whomever is setting up analysis passes must use this to + /// populate + /// the manager with all of the analysis passes available. + template void registerAnalysisPass(PassT Pass) { + registerAnalysisPassImpl(llvm_move(Pass)); + } + + /// \brief Require that a particular analysis pass is provided by the manager. + /// + /// This allows transform passes to assert ther requirements during + /// construction and fail fast if the analysis manager doesn't provide the + /// needed facilities. + /// + /// We force the analysis manager to have these passes explicitly registered + /// first to ensure that there is exactly one place in the code responsible + /// for adding an analysis pass to the manager as all transforms will share + /// a single pass within the manager and each may not be the canonical place + /// to initialize such a pass. + template void requireAnalysisPass() { + requireAnalysisPassImpl(); + } + + /// \brief Invalidate a specific analysis pass for an IR module. + /// + /// Note that the analysis result can disregard invalidation. + template void invalidate(Module *M) { + invalidateImpl(PassT::ID(), M); + } + + /// \brief Invalidate a specific analysis pass for an IR function. + /// + /// Note that the analysis result can disregard invalidation. + template void invalidate(Function *F) { + invalidateImpl(PassT::ID(), F); + } + + /// \brief Invalidate analyses cached for an IR Module. + /// + /// Note that specific analysis results can disregard invalidation by + /// overriding their invalidate method. + /// + /// The module must be the module this analysis manager was constructed + /// around. + void invalidateAll(Module *M); + + /// \brief Invalidate analyses cached for an IR Function. + /// + /// Note that specific analysis results can disregard invalidation by + /// overriding the invalidate method. + void invalidateAll(Function *F); + +private: + /// \brief Abstract concept of an analysis result. + /// + /// This concept is parameterized over the IR unit that this result pertains + /// to. + template struct AnalysisResultConcept { + virtual ~AnalysisResultConcept() {} + virtual AnalysisResultConcept *clone() = 0; + + /// \brief Method to try and mark a result as invalid. + /// + /// When the outer \c AnalysisManager detects a change in some underlying + /// unit of the IR, it will call this method on all of the results cached. + /// + /// \returns true if the result should indeed be invalidated (the default). + virtual bool invalidate(IRUnitT *IR) = 0; + }; + + /// \brief Wrapper to model the analysis result concept. + /// + /// Can wrap any type which implements a suitable invalidate member and model + /// the AnalysisResultConcept for the AnalysisManager. + template + struct AnalysisResultModel : AnalysisResultConcept { + AnalysisResultModel(ResultT Result) : Result(llvm_move(Result)) {} + virtual AnalysisResultModel *clone() { + return new AnalysisResultModel(Result); + } + + /// \brief The model delegates to the \c ResultT method. + virtual bool invalidate(IRUnitT *IR) { return Result.invalidate(IR); } + + ResultT Result; + }; + + /// \brief Abstract concept of an analysis pass. + /// + /// This concept is parameterized over the IR unit that it can run over and + /// produce an analysis result. + template struct AnalysisPassConcept { + virtual ~AnalysisPassConcept() {} + virtual AnalysisPassConcept *clone() = 0; + + /// \brief Method to run this analysis over a unit of IR. + /// \returns The analysis result object to be queried by users, the caller + /// takes ownership. + virtual AnalysisResultConcept *run(IRUnitT *IR) = 0; + }; + + /// \brief Wrapper to model the analysis pass concept. + /// + /// Can wrap any type which implements a suitable \c run method. The method + /// must accept the IRUnitT as an argument and produce an object which can be + /// wrapped in a \c AnalysisResultModel. + template + struct AnalysisPassModel : AnalysisPassConcept { + AnalysisPassModel(PassT Pass) : Pass(llvm_move(Pass)) {} + virtual AnalysisPassModel *clone() { return new AnalysisPassModel(Pass); } + + // FIXME: Replace PassT::IRUnitT with type traits when we use C++11. + typedef typename PassT::IRUnitT IRUnitT; + + // FIXME: Replace PassT::Result with type traits when we use C++11. + typedef AnalysisResultModel ResultModelT; + + /// \brief The model delegates to the \c PassT::run method. + /// + /// The return is wrapped in an \c AnalysisResultModel. + virtual ResultModelT *run(IRUnitT *IR) { + return new ResultModelT(Pass.run(IR)); + } + + PassT Pass; + }; + + + /// \brief Get a module pass result, running the pass if necessary. + const AnalysisResultConcept &getResultImpl(void *PassID, Module *M); + + /// \brief Get a function pass result, running the pass if necessary. + const AnalysisResultConcept &getResultImpl(void *PassID, + Function *F); + + /// \brief Invalidate a module pass result. + void invalidateImpl(void *PassID, Module *M); + + /// \brief Invalidate a function pass result. + void invalidateImpl(void *PassID, Function *F); + + + /// \brief Module pass specific implementation of registration. + template + typename enable_if >::type + registerAnalysisPassImpl(PassT Pass) { + assert(!ModuleAnalysisPasses.count(PassT::ID()) && + "Registered the same analysis pass twice!"); + ModuleAnalysisPasses[PassT::ID()] = + new AnalysisPassModel(llvm_move(Pass)); + } + + /// \brief Function pass specific implementation of registration. + template + typename enable_if >::type + registerAnalysisPassImpl(PassT Pass) { + assert(!FunctionAnalysisPasses.count(PassT::ID()) && + "Registered the same analysis pass twice!"); + FunctionAnalysisPasses[PassT::ID()] = + new AnalysisPassModel(llvm_move(Pass)); + } + + /// \brief Module pass specific implementation of requirement declaration. + template + typename enable_if >::type + requireAnalysisPassImpl() { + assert(ModuleAnalysisPasses.count(PassT::ID()) && + "This analysis pass was not registered prior to being required"); + } + + /// \brief Function pass specific implementation of requirement declaration. + template + typename enable_if >::type + requireAnalysisPassImpl() { + assert(FunctionAnalysisPasses.count(PassT::ID()) && + "This analysis pass was not registered prior to being required"); + } + + + /// \brief Map type from module analysis pass ID to pass concept pointer. + typedef DenseMap > > + ModuleAnalysisPassMapT; + + /// \brief Collection of module analysis passes, indexed by ID. + ModuleAnalysisPassMapT ModuleAnalysisPasses; + + /// \brief Map type from module analysis pass ID to pass result concept pointer. + typedef DenseMap > > + ModuleAnalysisResultMapT; + + /// \brief Cache of computed module analysis results for this module. + ModuleAnalysisResultMapT ModuleAnalysisResults; + + + /// \brief Map type from function analysis pass ID to pass concept pointer. + typedef DenseMap > > + FunctionAnalysisPassMapT; + + /// \brief Collection of function analysis passes, indexed by ID. + FunctionAnalysisPassMapT FunctionAnalysisPasses; + + /// \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 > > > + FunctionAnalysisResultListT; + + /// \brief Map type from function pointer to our custom list type. + typedef DenseMap FunctionAnalysisResultListMapT; + + /// \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. + FunctionAnalysisResultListMapT FunctionAnalysisResultLists; + + /// \brief Map type from a pair of analysis ID and function pointer to an + /// iterator into a particular result list. + typedef DenseMap, + FunctionAnalysisResultListT::iterator> + FunctionAnalysisResultMapT; + + /// \brief Map from an analysis ID and function to a particular cached + /// analysis result. + FunctionAnalysisResultMapT FunctionAnalysisResults; + + /// \brief Module handle for the \c AnalysisManager. + Module *M; +}; + } diff --git a/lib/IR/CMakeLists.txt b/lib/IR/CMakeLists.txt index 2ad5fdb..581946c 100644 --- a/lib/IR/CMakeLists.txt +++ b/lib/IR/CMakeLists.txt @@ -27,6 +27,7 @@ add_llvm_library(LLVMCore Metadata.cpp Module.cpp Pass.cpp + PassManager.cpp PassRegistry.cpp PrintModulePass.cpp Type.cpp diff --git a/lib/IR/PassManager.cpp b/lib/IR/PassManager.cpp new file mode 100644 index 0000000..e6c61e9 --- /dev/null +++ b/lib/IR/PassManager.cpp @@ -0,0 +1,155 @@ +//===- PassManager.h - Infrastructure for managing & running IR passes ----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/IR/PassManager.h" +#include "llvm/ADT/STLExtras.h" + +using namespace llvm; + +void ModulePassManager::run() { + for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) + if (Passes[Idx]->run(M)) + if (AM) AM->invalidateAll(M); +} + +bool FunctionPassManager::run(Module *M) { + bool Changed = false; + for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) + for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) + if (Passes[Idx]->run(I)) { + Changed = true; + if (AM) AM->invalidateAll(I); + } + return Changed; +} + +void AnalysisManager::invalidateAll(Function *F) { + assert(F->getParent() == M && "Invalidating a function from another module!"); + + // First invalidate any module results we still have laying about. + // FIXME: This is a total hack based on the fact that erasure doesn't + // invalidate iteration for DenseMap. + for (ModuleAnalysisResultMapT::iterator I = ModuleAnalysisResults.begin(), + E = ModuleAnalysisResults.end(); + I != E; ++I) + if (I->second->invalidate(M)) + ModuleAnalysisResults.erase(I); + + // Now clear all the invalidated results associated specifically with this + // function. + SmallVector InvalidatedPassIDs; + FunctionAnalysisResultListT &ResultsList = FunctionAnalysisResultLists[F]; + for (FunctionAnalysisResultListT::iterator I = ResultsList.begin(), + E = ResultsList.end(); + I != E; ++I) + if (I->second->invalidate(F)) { + FunctionAnalysisResultListT::iterator Old = I--; + InvalidatedPassIDs.push_back(Old->first); + ResultsList.erase(Old); + } + while (!InvalidatedPassIDs.empty()) + FunctionAnalysisResults.erase( + std::make_pair(InvalidatedPassIDs.pop_back_val(), F)); +} + +void AnalysisManager::invalidateAll(Module *M) { + // First invalidate any module results we still have laying about. + // FIXME: This is a total hack based on the fact that erasure doesn't + // invalidate iteration for DenseMap. + for (ModuleAnalysisResultMapT::iterator I = ModuleAnalysisResults.begin(), + E = ModuleAnalysisResults.end(); + I != E; ++I) + if (I->second->invalidate(M)) + ModuleAnalysisResults.erase(I); + + // Now walk all of the functions for which there are cached results, and + // attempt to invalidate each of those as the entire module may have changed. + // FIXME: How do we handle functions which have been deleted or RAUWed? + SmallVector InvalidatedPassIDs; + for (FunctionAnalysisResultListMapT::iterator + FI = FunctionAnalysisResultLists.begin(), + FE = FunctionAnalysisResultLists.end(); + FI != FE; ++FI) { + Function *F = FI->first; + FunctionAnalysisResultListT &ResultsList = FI->second; + for (FunctionAnalysisResultListT::iterator I = ResultsList.begin(), + E = ResultsList.end(); + I != E; ++I) + if (I->second->invalidate(F)) { + FunctionAnalysisResultListT::iterator Old = I--; + InvalidatedPassIDs.push_back(Old->first); + ResultsList.erase(Old); + } + while (!InvalidatedPassIDs.empty()) + FunctionAnalysisResults.erase( + std::make_pair(InvalidatedPassIDs.pop_back_val(), F)); + } +} + +const AnalysisManager::AnalysisResultConcept & +AnalysisManager::getResultImpl(void *PassID, Module *M) { + assert(M == this->M && "Wrong module used when querying the AnalysisManager"); + ModuleAnalysisResultMapT::iterator RI; + bool Inserted; + llvm::tie(RI, Inserted) = ModuleAnalysisResults.insert(std::make_pair( + PassID, polymorphic_ptr >())); + + if (Inserted) { + // We don't have a cached result for this result. Look up the pass and run + // it to produce a result, which we then add to the cache. + ModuleAnalysisPassMapT::const_iterator PI = + ModuleAnalysisPasses.find(PassID); + assert(PI != ModuleAnalysisPasses.end() && + "Analysis passes must be registered prior to being queried!"); + RI->second = PI->second->run(M); + } + + return *RI->second; +} + +const AnalysisManager::AnalysisResultConcept & +AnalysisManager::getResultImpl(void *PassID, Function *F) { + assert(F->getParent() == M && "Analyzing a function from another module!"); + + FunctionAnalysisResultMapT::iterator RI; + bool Inserted; + llvm::tie(RI, Inserted) = FunctionAnalysisResults.insert(std::make_pair( + std::make_pair(PassID, F), FunctionAnalysisResultListT::iterator())); + + if (Inserted) { + // We don't have a cached result for this result. Look up the pass and run + // it to produce a result, which we then add to the cache. + FunctionAnalysisPassMapT::const_iterator PI = + FunctionAnalysisPasses.find(PassID); + assert(PI != FunctionAnalysisPasses.end() && + "Analysis passes must be registered prior to being queried!"); + FunctionAnalysisResultListT &ResultList = FunctionAnalysisResultLists[F]; + ResultList.push_back(std::make_pair(PassID, PI->second->run(F))); + RI->second = llvm::prior(ResultList.end()); + } + + return *RI->second->second; +} + +void AnalysisManager::invalidateImpl(void *PassID, Module *M) { + assert(M == this->M && "Invalidating a pass over a different module!"); + ModuleAnalysisResults.erase(PassID); +} + +void AnalysisManager::invalidateImpl(void *PassID, Function *F) { + assert(F->getParent() == M && + "Invalidating a pass over a function from another module!"); + + FunctionAnalysisResultMapT::iterator RI = FunctionAnalysisResults.find(std::make_pair(PassID, F)); + if (RI == FunctionAnalysisResults.end()) + return; + + FunctionAnalysisResultLists[F].erase(RI->second); +} + diff --git a/unittests/IR/PassManagerTest.cpp b/unittests/IR/PassManagerTest.cpp index f2e04d9..8eec0ec 100644 --- a/unittests/IR/PassManagerTest.cpp +++ b/unittests/IR/PassManagerTest.cpp @@ -19,6 +19,36 @@ using namespace llvm; namespace { +class TestAnalysisPass { +public: + typedef Function IRUnitT; + + struct Result { + Result(int Count) : InstructionCount(Count) {} + bool invalidate(Function *) { return true; } + int InstructionCount; + }; + + /// \brief Returns an opaque, unique ID for this pass type. + static void *ID() { return (void *)&PassID; } + + /// \brief Run the analysis pass over the function and return a result. + Result run(Function *F) { + int Count = 0; + for (Function::iterator BBI = F->begin(), BBE = F->end(); BBI != BBE; ++BBI) + for (BasicBlock::iterator II = BBI->begin(), IE = BBI->end(); II != IE; + ++II) + ++Count; + return Result(Count); + } + +private: + /// \brief Private static data to provide unique ID. + static char PassID; +}; + +char TestAnalysisPass::PassID; + struct TestModulePass { TestModulePass(int &RunCount) : RunCount(RunCount) {} @@ -31,14 +61,23 @@ struct TestModulePass { }; struct TestFunctionPass { - TestFunctionPass(int &RunCount) : RunCount(RunCount) {} + TestFunctionPass(AnalysisManager &AM, int &RunCount, int &AnalyzedInstrCount) + : AM(AM), RunCount(RunCount), AnalyzedInstrCount(AnalyzedInstrCount) { + AM.requireAnalysisPass(); + } bool run(Function *F) { ++RunCount; + + const TestAnalysisPass::Result &AR = AM.getResult(F); + AnalyzedInstrCount += AR.InstructionCount; + return true; } + AnalysisManager &AM; int &RunCount; + int &AnalyzedInstrCount; }; Module *parseIR(const char *IR) { @@ -68,8 +107,11 @@ public: }; TEST_F(PassManagerTest, Basic) { - ModulePassManager MPM(M.get()); - FunctionPassManager FPM; + AnalysisManager AM(M.get()); + AM.registerAnalysisPass(TestAnalysisPass()); + + ModulePassManager MPM(M.get(), &AM); + FunctionPassManager FPM(&AM); // Count the runs over a module. int ModulePassRunCount = 0; @@ -77,12 +119,14 @@ TEST_F(PassManagerTest, Basic) { // Count the runs over a Function. int FunctionPassRunCount = 0; - FPM.addPass(TestFunctionPass(FunctionPassRunCount)); + int AnalyzedInstrCount = 0; + FPM.addPass(TestFunctionPass(AM, FunctionPassRunCount, AnalyzedInstrCount)); MPM.addPass(FPM); MPM.run(); EXPECT_EQ(1, ModulePassRunCount); EXPECT_EQ(3, FunctionPassRunCount); + EXPECT_EQ(5, AnalyzedInstrCount); } } -- cgit v1.1