Index: include/llvm/Analysis/CGSCCPassManager.h =================================================================== --- include/llvm/Analysis/CGSCCPassManager.h +++ include/llvm/Analysis/CGSCCPassManager.h @@ -145,13 +145,58 @@ } }; -extern template class InnerAnalysisManagerProxy; /// A proxy from a \c CGSCCAnalysisManager to a \c Module. typedef InnerAnalysisManagerProxy CGSCCAnalysisManagerModuleProxy; -extern template class OuterAnalysisManagerProxy; +/// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so +/// it can have access to the call graph in order to walk all the SCCs when +/// invalidating things. +template <> class CGSCCAnalysisManagerModuleProxy::Result { +public: + explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G) + : InnerAM(&InnerAM), G(&G) {} + + /// \brief Accessor for the analysis manager. + CGSCCAnalysisManager &getManager() { return *InnerAM; } + + /// \brief Handler for invalidation of the containing IR unit. + /// + /// If this analysis itself is preserved, then we assume that the set of \c + /// IR units that the inner analysis manager controls hasn't changed and + /// thus we don't need to invalidate *all* cached data associated with any + /// \c Module* in the \c CGSCCAnalysisManager. + /// + /// Regardless of whether this analysis is marked as preserved, all of the + /// analyses in the \c CGSCCAnalysisManager are potentially invalidated (for + /// the relevant inner set of their IR units) based on the set of preserved + /// analyses. + /// + /// Because this needs to understand the mapping from one IR unit to an + /// inner IR unit, this method isn't defined in the primary template. + /// Instead, each specialization of this template will need to provide an + /// explicit specialization of this method to handle that particular pair + /// of IR unit and inner CGSCCAnalysisManager. + bool invalidate(Module &M, const PreservedAnalyses &PA, + ModuleAnalysisManager::Invalidator &Inv); + +private: + CGSCCAnalysisManager *InnerAM; + LazyCallGraph *G; +}; + +/// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy +/// so it can pass the lazy call garph to the result. +template <> +CGSCCAnalysisManagerModuleProxy::Result +CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM); + +// Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern +// template. +extern template class InnerAnalysisManagerProxy; + +extern template class OuterAnalysisManagerProxy< + ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>; /// A proxy from a \c ModuleAnalysisManager to an \c SCC. typedef OuterAnalysisManagerProxy @@ -375,12 +420,12 @@ } while (!RCWorklist.empty()); } - // By definition we preserve the proxy. We also preserve all analyses on - // SCCs. 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. + // By definition we preserve the call garph, all SCC analyses, and the + // analysis proxies by handling them above and in any nested pass managers. + PA.preserve(); PA.preserve>(); PA.preserve(); + PA.preserve(); return PA; } @@ -397,12 +442,47 @@ return ModuleToPostOrderCGSCCPassAdaptor(std::move(Pass), DebugLogging); } -extern template class InnerAnalysisManagerProxy; /// A proxy from a \c FunctionAnalysisManager to an \c SCC. -typedef InnerAnalysisManagerProxy - FunctionAnalysisManagerCGSCCProxy; +/// +/// Note that this does not mirror the proxy from a \c FunctionAnalysisManager +/// to a \c Module, and instead indirects through that proxy. +/// +/// When a module pass runs and triggers invalidation, both the CGSCC and +/// Function analysis manager proxies on the module get an invalidation event. +/// We don't want to fully duplicate responsibility for most of the +/// invalidation logic. Instead, this layer is only responsible for SCC-local +/// invalidation events and works with the CGSCC proxy at the module layer to +/// delegate module-wide invalidation to the direct \c FunctionAnalysisManager +/// proxy at that layer. +class FunctionAnalysisManagerCGSCCProxy + : public AnalysisInfoMixin { +public: + class Result { + public: + explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {} + + /// \brief Accessor for the analysis manager. + FunctionAnalysisManager &getManager() { return *FAM; } + + bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, + CGSCCAnalysisManager::Invalidator &Inv); + + private: + FunctionAnalysisManager *FAM; + }; + + /// Computes the \c FunctionAnalysisManager and stores it in the result proxy. + Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &); + +private: + friend AnalysisInfoMixin; + static AnalysisKey Key; +}; + +// Ensure the \c FunctionAnalysisManagerCGSCCProxy is provided as an extern +// template. +extern template class InnerAnalysisManagerProxy< + FunctionAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>; extern template class OuterAnalysisManagerProxy; /// A proxy from a \c CGSCCAnalysisManager to a \c Function. Index: include/llvm/Analysis/LoopPassManager.h =================================================================== --- include/llvm/Analysis/LoopPassManager.h +++ include/llvm/Analysis/LoopPassManager.h @@ -38,11 +38,21 @@ /// pass manager infrastructure. typedef AnalysisManager LoopAnalysisManager; -extern template class InnerAnalysisManagerProxy; /// A proxy from a \c LoopAnalysisManager to a \c Function. typedef InnerAnalysisManagerProxy LoopAnalysisManagerFunctionProxy; +/// Specialization of the invalidate method for the \c +/// LoopAnalysisManagerFunctionProxy's result. +template <> +bool LoopAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + +// Ensure the \c LoopAnalysisManagerFunctionProxy is provided as an extern +// template. +extern template class InnerAnalysisManagerProxy; + extern template class OuterAnalysisManagerProxy; /// A proxy from a \c FunctionAnalysisManager to a \c Loop. typedef OuterAnalysisManagerProxy Index: include/llvm/IR/PassManager.h =================================================================== --- include/llvm/IR/PassManager.h +++ include/llvm/IR/PassManager.h @@ -739,63 +739,61 @@ public: class Result { public: - explicit Result(AnalysisManagerT &AM) : AM(&AM) {} - Result(Result &&Arg) : AM(std::move(Arg.AM)) { + explicit Result(AnalysisManagerT &InnerAM) : InnerAM(&InnerAM) {} + Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)) { // We have to null out the analysis manager in the moved-from state // because we are taking ownership of the responsibilty to clear the // analysis state. - Arg.AM = nullptr; + Arg.InnerAM = nullptr; } Result &operator=(Result &&RHS) { - AM = RHS.AM; + InnerAM = RHS.InnerAM; // We have to null out the analysis manager in the moved-from state // because we are taking ownership of the responsibilty to clear the // analysis state. - RHS.AM = nullptr; + RHS.InnerAM = nullptr; return *this; } ~Result() { - // AM is cleared in a moved from state where there is nothing to do. - if (!AM) + // InnerAM is cleared in a moved from state where there is nothing to do. + if (!InnerAM) return; // Clear out the analysis manager if we're being destroyed -- it means we // didn't even see an invalidate call when we got invalidated. - AM->clear(); + InnerAM->clear(); } /// \brief Accessor for the analysis manager. - AnalysisManagerT &getManager() { return *AM; } + AnalysisManagerT &getManager() { return *InnerAM; } - /// \brief Handler for invalidation of the module. + /// \brief Handler for invalidation of the containing IR unit. /// /// If this analysis itself is preserved, then we assume that the set of \c - /// Function objects in the \c Module hasn't changed and thus we don't need - /// to invalidate *all* cached data associated with a \c Function* in the \c - /// FunctionAnalysisManager. + /// IR units that the inner analysis manager controls hasn't changed and + /// thus we don't need to invalidate *all* cached data associated with any + /// \c IRUnitT* in the \c AnalysisManagerT. /// /// 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. + /// analyses in the \c AnalysisManagerT are potentially invalidated (for + /// the relevant inner set of their IR units) based on the set of preserved + /// analyses. + /// + /// Because this needs to understand the mapping from one IR unit to an + /// inner IR unit, this method isn't defined in the primary template. + /// Instead, each specialization of this template will need to provide an + /// explicit specialization of this method to handle that particular pair + /// of IR unit and inner AnalysisManagerT. 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 - // them. Just clear the entire manager. - if (!PA.preserved(InnerAnalysisManagerProxy::ID())) - AM->clear(); - - // Return false to indicate that this result is still a valid proxy. - return false; - } + typename AnalysisManager::Invalidator &Inv); private: - AnalysisManagerT *AM; + AnalysisManagerT *InnerAM; }; - explicit InnerAnalysisManagerProxy(AnalysisManagerT &AM) : AM(&AM) {} + explicit InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM) + : InnerAM(&InnerAM) {} /// \brief Run the analysis pass and create our proxy result object. /// @@ -806,9 +804,9 @@ /// 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(IRUnitT &IR, AnalysisManager &, + Result run(IRUnitT &IR, AnalysisManager &AM, ExtraArgTs...) { - return Result(*AM); + return Result(*InnerAM); } private: @@ -816,19 +814,29 @@ InnerAnalysisManagerProxy>; static AnalysisKey Key; - AnalysisManagerT *AM; + AnalysisManagerT *InnerAM; }; template AnalysisKey InnerAnalysisManagerProxy::Key; -extern template class InnerAnalysisManagerProxy; /// Provide the \c FunctionAnalysisManager to \c Module proxy. typedef InnerAnalysisManagerProxy FunctionAnalysisManagerModuleProxy; +/// Specialization of the invalidate method for the \c +/// FunctionAnalysisManagerModuleProxy's result. +template <> +bool FunctionAnalysisManagerModuleProxy::Result::invalidate( + Module &M, const PreservedAnalyses &PA, + ModuleAnalysisManager::Invalidator &Inv); + +// Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern +// template. +extern template class InnerAnalysisManagerProxy; + /// \brief A function analysis which acts as a proxy for a module analysis /// manager. /// Index: lib/Analysis/CGSCCPassManager.cpp =================================================================== --- lib/Analysis/CGSCCPassManager.cpp +++ lib/Analysis/CGSCCPassManager.cpp @@ -12,6 +12,8 @@ using namespace llvm; +// Explicit template instantiations and specialization defininitions for core +// template typedefs. namespace llvm { // Explicit instantiations for the core proxy templates. @@ -21,9 +23,9 @@ LazyCallGraph &, CGSCCUpdateResult &>; template class InnerAnalysisManagerProxy; template class OuterAnalysisManagerProxy; + LazyCallGraph::SCC, LazyCallGraph &>; template class InnerAnalysisManagerProxy; + LazyCallGraph::SCC, LazyCallGraph &>; template class OuterAnalysisManagerProxy; /// Explicitly specialize the pass manager run method to handle call graph @@ -83,6 +85,93 @@ return PA; } +bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( + Module &M, const PreservedAnalyses &PA, + ModuleAnalysisManager::Invalidator &Inv) { + // If this proxy or the call graph is going to be invalidated, we also need + // to clear all the keys coming from that analysis. + // + // We also directly invalidate the FAM's module proxy if necessary and if + // that proxy isn't preserved we can't preserve this proxy either. We rely on + // it to handle module -> function analysis invalidation in the face of + // structural changes and so if unavailable we conservatively clear the + // entire SCC layer as well rather than trying to do invaliadtion ourselves. + if (!PA.preserved() || + Inv.invalidate(M, PA) || + Inv.invalidate(M, PA)) { + InnerAM->clear(); + + // And the proxy itself should be marked as invalid so that we can observe + // the new call graph if and when created. This isn't strictly necessary + // because we cheat above, but is still useful. + return true; + } + + // Ok, we have a graph so we can propagate the invalidation down into it. + // Note that we do this even if the call graph is about to become invalid so + // that we trigger any secondary invalidation within the cached results for + // this inner analysis manager before we remove those results entirely. As an + // example, we want to first propagate the invalidation to any function + // analysis results that could be cached via a CGSCC proxy before we remove + // that proxy. + for (auto &RC : G->postorder_ref_sccs()) + for (auto &C : RC) + InnerAM->invalidate(C, PA); + + // Otherwise false to indicate that this result is still a valid proxy. + return false; +} + +template <> +CGSCCAnalysisManagerModuleProxy::Result +CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) { + // Force the Function analysis manager to also be available so that it can + // be accessed in an SCC analysis and proxied onward to function passes. + // FIXME: It is pretty awkward to just drop the result here and assert that + // we can find it again later. + (void)AM.getResult(M); + + return Result(*InnerAM, AM.getResult(M)); +} + +AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key; + +FunctionAnalysisManagerCGSCCProxy::Result +FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C, + CGSCCAnalysisManager &AM, + LazyCallGraph &CG) { + // Collect the FunctionAnalysisManager from the Module layer and use that to + // build the proxy result. + // + // This allows us to rely on the FunctionAnalysisMangaerModuleProxy to + // handle non-SCC parts of the invalidation of function analyses. + auto &MAM = AM.getResult(C, CG).getManager(); + Module &M = *C.begin()->getFunction().getParent(); + auto *FAMProxy = MAM.getCachedResult(M); + assert(FAMProxy && "The CGSCC pass manager requires that the FAM module " + "proxy is run on the module prior to entering the CGSCC " + "walk."); + + // Note that we hard-code invalidation handling of this proxy in the CGSCC + // analysis manager's Module proxy. This avoids the need to do anything + // special here to recompute all of this if ever the FAM's module proxy goes + // away. + return Result(FAMProxy->getManager()); +} + +bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate( + LazyCallGraph::SCC &C, const PreservedAnalyses &PA, + CGSCCAnalysisManager::Invalidator &Inv) { + for (LazyCallGraph::Node &N : C) + FAM->invalidate(N.getFunction(), PA); + + // This proxy doesn't need to handle invalidation itself. Instead, the + // module-level CGSCC proxy handles it above by ensuring that if the + // module-level FAM proxy becomes invalid the entire SCC layer is cleared + // which will include this proxy. + return false; +} + } // End llvm namespace namespace { Index: lib/Analysis/LoopPassManager.cpp =================================================================== --- lib/Analysis/LoopPassManager.cpp +++ lib/Analysis/LoopPassManager.cpp @@ -17,12 +17,30 @@ using namespace llvm; -// Explicit instantiations for core typedef'ed templates. +// Explicit template instantiations and specialization defininitions for core +// template typedefs. namespace llvm { template class PassManager; template class AnalysisManager; template class InnerAnalysisManagerProxy; template class OuterAnalysisManagerProxy; + +template <> +bool LoopAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + // 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(LoopAnalysisManagerFunctionProxy::ID())) + InnerAM->clear(); + + // FIXME: Proper suppor for invalidation isn't yet implemented for the LPM. + + // Return false to indicate that this result is still a valid proxy. + return false; +} } PreservedAnalyses llvm::getLoopPassPreservedAnalyses() { Index: lib/IR/PassManager.cpp =================================================================== --- lib/IR/PassManager.cpp +++ lib/IR/PassManager.cpp @@ -13,7 +13,8 @@ using namespace llvm; -// Explicit template instantiations for core template typedefs. +// Explicit template instantiations and specialization defininitions for core +// template typedefs. namespace llvm { template class AllAnalysesOn; template class AllAnalysesOn; @@ -23,6 +24,31 @@ template class AnalysisManager; template class InnerAnalysisManagerProxy; template class OuterAnalysisManagerProxy; + +template <> +bool FunctionAnalysisManagerModuleProxy::Result::invalidate( + Module &M, const PreservedAnalyses &PA, + ModuleAnalysisManager::Invalidator &Inv) { + // If this proxy isn't marked as preserved, then even if the result remains + // valid, the key itself may no longer be valid, so we clear everything. + // + // Note that in order to preserve this proxy, a module pass must ensure that + // the FAM has been completely updated to handle the deletion of functions. + // Specifically, any FAM-cached results for those functions need to have been + // forcibly cleared. When preserved, this proxy will only invalidate results + // cached on functions *still in the module* at the end of the module pass. + if (!PA.preserved(FunctionAnalysisManagerModuleProxy::ID())) { + InnerAM->clear(); + return true; + } + + // Otherwise propagate the invalidation event to all the remaining IR units. + for (Function &F : M) + InnerAM->invalidate(F, PA); + + // Return false to indicate that this result is still a valid proxy. + return false; +} } AnalysisKey PreservedAnalyses::AllAnalysesKey; Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -769,7 +769,6 @@ ModuleAnalysisManager &MAM) { MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); }); - CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(FAM); }); CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); }); FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); }); FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -79,6 +79,7 @@ #define CGSCC_ANALYSIS(NAME, CREATE_PASS) #endif CGSCC_ANALYSIS("no-op-cgscc", NoOpCGSCCAnalysis()) +CGSCC_ANALYSIS("fam-proxy", FunctionAnalysisManagerCGSCCProxy()) #undef CGSCC_ANALYSIS #ifndef CGSCC_PASS Index: test/Other/new-pass-manager.ll =================================================================== --- test/Other/new-pass-manager.ll +++ test/Other/new-pass-manager.ll @@ -20,7 +20,8 @@ ; RUN: | FileCheck %s --check-prefix=CHECK-CGSCC-PASS ; CHECK-CGSCC-PASS: Starting llvm::Module pass manager run ; CHECK-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor -; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}> +; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}CGSCCAnalysisManager{{.*}}> +; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}FunctionAnalysisManager{{.*}}> ; CHECK-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis ; CHECK-CGSCC-PASS-NEXT: Running an SCC pass across the RefSCC: [(foo)] ; CHECK-CGSCC-PASS-NEXT: Starting CGSCC pass manager run @@ -378,7 +379,8 @@ ; RUN: | FileCheck %s --check-prefix=CHECK-REPEAT-CGSCC-PASS ; CHECK-REPEAT-CGSCC-PASS: Starting llvm::Module pass manager run ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor -; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}> +; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}CGSCCAnalysisManager{{.*}}> +; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}FunctionAnalysisManager{{.*}}> ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running an SCC pass across the RefSCC: [(foo)] ; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -122,6 +122,24 @@ AnalysisKey TestImmutableFunctionAnalysis::Key; +struct LambdaModulePass : public PassInfoMixin { + template + LambdaModulePass(T &&Arg) : Func(std::forward(Arg)) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + LambdaModulePass(LambdaModulePass &&Arg) : Func(std::move(Arg.Func)) {} + LambdaModulePass &operator=(LambdaModulePass &&RHS) { + Func = std::move(RHS.Func); + return *this; + } + + PreservedAnalyses run(Module &F, ModuleAnalysisManager &AM) { + return Func(F, AM); + } + + std::function Func; +}; + struct LambdaSCCPass : public PassInfoMixin { template LambdaSCCPass(T &&Arg) : Func(std::forward(Arg)) {} // We have to explicitly define all the special member functions because MSVC @@ -232,7 +250,7 @@ MAM.registerPass([&] { return LazyCallGraphAnalysis(); }); MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); }); - CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(FAM); }); + CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(); }); CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); }); FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); }); FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); @@ -257,6 +275,14 @@ MPM.addPass(RequireAnalysisPass()); CGSCCPassManager CGPM1(/*DebugLogging*/ true); + FunctionPassManager FPM1(/*DebugLogging*/ true); + int FunctionPassRunCount1 = 0; + FPM1.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) { + ++FunctionPassRunCount1; + return PreservedAnalyses::none(); + })); + CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + int SCCPassRunCount1 = 0; int AnalyzedInstrCount1 = 0; int AnalyzedSCCFunctionCount1 = 0; @@ -289,23 +315,36 @@ return PreservedAnalyses::all(); })); - FunctionPassManager FPM1(/*DebugLogging*/ true); - int FunctionPassRunCount1 = 0; - FPM1.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) { - ++FunctionPassRunCount1; - return PreservedAnalyses::all(); + FunctionPassManager FPM2(/*DebugLogging*/ true); + int FunctionPassRunCount2 = 0; + FPM2.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) { + ++FunctionPassRunCount2; + return PreservedAnalyses::none(); })); - CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + FunctionPassManager FPM3(/*DebugLogging*/ true); + int FunctionPassRunCount3 = 0; + FPM3.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) { + ++FunctionPassRunCount3; + return PreservedAnalyses::none(); + })); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM3))); + MPM.run(*M, MAM); + EXPECT_EQ(4, SCCPassRunCount1); + EXPECT_EQ(6, FunctionPassRunCount1); + EXPECT_EQ(6, FunctionPassRunCount2); + EXPECT_EQ(6, FunctionPassRunCount3); + EXPECT_EQ(1, ModuleAnalysisRuns); EXPECT_EQ(4, SCCAnalysisRuns); EXPECT_EQ(6, FunctionAnalysisRuns); EXPECT_EQ(6, ImmutableFunctionAnalysisRuns); - EXPECT_EQ(4, SCCPassRunCount1); EXPECT_EQ(14, AnalyzedInstrCount1); EXPECT_EQ(6, AnalyzedSCCFunctionCount1); EXPECT_EQ(4 * 6, AnalyzedModuleFunctionCount1); @@ -473,4 +512,329 @@ EXPECT_FALSE(FoundModuleAnalysis3); } +// Test that a Module pass which fails to preserve an SCC analysis in fact +// invalidates that analysis. +TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysis) { + int SCCAnalysisRuns = 0; + CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); }); + + { + // Initial module pass for the basic case where we preserve the CGSCC bits + // but not the SCC analysis and have to re-run it. + ModulePassManager MPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + CGSCCPassManager CGPM1(/*DebugLogging*/ true); + CGPM1.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + + // Now run a module pass that preserves the LazyCallGraph and the proxy but + // not the SCC analysis. + MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) { + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again. This + // will trigger re-running it. + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + + MPM.run(*M, MAM); + // Two runs and four SCCs. + EXPECT_EQ(2 * 4, SCCAnalysisRuns); + } + { + // Next module pass checks that marking the SCC analysis preserved is + // sufficient. This should only run the analysis once for each SCC. + SCCAnalysisRuns = 0; + MAM.clear(); + CGAM.clear(); + ModulePassManager MPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + CGSCCPassManager CGPM1(/*DebugLogging*/ true); + CGPM1.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + + // Now run a module pass that preserves each of the necessary components + // (but not everything). + MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) { + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again but find + // it in the cache. + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + + MPM.run(*M, MAM); + // Four SCCs + EXPECT_EQ(4, SCCAnalysisRuns); + } + { + // Final module pass checks that even when the analysis is preserved, if the + // SCC information isn't we still nuke things because the SCC keys could + // change. + SCCAnalysisRuns = 0; + MAM.clear(); + CGAM.clear(); + ModulePassManager MPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + CGSCCPassManager CGPM1(/*DebugLogging*/ true); + CGPM1.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + + // Now run a module pass that preserves the analysis but not the call + // graph or proxy. + MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) { + PreservedAnalyses PA; + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again. + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + + MPM.run(*M, MAM); + // Two runs and four SCCs. + EXPECT_EQ(2 * 4, SCCAnalysisRuns); + } +} + +// Test that an SCC pass which fails to preserve a Function analysis in fact +// invalidates that analysis. +TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesFunctionAnalysis) { + int FunctionAnalysisRuns = 0; + FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); }); + + // Create a very simple module with a single function & SCC to make testing + // these issues much easier. + std::unique_ptr M = parseIR("declare void @g()\n" + "declare void @h()\n" + "define void @f() {\n" + "entry:\n" + " call void @g()\n" + " call void @h()\n" + " ret void\n" + "}\n"); + { + // Initial SCC pass for the basic case where we preserve the CGSCC bits but + // not the SCC analysis and have to re-run it. + CGSCCPassManager CGPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + FunctionPassManager FPM1(/*DebugLogging*/ true); + FPM1.addPass(RequireAnalysisPass()); + CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + + // Now run a module pass that preserves the LazyCallGraph and proxy but not + // the SCC analysis. + CGPM.addPass( + LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &, + LazyCallGraph &, CGSCCUpdateResult &) { + PreservedAnalyses PA; + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again. This + // will trigger re-running it. + FunctionPassManager FPM2(/*DebugLogging*/ true); + FPM2.addPass(RequireAnalysisPass()); + CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2))); + + ModulePassManager MPM(/*DebugLogging*/ true); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + MPM.run(*M, MAM); + EXPECT_EQ(2, FunctionAnalysisRuns); + } + { + // The next pass checks that marking the SCC analysis preserved is + // sufficient. This should only run the analysis once the SCC. + FunctionAnalysisRuns = 0; + CGAM.clear(); + FAM.clear(); + CGSCCPassManager CGPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + FunctionPassManager FPM1(/*DebugLogging*/ true); + FPM1.addPass(RequireAnalysisPass()); + CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + + // Now run a module pass that preserves each of the necessary components + // (but + // not everything). + CGPM.addPass( + LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &, + LazyCallGraph &, CGSCCUpdateResult &) { + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again but find + // it in the cache. + FunctionPassManager FPM2(/*DebugLogging*/ true); + FPM2.addPass(RequireAnalysisPass()); + CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2))); + + ModulePassManager MPM(/*DebugLogging*/ true); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + MPM.run(*M, MAM); + EXPECT_EQ(1, FunctionAnalysisRuns); + } + + // Note that there is no test for invalidating the call graph or other + // structure because there is no mechanism to do that from within a CGSCC + // pass. Instead, such a pass has to directly update the call graph + // structure. +} + +// Test that a madule pass invalidates function analyses even when only the +// CGSCC proxies are used and thus there isn't +// a FunctionAnalysisManagerModuleProxy. +TEST_F(CGSCCPassManagerTest, + TestModulePassInvalidatesFunctionAnalysisViaSCCProxy) { + MAM.registerPass([&] { return LazyCallGraphAnalysis(); }); + + int FunctionAnalysisRuns = 0; + FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); }); + + // Check that when everything but the function analysis is preserved by + // a module pass it is invalidated in the second nested function pass. + { + ModulePassManager MPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + FunctionPassManager FPM1(/*DebugLogging*/ true); + FPM1.addPass(RequireAnalysisPass()); + CGSCCPassManager CGPM1(/*DebugLogging*/ true); + CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + + // Now run a module pass that preserves the LazyCallGraph and proxy but not + // the Function analysis. + MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) { + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again. This + // will trigger re-running it. + FunctionPassManager FPM2(/*DebugLogging*/ true); + FPM2.addPass(RequireAnalysisPass()); + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + + MPM.run(*M, MAM); + // Two runs and 6 functions. + EXPECT_EQ(2 * 6, FunctionAnalysisRuns); + } + FunctionAnalysisRuns = 0; + FAM.clear(); + MAM.clear(); + CGAM.clear(); + + // Next check that by marking the function pass and FAM proxy as preserved, + // this propagates all the way through. + { + ModulePassManager MPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + FunctionPassManager FPM1(/*DebugLogging*/ true); + FPM1.addPass(RequireAnalysisPass()); + CGSCCPassManager CGPM1(/*DebugLogging*/ true); + CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + + // Now run a module pass that preserves the LazyCallGraph, the proxy, and + // the Function analysis. + MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) { + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again. This + // will trigger re-running it. + FunctionPassManager FPM2(/*DebugLogging*/ true); + FPM2.addPass(RequireAnalysisPass()); + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + + MPM.run(*M, MAM); + // One run and 6 functions. + EXPECT_EQ(6, FunctionAnalysisRuns); + } + FunctionAnalysisRuns = 0; + FAM.clear(); + MAM.clear(); + CGAM.clear(); + + // Next check that if the lazy call graph itself isn't preserved we still + // manage to invalidate everything. + { + ModulePassManager MPM(/*DebugLogging*/ true); + + // First force the analysis to be run. + FunctionPassManager FPM1(/*DebugLogging*/ true); + FPM1.addPass(RequireAnalysisPass()); + CGSCCPassManager CGPM1(/*DebugLogging*/ true); + CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1))); + + // Now run a module pass that preserves the LazyCallGraph but not the + // Function analysis. + MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) { + PreservedAnalyses PA; + return PA; + })); + + // And now a second CGSCC run which requires the SCC analysis again. This + // will trigger re-running it. + FunctionPassManager FPM2(/*DebugLogging*/ true); + FPM2.addPass(RequireAnalysisPass()); + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2))); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + + MPM.run(*M, MAM); + // Two runs and 6 functions. + EXPECT_EQ(2 * 6, FunctionAnalysisRuns); + } +} } Index: unittests/IR/PassManagerTest.cpp =================================================================== --- unittests/IR/PassManagerTest.cpp +++ unittests/IR/PassManagerTest.cpp @@ -91,19 +91,6 @@ } }; -struct TestMinPreservingModulePass - : PassInfoMixin { - PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) { - PreservedAnalyses PA; - - // Force running an analysis. - (void)AM.getResult(M); - - PA.preserve(); - return PA; - } -}; - struct TestFunctionPass : PassInfoMixin { TestFunctionPass(int &RunCount, int &AnalyzedInstrCount, int &AnalyzedFunctionCount, @@ -215,11 +202,11 @@ } TEST_F(PassManagerTest, Basic) { - FunctionAnalysisManager FAM; + FunctionAnalysisManager FAM(/*DebugLogging*/ true); int FunctionAnalysisRuns = 0; FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); }); - ModuleAnalysisManager MAM; + ModuleAnalysisManager MAM(/*DebugLogging*/ true); int ModuleAnalysisRuns = 0; MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); }); MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); @@ -233,11 +220,11 @@ int AnalyzedFunctionCount1 = 0; { // Pointless scoped copy to test move assignment. - ModulePassManager NestedMPM; + ModulePassManager NestedMPM(/*DebugLogging*/ true); FunctionPassManager FPM; { // Pointless scope to test move assignment. - FunctionPassManager NestedFPM; + FunctionPassManager NestedFPM(/*DebugLogging*/ true); NestedFPM.addPass(TestFunctionPass( FunctionPassRunCount1, AnalyzedInstrCount1, AnalyzedFunctionCount1)); FPM = std::move(NestedFPM); @@ -255,7 +242,7 @@ int AnalyzedInstrCount2 = 0; int AnalyzedFunctionCount2 = 0; { - FunctionPassManager FPM; + FunctionPassManager FPM(/*DebugLogging*/ true); FPM.addPass(TestFunctionPass(FunctionPassRunCount2, AnalyzedInstrCount2, AnalyzedFunctionCount2)); MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); @@ -268,15 +255,16 @@ int AnalyzedInstrCount3 = 0; int AnalyzedFunctionCount3 = 0; { - FunctionPassManager FPM; + FunctionPassManager FPM(/*DebugLogging*/ true); FPM.addPass(TestFunctionPass(FunctionPassRunCount3, AnalyzedInstrCount3, AnalyzedFunctionCount3)); FPM.addPass(TestInvalidationFunctionPass("f")); MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); } - // A fourth function pass manager but with a minimal intervening passes. - MPM.addPass(TestMinPreservingModulePass()); + // A fourth function pass manager but with only preserving intervening + // passes but triggering the module analysis. + MPM.addPass(RequireAnalysisPass()); int FunctionPassRunCount4 = 0; int AnalyzedInstrCount4 = 0; int AnalyzedFunctionCount4 = 0; @@ -287,12 +275,13 @@ MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); } - // A fifth function pass manager but which uses only cached results. + // A fifth function pass manager which invalidates one function first but + // uses only cached results. int FunctionPassRunCount5 = 0; int AnalyzedInstrCount5 = 0; int AnalyzedFunctionCount5 = 0; { - FunctionPassManager FPM; + FunctionPassManager FPM(/*DebugLogging*/ true); FPM.addPass(TestInvalidationFunctionPass("f")); FPM.addPass(TestFunctionPass(FunctionPassRunCount5, AnalyzedInstrCount5, AnalyzedFunctionCount5, @@ -317,16 +306,17 @@ EXPECT_EQ(0, AnalyzedFunctionCount3); EXPECT_EQ(3, FunctionPassRunCount4); EXPECT_EQ(5, AnalyzedInstrCount4); - EXPECT_EQ(0, AnalyzedFunctionCount4); + EXPECT_EQ(9, AnalyzedFunctionCount4); EXPECT_EQ(3, FunctionPassRunCount5); EXPECT_EQ(2, AnalyzedInstrCount5); // Only 'g' and 'h' were cached. - EXPECT_EQ(0, AnalyzedFunctionCount5); + EXPECT_EQ(9, AnalyzedFunctionCount5); // Validate the analysis counters: // first run over 3 functions, then module pass invalidates // second run over 3 functions, nothing invalidates // third run over 0 functions, but 1 function invalidated // fourth run over 1 function + // fifth run invalidates 1 function first, but runs over 0 functions EXPECT_EQ(7, FunctionAnalysisRuns); EXPECT_EQ(1, ModuleAnalysisRuns);