1 //===- PassManager.h - Pass management infrastructure -----------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This header defines various interfaces for pass management in LLVM. There
11 /// is no "pass" interface in LLVM per se. Instead, an instance of any class
12 /// which supports a method to 'run' it over a unit of IR can be used as
13 /// a pass. A pass manager is generally a tool to collect a sequence of passes
14 /// which run over a particular IR construct, and run each of them in sequence
15 /// over each such construct in the containing IR construct. As there is no
16 /// containing IR construct for a Module, a manager for passes over modules
17 /// forms the base case which runs its managed passes in sequence over the
18 /// single module provided.
20 /// The core IR library provides managers for running passes over
21 /// modules and functions.
23 /// * FunctionPassManager can run over a Module, runs each pass over
25 /// * ModulePassManager must be directly run, runs each pass over the Module.
27 /// Note that the implementations of the pass managers use concept-based
28 /// polymorphism as outlined in the "Value Semantics and Concept-based
29 /// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base
30 /// Class of Evil") by Sean Parent:
31 /// * http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations
32 /// * http://www.youtube.com/watch?v=_BpMYeUFXv8
33 /// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil
35 //===----------------------------------------------------------------------===//
37 #ifndef LLVM_IR_PASSMANAGER_H
38 #define LLVM_IR_PASSMANAGER_H
40 #include "llvm/ADT/DenseMap.h"
41 #include "llvm/ADT/SmallPtrSet.h"
42 #include "llvm/ADT/StringRef.h"
43 #include "llvm/ADT/TinyPtrVector.h"
44 #include "llvm/IR/Function.h"
45 #include "llvm/IR/Module.h"
46 #include "llvm/IR/PassInstrumentation.h"
47 #include "llvm/IR/PassManagerInternal.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Support/TypeName.h"
51 #include "llvm/Support/raw_ostream.h"
59 #include <type_traits>
65 /// A special type used by analysis passes to provide an address that
66 /// identifies that particular analysis pass type.
68 /// Analysis passes should have a static data member of this type and derive
69 /// from the \c AnalysisInfoMixin to get a static ID method used to identify
70 /// the analysis in the pass management infrastructure.
71 struct alignas(8) AnalysisKey
{};
73 /// A special type used to provide an address that identifies a set of related
74 /// analyses. These sets are primarily used below to mark sets of analyses as
77 /// For example, a transformation can indicate that it preserves the CFG of a
78 /// function by preserving the appropriate AnalysisSetKey. An analysis that
79 /// depends only on the CFG can then check if that AnalysisSetKey is preserved;
80 /// if it is, the analysis knows that it itself is preserved.
81 struct alignas(8) AnalysisSetKey
{};
83 /// This templated class represents "all analyses that operate over \<a
84 /// particular IR unit\>" (e.g. a Function or a Module) in instances of
85 /// PreservedAnalysis.
87 /// This lets a transformation say e.g. "I preserved all function analyses".
89 /// Note that you must provide an explicit instantiation declaration and
90 /// definition for this template in order to get the correct behavior on
91 /// Windows. Otherwise, the address of SetKey will not be stable.
92 template <typename IRUnitT
> class AllAnalysesOn
{
94 static AnalysisSetKey
*ID() { return &SetKey
; }
97 static AnalysisSetKey SetKey
;
100 template <typename IRUnitT
> AnalysisSetKey AllAnalysesOn
<IRUnitT
>::SetKey
;
102 extern template class AllAnalysesOn
<Module
>;
103 extern template class AllAnalysesOn
<Function
>;
105 /// Represents analyses that only rely on functions' control flow.
107 /// This can be used with \c PreservedAnalyses to mark the CFG as preserved and
108 /// to query whether it has been preserved.
110 /// The CFG of a function is defined as the set of basic blocks and the edges
111 /// between them. Changing the set of basic blocks in a function is enough to
112 /// mutate the CFG. Mutating the condition of a branch or argument of an
113 /// invoked function does not mutate the CFG, but changing the successor labels
114 /// of those instructions does.
117 static AnalysisSetKey
*ID() { return &SetKey
; }
120 static AnalysisSetKey SetKey
;
123 /// A set of analyses that are preserved following a run of a transformation
126 /// Transformation passes build and return these objects to communicate which
127 /// analyses are still valid after the transformation. For most passes this is
128 /// fairly simple: if they don't change anything all analyses are preserved,
129 /// otherwise only a short list of analyses that have been explicitly updated
132 /// This class also lets transformation passes mark abstract *sets* of analyses
133 /// as preserved. A transformation that (say) does not alter the CFG can
134 /// indicate such by marking a particular AnalysisSetKey as preserved, and
135 /// then analyses can query whether that AnalysisSetKey is preserved.
137 /// Finally, this class can represent an "abandoned" analysis, which is
138 /// not preserved even if it would be covered by some abstract set of analyses.
140 /// Given a `PreservedAnalyses` object, an analysis will typically want to
141 /// figure out whether it is preserved. In the example below, MyAnalysisType is
142 /// preserved if it's not abandoned, and (a) it's explicitly marked as
143 /// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both
144 /// AnalysisSetA and AnalysisSetB are preserved.
147 /// auto PAC = PA.getChecker<MyAnalysisType>();
148 /// if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() ||
149 /// (PAC.preservedSet<AnalysisSetA>() &&
150 /// PAC.preservedSet<AnalysisSetB>())) {
151 /// // The analysis has been successfully preserved ...
154 class PreservedAnalyses
{
156 /// Convenience factory function for the empty preserved set.
157 static PreservedAnalyses
none() { return PreservedAnalyses(); }
159 /// Construct a special preserved set that preserves all passes.
160 static PreservedAnalyses
all() {
161 PreservedAnalyses PA
;
162 PA
.PreservedIDs
.insert(&AllAnalysesKey
);
166 /// Construct a preserved analyses object with a single preserved set.
167 template <typename AnalysisSetT
>
168 static PreservedAnalyses
allInSet() {
169 PreservedAnalyses PA
;
170 PA
.preserveSet
<AnalysisSetT
>();
174 /// Mark an analysis as preserved.
175 template <typename AnalysisT
> void preserve() { preserve(AnalysisT::ID()); }
177 /// Given an analysis's ID, mark the analysis as preserved, adding it
179 void preserve(AnalysisKey
*ID
) {
180 // Clear this ID from the explicit not-preserved set if present.
181 NotPreservedAnalysisIDs
.erase(ID
);
183 // If we're not already preserving all analyses (other than those in
184 // NotPreservedAnalysisIDs).
185 if (!areAllPreserved())
186 PreservedIDs
.insert(ID
);
189 /// Mark an analysis set as preserved.
190 template <typename AnalysisSetT
> void preserveSet() {
191 preserveSet(AnalysisSetT::ID());
194 /// Mark an analysis set as preserved using its ID.
195 void preserveSet(AnalysisSetKey
*ID
) {
196 // If we're not already in the saturated 'all' state, add this set.
197 if (!areAllPreserved())
198 PreservedIDs
.insert(ID
);
201 /// Mark an analysis as abandoned.
203 /// An abandoned analysis is not preserved, even if it is nominally covered
204 /// by some other set or was previously explicitly marked as preserved.
206 /// Note that you can only abandon a specific analysis, not a *set* of
208 template <typename AnalysisT
> void abandon() { abandon(AnalysisT::ID()); }
210 /// Mark an analysis as abandoned using its ID.
212 /// An abandoned analysis is not preserved, even if it is nominally covered
213 /// by some other set or was previously explicitly marked as preserved.
215 /// Note that you can only abandon a specific analysis, not a *set* of
217 void abandon(AnalysisKey
*ID
) {
218 PreservedIDs
.erase(ID
);
219 NotPreservedAnalysisIDs
.insert(ID
);
222 /// Intersect this set with another in place.
224 /// This is a mutating operation on this preserved set, removing all
225 /// preserved passes which are not also preserved in the argument.
226 void intersect(const PreservedAnalyses
&Arg
) {
227 if (Arg
.areAllPreserved())
229 if (areAllPreserved()) {
233 // The intersection requires the *union* of the explicitly not-preserved
234 // IDs and the *intersection* of the preserved IDs.
235 for (auto ID
: Arg
.NotPreservedAnalysisIDs
) {
236 PreservedIDs
.erase(ID
);
237 NotPreservedAnalysisIDs
.insert(ID
);
239 for (auto ID
: PreservedIDs
)
240 if (!Arg
.PreservedIDs
.count(ID
))
241 PreservedIDs
.erase(ID
);
244 /// Intersect this set with a temporary other set in place.
246 /// This is a mutating operation on this preserved set, removing all
247 /// preserved passes which are not also preserved in the argument.
248 void intersect(PreservedAnalyses
&&Arg
) {
249 if (Arg
.areAllPreserved())
251 if (areAllPreserved()) {
252 *this = std::move(Arg
);
255 // The intersection requires the *union* of the explicitly not-preserved
256 // IDs and the *intersection* of the preserved IDs.
257 for (auto ID
: Arg
.NotPreservedAnalysisIDs
) {
258 PreservedIDs
.erase(ID
);
259 NotPreservedAnalysisIDs
.insert(ID
);
261 for (auto ID
: PreservedIDs
)
262 if (!Arg
.PreservedIDs
.count(ID
))
263 PreservedIDs
.erase(ID
);
266 /// A checker object that makes it easy to query for whether an analysis or
267 /// some set covering it is preserved.
268 class PreservedAnalysisChecker
{
269 friend class PreservedAnalyses
;
271 const PreservedAnalyses
&PA
;
272 AnalysisKey
*const ID
;
273 const bool IsAbandoned
;
275 /// A PreservedAnalysisChecker is tied to a particular Analysis because
276 /// `preserved()` and `preservedSet()` both return false if the Analysis
278 PreservedAnalysisChecker(const PreservedAnalyses
&PA
, AnalysisKey
*ID
)
279 : PA(PA
), ID(ID
), IsAbandoned(PA
.NotPreservedAnalysisIDs
.count(ID
)) {}
282 /// Returns true if the checker's analysis was not abandoned and either
283 /// - the analysis is explicitly preserved or
284 /// - all analyses are preserved.
286 return !IsAbandoned
&& (PA
.PreservedIDs
.count(&AllAnalysesKey
) ||
287 PA
.PreservedIDs
.count(ID
));
290 /// Return true if the checker's analysis was not abandoned, i.e. it was not
291 /// explicitly invalidated. Even if the analysis is not explicitly
292 /// preserved, if the analysis is known stateless, then it is preserved.
293 bool preservedWhenStateless() {
297 /// Returns true if the checker's analysis was not abandoned and either
298 /// - \p AnalysisSetT is explicitly preserved or
299 /// - all analyses are preserved.
300 template <typename AnalysisSetT
> bool preservedSet() {
301 AnalysisSetKey
*SetID
= AnalysisSetT::ID();
302 return !IsAbandoned
&& (PA
.PreservedIDs
.count(&AllAnalysesKey
) ||
303 PA
.PreservedIDs
.count(SetID
));
307 /// Build a checker for this `PreservedAnalyses` and the specified analysis
310 /// You can use the returned object to query whether an analysis was
311 /// preserved. See the example in the comment on `PreservedAnalysis`.
312 template <typename AnalysisT
> PreservedAnalysisChecker
getChecker() const {
313 return PreservedAnalysisChecker(*this, AnalysisT::ID());
316 /// Build a checker for this `PreservedAnalyses` and the specified analysis
319 /// You can use the returned object to query whether an analysis was
320 /// preserved. See the example in the comment on `PreservedAnalysis`.
321 PreservedAnalysisChecker
getChecker(AnalysisKey
*ID
) const {
322 return PreservedAnalysisChecker(*this, ID
);
325 /// Test whether all analyses are preserved (and none are abandoned).
327 /// This is used primarily to optimize for the common case of a transformation
328 /// which makes no changes to the IR.
329 bool areAllPreserved() const {
330 return NotPreservedAnalysisIDs
.empty() &&
331 PreservedIDs
.count(&AllAnalysesKey
);
334 /// Directly test whether a set of analyses is preserved.
336 /// This is only true when no analyses have been explicitly abandoned.
337 template <typename AnalysisSetT
> bool allAnalysesInSetPreserved() const {
338 return allAnalysesInSetPreserved(AnalysisSetT::ID());
341 /// Directly test whether a set of analyses is preserved.
343 /// This is only true when no analyses have been explicitly abandoned.
344 bool allAnalysesInSetPreserved(AnalysisSetKey
*SetID
) const {
345 return NotPreservedAnalysisIDs
.empty() &&
346 (PreservedIDs
.count(&AllAnalysesKey
) || PreservedIDs
.count(SetID
));
350 /// A special key used to indicate all analyses.
351 static AnalysisSetKey AllAnalysesKey
;
353 /// The IDs of analyses and analysis sets that are preserved.
354 SmallPtrSet
<void *, 2> PreservedIDs
;
356 /// The IDs of explicitly not-preserved analyses.
358 /// If an analysis in this set is covered by a set in `PreservedIDs`, we
359 /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always
360 /// "wins" over analysis sets in `PreservedIDs`.
362 /// Also, a given ID should never occur both here and in `PreservedIDs`.
363 SmallPtrSet
<AnalysisKey
*, 2> NotPreservedAnalysisIDs
;
366 // Forward declare the analysis manager template.
367 template <typename IRUnitT
, typename
... ExtraArgTs
> class AnalysisManager
;
369 /// A CRTP mix-in to automatically provide informational APIs needed for
372 /// This provides some boilerplate for types that are passes.
373 template <typename DerivedT
> struct PassInfoMixin
{
374 /// Gets the name of the pass we are mixed into.
375 static StringRef
name() {
376 static_assert(std::is_base_of
<PassInfoMixin
, DerivedT
>::value
,
377 "Must pass the derived type as the template argument!");
378 StringRef Name
= getTypeName
<DerivedT
>();
379 if (Name
.startswith("llvm::"))
380 Name
= Name
.drop_front(strlen("llvm::"));
385 /// A CRTP mix-in that provides informational APIs needed for analysis passes.
387 /// This provides some boilerplate for types that are analysis passes. It
388 /// automatically mixes in \c PassInfoMixin.
389 template <typename DerivedT
>
390 struct AnalysisInfoMixin
: PassInfoMixin
<DerivedT
> {
391 /// Returns an opaque, unique ID for this analysis type.
393 /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus
394 /// suitable for use in sets, maps, and other data structures that use the low
395 /// bits of pointers.
397 /// Note that this requires the derived type provide a static \c AnalysisKey
398 /// member called \c Key.
400 /// FIXME: The only reason the mixin type itself can't declare the Key value
401 /// is that some compilers cannot correctly unique a templated static variable
402 /// so it has the same addresses in each instantiation. The only currently
403 /// known platform with this limitation is Windows DLL builds, specifically
404 /// building each part of LLVM as a DLL. If we ever remove that build
405 /// configuration, this mixin can provide the static key as well.
406 static AnalysisKey
*ID() {
407 static_assert(std::is_base_of
<AnalysisInfoMixin
, DerivedT
>::value
,
408 "Must pass the derived type as the template argument!");
409 return &DerivedT::Key
;
415 /// Actual unpacker of extra arguments in getAnalysisResult,
416 /// passes only those tuple arguments that are mentioned in index_sequence.
417 template <typename PassT
, typename IRUnitT
, typename AnalysisManagerT
,
418 typename
... ArgTs
, size_t... Ns
>
419 typename
PassT::Result
420 getAnalysisResultUnpackTuple(AnalysisManagerT
&AM
, IRUnitT
&IR
,
421 std::tuple
<ArgTs
...> Args
,
422 std::index_sequence
<Ns
...>) {
424 return AM
.template getResult
<PassT
>(IR
, std::get
<Ns
>(Args
)...);
427 /// Helper for *partial* unpacking of extra arguments in getAnalysisResult.
429 /// Arguments passed in tuple come from PassManager, so they might have extra
430 /// arguments after those AnalysisManager's ExtraArgTs ones that we need to
431 /// pass to getResult.
432 template <typename PassT
, typename IRUnitT
, typename
... AnalysisArgTs
,
433 typename
... MainArgTs
>
434 typename
PassT::Result
435 getAnalysisResult(AnalysisManager
<IRUnitT
, AnalysisArgTs
...> &AM
, IRUnitT
&IR
,
436 std::tuple
<MainArgTs
...> Args
) {
437 return (getAnalysisResultUnpackTuple
<
438 PassT
, IRUnitT
>)(AM
, IR
, Args
,
439 std::index_sequence_for
<AnalysisArgTs
...>{});
442 } // namespace detail
444 // Forward declare the pass instrumentation analysis explicitly queried in
445 // generic PassManager code.
446 // FIXME: figure out a way to move PassInstrumentationAnalysis into its own
448 class PassInstrumentationAnalysis
;
450 /// Manages a sequence of passes over a particular unit of IR.
452 /// A pass manager contains a sequence of passes to run over a particular unit
453 /// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of
454 /// IR, and when run over some given IR will run each of its contained passes in
455 /// sequence. Pass managers are the primary and most basic building block of a
458 /// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT>
459 /// argument. The pass manager will propagate that analysis manager to each
460 /// pass it runs, and will call the analysis manager's invalidation routine with
461 /// the PreservedAnalyses of each pass it runs.
462 template <typename IRUnitT
,
463 typename AnalysisManagerT
= AnalysisManager
<IRUnitT
>,
464 typename
... ExtraArgTs
>
465 class PassManager
: public PassInfoMixin
<
466 PassManager
<IRUnitT
, AnalysisManagerT
, ExtraArgTs
...>> {
468 /// Construct a pass manager.
470 /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs().
471 explicit PassManager(bool DebugLogging
= false) : DebugLogging(DebugLogging
) {}
473 // FIXME: These are equivalent to the default move constructor/move
474 // assignment. However, using = default triggers linker errors due to the
475 // explicit instantiations below. Find away to use the default and remove the
476 // duplicated code here.
477 PassManager(PassManager
&&Arg
)
478 : Passes(std::move(Arg
.Passes
)),
479 DebugLogging(std::move(Arg
.DebugLogging
)) {}
481 PassManager
&operator=(PassManager
&&RHS
) {
482 Passes
= std::move(RHS
.Passes
);
483 DebugLogging
= std::move(RHS
.DebugLogging
);
487 /// Run all of the passes in this manager over the given unit of IR.
488 /// ExtraArgs are passed to each pass.
489 PreservedAnalyses
run(IRUnitT
&IR
, AnalysisManagerT
&AM
,
490 ExtraArgTs
... ExtraArgs
) {
491 PreservedAnalyses PA
= PreservedAnalyses::all();
493 // Request PassInstrumentation from analysis manager, will use it to run
494 // instrumenting callbacks for the passes later.
495 // Here we use std::tuple wrapper over getResult which helps to extract
496 // AnalysisManager's arguments out of the whole ExtraArgs set.
497 PassInstrumentation PI
=
498 detail::getAnalysisResult
<PassInstrumentationAnalysis
>(
499 AM
, IR
, std::tuple
<ExtraArgTs
...>(ExtraArgs
...));
502 dbgs() << "Starting " << getTypeName
<IRUnitT
>() << " pass manager run.\n";
504 for (unsigned Idx
= 0, Size
= Passes
.size(); Idx
!= Size
; ++Idx
) {
505 auto *P
= Passes
[Idx
].get();
507 dbgs() << "Running pass: " << P
->name() << " on " << IR
.getName()
510 // Check the PassInstrumentation's BeforePass callbacks before running the
511 // pass, skip its execution completely if asked to (callback returns
513 if (!PI
.runBeforePass
<IRUnitT
>(*P
, IR
))
516 PreservedAnalyses PassPA
= P
->run(IR
, AM
, ExtraArgs
...);
518 // Call onto PassInstrumentation's AfterPass callbacks immediately after
520 PI
.runAfterPass
<IRUnitT
>(*P
, IR
);
522 // Update the analysis manager as each pass runs and potentially
523 // invalidates analyses.
524 AM
.invalidate(IR
, PassPA
);
526 // Finally, intersect the preserved analyses to compute the aggregate
527 // preserved set for this pass manager.
528 PA
.intersect(std::move(PassPA
));
530 // FIXME: Historically, the pass managers all called the LLVM context's
531 // yield function here. We don't have a generic way to acquire the
532 // context and it isn't yet clear what the right pattern is for yielding
533 // in the new pass manager so it is currently omitted.
534 //IR.getContext().yield();
537 // Invalidation was handled after each pass in the above loop for the
538 // current unit of IR. Therefore, the remaining analysis results in the
539 // AnalysisManager are preserved. We mark this with a set so that we don't
540 // need to inspect each one individually.
541 PA
.preserveSet
<AllAnalysesOn
<IRUnitT
>>();
544 dbgs() << "Finished " << getTypeName
<IRUnitT
>() << " pass manager run.\n";
549 template <typename PassT
> void addPass(PassT Pass
) {
551 detail::PassModel
<IRUnitT
, PassT
, PreservedAnalyses
, AnalysisManagerT
,
554 Passes
.emplace_back(new PassModelT(std::move(Pass
)));
559 detail::PassConcept
<IRUnitT
, AnalysisManagerT
, ExtraArgTs
...>;
561 std::vector
<std::unique_ptr
<PassConceptT
>> Passes
;
563 /// Flag indicating whether we should do debug logging.
567 extern template class PassManager
<Module
>;
569 /// Convenience typedef for a pass manager over modules.
570 using ModulePassManager
= PassManager
<Module
>;
572 extern template class PassManager
<Function
>;
574 /// Convenience typedef for a pass manager over functions.
575 using FunctionPassManager
= PassManager
<Function
>;
577 /// Pseudo-analysis pass that exposes the \c PassInstrumentation to pass
578 /// managers. Goes before AnalysisManager definition to provide its
579 /// internals (e.g PassInstrumentationAnalysis::ID) for use there if needed.
580 /// FIXME: figure out a way to move PassInstrumentationAnalysis into its own
582 class PassInstrumentationAnalysis
583 : public AnalysisInfoMixin
<PassInstrumentationAnalysis
> {
584 friend AnalysisInfoMixin
<PassInstrumentationAnalysis
>;
585 static AnalysisKey Key
;
587 PassInstrumentationCallbacks
*Callbacks
;
590 /// PassInstrumentationCallbacks object is shared, owned by something else,
591 /// not this analysis.
592 PassInstrumentationAnalysis(PassInstrumentationCallbacks
*Callbacks
= nullptr)
593 : Callbacks(Callbacks
) {}
595 using Result
= PassInstrumentation
;
597 template <typename IRUnitT
, typename AnalysisManagerT
, typename
... ExtraArgTs
>
598 Result
run(IRUnitT
&, AnalysisManagerT
&, ExtraArgTs
&&...) {
599 return PassInstrumentation(Callbacks
);
603 /// A container for analyses that lazily runs them and caches their
606 /// This class can manage analyses for any IR unit where the address of the IR
607 /// unit sufficies as its identity.
608 template <typename IRUnitT
, typename
... ExtraArgTs
> class AnalysisManager
{
613 // Now that we've defined our invalidator, we can define the concept types.
614 using ResultConceptT
=
615 detail::AnalysisResultConcept
<IRUnitT
, PreservedAnalyses
, Invalidator
>;
617 detail::AnalysisPassConcept
<IRUnitT
, PreservedAnalyses
, Invalidator
,
620 /// List of analysis pass IDs and associated concept pointers.
622 /// Requires iterators to be valid across appending new entries and arbitrary
623 /// erases. Provides the analysis ID to enable finding iterators to a given
624 /// entry in maps below, and provides the storage for the actual result
626 using AnalysisResultListT
=
627 std::list
<std::pair
<AnalysisKey
*, std::unique_ptr
<ResultConceptT
>>>;
629 /// Map type from IRUnitT pointer to our custom list type.
630 using AnalysisResultListMapT
= DenseMap
<IRUnitT
*, AnalysisResultListT
>;
632 /// Map type from a pair of analysis ID and IRUnitT pointer to an
633 /// iterator into a particular result list (which is where the actual analysis
634 /// result is stored).
635 using AnalysisResultMapT
=
636 DenseMap
<std::pair
<AnalysisKey
*, IRUnitT
*>,
637 typename
AnalysisResultListT::iterator
>;
640 /// API to communicate dependencies between analyses during invalidation.
642 /// When an analysis result embeds handles to other analysis results, it
643 /// needs to be invalidated both when its own information isn't preserved and
644 /// when any of its embedded analysis results end up invalidated. We pass an
645 /// \c Invalidator object as an argument to \c invalidate() in order to let
646 /// the analysis results themselves define the dependency graph on the fly.
647 /// This lets us avoid building building an explicit representation of the
648 /// dependencies between analysis results.
651 /// Trigger the invalidation of some other analysis pass if not already
652 /// handled and return whether it was in fact invalidated.
654 /// This is expected to be called from within a given analysis result's \c
655 /// invalidate method to trigger a depth-first walk of all inter-analysis
656 /// dependencies. The same \p IR unit and \p PA passed to that result's \c
657 /// invalidate method should in turn be provided to this routine.
659 /// The first time this is called for a given analysis pass, it will call
660 /// the corresponding result's \c invalidate method. Subsequent calls will
661 /// use a cache of the results of that initial call. It is an error to form
662 /// cyclic dependencies between analysis results.
664 /// This returns true if the given analysis's result is invalid. Any
665 /// dependecies on it will become invalid as a result.
666 template <typename PassT
>
667 bool invalidate(IRUnitT
&IR
, const PreservedAnalyses
&PA
) {
669 detail::AnalysisResultModel
<IRUnitT
, PassT
, typename
PassT::Result
,
670 PreservedAnalyses
, Invalidator
>;
672 return invalidateImpl
<ResultModelT
>(PassT::ID(), IR
, PA
);
675 /// A type-erased variant of the above invalidate method with the same core
676 /// API other than passing an analysis ID rather than an analysis type
679 /// This is sadly less efficient than the above routine, which leverages
680 /// the type parameter to avoid the type erasure overhead.
681 bool invalidate(AnalysisKey
*ID
, IRUnitT
&IR
, const PreservedAnalyses
&PA
) {
682 return invalidateImpl
<>(ID
, IR
, PA
);
686 friend class AnalysisManager
;
688 template <typename ResultT
= ResultConceptT
>
689 bool invalidateImpl(AnalysisKey
*ID
, IRUnitT
&IR
,
690 const PreservedAnalyses
&PA
) {
691 // If we've already visited this pass, return true if it was invalidated
692 // and false otherwise.
693 auto IMapI
= IsResultInvalidated
.find(ID
);
694 if (IMapI
!= IsResultInvalidated
.end())
695 return IMapI
->second
;
697 // Otherwise look up the result object.
698 auto RI
= Results
.find({ID
, &IR
});
699 assert(RI
!= Results
.end() &&
700 "Trying to invalidate a dependent result that isn't in the "
701 "manager's cache is always an error, likely due to a stale result "
704 auto &Result
= static_cast<ResultT
&>(*RI
->second
->second
);
706 // Insert into the map whether the result should be invalidated and return
707 // that. Note that we cannot reuse IMapI and must do a fresh insert here,
708 // as calling invalidate could (recursively) insert things into the map,
709 // making any iterator or reference invalid.
711 std::tie(IMapI
, Inserted
) =
712 IsResultInvalidated
.insert({ID
, Result
.invalidate(IR
, PA
, *this)});
714 assert(Inserted
&& "Should not have already inserted this ID, likely "
715 "indicates a dependency cycle!");
716 return IMapI
->second
;
719 Invalidator(SmallDenseMap
<AnalysisKey
*, bool, 8> &IsResultInvalidated
,
720 const AnalysisResultMapT
&Results
)
721 : IsResultInvalidated(IsResultInvalidated
), Results(Results
) {}
723 SmallDenseMap
<AnalysisKey
*, bool, 8> &IsResultInvalidated
;
724 const AnalysisResultMapT
&Results
;
727 /// Construct an empty analysis manager.
729 /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs().
730 AnalysisManager(bool DebugLogging
= false) : DebugLogging(DebugLogging
) {}
731 AnalysisManager(AnalysisManager
&&) = default;
732 AnalysisManager
&operator=(AnalysisManager
&&) = default;
734 /// Returns true if the analysis manager has an empty results cache.
736 assert(AnalysisResults
.empty() == AnalysisResultLists
.empty() &&
737 "The storage and index of analysis results disagree on how many "
739 return AnalysisResults
.empty();
742 /// Clear any cached analysis results for a single unit of IR.
744 /// This doesn't invalidate, but instead simply deletes, the relevant results.
745 /// It is useful when the IR is being removed and we want to clear out all the
746 /// memory pinned for it.
747 void clear(IRUnitT
&IR
, llvm::StringRef Name
) {
749 dbgs() << "Clearing all analysis results for: " << Name
<< "\n";
751 auto ResultsListI
= AnalysisResultLists
.find(&IR
);
752 if (ResultsListI
== AnalysisResultLists
.end())
754 // Delete the map entries that point into the results list.
755 for (auto &IDAndResult
: ResultsListI
->second
)
756 AnalysisResults
.erase({IDAndResult
.first
, &IR
});
758 // And actually destroy and erase the results associated with this IR.
759 AnalysisResultLists
.erase(ResultsListI
);
762 /// Clear all analysis results cached by this AnalysisManager.
764 /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply
765 /// deletes them. This lets you clean up the AnalysisManager when the set of
766 /// IR units itself has potentially changed, and thus we can't even look up a
767 /// a result and invalidate/clear it directly.
769 AnalysisResults
.clear();
770 AnalysisResultLists
.clear();
773 /// Get the result of an analysis pass for a given IR unit.
775 /// Runs the analysis if a cached result is not available.
776 template <typename PassT
>
777 typename
PassT::Result
&getResult(IRUnitT
&IR
, ExtraArgTs
... ExtraArgs
) {
778 assert(AnalysisPasses
.count(PassT::ID()) &&
779 "This analysis pass was not registered prior to being queried");
780 ResultConceptT
&ResultConcept
=
781 getResultImpl(PassT::ID(), IR
, ExtraArgs
...);
784 detail::AnalysisResultModel
<IRUnitT
, PassT
, typename
PassT::Result
,
785 PreservedAnalyses
, Invalidator
>;
787 return static_cast<ResultModelT
&>(ResultConcept
).Result
;
790 /// Get the cached result of an analysis pass for a given IR unit.
792 /// This method never runs the analysis.
794 /// \returns null if there is no cached result.
795 template <typename PassT
>
796 typename
PassT::Result
*getCachedResult(IRUnitT
&IR
) const {
797 assert(AnalysisPasses
.count(PassT::ID()) &&
798 "This analysis pass was not registered prior to being queried");
800 ResultConceptT
*ResultConcept
= getCachedResultImpl(PassT::ID(), IR
);
805 detail::AnalysisResultModel
<IRUnitT
, PassT
, typename
PassT::Result
,
806 PreservedAnalyses
, Invalidator
>;
808 return &static_cast<ResultModelT
*>(ResultConcept
)->Result
;
811 /// Register an analysis pass with the manager.
813 /// The parameter is a callable whose result is an analysis pass. This allows
814 /// passing in a lambda to construct the analysis.
816 /// The analysis type to register is the type returned by calling the \c
817 /// PassBuilder argument. If that type has already been registered, then the
818 /// argument will not be called and this function will return false.
819 /// Otherwise, we register the analysis returned by calling \c PassBuilder(),
820 /// and this function returns true.
822 /// (Note: Although the return value of this function indicates whether or not
823 /// an analysis was previously registered, there intentionally isn't a way to
824 /// query this directly. Instead, you should just register all the analyses
825 /// you might want and let this class run them lazily. This idiom lets us
826 /// minimize the number of times we have to look up analyses in our
828 template <typename PassBuilderT
>
829 bool registerPass(PassBuilderT
&&PassBuilder
) {
830 using PassT
= decltype(PassBuilder());
832 detail::AnalysisPassModel
<IRUnitT
, PassT
, PreservedAnalyses
,
833 Invalidator
, ExtraArgTs
...>;
835 auto &PassPtr
= AnalysisPasses
[PassT::ID()];
837 // Already registered this pass type!
840 // Construct a new model around the instance returned by the builder.
841 PassPtr
.reset(new PassModelT(PassBuilder()));
845 /// Invalidate a specific analysis pass for an IR module.
847 /// Note that the analysis result can disregard invalidation, if it determines
848 /// it is in fact still valid.
849 template <typename PassT
> void invalidate(IRUnitT
&IR
) {
850 assert(AnalysisPasses
.count(PassT::ID()) &&
851 "This analysis pass was not registered prior to being invalidated");
852 invalidateImpl(PassT::ID(), IR
);
855 /// Invalidate cached analyses for an IR unit.
857 /// Walk through all of the analyses pertaining to this unit of IR and
858 /// invalidate them, unless they are preserved by the PreservedAnalyses set.
859 void invalidate(IRUnitT
&IR
, const PreservedAnalyses
&PA
) {
860 // We're done if all analyses on this IR unit are preserved.
861 if (PA
.allAnalysesInSetPreserved
<AllAnalysesOn
<IRUnitT
>>())
865 dbgs() << "Invalidating all non-preserved analyses for: " << IR
.getName()
868 // Track whether each analysis's result is invalidated in
869 // IsResultInvalidated.
870 SmallDenseMap
<AnalysisKey
*, bool, 8> IsResultInvalidated
;
871 Invalidator
Inv(IsResultInvalidated
, AnalysisResults
);
872 AnalysisResultListT
&ResultsList
= AnalysisResultLists
[&IR
];
873 for (auto &AnalysisResultPair
: ResultsList
) {
874 // This is basically the same thing as Invalidator::invalidate, but we
875 // can't call it here because we're operating on the type-erased result.
876 // Moreover if we instead called invalidate() directly, it would do an
877 // unnecessary look up in ResultsList.
878 AnalysisKey
*ID
= AnalysisResultPair
.first
;
879 auto &Result
= *AnalysisResultPair
.second
;
881 auto IMapI
= IsResultInvalidated
.find(ID
);
882 if (IMapI
!= IsResultInvalidated
.end())
883 // This result was already handled via the Invalidator.
886 // Try to invalidate the result, giving it the Invalidator so it can
887 // recursively query for any dependencies it has and record the result.
888 // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as
889 // Result.invalidate may insert things into the map, invalidating our
892 IsResultInvalidated
.insert({ID
, Result
.invalidate(IR
, PA
, Inv
)})
895 assert(Inserted
&& "Should never have already inserted this ID, likely "
896 "indicates a cycle!");
899 // Now erase the results that were marked above as invalidated.
900 if (!IsResultInvalidated
.empty()) {
901 for (auto I
= ResultsList
.begin(), E
= ResultsList
.end(); I
!= E
;) {
902 AnalysisKey
*ID
= I
->first
;
903 if (!IsResultInvalidated
.lookup(ID
)) {
909 dbgs() << "Invalidating analysis: " << this->lookUpPass(ID
).name()
910 << " on " << IR
.getName() << "\n";
912 I
= ResultsList
.erase(I
);
913 AnalysisResults
.erase({ID
, &IR
});
917 if (ResultsList
.empty())
918 AnalysisResultLists
.erase(&IR
);
922 /// Look up a registered analysis pass.
923 PassConceptT
&lookUpPass(AnalysisKey
*ID
) {
924 typename
AnalysisPassMapT::iterator PI
= AnalysisPasses
.find(ID
);
925 assert(PI
!= AnalysisPasses
.end() &&
926 "Analysis passes must be registered prior to being queried!");
930 /// Look up a registered analysis pass.
931 const PassConceptT
&lookUpPass(AnalysisKey
*ID
) const {
932 typename
AnalysisPassMapT::const_iterator PI
= AnalysisPasses
.find(ID
);
933 assert(PI
!= AnalysisPasses
.end() &&
934 "Analysis passes must be registered prior to being queried!");
938 /// Get an analysis result, running the pass if necessary.
939 ResultConceptT
&getResultImpl(AnalysisKey
*ID
, IRUnitT
&IR
,
940 ExtraArgTs
... ExtraArgs
) {
941 typename
AnalysisResultMapT::iterator RI
;
943 std::tie(RI
, Inserted
) = AnalysisResults
.insert(std::make_pair(
944 std::make_pair(ID
, &IR
), typename
AnalysisResultListT::iterator()));
946 // If we don't have a cached result for this function, look up the pass and
947 // run it to produce a result, which we then add to the cache.
949 auto &P
= this->lookUpPass(ID
);
951 dbgs() << "Running analysis: " << P
.name() << " on " << IR
.getName()
954 PassInstrumentation PI
;
955 if (ID
!= PassInstrumentationAnalysis::ID()) {
956 PI
= getResult
<PassInstrumentationAnalysis
>(IR
, ExtraArgs
...);
957 PI
.runBeforeAnalysis(P
, IR
);
960 AnalysisResultListT
&ResultList
= AnalysisResultLists
[&IR
];
961 ResultList
.emplace_back(ID
, P
.run(IR
, *this, ExtraArgs
...));
963 PI
.runAfterAnalysis(P
, IR
);
965 // P.run may have inserted elements into AnalysisResults and invalidated
967 RI
= AnalysisResults
.find({ID
, &IR
});
968 assert(RI
!= AnalysisResults
.end() && "we just inserted it!");
970 RI
->second
= std::prev(ResultList
.end());
973 return *RI
->second
->second
;
976 /// Get a cached analysis result or return null.
977 ResultConceptT
*getCachedResultImpl(AnalysisKey
*ID
, IRUnitT
&IR
) const {
978 typename
AnalysisResultMapT::const_iterator RI
=
979 AnalysisResults
.find({ID
, &IR
});
980 return RI
== AnalysisResults
.end() ? nullptr : &*RI
->second
->second
;
983 /// Invalidate a function pass result.
984 void invalidateImpl(AnalysisKey
*ID
, IRUnitT
&IR
) {
985 typename
AnalysisResultMapT::iterator RI
=
986 AnalysisResults
.find({ID
, &IR
});
987 if (RI
== AnalysisResults
.end())
991 dbgs() << "Invalidating analysis: " << this->lookUpPass(ID
).name()
992 << " on " << IR
.getName() << "\n";
993 AnalysisResultLists
[&IR
].erase(RI
->second
);
994 AnalysisResults
.erase(RI
);
997 /// Map type from module analysis pass ID to pass concept pointer.
998 using AnalysisPassMapT
=
999 DenseMap
<AnalysisKey
*, std::unique_ptr
<PassConceptT
>>;
1001 /// Collection of module analysis passes, indexed by ID.
1002 AnalysisPassMapT AnalysisPasses
;
1004 /// Map from function to a list of function analysis results.
1006 /// Provides linear time removal of all analysis results for a function and
1007 /// the ultimate storage for a particular cached analysis result.
1008 AnalysisResultListMapT AnalysisResultLists
;
1010 /// Map from an analysis ID and function to a particular cached
1011 /// analysis result.
1012 AnalysisResultMapT AnalysisResults
;
1014 /// Indicates whether we log to \c llvm::dbgs().
1018 extern template class AnalysisManager
<Module
>;
1020 /// Convenience typedef for the Module analysis manager.
1021 using ModuleAnalysisManager
= AnalysisManager
<Module
>;
1023 extern template class AnalysisManager
<Function
>;
1025 /// Convenience typedef for the Function analysis manager.
1026 using FunctionAnalysisManager
= AnalysisManager
<Function
>;
1028 /// An analysis over an "outer" IR unit that provides access to an
1029 /// analysis manager over an "inner" IR unit. The inner unit must be contained
1030 /// in the outer unit.
1032 /// For example, InnerAnalysisManagerProxy<FunctionAnalysisManager, Module> is
1033 /// an analysis over Modules (the "outer" unit) that provides access to a
1034 /// Function analysis manager. The FunctionAnalysisManager is the "inner"
1035 /// manager being proxied, and Functions are the "inner" unit. The inner/outer
1036 /// relationship is valid because each Function is contained in one Module.
1038 /// If you're (transitively) within a pass manager for an IR unit U that
1039 /// contains IR unit V, you should never use an analysis manager over V, except
1040 /// via one of these proxies.
1042 /// Note that the proxy's result is a move-only RAII object. The validity of
1043 /// the analyses in the inner analysis manager is tied to its lifetime.
1044 template <typename AnalysisManagerT
, typename IRUnitT
, typename
... ExtraArgTs
>
1045 class InnerAnalysisManagerProxy
1046 : public AnalysisInfoMixin
<
1047 InnerAnalysisManagerProxy
<AnalysisManagerT
, IRUnitT
>> {
1051 explicit Result(AnalysisManagerT
&InnerAM
) : InnerAM(&InnerAM
) {}
1053 Result(Result
&&Arg
) : InnerAM(std::move(Arg
.InnerAM
)) {
1054 // We have to null out the analysis manager in the moved-from state
1055 // because we are taking ownership of the responsibilty to clear the
1057 Arg
.InnerAM
= nullptr;
1061 // InnerAM is cleared in a moved from state where there is nothing to do.
1065 // Clear out the analysis manager if we're being destroyed -- it means we
1066 // didn't even see an invalidate call when we got invalidated.
1070 Result
&operator=(Result
&&RHS
) {
1071 InnerAM
= RHS
.InnerAM
;
1072 // We have to null out the analysis manager in the moved-from state
1073 // because we are taking ownership of the responsibilty to clear the
1075 RHS
.InnerAM
= nullptr;
1079 /// Accessor for the analysis manager.
1080 AnalysisManagerT
&getManager() { return *InnerAM
; }
1082 /// Handler for invalidation of the outer IR unit, \c IRUnitT.
1084 /// If the proxy analysis itself is not preserved, we assume that the set of
1085 /// inner IR objects contained in IRUnit may have changed. In this case,
1086 /// we have to call \c clear() on the inner analysis manager, as it may now
1087 /// have stale pointers to its inner IR objects.
1089 /// Regardless of whether the proxy analysis is marked as preserved, all of
1090 /// the analyses in the inner analysis manager are potentially invalidated
1091 /// based on the set of preserved analyses.
1093 IRUnitT
&IR
, const PreservedAnalyses
&PA
,
1094 typename AnalysisManager
<IRUnitT
, ExtraArgTs
...>::Invalidator
&Inv
);
1097 AnalysisManagerT
*InnerAM
;
1100 explicit InnerAnalysisManagerProxy(AnalysisManagerT
&InnerAM
)
1101 : InnerAM(&InnerAM
) {}
1103 /// Run the analysis pass and create our proxy result object.
1105 /// This doesn't do any interesting work; it is primarily used to insert our
1106 /// proxy result object into the outer analysis cache so that we can proxy
1107 /// invalidation to the inner analysis manager.
1108 Result
run(IRUnitT
&IR
, AnalysisManager
<IRUnitT
, ExtraArgTs
...> &AM
,
1110 return Result(*InnerAM
);
1114 friend AnalysisInfoMixin
<
1115 InnerAnalysisManagerProxy
<AnalysisManagerT
, IRUnitT
>>;
1117 static AnalysisKey Key
;
1119 AnalysisManagerT
*InnerAM
;
1122 template <typename AnalysisManagerT
, typename IRUnitT
, typename
... ExtraArgTs
>
1124 InnerAnalysisManagerProxy
<AnalysisManagerT
, IRUnitT
, ExtraArgTs
...>::Key
;
1126 /// Provide the \c FunctionAnalysisManager to \c Module proxy.
1127 using FunctionAnalysisManagerModuleProxy
=
1128 InnerAnalysisManagerProxy
<FunctionAnalysisManager
, Module
>;
1130 /// Specialization of the invalidate method for the \c
1131 /// FunctionAnalysisManagerModuleProxy's result.
1133 bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
1134 Module
&M
, const PreservedAnalyses
&PA
,
1135 ModuleAnalysisManager::Invalidator
&Inv
);
1137 // Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern
1139 extern template class InnerAnalysisManagerProxy
<FunctionAnalysisManager
,
1142 /// An analysis over an "inner" IR unit that provides access to an
1143 /// analysis manager over a "outer" IR unit. The inner unit must be contained
1144 /// in the outer unit.
1146 /// For example OuterAnalysisManagerProxy<ModuleAnalysisManager, Function> is an
1147 /// analysis over Functions (the "inner" unit) which provides access to a Module
1148 /// analysis manager. The ModuleAnalysisManager is the "outer" manager being
1149 /// proxied, and Modules are the "outer" IR unit. The inner/outer relationship
1150 /// is valid because each Function is contained in one Module.
1152 /// This proxy only exposes the const interface of the outer analysis manager,
1153 /// to indicate that you cannot cause an outer analysis to run from within an
1154 /// inner pass. Instead, you must rely on the \c getCachedResult API.
1156 /// This proxy doesn't manage invalidation in any way -- that is handled by the
1157 /// recursive return path of each layer of the pass manager. A consequence of
1158 /// this is the outer analyses may be stale. We invalidate the outer analyses
1159 /// only when we're done running passes over the inner IR units.
1160 template <typename AnalysisManagerT
, typename IRUnitT
, typename
... ExtraArgTs
>
1161 class OuterAnalysisManagerProxy
1162 : public AnalysisInfoMixin
<
1163 OuterAnalysisManagerProxy
<AnalysisManagerT
, IRUnitT
, ExtraArgTs
...>> {
1165 /// Result proxy object for \c OuterAnalysisManagerProxy.
1168 explicit Result(const AnalysisManagerT
&AM
) : AM(&AM
) {}
1170 const AnalysisManagerT
&getManager() const { return *AM
; }
1172 /// When invalidation occurs, remove any registered invalidation events.
1174 IRUnitT
&IRUnit
, const PreservedAnalyses
&PA
,
1175 typename AnalysisManager
<IRUnitT
, ExtraArgTs
...>::Invalidator
&Inv
) {
1176 // Loop over the set of registered outer invalidation mappings and if any
1177 // of them map to an analysis that is now invalid, clear it out.
1178 SmallVector
<AnalysisKey
*, 4> DeadKeys
;
1179 for (auto &KeyValuePair
: OuterAnalysisInvalidationMap
) {
1180 AnalysisKey
*OuterID
= KeyValuePair
.first
;
1181 auto &InnerIDs
= KeyValuePair
.second
;
1182 InnerIDs
.erase(llvm::remove_if(InnerIDs
, [&](AnalysisKey
*InnerID
) {
1183 return Inv
.invalidate(InnerID
, IRUnit
, PA
); }),
1185 if (InnerIDs
.empty())
1186 DeadKeys
.push_back(OuterID
);
1189 for (auto OuterID
: DeadKeys
)
1190 OuterAnalysisInvalidationMap
.erase(OuterID
);
1192 // The proxy itself remains valid regardless of anything else.
1196 /// Register a deferred invalidation event for when the outer analysis
1197 /// manager processes its invalidations.
1198 template <typename OuterAnalysisT
, typename InvalidatedAnalysisT
>
1199 void registerOuterAnalysisInvalidation() {
1200 AnalysisKey
*OuterID
= OuterAnalysisT::ID();
1201 AnalysisKey
*InvalidatedID
= InvalidatedAnalysisT::ID();
1203 auto &InvalidatedIDList
= OuterAnalysisInvalidationMap
[OuterID
];
1204 // Note, this is a linear scan. If we end up with large numbers of
1205 // analyses that all trigger invalidation on the same outer analysis,
1206 // this entire system should be changed to some other deterministic
1207 // data structure such as a `SetVector` of a pair of pointers.
1208 auto InvalidatedIt
= std::find(InvalidatedIDList
.begin(),
1209 InvalidatedIDList
.end(), InvalidatedID
);
1210 if (InvalidatedIt
== InvalidatedIDList
.end())
1211 InvalidatedIDList
.push_back(InvalidatedID
);
1214 /// Access the map from outer analyses to deferred invalidation requiring
1216 const SmallDenseMap
<AnalysisKey
*, TinyPtrVector
<AnalysisKey
*>, 2> &
1217 getOuterInvalidations() const {
1218 return OuterAnalysisInvalidationMap
;
1222 const AnalysisManagerT
*AM
;
1224 /// A map from an outer analysis ID to the set of this IR-unit's analyses
1225 /// which need to be invalidated.
1226 SmallDenseMap
<AnalysisKey
*, TinyPtrVector
<AnalysisKey
*>, 2>
1227 OuterAnalysisInvalidationMap
;
1230 OuterAnalysisManagerProxy(const AnalysisManagerT
&AM
) : AM(&AM
) {}
1232 /// Run the analysis pass and create our proxy result object.
1233 /// Nothing to see here, it just forwards the \c AM reference into the
1235 Result
run(IRUnitT
&, AnalysisManager
<IRUnitT
, ExtraArgTs
...> &,
1241 friend AnalysisInfoMixin
<
1242 OuterAnalysisManagerProxy
<AnalysisManagerT
, IRUnitT
, ExtraArgTs
...>>;
1244 static AnalysisKey Key
;
1246 const AnalysisManagerT
*AM
;
1249 template <typename AnalysisManagerT
, typename IRUnitT
, typename
... ExtraArgTs
>
1251 OuterAnalysisManagerProxy
<AnalysisManagerT
, IRUnitT
, ExtraArgTs
...>::Key
;
1253 extern template class OuterAnalysisManagerProxy
<ModuleAnalysisManager
,
1255 /// Provide the \c ModuleAnalysisManager to \c Function proxy.
1256 using ModuleAnalysisManagerFunctionProxy
=
1257 OuterAnalysisManagerProxy
<ModuleAnalysisManager
, Function
>;
1259 /// Trivial adaptor that maps from a module to its functions.
1261 /// Designed to allow composition of a FunctionPass(Manager) and
1262 /// a ModulePassManager, by running the FunctionPass(Manager) over every
1263 /// function in the module.
1265 /// Function passes run within this adaptor can rely on having exclusive access
1266 /// to the function they are run over. They should not read or modify any other
1267 /// functions! Other threads or systems may be manipulating other functions in
1268 /// the module, and so their state should never be relied on.
1269 /// FIXME: Make the above true for all of LLVM's actual passes, some still
1270 /// violate this principle.
1272 /// Function passes can also read the module containing the function, but they
1273 /// should not modify that module outside of the use lists of various globals.
1274 /// For example, a function pass is not permitted to add functions to the
1276 /// FIXME: Make the above true for all of LLVM's actual passes, some still
1277 /// violate this principle.
1279 /// Note that although function passes can access module analyses, module
1280 /// analyses are not invalidated while the function passes are running, so they
1281 /// may be stale. Function analyses will not be stale.
1282 template <typename FunctionPassT
>
1283 class ModuleToFunctionPassAdaptor
1284 : public PassInfoMixin
<ModuleToFunctionPassAdaptor
<FunctionPassT
>> {
1286 explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass
)
1287 : Pass(std::move(Pass
)) {}
1289 /// Runs the function pass across every function in the module.
1290 PreservedAnalyses
run(Module
&M
, ModuleAnalysisManager
&AM
) {
1291 FunctionAnalysisManager
&FAM
=
1292 AM
.getResult
<FunctionAnalysisManagerModuleProxy
>(M
).getManager();
1294 // Request PassInstrumentation from analysis manager, will use it to run
1295 // instrumenting callbacks for the passes later.
1296 PassInstrumentation PI
= AM
.getResult
<PassInstrumentationAnalysis
>(M
);
1298 PreservedAnalyses PA
= PreservedAnalyses::all();
1299 for (Function
&F
: M
) {
1300 if (F
.isDeclaration())
1303 // Check the PassInstrumentation's BeforePass callbacks before running the
1304 // pass, skip its execution completely if asked to (callback returns
1306 if (!PI
.runBeforePass
<Function
>(Pass
, F
))
1308 PreservedAnalyses PassPA
= Pass
.run(F
, FAM
);
1310 PI
.runAfterPass(Pass
, F
);
1312 // We know that the function pass couldn't have invalidated any other
1313 // function's analyses (that's the contract of a function pass), so
1314 // directly handle the function analysis manager's invalidation here.
1315 FAM
.invalidate(F
, PassPA
);
1317 // Then intersect the preserved set so that invalidation of module
1318 // analyses will eventually occur when the module pass completes.
1319 PA
.intersect(std::move(PassPA
));
1322 // The FunctionAnalysisManagerModuleProxy is preserved because (we assume)
1323 // the function passes we ran didn't add or remove any functions.
1325 // We also preserve all analyses on Functions, because we did all the
1326 // invalidation we needed to do above.
1327 PA
.preserveSet
<AllAnalysesOn
<Function
>>();
1328 PA
.preserve
<FunctionAnalysisManagerModuleProxy
>();
1336 /// A function to deduce a function pass type and wrap it in the
1337 /// templated adaptor.
1338 template <typename FunctionPassT
>
1339 ModuleToFunctionPassAdaptor
<FunctionPassT
>
1340 createModuleToFunctionPassAdaptor(FunctionPassT Pass
) {
1341 return ModuleToFunctionPassAdaptor
<FunctionPassT
>(std::move(Pass
));
1344 /// A utility pass template to force an analysis result to be available.
1346 /// If there are extra arguments at the pass's run level there may also be
1347 /// extra arguments to the analysis manager's \c getResult routine. We can't
1348 /// guess how to effectively map the arguments from one to the other, and so
1349 /// this specialization just ignores them.
1351 /// Specific patterns of run-method extra arguments and analysis manager extra
1352 /// arguments will have to be defined as appropriate specializations.
1353 template <typename AnalysisT
, typename IRUnitT
,
1354 typename AnalysisManagerT
= AnalysisManager
<IRUnitT
>,
1355 typename
... ExtraArgTs
>
1356 struct RequireAnalysisPass
1357 : PassInfoMixin
<RequireAnalysisPass
<AnalysisT
, IRUnitT
, AnalysisManagerT
,
1359 /// Run this pass over some unit of IR.
1361 /// This pass can be run over any unit of IR and use any analysis manager
1362 /// provided they satisfy the basic API requirements. When this pass is
1363 /// created, these methods can be instantiated to satisfy whatever the
1364 /// context requires.
1365 PreservedAnalyses
run(IRUnitT
&Arg
, AnalysisManagerT
&AM
,
1366 ExtraArgTs
&&... Args
) {
1367 (void)AM
.template getResult
<AnalysisT
>(Arg
,
1368 std::forward
<ExtraArgTs
>(Args
)...);
1370 return PreservedAnalyses::all();
1374 /// A no-op pass template which simply forces a specific analysis result
1375 /// to be invalidated.
1376 template <typename AnalysisT
>
1377 struct InvalidateAnalysisPass
1378 : PassInfoMixin
<InvalidateAnalysisPass
<AnalysisT
>> {
1379 /// Run this pass over some unit of IR.
1381 /// This pass can be run over any unit of IR and use any analysis manager,
1382 /// provided they satisfy the basic API requirements. When this pass is
1383 /// created, these methods can be instantiated to satisfy whatever the
1384 /// context requires.
1385 template <typename IRUnitT
, typename AnalysisManagerT
, typename
... ExtraArgTs
>
1386 PreservedAnalyses
run(IRUnitT
&Arg
, AnalysisManagerT
&AM
, ExtraArgTs
&&...) {
1387 auto PA
= PreservedAnalyses::all();
1388 PA
.abandon
<AnalysisT
>();
1393 /// A utility pass that does nothing, but preserves no analyses.
1395 /// Because this preserves no analyses, any analysis passes queried after this
1396 /// pass runs will recompute fresh results.
1397 struct InvalidateAllAnalysesPass
: PassInfoMixin
<InvalidateAllAnalysesPass
> {
1398 /// Run this pass over some unit of IR.
1399 template <typename IRUnitT
, typename AnalysisManagerT
, typename
... ExtraArgTs
>
1400 PreservedAnalyses
run(IRUnitT
&, AnalysisManagerT
&, ExtraArgTs
&&...) {
1401 return PreservedAnalyses::none();
1405 /// A utility pass template that simply runs another pass multiple times.
1407 /// This can be useful when debugging or testing passes. It also serves as an
1408 /// example of how to extend the pass manager in ways beyond composition.
1409 template <typename PassT
>
1410 class RepeatedPass
: public PassInfoMixin
<RepeatedPass
<PassT
>> {
1412 RepeatedPass(int Count
, PassT P
) : Count(Count
), P(std::move(P
)) {}
1414 template <typename IRUnitT
, typename AnalysisManagerT
, typename
... Ts
>
1415 PreservedAnalyses
run(IRUnitT
&IR
, AnalysisManagerT
&AM
, Ts
&&... Args
) {
1417 // Request PassInstrumentation from analysis manager, will use it to run
1418 // instrumenting callbacks for the passes later.
1419 // Here we use std::tuple wrapper over getResult which helps to extract
1420 // AnalysisManager's arguments out of the whole Args set.
1421 PassInstrumentation PI
=
1422 detail::getAnalysisResult
<PassInstrumentationAnalysis
>(
1423 AM
, IR
, std::tuple
<Ts
...>(Args
...));
1425 auto PA
= PreservedAnalyses::all();
1426 for (int i
= 0; i
< Count
; ++i
) {
1427 // Check the PassInstrumentation's BeforePass callbacks before running the
1428 // pass, skip its execution completely if asked to (callback returns
1430 if (!PI
.runBeforePass
<IRUnitT
>(P
, IR
))
1432 PA
.intersect(P
.run(IR
, AM
, std::forward
<Ts
>(Args
)...));
1433 PI
.runAfterPass(P
, IR
);
1443 template <typename PassT
>
1444 RepeatedPass
<PassT
> createRepeatedPass(int Count
, PassT P
) {
1445 return RepeatedPass
<PassT
>(Count
, std::move(P
));
1448 } // end namespace llvm
1450 #endif // LLVM_IR_PASSMANAGER_H