diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/CGSCCPassManager.h | 4 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/LoopPassManager.h | 6 | ||||
| -rw-r--r-- | llvm/include/llvm/IR/PassManager.h | 318 | ||||
| -rw-r--r-- | llvm/include/llvm/IR/PassManagerInternal.h | 5 | ||||
| -rw-r--r-- | llvm/lib/Analysis/CGSCCPassManager.cpp | 50 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LoopPassManager.cpp | 3 | ||||
| -rw-r--r-- | llvm/lib/IR/PassManager.cpp | 50 | ||||
| -rw-r--r-- | llvm/unittests/Analysis/CGSCCPassManagerTest.cpp | 263 | ||||
| -rw-r--r-- | llvm/unittests/IR/PassManagerTest.cpp | 370 |
9 files changed, 944 insertions, 125 deletions
diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h index 73f462e4bf1..4a91e08a13c 100644 --- a/llvm/include/llvm/Analysis/CGSCCPassManager.h +++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h @@ -436,8 +436,8 @@ public: // 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<AllAnalysesOn<LazyCallGraph::SCC>>(); PA.preserve<LazyCallGraphAnalysis>(); - PA.preserve<AllAnalysesOn<LazyCallGraph::SCC>>(); PA.preserve<CGSCCAnalysisManagerModuleProxy>(); PA.preserve<FunctionAnalysisManagerModuleProxy>(); return PA; @@ -585,7 +585,7 @@ public: // 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<AllAnalysesOn<Function>>(); + PA.preserveSet<AllAnalysesOn<Function>>(); PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); // We've also ensured that we updated the call graph along the way. diff --git a/llvm/include/llvm/Analysis/LoopPassManager.h b/llvm/include/llvm/Analysis/LoopPassManager.h index c26336880bb..ae9c16502fe 100644 --- a/llvm/include/llvm/Analysis/LoopPassManager.h +++ b/llvm/include/llvm/Analysis/LoopPassManager.h @@ -111,8 +111,8 @@ public: // 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 @@ -128,7 +128,7 @@ public: // 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<AllAnalysesOn<Loop>>(); + PA.preserveSet<AllAnalysesOn<Loop>>(); PA.preserve<LoopAnalysisManagerFunctionProxy>(); return PA; } diff --git a/llvm/include/llvm/IR/PassManager.h b/llvm/include/llvm/IR/PassManager.h index 83712652f5a..c064e4b51be 100644 --- a/llvm/include/llvm/IR/PassManager.h +++ b/llvm/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 @@ namespace llvm { /// 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<MyIRUnit> is preserved, or (c) both +/// AnalysisSetA and AnalysisSetB are preserved. +/// +/// ``` +/// auto PAC = PA.getChecker<MyAnalysisType>(); +/// if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() || +/// (PAC.preservedSet<AnalysisSetA>() && +/// PAC.preservedSet<AnalysisSetB>())) { +/// // The analysis has been successfully preserved ... +/// } +/// ``` class PreservedAnalyses { public: /// \brief Convenience factory function for the empty preserved set. @@ -79,17 +113,55 @@ public: /// \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 <typename PassT> void preserve() { preserve(PassT::ID()); } + /// Mark an analysis as preserved. + template <typename AnalysisT> 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 <typename AnalysisSetT> 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 <typename AnalysisT> 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 @@ public: 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 @@ public: 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 <typename PassT> 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 <typename AnalysisSetT> 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 <typename AnalysisT> 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 <typename AnalysisSetT> 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<AnalysisKey *, 2> PreservedAnalysisIDs; + /// The IDs of analyses and analysis sets that are preserved. + SmallPtrSet<void *, 2> 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<AnalysisKey *, 2> NotPreservedAnalysisIDs; }; // Forward declare the analysis manager template. @@ -220,13 +360,13 @@ struct AnalysisInfoMixin : PassInfoMixin<DerivedT> { template <typename IRUnitT> class AllAnalysesOn { public: - static AnalysisKey *ID() { return &SetKey; } + static AnalysisSetKey *ID() { return &SetKey; } private: - static AnalysisKey SetKey; + static AnalysisSetKey SetKey; }; -template <typename IRUnitT> AnalysisKey AllAnalysesOn<IRUnitT>::SetKey; +template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey; extern template class AllAnalysesOn<Module>; extern template class AllAnalysesOn<Function>; @@ -300,7 +440,7 @@ public: // 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<AllAnalysesOn<IRUnitT>>(); + PA.preserveSet<AllAnalysesOn<IRUnitT>>(); if (DebugLogging) dbgs() << "Finished " << getTypeName<IRUnitT>() << " pass manager run.\n"; @@ -399,8 +539,29 @@ public: /// any dependecies on it will become invalid as a result. template <typename PassT> bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { - AnalysisKey *ID = PassT::ID(); + typedef detail::AnalysisResultModel<IRUnitT, PassT, + typename PassT::Result, + PreservedAnalyses, Invalidator> + ResultModelT; + return invalidateImpl<ResultModelT>(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 <typename ResultT = ResultConceptT> + 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 @@ public: "manager's cache is always an error, likely due to a stale result " "handle!"); - typedef detail::AnalysisResultModel<IRUnitT, PassT, - typename PassT::Result, - PreservedAnalyses, Invalidator> - ResultModelT; - auto &ResultModel = static_cast<ResultModelT &>(*RI->second->second); + auto &Result = static_cast<ResultT &>(*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<AnalysisKey *, bool, 8> &IsResultInvalidated, const AnalysisResultMapT &Results) : IsResultInvalidated(IsResultInvalidated), Results(Results) {} @@ -576,8 +730,8 @@ public: /// 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<AllAnalysesOn<IRUnitT>>()) + // We're done if all analyses on this IR unit are preserved. + if (PA.allAnalysesInSetPreserved<AllAnalysesOn<IRUnitT>>()) return; if (DebugLogging) @@ -857,9 +1011,13 @@ extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager, /// 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 <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> class OuterAnalysisManagerProxy : public AnalysisInfoMixin< @@ -879,8 +1037,38 @@ public: return false; } + /// Register a deferred invalidation event for when the outer analysis + /// manager processes its invalidations. + template <typename OuterAnalysisT, typename InvalidatedAnalysisT> + 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<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 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<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2> + OuterAnalysisInvalidationMap; }; OuterAnalysisManagerProxy(const AnalysisManagerT &AM) : AM(&AM) {} @@ -967,7 +1155,7 @@ public: // 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<AllAnalysesOn<Function>>(); + PA.preserveSet<AllAnalysesOn<Function>>(); PA.preserve<FunctionAnalysisManagerModuleProxy>(); return PA; } diff --git a/llvm/include/llvm/IR/PassManagerInternal.h b/llvm/include/llvm/IR/PassManagerInternal.h index d9a748832e8..02f21675fa9 100644 --- a/llvm/include/llvm/IR/PassManagerInternal.h +++ b/llvm/include/llvm/IR/PassManagerInternal.h @@ -25,6 +25,7 @@ namespace llvm { +template <typename IRUnitT> class AllAnalysesOn; template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager; class Invalidator; class PreservedAnalyses; @@ -191,7 +192,9 @@ struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT, // ones that use the trivial behavior. bool invalidate(IRUnitT &, const PreservedAnalysesT &PA, InvalidatorT &) override { - return !PA.preserved(PassT::ID()); + auto PAC = PA.template getChecker<PassT>(); + return !PAC.preserved() && + !PAC.template preservedSet<AllAnalysesOn<IRUnitT>>(); } ResultT Result; diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp index 2fa258bffea..1d3b184c621 100644 --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -76,7 +76,7 @@ PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, // 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<AllAnalysesOn<LazyCallGraph::SCC>>(); + PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>(); if (DebugLogging) dbgs() << "Finished CGSCC pass manager run.\n"; @@ -87,6 +87,10 @@ PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, 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. // @@ -94,8 +98,9 @@ bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( // 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<CGSCCAnalysisManagerModuleProxy>() || + // entire SCC layer as well rather than trying to do invalidation ourselves. + auto PAC = PA.getChecker<CGSCCAnalysisManagerModuleProxy>(); + if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) || Inv.invalidate<LazyCallGraphAnalysis>(M, PA) || Inv.invalidate<FunctionAnalysisManagerModuleProxy>(M, PA)) { InnerAM->clear(); @@ -106,10 +111,45 @@ bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( return true; } + // Directly check if the relevant set is preserved so we can short circuit + // invalidating SCCs below. + bool AreSCCAnalysesPreserved = + PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>(); + // 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<PreservedAnalyses> 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<ModuleAnalysisManagerCGSCCProxy>(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; diff --git a/llvm/lib/Analysis/LoopPassManager.cpp b/llvm/lib/Analysis/LoopPassManager.cpp index deb68e75ded..044e5d55daf 100644 --- a/llvm/lib/Analysis/LoopPassManager.cpp +++ b/llvm/lib/Analysis/LoopPassManager.cpp @@ -33,7 +33,8 @@ bool LoopAnalysisManagerFunctionProxy::Result::invalidate( // 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<LoopAnalysisManagerFunctionProxy>(); + if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Loop>>()) InnerAM->clear(); // FIXME: Proper suppor for invalidation isn't yet implemented for the LPM. diff --git a/llvm/lib/IR/PassManager.cpp b/llvm/lib/IR/PassManager.cpp index 7c478ea1cf6..8f68bb1daec 100644 --- a/llvm/lib/IR/PassManager.cpp +++ b/llvm/lib/IR/PassManager.cpp @@ -29,6 +29,10 @@ template <> 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 @@ bool FunctionAnalysisManagerModuleProxy::Result::invalidate( // 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<FunctionAnalysisManagerModuleProxy>(); + if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) { 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<AllAnalysesOn<Function>>(); + + // Now walk all the functions to see if any inner analysis invalidation is + // necessary. + for (Function &F : M) { + Optional<PreservedAnalyses> 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<ModuleAnalysisManagerFunctionProxy>(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; diff --git a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp index 95c107a93a2..ab5d1862c23 100644 --- a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp +++ b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp @@ -820,4 +820,267 @@ TEST_F(CGSCCPassManagerTest, // 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<TestIndirectSCCAnalysis> { + 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<TestIndirectSCCAnalysis>(); + return !(PAC.preserved() || + PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) || + Inv.invalidate<TestSCCAnalysis>(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<TestSCCAnalysis>(C, CG); + + auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(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<TestModuleAnalysis>( + *C.begin()->getFunction().getParent()); + // Register the dependency as module analysis dependencies have to be + // pre-registered on the proxy. + ModuleProxy.registerOuterAnalysisInvalidation<TestModuleAnalysis, + TestIndirectSCCAnalysis>(); + + return Result(SCCDep, MDep); + } + +private: + friend AnalysisInfoMixin<TestIndirectSCCAnalysis>; + 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<TestDoublyIndirectSCCAnalysis> { + 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<TestDoublyIndirectSCCAnalysis>(); + return !(PAC.preserved() || + PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) || + Inv.invalidate<TestIndirectSCCAnalysis>(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<TestIndirectSCCAnalysis>(C, CG); + return Result(IDep); + } + +private: + friend AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis>; + 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<TestIndirectFunctionAnalysis> { + 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<TestIndirectFunctionAnalysis>(); + return !(PAC.preserved() || + PAC.preservedSet<AllAnalysesOn<Function>>()) || + Inv.invalidate<TestFunctionAnalysis>(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<TestFunctionAnalysis>(F); + + auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); + const ModuleAnalysisManager &MAM = ModuleProxy.getManager(); + // For the test, we insist that the module analysis starts off in the + // cache. + auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(*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<LazyCallGraphAnalysis>(*F.getParent()); + auto &CGSCCProxy = AM.getResult<CGSCCAnalysisManagerFunctionProxy>(F); + const CGSCCAnalysisManager &CGAM = CGSCCProxy.getManager(); + // For the test, we insist that the CGSCC analysis starts off in the cache. + auto &SCCDep = + *CGAM.getCachedResult<TestSCCAnalysis>(*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<TestIndirectFunctionAnalysis>; + 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<TestDoublyIndirectSCCAnalysis>(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<TestDoublyIndirectSCCAnalysis>(C, CG); + auto &IndirectResult = DoublyIndirectResult.IDep; + FunctionCount += IndirectResult.SCCDep.FunctionCount; + auto PA = PreservedAnalyses::none(); + if (C.getName() == "(g)") + PA.preserve<TestSCCAnalysis>(); + else if (C.getName() == "(h3, h1, h2)") + PA.preserve<TestIndirectSCCAnalysis>(); + 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<TestDoublyIndirectSCCAnalysis>(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<TestDoublyIndirectSCCAnalysis>(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<TestModuleAnalysis, Module>()); + 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<TestModuleAnalysis, Module>()); + 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); +} } diff --git a/llvm/unittests/IR/PassManagerTest.cpp b/llvm/unittests/IR/PassManagerTest.cpp index d7515ba6b7d..b3a039a364f 100644 --- a/llvm/unittests/IR/PassManagerTest.cpp +++ b/llvm/unittests/IR/PassManagerTest.cpp @@ -168,37 +168,224 @@ public: "}\n")) {} }; -TEST_F(PassManagerTest, BasicPreservedAnalyses) { +TEST(PreservedAnalysesTest, Basic) { PreservedAnalyses PA1 = PreservedAnalyses(); - EXPECT_FALSE(PA1.preserved<TestFunctionAnalysis>()); - EXPECT_FALSE(PA1.preserved<TestModuleAnalysis>()); - PreservedAnalyses PA2 = PreservedAnalyses::none(); - EXPECT_FALSE(PA2.preserved<TestFunctionAnalysis>()); - EXPECT_FALSE(PA2.preserved<TestModuleAnalysis>()); - PreservedAnalyses PA3 = PreservedAnalyses::all(); - EXPECT_TRUE(PA3.preserved<TestFunctionAnalysis>()); - EXPECT_TRUE(PA3.preserved<TestModuleAnalysis>()); + { + auto PAC = PA1.getChecker<TestFunctionAnalysis>(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>()); + } + { + auto PAC = PA1.getChecker<TestModuleAnalysis>(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Module>>()); + } + auto PA2 = PreservedAnalyses::none(); + { + auto PAC = PA2.getChecker<TestFunctionAnalysis>(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>()); + } + auto PA3 = PreservedAnalyses::all(); + { + auto PAC = PA3.getChecker<TestFunctionAnalysis>(); + EXPECT_TRUE(PAC.preserved()); + EXPECT_TRUE(PAC.preservedSet<AllAnalysesOn<Function>>()); + } PreservedAnalyses PA4 = PA1; - EXPECT_FALSE(PA4.preserved<TestFunctionAnalysis>()); - EXPECT_FALSE(PA4.preserved<TestModuleAnalysis>()); + { + auto PAC = PA4.getChecker<TestFunctionAnalysis>(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>()); + } PA4 = PA3; - EXPECT_TRUE(PA4.preserved<TestFunctionAnalysis>()); - EXPECT_TRUE(PA4.preserved<TestModuleAnalysis>()); + { + auto PAC = PA4.getChecker<TestFunctionAnalysis>(); + EXPECT_TRUE(PAC.preserved()); + EXPECT_TRUE(PAC.preservedSet<AllAnalysesOn<Function>>()); + } PA4 = std::move(PA2); - EXPECT_FALSE(PA4.preserved<TestFunctionAnalysis>()); - EXPECT_FALSE(PA4.preserved<TestModuleAnalysis>()); - PA4.preserve<TestFunctionAnalysis>(); - EXPECT_TRUE(PA4.preserved<TestFunctionAnalysis>()); - EXPECT_FALSE(PA4.preserved<TestModuleAnalysis>()); - PA1.preserve<TestModuleAnalysis>(); - EXPECT_FALSE(PA1.preserved<TestFunctionAnalysis>()); - EXPECT_TRUE(PA1.preserved<TestModuleAnalysis>()); + { + auto PAC = PA4.getChecker<TestFunctionAnalysis>(); + EXPECT_FALSE(PAC.preserved()); + EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>()); + } +} + +TEST(PreservedAnalysesTest, Preserve) { + auto PA = PreservedAnalyses::none(); + PA.preserve<TestFunctionAnalysis>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>().preserved()); + PA.preserve<TestModuleAnalysis>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>().preserved()); + + // Redundant calls are fine. + PA.preserve<TestFunctionAnalysis>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>().preserved()); +} + +TEST(PreservedAnalysesTest, PreserveSets) { + auto PA = PreservedAnalyses::none(); + PA.preserveSet<AllAnalysesOn<Function>>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + PA.preserveSet<AllAnalysesOn<Module>>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Mixing is fine. + PA.preserve<TestFunctionAnalysis>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Redundant calls are fine. + PA.preserveSet<AllAnalysesOn<Module>>(); + EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); +} + +TEST(PreservedAnalysisTest, Intersect) { + // Setup the initial sets. + auto PA1 = PreservedAnalyses::none(); PA1.preserve<TestFunctionAnalysis>(); - EXPECT_TRUE(PA1.preserved<TestFunctionAnalysis>()); - EXPECT_TRUE(PA1.preserved<TestModuleAnalysis>()); - PA1.intersect(PA4); - EXPECT_TRUE(PA1.preserved<TestFunctionAnalysis>()); - EXPECT_FALSE(PA1.preserved<TestModuleAnalysis>()); + PA1.preserveSet<AllAnalysesOn<Module>>(); + auto PA2 = PreservedAnalyses::none(); + PA2.preserve<TestFunctionAnalysis>(); + PA2.preserveSet<AllAnalysesOn<Function>>(); + PA2.preserve<TestModuleAnalysis>(); + PA2.preserveSet<AllAnalysesOn<Module>>(); + auto PA3 = PreservedAnalyses::none(); + PA3.preserve<TestModuleAnalysis>(); + PA3.preserveSet<AllAnalysesOn<Function>>(); + + // Self intersection is a no-op. + auto Intersected = PA1; + Intersected.intersect(PA1); + EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Intersecting with all is a no-op. + Intersected.intersect(PreservedAnalyses::all()); + EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Intersecting a narrow set with a more broad set is the narrow set. + Intersected.intersect(PA2); + EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Intersecting a broad set with a more narrow set is the narrow set. + Intersected = PA2; + Intersected.intersect(PA1); + EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Intersecting with empty clears. + Intersected.intersect(PreservedAnalyses::none()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Intersecting non-overlapping clears. + Intersected = PA1; + Intersected.intersect(PA3); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // 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<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // Intersecting with move works for incoming all and existing all. + auto Tmp2 = PreservedAnalyses::all(); + Intersected.intersect(std::move(Tmp2)); + EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + Intersected = PreservedAnalyses::all(); + auto Tmp3 = PA1; + Intersected.intersect(std::move(Tmp3)); + EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved()); + EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved()); + EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); +} + +TEST(PreservedAnalysisTest, Abandon) { + auto PA = PreservedAnalyses::none(); + + // We can abandon things after they are preserved. + PA.preserve<TestFunctionAnalysis>(); + PA.abandon<TestFunctionAnalysis>(); + EXPECT_FALSE(PA.getChecker<TestFunctionAnalysis>().preserved()); + + // Repeated is fine, and abandoning if they were never preserved is fine. + PA.abandon<TestFunctionAnalysis>(); + EXPECT_FALSE(PA.getChecker<TestFunctionAnalysis>().preserved()); + PA.abandon<TestModuleAnalysis>(); + EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>().preserved()); + + // Even if the sets are preserved, the abandoned analyses' checker won't + // return true for those sets. + PA.preserveSet<AllAnalysesOn<Function>>(); + PA.preserveSet<AllAnalysesOn<Module>>(); + EXPECT_FALSE(PA.getChecker<TestFunctionAnalysis>() + .preservedSet<AllAnalysesOn<Function>>()); + EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>() + .preservedSet<AllAnalysesOn<Module>>()); + + // 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<AllAnalysesOn<Function>>()); + EXPECT_TRUE(PA.getChecker(FakeID).preservedSet<AllAnalysesOn<Module>>()); } TEST_F(PassManagerTest, Basic) { @@ -385,12 +572,16 @@ TEST_F(PassManagerTest, CustomizedPassManagerArgs) { struct TestIndirectFunctionAnalysis : public AnalysisInfoMixin<TestIndirectFunctionAnalysis> { 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<TestIndirectFunctionAnalysis>() || + auto PAC = PA.getChecker<TestIndirectFunctionAnalysis>(); + return !(PAC.preserved() || + PAC.preservedSet<AllAnalysesOn<Function>>()) || Inv.invalidate<TestFunctionAnalysis>(F, PA); } }; @@ -400,7 +591,17 @@ struct TestIndirectFunctionAnalysis /// Run the analysis pass over the function and return a result. Result run(Function &F, FunctionAnalysisManager &AM) { ++Runs; - return Result(AM.getResult<TestFunctionAnalysis>(F)); + auto &FDep = AM.getResult<TestFunctionAnalysis>(F); + auto &Proxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); + const ModuleAnalysisManager &MAM = Proxy.getManager(); + // For the test, we insist that the module analysis starts off in the + // cache. + auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(*F.getParent()); + // And register the dependency as module analysis dependencies have to be + // pre-registered on the proxy. + Proxy.registerOuterAnalysisInvalidation<TestModuleAnalysis, + TestIndirectFunctionAnalysis>(); + return Result(FDep, MDep); } private: @@ -412,6 +613,46 @@ private: 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<TestDoublyIndirectFunctionAnalysis> { + 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<TestDoublyIndirectFunctionAnalysis>(); + return !(PAC.preserved() || + PAC.preservedSet<AllAnalysesOn<Function>>()) || + Inv.invalidate<TestIndirectFunctionAnalysis>(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<TestIndirectFunctionAnalysis>(F); + return Result(IDep); + } + +private: + friend AnalysisInfoMixin<TestDoublyIndirectFunctionAnalysis>; + static AnalysisKey Key; + + int &Runs; +}; + +AnalysisKey TestDoublyIndirectFunctionAnalysis::Key; + struct LambdaPass : public PassInfoMixin<LambdaPass> { using FuncT = std::function<PreservedAnalyses(Function &, FunctionAnalysisManager &)>; @@ -426,23 +667,31 @@ struct LambdaPass : public PassInfoMixin<LambdaPass> { 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<TestIndirectFunctionAnalysis>(F).Dep.InstructionCount; + auto &DoublyIndirectResult = + AM.getResult<TestDoublyIndirectFunctionAnalysis>(F); + auto &IndirectResult = DoublyIndirectResult.IDep; + InstrCount += IndirectResult.FDep.InstructionCount; + FunctionCount += IndirectResult.MDep.FunctionCount; return PreservedAnalyses::all(); })); // Next, invalidate @@ -450,8 +699,11 @@ TEST_F(PassManagerTest, IndirectAnalysisInvalidation) { // - just the underlying (indirect) analysis for "g", and // - just the direct analysis for "h". FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) { - InstrCount += - AM.getResult<TestIndirectFunctionAnalysis>(F).Dep.InstructionCount; + auto &DoublyIndirectResult = + AM.getResult<TestDoublyIndirectFunctionAnalysis>(F); + auto &IndirectResult = DoublyIndirectResult.IDep; + InstrCount += IndirectResult.FDep.InstructionCount; + FunctionCount += IndirectResult.MDep.FunctionCount; auto PA = PreservedAnalyses::none(); if (F.getName() == "g") PA.preserve<TestFunctionAnalysis>(); @@ -462,23 +714,55 @@ TEST_F(PassManagerTest, IndirectAnalysisInvalidation) { // 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<TestIndirectFunctionAnalysis>(F).Dep.InstructionCount; + auto &DoublyIndirectResult = + AM.getResult<TestDoublyIndirectFunctionAnalysis>(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<TestDoublyIndirectFunctionAnalysis>(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<TestModuleAnalysis, Module>()); 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<TestModuleAnalysis, Module>()); + 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); } } |
