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

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