1 //===- PassManager.h - Pass management infrastructure -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This header defines various interfaces for pass management in LLVM. There
12 /// is no "pass" interface in LLVM per se. Instead, an instance of any class
13 /// which supports a method to 'run' it over a unit of IR can be used as
14 /// a pass. A pass manager is generally a tool to collect a sequence of passes
15 /// which run over a particular IR construct, and run each of them in sequence
16 /// over each such construct in the containing IR construct. As there is no
17 /// containing IR construct for a Module, a manager for passes over modules
18 /// forms the base case which runs its managed passes in sequence over the
19 /// single module provided.
21 /// The core IR library provides managers for running passes over
22 /// modules and functions.
24 /// * FunctionPassManager can run over a Module, runs each pass over
26 /// * ModulePassManager must be directly run, runs each pass over the Module.
28 /// Note that the implementations of the pass managers use concept-based
29 /// polymorphism as outlined in the "Value Semantics and Concept-based
30 /// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base
31 /// Class of Evil") by Sean Parent:
32 /// * http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations
33 /// * http://www.youtube.com/watch?v=_BpMYeUFXv8
34 /// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil
36 //===----------------------------------------------------------------------===//
38 #ifndef LLVM_IR_PASS_MANAGER_H
39 #define LLVM_IR_PASS_MANAGER_H
41 #include "llvm/ADT/DenseMap.h"
42 #include "llvm/ADT/STLExtras.h"
43 #include "llvm/ADT/SmallPtrSet.h"
44 #include "llvm/IR/Function.h"
45 #include "llvm/IR/Module.h"
46 #include "llvm/Support/type_traits.h"
56 /// \brief An abstract set of preserved analyses following a transformation pass
59 /// When a transformation pass is run, it can return a set of analyses whose
60 /// results were preserved by that transformation. The default set is "none",
61 /// and preserving analyses must be done explicitly.
63 /// There is also an explicit all state which can be used (for example) when
64 /// the IR is not mutated at all.
65 class PreservedAnalyses {
67 PreservedAnalyses() {}
68 PreservedAnalyses(const PreservedAnalyses &Arg)
69 : PreservedPassIDs(Arg.PreservedPassIDs) {}
70 PreservedAnalyses(PreservedAnalyses &&Arg)
71 : PreservedPassIDs(Arg.PreservedPassIDs) {}
72 PreservedAnalyses &operator=(PreservedAnalyses RHS) {
73 std::swap(*this, RHS);
77 /// \brief Convenience factory function for the empty preserved set.
78 static PreservedAnalyses none() { return PreservedAnalyses(); }
80 /// \brief Construct a special preserved set that preserves all passes.
81 static PreservedAnalyses all() {
83 PA.PreservedPassIDs.insert((void *)AllPassesID);
87 /// \brief Mark a particular pass as preserved, adding it to the set.
88 template <typename PassT> void preserve() {
89 if (!areAllPreserved())
90 PreservedPassIDs.insert(PassT::ID());
93 /// \brief Intersect this set with another in place.
95 /// This is a mutating operation on this preserved set, removing all
96 /// preserved passes which are not also preserved in the argument.
97 void intersect(const PreservedAnalyses &Arg) {
98 if (Arg.areAllPreserved())
100 if (areAllPreserved()) {
101 PreservedPassIDs = Arg.PreservedPassIDs;
104 for (SmallPtrSet<void *, 2>::const_iterator I = PreservedPassIDs.begin(),
105 E = PreservedPassIDs.end();
107 if (!Arg.PreservedPassIDs.count(*I))
108 PreservedPassIDs.erase(*I);
111 /// \brief Intersect this set with a temporary other set in place.
113 /// This is a mutating operation on this preserved set, removing all
114 /// preserved passes which are not also preserved in the argument.
115 void intersect(PreservedAnalyses &&Arg) {
116 if (Arg.areAllPreserved())
118 if (areAllPreserved()) {
119 PreservedPassIDs = std::move(Arg.PreservedPassIDs);
122 for (SmallPtrSet<void *, 2>::const_iterator I = PreservedPassIDs.begin(),
123 E = PreservedPassIDs.end();
125 if (!Arg.PreservedPassIDs.count(*I))
126 PreservedPassIDs.erase(*I);
129 /// \brief Query whether a pass is marked as preserved by this set.
130 template <typename PassT> bool preserved() const {
131 return preserved(PassT::ID());
134 /// \brief Query whether an abstract pass ID is marked as preserved by this
136 bool preserved(void *PassID) const {
137 return PreservedPassIDs.count((void *)AllPassesID) ||
138 PreservedPassIDs.count(PassID);
142 // Note that this must not be -1 or -2 as those are already used by the
144 static const uintptr_t AllPassesID = (intptr_t)-3;
146 bool areAllPreserved() const { return PreservedPassIDs.count((void *)AllPassesID); }
148 SmallPtrSet<void *, 2> PreservedPassIDs;
151 /// \brief Implementation details of the pass manager interfaces.
154 /// \brief Template for the abstract base class used to dispatch
155 /// polymorphically over pass objects.
156 template <typename IRUnitT, typename AnalysisManagerT> struct PassConcept {
157 // Boiler plate necessary for the container of derived classes.
158 virtual ~PassConcept() {}
160 /// \brief The polymorphic API which runs the pass over a given IR entity.
162 /// Note that actual pass object can omit the analysis manager argument if
163 /// desired. Also that the analysis manager may be null if there is no
164 /// analysis manager in the pass pipeline.
165 virtual PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) = 0;
167 /// \brief Polymorphic method to access the name of a pass.
168 virtual StringRef name() = 0;
171 /// \brief SFINAE metafunction for computing whether \c PassT has a run method
172 /// accepting an \c AnalysisManagerT.
173 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
175 class PassRunAcceptsAnalysisManager {
176 typedef char SmallType;
177 struct BigType { char a, b; };
179 template <typename T, ResultT (T::*)(IRUnitT, AnalysisManagerT *)>
182 template <typename T> static SmallType f(Checker<T, &T::run> *);
183 template <typename T> static BigType f(...);
186 enum { Value = sizeof(f<PassT>(0)) == sizeof(SmallType) };
189 /// \brief A template wrapper used to implement the polymorphic API.
191 /// Can be instantiated for any object which provides a \c run method accepting
192 /// an \c IRUnitT. It requires the pass to be a copyable object. When the
193 /// \c run method also accepts an \c AnalysisManagerT*, we pass it along.
194 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
195 bool AcceptsAnalysisManager = PassRunAcceptsAnalysisManager<
196 IRUnitT, AnalysisManagerT, PassT, PreservedAnalyses>::Value>
199 /// \brief Specialization of \c PassModel for passes that accept an analyis
201 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
202 struct PassModel<IRUnitT, AnalysisManagerT, PassT,
203 true> : PassConcept<IRUnitT, AnalysisManagerT> {
204 explicit PassModel(PassT Pass) : Pass(std::move(Pass)) {}
205 PassModel(const PassModel &Arg) : Pass(Arg.Pass) {}
206 PassModel(PassModel &&Arg) : Pass(Arg.Pass) {}
207 PassModel &operator=(PassModel RHS) {
208 std::swap(*this, RHS);
212 PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) override {
213 return Pass.run(IR, AM);
215 StringRef name() override { return PassT::name(); }
219 /// \brief Specialization of \c PassModel for passes that accept an analyis
221 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
222 struct PassModel<IRUnitT, AnalysisManagerT, PassT,
223 false> : PassConcept<IRUnitT, AnalysisManagerT> {
224 explicit PassModel(PassT Pass) : Pass(std::move(Pass)) {}
225 PassModel(const PassModel &Arg) : Pass(Arg.Pass) {}
226 PassModel(PassModel &&Arg) : Pass(Arg.Pass) {}
227 PassModel &operator=(PassModel RHS) {
228 std::swap(*this, RHS);
232 PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) override {
235 StringRef name() override { return PassT::name(); }
239 /// \brief Abstract concept of an analysis result.
241 /// This concept is parameterized over the IR unit that this result pertains
243 template <typename IRUnitT> struct AnalysisResultConcept {
244 virtual ~AnalysisResultConcept() {}
246 /// \brief Method to try and mark a result as invalid.
248 /// When the outer analysis manager detects a change in some underlying
249 /// unit of the IR, it will call this method on all of the results cached.
251 /// This method also receives a set of preserved analyses which can be used
252 /// to avoid invalidation because the pass which changed the underlying IR
253 /// took care to update or preserve the analysis result in some way.
255 /// \returns true if the result is indeed invalid (the default).
256 virtual bool invalidate(IRUnitT IR, const PreservedAnalyses &PA) = 0;
259 /// \brief SFINAE metafunction for computing whether \c ResultT provides an
260 /// \c invalidate member function.
261 template <typename IRUnitT, typename ResultT> class ResultHasInvalidateMethod {
262 typedef char SmallType;
263 struct BigType { char a, b; };
265 template <typename T, bool (T::*)(IRUnitT, const PreservedAnalyses &)>
268 template <typename T> static SmallType f(Checker<T, &T::invalidate> *);
269 template <typename T> static BigType f(...);
272 enum { Value = sizeof(f<ResultT>(0)) == sizeof(SmallType) };
275 /// \brief Wrapper to model the analysis result concept.
277 /// By default, this will implement the invalidate method with a trivial
278 /// implementation so that the actual analysis result doesn't need to provide
279 /// an invalidation handler. It is only selected when the invalidation handler
280 /// is not part of the ResultT's interface.
281 template <typename IRUnitT, typename PassT, typename ResultT,
282 bool HasInvalidateHandler =
283 ResultHasInvalidateMethod<IRUnitT, ResultT>::Value>
284 struct AnalysisResultModel;
286 /// \brief Specialization of \c AnalysisResultModel which provides the default
287 /// invalidate functionality.
288 template <typename IRUnitT, typename PassT, typename ResultT>
289 struct AnalysisResultModel<IRUnitT, PassT, ResultT,
290 false> : AnalysisResultConcept<IRUnitT> {
291 explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
292 AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
293 AnalysisResultModel(AnalysisResultModel &&Arg) : Result(Arg.Result) {}
294 AnalysisResultModel &operator=(AnalysisResultModel RHS) {
295 std::swap(*this, RHS);
299 /// \brief The model bases invalidation solely on being in the preserved set.
301 // FIXME: We should actually use two different concepts for analysis results
302 // rather than two different models, and avoid the indirect function call for
303 // ones that use the trivial behavior.
304 bool invalidate(IRUnitT, const PreservedAnalyses &PA) override {
305 return !PA.preserved(PassT::ID());
311 /// \brief Specialization of \c AnalysisResultModel which delegates invalidate
312 /// handling to \c ResultT.
313 template <typename IRUnitT, typename PassT, typename ResultT>
314 struct AnalysisResultModel<IRUnitT, PassT, ResultT,
315 true> : AnalysisResultConcept<IRUnitT> {
316 explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
317 AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
318 AnalysisResultModel(AnalysisResultModel &&Arg) : Result(Arg.Result) {}
319 AnalysisResultModel &operator=(AnalysisResultModel RHS) {
320 std::swap(*this, RHS);
324 /// \brief The model delegates to the \c ResultT method.
325 bool invalidate(IRUnitT IR, const PreservedAnalyses &PA) override {
326 return Result.invalidate(IR, PA);
332 /// \brief Abstract concept of an analysis pass.
334 /// This concept is parameterized over the IR unit that it can run over and
335 /// produce an analysis result.
336 template <typename IRUnitT, typename AnalysisManagerT>
337 struct AnalysisPassConcept {
338 virtual ~AnalysisPassConcept() {}
340 /// \brief Method to run this analysis over a unit of IR.
341 /// \returns A unique_ptr to the analysis result object to be queried by
343 virtual std::unique_ptr<AnalysisResultConcept<IRUnitT>>
344 run(IRUnitT IR, AnalysisManagerT *AM) = 0;
347 /// \brief Wrapper to model the analysis pass concept.
349 /// Can wrap any type which implements a suitable \c run method. The method
350 /// must accept the IRUnitT as an argument and produce an object which can be
351 /// wrapped in a \c AnalysisResultModel.
352 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
353 bool AcceptsAnalysisManager = PassRunAcceptsAnalysisManager<
354 IRUnitT, AnalysisManagerT, PassT,
355 typename PassT::Result>::Value> struct AnalysisPassModel;
357 /// \brief Specialization of \c AnalysisPassModel which passes an
358 /// \c AnalysisManager to PassT's run method.
359 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
360 struct AnalysisPassModel<IRUnitT, AnalysisManagerT, PassT,
361 true> : AnalysisPassConcept<IRUnitT,
363 explicit AnalysisPassModel(PassT Pass) : Pass(std::move(Pass)) {}
364 AnalysisPassModel(const AnalysisPassModel &Arg) : Pass(Arg.Pass) {}
365 AnalysisPassModel(AnalysisPassModel &&Arg) : Pass(Arg.Pass) {}
366 AnalysisPassModel &operator=(AnalysisPassModel RHS) {
367 std::swap(*this, RHS);
371 // FIXME: Replace PassT::Result with type traits when we use C++11.
372 typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
375 /// \brief The model delegates to the \c PassT::run method.
377 /// The return is wrapped in an \c AnalysisResultModel.
378 std::unique_ptr<AnalysisResultConcept<IRUnitT>>
379 run(IRUnitT IR, AnalysisManagerT *AM) override {
380 return make_unique<ResultModelT>(Pass.run(IR, AM));
386 /// \brief Specialization of \c AnalysisPassModel which does not pass an
387 /// \c AnalysisManager to PassT's run method.
388 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
389 struct AnalysisPassModel<IRUnitT, AnalysisManagerT, PassT,
390 false> : AnalysisPassConcept<IRUnitT,
392 explicit AnalysisPassModel(PassT Pass) : Pass(std::move(Pass)) {}
393 AnalysisPassModel(const AnalysisPassModel &Arg) : Pass(Arg.Pass) {}
394 AnalysisPassModel(AnalysisPassModel &&Arg) : Pass(Arg.Pass) {}
395 AnalysisPassModel &operator=(AnalysisPassModel RHS) {
396 std::swap(*this, RHS);
400 // FIXME: Replace PassT::Result with type traits when we use C++11.
401 typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
404 /// \brief The model delegates to the \c PassT::run method.
406 /// The return is wrapped in an \c AnalysisResultModel.
407 std::unique_ptr<AnalysisResultConcept<IRUnitT>>
408 run(IRUnitT IR, AnalysisManagerT *) override {
409 return make_unique<ResultModelT>(Pass.run(IR));
417 class ModuleAnalysisManager;
419 class ModulePassManager {
421 // We have to explicitly define all the special member functions because MSVC
422 // 2013 refuses to generate them.
423 ModulePassManager() {}
424 ModulePassManager(ModulePassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
425 ModulePassManager &operator=(ModulePassManager &&RHS) {
426 Passes = std::move(RHS.Passes);
430 /// \brief Run all of the module passes in this module pass manager over
433 /// This method should only be called for a single module as there is the
434 /// expectation that the lifetime of a pass is bounded to that of a module.
435 PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM = 0);
437 template <typename ModulePassT> void addPass(ModulePassT Pass) {
438 Passes.emplace_back(new ModulePassModel<ModulePassT>(std::move(Pass)));
441 static StringRef name() { return "ModulePassManager"; }
444 // Pull in the concept type and model template specialized for modules.
445 typedef detail::PassConcept<Module *, ModuleAnalysisManager> ModulePassConcept;
446 template <typename PassT>
447 struct ModulePassModel
448 : detail::PassModel<Module *, ModuleAnalysisManager, PassT> {
449 ModulePassModel(PassT Pass)
450 : detail::PassModel<Module *, ModuleAnalysisManager, PassT>(
454 ModulePassManager(const ModulePassManager &) LLVM_DELETED_FUNCTION;
455 ModulePassManager &operator=(const ModulePassManager &) LLVM_DELETED_FUNCTION;
457 std::vector<std::unique_ptr<ModulePassConcept>> Passes;
460 class FunctionAnalysisManager;
462 class FunctionPassManager {
464 // We have to explicitly define all the special member functions because MSVC
465 // 2013 refuses to generate them.
466 FunctionPassManager() {}
467 FunctionPassManager(FunctionPassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
468 FunctionPassManager &operator=(FunctionPassManager &&RHS) {
469 Passes = std::move(RHS.Passes);
473 template <typename FunctionPassT> void addPass(FunctionPassT Pass) {
474 Passes.emplace_back(new FunctionPassModel<FunctionPassT>(std::move(Pass)));
477 PreservedAnalyses run(Function *F, FunctionAnalysisManager *AM = 0);
479 static StringRef name() { return "FunctionPassManager"; }
482 // Pull in the concept type and model template specialized for functions.
483 typedef detail::PassConcept<Function *, FunctionAnalysisManager>
485 template <typename PassT>
486 struct FunctionPassModel
487 : detail::PassModel<Function *, FunctionAnalysisManager, PassT> {
488 FunctionPassModel(PassT Pass)
489 : detail::PassModel<Function *, FunctionAnalysisManager, PassT>(
493 FunctionPassManager(const FunctionPassManager &) LLVM_DELETED_FUNCTION;
494 FunctionPassManager &
495 operator=(const FunctionPassManager &) LLVM_DELETED_FUNCTION;
497 std::vector<std::unique_ptr<FunctionPassConcept>> Passes;
502 /// \brief A CRTP base used to implement analysis managers.
504 /// This class template serves as the boiler plate of an analysis manager. Any
505 /// analysis manager can be implemented on top of this base class. Any
506 /// implementation will be required to provide specific hooks:
509 /// - getCachedResultImpl
512 /// The details of the call pattern are within.
513 template <typename DerivedT, typename IRUnitT>
514 class AnalysisManagerBase {
515 DerivedT *derived_this() { return static_cast<DerivedT *>(this); }
516 const DerivedT *derived_this() const { return static_cast<const DerivedT *>(this); }
518 AnalysisManagerBase(const AnalysisManagerBase &) LLVM_DELETED_FUNCTION;
519 AnalysisManagerBase &
520 operator=(const AnalysisManagerBase &) LLVM_DELETED_FUNCTION;
523 typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT;
524 typedef detail::AnalysisPassConcept<IRUnitT, DerivedT> PassConceptT;
526 // FIXME: Provide template aliases for the models when we're using C++11 in
527 // a mode supporting them.
529 AnalysisManagerBase() {}
530 AnalysisManagerBase(AnalysisManagerBase &&Arg)
531 : AnalysisPasses(std::move(Arg.AnalysisPasses)) {}
532 AnalysisManagerBase &operator=(AnalysisManagerBase &&RHS) {
533 AnalysisPasses = std::move(RHS.AnalysisPasses);
538 /// \brief Get the result of an analysis pass for this module.
540 /// If there is not a valid cached result in the manager already, this will
541 /// re-run the analysis to produce a valid result.
542 template <typename PassT> typename PassT::Result &getResult(IRUnitT IR) {
543 assert(AnalysisPasses.count(PassT::ID()) &&
544 "This analysis pass was not registered prior to being queried");
546 ResultConceptT &ResultConcept =
547 derived_this()->getResultImpl(PassT::ID(), IR);
548 typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
550 return static_cast<ResultModelT &>(ResultConcept).Result;
553 /// \brief Get the cached result of an analysis pass for this module.
555 /// This method never runs the analysis.
557 /// \returns null if there is no cached result.
558 template <typename PassT>
559 typename PassT::Result *getCachedResult(IRUnitT IR) const {
560 assert(AnalysisPasses.count(PassT::ID()) &&
561 "This analysis pass was not registered prior to being queried");
563 ResultConceptT *ResultConcept =
564 derived_this()->getCachedResultImpl(PassT::ID(), IR);
568 typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
570 return &static_cast<ResultModelT *>(ResultConcept)->Result;
573 /// \brief Register an analysis pass with the manager.
575 /// This provides an initialized and set-up analysis pass to the analysis
576 /// manager. Whomever is setting up analysis passes must use this to populate
577 /// the manager with all of the analysis passes available.
578 template <typename PassT> void registerPass(PassT Pass) {
579 assert(!AnalysisPasses.count(PassT::ID()) &&
580 "Registered the same analysis pass twice!");
581 typedef detail::AnalysisPassModel<IRUnitT, DerivedT, PassT> PassModelT;
582 AnalysisPasses[PassT::ID()].reset(new PassModelT(std::move(Pass)));
585 /// \brief Invalidate a specific analysis pass for an IR module.
587 /// Note that the analysis result can disregard invalidation.
588 template <typename PassT> void invalidate(Module *M) {
589 assert(AnalysisPasses.count(PassT::ID()) &&
590 "This analysis pass was not registered prior to being invalidated");
591 derived_this()->invalidateImpl(PassT::ID(), M);
594 /// \brief Invalidate analyses cached for an IR unit.
596 /// Walk through all of the analyses pertaining to this unit of IR and
597 /// invalidate them unless they are preserved by the PreservedAnalyses set.
598 void invalidate(IRUnitT IR, const PreservedAnalyses &PA) {
599 derived_this()->invalidateImpl(IR, PA);
603 /// \brief Lookup a registered analysis pass.
604 PassConceptT &lookupPass(void *PassID) {
605 typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(PassID);
606 assert(PI != AnalysisPasses.end() &&
607 "Analysis passes must be registered prior to being queried!");
611 /// \brief Lookup a registered analysis pass.
612 const PassConceptT &lookupPass(void *PassID) const {
613 typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(PassID);
614 assert(PI != AnalysisPasses.end() &&
615 "Analysis passes must be registered prior to being queried!");
620 /// \brief Map type from module analysis pass ID to pass concept pointer.
621 typedef DenseMap<void *, std::unique_ptr<PassConceptT>> AnalysisPassMapT;
623 /// \brief Collection of module analysis passes, indexed by ID.
624 AnalysisPassMapT AnalysisPasses;
629 /// \brief A module analysis pass manager with lazy running and caching of
631 class ModuleAnalysisManager
632 : public detail::AnalysisManagerBase<ModuleAnalysisManager, Module *> {
633 friend class detail::AnalysisManagerBase<ModuleAnalysisManager, Module *>;
634 typedef detail::AnalysisManagerBase<ModuleAnalysisManager, Module *> BaseT;
635 typedef BaseT::ResultConceptT ResultConceptT;
636 typedef BaseT::PassConceptT PassConceptT;
639 ModuleAnalysisManager() {}
640 ModuleAnalysisManager(ModuleAnalysisManager &&Arg)
641 : BaseT(std::move(static_cast<BaseT &>(Arg))),
642 ModuleAnalysisResults(std::move(Arg.ModuleAnalysisResults)) {}
643 ModuleAnalysisManager &operator=(ModuleAnalysisManager &&RHS) {
644 BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
645 ModuleAnalysisResults = std::move(RHS.ModuleAnalysisResults);
650 ModuleAnalysisManager(const ModuleAnalysisManager &) LLVM_DELETED_FUNCTION;
651 ModuleAnalysisManager &
652 operator=(const ModuleAnalysisManager &) LLVM_DELETED_FUNCTION;
654 /// \brief Get a module pass result, running the pass if necessary.
655 ResultConceptT &getResultImpl(void *PassID, Module *M);
657 /// \brief Get a cached module pass result or return null.
658 ResultConceptT *getCachedResultImpl(void *PassID, Module *M) const;
660 /// \brief Invalidate a module pass result.
661 void invalidateImpl(void *PassID, Module *M);
663 /// \brief Invalidate results across a module.
664 void invalidateImpl(Module *M, const PreservedAnalyses &PA);
666 /// \brief Map type from module analysis pass ID to pass result concept pointer.
667 typedef DenseMap<void *,
668 std::unique_ptr<detail::AnalysisResultConcept<Module *>>>
669 ModuleAnalysisResultMapT;
671 /// \brief Cache of computed module analysis results for this module.
672 ModuleAnalysisResultMapT ModuleAnalysisResults;
675 /// \brief A function analysis manager to coordinate and cache analyses run over
677 class FunctionAnalysisManager
678 : public detail::AnalysisManagerBase<FunctionAnalysisManager, Function *> {
679 friend class detail::AnalysisManagerBase<FunctionAnalysisManager, Function *>;
680 typedef detail::AnalysisManagerBase<FunctionAnalysisManager, Function *> BaseT;
681 typedef BaseT::ResultConceptT ResultConceptT;
682 typedef BaseT::PassConceptT PassConceptT;
685 // Most public APIs are inherited from the CRTP base class.
687 FunctionAnalysisManager() {}
688 FunctionAnalysisManager(FunctionAnalysisManager &&Arg)
689 : BaseT(std::move(static_cast<BaseT &>(Arg))),
690 FunctionAnalysisResults(std::move(Arg.FunctionAnalysisResults)) {}
691 FunctionAnalysisManager &operator=(FunctionAnalysisManager &&RHS) {
692 BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
693 FunctionAnalysisResults = std::move(RHS.FunctionAnalysisResults);
697 /// \brief Returns true if the analysis manager has an empty results cache.
700 /// \brief Clear the function analysis result cache.
702 /// This routine allows cleaning up when the set of functions itself has
703 /// potentially changed, and thus we can't even look up a a result and
704 /// invalidate it directly. Notably, this does *not* call invalidate
705 /// functions as there is nothing to be done for them.
709 FunctionAnalysisManager(const FunctionAnalysisManager &) LLVM_DELETED_FUNCTION;
710 FunctionAnalysisManager &
711 operator=(const FunctionAnalysisManager &) LLVM_DELETED_FUNCTION;
713 /// \brief Get a function pass result, running the pass if necessary.
714 ResultConceptT &getResultImpl(void *PassID, Function *F);
716 /// \brief Get a cached function pass result or return null.
717 ResultConceptT *getCachedResultImpl(void *PassID, Function *F) const;
719 /// \brief Invalidate a function pass result.
720 void invalidateImpl(void *PassID, Function *F);
722 /// \brief Invalidate the results for a function..
723 void invalidateImpl(Function *F, const PreservedAnalyses &PA);
725 /// \brief List of function analysis pass IDs and associated concept pointers.
727 /// Requires iterators to be valid across appending new entries and arbitrary
728 /// erases. Provides both the pass ID and concept pointer such that it is
729 /// half of a bijection and provides storage for the actual result concept.
730 typedef std::list<std::pair<
731 void *, std::unique_ptr<detail::AnalysisResultConcept<Function *>>>>
732 FunctionAnalysisResultListT;
734 /// \brief Map type from function pointer to our custom list type.
735 typedef DenseMap<Function *, FunctionAnalysisResultListT>
736 FunctionAnalysisResultListMapT;
738 /// \brief Map from function to a list of function analysis results.
740 /// Provides linear time removal of all analysis results for a function and
741 /// the ultimate storage for a particular cached analysis result.
742 FunctionAnalysisResultListMapT FunctionAnalysisResultLists;
744 /// \brief Map type from a pair of analysis ID and function pointer to an
745 /// iterator into a particular result list.
746 typedef DenseMap<std::pair<void *, Function *>,
747 FunctionAnalysisResultListT::iterator>
748 FunctionAnalysisResultMapT;
750 /// \brief Map from an analysis ID and function to a particular cached
752 FunctionAnalysisResultMapT FunctionAnalysisResults;
755 /// \brief A module analysis which acts as a proxy for a function analysis
758 /// This primarily proxies invalidation information from the module analysis
759 /// manager and module pass manager to a function analysis manager. You should
760 /// never use a function analysis manager from within (transitively) a module
761 /// pass manager unless your parent module pass has received a proxy result
763 class FunctionAnalysisManagerModuleProxy {
767 static void *ID() { return (void *)&PassID; }
769 explicit FunctionAnalysisManagerModuleProxy(FunctionAnalysisManager &FAM)
771 FunctionAnalysisManagerModuleProxy(
772 const FunctionAnalysisManagerModuleProxy &Arg)
774 FunctionAnalysisManagerModuleProxy(FunctionAnalysisManagerModuleProxy &&Arg)
776 FunctionAnalysisManagerModuleProxy &
777 operator=(FunctionAnalysisManagerModuleProxy RHS) {
778 std::swap(*this, RHS);
782 /// \brief Run the analysis pass and create our proxy result object.
784 /// This doesn't do any interesting work, it is primarily used to insert our
785 /// proxy result object into the module analysis cache so that we can proxy
786 /// invalidation to the function analysis manager.
788 /// In debug builds, it will also assert that the analysis manager is empty
789 /// as no queries should arrive at the function analysis manager prior to
790 /// this analysis being requested.
791 Result run(Module *M);
796 FunctionAnalysisManager &FAM;
799 /// \brief The result proxy object for the
800 /// \c FunctionAnalysisManagerModuleProxy.
802 /// See its documentation for more information.
803 class FunctionAnalysisManagerModuleProxy::Result {
805 explicit Result(FunctionAnalysisManager &FAM) : FAM(FAM) {}
806 Result(const Result &Arg) : FAM(Arg.FAM) {}
807 Result(Result &&Arg) : FAM(Arg.FAM) {}
808 Result &operator=(Result RHS) {
809 std::swap(*this, RHS);
814 /// \brief Accessor for the \c FunctionAnalysisManager.
815 FunctionAnalysisManager &getManager() { return FAM; }
817 /// \brief Handler for invalidation of the module.
819 /// If this analysis itself is preserved, then we assume that the set of \c
820 /// Function objects in the \c Module hasn't changed and thus we don't need
821 /// to invalidate *all* cached data associated with a \c Function* in the \c
822 /// FunctionAnalysisManager.
824 /// Regardless of whether this analysis is marked as preserved, all of the
825 /// analyses in the \c FunctionAnalysisManager are potentially invalidated
826 /// based on the set of preserved analyses.
827 bool invalidate(Module *M, const PreservedAnalyses &PA);
830 FunctionAnalysisManager &FAM;
833 /// \brief A function analysis which acts as a proxy for a module analysis
836 /// This primarily provides an accessor to a parent module analysis manager to
837 /// function passes. Only the const interface of the module analysis manager is
838 /// provided to indicate that once inside of a function analysis pass you
839 /// cannot request a module analysis to actually run. Instead, the user must
840 /// rely on the \c getCachedResult API.
842 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
843 /// the recursive return path of each layer of the pass manager and the
844 /// returned PreservedAnalysis set.
845 class ModuleAnalysisManagerFunctionProxy {
847 /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
850 explicit Result(const ModuleAnalysisManager &MAM) : MAM(MAM) {}
851 Result(const Result &Arg) : MAM(Arg.MAM) {}
852 Result(Result &&Arg) : MAM(Arg.MAM) {}
853 Result &operator=(Result RHS) {
854 std::swap(*this, RHS);
858 const ModuleAnalysisManager &getManager() const { return MAM; }
860 /// \brief Handle invalidation by ignoring it, this pass is immutable.
861 bool invalidate(Function *) { return false; }
864 const ModuleAnalysisManager &MAM;
867 static void *ID() { return (void *)&PassID; }
869 ModuleAnalysisManagerFunctionProxy(const ModuleAnalysisManager &MAM)
872 /// \brief Run the analysis pass and create our proxy result object.
873 /// Nothing to see here, it just forwards the \c MAM reference into the
875 Result run(Function *) { return Result(MAM); }
880 const ModuleAnalysisManager &MAM;
883 /// \brief Trivial adaptor that maps from a module to its functions.
885 /// Designed to allow composition of a FunctionPass(Manager) and
886 /// a ModulePassManager. Note that if this pass is constructed with a pointer
887 /// to a \c ModuleAnalysisManager it will run the
888 /// \c FunctionAnalysisManagerModuleProxy analysis prior to running the function
889 /// pass over the module to enable a \c FunctionAnalysisManager to be used
890 /// within this run safely.
891 template <typename FunctionPassT>
892 class ModuleToFunctionPassAdaptor {
894 explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
895 : Pass(std::move(Pass)) {}
896 ModuleToFunctionPassAdaptor(const ModuleToFunctionPassAdaptor &Arg)
898 ModuleToFunctionPassAdaptor(ModuleToFunctionPassAdaptor &&Arg)
899 : Pass(std::move(Arg.Pass)) {}
900 ModuleToFunctionPassAdaptor &operator=(ModuleToFunctionPassAdaptor RHS) {
901 std::swap(*this, RHS);
905 /// \brief Runs the function pass across every function in the module.
906 PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) {
907 FunctionAnalysisManager *FAM = 0;
909 // Setup the function analysis manager from its proxy.
910 FAM = &AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
912 PreservedAnalyses PA = PreservedAnalyses::all();
913 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
914 PreservedAnalyses PassPA = Pass.run(I, FAM);
916 // We know that the function pass couldn't have invalidated any other
917 // function's analyses (that's the contract of a function pass), so
918 // directly handle the function analysis manager's invalidation here.
920 FAM->invalidate(I, PassPA);
922 // Then intersect the preserved set so that invalidation of module
923 // analyses will eventually occur when the module pass completes.
924 PA.intersect(std::move(PassPA));
927 // By definition we preserve the proxy. This precludes *any* invalidation
928 // of function analyses by the proxy, but that's OK because we've taken
929 // care to invalidate analyses in the function analysis manager
930 // incrementally above.
931 PA.preserve<FunctionAnalysisManagerModuleProxy>();
935 static StringRef name() { return "ModuleToFunctionPassAdaptor"; }
941 /// \brief A function to deduce a function pass type and wrap it in the
942 /// templated adaptor.
943 template <typename FunctionPassT>
944 ModuleToFunctionPassAdaptor<FunctionPassT>
945 createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
946 return std::move(ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));