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

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