LLVM 18.0.0git
PassManager.h
Go to the documentation of this file.
1//===- PassManager.h - Pass management infrastructure -----------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8/// \file
9///
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.
19///
20/// The core IR library provides managers for running passes over
21/// modules and functions.
22///
23/// * FunctionPassManager can run over a Module, runs each pass over
24/// a Function.
25/// * ModulePassManager must be directly run, runs each pass over the Module.
26///
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
34///
35//===----------------------------------------------------------------------===//
36
37#ifndef LLVM_IR_PASSMANAGER_H
38#define LLVM_IR_PASSMANAGER_H
39
40#include "llvm/ADT/DenseMap.h"
41#include "llvm/ADT/STLExtras.h"
43#include "llvm/ADT/StringRef.h"
45#include "llvm/IR/Function.h"
46#include "llvm/IR/Module.h"
52#include <cassert>
53#include <cstring>
54#include <iterator>
55#include <list>
56#include <memory>
57#include <tuple>
58#include <type_traits>
59#include <utility>
60#include <vector>
61
63
64namespace llvm {
65
66// RemoveDIs: Provide facilities for converting debug-info from one form to
67// another, which are no-ops for everything but modules.
68template <class IRUnitT> inline bool shouldConvertDbgInfo(IRUnitT &IR) {
69 return false;
70}
71template <> inline bool shouldConvertDbgInfo(Module &IR) {
72 return !IR.IsNewDbgInfoFormat && UseNewDbgInfoFormat;
73}
74template <class IRUnitT> inline void doConvertDbgInfoToNew(IRUnitT &IR) {}
75template <> inline void doConvertDbgInfoToNew(Module &IR) {
76 IR.convertToNewDbgValues();
77}
78template <class IRUnitT> inline void doConvertDebugInfoToOld(IRUnitT &IR) {}
79template <> inline void doConvertDebugInfoToOld(Module &IR) {
80 IR.convertFromNewDbgValues();
81}
82
83/// A special type used by analysis passes to provide an address that
84/// identifies that particular analysis pass type.
85///
86/// Analysis passes should have a static data member of this type and derive
87/// from the \c AnalysisInfoMixin to get a static ID method used to identify
88/// the analysis in the pass management infrastructure.
89struct alignas(8) AnalysisKey {};
90
91/// A special type used to provide an address that identifies a set of related
92/// analyses. These sets are primarily used below to mark sets of analyses as
93/// preserved.
94///
95/// For example, a transformation can indicate that it preserves the CFG of a
96/// function by preserving the appropriate AnalysisSetKey. An analysis that
97/// depends only on the CFG can then check if that AnalysisSetKey is preserved;
98/// if it is, the analysis knows that it itself is preserved.
99struct alignas(8) AnalysisSetKey {};
100
101/// This templated class represents "all analyses that operate over <a
102/// particular IR unit>" (e.g. a Function or a Module) in instances of
103/// PreservedAnalysis.
104///
105/// This lets a transformation say e.g. "I preserved all function analyses".
106///
107/// Note that you must provide an explicit instantiation declaration and
108/// definition for this template in order to get the correct behavior on
109/// Windows. Otherwise, the address of SetKey will not be stable.
110template <typename IRUnitT> class AllAnalysesOn {
111public:
112 static AnalysisSetKey *ID() { return &SetKey; }
113
114private:
115 static AnalysisSetKey SetKey;
116};
117
118template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
119
120extern template class AllAnalysesOn<Module>;
121extern template class AllAnalysesOn<Function>;
122
123/// Represents analyses that only rely on functions' control flow.
124///
125/// This can be used with \c PreservedAnalyses to mark the CFG as preserved and
126/// to query whether it has been preserved.
127///
128/// The CFG of a function is defined as the set of basic blocks and the edges
129/// between them. Changing the set of basic blocks in a function is enough to
130/// mutate the CFG. Mutating the condition of a branch or argument of an
131/// invoked function does not mutate the CFG, but changing the successor labels
132/// of those instructions does.
134public:
135 static AnalysisSetKey *ID() { return &SetKey; }
136
137private:
138 static AnalysisSetKey SetKey;
139};
140
141/// A set of analyses that are preserved following a run of a transformation
142/// pass.
143///
144/// Transformation passes build and return these objects to communicate which
145/// analyses are still valid after the transformation. For most passes this is
146/// fairly simple: if they don't change anything all analyses are preserved,
147/// otherwise only a short list of analyses that have been explicitly updated
148/// are preserved.
149///
150/// This class also lets transformation passes mark abstract *sets* of analyses
151/// as preserved. A transformation that (say) does not alter the CFG can
152/// indicate such by marking a particular AnalysisSetKey as preserved, and
153/// then analyses can query whether that AnalysisSetKey is preserved.
154///
155/// Finally, this class can represent an "abandoned" analysis, which is
156/// not preserved even if it would be covered by some abstract set of analyses.
157///
158/// Given a `PreservedAnalyses` object, an analysis will typically want to
159/// figure out whether it is preserved. In the example below, MyAnalysisType is
160/// preserved if it's not abandoned, and (a) it's explicitly marked as
161/// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both
162/// AnalysisSetA and AnalysisSetB are preserved.
163///
164/// ```
165/// auto PAC = PA.getChecker<MyAnalysisType>();
166/// if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() ||
167/// (PAC.preservedSet<AnalysisSetA>() &&
168/// PAC.preservedSet<AnalysisSetB>())) {
169/// // The analysis has been successfully preserved ...
170/// }
171/// ```
173public:
174 /// Convenience factory function for the empty preserved set.
176
177 /// Construct a special preserved set that preserves all passes.
180 PA.PreservedIDs.insert(&AllAnalysesKey);
181 return PA;
182 }
183
184 /// Construct a preserved analyses object with a single preserved set.
185 template <typename AnalysisSetT>
188 PA.preserveSet<AnalysisSetT>();
189 return PA;
190 }
191
192 /// Mark an analysis as preserved.
193 template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); }
194
195 /// Given an analysis's ID, mark the analysis as preserved, adding it
196 /// to the set.
198 // Clear this ID from the explicit not-preserved set if present.
199 NotPreservedAnalysisIDs.erase(ID);
200
201 // If we're not already preserving all analyses (other than those in
202 // NotPreservedAnalysisIDs).
203 if (!areAllPreserved())
204 PreservedIDs.insert(ID);
205 }
206
207 /// Mark an analysis set as preserved.
208 template <typename AnalysisSetT> void preserveSet() {
209 preserveSet(AnalysisSetT::ID());
210 }
211
212 /// Mark an analysis set as preserved using its ID.
214 // If we're not already in the saturated 'all' state, add this set.
215 if (!areAllPreserved())
216 PreservedIDs.insert(ID);
217 }
218
219 /// Mark an analysis as abandoned.
220 ///
221 /// An abandoned analysis is not preserved, even if it is nominally covered
222 /// by some other set or was previously explicitly marked as preserved.
223 ///
224 /// Note that you can only abandon a specific analysis, not a *set* of
225 /// analyses.
226 template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); }
227
228 /// Mark an analysis as abandoned using its ID.
229 ///
230 /// An abandoned analysis is not preserved, even if it is nominally covered
231 /// by some other set or was previously explicitly marked as preserved.
232 ///
233 /// Note that you can only abandon a specific analysis, not a *set* of
234 /// analyses.
236 PreservedIDs.erase(ID);
237 NotPreservedAnalysisIDs.insert(ID);
238 }
239
240 /// Intersect this set with another in place.
241 ///
242 /// This is a mutating operation on this preserved set, removing all
243 /// preserved passes which are not also preserved in the argument.
244 void intersect(const PreservedAnalyses &Arg) {
245 if (Arg.areAllPreserved())
246 return;
247 if (areAllPreserved()) {
248 *this = Arg;
249 return;
250 }
251 // The intersection requires the *union* of the explicitly not-preserved
252 // IDs and the *intersection* of the preserved IDs.
253 for (auto *ID : Arg.NotPreservedAnalysisIDs) {
254 PreservedIDs.erase(ID);
255 NotPreservedAnalysisIDs.insert(ID);
256 }
257 for (auto *ID : PreservedIDs)
258 if (!Arg.PreservedIDs.count(ID))
259 PreservedIDs.erase(ID);
260 }
261
262 /// Intersect this set with a temporary other set in place.
263 ///
264 /// This is a mutating operation on this preserved set, removing all
265 /// preserved passes which are not also preserved in the argument.
267 if (Arg.areAllPreserved())
268 return;
269 if (areAllPreserved()) {
270 *this = std::move(Arg);
271 return;
272 }
273 // The intersection requires the *union* of the explicitly not-preserved
274 // IDs and the *intersection* of the preserved IDs.
275 for (auto *ID : Arg.NotPreservedAnalysisIDs) {
276 PreservedIDs.erase(ID);
277 NotPreservedAnalysisIDs.insert(ID);
278 }
279 for (auto *ID : PreservedIDs)
280 if (!Arg.PreservedIDs.count(ID))
281 PreservedIDs.erase(ID);
282 }
283
284 /// A checker object that makes it easy to query for whether an analysis or
285 /// some set covering it is preserved.
287 friend class PreservedAnalyses;
288
289 const PreservedAnalyses &PA;
290 AnalysisKey *const ID;
291 const bool IsAbandoned;
292
293 /// A PreservedAnalysisChecker is tied to a particular Analysis because
294 /// `preserved()` and `preservedSet()` both return false if the Analysis
295 /// was abandoned.
297 : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(ID)) {}
298
299 public:
300 /// Returns true if the checker's analysis was not abandoned and either
301 /// - the analysis is explicitly preserved or
302 /// - all analyses are preserved.
303 bool preserved() {
304 return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||
305 PA.PreservedIDs.count(ID));
306 }
307
308 /// Return true if the checker's analysis was not abandoned, i.e. it was not
309 /// explicitly invalidated. Even if the analysis is not explicitly
310 /// preserved, if the analysis is known stateless, then it is preserved.
312 return !IsAbandoned;
313 }
314
315 /// Returns true if the checker's analysis was not abandoned and either
316 /// - \p AnalysisSetT is explicitly preserved or
317 /// - all analyses are preserved.
318 template <typename AnalysisSetT> bool preservedSet() {
319 AnalysisSetKey *SetID = AnalysisSetT::ID();
320 return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||
321 PA.PreservedIDs.count(SetID));
322 }
323 };
324
325 /// Build a checker for this `PreservedAnalyses` and the specified analysis
326 /// type.
327 ///
328 /// You can use the returned object to query whether an analysis was
329 /// preserved. See the example in the comment on `PreservedAnalysis`.
330 template <typename AnalysisT> PreservedAnalysisChecker getChecker() const {
331 return PreservedAnalysisChecker(*this, AnalysisT::ID());
332 }
333
334 /// Build a checker for this `PreservedAnalyses` and the specified analysis
335 /// ID.
336 ///
337 /// You can use the returned object to query whether an analysis was
338 /// preserved. See the example in the comment on `PreservedAnalysis`.
340 return PreservedAnalysisChecker(*this, ID);
341 }
342
343 /// Test whether all analyses are preserved (and none are abandoned).
344 ///
345 /// This is used primarily to optimize for the common case of a transformation
346 /// which makes no changes to the IR.
347 bool areAllPreserved() const {
348 return NotPreservedAnalysisIDs.empty() &&
349 PreservedIDs.count(&AllAnalysesKey);
350 }
351
352 /// Directly test whether a set of analyses is preserved.
353 ///
354 /// This is only true when no analyses have been explicitly abandoned.
355 template <typename AnalysisSetT> bool allAnalysesInSetPreserved() const {
356 return allAnalysesInSetPreserved(AnalysisSetT::ID());
357 }
358
359 /// Directly test whether a set of analyses is preserved.
360 ///
361 /// This is only true when no analyses have been explicitly abandoned.
363 return NotPreservedAnalysisIDs.empty() &&
364 (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(SetID));
365 }
366
367private:
368 /// A special key used to indicate all analyses.
369 static AnalysisSetKey AllAnalysesKey;
370
371 /// The IDs of analyses and analysis sets that are preserved.
372 SmallPtrSet<void *, 2> PreservedIDs;
373
374 /// The IDs of explicitly not-preserved analyses.
375 ///
376 /// If an analysis in this set is covered by a set in `PreservedIDs`, we
377 /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always
378 /// "wins" over analysis sets in `PreservedIDs`.
379 ///
380 /// Also, a given ID should never occur both here and in `PreservedIDs`.
381 SmallPtrSet<AnalysisKey *, 2> NotPreservedAnalysisIDs;
382};
383
384// Forward declare the analysis manager template.
385template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
386
387/// A CRTP mix-in to automatically provide informational APIs needed for
388/// passes.
389///
390/// This provides some boilerplate for types that are passes.
391template <typename DerivedT> struct PassInfoMixin {
392 /// Gets the name of the pass we are mixed into.
393 static StringRef name() {
394 static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value,
395 "Must pass the derived type as the template argument!");
396 StringRef Name = getTypeName<DerivedT>();
397 Name.consume_front("llvm::");
398 return Name;
399 }
400
402 function_ref<StringRef(StringRef)> MapClassName2PassName) {
403 StringRef ClassName = DerivedT::name();
404 auto PassName = MapClassName2PassName(ClassName);
405 OS << PassName;
406 }
407};
408
409/// A CRTP mix-in that provides informational APIs needed for analysis passes.
410///
411/// This provides some boilerplate for types that are analysis passes. It
412/// automatically mixes in \c PassInfoMixin.
413template <typename DerivedT>
415 /// Returns an opaque, unique ID for this analysis type.
416 ///
417 /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus
418 /// suitable for use in sets, maps, and other data structures that use the low
419 /// bits of pointers.
420 ///
421 /// Note that this requires the derived type provide a static \c AnalysisKey
422 /// member called \c Key.
423 ///
424 /// FIXME: The only reason the mixin type itself can't declare the Key value
425 /// is that some compilers cannot correctly unique a templated static variable
426 /// so it has the same addresses in each instantiation. The only currently
427 /// known platform with this limitation is Windows DLL builds, specifically
428 /// building each part of LLVM as a DLL. If we ever remove that build
429 /// configuration, this mixin can provide the static key as well.
430 static AnalysisKey *ID() {
431 static_assert(std::is_base_of<AnalysisInfoMixin, DerivedT>::value,
432 "Must pass the derived type as the template argument!");
433 return &DerivedT::Key;
434 }
435};
436
437namespace detail {
438
439/// Actual unpacker of extra arguments in getAnalysisResult,
440/// passes only those tuple arguments that are mentioned in index_sequence.
441template <typename PassT, typename IRUnitT, typename AnalysisManagerT,
442 typename... ArgTs, size_t... Ns>
443typename PassT::Result
444getAnalysisResultUnpackTuple(AnalysisManagerT &AM, IRUnitT &IR,
445 std::tuple<ArgTs...> Args,
446 std::index_sequence<Ns...>) {
447 (void)Args;
448 return AM.template getResult<PassT>(IR, std::get<Ns>(Args)...);
449}
450
451/// Helper for *partial* unpacking of extra arguments in getAnalysisResult.
452///
453/// Arguments passed in tuple come from PassManager, so they might have extra
454/// arguments after those AnalysisManager's ExtraArgTs ones that we need to
455/// pass to getResult.
456template <typename PassT, typename IRUnitT, typename... AnalysisArgTs,
457 typename... MainArgTs>
458typename PassT::Result
460 std::tuple<MainArgTs...> Args) {
462 PassT, IRUnitT>)(AM, IR, Args,
463 std::index_sequence_for<AnalysisArgTs...>{});
464}
465
466} // namespace detail
467
468// Forward declare the pass instrumentation analysis explicitly queried in
469// generic PassManager code.
470// FIXME: figure out a way to move PassInstrumentationAnalysis into its own
471// header.
472class PassInstrumentationAnalysis;
473
474/// Manages a sequence of passes over a particular unit of IR.
475///
476/// A pass manager contains a sequence of passes to run over a particular unit
477/// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of
478/// IR, and when run over some given IR will run each of its contained passes in
479/// sequence. Pass managers are the primary and most basic building block of a
480/// pass pipeline.
481///
482/// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT>
483/// argument. The pass manager will propagate that analysis manager to each
484/// pass it runs, and will call the analysis manager's invalidation routine with
485/// the PreservedAnalyses of each pass it runs.
486template <typename IRUnitT,
487 typename AnalysisManagerT = AnalysisManager<IRUnitT>,
488 typename... ExtraArgTs>
490 PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
491public:
492 /// Construct a pass manager.
493 explicit PassManager() = default;
494
495 // FIXME: These are equivalent to the default move constructor/move
496 // assignment. However, using = default triggers linker errors due to the
497 // explicit instantiations below. Find away to use the default and remove the
498 // duplicated code here.
500
502 Passes = std::move(RHS.Passes);
503 return *this;
504 }
505
507 function_ref<StringRef(StringRef)> MapClassName2PassName) {
508 for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
509 auto *P = Passes[Idx].get();
510 P->printPipeline(OS, MapClassName2PassName);
511 if (Idx + 1 < Size)
512 OS << ',';
513 }
514 }
515
516 /// Run all of the passes in this manager over the given unit of IR.
517 /// ExtraArgs are passed to each pass.
518 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
519 ExtraArgTs... ExtraArgs) {
521
522 // Request PassInstrumentation from analysis manager, will use it to run
523 // instrumenting callbacks for the passes later.
524 // Here we use std::tuple wrapper over getResult which helps to extract
525 // AnalysisManager's arguments out of the whole ExtraArgs set.
527 detail::getAnalysisResult<PassInstrumentationAnalysis>(
528 AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));
529
530 // RemoveDIs: if requested, convert debug-info to DPValue representation
531 // for duration of these passes.
532 bool ShouldConvertDbgInfo = shouldConvertDbgInfo(IR);
533 if (ShouldConvertDbgInfo)
535
536 for (auto &Pass : Passes) {
537 // Check the PassInstrumentation's BeforePass callbacks before running the
538 // pass, skip its execution completely if asked to (callback returns
539 // false).
540 if (!PI.runBeforePass<IRUnitT>(*Pass, IR))
541 continue;
542
543 PreservedAnalyses PassPA = Pass->run(IR, AM, ExtraArgs...);
544
545 // Update the analysis manager as each pass runs and potentially
546 // invalidates analyses.
547 AM.invalidate(IR, PassPA);
548
549 // Call onto PassInstrumentation's AfterPass callbacks immediately after
550 // running the pass.
551 PI.runAfterPass<IRUnitT>(*Pass, IR, PassPA);
552
553 // Finally, intersect the preserved analyses to compute the aggregate
554 // preserved set for this pass manager.
555 PA.intersect(std::move(PassPA));
556 }
557
558 if (ShouldConvertDbgInfo)
560
561 // Invalidation was handled after each pass in the above loop for the
562 // current unit of IR. Therefore, the remaining analysis results in the
563 // AnalysisManager are preserved. We mark this with a set so that we don't
564 // need to inspect each one individually.
566
567 return PA;
568 }
569
570 template <typename PassT>
572 std::enable_if_t<!std::is_same<PassT, PassManager>::value>
573 addPass(PassT &&Pass) {
574 using PassModelT =
575 detail::PassModel<IRUnitT, PassT, PreservedAnalyses, AnalysisManagerT,
576 ExtraArgTs...>;
577 // Do not use make_unique or emplace_back, they cause too many template
578 // instantiations, causing terrible compile times.
579 Passes.push_back(std::unique_ptr<PassConceptT>(
580 new PassModelT(std::forward<PassT>(Pass))));
581 }
582
583 /// When adding a pass manager pass that has the same type as this pass
584 /// manager, simply move the passes over. This is because we don't have use
585 /// cases rely on executing nested pass managers. Doing this could reduce
586 /// implementation complexity and avoid potential invalidation issues that may
587 /// happen with nested pass managers of the same type.
588 template <typename PassT>
590 std::enable_if_t<std::is_same<PassT, PassManager>::value>
591 addPass(PassT &&Pass) {
592 for (auto &P : Pass.Passes)
593 Passes.push_back(std::move(P));
594 }
595
596 /// Returns if the pass manager contains any passes.
597 bool isEmpty() const { return Passes.empty(); }
598
599 static bool isRequired() { return true; }
600
601protected:
603 detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
604
605 std::vector<std::unique_ptr<PassConceptT>> Passes;
606};
607
608extern template class PassManager<Module>;
609
610/// Convenience typedef for a pass manager over modules.
612
613extern template class PassManager<Function>;
614
615/// Convenience typedef for a pass manager over functions.
617
618/// Pseudo-analysis pass that exposes the \c PassInstrumentation to pass
619/// managers. Goes before AnalysisManager definition to provide its
620/// internals (e.g PassInstrumentationAnalysis::ID) for use there if needed.
621/// FIXME: figure out a way to move PassInstrumentationAnalysis into its own
622/// header.
626 static AnalysisKey Key;
627
629
630public:
631 /// PassInstrumentationCallbacks object is shared, owned by something else,
632 /// not this analysis.
634 : Callbacks(Callbacks) {}
635
637
638 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
639 Result run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {
640 return PassInstrumentation(Callbacks);
641 }
642};
643
644/// A container for analyses that lazily runs them and caches their
645/// results.
646///
647/// This class can manage analyses for any IR unit where the address of the IR
648/// unit sufficies as its identity.
649template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager {
650public:
651 class Invalidator;
652
653private:
654 // Now that we've defined our invalidator, we can define the concept types.
655 using ResultConceptT =
657 using PassConceptT =
659 ExtraArgTs...>;
660
661 /// List of analysis pass IDs and associated concept pointers.
662 ///
663 /// Requires iterators to be valid across appending new entries and arbitrary
664 /// erases. Provides the analysis ID to enable finding iterators to a given
665 /// entry in maps below, and provides the storage for the actual result
666 /// concept.
667 using AnalysisResultListT =
668 std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>;
669
670 /// Map type from IRUnitT pointer to our custom list type.
672
673 /// Map type from a pair of analysis ID and IRUnitT pointer to an
674 /// iterator into a particular result list (which is where the actual analysis
675 /// result is stored).
676 using AnalysisResultMapT =
678 typename AnalysisResultListT::iterator>;
679
680public:
681 /// API to communicate dependencies between analyses during invalidation.
682 ///
683 /// When an analysis result embeds handles to other analysis results, it
684 /// needs to be invalidated both when its own information isn't preserved and
685 /// when any of its embedded analysis results end up invalidated. We pass an
686 /// \c Invalidator object as an argument to \c invalidate() in order to let
687 /// the analysis results themselves define the dependency graph on the fly.
688 /// This lets us avoid building an explicit representation of the
689 /// dependencies between analysis results.
691 public:
692 /// Trigger the invalidation of some other analysis pass if not already
693 /// handled and return whether it was in fact invalidated.
694 ///
695 /// This is expected to be called from within a given analysis result's \c
696 /// invalidate method to trigger a depth-first walk of all inter-analysis
697 /// dependencies. The same \p IR unit and \p PA passed to that result's \c
698 /// invalidate method should in turn be provided to this routine.
699 ///
700 /// The first time this is called for a given analysis pass, it will call
701 /// the corresponding result's \c invalidate method. Subsequent calls will
702 /// use a cache of the results of that initial call. It is an error to form
703 /// cyclic dependencies between analysis results.
704 ///
705 /// This returns true if the given analysis's result is invalid. Any
706 /// dependecies on it will become invalid as a result.
707 template <typename PassT>
708 bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
709 using ResultModelT =
710 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
712
713 return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);
714 }
715
716 /// A type-erased variant of the above invalidate method with the same core
717 /// API other than passing an analysis ID rather than an analysis type
718 /// parameter.
719 ///
720 /// This is sadly less efficient than the above routine, which leverages
721 /// the type parameter to avoid the type erasure overhead.
722 bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
723 return invalidateImpl<>(ID, IR, PA);
724 }
725
726 private:
727 friend class AnalysisManager;
728
729 template <typename ResultT = ResultConceptT>
730 bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,
731 const PreservedAnalyses &PA) {
732 // If we've already visited this pass, return true if it was invalidated
733 // and false otherwise.
734 auto IMapI = IsResultInvalidated.find(ID);
735 if (IMapI != IsResultInvalidated.end())
736 return IMapI->second;
737
738 // Otherwise look up the result object.
739 auto RI = Results.find({ID, &IR});
740 assert(RI != Results.end() &&
741 "Trying to invalidate a dependent result that isn't in the "
742 "manager's cache is always an error, likely due to a stale result "
743 "handle!");
744
745 auto &Result = static_cast<ResultT &>(*RI->second->second);
746
747 // Insert into the map whether the result should be invalidated and return
748 // that. Note that we cannot reuse IMapI and must do a fresh insert here,
749 // as calling invalidate could (recursively) insert things into the map,
750 // making any iterator or reference invalid.
751 bool Inserted;
752 std::tie(IMapI, Inserted) =
753 IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});
754 (void)Inserted;
755 assert(Inserted && "Should not have already inserted this ID, likely "
756 "indicates a dependency cycle!");
757 return IMapI->second;
758 }
759
760 Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated,
761 const AnalysisResultMapT &Results)
762 : IsResultInvalidated(IsResultInvalidated), Results(Results) {}
763
764 SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;
765 const AnalysisResultMapT &Results;
766 };
767
768 /// Construct an empty analysis manager.
772
773 /// Returns true if the analysis manager has an empty results cache.
774 bool empty() const {
775 assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&
776 "The storage and index of analysis results disagree on how many "
777 "there are!");
778 return AnalysisResults.empty();
779 }
780
781 /// Clear any cached analysis results for a single unit of IR.
782 ///
783 /// This doesn't invalidate, but instead simply deletes, the relevant results.
784 /// It is useful when the IR is being removed and we want to clear out all the
785 /// memory pinned for it.
786 void clear(IRUnitT &IR, llvm::StringRef Name);
787
788 /// Clear all analysis results cached by this AnalysisManager.
789 ///
790 /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply
791 /// deletes them. This lets you clean up the AnalysisManager when the set of
792 /// IR units itself has potentially changed, and thus we can't even look up a
793 /// a result and invalidate/clear it directly.
794 void clear() {
795 AnalysisResults.clear();
796 AnalysisResultLists.clear();
797 }
798
799 /// Get the result of an analysis pass for a given IR unit.
800 ///
801 /// Runs the analysis if a cached result is not available.
802 template <typename PassT>
803 typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) {
804 assert(AnalysisPasses.count(PassT::ID()) &&
805 "This analysis pass was not registered prior to being queried");
806 ResultConceptT &ResultConcept =
807 getResultImpl(PassT::ID(), IR, ExtraArgs...);
808
809 using ResultModelT =
810 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
812
813 return static_cast<ResultModelT &>(ResultConcept).Result;
814 }
815
816 /// Get the cached result of an analysis pass for a given IR unit.
817 ///
818 /// This method never runs the analysis.
819 ///
820 /// \returns null if there is no cached result.
821 template <typename PassT>
822 typename PassT::Result *getCachedResult(IRUnitT &IR) const {
823 assert(AnalysisPasses.count(PassT::ID()) &&
824 "This analysis pass was not registered prior to being queried");
825
826 ResultConceptT *ResultConcept = getCachedResultImpl(PassT::ID(), IR);
827 if (!ResultConcept)
828 return nullptr;
829
830 using ResultModelT =
831 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
833
834 return &static_cast<ResultModelT *>(ResultConcept)->Result;
835 }
836
837 /// Verify that the given Result cannot be invalidated, assert otherwise.
838 template <typename PassT>
839 void verifyNotInvalidated(IRUnitT &IR, typename PassT::Result *Result) const {
841 SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
842 Invalidator Inv(IsResultInvalidated, AnalysisResults);
843 assert(!Result->invalidate(IR, PA, Inv) &&
844 "Cached result cannot be invalidated");
845 }
846
847 /// Register an analysis pass with the manager.
848 ///
849 /// The parameter is a callable whose result is an analysis pass. This allows
850 /// passing in a lambda to construct the analysis.
851 ///
852 /// The analysis type to register is the type returned by calling the \c
853 /// PassBuilder argument. If that type has already been registered, then the
854 /// argument will not be called and this function will return false.
855 /// Otherwise, we register the analysis returned by calling \c PassBuilder(),
856 /// and this function returns true.
857 ///
858 /// (Note: Although the return value of this function indicates whether or not
859 /// an analysis was previously registered, there intentionally isn't a way to
860 /// query this directly. Instead, you should just register all the analyses
861 /// you might want and let this class run them lazily. This idiom lets us
862 /// minimize the number of times we have to look up analyses in our
863 /// hashtable.)
864 template <typename PassBuilderT>
865 bool registerPass(PassBuilderT &&PassBuilder) {
866 using PassT = decltype(PassBuilder());
867 using PassModelT =
869 Invalidator, ExtraArgTs...>;
870
871 auto &PassPtr = AnalysisPasses[PassT::ID()];
872 if (PassPtr)
873 // Already registered this pass type!
874 return false;
875
876 // Construct a new model around the instance returned by the builder.
877 PassPtr.reset(new PassModelT(PassBuilder()));
878 return true;
879 }
880
881 /// Invalidate cached analyses for an IR unit.
882 ///
883 /// Walk through all of the analyses pertaining to this unit of IR and
884 /// invalidate them, unless they are preserved by the PreservedAnalyses set.
885 void invalidate(IRUnitT &IR, const PreservedAnalyses &PA);
886
887private:
888 /// Look up a registered analysis pass.
889 PassConceptT &lookUpPass(AnalysisKey *ID) {
890 typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(ID);
891 assert(PI != AnalysisPasses.end() &&
892 "Analysis passes must be registered prior to being queried!");
893 return *PI->second;
894 }
895
896 /// Look up a registered analysis pass.
897 const PassConceptT &lookUpPass(AnalysisKey *ID) const {
898 typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(ID);
899 assert(PI != AnalysisPasses.end() &&
900 "Analysis passes must be registered prior to being queried!");
901 return *PI->second;
902 }
903
904 /// Get an analysis result, running the pass if necessary.
905 ResultConceptT &getResultImpl(AnalysisKey *ID, IRUnitT &IR,
906 ExtraArgTs... ExtraArgs);
907
908 /// Get a cached analysis result or return null.
909 ResultConceptT *getCachedResultImpl(AnalysisKey *ID, IRUnitT &IR) const {
911 AnalysisResults.find({ID, &IR});
912 return RI == AnalysisResults.end() ? nullptr : &*RI->second->second;
913 }
914
915 /// Map type from analysis pass ID to pass concept pointer.
916 using AnalysisPassMapT =
917 DenseMap<AnalysisKey *, std::unique_ptr<PassConceptT>>;
918
919 /// Collection of analysis passes, indexed by ID.
920 AnalysisPassMapT AnalysisPasses;
921
922 /// Map from IR unit to a list of analysis results.
923 ///
924 /// Provides linear time removal of all analysis results for a IR unit and
925 /// the ultimate storage for a particular cached analysis result.
926 AnalysisResultListMapT AnalysisResultLists;
927
928 /// Map from an analysis ID and IR unit to a particular cached
929 /// analysis result.
930 AnalysisResultMapT AnalysisResults;
931};
932
933extern template class AnalysisManager<Module>;
934
935/// Convenience typedef for the Module analysis manager.
937
938extern template class AnalysisManager<Function>;
939
940/// Convenience typedef for the Function analysis manager.
942
943/// An analysis over an "outer" IR unit that provides access to an
944/// analysis manager over an "inner" IR unit. The inner unit must be contained
945/// in the outer unit.
946///
947/// For example, InnerAnalysisManagerProxy<FunctionAnalysisManager, Module> is
948/// an analysis over Modules (the "outer" unit) that provides access to a
949/// Function analysis manager. The FunctionAnalysisManager is the "inner"
950/// manager being proxied, and Functions are the "inner" unit. The inner/outer
951/// relationship is valid because each Function is contained in one Module.
952///
953/// If you're (transitively) within a pass manager for an IR unit U that
954/// contains IR unit V, you should never use an analysis manager over V, except
955/// via one of these proxies.
956///
957/// Note that the proxy's result is a move-only RAII object. The validity of
958/// the analyses in the inner analysis manager is tied to its lifetime.
959template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
961 : public AnalysisInfoMixin<
962 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> {
963public:
964 class Result {
965 public:
966 explicit Result(AnalysisManagerT &InnerAM) : InnerAM(&InnerAM) {}
967
968 Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)) {
969 // We have to null out the analysis manager in the moved-from state
970 // because we are taking ownership of the responsibilty to clear the
971 // analysis state.
972 Arg.InnerAM = nullptr;
973 }
974
976 // InnerAM is cleared in a moved from state where there is nothing to do.
977 if (!InnerAM)
978 return;
979
980 // Clear out the analysis manager if we're being destroyed -- it means we
981 // didn't even see an invalidate call when we got invalidated.
982 InnerAM->clear();
983 }
984
986 InnerAM = RHS.InnerAM;
987 // We have to null out the analysis manager in the moved-from state
988 // because we are taking ownership of the responsibilty to clear the
989 // analysis state.
990 RHS.InnerAM = nullptr;
991 return *this;
992 }
993
994 /// Accessor for the analysis manager.
995 AnalysisManagerT &getManager() { return *InnerAM; }
996
997 /// Handler for invalidation of the outer IR unit, \c IRUnitT.
998 ///
999 /// If the proxy analysis itself is not preserved, we assume that the set of
1000 /// inner IR objects contained in IRUnit may have changed. In this case,
1001 /// we have to call \c clear() on the inner analysis manager, as it may now
1002 /// have stale pointers to its inner IR objects.
1003 ///
1004 /// Regardless of whether the proxy analysis is marked as preserved, all of
1005 /// the analyses in the inner analysis manager are potentially invalidated
1006 /// based on the set of preserved analyses.
1008 IRUnitT &IR, const PreservedAnalyses &PA,
1010
1011 private:
1012 AnalysisManagerT *InnerAM;
1013 };
1014
1015 explicit InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM)
1016 : InnerAM(&InnerAM) {}
1017
1018 /// Run the analysis pass and create our proxy result object.
1019 ///
1020 /// This doesn't do any interesting work; it is primarily used to insert our
1021 /// proxy result object into the outer analysis cache so that we can proxy
1022 /// invalidation to the inner analysis manager.
1024 ExtraArgTs...) {
1025 return Result(*InnerAM);
1026 }
1027
1028private:
1029 friend AnalysisInfoMixin<
1031
1032 static AnalysisKey Key;
1033
1034 AnalysisManagerT *InnerAM;
1035};
1036
1037template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
1038AnalysisKey
1039 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
1040
1041/// Provide the \c FunctionAnalysisManager to \c Module proxy.
1044
1045/// Specialization of the invalidate method for the \c
1046/// FunctionAnalysisManagerModuleProxy's result.
1047template <>
1048bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
1049 Module &M, const PreservedAnalyses &PA,
1051
1052// Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern
1053// template.
1055 Module>;
1056
1057/// An analysis over an "inner" IR unit that provides access to an
1058/// analysis manager over a "outer" IR unit. The inner unit must be contained
1059/// in the outer unit.
1060///
1061/// For example OuterAnalysisManagerProxy<ModuleAnalysisManager, Function> is an
1062/// analysis over Functions (the "inner" unit) which provides access to a Module
1063/// analysis manager. The ModuleAnalysisManager is the "outer" manager being
1064/// proxied, and Modules are the "outer" IR unit. The inner/outer relationship
1065/// is valid because each Function is contained in one Module.
1066///
1067/// This proxy only exposes the const interface of the outer analysis manager,
1068/// to indicate that you cannot cause an outer analysis to run from within an
1069/// inner pass. Instead, you must rely on the \c getCachedResult API. This is
1070/// due to keeping potential future concurrency in mind. To give an example,
1071/// running a module analysis before any function passes may give a different
1072/// result than running it in a function pass. Both may be valid, but it would
1073/// produce non-deterministic results. GlobalsAA is a good analysis example,
1074/// because the cached information has the mod/ref info for all memory for each
1075/// function at the time the analysis was computed. The information is still
1076/// valid after a function transformation, but it may be *different* if
1077/// recomputed after that transform. GlobalsAA is never invalidated.
1078
1079///
1080/// This proxy doesn't manage invalidation in any way -- that is handled by the
1081/// recursive return path of each layer of the pass manager. A consequence of
1082/// this is the outer analyses may be stale. We invalidate the outer analyses
1083/// only when we're done running passes over the inner IR units.
1084template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
1086 : public AnalysisInfoMixin<
1087 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>> {
1088public:
1089 /// Result proxy object for \c OuterAnalysisManagerProxy.
1090 class Result {
1091 public:
1092 explicit Result(const AnalysisManagerT &OuterAM) : OuterAM(&OuterAM) {}
1093
1094 /// Get a cached analysis. If the analysis can be invalidated, this will
1095 /// assert.
1096 template <typename PassT, typename IRUnitTParam>
1097 typename PassT::Result *getCachedResult(IRUnitTParam &IR) const {
1098 typename PassT::Result *Res =
1099 OuterAM->template getCachedResult<PassT>(IR);
1100 if (Res)
1101 OuterAM->template verifyNotInvalidated<PassT>(IR, Res);
1102 return Res;
1103 }
1104
1105 /// Method provided for unit testing, not intended for general use.
1106 template <typename PassT, typename IRUnitTParam>
1107 bool cachedResultExists(IRUnitTParam &IR) const {
1108 typename PassT::Result *Res =
1109 OuterAM->template getCachedResult<PassT>(IR);
1110 return Res != nullptr;
1111 }
1112
1113 /// When invalidation occurs, remove any registered invalidation events.
1115 IRUnitT &IRUnit, const PreservedAnalyses &PA,
1117 // Loop over the set of registered outer invalidation mappings and if any
1118 // of them map to an analysis that is now invalid, clear it out.
1120 for (auto &KeyValuePair : OuterAnalysisInvalidationMap) {
1121 AnalysisKey *OuterID = KeyValuePair.first;
1122 auto &InnerIDs = KeyValuePair.second;
1123 llvm::erase_if(InnerIDs, [&](AnalysisKey *InnerID) {
1124 return Inv.invalidate(InnerID, IRUnit, PA);
1125 });
1126 if (InnerIDs.empty())
1127 DeadKeys.push_back(OuterID);
1128 }
1129
1130 for (auto *OuterID : DeadKeys)
1131 OuterAnalysisInvalidationMap.erase(OuterID);
1132
1133 // The proxy itself remains valid regardless of anything else.
1134 return false;
1135 }
1136
1137 /// Register a deferred invalidation event for when the outer analysis
1138 /// manager processes its invalidations.
1139 template <typename OuterAnalysisT, typename InvalidatedAnalysisT>
1141 AnalysisKey *OuterID = OuterAnalysisT::ID();
1142 AnalysisKey *InvalidatedID = InvalidatedAnalysisT::ID();
1143
1144 auto &InvalidatedIDList = OuterAnalysisInvalidationMap[OuterID];
1145 // Note, this is a linear scan. If we end up with large numbers of
1146 // analyses that all trigger invalidation on the same outer analysis,
1147 // this entire system should be changed to some other deterministic
1148 // data structure such as a `SetVector` of a pair of pointers.
1149 if (!llvm::is_contained(InvalidatedIDList, InvalidatedID))
1150 InvalidatedIDList.push_back(InvalidatedID);
1151 }
1152
1153 /// Access the map from outer analyses to deferred invalidation requiring
1154 /// analyses.
1157 return OuterAnalysisInvalidationMap;
1158 }
1159
1160 private:
1161 const AnalysisManagerT *OuterAM;
1162
1163 /// A map from an outer analysis ID to the set of this IR-unit's analyses
1164 /// which need to be invalidated.
1166 OuterAnalysisInvalidationMap;
1167 };
1168
1169 OuterAnalysisManagerProxy(const AnalysisManagerT &OuterAM)
1170 : OuterAM(&OuterAM) {}
1171
1172 /// Run the analysis pass and create our proxy result object.
1173 /// Nothing to see here, it just forwards the \c OuterAM reference into the
1174 /// result.
1176 ExtraArgTs...) {
1177 return Result(*OuterAM);
1178 }
1179
1180private:
1181 friend AnalysisInfoMixin<
1182 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>>;
1183
1184 static AnalysisKey Key;
1185
1186 const AnalysisManagerT *OuterAM;
1187};
1188
1189template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
1190AnalysisKey
1191 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
1192
1193extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
1194 Function>;
1195/// Provide the \c ModuleAnalysisManager to \c Function proxy.
1198
1199/// Trivial adaptor that maps from a module to its functions.
1200///
1201/// Designed to allow composition of a FunctionPass(Manager) and
1202/// a ModulePassManager, by running the FunctionPass(Manager) over every
1203/// function in the module.
1204///
1205/// Function passes run within this adaptor can rely on having exclusive access
1206/// to the function they are run over. They should not read or modify any other
1207/// functions! Other threads or systems may be manipulating other functions in
1208/// the module, and so their state should never be relied on.
1209/// FIXME: Make the above true for all of LLVM's actual passes, some still
1210/// violate this principle.
1211///
1212/// Function passes can also read the module containing the function, but they
1213/// should not modify that module outside of the use lists of various globals.
1214/// For example, a function pass is not permitted to add functions to the
1215/// module.
1216/// FIXME: Make the above true for all of LLVM's actual passes, some still
1217/// violate this principle.
1218///
1219/// Note that although function passes can access module analyses, module
1220/// analyses are not invalidated while the function passes are running, so they
1221/// may be stale. Function analyses will not be stale.
1223 : public PassInfoMixin<ModuleToFunctionPassAdaptor> {
1224public:
1226
1227 explicit ModuleToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass,
1228 bool EagerlyInvalidate)
1229 : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate) {}
1230
1231 /// Runs the function pass across every function in the module.
1234 function_ref<StringRef(StringRef)> MapClassName2PassName);
1235
1236 static bool isRequired() { return true; }
1237
1238private:
1239 std::unique_ptr<PassConceptT> Pass;
1240 bool EagerlyInvalidate;
1241};
1242
1243/// A function to deduce a function pass type and wrap it in the
1244/// templated adaptor.
1245template <typename FunctionPassT>
1246ModuleToFunctionPassAdaptor
1248 bool EagerlyInvalidate = false) {
1249 using PassModelT =
1252 // Do not use make_unique, it causes too many template instantiations,
1253 // causing terrible compile times.
1255 std::unique_ptr<ModuleToFunctionPassAdaptor::PassConceptT>(
1256 new PassModelT(std::forward<FunctionPassT>(Pass))),
1257 EagerlyInvalidate);
1258}
1259
1260/// A utility pass template to force an analysis result to be available.
1261///
1262/// If there are extra arguments at the pass's run level there may also be
1263/// extra arguments to the analysis manager's \c getResult routine. We can't
1264/// guess how to effectively map the arguments from one to the other, and so
1265/// this specialization just ignores them.
1266///
1267/// Specific patterns of run-method extra arguments and analysis manager extra
1268/// arguments will have to be defined as appropriate specializations.
1269template <typename AnalysisT, typename IRUnitT,
1270 typename AnalysisManagerT = AnalysisManager<IRUnitT>,
1271 typename... ExtraArgTs>
1273 : PassInfoMixin<RequireAnalysisPass<AnalysisT, IRUnitT, AnalysisManagerT,
1274 ExtraArgTs...>> {
1275 /// Run this pass over some unit of IR.
1276 ///
1277 /// This pass can be run over any unit of IR and use any analysis manager
1278 /// provided they satisfy the basic API requirements. When this pass is
1279 /// created, these methods can be instantiated to satisfy whatever the
1280 /// context requires.
1281 PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM,
1282 ExtraArgTs &&... Args) {
1283 (void)AM.template getResult<AnalysisT>(Arg,
1284 std::forward<ExtraArgTs>(Args)...);
1285
1286 return PreservedAnalyses::all();
1287 }
1289 function_ref<StringRef(StringRef)> MapClassName2PassName) {
1290 auto ClassName = AnalysisT::name();
1291 auto PassName = MapClassName2PassName(ClassName);
1292 OS << "require<" << PassName << '>';
1293 }
1294 static bool isRequired() { return true; }
1295};
1296
1297/// A no-op pass template which simply forces a specific analysis result
1298/// to be invalidated.
1299template <typename AnalysisT>
1301 : PassInfoMixin<InvalidateAnalysisPass<AnalysisT>> {
1302 /// Run this pass over some unit of IR.
1303 ///
1304 /// This pass can be run over any unit of IR and use any analysis manager,
1305 /// provided they satisfy the basic API requirements. When this pass is
1306 /// created, these methods can be instantiated to satisfy whatever the
1307 /// context requires.
1308 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
1309 PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&...) {
1310 auto PA = PreservedAnalyses::all();
1311 PA.abandon<AnalysisT>();
1312 return PA;
1313 }
1315 function_ref<StringRef(StringRef)> MapClassName2PassName) {
1316 auto ClassName = AnalysisT::name();
1317 auto PassName = MapClassName2PassName(ClassName);
1318 OS << "invalidate<" << PassName << '>';
1319 }
1320};
1321
1322/// A utility pass that does nothing, but preserves no analyses.
1323///
1324/// Because this preserves no analyses, any analysis passes queried after this
1325/// pass runs will recompute fresh results.
1326struct InvalidateAllAnalysesPass : PassInfoMixin<InvalidateAllAnalysesPass> {
1327 /// Run this pass over some unit of IR.
1328 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
1329 PreservedAnalyses run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {
1330 return PreservedAnalyses::none();
1331 }
1332};
1333
1334/// A utility pass template that simply runs another pass multiple times.
1335///
1336/// This can be useful when debugging or testing passes. It also serves as an
1337/// example of how to extend the pass manager in ways beyond composition.
1338template <typename PassT>
1339class RepeatedPass : public PassInfoMixin<RepeatedPass<PassT>> {
1340public:
1341 RepeatedPass(int Count, PassT &&P)
1342 : Count(Count), P(std::forward<PassT>(P)) {}
1343
1344 template <typename IRUnitT, typename AnalysisManagerT, typename... Ts>
1345 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, Ts &&... Args) {
1346
1347 // Request PassInstrumentation from analysis manager, will use it to run
1348 // instrumenting callbacks for the passes later.
1349 // Here we use std::tuple wrapper over getResult which helps to extract
1350 // AnalysisManager's arguments out of the whole Args set.
1352 detail::getAnalysisResult<PassInstrumentationAnalysis>(
1353 AM, IR, std::tuple<Ts...>(Args...));
1354
1355 auto PA = PreservedAnalyses::all();
1356 for (int i = 0; i < Count; ++i) {
1357 // Check the PassInstrumentation's BeforePass callbacks before running the
1358 // pass, skip its execution completely if asked to (callback returns
1359 // false).
1360 if (!PI.runBeforePass<IRUnitT>(P, IR))
1361 continue;
1362 PreservedAnalyses IterPA = P.run(IR, AM, std::forward<Ts>(Args)...);
1363 PA.intersect(IterPA);
1364 PI.runAfterPass(P, IR, IterPA);
1365 }
1366 return PA;
1367 }
1368
1370 function_ref<StringRef(StringRef)> MapClassName2PassName) {
1371 OS << "repeat<" << Count << ">(";
1372 P.printPipeline(OS, MapClassName2PassName);
1373 OS << ')';
1374 }
1375
1376private:
1377 int Count;
1378 PassT P;
1379};
1380
1381template <typename PassT>
1383 return RepeatedPass<PassT>(Count, std::forward<PassT>(P));
1384}
1385
1386} // end namespace llvm
1387
1388#endif // LLVM_IR_PASSMANAGER_H
Function Alias Analysis Results
#define LLVM_ATTRIBUTE_MINSIZE
Definition: Compiler.h:214
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
std::string Name
uint64_t Size
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:81
Module.h This file contains the declarations for the Module class.
#define P(N)
This file defines the Pass Instrumentation classes that provide instrumentation points into the pass ...
This header provides internal APIs and implementation details used by the pass management interfaces ...
llvm::cl::opt< bool > UseNewDbgInfoFormat
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
static const char PassName[]
Value * RHS
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:110
static AnalysisSetKey * ID()
Definition: PassManager.h:112
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:690
bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA)
A type-erased variant of the above invalidate method with the same core API other than passing an ana...
Definition: PassManager.h:722
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:708
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
AnalysisManager()
Construct an empty analysis manager.
void clear()
Clear all analysis results cached by this AnalysisManager.
Definition: PassManager.h:794
AnalysisManager(AnalysisManager &&)
void verifyNotInvalidated(IRUnitT &IR, typename PassT::Result *Result) const
Verify that the given Result cannot be invalidated, assert otherwise.
Definition: PassManager.h:839
AnalysisManager & operator=(AnalysisManager &&)
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:822
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:865
bool empty() const
Returns true if the analysis manager has an empty results cache.
Definition: PassManager.h:774
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:133
static AnalysisSetKey * ID()
Definition: PassManager.h:135
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition: DenseMap.h:71
bool empty() const
Definition: DenseMap.h:98
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
Definition: DenseMap.h:73
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
Handler for invalidation of the outer IR unit, IRUnitT.
Result(AnalysisManagerT &InnerAM)
Definition: PassManager.h:966
AnalysisManagerT & getManager()
Accessor for the analysis manager.
Definition: PassManager.h:995
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:962
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:1023
InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM)
Definition: PassManager.h:1015
Trivial adaptor that maps from a module to its functions.
Definition: PassManager.h:1223
ModuleToFunctionPassAdaptor(std::unique_ptr< PassConceptT > Pass, bool EagerlyInvalidate)
Definition: PassManager.h:1227
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Runs the function pass across every function in the module.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.cpp:93
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Result proxy object for OuterAnalysisManagerProxy.
Definition: PassManager.h:1090
Result(const AnalysisManagerT &OuterAM)
Definition: PassManager.h:1092
PassT::Result * getCachedResult(IRUnitTParam &IR) const
Get a cached analysis.
Definition: PassManager.h:1097
bool invalidate(IRUnitT &IRUnit, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
When invalidation occurs, remove any registered invalidation events.
Definition: PassManager.h:1114
bool cachedResultExists(IRUnitTParam &IR) const
Method provided for unit testing, not intended for general use.
Definition: PassManager.h:1107
const SmallDenseMap< AnalysisKey *, TinyPtrVector< AnalysisKey * >, 2 > & getOuterInvalidations() const
Access the map from outer analyses to deferred invalidation requiring analyses.
Definition: PassManager.h:1156
void registerOuterAnalysisInvalidation()
Register a deferred invalidation event for when the outer analysis manager processes its invalidation...
Definition: PassManager.h:1140
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1087
Result run(IRUnitT &, AnalysisManager< IRUnitT, ExtraArgTs... > &, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:1175
OuterAnalysisManagerProxy(const AnalysisManagerT &OuterAM)
Definition: PassManager.h:1169
This class provides access to building LLVM's passes.
Definition: PassBuilder.h:103
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:624
Result run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...)
Definition: PassManager.h:639
PassInstrumentationAnalysis(PassInstrumentationCallbacks *Callbacks=nullptr)
PassInstrumentationCallbacks object is shared, owned by something else, not this analysis.
Definition: PassManager.h:633
This class manages callbacks registration, as well as provides a way for PassInstrumentation to pass ...
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
void runAfterPass(const PassT &Pass, const IRUnitT &IR, const PreservedAnalyses &PA) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
Manages a sequence of passes over a particular unit of IR.
Definition: PassManager.h:490
PassManager(PassManager &&Arg)
Definition: PassManager.h:499
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.h:506
PassManager & operator=(PassManager &&RHS)
Definition: PassManager.h:501
LLVM_ATTRIBUTE_MINSIZE std::enable_if_t<!std::is_same< PassT, PassManager >::value > addPass(PassT &&Pass)
Definition: PassManager.h:573
std::vector< std::unique_ptr< PassConceptT > > Passes
Definition: PassManager.h:605
PassManager()=default
Construct a pass manager.
static bool isRequired()
Definition: PassManager.h:599
LLVM_ATTRIBUTE_MINSIZE std::enable_if_t< std::is_same< PassT, PassManager >::value > addPass(PassT &&Pass)
When adding a pass manager pass that has the same type as this pass manager, simply move the passes o...
Definition: PassManager.h:591
PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs)
Run all of the passes in this manager over the given unit of IR.
Definition: PassManager.h:518
bool isEmpty() const
Returns if the pass manager contains any passes.
Definition: PassManager.h:597
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
A checker object that makes it easy to query for whether an analysis or some set covering it is prese...
Definition: PassManager.h:286
bool preserved()
Returns true if the checker's analysis was not abandoned and either.
Definition: PassManager.h:303
bool preservedWhenStateless()
Return true if the checker's analysis was not abandoned, i.e.
Definition: PassManager.h:311
bool preservedSet()
Returns true if the checker's analysis was not abandoned and either.
Definition: PassManager.h:318
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:172
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:175
void preserveSet(AnalysisSetKey *ID)
Mark an analysis set as preserved using its ID.
Definition: PassManager.h:213
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: PassManager.h:347
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
Definition: PassManager.h:355
PreservedAnalysisChecker getChecker(AnalysisKey *ID) const
Build a checker for this PreservedAnalyses and the specified analysis ID.
Definition: PassManager.h:339
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: PassManager.h:244
void intersect(PreservedAnalyses &&Arg)
Intersect this set with a temporary other set in place.
Definition: PassManager.h:266
void abandon(AnalysisKey *ID)
Mark an analysis as abandoned using its ID.
Definition: PassManager.h:235
bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const
Directly test whether a set of analyses is preserved.
Definition: PassManager.h:362
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:208
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:330
void preserve(AnalysisKey *ID)
Given an analysis's ID, mark the analysis as preserved, adding it to the set.
Definition: PassManager.h:197
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:226
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:193
static PreservedAnalyses allInSet()
Construct a preserved analyses object with a single preserved set.
Definition: PassManager.h:186
A utility pass template that simply runs another pass multiple times.
Definition: PassManager.h:1339
PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, Ts &&... Args)
Definition: PassManager.h:1345
RepeatedPass(int Count, PassT &&P)
Definition: PassManager.h:1341
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.h:1369
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
PassT::Result getAnalysisResultUnpackTuple(AnalysisManagerT &AM, IRUnitT &IR, std::tuple< ArgTs... > Args, std::index_sequence< Ns... >)
Actual unpacker of extra arguments in getAnalysisResult, passes only those tuple arguments that are m...
Definition: PassManager.h:444
PassT::Result getAnalysisResult(AnalysisManager< IRUnitT, AnalysisArgTs... > &AM, IRUnitT &IR, std::tuple< MainArgTs... > Args)
Helper for partial unpacking of extra arguments in getAnalysisResult.
Definition: PassManager.h:459
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ModuleToFunctionPassAdaptor createModuleToFunctionPassAdaptor(FunctionPassT &&Pass, bool EagerlyInvalidate=false)
A function to deduce a function pass type and wrap it in the templated adaptor.
Definition: PassManager.h:1247
RepeatedPass< PassT > createRepeatedPass(int Count, PassT &&P)
Definition: PassManager.h:1382
void doConvertDebugInfoToOld(IRUnitT &IR)
Definition: PassManager.h:78
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition: PassManager.h:936
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:941
void doConvertDbgInfoToNew(IRUnitT &IR)
Definition: PassManager.h:74
bool shouldConvertDbgInfo(IRUnitT &IR)
Definition: PassManager.h:68
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1918
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1853
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2020
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1883
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:414
static AnalysisKey * ID()
Returns an opaque, unique ID for this analysis type.
Definition: PassManager.h:430
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:89
A special type used to provide an address that identifies a set of related analyses.
Definition: PassManager.h:99
A utility pass that does nothing, but preserves no analyses.
Definition: PassManager.h:1326
PreservedAnalyses run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...)
Run this pass over some unit of IR.
Definition: PassManager.h:1329
A no-op pass template which simply forces a specific analysis result to be invalidated.
Definition: PassManager.h:1301
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.h:1314
PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&...)
Run this pass over some unit of IR.
Definition: PassManager.h:1309
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:391
static StringRef name()
Gets the name of the pass we are mixed into.
Definition: PassManager.h:393
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.h:401
A utility pass template to force an analysis result to be available.
Definition: PassManager.h:1274
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.h:1288
PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&... Args)
Run this pass over some unit of IR.
Definition: PassManager.h:1281
Abstract concept of an analysis pass.
Wrapper to model the analysis pass concept.
Abstract concept of an analysis result.
Wrapper to model the analysis result concept.
A template wrapper used to implement the polymorphic API.