Index: include/llvm/Analysis/CFLAndersAliasAnalysis.h =================================================================== --- include/llvm/Analysis/CFLAndersAliasAnalysis.h +++ include/llvm/Analysis/CFLAndersAliasAnalysis.h @@ -42,7 +42,10 @@ /// Handle invalidation events from the new pass manager. /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } /// Evict the given function from cache void evict(const Function &Fn); Index: include/llvm/Analysis/CFLSteensAliasAnalysis.h =================================================================== --- include/llvm/Analysis/CFLSteensAliasAnalysis.h +++ include/llvm/Analysis/CFLSteensAliasAnalysis.h @@ -45,7 +45,10 @@ /// Handle invalidation events from the new pass manager. /// /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } /// \brief Inserts the given Function into the cache. void scan(Function *Fn); Index: include/llvm/Analysis/ObjCARCAliasAnalysis.h =================================================================== --- include/llvm/Analysis/ObjCARCAliasAnalysis.h +++ include/llvm/Analysis/ObjCARCAliasAnalysis.h @@ -48,7 +48,10 @@ /// Handle invalidation events from the new pass manager. /// /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal); Index: include/llvm/Analysis/ScopedNoAliasAA.h =================================================================== --- include/llvm/Analysis/ScopedNoAliasAA.h +++ include/llvm/Analysis/ScopedNoAliasAA.h @@ -34,7 +34,10 @@ /// Handle invalidation events from the new pass manager. /// /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc); Index: include/llvm/Analysis/TargetLibraryInfo.h =================================================================== --- include/llvm/Analysis/TargetLibraryInfo.h +++ include/llvm/Analysis/TargetLibraryInfo.h @@ -272,8 +272,14 @@ /// /// If we try to invalidate this info, just return false. It cannot become /// invalid even if the module or function changes. - bool invalidate(Module &, const PreservedAnalyses &) { return false; } - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Module &, const PreservedAnalyses &, + ModuleAnalysisManager::Invalidator &) { + return false; + } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } }; /// Analysis pass providing the \c TargetLibraryInfo. Index: include/llvm/Analysis/TargetTransformInfo.h =================================================================== --- include/llvm/Analysis/TargetTransformInfo.h +++ include/llvm/Analysis/TargetTransformInfo.h @@ -87,7 +87,8 @@ /// When used as a result of \c TargetIRAnalysis this method will be called /// when the function this was computed for changes. When it returns false, /// the information is preserved across those changes. - bool invalidate(Function &, const PreservedAnalyses &) { + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { // FIXME: We should probably in some way ensure that the subtarget // information for a function hasn't changed. return false; Index: include/llvm/Analysis/TypeBasedAliasAnalysis.h =================================================================== --- include/llvm/Analysis/TypeBasedAliasAnalysis.h +++ include/llvm/Analysis/TypeBasedAliasAnalysis.h @@ -33,7 +33,10 @@ /// Handle invalidation events from the new pass manager. /// /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal); Index: include/llvm/IR/PassManager.h =================================================================== --- include/llvm/IR/PassManager.h +++ include/llvm/IR/PassManager.h @@ -348,11 +348,86 @@ /// IR unit sufficies as its identity. It manages the cache for a unit of IR via /// the address of each unit of IR cached. template class AnalysisManager { - typedef detail::AnalysisResultConcept ResultConceptT; - typedef detail::AnalysisPassConcept PassConceptT; +public: + class Invalidator; + +private: + // Now that we've defined our invalidator, we can build types for the concept + // types. + typedef detail::AnalysisResultConcept + ResultConceptT; + typedef detail::AnalysisPassConcept + PassConceptT; + /// \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>> + AnalysisResultListT; + + /// \brief Map type from function pointer to our custom list type. + typedef DenseMap AnalysisResultListMapT; + + /// \brief Map type from a pair of analysis ID and function pointer to an + /// iterator into a particular result list. + typedef DenseMap, + typename AnalysisResultListT::iterator> + AnalysisResultMapT; public: - // Most public APIs are inherited from the CRTP base class. + /// An API provided to analysis results when they are handling invalidation to + /// allow them to invalidate other analyses they depend on. + /// + /// This is used to support analysis results which embed handles to other + /// analysis results and thus recursive invalidation must be performed. We + /// pass in this API from the analysis manager in order to let the analysis + /// results themselves define the dependency graph rather than tracking and + /// hard coding it anywhere. + class Invalidator { + public: + template + bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { + void *PassID = PassT::ID(); + SmallDenseMap::iterator IMapI; + bool Inserted; + std::tie(IMapI, Inserted) = IsResultInvalidated.insert({PassID, false}); + + // If we've already visited this pass, return true if it was invalidated + // and false otherwise. + if (!Inserted) + return IMapI->second; + + // Otherwise lookup the result object. + auto RI = Results.find({PassID, &IR}); + assert(RI != Results.end() && + "Trying to invalidate a dependent result that isn't in the " + "manager's cache is always an error, likely due to a stale result " + "handle!"); + + typedef detail::AnalysisResultModel + ResultModelT; + auto &ResultModel = static_cast(*RI->second->second); + + // Mark in the map whether the result should be invalidated and return + // that. + IMapI->second = ResultModel.invalidate(IR, PA, *this); + return IMapI->second; + } + + private: + friend class AnalysisManager; + + Invalidator(SmallDenseMap &IsResultInvalidated, + const AnalysisResultMapT &Results) + : IsResultInvalidated(IsResultInvalidated), Results(Results) {} + + SmallDenseMap &IsResultInvalidated; + const AnalysisResultMapT &Results; + }; /// \brief Construct an empty analysis manager. /// @@ -402,7 +477,8 @@ "This analysis pass was not registered prior to being queried"); ResultConceptT &ResultConcept = getResultImpl(PassT::ID(), IR, ExtraArgs...); - typedef detail::AnalysisResultModel + typedef detail::AnalysisResultModel ResultModelT; return static_cast(ResultConcept).Result; } @@ -421,7 +497,8 @@ if (!ResultConcept) return nullptr; - typedef detail::AnalysisResultModel + typedef detail::AnalysisResultModel ResultModelT; return &static_cast(ResultConcept)->Result; } @@ -446,7 +523,9 @@ /// away. template bool registerPass(PassBuilderT PassBuilder) { typedef decltype(PassBuilder()) PassT; - typedef detail::AnalysisPassModel PassModelT; + typedef detail::AnalysisPassModel + PassModelT; auto &PassPtr = AnalysisPasses[PassT::ID()]; if (PassPtr) @@ -470,8 +549,8 @@ /// \brief Invalidate analyses cached for an IR unit. /// /// Walk through all of the analyses pertaining to this unit of IR and - /// invalidate them unless they are preserved by the PreservedAnalyses set. - /// We accept the PreservedAnalyses set by value and update it with each + /// invalidate them unless they are preserved by the PreservedAnalysesT set. + /// We accept the PreservedAnalysesT set by value and update it with each /// analyis pass which has been successfully invalidated and thus can be /// preserved going forward. The updated set is returned. PreservedAnalyses invalidate(IRUnitT &IR, PreservedAnalyses PA) { @@ -483,37 +562,47 @@ dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName() << "\n"; - // Clear all the invalidated results associated specifically with this - // function. - SmallVector InvalidatedPassIDs; + // Track whether each pass's result is invalidated with a map that is fed + // to an Invalidator instance to additionally memoize the calls to each + // result's invalidate routine. + SmallDenseMap IsResultInvalidated; + Invalidator Inv(IsResultInvalidated, AnalysisResults); AnalysisResultListT &ResultsList = AnalysisResultLists[&IR]; - for (typename AnalysisResultListT::iterator I = ResultsList.begin(), - E = ResultsList.end(); - I != E;) { - void *PassID = I->first; + for (auto &AnalysisResultPair : ResultsList) { + // We don't directly use the Invalidator here because we have to operate + // on the type erased result where it doesn't, but we don't have to look + // up the result in the map where it does. + void *PassID = AnalysisResultPair.first; + auto &Result = *AnalysisResultPair.second; + + SmallDenseMap::iterator IMapI; + bool Inserted; + std::tie(IMapI, Inserted) = IsResultInvalidated.insert({PassID, false}); + if (!Inserted) + // This result was already handled via the invalidator. + continue; - // Pass the invalidation down to the pass itself to see if it thinks it is - // necessary. The analysis pass can return false if no action on the part - // of the analysis manager is required for this invalidation event. - if (I->second->invalidate(IR, PA)) { - if (DebugLogging) - dbgs() << "Invalidating analysis: " << this->lookupPass(PassID).name() - << "\n"; - - InvalidatedPassIDs.push_back(I->first); - I = ResultsList.erase(I); - } else { + // Try to invalidate the result, giving it the Invalidator so it can + // recursively query for any dependencies it has and record the result. + IMapI->second = Result.invalidate(IR, PA, Inv); + } + + // Now re-walk the list of results but this time erasing the ones which + // have been invalidated. + for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) { + void *PassID = I->first; + if (!IsResultInvalidated.lookup(PassID)) { ++I; + continue; } - // After handling each pass, we mark it as preserved. Once we've - // invalidated any stale results, the rest of the system is allowed to - // start preserving this analysis again. - PA.preserve(PassID); + if (DebugLogging) + dbgs() << "Invalidating analysis: " << this->lookupPass(PassID).name() + << "\n"; + + I = ResultsList.erase(I); + AnalysisResults.erase({PassID, &IR}); } - while (!InvalidatedPassIDs.empty()) - AnalysisResults.erase( - std::make_pair(InvalidatedPassIDs.pop_back_val(), &IR)); if (ResultsList.empty()) AnalysisResultLists.erase(&IR); @@ -595,30 +684,12 @@ /// \brief Collection of module analysis passes, indexed by ID. AnalysisPassMapT AnalysisPasses; - /// \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>>> - AnalysisResultListT; - - /// \brief Map type from function pointer to our custom list type. - typedef DenseMap AnalysisResultListMapT; - /// \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. AnalysisResultListMapT AnalysisResultLists; - /// \brief Map type from a pair of analysis ID and function pointer to an - /// iterator into a particular result list. - typedef DenseMap, - typename AnalysisResultListT::iterator> - AnalysisResultMapT; - /// \brief Map from an analysis ID and function to a particular cached /// analysis result. AnalysisResultMapT AnalysisResults; @@ -692,7 +763,9 @@ /// 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(IRUnitT &IR, const PreservedAnalyses &PA) { + bool invalidate( + IRUnitT &IR, const PreservedAnalyses &PA, + typename AnalysisManager::Invalidator &) { // 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 @@ -785,7 +858,11 @@ const AnalysisManagerT &getManager() const { return *AM; } /// \brief Handle invalidation by ignoring it, this pass is immutable. - bool invalidate(IRUnitT &, const PreservedAnalyses &) { return false; } + bool invalidate( + IRUnitT &, const PreservedAnalyses &, + typename AnalysisManager::Invalidator &) { + return false; + } private: const AnalysisManagerT *AM; Index: include/llvm/IR/PassManagerInternal.h =================================================================== --- include/llvm/IR/PassManagerInternal.h +++ include/llvm/IR/PassManagerInternal.h @@ -24,6 +24,7 @@ namespace llvm { template class AnalysisManager; +class Invalidator; class PreservedAnalyses; /// \brief Implementation details of the pass manager interfaces. @@ -82,7 +83,8 @@ /// /// This concept is parameterized over the IR unit that this result pertains /// to. -template struct AnalysisResultConcept { +template +struct AnalysisResultConcept { virtual ~AnalysisResultConcept() {} /// \brief Method to try and mark a result as invalid. @@ -95,7 +97,8 @@ /// took care to update or preserve the analysis result in some way. /// /// \returns true if the result is indeed invalid (the default). - virtual bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) = 0; + virtual bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA, + InvalidatorT &Inv) = 0; }; /// \brief SFINAE metafunction for computing whether \c ResultT provides an @@ -141,7 +144,7 @@ /// an invalidation handler. It is only selected when the invalidation handler /// is not part of the ResultT's interface. template ::Value> struct AnalysisResultModel; @@ -149,9 +152,10 @@ /// \brief Specialization of \c AnalysisResultModel which provides the default /// invalidate functionality. template -struct AnalysisResultModel - : AnalysisResultConcept { + typename PreservedAnalysesT, typename InvalidatorT> +struct AnalysisResultModel + : AnalysisResultConcept { explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {} // We have to explicitly define all the special member functions because MSVC // refuses to generate them. @@ -172,7 +176,8 @@ // FIXME: We should actually use two different concepts for analysis results // rather than two different models, and avoid the indirect function call for // ones that use the trivial behavior. - bool invalidate(IRUnitT &, const PreservedAnalysesT &PA) override { + bool invalidate(IRUnitT &, const PreservedAnalysesT &PA, + InvalidatorT &) override { return !PA.preserved(PassT::ID()); } @@ -182,9 +187,10 @@ /// \brief Specialization of \c AnalysisResultModel which delegates invalidate /// handling to \c ResultT. template -struct AnalysisResultModel - : AnalysisResultConcept { + typename PreservedAnalysesT, typename InvalidatorT> +struct AnalysisResultModel + : AnalysisResultConcept { explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {} // We have to explicitly define all the special member functions because MSVC // refuses to generate them. @@ -201,8 +207,9 @@ } /// \brief The model delegates to the \c ResultT method. - bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA) override { - return Result.invalidate(IR, PA); + bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA, + InvalidatorT &Inv) override { + return Result.invalidate(IR, PA, Inv); } ResultT Result; @@ -212,13 +219,16 @@ /// /// This concept is parameterized over the IR unit that it can run over and /// produce an analysis result. -template struct AnalysisPassConcept { +template +struct AnalysisPassConcept { virtual ~AnalysisPassConcept() {} /// \brief Method to run this analysis over a unit of IR. /// \returns A unique_ptr to the analysis result object to be queried by /// users. - virtual std::unique_ptr> + virtual std::unique_ptr< + AnalysisResultConcept> run(IRUnitT &IR, AnalysisManager &AM, ExtraArgTs... ExtraArgs) = 0; @@ -231,8 +241,10 @@ /// Can wrap any type which implements a suitable \c run method. The method /// must accept an \c IRUnitT& and an \c AnalysisManager& as arguments /// and produce an object which can be wrapped in a \c AnalysisResultModel. -template -struct AnalysisPassModel : AnalysisPassConcept { +template +struct AnalysisPassModel : AnalysisPassConcept { explicit AnalysisPassModel(PassT Pass) : Pass(std::move(Pass)) {} // We have to explicitly define all the special member functions because MSVC // refuses to generate them. @@ -248,13 +260,15 @@ } // FIXME: Replace PassT::Result with type traits when we use C++11. - typedef AnalysisResultModel + typedef AnalysisResultModel ResultModelT; /// \brief The model delegates to the \c PassT::run method. /// /// The return is wrapped in an \c AnalysisResultModel. - std::unique_ptr> + std::unique_ptr< + AnalysisResultConcept> run(IRUnitT &IR, AnalysisManager &AM, ExtraArgTs... ExtraArgs) override { return make_unique(Pass.run(IR, AM, ExtraArgs...)); Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -105,7 +105,10 @@ class TestImmutableFunctionAnalysis { public: struct Result { - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } }; static void *ID() { return (void *)&PassID; } Index: unittests/IR/PassManagerTest.cpp =================================================================== --- unittests/IR/PassManagerTest.cpp +++ unittests/IR/PassManagerTest.cpp @@ -388,4 +388,104 @@ // And ensure that we accumulated the correct result. EXPECT_EQ(42 * (int)M->size(), Result); } + +/// A test analysis pass which caches in its result another analyses pass and +/// uses it to serve queries, and must therefore invalidate itself when its +/// dependency is invalidated. +struct TestIndirectFunctionAnalysis + : public AnalysisInfoMixin { + struct Result { + Result(TestFunctionAnalysis::Result &Dep) : Dep(Dep) {} + TestFunctionAnalysis::Result &Dep; + + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + return !PA.preserved() || + Inv.invalidate(F, PA); + } + }; + + TestIndirectFunctionAnalysis(int &Runs) : Runs(Runs) {} + + /// Run the analysis pass over the function and return a result. + Result run(Function &F, FunctionAnalysisManager &AM) { + ++Runs; + return Result(AM.getResult(F)); + } + +private: + friend AnalysisInfoMixin; + static char PassID; + + int &Runs; +}; + +char TestIndirectFunctionAnalysis::PassID; + +struct LambdaPass : public PassInfoMixin { + template LambdaPass(T &&Arg) : Func(std::forward(Arg)) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { + return Func(F, AM); + } + + std::function Func; +}; + +TEST_F(PassManagerTest, IndirectAnalysisInvalidation) { + FunctionAnalysisManager FAM(/*DebugLogging*/ true); + int AnalysisRuns = 0, IndirectAnalysisRuns = 0; + FAM.registerPass([&] { return TestFunctionAnalysis(AnalysisRuns); }); + FAM.registerPass( + [&] { return TestIndirectFunctionAnalysis(IndirectAnalysisRuns); }); + + ModuleAnalysisManager MAM(/*DebugLogging*/ true); + MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); + FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); + + int InstrCount = 0; + ModulePassManager MPM(/*DebugLogging*/ true); + FunctionPassManager FPM(/*DebugLogging*/ true); + // First just use the analysis to get the instruction count, and preserve + // everything + FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) { + InstrCount += + AM.getResult(F).Dep.InstructionCount; + return PreservedAnalyses::all(); + })); + // Next, for one function invalidate just the underlying analysis, for + // another function invalidate the indirect analysis, and for the final + // function invalidate both. + FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) { + InstrCount += + AM.getResult(F).Dep.InstructionCount; + auto PA = PreservedAnalyses::none(); + if (F.getName() == "g") + PA.preserve(); + else if (F.getName() == "h") + PA.preserve(); + return PA; + })); + // Finally, use the analysis again on each function forcing re-computation + // for all of them. + FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) { + InstrCount += + AM.getResult(F).Dep.InstructionCount; + return PreservedAnalyses::all(); + })); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + MPM.run(*M, MAM); + + // There are generally two possible runs for ecah of the three functions. But + // for one function, we only invalidate the indirect analysis so the base one + // only gets run five times. + EXPECT_EQ(5, AnalysisRuns); + // The indiract analysis is invalidate for each function (either directly or + // indirectly) and run twice total for each. + EXPECT_EQ(6, IndirectAnalysisRuns); + + // There are 5 total instructions in the module and we add the count three + // times total. + EXPECT_EQ(5 * 3, InstrCount); +} }