Index: llvm/trunk/include/llvm/IR/PassManager.h =================================================================== --- llvm/trunk/include/llvm/IR/PassManager.h +++ llvm/trunk/include/llvm/IR/PassManager.h @@ -64,32 +64,31 @@ struct alignas(8) AnalysisKey {}; /// A special type used to provide an address that identifies a set of related -/// analyses. +/// analyses. These sets are primarily used below to mark sets of analyses as +/// preserved. /// -/// 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. +/// For example, a transformation can indicate that it preserves the CFG of a +/// function by preserving the appropriate AnalysisSetKey. An analysis that +/// depends only on the CFG can then check if that AnalysisSetKey is preserved; +/// if it is, the analysis knows that it itself is preserved. struct alignas(8) AnalysisSetKey {}; -/// Class for tracking what analyses are preserved after a transformation pass -/// runs over some unit of IR. +/// A set of analyses that are preserved following a run of a transformation +/// pass. /// -/// 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, +/// Transformation passes build and return these objects to communicate which +/// analyses are still valid after the transformation. 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. +/// This class also lets transformation passes mark abstract *sets* of analyses +/// as preserved. A transformation that (say) does not alter the CFG can +/// indicate such by marking a particular AnalysisSetKey as preserved, and +/// then analyses can query whether that AnalysisSetKey is preserved. +/// +/// Finally, this class can represent an "abandoned" analysis, which is +/// 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 @@ -120,7 +119,8 @@ /// Mark an analysis as preserved. template void preserve() { preserve(AnalysisT::ID()); } - /// Mark an analysis as preserved using its ID. + /// \brief Given an analysis's ID, mark the analysis as preserved, adding it + /// to the set. void preserve(AnalysisKey *ID) { // Clear this ID from the explicit not-preserved set if present. NotPreservedAnalysisIDs.erase(ID); @@ -224,17 +224,17 @@ : 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. + /// Returns true if the checker's analysis was not abandoned and either + /// - the analysis is explicitly preserved or + /// - all analyses are preserved. bool preserved() { return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) || PA.PreservedIDs.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. + /// Returns true if the checker's analysis was not abandoned and either + /// - \p AnalysisSetT is explicitly preserved or + /// - all analyses are preserved. template bool preservedSet() { AnalysisSetKey *SetID = AnalysisSetT::ID(); return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) || @@ -262,8 +262,8 @@ /// Test whether all analyses are preserved (and none are abandoned). /// - /// This lets analyses optimize for the common case where a transformation - /// made no changes to the IR. + /// This is used primarily to optimize for the common case of a transformation + /// which makes no changes to the IR. bool areAllPreserved() const { return NotPreservedAnalysisIDs.empty() && PreservedIDs.count(&AllAnalysesKey); @@ -307,9 +307,9 @@ /// A CRTP mix-in to automatically provide informational APIs needed for /// passes. /// -/// This provides some boiler plate for types that are passes. +/// This provides some boilerplate for types that are passes. template struct PassInfoMixin { - /// Returns the name of the derived pass type. + /// Gets the name of the pass we are mixed into. static StringRef name() { StringRef Name = getTypeName(); if (Name.startswith("llvm::")) @@ -318,41 +318,35 @@ } }; -/// A CRTP mix-in to automatically provide informational APIs needed for -/// analysis passes. +/// A CRTP mix-in that provides informational APIs needed for analysis passes. /// -/// This provides some boiler plate for types that are analysis passes. It -/// automatically mixes in \c PassInfoMixin and adds informational APIs -/// specifically used for analyses. +/// This provides some boilerplate for types that are analysis passes. It +/// automatically mixes in \c PassInfoMixin. template struct AnalysisInfoMixin : PassInfoMixin { /// Returns an opaque, unique ID for this analysis type. /// - /// This ID is a pointer type that is guaranteed to be 8-byte aligned and - /// thus suitable for use in sets, maps, and other data structures optimized - /// for pointer-like types using the alignment-provided low bits. + /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus + /// suitable for use in sets, maps, and other data structures that use the low + /// bits of pointers. /// /// Note that this requires the derived type provide a static \c AnalysisKey /// member called \c Key. /// - /// FIXME: The only reason the derived type needs to provide this rather than - /// this mixin providing it is due to broken implementations which cannot - /// correctly unique a templated static so that they have the same addresses - /// for each instantiation and are definitively emitted once for each - /// instantiation. The only currently known platform with this limitation are - /// Windows DLL builds, specifically building each part of LLVM as a DLL. If - /// we ever remove that build configuration, this mixin can provide the - /// static key as well. + /// FIXME: The only reason the mixin type itself can't declare the Key value + /// is that some compilers cannot correctly unique a templated static variable + /// so it has the same addresses in each instantiation. The only currently + /// known platform with this limitation is Windows DLL builds, specifically + /// building each part of LLVM as a DLL. If we ever remove that build + /// configuration, this mixin can provide the static key as well. static AnalysisKey *ID() { return &DerivedT::Key; } }; -/// A class template to provide analysis sets for IR units. +/// This templated class represents "all analyses that operate over " (e.g. a Function or a Module) in instances of +/// PreservedAnalysis. /// -/// Analyses operate on units of IR. It is useful to be able to talk about -/// preservation of all analyses for a given unit of IR as a set. This class -/// template can be used with the \c PreservedAnalyses API for that purpose and -/// the \c AnalysisManager will automatically check and use this set to skip -/// invalidation events. +/// This lets a transformation say e.g. "I preserved all function analyses". /// /// Note that you must provide an explicit instantiation declaration and /// definition for this template in order to get the correct behavior on @@ -371,17 +365,18 @@ extern template class AllAnalysesOn; extern template class AllAnalysesOn; -/// \brief Manages a sequence of passes over units of IR. +/// \brief Manages a sequence of passes over a particular unit of IR. /// -/// A pass manager contains a sequence of passes to run over units of IR. It is -/// itself a valid pass over that unit of IR, and when over some given IR will -/// run each pass in sequence. This is the primary and most basic building -/// block of a pass pipeline. -/// -/// If it is run with an \c AnalysisManager argument, it will propagate -/// that analysis manager to each pass it runs, as well as calling the analysis -/// manager's invalidation routine with the PreservedAnalyses of each pass it -/// runs. +/// A pass manager contains a sequence of passes to run over a particular unit +/// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of +/// IR, and when run over some given IR will run each of its contained passes in +/// sequence. Pass managers are the primary and most basic building block of a +/// pass pipeline. +/// +/// When you run a pass manager, you provide an \c AnalysisManager +/// argument. The pass manager will propagate that analysis manager to each +/// pass it runs, and will call the analysis manager's invalidation routine with +/// the PreservedAnalyses of each pass it runs. template , typename... ExtraArgTs> @@ -390,7 +385,7 @@ public: /// \brief Construct a pass manager. /// - /// It can be passed a flag to get debug logging as the passes are run. + /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs(). explicit PassManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {} // FIXME: These are equivalent to the default move constructor/move @@ -400,13 +395,15 @@ PassManager(PassManager &&Arg) : Passes(std::move(Arg.Passes)), DebugLogging(std::move(Arg.DebugLogging)) {} + PassManager &operator=(PassManager &&RHS) { Passes = std::move(RHS.Passes); DebugLogging = std::move(RHS.DebugLogging); return *this; } - /// \brief Run all of the passes in this manager over the IR. + /// \brief Run all of the passes in this manager over the given unit of IR. + /// ExtraArgs are passed to each pass. PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs) { PreservedAnalyses PA = PreservedAnalyses::all(); @@ -425,7 +422,7 @@ // invalidates analyses. AM.invalidate(IR, PassPA); - // Finally, we intersect the preserved analyses to compute the aggregate + // Finally, intersect the preserved analyses to compute the aggregate // preserved set for this pass manager. PA.intersect(std::move(PassPA)); @@ -473,30 +470,29 @@ /// \brief Convenience typedef for a pass manager over functions. typedef PassManager FunctionPassManager; -/// \brief A generic analysis pass manager with lazy running and caching of +/// \brief A container for analyses that lazily runs them and caches their /// results. /// -/// This analysis manager can be used for any IR unit where the address of the -/// IR unit sufficies as its identity. It manages the cache for a unit of IR via -/// the address of each unit of IR cached. +/// This class can manage analyses for any IR unit where the address of the IR +/// unit sufficies as its identity. template class AnalysisManager { public: class Invalidator; private: - // Now that we've defined our invalidator, we can build types for the concept - // types. + // Now that we've defined our invalidator, we can define the concept types. typedef detail::AnalysisResultConcept ResultConceptT; typedef detail::AnalysisPassConcept PassConceptT; - /// \brief List of function analysis pass IDs and associated concept pointers. + /// \brief List of analysis pass IDs and associated concept pointers. /// /// Requires iterators to be valid across appending new entries and arbitrary - /// erases. Provides the analysis ID to enable finding iterators to a given entry - /// in maps below, and provides the storage for the actual result concept. + /// erases. Provides the analysis ID to enable finding iterators to a given + /// entry in maps below, and provides the storage for the actual result + /// concept. typedef std::list>> AnalysisResultListT; @@ -504,8 +500,8 @@ typedef DenseMap AnalysisResultListMapT; /// \brief Map type from a pair of analysis ID and IRUnitT pointer to an - /// iterator into a particular result list which is where the actual result - /// is stored. + /// iterator into a particular result list (which is where the actual analysis + /// result is stored). typedef DenseMap, typename AnalysisResultListT::iterator> AnalysisResultMapT; @@ -515,28 +511,28 @@ /// /// When an analysis result embeds handles to other analysis results, it /// needs to be invalidated both when its own information isn't preserved and - /// if any of those embedded analysis results end up invalidated. We pass in - /// an \c Invalidator object from the analysis manager in order to let the - /// analysis results themselves define the dependency graph on the fly. This - /// avoids building an explicit data structure representation of the + /// when any of its embedded analysis results end up invalidated. We pass an + /// \c Invalidator object as an argument to \c invalidate() in order to let + /// the analysis results themselves define the dependency graph on the fly. + /// This lets us avoid building building an explicit representation of the /// dependencies between analysis results. class Invalidator { public: /// Trigger the invalidation of some other analysis pass if not already - /// handled and return whether it will in fact be invalidated. + /// handled and return whether it was in fact invalidated. /// /// This is expected to be called from within a given analysis result's \c /// invalidate method to trigger a depth-first walk of all inter-analysis /// dependencies. The same \p IR unit and \p PA passed to that result's \c /// invalidate method should in turn be provided to this routine. /// - /// The first time this is called for a given analysis pass, it will - /// trigger the corresponding result's \c invalidate method to be called. - /// Subsequent calls will use a cache of the results of that initial call. - /// It is an error to form cyclic dependencies between analysis results. + /// The first time this is called for a given analysis pass, it will call + /// the corresponding result's \c invalidate method. Subsequent calls will + /// use a cache of the results of that initial call. It is an error to form + /// cyclic dependencies between analysis results. /// - /// This returns true if the given analysis pass's result is invalid and - /// any dependecies on it will become invalid as a result. + /// This returns true if the given analysis's result is invalid. Any + /// dependecies on it will become invalid as a result. template bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { typedef detail::AnalysisResultModel(*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. + // Insert into the map whether the result should be invalidated and return + // that. Note that we cannot reuse IMapI and must do a fresh insert here, + // as calling invalidate could (recursively) insert things into the map, + // making any iterator or reference invalid. bool Inserted; std::tie(IMapI, Inserted) = IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)}); @@ -600,8 +596,7 @@ /// \brief Construct an empty analysis manager. /// - /// A flag can be passed to indicate that the manager should perform debug - /// logging. + /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs(). AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {} AnalysisManager(AnalysisManager &&) = default; AnalysisManager &operator=(AnalysisManager &&) = default; @@ -614,11 +609,11 @@ return AnalysisResults.empty(); } - /// \brief Clear any results for a single unit of IR. + /// \brief Clear any cached analysis results for a single unit of IR. /// - /// This doesn't invalidate but directly clears the results. It is useful - /// when the IR is being removed and we want to clear out all the memory - /// pinned for it. + /// This doesn't invalidate, but instead simply deletes, the relevant results. + /// It is useful when the IR is being removed and we want to clear out all the + /// memory pinned for it. void clear(IRUnitT &IR) { if (DebugLogging) dbgs() << "Clearing all analysis results for: " << IR.getName() << "\n"; @@ -626,7 +621,7 @@ auto ResultsListI = AnalysisResultLists.find(&IR); if (ResultsListI == AnalysisResultLists.end()) return; - // Clear the map pointing into the results list. + // Delete the map entries that point into the results list. for (auto &IDAndResult : ResultsListI->second) AnalysisResults.erase({IDAndResult.first, &IR}); @@ -634,21 +629,20 @@ AnalysisResultLists.erase(ResultsListI); } - /// \brief Clear the analysis result cache. + /// \brief Clear all analysis results cached by this AnalysisManager. /// - /// This routine allows cleaning up when the set of IR units itself has - /// potentially changed, and thus we can't even look up a a result and - /// invalidate it directly. Notably, this does *not* call invalidate - /// functions as there is nothing to be done for them. + /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply + /// deletes them. This lets you clean up the AnalysisManager when the set of + /// IR units itself has potentially changed, and thus we can't even look up a + /// a result and invalidate/clear it directly. void clear() { AnalysisResults.clear(); AnalysisResultLists.clear(); } - /// \brief Get the result of an analysis pass for this module. + /// \brief Get the result of an analysis pass for a given IR unit. /// - /// If there is not a valid cached result in the manager already, this will - /// re-run the analysis to produce a valid result. + /// Runs the analysis if a cached result is not available. template typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) { assert(AnalysisPasses.count(PassT::ID()) && @@ -661,7 +655,7 @@ return static_cast(ResultConcept).Result; } - /// \brief Get the cached result of an analysis pass for this module. + /// \brief Get the cached result of an analysis pass for a given IR unit. /// /// This method never runs the analysis. /// @@ -683,22 +677,21 @@ /// \brief Register an analysis pass with the manager. /// - /// The argument is a callable whose result is a pass. This allows passing in - /// a lambda to construct the pass. + /// The parameter is a callable whose result is an analysis pass. This allows + /// passing in a lambda to construct the analysis. /// - /// The pass type registered is the result type of calling the argument. If - /// that pass has already been registered, then the argument will not be - /// called and this function will return false. Otherwise, the pass type - /// becomes registered, with the instance provided by calling the argument - /// once, and this function returns true. - /// - /// While this returns whether or not the pass type was already registered, - /// there in't an independent way to query that as that would be prone to - /// risky use when *querying* the analysis manager. Instead, the only - /// supported use case is avoiding duplicate registry of an analysis. This - /// interface also lends itself to minimizing the number of times we have to - /// do lookups for analyses or construct complex passes only to throw them - /// away. + /// The analysis type to register is the type returned by calling the \c + /// PassBuilder argument. If that type has already been registered, then the + /// argument will not be called and this function will return false. + /// Otherwise, we register the analysis returned by calling \c PassBuilder(), + /// and this function returns true. + /// + /// (Note: Although the return value of this function indicates whether or not + /// an analysis was previously registered, there intentionally isn't a way to + /// query this directly. Instead, you should just register all the analyses + /// you might want and let this class run them lazily. This idiom lets us + /// minimize the number of times we have to look up analyses in our + /// hashtable.) template bool registerPass(PassBuilderT &&PassBuilder) { typedef decltype(PassBuilder()) PassT; @@ -718,17 +711,18 @@ /// \brief Invalidate a specific analysis pass for an IR module. /// - /// Note that the analysis result can disregard invalidation. + /// Note that the analysis result can disregard invalidation, if it determines + /// it is in fact still valid. template void invalidate(IRUnitT &IR) { assert(AnalysisPasses.count(PassT::ID()) && "This analysis pass was not registered prior to being invalidated"); invalidateImpl(PassT::ID(), IR); } - /// \brief Invalidate analyses cached for an IR unit. + /// \brief Invalidate cached analyses for an IR unit. /// /// Walk through all of the analyses pertaining to this unit of IR and - /// invalidate them unless they are preserved by the PreservedAnalyses set. + /// invalidate them, unless they are preserved by the PreservedAnalyses set. void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { // We're done if all analyses on this IR unit are preserved. if (PA.allAnalysesInSetPreserved>()) @@ -738,8 +732,8 @@ dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName() << "\n"; - // Track whether each pass's result is invalidated. Memoize the results - // using the IsResultInvalidated map. + // Track whether each analysis's result is invalidated in + // IsResultInvalidated. SmallDenseMap IsResultInvalidated; Invalidator Inv(IsResultInvalidated, AnalysisResults); AnalysisResultListT &ResultsList = AnalysisResultLists[&IR]; @@ -758,9 +752,9 @@ // Try to invalidate the result, giving it the Invalidator so it can // recursively query for any dependencies it has and record the result. - // Note that we cannot re-use 'IMapI' here or pre-insert the ID as the - // invalidate method may insert things into the map as well, invalidating - // any iterator or pointer. + // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as + // Result.invalidate may insert things into the map, invalidating our + // iterator. bool Inserted = IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)}) .second; @@ -873,7 +867,7 @@ /// analysis result. AnalysisResultMapT AnalysisResults; - /// \brief A flag indicating whether debug logging is enabled. + /// \brief Indicates whether we log to \c llvm::dbgs(). bool DebugLogging; };