Index: include/llvm/Analysis/CGSCCPassManager.h =================================================================== --- include/llvm/Analysis/CGSCCPassManager.h +++ include/llvm/Analysis/CGSCCPassManager.h @@ -427,8 +427,8 @@ // 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.preserveSet>(); PA.preserve(); - PA.preserve>(); PA.preserve(); PA.preserve(); return PA; @@ -581,7 +581,7 @@ // Functions. This precludes *any* invalidation of function analyses by the // proxy, but that's OK because we've taken care to invalidate analyses in // the function analysis manager incrementally above. - PA.preserve>(); + PA.preserveSet>(); PA.preserve(); // We've also ensured that we updated the call graph along the way. Index: include/llvm/Analysis/LoopPassManager.h =================================================================== --- include/llvm/Analysis/LoopPassManager.h +++ include/llvm/Analysis/LoopPassManager.h @@ -99,8 +99,8 @@ // post-order. for (auto *L : reverse(Loops)) { PreservedAnalyses PassPA = Pass.run(*L, LAM); - assert(PassPA.preserved(getLoopPassPreservedAnalyses()) && - "Loop passes must preserve all relevant analyses"); + // FIXME: We should verify the set of analyses relevant to Loop passes + // are preserved. // We know that the loop pass couldn't have invalidated any other loop's // analyses (that's the contract of a loop pass), so directly handle the @@ -116,7 +116,7 @@ // Loops. This precludes *any* invalidation of loop analyses by the proxy, // but that's OK because we've taken care to invalidate analyses in the // loop analysis manager incrementally above. - PA.preserve>(); + PA.preserveSet>(); PA.preserve(); return PA; } 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" @@ -62,15 +63,48 @@ /// the analysis in the pass management infrastructure. struct alignas(8) AnalysisKey {}; -/// \brief An abstract set of preserved analyses following a transformation pass -/// run. +/// A special type used to provide an address that identifies a set of related +/// analyses. /// -/// When a transformation pass is run, it can return a set of analyses whose -/// results were preserved by that transformation. The default set is "none", -/// and preserving analyses must be done explicitly. +/// These sets are primarily used below to mark sets of analyses as preserved. +/// An example would be analyses depending only on the CFG of a function. +/// A transformation can mark that it is preserving the CFG of a function and +/// then analyses can check for this rather than each transform having to fully +/// enumerate every analysis preserved. +struct alignas(8) AnalysisSetKey {}; + +/// Class for tracking what analyses are preserved after a transformation pass +/// runs over some unit of IR. /// -/// There is also an explicit all state which can be used (for example) when -/// the IR is not mutated at all. +/// Transformation passes build and return these objects when run over the IR +/// to communicate which analyses remain valid afterward. For most passes this +/// is fairly simple: if they don't change anything all analyses are preserved, +/// otherwise only a short list of analyses that have been explicitly updated +/// are preserved. +/// +/// This class also provides the ability to mark abstract *sets* of analyses as +/// preserved. These sets allow passes to indicate that they preserve broad +/// aspects of the IR (such as its CFG) and analyses to opt in to that being +/// sufficient without the passes having to fully enumerate such analyses. +/// +/// Finally, this class can represent "abandoning" an analysis, which marks it +/// as not-preserved even if it would be covered by some abstract set of +/// analyses. +/// +/// Given a `PreservedAnalyses` object, an analysis will typically want to +/// figure out whether it is preserved. In the example below, MyAnalysisType is +/// preserved if it's not abandoned, and (a) it's explicitly marked as +/// preserved, (b), the set AllAnalysesOn is preserved, or (c) both +/// AnalysisSetA and AnalysisSetB are preserved. +/// +/// ``` +/// auto PAC = PA.getChecker(); +/// if (PAC.preserved() || PAC.preservedSet>() || +/// (PAC.preservedSet() && +/// PAC.preservedSet())) { +/// // The analysis has been successfully preserved ... +/// } +/// ``` class PreservedAnalyses { public: /// \brief Convenience factory function for the empty preserved set. @@ -79,17 +113,55 @@ /// \brief Construct a special preserved set that preserves all passes. static PreservedAnalyses all() { PreservedAnalyses PA; - PA.PreservedAnalysisIDs.insert(&AllAnalysesKey); + PA.PreservedIDs.insert(&AllAnalysesKey); return PA; } - /// \brief Mark a particular pass as preserved, adding it to the set. - template void preserve() { preserve(PassT::ID()); } + /// Mark an analysis as preserved. + template void preserve() { preserve(AnalysisT::ID()); } - /// \brief Mark an abstract ID as preserved, adding it to the set. + /// Mark an analysis as preserved using its ID. 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); + PreservedIDs.insert(ID); + } + + /// Mark an analysis set as preserved. + template void preserveSet() { + preserveSet(AnalysisSetT::ID()); + } + + /// Mark an analysis set as preserved using its ID. + void preserveSet(AnalysisSetKey *ID) { + // If we're not already in the saturated 'all' state, add this set. + if (!areAllPreserved()) + PreservedIDs.insert(ID); + } + + /// Mark an analysis as abandoned. + /// + /// An abandoned analysis is not preserved, even if it is nominally covered + /// by some other set or was previously explicitly marked as preserved. + /// + /// Note that you can only abandon a specific analysis, not a *set* of + /// analyses. + template void abandon() { abandon(AnalysisT::ID()); } + + /// Mark an analysis as abandoned using its ID. + /// + /// An abandoned analysis is not preserved, even if it is nominally covered + /// by some other set or was previously explicitly marked as preserved. + /// + /// Note that you can only abandon a specific analysis, not a *set* of + /// analyses. + void abandon(AnalysisKey *ID) { + PreservedIDs.erase(ID); + NotPreservedAnalysisIDs.insert(ID); } /// \brief Intersect this set with another in place. @@ -100,12 +172,18 @@ if (Arg.areAllPreserved()) return; if (areAllPreserved()) { - PreservedAnalysisIDs = Arg.PreservedAnalysisIDs; + *this = Arg; return; } - for (auto ID : PreservedAnalysisIDs) - if (!Arg.PreservedAnalysisIDs.count(ID)) - PreservedAnalysisIDs.erase(ID); + // The intersection requires the *union* of the explicitly not-preserved + // IDs and the *intersection* of the preserved IDs. + for (auto ID : Arg.NotPreservedAnalysisIDs) { + PreservedIDs.erase(ID); + NotPreservedAnalysisIDs.insert(ID); + } + for (auto ID : PreservedIDs) + if (!Arg.PreservedIDs.count(ID)) + PreservedIDs.erase(ID); } /// \brief Intersect this set with a temporary other set in place. @@ -116,49 +194,111 @@ if (Arg.areAllPreserved()) return; if (areAllPreserved()) { - PreservedAnalysisIDs = std::move(Arg.PreservedAnalysisIDs); + *this = std::move(Arg); return; } - for (auto ID : PreservedAnalysisIDs) - if (!Arg.PreservedAnalysisIDs.count(ID)) - PreservedAnalysisIDs.erase(ID); + // The intersection requires the *union* of the explicitly not-preserved + // IDs and the *intersection* of the preserved IDs. + for (auto ID : Arg.NotPreservedAnalysisIDs) { + PreservedIDs.erase(ID); + NotPreservedAnalysisIDs.insert(ID); + } + for (auto ID : PreservedIDs) + if (!Arg.PreservedIDs.count(ID)) + PreservedIDs.erase(ID); } - /// \brief Query whether a pass is marked as preserved by this set. - template bool preserved() const { - return preserved(PassT::ID()); - } + /// A checker object that makes it easy to query for whether an analysis or + /// some set covering it is preserved. + class PreservedAnalysisChecker { + friend class PreservedAnalyses; + + const PreservedAnalyses &PA; + AnalysisKey *const ID; + const bool IsAbandoned; + + /// A PreservedAnalysisChecker is tied to a particular Analysis because + /// `preserved()` and `preservedSet()` both return false if the Analysis + /// was abandoned. + PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID) + : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(ID)) {} + + public: + /// Returns true if the checker's analysis was not abandoned and the + /// analysis is either is explicitly preserved or all analyses are + /// preserved. + bool preserved() { + return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) || + PA.PreservedIDs.count(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); + /// Returns true if the checker's analysis was not abandoned and either the + /// provided set type is either explicitly preserved or all analyses are + /// preserved. + template bool preservedSet() { + AnalysisSetKey *SetID = AnalysisSetT::ID(); + return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) || + PA.PreservedIDs.count(SetID)); + } + }; + + /// Build a checker for this `PreservedAnalyses` and the specified analysis + /// type. + /// + /// You can use the returned object to query whether an analysis was + /// preserved. See the example in the comment on `PreservedAnalysis`. + template PreservedAnalysisChecker getChecker() const { + return PreservedAnalysisChecker(*this, AnalysisT::ID()); } - /// \brief Query whether all of the analyses in the set are preserved. - bool preserved(const PreservedAnalyses& Arg) { - if (Arg.areAllPreserved()) - return areAllPreserved(); - for (auto ID : Arg.PreservedAnalysisIDs) - if (!preserved(ID)) - return false; - return true; + /// Build a checker for this `PreservedAnalyses` and the specified analysis + /// ID. + /// + /// You can use the returned object to query whether an analysis was + /// preserved. See the example in the comment on `PreservedAnalysis`. + PreservedAnalysisChecker getChecker(AnalysisKey *ID) const { + return PreservedAnalysisChecker(*this, ID); } - /// \brief Test whether all passes are preserved. + /// Test whether all analyses are preserved (and none are abandoned). /// - /// This is used primarily to optimize for the case of no changes which will - /// common in many scenarios. + /// This lets analyses optimize for the common case where a transformation + /// made no changes to the IR. bool areAllPreserved() const { - return PreservedAnalysisIDs.count(&AllAnalysesKey); + return NotPreservedAnalysisIDs.empty() && + PreservedIDs.count(&AllAnalysesKey); + } + + /// Directly test whether a set of analyses is preserved. + /// + /// This is only true when no analyses have been explicitly abandoned. + template bool allAnalysesInSetPreserved() const { + return allAnalysesInSetPreserved(AnalysisSetT::ID()); + } + + /// Directly test whether a set of analyses is preserved. + /// + /// This is only true when no analyses have been explicitly abandoned. + bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const { + return NotPreservedAnalysisIDs.empty() && + (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(SetID)); } private: - // A special key used to indicate all analyses. - static AnalysisKey AllAnalysesKey; + /// A special key used to indicate all analyses. + static AnalysisSetKey AllAnalysesKey; - SmallPtrSet PreservedAnalysisIDs; + /// The IDs of analyses and analysis sets that are preserved. + SmallPtrSet PreservedIDs; + + /// The IDs of explicitly not-preserved analyses. + /// + /// If an analysis in this set is covered by a set in `PreservedIDs`, we + /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always + /// "wins" over analysis sets in `PreservedIDs`. + /// + /// Also, a given ID should never occur both here and in `PreservedIDs`. + SmallPtrSet NotPreservedAnalysisIDs; }; // Forward declare the analysis manager template. @@ -220,13 +360,13 @@ template class AllAnalysesOn { public: - static AnalysisKey *ID() { return &SetKey; } + static AnalysisSetKey *ID() { return &SetKey; } private: - static AnalysisKey SetKey; + static AnalysisSetKey SetKey; }; -template AnalysisKey AllAnalysesOn::SetKey; +template AnalysisSetKey AllAnalysesOn::SetKey; extern template class AllAnalysesOn; extern template class AllAnalysesOn; @@ -300,7 +440,7 @@ // current unit of IR. Therefore, the remaining analysis results in the // AnalysisManager are preserved. We mark this with a set so that we don't // need to inspect each one individually. - PA.preserve>(); + PA.preserveSet>(); if (DebugLogging) dbgs() << "Finished " << getTypeName() << " pass manager run.\n"; @@ -399,8 +539,29 @@ /// 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. + bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) { + return invalidateImpl<>(ID, IR, PA); + } + + private: + friend class AnalysisManager; + + 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 +575,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 +730,8 @@ /// 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're done if all analyses on this IR unit are preserved. + if (PA.allAnalysesInSetPreserved>()) return; if (DebugLogging) @@ -857,9 +1011,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 +1037,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) {} @@ -967,7 +1155,7 @@ // Function units. This precludes *any* invalidation of function analyses // by the proxy, but that's OK because we've taken care to invalidate // analyses in the function analysis manager incrementally above. - PA.preserve>(); + PA.preserveSet>(); PA.preserve(); return PA; } 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,9 @@ // ones that use the trivial behavior. bool invalidate(IRUnitT &, const PreservedAnalysesT &PA, InvalidatorT &) override { - return !PA.preserved(PassT::ID()); + auto PAC = PA.template getChecker(); + return !PAC.preserved() && + !PAC.template preservedSet>(); } ResultT Result; Index: lib/Analysis/CGSCCPassManager.cpp =================================================================== --- lib/Analysis/CGSCCPassManager.cpp +++ lib/Analysis/CGSCCPassManager.cpp @@ -78,7 +78,7 @@ // SCC. Therefore, the remaining analysis results in the AnalysisManager are // preserved. We mark this with a set so that we don't need to inspect each // one individually. - PA.preserve>(); + PA.preserveSet>(); if (DebugLogging) dbgs() << "Finished CGSCC pass manager run.\n"; @@ -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,9 @@ // 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. + auto PAC = PA.getChecker(); + if (!(PAC.preserved() || PAC.preservedSet>()) || Inv.invalidate(M, PA) || Inv.invalidate(M, PA)) { InnerAM->clear(); @@ -108,10 +113,45 @@ return true; } + // Directly check if the relevant set is preserved so we can short circuit + // invalidating SCCs below. + bool AreSCCAnalysesPreserved = + PA.allAnalysesInSetPreserved>(); + // 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/Analysis/LoopPassManager.cpp =================================================================== --- lib/Analysis/LoopPassManager.cpp +++ lib/Analysis/LoopPassManager.cpp @@ -33,7 +33,8 @@ // the module may have changed. We therefore can't call // InnerAM->invalidate(), because any pointers to Functions it has may be // stale. - if (!PA.preserved(LoopAnalysisManagerFunctionProxy::ID())) + auto PAC = PA.getChecker(); + if (!PAC.preserved() && !PAC.preservedSet>()) InnerAM->clear(); // FIXME: Proper suppor for invalidation isn't yet implemented for the LPM. 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,18 +41,54 @@ // 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())) { + auto PAC = PA.getChecker(); + if (!PAC.preserved() && !PAC.preservedSet>()) { 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.allAnalysesInSetPreserved>(); + + // 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; } } -AnalysisKey PreservedAnalyses::AllAnalysesKey; +AnalysisSetKey PreservedAnalyses::AllAnalysesKey; Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -820,4 +820,267 @@ // 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) { + auto PAC = PA.getChecker(); + return !(PAC.preserved() || + PAC.preservedSet>()) || + 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) { + auto PAC = PA.getChecker(); + return !(PAC.preserved() || + PAC.preservedSet>()) || + 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) { + auto PAC = PA.getChecker(); + return !(PAC.preserved() || + PAC.preservedSet>()) || + 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 @@ -168,37 +168,224 @@ "}\n")) {} }; -TEST_F(PassManagerTest, BasicPreservedAnalyses) { +TEST(PreservedAnalysesTest, Basic) { PreservedAnalyses PA1 = PreservedAnalyses(); - EXPECT_FALSE(PA1.preserved()); - EXPECT_FALSE(PA1.preserved()); - PreservedAnalyses PA2 = PreservedAnalyses::none(); - EXPECT_FALSE(PA2.preserved()); - EXPECT_FALSE(PA2.preserved()); - PreservedAnalyses PA3 = PreservedAnalyses::all(); - EXPECT_TRUE(PA3.preserved()); - EXPECT_TRUE(PA3.preserved()); + { + auto PAC = PA1.getChecker(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet>()); + } + { + auto PAC = PA1.getChecker(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet>()); + } + auto PA2 = PreservedAnalyses::none(); + { + auto PAC = PA2.getChecker(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet>()); + } + auto PA3 = PreservedAnalyses::all(); + { + auto PAC = PA3.getChecker(); + EXPECT_TRUE(PAC.preserved()); + EXPECT_TRUE(PAC.preservedSet>()); + } PreservedAnalyses PA4 = PA1; - EXPECT_FALSE(PA4.preserved()); - EXPECT_FALSE(PA4.preserved()); + { + auto PAC = PA4.getChecker(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet>()); + } PA4 = PA3; - EXPECT_TRUE(PA4.preserved()); - EXPECT_TRUE(PA4.preserved()); + { + auto PAC = PA4.getChecker(); + EXPECT_TRUE(PAC.preserved()); + EXPECT_TRUE(PAC.preservedSet>()); + } PA4 = std::move(PA2); - EXPECT_FALSE(PA4.preserved()); - EXPECT_FALSE(PA4.preserved()); - PA4.preserve(); - EXPECT_TRUE(PA4.preserved()); - EXPECT_FALSE(PA4.preserved()); - PA1.preserve(); - EXPECT_FALSE(PA1.preserved()); - EXPECT_TRUE(PA1.preserved()); + { + auto PAC = PA4.getChecker(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet>()); + } +} + +TEST(PreservedAnalysesTest, Preserve) { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + EXPECT_TRUE(PA.getChecker().preserved()); + EXPECT_FALSE(PA.getChecker().preserved()); + PA.preserve(); + EXPECT_TRUE(PA.getChecker().preserved()); + EXPECT_TRUE(PA.getChecker().preserved()); + + // Redundant calls are fine. + PA.preserve(); + EXPECT_TRUE(PA.getChecker().preserved()); + EXPECT_TRUE(PA.getChecker().preserved()); +} + +TEST(PreservedAnalysesTest, PreserveSets) { + auto PA = PreservedAnalyses::none(); + PA.preserveSet>(); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); + EXPECT_FALSE(PA.getChecker() + .preservedSet>()); + PA.preserveSet>(); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); + + // Mixing is fine. + PA.preserve(); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); + + // Redundant calls are fine. + PA.preserveSet>(); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); + EXPECT_TRUE(PA.getChecker() + .preservedSet>()); +} + +TEST(PreservedAnalysisTest, Intersect) { + // Setup the initial sets. + auto PA1 = PreservedAnalyses::none(); PA1.preserve(); - EXPECT_TRUE(PA1.preserved()); - EXPECT_TRUE(PA1.preserved()); - PA1.intersect(PA4); - EXPECT_TRUE(PA1.preserved()); - EXPECT_FALSE(PA1.preserved()); + PA1.preserveSet>(); + auto PA2 = PreservedAnalyses::none(); + PA2.preserve(); + PA2.preserveSet>(); + PA2.preserve(); + PA2.preserveSet>(); + auto PA3 = PreservedAnalyses::none(); + PA3.preserve(); + PA3.preserveSet>(); + + // Self intersection is a no-op. + auto Intersected = PA1; + Intersected.intersect(PA1); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting with all is a no-op. + Intersected.intersect(PreservedAnalyses::all()); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting a narrow set with a more broad set is the narrow set. + Intersected.intersect(PA2); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting a broad set with a more narrow set is the narrow set. + Intersected = PA2; + Intersected.intersect(PA1); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting with empty clears. + Intersected.intersect(PreservedAnalyses::none()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting non-overlapping clears. + Intersected = PA1; + Intersected.intersect(PA3); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting with moves works in when there is storage on both sides. + Intersected = PA1; + auto Tmp = PA2; + Intersected.intersect(std::move(Tmp)); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); + + // Intersecting with move works for incoming all and existing all. + auto Tmp2 = PreservedAnalyses::all(); + Intersected.intersect(std::move(Tmp2)); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); + Intersected = PreservedAnalyses::all(); + auto Tmp3 = PA1; + Intersected.intersect(std::move(Tmp3)); + EXPECT_TRUE(Intersected.getChecker().preserved()); + EXPECT_FALSE(Intersected.getChecker() + .preservedSet>()); + EXPECT_FALSE(Intersected.getChecker().preserved()); + EXPECT_TRUE(Intersected.getChecker() + .preservedSet>()); +} + +TEST(PreservedAnalysisTest, Abandon) { + auto PA = PreservedAnalyses::none(); + + // We can abandon things after they are preserved. + PA.preserve(); + PA.abandon(); + EXPECT_FALSE(PA.getChecker().preserved()); + + // Repeated is fine, and abandoning if they were never preserved is fine. + PA.abandon(); + EXPECT_FALSE(PA.getChecker().preserved()); + PA.abandon(); + EXPECT_FALSE(PA.getChecker().preserved()); + + // Even if the sets are preserved, the abandoned analyses' checker won't + // return true for those sets. + PA.preserveSet>(); + PA.preserveSet>(); + EXPECT_FALSE(PA.getChecker() + .preservedSet>()); + EXPECT_FALSE(PA.getChecker() + .preservedSet>()); + + // But an arbitrary (opaque) analysis will still observe the sets as + // preserved. This also checks that we can use an explicit ID rather than + // a type. + AnalysisKey FakeKey, *FakeID = &FakeKey; + EXPECT_TRUE(PA.getChecker(FakeID).preservedSet>()); + EXPECT_TRUE(PA.getChecker(FakeID).preservedSet>()); } TEST_F(PassManagerTest, Basic) { @@ -385,12 +572,16 @@ 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() || + auto PAC = PA.getChecker(); + return !(PAC.preserved() || + PAC.preservedSet>()) || Inv.invalidate(F, PA); } }; @@ -400,7 +591,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 +613,46 @@ 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) { + auto PAC = PA.getChecker(); + return !(PAC.preserved() || + PAC.preservedSet>()) || + 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 +667,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 +699,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 +714,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); } }