Index: include/llvm/IR/PassManager.h =================================================================== --- include/llvm/IR/PassManager.h +++ include/llvm/IR/PassManager.h @@ -41,6 +41,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/TinyPtrVector.h" #include "llvm/IR/Function.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManagerInternal.h" @@ -83,15 +84,47 @@ return PA; } - /// \brief Mark a particular pass as preserved, adding it to the set. + /// Mark a particular analysis or analysis set as preserved. + /// + /// Both specific analysis passes and abstract analysis sets can be + /// preserved. See the query API below to understand how sets and analyses + /// interact. template void preserve() { preserve(PassT::ID()); } - /// \brief Mark an abstract ID as preserved, adding it to the set. + /// Mark an abstract ID as preserved, adding it to the set. void preserve(AnalysisKey *ID) { + // Clear this ID from the explicit not-preserved set if present. + NotPreservedAnalysisIDs.erase(ID); + + // If we're not already preserving all analyses (other than those in + // NotPreservedAnalysisIDs). if (!areAllPreserved()) PreservedAnalysisIDs.insert(ID); } + /// Mark a particular pass as abandoned, removing it from the preserved set + /// even if covered by some other set or previously explicitly marked as + /// preserved. + /// + /// Note that you can only abandon a specific analysis, not a *set* of + /// analyses. + template void abandon() { abandon(PassT::ID()); } + + /// Mark a particular analysis ID as abandoned, removing it from the + /// preserved set even if covered by some other set. + /// + /// Note that you can only abandon a specific analysis, not a *set* of + /// analyses. + void abandon(AnalysisKey *ID) { + // Clear this ID from the preserved set if present. + PreservedAnalysisIDs.erase(ID); + + // And add it to the explicitly not-preserved set so, even if there is some + // general set being preserved, that won't cause this particular analysis + // to be preserved. + NotPreservedAnalysisIDs.insert(ID); + } + /// \brief Intersect this set with another in place. /// /// This is a mutating operation on this preserved set, removing all @@ -100,9 +133,15 @@ if (Arg.areAllPreserved()) return; if (areAllPreserved()) { - PreservedAnalysisIDs = Arg.PreservedAnalysisIDs; + *this = Arg; return; } + // The intersection requires the *union* of the explicitly not preserved + // IDs and the *intersection* of the preserved IDs. + for (auto ID : Arg.NotPreservedAnalysisIDs) { + PreservedAnalysisIDs.erase(ID); + NotPreservedAnalysisIDs.insert(ID); + } for (auto ID : PreservedAnalysisIDs) if (!Arg.PreservedAnalysisIDs.count(ID)) PreservedAnalysisIDs.erase(ID); @@ -116,27 +155,60 @@ if (Arg.areAllPreserved()) return; if (areAllPreserved()) { - PreservedAnalysisIDs = std::move(Arg.PreservedAnalysisIDs); + *this = std::move(Arg); return; } + // The intersection requires the *union* of the explicitly not preserved + // IDs and the *intersection* of the preserved IDs. + for (auto ID : Arg.NotPreservedAnalysisIDs) { + PreservedAnalysisIDs.erase(ID); + NotPreservedAnalysisIDs.insert(ID); + } for (auto ID : PreservedAnalysisIDs) if (!Arg.PreservedAnalysisIDs.count(ID)) PreservedAnalysisIDs.erase(ID); } - /// \brief Query whether a pass is marked as preserved by this set. - template bool preserved() const { - return preserved(PassT::ID()); + /// Query whether a particular analysis or one of the sets covering this + /// analysis is marked as preserved by this set. + /// + /// The list of sets following the analysis may be empty or may contain, for + /// example, a set abstractly representing all analyses on a particular unit + /// of IR or all analysis which rely only on the CFG being preserved, etc. + template bool preserved() const { + return preserved(AnalysisT::ID(), {SetTs::ID()...}); } - /// \brief Query whether an abstract pass ID is marked as preserved by this - /// set. - bool preserved(AnalysisKey *ID) const { - return PreservedAnalysisIDs.count(&AllAnalysesKey) || - PreservedAnalysisIDs.count(ID); + /// Query whether a particular analysis ID or an ID representing one of the + /// sets covering that analysis ID is marked as preserved by this set. + /// + /// The list of set IDs following the analysis ID may be empty or may + /// contain, for example, an ID for a set abstractly representing all + /// analyses on a particular unit of IR or all analyses which rely only on + /// the CFG being preserved, etc. + bool preserved(AnalysisKey *ID, + std::initializer_list SetIDs = {}) const { +#ifndef NDEBUG + for (auto SetID : SetIDs) + assert(!NotPreservedAnalysisIDs.count(SetID) && + "Either an analysis ID was provided as an abstract set ID, or a " + "set ID was abandoned."); +#endif + if (NotPreservedAnalysisIDs.count(ID)) + return false; + if (PreservedAnalysisIDs.count(ID)) + return true; + if (PreservedAnalysisIDs.count(&AllAnalysesKey)) + return true; + for (auto SetID : SetIDs) + if (PreservedAnalysisIDs.count(SetID)) + return true; + + // Neither the analysis nor any covering set was preserved. + return false; } - /// \brief Query whether all of the analyses in the set are preserved. + /// Query whether all of the analyses in the set are preserved. bool preserved(const PreservedAnalyses& Arg) { if (Arg.areAllPreserved()) return areAllPreserved(); @@ -146,19 +218,31 @@ return true; } - /// \brief Test whether all passes are preserved. + /// Test whether all passes are preserved. /// /// This is used primarily to optimize for the case of no changes which will /// common in many scenarios. bool areAllPreserved() const { - return PreservedAnalysisIDs.count(&AllAnalysesKey); + return NotPreservedAnalysisIDs.empty() && + PreservedAnalysisIDs.count(&AllAnalysesKey); } private: - // A special key used to indicate all analyses. + /// A special key used to indicate all analyses. static AnalysisKey AllAnalysesKey; + /// The set of preserved analyses. + /// + /// Unless covered directly or via some set here, analyses are assumed to not + /// be preserved. SmallPtrSet PreservedAnalysisIDs; + + /// The set of explicitly not-preserved analyses. + /// + /// This can override a set which is preserved above and make a specific + /// analysis not preserved. It always wins over the above set and should not + /// include any synthetic set IDs such as the "all" ID. + SmallPtrSet NotPreservedAnalysisIDs; }; // Forward declare the analysis manager template. @@ -399,8 +483,34 @@ /// any dependecies on it will become invalid as a result. template bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { - AnalysisKey *ID = PassT::ID(); + typedef detail::AnalysisResultModel + ResultModelT; + return invalidateImpl(PassT::ID(), IR, PA); + } + /// A type-erased variant of the above invalidate method with the same core + /// API other than passing an analysis ID rather than an analysis type + /// parameter. + /// + /// This is sadly less efficient than the above routine which leverages the + /// type parameter to avoid the type erasure overhead, but in some cases + /// the caller needed to do type erasure themselves. + bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) { + return invalidateImpl<>(ID, IR, PA); + } + + private: + friend class AnalysisManager; + + /// Helper to implemente the invalidate methods above, see their + /// documentation for the detailed interface. This implementation is + /// factored to allow common code to be used whether we can compute + /// a concrete result type or we need to use the type erased concept type. + template + bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR, + const PreservedAnalyses &PA) { // If we've already visited this pass, return true if it was invalidated // and false otherwise. auto IMapI = IsResultInvalidated.find(ID); @@ -414,28 +524,21 @@ "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); + auto &Result = static_cast(*RI->second->second); // Insert into the map whether the result should be invalidated and // return that. Note that we cannot re-use IMapI and must do a fresh // insert here as calling the invalidate routine could (recursively) // insert things into the map making any iterator or reference invalid. bool Inserted; - std::tie(IMapI, Inserted) = IsResultInvalidated.insert( - {ID, ResultModel.invalidate(IR, PA, *this)}); + std::tie(IMapI, Inserted) = + IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)}); (void)Inserted; assert(Inserted && "Should not have already inserted this ID, likely " "indicates a dependency cycle!"); return IMapI->second; } - private: - friend class AnalysisManager; - Invalidator(SmallDenseMap &IsResultInvalidated, const AnalysisResultMapT &Results) : IsResultInvalidated(IsResultInvalidated), Results(Results) {} @@ -576,8 +679,10 @@ /// Walk through all of the analyses pertaining to this unit of IR and /// invalidate them unless they are preserved by the PreservedAnalyses set. void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { - // Short circuit for common cases of all analyses being preserved. - if (PA.areAllPreserved() || PA.preserved>()) + // We can only short circuit if *all* are preserved. Even if a set for this + // IR unit is preserved there might be abandoned analyses that need to be + // invalidated. + if (PA.areAllPreserved()) return; if (DebugLogging) @@ -857,9 +962,13 @@ /// cannot request a module analysis to actually run. Instead, the user must /// rely on the \c getCachedResult API. /// -/// This proxy *doesn't* manage the invalidation in any way. That is handled by -/// the recursive return path of each layer of the pass manager and the -/// returned PreservedAnalysis set. +/// The invalidation provided by this proxy involves tracking when an +/// invalidation event in the outer analysis manager needs to trigger an +/// invalidation of a particular analysis on this IR unit. +/// +/// Because outer analyses aren't invalidated while these IR units are being +/// precessed, we have to register and handle these as deferred invalidation +/// events. template class OuterAnalysisManagerProxy : public AnalysisInfoMixin< @@ -879,8 +988,38 @@ return false; } + /// Register a deferred invalidation event for when the outer analysis + /// manager processes its invalidations. + template + void registerOuterAnalysisInvalidation() { + AnalysisKey *OuterID = OuterAnalysisT::ID(); + AnalysisKey *InvalidatedID = InvalidatedAnalysisT::ID(); + + auto &InvalidatedIDList = OuterAnalysisInvalidationMap[OuterID]; + // Note, this is a linear scan. If we end up with large numbers of + // analyses that all trigger invalidation on the same outer analysis, + // this entire system should be changed to some other deterministic + // data structure such as a `SetVector` of a pair of pointers. + auto InvalidatedIt = std::find(InvalidatedIDList.begin(), + InvalidatedIDList.end(), InvalidatedID); + if (InvalidatedIt == InvalidatedIDList.end()) + InvalidatedIDList.push_back(InvalidatedID); + } + + /// Access the map from outer analyses to deferred invalidation requiring + /// analyses. + const SmallDenseMap, 2> & + getOuterInvalidations() const { + return OuterAnalysisInvalidationMap; + } + private: const AnalysisManagerT *AM; + + /// A map from an outer analysis ID to the set of this IR-unit's analyses + /// which need to be invalidated. + SmallDenseMap, 2> + OuterAnalysisInvalidationMap; }; OuterAnalysisManagerProxy(const AnalysisManagerT &AM) : AM(&AM) {} Index: include/llvm/IR/PassManagerInternal.h =================================================================== --- include/llvm/IR/PassManagerInternal.h +++ include/llvm/IR/PassManagerInternal.h @@ -25,6 +25,7 @@ namespace llvm { +template class AllAnalysesOn; template class AnalysisManager; class Invalidator; class PreservedAnalyses; @@ -191,7 +192,7 @@ // ones that use the trivial behavior. bool invalidate(IRUnitT &, const PreservedAnalysesT &PA, InvalidatorT &) override { - return !PA.preserved(PassT::ID()); + return !PA.template preserved>(); } ResultT Result; Index: lib/Analysis/CGSCCPassManager.cpp =================================================================== --- lib/Analysis/CGSCCPassManager.cpp +++ lib/Analysis/CGSCCPassManager.cpp @@ -89,6 +89,10 @@ bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( Module &M, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &Inv) { + // If literally everything is preserved, we're done. + if (PA.areAllPreserved()) + return false; // This is still a valid proxy. + // If this proxy or the call graph is going to be invalidated, we also need // to clear all the keys coming from that analysis. // @@ -96,8 +100,8 @@ // 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 it's unavailable we conservatively clear the - // entire SCC layer as well rather than trying to do invaliadtion ourselves. - if (!PA.preserved() || + // entire SCC layer as well rather than trying to do invalidation ourselves. + if (!PA.preserved>() || Inv.invalidate(M, PA) || Inv.invalidate(M, PA)) { InnerAM->clear(); @@ -108,10 +112,45 @@ return true; } + // Directly check if the relevant set is preserved so we can short circuit + // invalidating SCCs below without re-querying the preserved set. + bool AreSCCAnalysesPreserved = + PA.preserved>(); + // Ok, we have a graph, so we can propagate the invalidation down into it. for (auto &RC : G->postorder_ref_sccs()) - for (auto &C : RC) - InnerAM->invalidate(C, PA); + for (auto &C : RC) { + Optional InnerPA; + + // Check to see whether the preserved set needs to be adjusted based on + // module-level analysis invalidation triggering deferred invalidation + // for this SCC. + if (auto *OuterProxy = + InnerAM->getCachedResult(C)) + for (const auto &OuterInvalidationPair : + OuterProxy->getOuterInvalidations()) { + AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; + const auto &InnerAnalysisIDs = OuterInvalidationPair.second; + if (Inv.invalidate(OuterAnalysisID, M, PA)) { + if (!InnerPA) + InnerPA = PA; + for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) + InnerPA->abandon(InnerAnalysisID); + } + } + + // Check if we needed a custom PA set. If so we'll need to run the inner + // invalidation. + if (InnerPA) { + InnerAM->invalidate(C, *InnerPA); + continue; + } + + // Otherwise we only need to do invalidation if the original PA set didn't + // preserve all SCC analyses. + if (!AreSCCAnalysesPreserved) + InnerAM->invalidate(C, PA); + } // Return false to indicate that this result is still a valid proxy. return false; Index: lib/IR/PassManager.cpp =================================================================== --- lib/IR/PassManager.cpp +++ lib/IR/PassManager.cpp @@ -29,6 +29,10 @@ bool FunctionAnalysisManagerModuleProxy::Result::invalidate( Module &M, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &Inv) { + // If literally everything is preserved, we're done. + if (PA.areAllPreserved()) + return false; // This is still a valid proxy. + // 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. // @@ -37,14 +41,49 @@ // 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())) { + if (!PA.preserved>()) { InnerAM->clear(); return true; } - // Otherwise propagate the invalidation event to all the remaining IR units. - for (Function &F : M) - InnerAM->invalidate(F, PA); + // Directly check if the relevant set is preserved. + bool AreFunctionAnalysesPreserved = PA.preserved>(); + + // Now walk all the functions to see if any inner analysis invalidation is + // necessary. + for (Function &F : M) { + Optional FunctionPA; + + // Check to see whether the preserved set needs to be pruned based on + // module-level analysis invalidation that triggers deferred invalidation + // registered with the outer analysis manager proxy for this function. + if (auto *OuterProxy = + InnerAM->getCachedResult(F)) + for (const auto &OuterInvalidationPair : + OuterProxy->getOuterInvalidations()) { + AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; + const auto &InnerAnalysisIDs = OuterInvalidationPair.second; + if (Inv.invalidate(OuterAnalysisID, M, PA)) { + if (!FunctionPA) + FunctionPA = PA; + for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) + FunctionPA->abandon(InnerAnalysisID); + } + } + + // Check if we needed a custom PA set, and if so we'll need to run the + // inner invalidation. + if (FunctionPA) { + InnerAM->invalidate(F, *FunctionPA); + continue; + } + + // Otherwise we only need to do invalidation if the original PA set didn't + // preserve all function analyses. + if (!AreFunctionAnalysesPreserved) + InnerAM->invalidate(F, PA); + } // Return false to indicate that this result is still a valid proxy. return false; Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -820,4 +820,264 @@ // Two runs and 6 functions. EXPECT_EQ(2 * 6, FunctionAnalysisRuns); } + +/// A test CGSCC-level 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. +/// +/// FIXME: Currently this doesn't also depend on a function analysis and if it +/// did we would fail to invalidate it correctly. +struct TestIndirectSCCAnalysis + : public AnalysisInfoMixin { + struct Result { + Result(TestSCCAnalysis::Result &SCCDep, TestModuleAnalysis::Result &MDep) + : SCCDep(SCCDep), MDep(MDep) {} + TestSCCAnalysis::Result &SCCDep; + TestModuleAnalysis::Result &MDep; + + bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, + CGSCCAnalysisManager::Invalidator &Inv) { + return !PA.preserved>() || + Inv.invalidate(C, PA); + } + }; + + TestIndirectSCCAnalysis(int &Runs) : Runs(Runs) {} + + /// Run the analysis pass over the function and return a result. + Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG) { + ++Runs; + auto &SCCDep = AM.getResult(C, CG); + + auto &ModuleProxy = AM.getResult(C, CG); + const ModuleAnalysisManager &MAM = ModuleProxy.getManager(); + // For the test, we insist that the module analysis starts off in the + // cache. + auto &MDep = *MAM.getCachedResult( + *C.begin()->getFunction().getParent()); + // Register the dependency as module analysis dependencies have to be + // pre-registered on the proxy. + ModuleProxy.registerOuterAnalysisInvalidation(); + + return Result(SCCDep, MDep); + } + +private: + friend AnalysisInfoMixin; + static AnalysisKey Key; + + int &Runs; +}; + +AnalysisKey TestIndirectSCCAnalysis::Key; + +/// A test analysis pass which caches in its result the result from the above +/// indirect analysis pass. +/// +/// This allows us to ensure that whenever an analysis pass is invalidated due +/// to dependencies (especially dependencies across IR units that trigger +/// asynchronous invalidation) we correctly detect that this may in turn cause +/// other analysis to be invalidated. +struct TestDoublyIndirectSCCAnalysis + : public AnalysisInfoMixin { + struct Result { + Result(TestIndirectSCCAnalysis::Result &IDep) : IDep(IDep) {} + TestIndirectSCCAnalysis::Result &IDep; + + bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, + CGSCCAnalysisManager::Invalidator &Inv) { + return !PA.preserved>() || + Inv.invalidate(C, PA); + } + }; + + TestDoublyIndirectSCCAnalysis(int &Runs) : Runs(Runs) {} + + /// Run the analysis pass over the function and return a result. + Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG) { + ++Runs; + auto &IDep = AM.getResult(C, CG); + return Result(IDep); + } + +private: + friend AnalysisInfoMixin; + static AnalysisKey Key; + + int &Runs; +}; + +AnalysisKey TestDoublyIndirectSCCAnalysis::Key; + +/// A test analysis pass which caches results from three different IR unit +/// layers and requires intermediate layers to correctly propagate the entire +/// distance. +struct TestIndirectFunctionAnalysis + : public AnalysisInfoMixin { + struct Result { + Result(TestFunctionAnalysis::Result &FDep, TestModuleAnalysis::Result &MDep, + TestSCCAnalysis::Result &SCCDep) + : FDep(FDep), MDep(MDep), SCCDep(SCCDep) {} + TestFunctionAnalysis::Result &FDep; + TestModuleAnalysis::Result &MDep; + TestSCCAnalysis::Result &SCCDep; + + 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; + auto &FDep = AM.getResult(F); + + auto &ModuleProxy = AM.getResult(F); + const ModuleAnalysisManager &MAM = ModuleProxy.getManager(); + // For the test, we insist that the module analysis starts off in the + // cache. + auto &MDep = *MAM.getCachedResult(*F.getParent()); + // Register the dependency as module analysis dependencies have to be + // pre-registered on the proxy. + ModuleProxy.registerOuterAnalysisInvalidation< + TestModuleAnalysis, TestIndirectFunctionAnalysis>(); + + // For thet test we assume this is run inside a CGSCC pass manager. + const LazyCallGraph &CG = + *MAM.getCachedResult(*F.getParent()); + auto &CGSCCProxy = AM.getResult(F); + const CGSCCAnalysisManager &CGAM = CGSCCProxy.getManager(); + // For the test, we insist that the CGSCC analysis starts off in the cache. + auto &SCCDep = + *CGAM.getCachedResult(*CG.lookupSCC(*CG.lookup(F))); + // Register the dependency as CGSCC analysis dependencies have to be + // pre-registered on the proxy. + CGSCCProxy.registerOuterAnalysisInvalidation< + TestSCCAnalysis, TestIndirectFunctionAnalysis>(); + + return Result(FDep, MDep, SCCDep); + } + +private: + friend AnalysisInfoMixin; + static AnalysisKey Key; + + int &Runs; +}; + +AnalysisKey TestIndirectFunctionAnalysis::Key; + +TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) { + int ModuleAnalysisRuns = 0; + MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); }); + + int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0, + DoublyIndirectSCCAnalysisRuns = 0; + CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); }); + CGAM.registerPass( + [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns); }); + CGAM.registerPass([&] { + return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns); + }); + + int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0; + FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); }); + FAM.registerPass([&] { + return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns); + }); + + ModulePassManager MPM(/*DebugLogging*/ true); + + int FunctionCount = 0; + CGSCCPassManager CGPM(/*DebugLogging*/ true); + // First just use the analysis to get the function count and preserve + // everything. + CGPM.addPass( + LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { + auto &DoublyIndirectResult = + AM.getResult(C, CG); + auto &IndirectResult = DoublyIndirectResult.IDep; + FunctionCount += IndirectResult.SCCDep.FunctionCount; + return PreservedAnalyses::all(); + })); + // Next, invalidate + // - both analyses for the (f) and (x) SCCs, + // - just the underlying (indirect) analysis for (g) SCC, and + // - just the direct analysis for (h1,h2,h3) SCC. + CGPM.addPass( + LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { + auto &DoublyIndirectResult = + AM.getResult(C, CG); + auto &IndirectResult = DoublyIndirectResult.IDep; + FunctionCount += IndirectResult.SCCDep.FunctionCount; + auto PA = PreservedAnalyses::none(); + if (C.getName() == "(g)") + PA.preserve(); + else if (C.getName() == "(h3, h1, h2)") + PA.preserve(); + return PA; + })); + // Finally, use the analysis again on each function, forcing re-computation + // for all of them. + CGPM.addPass( + LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { + auto &DoublyIndirectResult = + AM.getResult(C, CG); + auto &IndirectResult = DoublyIndirectResult.IDep; + FunctionCount += IndirectResult.SCCDep.FunctionCount; + return PreservedAnalyses::all(); + })); + + // Create a second CGSCC pass manager. This will cause the module-level + // invalidation to occur, which will force yet another invalidation of the + // indirect SCC-level analysis as the module analysis it depends on gets + // invalidated. + CGSCCPassManager CGPM2(/*DebugLogging*/ true); + CGPM2.addPass( + LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { + auto &DoublyIndirectResult = + AM.getResult(C, CG); + auto &IndirectResult = DoublyIndirectResult.IDep; + FunctionCount += IndirectResult.SCCDep.FunctionCount; + return PreservedAnalyses::all(); + })); + + // Add a requires pass to populate the module analysis and then our function + // pass pipeline. + MPM.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + // Now require the module analysis again (it will have been invalidated once) + // and then use it again from a function pass manager. + MPM.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2))); + MPM.run(*M, MAM); + + // There are generally two possible runs for each of the four SCCs. But + // for one SCC, we only invalidate the indirect analysis so the base one + // only gets run seven times. + EXPECT_EQ(7, SCCAnalysisRuns); + // The module analysis pass should be run twice here. + EXPECT_EQ(2, ModuleAnalysisRuns); + // The indirect analysis is invalidated (either directly or indirectly) three + // times for each of four SCCs. + EXPECT_EQ(3 * 4, IndirectSCCAnalysisRuns); + EXPECT_EQ(3 * 4, DoublyIndirectSCCAnalysisRuns); + + // Four passes count each of six functions once (via SCCs). + EXPECT_EQ(4 * 6, FunctionCount); +} } Index: unittests/IR/PassManagerTest.cpp =================================================================== --- unittests/IR/PassManagerTest.cpp +++ unittests/IR/PassManagerTest.cpp @@ -171,7 +171,10 @@ TEST_F(PassManagerTest, BasicPreservedAnalyses) { PreservedAnalyses PA1 = PreservedAnalyses(); EXPECT_FALSE(PA1.preserved()); + EXPECT_FALSE( + (PA1.preserved>())); EXPECT_FALSE(PA1.preserved()); + EXPECT_FALSE((PA1.preserved>())); PreservedAnalyses PA2 = PreservedAnalyses::none(); EXPECT_FALSE(PA2.preserved()); EXPECT_FALSE(PA2.preserved()); @@ -385,12 +388,15 @@ struct TestIndirectFunctionAnalysis : public AnalysisInfoMixin { struct Result { - Result(TestFunctionAnalysis::Result &Dep) : Dep(Dep) {} - TestFunctionAnalysis::Result &Dep; + Result(TestFunctionAnalysis::Result &FDep, TestModuleAnalysis::Result &MDep) + : FDep(FDep), MDep(MDep) {} + TestFunctionAnalysis::Result &FDep; + TestModuleAnalysis::Result &MDep; bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv) { - return !PA.preserved() || + return !PA.preserved>() || Inv.invalidate(F, PA); } }; @@ -400,7 +406,17 @@ /// Run the analysis pass over the function and return a result. Result run(Function &F, FunctionAnalysisManager &AM) { ++Runs; - return Result(AM.getResult(F)); + auto &FDep = AM.getResult(F); + auto &Proxy = AM.getResult(F); + const ModuleAnalysisManager &MAM = Proxy.getManager(); + // For the test, we insist that the module analysis starts off in the + // cache. + auto &MDep = *MAM.getCachedResult(*F.getParent()); + // And register the dependency as module analysis dependencies have to be + // pre-registered on the proxy. + Proxy.registerOuterAnalysisInvalidation(); + return Result(FDep, MDep); } private: @@ -412,6 +428,45 @@ AnalysisKey TestIndirectFunctionAnalysis::Key; +/// A test analysis pass which chaches in its result the result from the above +/// indirect analysis pass. +/// +/// This allows us to ensure that whenever an analysis pass is invalidated due +/// to dependencies (especially dependencies across IR units that trigger +/// asynchronous invalidation) we correctly detect that this may in turn cause +/// other analysis to be invalidated. +struct TestDoublyIndirectFunctionAnalysis + : public AnalysisInfoMixin { + struct Result { + Result(TestIndirectFunctionAnalysis::Result &IDep) : IDep(IDep) {} + TestIndirectFunctionAnalysis::Result &IDep; + + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + return !PA.preserved>() || + Inv.invalidate(F, PA); + } + }; + + TestDoublyIndirectFunctionAnalysis(int &Runs) : Runs(Runs) {} + + /// Run the analysis pass over the function and return a result. + Result run(Function &F, FunctionAnalysisManager &AM) { + ++Runs; + auto &IDep = AM.getResult(F); + return Result(IDep); + } + +private: + friend AnalysisInfoMixin; + static AnalysisKey Key; + + int &Runs; +}; + +AnalysisKey TestDoublyIndirectFunctionAnalysis::Key; + struct LambdaPass : public PassInfoMixin { using FuncT = std::function; @@ -426,23 +481,31 @@ TEST_F(PassManagerTest, IndirectAnalysisInvalidation) { FunctionAnalysisManager FAM(/*DebugLogging*/ true); - int AnalysisRuns = 0, IndirectAnalysisRuns = 0; - FAM.registerPass([&] { return TestFunctionAnalysis(AnalysisRuns); }); + int FunctionAnalysisRuns = 0, ModuleAnalysisRuns = 0, + IndirectAnalysisRuns = 0, DoublyIndirectAnalysisRuns = 0; + FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); }); FAM.registerPass( [&] { return TestIndirectFunctionAnalysis(IndirectAnalysisRuns); }); + FAM.registerPass([&] { + return TestDoublyIndirectFunctionAnalysis(DoublyIndirectAnalysisRuns); + }); ModuleAnalysisManager MAM(/*DebugLogging*/ true); + MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); }); MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); - int InstrCount = 0; + int InstrCount = 0, FunctionCount = 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; + auto &DoublyIndirectResult = + AM.getResult(F); + auto &IndirectResult = DoublyIndirectResult.IDep; + InstrCount += IndirectResult.FDep.InstructionCount; + FunctionCount += IndirectResult.MDep.FunctionCount; return PreservedAnalyses::all(); })); // Next, invalidate @@ -450,8 +513,11 @@ // - 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 &DoublyIndirectResult = + AM.getResult(F); + auto &IndirectResult = DoublyIndirectResult.IDep; + InstrCount += IndirectResult.FDep.InstructionCount; + FunctionCount += IndirectResult.MDep.FunctionCount; auto PA = PreservedAnalyses::none(); if (F.getName() == "g") PA.preserve(); @@ -462,23 +528,55 @@ // 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; + auto &DoublyIndirectResult = + AM.getResult(F); + auto &IndirectResult = DoublyIndirectResult.IDep; + InstrCount += IndirectResult.FDep.InstructionCount; + FunctionCount += IndirectResult.MDep.FunctionCount; return PreservedAnalyses::all(); })); + + // Create a second function pass manager. This will cause the module-level + // invalidation to occur, which will force yet another invalidation of the + // indirect function-level analysis as the module analysis it depends on gets + // invalidated. + FunctionPassManager FPM2(/*DebugLogging*/ true); + FPM2.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) { + auto &DoublyIndirectResult = + AM.getResult(F); + auto &IndirectResult = DoublyIndirectResult.IDep; + InstrCount += IndirectResult.FDep.InstructionCount; + FunctionCount += IndirectResult.MDep.FunctionCount; + return PreservedAnalyses::all(); + })); + + // Add a requires pass to populate the module analysis and then our function + // pass pipeline. + MPM.addPass(RequireAnalysisPass()); MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + // Now require the module analysis again (it will have been invalidated once) + // and then use it again from a function pass manager. + MPM.addPass(RequireAnalysisPass()); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM2))); 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); + EXPECT_EQ(5, FunctionAnalysisRuns); + // The module analysis pass should be run twice here. + EXPECT_EQ(2, ModuleAnalysisRuns); // The indirect analysis is invalidated for each function (either directly or // indirectly) and run twice for each. - EXPECT_EQ(6, IndirectAnalysisRuns); + EXPECT_EQ(9, IndirectAnalysisRuns); + EXPECT_EQ(9, DoublyIndirectAnalysisRuns); - // There are five instructions in the module and we add the count three + // There are five instructions in the module and we add the count four // times. - EXPECT_EQ(5 * 3, InstrCount); + EXPECT_EQ(5 * 4, InstrCount); + + // There are three functions and we count them four times for each of the + // three functions. + EXPECT_EQ(3 * 4 * 3, FunctionCount); } }