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/CGSCCPassManager.h =================================================================== --- include/llvm/Analysis/CGSCCPassManager.h +++ include/llvm/Analysis/CGSCCPassManager.h @@ -97,6 +97,9 @@ struct CGSCCUpdateResult; +/// Extern template declaration for the analysis set for this IR unit. +extern template class AllAnalysesOn; + extern template class AnalysisManager; /// \brief The CGSCC analysis manager. /// 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 @@ -30,7 +30,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 @@ -313,8 +313,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 @@ -30,7 +30,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 @@ -339,11 +339,89 @@ /// 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 the pass ID to enable finding iterators to a given entry + /// in maps below, and provides the storage for the actual result concept. + typedef std::list>> + AnalysisResultListT; + + /// \brief Map type from IRUnitT pointer to our custom list type. + typedef DenseMap AnalysisResultListMapT; + + /// \brief Map type from a pair of analysis ID and IRUnitT pointer to an + /// iterator into a particular result list which is where the actual result + /// is stored. + typedef DenseMap, + typename AnalysisResultListT::iterator> + AnalysisResultMapT; public: - // Most public APIs are inherited from the CRTP base class. + /// API to communicate dependencies between analyses during invalidation. + /// + /// When an analysis result embeds handles to other analysis results, it + /// needs to be invalidated both when its own information isn't preserved and + /// if any of those embedded analysis results end up invalidated. We pass in + /// an \c Invalidator object from the analysis manager in order to let the + /// analysis results themselves define the dependency graph on the fly. This + /// avoids building an explicit data structure representation of the + /// dependencies between analysis results. + class Invalidator { + public: + template + bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { + AnalysisKey *ID = PassT::ID(); + SmallDenseMap::iterator IMapI; + bool Inserted; + std::tie(IMapI, Inserted) = IsResultInvalidated.insert({ID, false}); + + // If we've already visited this pass, return true if it was invalidated + // and false otherwise. + if (!Inserted) + return IMapI->second; + + // Otherwise look up the result object. + auto RI = Results.find({ID, &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. /// @@ -405,7 +483,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; } @@ -424,7 +503,8 @@ if (!ResultConcept) return nullptr; - typedef detail::AnalysisResultModel + typedef detail::AnalysisResultModel ResultModelT; return &static_cast(ResultConcept)->Result; } @@ -449,7 +529,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) @@ -483,31 +565,46 @@ dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName() << "\n"; - // Clear all the invalidated results associated specifically with this - // function. - SmallVector InvalidatedIDs; + // Track whether each pass's result is invalidated. Memoize the results + // using the IsResultInvalidated map. + SmallDenseMap IsResultInvalidated; + Invalidator Inv(IsResultInvalidated, AnalysisResults); AnalysisResultListT &ResultsList = AnalysisResultLists[&IR]; - for (typename AnalysisResultListT::iterator I = ResultsList.begin(), - E = ResultsList.end(); - I != E;) { - AnalysisKey *ID = I->first; + for (auto &AnalysisResultPair : ResultsList) { + // This is basically the same thing as Invalidator::invalidate, but we + // can't call it here because we're operating on the type-erased result. + // Moreover if we instead called invalidate() directly, it would do an + // unnecessary lookup in ResultsList. + AnalysisKey *ID = AnalysisResultPair.first; + auto &Result = *AnalysisResultPair.second; + + SmallDenseMap::iterator IMapI; + bool Inserted; + std::tie(IMapI, Inserted) = IsResultInvalidated.insert({ID, 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(ID).name() - << "\n"; - - InvalidatedIDs.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 erase the results that were marked above as invalidated. + for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) { + AnalysisKey *ID = I->first; + if (!IsResultInvalidated.lookup(ID)) { ++I; + continue; } + + if (DebugLogging) + dbgs() << "Invalidating analysis: " << this->lookupPass(ID).name() + << "\n"; + + I = ResultsList.erase(I); + AnalysisResults.erase({ID, &IR}); } - while (!InvalidatedIDs.empty()) - AnalysisResults.erase(std::make_pair(InvalidatedIDs.pop_back_val(), &IR)); if (ResultsList.empty()) AnalysisResultLists.erase(&IR); @@ -586,30 +683,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; @@ -683,7 +762,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 @@ -758,7 +839,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 @@ -26,6 +26,7 @@ namespace llvm { template class AnalysisManager; +class Invalidator; class PreservedAnalyses; /// \brief Implementation details of the pass manager interfaces. @@ -88,7 +89,8 @@ /// /// This concept is parameterized over the IR unit that this result pertains /// to. -template struct AnalysisResultConcept { +template +struct AnalysisResultConcept { virtual ~AnalysisResultConcept() = default; /// \brief Method to try and mark a result as invalid. @@ -96,12 +98,18 @@ /// When the outer analysis manager detects a change in some underlying /// unit of the IR, it will call this method on all of the results cached. /// - /// This method also receives a set of preserved analyses which can be used - /// to avoid invalidation because the pass which changed the underlying IR - /// took care to update or preserve the analysis result in some way. + /// \p PA is a set of preserved analyses which can be used to avoid + /// invalidation because the pass which changed the underlying IR took care + /// to update or preserve the analysis result in some way. + /// + /// \p Inv is typically a \c AnalysisManager::Invalidator object that can be + /// used by a particular analysis result to discover if other analyises + /// results are also invalidated in the event that this result depends on + /// them. See the documentation in the \c AnalysisManager for more details. /// /// \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 @@ -147,7 +155,7 @@ /// an invalidation handler. It is only selected when the invalidation handler /// is not part of the ResultT's interface. template ::Value> struct AnalysisResultModel; @@ -155,9 +163,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. @@ -180,7 +189,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()); } @@ -190,9 +200,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. @@ -211,8 +222,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; @@ -222,13 +234,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() = default; /// \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; @@ -241,8 +256,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. @@ -260,13 +277,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: lib/Analysis/CGSCCPassManager.cpp =================================================================== --- lib/Analysis/CGSCCPassManager.cpp +++ lib/Analysis/CGSCCPassManager.cpp @@ -15,6 +15,7 @@ namespace llvm { // Explicit instantiations for the core proxy templates. +template class AllAnalysesOn; template class AnalysisManager; template class PassManager; Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -100,7 +100,10 @@ : public AnalysisInfoMixin { public: struct Result { - bool invalidate(Function &, const PreservedAnalyses &) { return false; } + bool invalidate(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &) { + return false; + } }; TestImmutableFunctionAnalysis(int &Runs) : Runs(Runs) {} Index: unittests/IR/PassManagerTest.cpp =================================================================== --- unittests/IR/PassManagerTest.cpp +++ unittests/IR/PassManagerTest.cpp @@ -388,4 +388,107 @@ // 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 analysis pass and +/// uses it to serve queries. This requires the result to 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 AnalysisKey Key; + + int &Runs; +}; + +AnalysisKey TestIndirectFunctionAnalysis::Key; + +struct LambdaPass : public PassInfoMixin { + using FuncT = std::function; + + LambdaPass(FuncT Func) : Func(std::move(Func)) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { + return Func(F, AM); + } + + FuncT 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, invalidate + // - both analyses for "f", + // - just the underlying (indirect) analysis for "g", and + // - just the direct analysis for "h". + 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 each 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 indirect analysis is invalidated for each function (either directly or + // indirectly) and run twice for each. + EXPECT_EQ(6, IndirectAnalysisRuns); + + // There are five instructions in the module and we add the count three + // times. + EXPECT_EQ(5 * 3, InstrCount); +} }