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 | |
58 | namespace llvm { |
59 | |
60 | class Function; |
61 | class Module; |
62 | |
63 | // Forward declare the analysis manager template. |
64 | template <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. |
70 | template <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. |
92 | template <typename DerivedT> |
93 | struct 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 | |
116 | namespace detail { |
117 | |
118 | /// Actual unpacker of extra arguments in getAnalysisResult, |
119 | /// passes only those tuple arguments that are mentioned in index_sequence. |
120 | template <typename PassT, typename IRUnitT, typename AnalysisManagerT, |
121 | typename... ArgTs, size_t... Ns> |
122 | typename PassT::Result |
123 | getAnalysisResultUnpackTuple(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. |
135 | template <typename PassT, typename IRUnitT, typename... AnalysisArgTs, |
136 | typename... MainArgTs> |
137 | typename PassT::Result |
138 | getAnalysisResult(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. |
159 | template <typename IRUnitT, |
160 | typename AnalysisManagerT = AnalysisManager<IRUnitT>, |
161 | typename... ExtraArgTs> |
162 | class PassManager : public PassInfoMixin< |
163 | PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> { |
164 | public: |
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... ); |
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 | |
222 | protected: |
223 | using PassConceptT = |
224 | detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>; |
225 | |
226 | std::vector<std::unique_ptr<PassConceptT>> Passes; |
227 | }; |
228 | |
229 | template <typename IRUnitT> |
230 | void printIRUnitNameForStackTrace(raw_ostream &OS, const IRUnitT &IR); |
231 | |
232 | template <> |
233 | LLVM_ABI void printIRUnitNameForStackTrace<Module>(raw_ostream &OS, |
234 | const Module &IR); |
235 | |
236 | extern template class LLVM_TEMPLATE_ABI PassManager<Module>; |
237 | |
238 | /// Convenience typedef for a pass manager over modules. |
239 | using ModulePassManager = PassManager<Module>; |
240 | |
241 | template <> |
242 | LLVM_ABI void printIRUnitNameForStackTrace<Function>(raw_ostream &OS, |
243 | const Function &IR); |
244 | |
245 | extern template class LLVM_TEMPLATE_ABI PassManager<Function>; |
246 | |
247 | /// Convenience typedef for a pass manager over functions. |
248 | using 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. |
255 | template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager { |
256 | public: |
257 | class Invalidator; |
258 | |
259 | private: |
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 | |
284 | public: |
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... ) { |
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 | |
494 | private: |
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... ); |
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 | |
540 | extern template class LLVM_TEMPLATE_ABI AnalysisManager<Module>; |
541 | |
542 | /// Convenience typedef for the Module analysis manager. |
543 | using ModuleAnalysisManager = AnalysisManager<Module>; |
544 | |
545 | extern template class LLVM_TEMPLATE_ABI AnalysisManager<Function>; |
546 | |
547 | /// Convenience typedef for the Function analysis manager. |
548 | using 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. |
566 | template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> |
567 | class LLVM_TEMPLATE_ABI InnerAnalysisManagerProxy |
568 | : public AnalysisInfoMixin< |
569 | InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> { |
570 | public: |
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 | |
635 | private: |
636 | friend AnalysisInfoMixin< |
637 | InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>; |
638 | |
639 | static AnalysisKey Key; |
640 | |
641 | AnalysisManagerT *InnerAM; |
642 | }; |
643 | |
644 | template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> |
645 | AnalysisKey |
646 | InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key; |
647 | |
648 | /// Provide the \c FunctionAnalysisManager to \c Module proxy. |
649 | using FunctionAnalysisManagerModuleProxy = |
650 | InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>; |
651 | |
652 | /// Specialization of the invalidate method for the \c |
653 | /// FunctionAnalysisManagerModuleProxy's result. |
654 | template <> |
655 | LLVM_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. |
661 | extern 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. |
691 | template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> |
692 | class OuterAnalysisManagerProxy |
693 | : public AnalysisInfoMixin< |
694 | OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>> { |
695 | public: |
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 | |
787 | private: |
788 | friend AnalysisInfoMixin< |
789 | OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>>; |
790 | |
791 | static AnalysisKey Key; |
792 | |
793 | const AnalysisManagerT *OuterAM; |
794 | }; |
795 | |
796 | template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> |
797 | AnalysisKey |
798 | OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key; |
799 | |
800 | extern template class LLVM_TEMPLATE_ABI |
801 | OuterAnalysisManagerProxy<ModuleAnalysisManager, Function>; |
802 | /// Provide the \c ModuleAnalysisManager to \c Function proxy. |
803 | using 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. |
829 | class ModuleToFunctionPassAdaptor |
830 | : public PassInfoMixin<ModuleToFunctionPassAdaptor> { |
831 | public: |
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 | |
846 | private: |
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. |
853 | template <typename FunctionPassT> |
854 | ModuleToFunctionPassAdaptor |
855 | createModuleToFunctionPassAdaptor(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. |
876 | template <typename AnalysisT, typename IRUnitT, |
877 | typename AnalysisManagerT = AnalysisManager<IRUnitT>, |
878 | typename... ExtraArgTs> |
879 | struct 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. |
906 | template <typename AnalysisT> |
907 | struct 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. |
933 | struct 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 | |