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"
42#include "llvm/ADT/SmallPtrSet.h"
43#include "llvm/ADT/StringRef.h"
44#include "llvm/ADT/TinyPtrVector.h"
45#include "llvm/IR/Analysis.h"
46#include "llvm/IR/Function.h"
47#include "llvm/IR/Module.h"
48#include "llvm/IR/PassInstrumentation.h"
49#include "llvm/IR/PassManagerInternal.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/TimeProfiler.h"
52#include "llvm/Support/TypeName.h"
53#include <cassert>
54#include <cstring>
55#include <iterator>
56#include <list>
57#include <memory>
58#include <tuple>
59#include <type_traits>
60#include <utility>
61#include <vector>
62
63extern llvm::cl::opt<bool> UseNewDbgInfoFormat;
64
65namespace llvm {
66
67// Forward declare the analysis manager template.
68template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
69
70/// A CRTP mix-in to automatically provide informational APIs needed for
71/// passes.
72///
73/// This provides some boilerplate for types that are passes.
74template <typename DerivedT> struct PassInfoMixin {
75 /// Gets the name of the pass we are mixed into.
76 static StringRef name() {
77 static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value,
78 "Must pass the derived type as the template argument!");
79 StringRef Name = getTypeName<DerivedT>();
80 Name.consume_front(Prefix: "llvm::");
81 return Name;
82 }
83
84 void printPipeline(raw_ostream &OS,
85 function_ref<StringRef(StringRef)> MapClassName2PassName) {
86 StringRef ClassName = DerivedT::name();
87 auto PassName = MapClassName2PassName(ClassName);
88 OS << PassName;
89 }
90};
91
92/// A CRTP mix-in that provides informational APIs needed for analysis passes.
93///
94/// This provides some boilerplate for types that are analysis passes. It
95/// automatically mixes in \c PassInfoMixin.
96template <typename DerivedT>
97struct AnalysisInfoMixin : PassInfoMixin<DerivedT> {
98 /// Returns an opaque, unique ID for this analysis type.
99 ///
100 /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus
101 /// suitable for use in sets, maps, and other data structures that use the low
102 /// bits of pointers.
103 ///
104 /// Note that this requires the derived type provide a static \c AnalysisKey
105 /// member called \c Key.
106 ///
107 /// FIXME: The only reason the mixin type itself can't declare the Key value
108 /// is that some compilers cannot correctly unique a templated static variable
109 /// so it has the same addresses in each instantiation. The only currently
110 /// known platform with this limitation is Windows DLL builds, specifically
111 /// building each part of LLVM as a DLL. If we ever remove that build
112 /// configuration, this mixin can provide the static key as well.
113 static AnalysisKey *ID() {
114 static_assert(std::is_base_of<AnalysisInfoMixin, DerivedT>::value,
115 "Must pass the derived type as the template argument!");
116 return &DerivedT::Key;
117 }
118};
119
120namespace detail {
121
122/// Actual unpacker of extra arguments in getAnalysisResult,
123/// passes only those tuple arguments that are mentioned in index_sequence.
124template <typename PassT, typename IRUnitT, typename AnalysisManagerT,
125 typename... ArgTs, size_t... Ns>
126typename PassT::Result
127getAnalysisResultUnpackTuple(AnalysisManagerT &AM, IRUnitT &IR,
128 std::tuple<ArgTs...> Args,
129 std::index_sequence<Ns...>) {
130 (void)Args;
131 return AM.template getResult<PassT>(IR, std::get<Ns>(Args)...);
132}
133
134/// Helper for *partial* unpacking of extra arguments in getAnalysisResult.
135///
136/// Arguments passed in tuple come from PassManager, so they might have extra
137/// arguments after those AnalysisManager's ExtraArgTs ones that we need to
138/// pass to getResult.
139template <typename PassT, typename IRUnitT, typename... AnalysisArgTs,
140 typename... MainArgTs>
141typename PassT::Result
142getAnalysisResult(AnalysisManager<IRUnitT, AnalysisArgTs...> &AM, IRUnitT &IR,
143 std::tuple<MainArgTs...> Args) {
144 return (getAnalysisResultUnpackTuple<
145 PassT, IRUnitT>)(AM, IR, Args,
146 std::index_sequence_for<AnalysisArgTs...>{});
147}
148
149} // namespace detail
150
151// Forward declare the pass instrumentation analysis explicitly queried in
152// generic PassManager code.
153// FIXME: figure out a way to move PassInstrumentationAnalysis into its own
154// header.
155class PassInstrumentationAnalysis;
156
157/// Manages a sequence of passes over a particular unit of IR.
158///
159/// A pass manager contains a sequence of passes to run over a particular unit
160/// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of
161/// IR, and when run over some given IR will run each of its contained passes in
162/// sequence. Pass managers are the primary and most basic building block of a
163/// pass pipeline.
164///
165/// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT>
166/// argument. The pass manager will propagate that analysis manager to each
167/// pass it runs, and will call the analysis manager's invalidation routine with
168/// the PreservedAnalyses of each pass it runs.
169template <typename IRUnitT,
170 typename AnalysisManagerT = AnalysisManager<IRUnitT>,
171 typename... ExtraArgTs>
172class PassManager : public PassInfoMixin<
173 PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
174public:
175 /// Construct a pass manager.
176 explicit PassManager() = default;
177
178 // FIXME: These are equivalent to the default move constructor/move
179 // assignment. However, using = default triggers linker errors due to the
180 // explicit instantiations below. Find away to use the default and remove the
181 // duplicated code here.
182 PassManager(PassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
183
184 PassManager &operator=(PassManager &&RHS) {
185 Passes = std::move(RHS.Passes);
186 return *this;
187 }
188
189 void printPipeline(raw_ostream &OS,
190 function_ref<StringRef(StringRef)> MapClassName2PassName) {
191 for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
192 auto *P = Passes[Idx].get();
193 P->printPipeline(OS, MapClassName2PassName);
194 if (Idx + 1 < Size)
195 OS << ',';
196 }
197 }
198
199 /// Run all of the passes in this manager over the given unit of IR.
200 /// ExtraArgs are passed to each pass.
201 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
202 ExtraArgTs... ExtraArgs) {
203 PreservedAnalyses PA = PreservedAnalyses::all();
204
205 // Request PassInstrumentation from analysis manager, will use it to run
206 // instrumenting callbacks for the passes later.
207 // Here we use std::tuple wrapper over getResult which helps to extract
208 // AnalysisManager's arguments out of the whole ExtraArgs set.
209 PassInstrumentation PI =
210 detail::getAnalysisResult<PassInstrumentationAnalysis>(
211 AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));
212
213 // RemoveDIs: if requested, convert debug-info to DbgRecord representation
214 // for duration of these passes.
215 ScopedDbgInfoFormatSetter FormatSetter(IR, UseNewDbgInfoFormat);
216
217 for (auto &Pass : Passes) {
218 // Check the PassInstrumentation's BeforePass callbacks before running the
219 // pass, skip its execution completely if asked to (callback returns
220 // false).
221 if (!PI.runBeforePass<IRUnitT>(*Pass, IR))
222 continue;
223
224 PreservedAnalyses PassPA = Pass->run(IR, AM, ExtraArgs...);
225
226 // Update the analysis manager as each pass runs and potentially
227 // invalidates analyses.
228 AM.invalidate(IR, PassPA);
229
230 // Call onto PassInstrumentation's AfterPass callbacks immediately after
231 // running the pass.
232 PI.runAfterPass<IRUnitT>(*Pass, IR, PassPA);
233
234 // Finally, intersect the preserved analyses to compute the aggregate
235 // preserved set for this pass manager.
236 PA.intersect(Arg: std::move(PassPA));
237 }
238
239 // Invalidation was handled after each pass in the above loop for the
240 // current unit of IR. Therefore, the remaining analysis results in the
241 // AnalysisManager are preserved. We mark this with a set so that we don't
242 // need to inspect each one individually.
243 PA.preserveSet<AllAnalysesOn<IRUnitT>>();
244
245 return PA;
246 }
247
248 // FIXME: Revert to enable_if style when gcc >= 11.1
249 template <typename PassT> LLVM_ATTRIBUTE_MINSIZE void addPass(PassT &&Pass) {
250 using PassModelT =
251 detail::PassModel<IRUnitT, PassT, AnalysisManagerT, ExtraArgTs...>;
252 if constexpr (!std::is_same_v<PassT, PassManager>) {
253 // Do not use make_unique or emplace_back, they cause too many template
254 // instantiations, causing terrible compile times.
255 Passes.push_back(std::unique_ptr<PassConceptT>(
256 new PassModelT(std::forward<PassT>(Pass))));
257 } else {
258 /// When adding a pass manager pass that has the same type as this pass
259 /// manager, simply move the passes over. This is because we don't have
260 /// use cases rely on executing nested pass managers. Doing this could
261 /// reduce implementation complexity and avoid potential invalidation
262 /// issues that may happen with nested pass managers of the same type.
263 for (auto &P : Pass.Passes)
264 Passes.push_back(std::move(P));
265 }
266 }
267
268 /// Returns if the pass manager contains any passes.
269 bool isEmpty() const { return Passes.empty(); }
270
271 static bool isRequired() { return true; }
272
273protected:
274 using PassConceptT =
275 detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
276
277 std::vector<std::unique_ptr<PassConceptT>> Passes;
278};
279
280extern template class PassManager<Module>;
281
282/// Convenience typedef for a pass manager over modules.
283using ModulePassManager = PassManager<Module>;
284
285extern template class PassManager<Function>;
286
287/// Convenience typedef for a pass manager over functions.
288using FunctionPassManager = PassManager<Function>;
289
290/// Pseudo-analysis pass that exposes the \c PassInstrumentation to pass
291/// managers. Goes before AnalysisManager definition to provide its
292/// internals (e.g PassInstrumentationAnalysis::ID) for use there if needed.
293/// FIXME: figure out a way to move PassInstrumentationAnalysis into its own
294/// header.
295class PassInstrumentationAnalysis
296 : public AnalysisInfoMixin<PassInstrumentationAnalysis> {
297 friend AnalysisInfoMixin<PassInstrumentationAnalysis>;
298 static AnalysisKey Key;
299
300 PassInstrumentationCallbacks *Callbacks;
301
302public:
303 /// PassInstrumentationCallbacks object is shared, owned by something else,
304 /// not this analysis.
305 PassInstrumentationAnalysis(PassInstrumentationCallbacks *Callbacks = nullptr)
306 : Callbacks(Callbacks) {}
307
308 using Result = PassInstrumentation;
309
310 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
311 Result run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {
312 return PassInstrumentation(Callbacks);
313 }
314};
315
316/// A container for analyses that lazily runs them and caches their
317/// results.
318///
319/// This class can manage analyses for any IR unit where the address of the IR
320/// unit sufficies as its identity.
321template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager {
322public:
323 class Invalidator;
324
325private:
326 // Now that we've defined our invalidator, we can define the concept types.
327 using ResultConceptT = detail::AnalysisResultConcept<IRUnitT, Invalidator>;
328 using PassConceptT =
329 detail::AnalysisPassConcept<IRUnitT, Invalidator, ExtraArgTs...>;
330
331 /// List of analysis pass IDs and associated concept pointers.
332 ///
333 /// Requires iterators to be valid across appending new entries and arbitrary
334 /// erases. Provides the analysis ID to enable finding iterators to a given
335 /// entry in maps below, and provides the storage for the actual result
336 /// concept.
337 using AnalysisResultListT =
338 std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>;
339
340 /// Map type from IRUnitT pointer to our custom list type.
341 using AnalysisResultListMapT = DenseMap<IRUnitT *, AnalysisResultListT>;
342
343 /// Map type from a pair of analysis ID and IRUnitT pointer to an
344 /// iterator into a particular result list (which is where the actual analysis
345 /// result is stored).
346 using AnalysisResultMapT =
347 DenseMap<std::pair<AnalysisKey *, IRUnitT *>,
348 typename AnalysisResultListT::iterator>;
349
350public:
351 /// API to communicate dependencies between analyses during invalidation.
352 ///
353 /// When an analysis result embeds handles to other analysis results, it
354 /// needs to be invalidated both when its own information isn't preserved and
355 /// when any of its embedded analysis results end up invalidated. We pass an
356 /// \c Invalidator object as an argument to \c invalidate() in order to let
357 /// the analysis results themselves define the dependency graph on the fly.
358 /// This lets us avoid building an explicit representation of the
359 /// dependencies between analysis results.
360 class Invalidator {
361 public:
362 /// Trigger the invalidation of some other analysis pass if not already
363 /// handled and return whether it was in fact invalidated.
364 ///
365 /// This is expected to be called from within a given analysis result's \c
366 /// invalidate method to trigger a depth-first walk of all inter-analysis
367 /// dependencies. The same \p IR unit and \p PA passed to that result's \c
368 /// invalidate method should in turn be provided to this routine.
369 ///
370 /// The first time this is called for a given analysis pass, it will call
371 /// the corresponding result's \c invalidate method. Subsequent calls will
372 /// use a cache of the results of that initial call. It is an error to form
373 /// cyclic dependencies between analysis results.
374 ///
375 /// This returns true if the given analysis's result is invalid. Any
376 /// dependecies on it will become invalid as a result.
377 template <typename PassT>
378 bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
379 using ResultModelT =
380 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
381 Invalidator>;
382
383 return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);
384 }
385
386 /// A type-erased variant of the above invalidate method with the same core
387 /// API other than passing an analysis ID rather than an analysis type
388 /// parameter.
389 ///
390 /// This is sadly less efficient than the above routine, which leverages
391 /// the type parameter to avoid the type erasure overhead.
392 bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
393 return invalidateImpl<>(ID, IR, PA);
394 }
395
396 private:
397 friend class AnalysisManager;
398
399 template <typename ResultT = ResultConceptT>
400 bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,
401 const PreservedAnalyses &PA) {
402 // If we've already visited this pass, return true if it was invalidated
403 // and false otherwise.
404 auto IMapI = IsResultInvalidated.find(Val: ID);
405 if (IMapI != IsResultInvalidated.end())
406 return IMapI->second;
407
408 // Otherwise look up the result object.
409 auto RI = Results.find({ID, &IR});
410 assert(RI != Results.end() &&
411 "Trying to invalidate a dependent result that isn't in the "
412 "manager's cache is always an error, likely due to a stale result "
413 "handle!");
414
415 auto &Result = static_cast<ResultT &>(*RI->second->second);
416
417 // Insert into the map whether the result should be invalidated and return
418 // that. Note that we cannot reuse IMapI and must do a fresh insert here,
419 // as calling invalidate could (recursively) insert things into the map,
420 // making any iterator or reference invalid.
421 bool Inserted;
422 std::tie(args&: IMapI, args&: Inserted) =
423 IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});
424 (void)Inserted;
425 assert(Inserted && "Should not have already inserted this ID, likely "
426 "indicates a dependency cycle!");
427 return IMapI->second;
428 }
429
430 Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated,
431 const AnalysisResultMapT &Results)
432 : IsResultInvalidated(IsResultInvalidated), Results(Results) {}
433
434 SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;
435 const AnalysisResultMapT &Results;
436 };
437
438 /// Construct an empty analysis manager.
439 AnalysisManager();
440 AnalysisManager(AnalysisManager &&);
441 AnalysisManager &operator=(AnalysisManager &&);
442
443 /// Returns true if the analysis manager has an empty results cache.
444 bool empty() const {
445 assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&
446 "The storage and index of analysis results disagree on how many "
447 "there are!");
448 return AnalysisResults.empty();
449 }
450
451 /// Clear any cached analysis results for a single unit of IR.
452 ///
453 /// This doesn't invalidate, but instead simply deletes, the relevant results.
454 /// It is useful when the IR is being removed and we want to clear out all the
455 /// memory pinned for it.
456 void clear(IRUnitT &IR, llvm::StringRef Name);
457
458 /// Clear all analysis results cached by this AnalysisManager.
459 ///
460 /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply
461 /// deletes them. This lets you clean up the AnalysisManager when the set of
462 /// IR units itself has potentially changed, and thus we can't even look up a
463 /// a result and invalidate/clear it directly.
464 void clear() {
465 AnalysisResults.clear();
466 AnalysisResultLists.clear();
467 }
468
469 /// Get the result of an analysis pass for a given IR unit.
470 ///
471 /// Runs the analysis if a cached result is not available.
472 template <typename PassT>
473 typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) {
474 assert(AnalysisPasses.count(PassT::ID()) &&
475 "This analysis pass was not registered prior to being queried");
476 ResultConceptT &ResultConcept =
477 getResultImpl(ID: PassT::ID(), IR, ExtraArgs: ExtraArgs...);
478
479 using ResultModelT =
480 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
481 Invalidator>;
482
483 return static_cast<ResultModelT &>(ResultConcept).Result;
484 }
485
486 /// Get the cached result of an analysis pass for a given IR unit.
487 ///
488 /// This method never runs the analysis.
489 ///
490 /// \returns null if there is no cached result.
491 template <typename PassT>
492 typename PassT::Result *getCachedResult(IRUnitT &IR) const {
493 assert(AnalysisPasses.count(PassT::ID()) &&
494 "This analysis pass was not registered prior to being queried");
495
496 ResultConceptT *ResultConcept = getCachedResultImpl(ID: PassT::ID(), IR);
497 if (!ResultConcept)
498 return nullptr;
499
500 using ResultModelT =
501 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
502 Invalidator>;
503
504 return &static_cast<ResultModelT *>(ResultConcept)->Result;
505 }
506
507 /// Verify that the given Result cannot be invalidated, assert otherwise.
508 template <typename PassT>
509 void verifyNotInvalidated(IRUnitT &IR, typename PassT::Result *Result) const {
510 PreservedAnalyses PA = PreservedAnalyses::none();
511 SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
512 Invalidator Inv(IsResultInvalidated, AnalysisResults);
513 assert(!Result->invalidate(IR, PA, Inv) &&
514 "Cached result cannot be invalidated");
515 }
516
517 /// Register an analysis pass with the manager.
518 ///
519 /// The parameter is a callable whose result is an analysis pass. This allows
520 /// passing in a lambda to construct the analysis.
521 ///
522 /// The analysis type to register is the type returned by calling the \c
523 /// PassBuilder argument. If that type has already been registered, then the
524 /// argument will not be called and this function will return false.
525 /// Otherwise, we register the analysis returned by calling \c PassBuilder(),
526 /// and this function returns true.
527 ///
528 /// (Note: Although the return value of this function indicates whether or not
529 /// an analysis was previously registered, there intentionally isn't a way to
530 /// query this directly. Instead, you should just register all the analyses
531 /// you might want and let this class run them lazily. This idiom lets us
532 /// minimize the number of times we have to look up analyses in our
533 /// hashtable.)
534 template <typename PassBuilderT>
535 bool registerPass(PassBuilderT &&PassBuilder) {
536 using PassT = decltype(PassBuilder());
537 using PassModelT =
538 detail::AnalysisPassModel<IRUnitT, PassT, Invalidator, ExtraArgTs...>;
539
540 auto &PassPtr = AnalysisPasses[PassT::ID()];
541 if (PassPtr)
542 // Already registered this pass type!
543 return false;
544
545 // Construct a new model around the instance returned by the builder.
546 PassPtr.reset(new PassModelT(PassBuilder()));
547 return true;
548 }
549
550 /// Invalidate cached analyses for an IR unit.
551 ///
552 /// Walk through all of the analyses pertaining to this unit of IR and
553 /// invalidate them, unless they are preserved by the PreservedAnalyses set.
554 void invalidate(IRUnitT &IR, const PreservedAnalyses &PA);
555
556private:
557 /// Look up a registered analysis pass.
558 PassConceptT &lookUpPass(AnalysisKey *ID) {
559 typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(ID);
560 assert(PI != AnalysisPasses.end() &&
561 "Analysis passes must be registered prior to being queried!");
562 return *PI->second;
563 }
564
565 /// Look up a registered analysis pass.
566 const PassConceptT &lookUpPass(AnalysisKey *ID) const {
567 typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(ID);
568 assert(PI != AnalysisPasses.end() &&
569 "Analysis passes must be registered prior to being queried!");
570 return *PI->second;
571 }
572
573 /// Get an analysis result, running the pass if necessary.
574 ResultConceptT &getResultImpl(AnalysisKey *ID, IRUnitT &IR,
575 ExtraArgTs... ExtraArgs);
576
577 /// Get a cached analysis result or return null.
578 ResultConceptT *getCachedResultImpl(AnalysisKey *ID, IRUnitT &IR) const {
579 typename AnalysisResultMapT::const_iterator RI =
580 AnalysisResults.find({ID, &IR});
581 return RI == AnalysisResults.end() ? nullptr : &*RI->second->second;
582 }
583
584 /// Map type from analysis pass ID to pass concept pointer.
585 using AnalysisPassMapT =
586 DenseMap<AnalysisKey *, std::unique_ptr<PassConceptT>>;
587
588 /// Collection of analysis passes, indexed by ID.
589 AnalysisPassMapT AnalysisPasses;
590
591 /// Map from IR unit to a list of analysis results.
592 ///
593 /// Provides linear time removal of all analysis results for a IR unit and
594 /// the ultimate storage for a particular cached analysis result.
595 AnalysisResultListMapT AnalysisResultLists;
596
597 /// Map from an analysis ID and IR unit to a particular cached
598 /// analysis result.
599 AnalysisResultMapT AnalysisResults;
600};
601
602extern template class AnalysisManager<Module>;
603
604/// Convenience typedef for the Module analysis manager.
605using ModuleAnalysisManager = AnalysisManager<Module>;
606
607extern template class AnalysisManager<Function>;
608
609/// Convenience typedef for the Function analysis manager.
610using FunctionAnalysisManager = AnalysisManager<Function>;
611
612/// An analysis over an "outer" IR unit that provides access to an
613/// analysis manager over an "inner" IR unit. The inner unit must be contained
614/// in the outer unit.
615///
616/// For example, InnerAnalysisManagerProxy<FunctionAnalysisManager, Module> is
617/// an analysis over Modules (the "outer" unit) that provides access to a
618/// Function analysis manager. The FunctionAnalysisManager is the "inner"
619/// manager being proxied, and Functions are the "inner" unit. The inner/outer
620/// relationship is valid because each Function is contained in one Module.
621///
622/// If you're (transitively) within a pass manager for an IR unit U that
623/// contains IR unit V, you should never use an analysis manager over V, except
624/// via one of these proxies.
625///
626/// Note that the proxy's result is a move-only RAII object. The validity of
627/// the analyses in the inner analysis manager is tied to its lifetime.
628template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
629class InnerAnalysisManagerProxy
630 : public AnalysisInfoMixin<
631 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> {
632public:
633 class Result {
634 public:
635 explicit Result(AnalysisManagerT &InnerAM) : InnerAM(&InnerAM) {}
636
637 Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)) {
638 // We have to null out the analysis manager in the moved-from state
639 // because we are taking ownership of the responsibilty to clear the
640 // analysis state.
641 Arg.InnerAM = nullptr;
642 }
643
644 ~Result() {
645 // InnerAM is cleared in a moved from state where there is nothing to do.
646 if (!InnerAM)
647 return;
648
649 // Clear out the analysis manager if we're being destroyed -- it means we
650 // didn't even see an invalidate call when we got invalidated.
651 InnerAM->clear();
652 }
653
654 Result &operator=(Result &&RHS) {
655 InnerAM = RHS.InnerAM;
656 // We have to null out the analysis manager in the moved-from state
657 // because we are taking ownership of the responsibilty to clear the
658 // analysis state.
659 RHS.InnerAM = nullptr;
660 return *this;
661 }
662
663 /// Accessor for the analysis manager.
664 AnalysisManagerT &getManager() { return *InnerAM; }
665
666 /// Handler for invalidation of the outer IR unit, \c IRUnitT.
667 ///
668 /// If the proxy analysis itself is not preserved, we assume that the set of
669 /// inner IR objects contained in IRUnit may have changed. In this case,
670 /// we have to call \c clear() on the inner analysis manager, as it may now
671 /// have stale pointers to its inner IR objects.
672 ///
673 /// Regardless of whether the proxy analysis is marked as preserved, all of
674 /// the analyses in the inner analysis manager are potentially invalidated
675 /// based on the set of preserved analyses.
676 bool invalidate(
677 IRUnitT &IR, const PreservedAnalyses &PA,
678 typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv);
679
680 private:
681 AnalysisManagerT *InnerAM;
682 };
683
684 explicit InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM)
685 : InnerAM(&InnerAM) {}
686
687 /// Run the analysis pass and create our proxy result object.
688 ///
689 /// This doesn't do any interesting work; it is primarily used to insert our
690 /// proxy result object into the outer analysis cache so that we can proxy
691 /// invalidation to the inner analysis manager.
692 Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
693 ExtraArgTs...) {
694 return Result(*InnerAM);
695 }
696
697private:
698 friend AnalysisInfoMixin<
699 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>;
700
701 static AnalysisKey Key;
702
703 AnalysisManagerT *InnerAM;
704};
705
706template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
707AnalysisKey
708 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
709
710/// Provide the \c FunctionAnalysisManager to \c Module proxy.
711using FunctionAnalysisManagerModuleProxy =
712 InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>;
713
714/// Specialization of the invalidate method for the \c
715/// FunctionAnalysisManagerModuleProxy's result.
716template <>
717bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
718 Module &M, const PreservedAnalyses &PA,
719 ModuleAnalysisManager::Invalidator &Inv);
720
721// Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern
722// template.
723extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
724 Module>;
725
726/// An analysis over an "inner" IR unit that provides access to an
727/// analysis manager over a "outer" IR unit. The inner unit must be contained
728/// in the outer unit.
729///
730/// For example OuterAnalysisManagerProxy<ModuleAnalysisManager, Function> is an
731/// analysis over Functions (the "inner" unit) which provides access to a Module
732/// analysis manager. The ModuleAnalysisManager is the "outer" manager being
733/// proxied, and Modules are the "outer" IR unit. The inner/outer relationship
734/// is valid because each Function is contained in one Module.
735///
736/// This proxy only exposes the const interface of the outer analysis manager,
737/// to indicate that you cannot cause an outer analysis to run from within an
738/// inner pass. Instead, you must rely on the \c getCachedResult API. This is
739/// due to keeping potential future concurrency in mind. To give an example,
740/// running a module analysis before any function passes may give a different
741/// result than running it in a function pass. Both may be valid, but it would
742/// produce non-deterministic results. GlobalsAA is a good analysis example,
743/// because the cached information has the mod/ref info for all memory for each
744/// function at the time the analysis was computed. The information is still
745/// valid after a function transformation, but it may be *different* if
746/// recomputed after that transform. GlobalsAA is never invalidated.
747
748///
749/// This proxy doesn't manage invalidation in any way -- that is handled by the
750/// recursive return path of each layer of the pass manager. A consequence of
751/// this is the outer analyses may be stale. We invalidate the outer analyses
752/// only when we're done running passes over the inner IR units.
753template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
754class OuterAnalysisManagerProxy
755 : public AnalysisInfoMixin<
756 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>> {
757public:
758 /// Result proxy object for \c OuterAnalysisManagerProxy.
759 class Result {
760 public:
761 explicit Result(const AnalysisManagerT &OuterAM) : OuterAM(&OuterAM) {}
762
763 /// Get a cached analysis. If the analysis can be invalidated, this will
764 /// assert.
765 template <typename PassT, typename IRUnitTParam>
766 typename PassT::Result *getCachedResult(IRUnitTParam &IR) const {
767 typename PassT::Result *Res =
768 OuterAM->template getCachedResult<PassT>(IR);
769 if (Res)
770 OuterAM->template verifyNotInvalidated<PassT>(IR, Res);
771 return Res;
772 }
773
774 /// Method provided for unit testing, not intended for general use.
775 template <typename PassT, typename IRUnitTParam>
776 bool cachedResultExists(IRUnitTParam &IR) const {
777 typename PassT::Result *Res =
778 OuterAM->template getCachedResult<PassT>(IR);
779 return Res != nullptr;
780 }
781
782 /// When invalidation occurs, remove any registered invalidation events.
783 bool invalidate(
784 IRUnitT &IRUnit, const PreservedAnalyses &PA,
785 typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv) {
786 // Loop over the set of registered outer invalidation mappings and if any
787 // of them map to an analysis that is now invalid, clear it out.
788 SmallVector<AnalysisKey *, 4> DeadKeys;
789 for (auto &KeyValuePair : OuterAnalysisInvalidationMap) {
790 AnalysisKey *OuterID = KeyValuePair.first;
791 auto &InnerIDs = KeyValuePair.second;
792 llvm::erase_if(InnerIDs, [&](AnalysisKey *InnerID) {
793 return Inv.invalidate(InnerID, IRUnit, PA);
794 });
795 if (InnerIDs.empty())
796 DeadKeys.push_back(Elt: OuterID);
797 }
798
799 for (auto *OuterID : DeadKeys)
800 OuterAnalysisInvalidationMap.erase(Val: OuterID);
801
802 // The proxy itself remains valid regardless of anything else.
803 return false;
804 }
805
806 /// Register a deferred invalidation event for when the outer analysis
807 /// manager processes its invalidations.
808 template <typename OuterAnalysisT, typename InvalidatedAnalysisT>
809 void registerOuterAnalysisInvalidation() {
810 AnalysisKey *OuterID = OuterAnalysisT::ID();
811 AnalysisKey *InvalidatedID = InvalidatedAnalysisT::ID();
812
813 auto &InvalidatedIDList = OuterAnalysisInvalidationMap[OuterID];
814 // Note, this is a linear scan. If we end up with large numbers of
815 // analyses that all trigger invalidation on the same outer analysis,
816 // this entire system should be changed to some other deterministic
817 // data structure such as a `SetVector` of a pair of pointers.
818 if (!llvm::is_contained(Range&: InvalidatedIDList, Element: InvalidatedID))
819 InvalidatedIDList.push_back(NewVal: InvalidatedID);
820 }
821
822 /// Access the map from outer analyses to deferred invalidation requiring
823 /// analyses.
824 const SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2> &
825 getOuterInvalidations() const {
826 return OuterAnalysisInvalidationMap;
827 }
828
829 private:
830 const AnalysisManagerT *OuterAM;
831
832 /// A map from an outer analysis ID to the set of this IR-unit's analyses
833 /// which need to be invalidated.
834 SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2>
835 OuterAnalysisInvalidationMap;
836 };
837
838 OuterAnalysisManagerProxy(const AnalysisManagerT &OuterAM)
839 : OuterAM(&OuterAM) {}
840
841 /// Run the analysis pass and create our proxy result object.
842 /// Nothing to see here, it just forwards the \c OuterAM reference into the
843 /// result.
844 Result run(IRUnitT &, AnalysisManager<IRUnitT, ExtraArgTs...> &,
845 ExtraArgTs...) {
846 return Result(*OuterAM);
847 }
848
849private:
850 friend AnalysisInfoMixin<
851 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>>;
852
853 static AnalysisKey Key;
854
855 const AnalysisManagerT *OuterAM;
856};
857
858template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
859AnalysisKey
860 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key;
861
862extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
863 Function>;
864/// Provide the \c ModuleAnalysisManager to \c Function proxy.
865using ModuleAnalysisManagerFunctionProxy =
866 OuterAnalysisManagerProxy<ModuleAnalysisManager, Function>;
867
868/// Trivial adaptor that maps from a module to its functions.
869///
870/// Designed to allow composition of a FunctionPass(Manager) and
871/// a ModulePassManager, by running the FunctionPass(Manager) over every
872/// function in the module.
873///
874/// Function passes run within this adaptor can rely on having exclusive access
875/// to the function they are run over. They should not read or modify any other
876/// functions! Other threads or systems may be manipulating other functions in
877/// the module, and so their state should never be relied on.
878/// FIXME: Make the above true for all of LLVM's actual passes, some still
879/// violate this principle.
880///
881/// Function passes can also read the module containing the function, but they
882/// should not modify that module outside of the use lists of various globals.
883/// For example, a function pass is not permitted to add functions to the
884/// module.
885/// FIXME: Make the above true for all of LLVM's actual passes, some still
886/// violate this principle.
887///
888/// Note that although function passes can access module analyses, module
889/// analyses are not invalidated while the function passes are running, so they
890/// may be stale. Function analyses will not be stale.
891class ModuleToFunctionPassAdaptor
892 : public PassInfoMixin<ModuleToFunctionPassAdaptor> {
893public:
894 using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>;
895
896 explicit ModuleToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass,
897 bool EagerlyInvalidate)
898 : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate) {}
899
900 /// Runs the function pass across every function in the module.
901 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
902 void printPipeline(raw_ostream &OS,
903 function_ref<StringRef(StringRef)> MapClassName2PassName);
904
905 static bool isRequired() { return true; }
906
907private:
908 std::unique_ptr<PassConceptT> Pass;
909 bool EagerlyInvalidate;
910};
911
912/// A function to deduce a function pass type and wrap it in the
913/// templated adaptor.
914template <typename FunctionPassT>
915ModuleToFunctionPassAdaptor
916createModuleToFunctionPassAdaptor(FunctionPassT &&Pass,
917 bool EagerlyInvalidate = false) {
918 using PassModelT =
919 detail::PassModel<Function, FunctionPassT, FunctionAnalysisManager>;
920 // Do not use make_unique, it causes too many template instantiations,
921 // causing terrible compile times.
922 return ModuleToFunctionPassAdaptor(
923 std::unique_ptr<ModuleToFunctionPassAdaptor::PassConceptT>(
924 new PassModelT(std::forward<FunctionPassT>(Pass))),
925 EagerlyInvalidate);
926}
927
928/// A utility pass template to force an analysis result to be available.
929///
930/// If there are extra arguments at the pass's run level there may also be
931/// extra arguments to the analysis manager's \c getResult routine. We can't
932/// guess how to effectively map the arguments from one to the other, and so
933/// this specialization just ignores them.
934///
935/// Specific patterns of run-method extra arguments and analysis manager extra
936/// arguments will have to be defined as appropriate specializations.
937template <typename AnalysisT, typename IRUnitT,
938 typename AnalysisManagerT = AnalysisManager<IRUnitT>,
939 typename... ExtraArgTs>
940struct RequireAnalysisPass
941 : PassInfoMixin<RequireAnalysisPass<AnalysisT, IRUnitT, AnalysisManagerT,
942 ExtraArgTs...>> {
943 /// Run this pass over some unit of IR.
944 ///
945 /// This pass can be run over any unit of IR and use any analysis manager
946 /// provided they satisfy the basic API requirements. When this pass is
947 /// created, these methods can be instantiated to satisfy whatever the
948 /// context requires.
949 PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM,
950 ExtraArgTs &&... Args) {
951 (void)AM.template getResult<AnalysisT>(Arg,
952 std::forward<ExtraArgTs>(Args)...);
953
954 return PreservedAnalyses::all();
955 }
956 void printPipeline(raw_ostream &OS,
957 function_ref<StringRef(StringRef)> MapClassName2PassName) {
958 auto ClassName = AnalysisT::name();
959 auto PassName = MapClassName2PassName(ClassName);
960 OS << "require<" << PassName << '>';
961 }
962 static bool isRequired() { return true; }
963};
964
965/// A no-op pass template which simply forces a specific analysis result
966/// to be invalidated.
967template <typename AnalysisT>
968struct InvalidateAnalysisPass
969 : PassInfoMixin<InvalidateAnalysisPass<AnalysisT>> {
970 /// Run this pass over some unit of IR.
971 ///
972 /// This pass can be run over any unit of IR and use any analysis manager,
973 /// provided they satisfy the basic API requirements. When this pass is
974 /// created, these methods can be instantiated to satisfy whatever the
975 /// context requires.
976 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
977 PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&...) {
978 auto PA = PreservedAnalyses::all();
979 PA.abandon<AnalysisT>();
980 return PA;
981 }
982 void printPipeline(raw_ostream &OS,
983 function_ref<StringRef(StringRef)> MapClassName2PassName) {
984 auto ClassName = AnalysisT::name();
985 auto PassName = MapClassName2PassName(ClassName);
986 OS << "invalidate<" << PassName << '>';
987 }
988};
989
990/// A utility pass that does nothing, but preserves no analyses.
991///
992/// Because this preserves no analyses, any analysis passes queried after this
993/// pass runs will recompute fresh results.
994struct InvalidateAllAnalysesPass : PassInfoMixin<InvalidateAllAnalysesPass> {
995 /// Run this pass over some unit of IR.
996 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
997 PreservedAnalyses run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) {
998 return PreservedAnalyses::none();
999 }
1000};
1001
1002/// A utility pass template that simply runs another pass multiple times.
1003///
1004/// This can be useful when debugging or testing passes. It also serves as an
1005/// example of how to extend the pass manager in ways beyond composition.
1006template <typename PassT>
1007class RepeatedPass : public PassInfoMixin<RepeatedPass<PassT>> {
1008public:
1009 RepeatedPass(int Count, PassT &&P)
1010 : Count(Count), P(std::forward<PassT>(P)) {}
1011
1012 template <typename IRUnitT, typename AnalysisManagerT, typename... Ts>
1013 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, Ts &&... Args) {
1014
1015 // Request PassInstrumentation from analysis manager, will use it to run
1016 // instrumenting callbacks for the passes later.
1017 // Here we use std::tuple wrapper over getResult which helps to extract
1018 // AnalysisManager's arguments out of the whole Args set.
1019 PassInstrumentation PI =
1020 detail::getAnalysisResult<PassInstrumentationAnalysis>(
1021 AM, IR, std::tuple<Ts...>(Args...));
1022
1023 auto PA = PreservedAnalyses::all();
1024 for (int i = 0; i < Count; ++i) {
1025 // Check the PassInstrumentation's BeforePass callbacks before running the
1026 // pass, skip its execution completely if asked to (callback returns
1027 // false).
1028 if (!PI.runBeforePass<IRUnitT>(P, IR))
1029 continue;
1030 PreservedAnalyses IterPA = P.run(IR, AM, std::forward<Ts>(Args)...);
1031 PA.intersect(Arg: IterPA);
1032 PI.runAfterPass(P, IR, IterPA);
1033 }
1034 return PA;
1035 }
1036
1037 void printPipeline(raw_ostream &OS,
1038 function_ref<StringRef(StringRef)> MapClassName2PassName) {
1039 OS << "repeat<" << Count << ">(";
1040 P.printPipeline(OS, MapClassName2PassName);
1041 OS << ')';
1042 }
1043
1044private:
1045 int Count;
1046 PassT P;
1047};
1048
1049template <typename PassT>
1050RepeatedPass<PassT> createRepeatedPass(int Count, PassT &&P) {
1051 return RepeatedPass<PassT>(Count, std::forward<PassT>(P));
1052}
1053
1054} // end namespace llvm
1055
1056#endif // LLVM_IR_PASSMANAGER_H
1057

source code of llvm/include/llvm/IR/PassManager.h