[PM] Fix a pretty nasty bug where the new pass manager would invalidate
[oota-llvm.git] / include / llvm / IR / PassManager.h
1 //===- PassManager.h - Pass management infrastructure -----------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
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.
20 ///
21 /// The core IR library provides managers for running passes over
22 /// modules and functions.
23 ///
24 /// * FunctionPassManager can run over a Module, runs each pass over
25 ///   a Function.
26 /// * ModulePassManager must be directly run, runs each pass over the Module.
27 ///
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
35 ///
36 //===----------------------------------------------------------------------===//
37
38 #ifndef LLVM_IR_PASSMANAGER_H
39 #define LLVM_IR_PASSMANAGER_H
40
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/IR/PassManagerInternal.h"
47 #include "llvm/Support/type_traits.h"
48 #include <list>
49 #include <memory>
50 #include <vector>
51
52 namespace llvm {
53
54 class Module;
55 class Function;
56
57 /// \brief An abstract set of preserved analyses following a transformation pass
58 /// run.
59 ///
60 /// When a transformation pass is run, it can return a set of analyses whose
61 /// results were preserved by that transformation. The default set is "none",
62 /// and preserving analyses must be done explicitly.
63 ///
64 /// There is also an explicit all state which can be used (for example) when
65 /// the IR is not mutated at all.
66 class PreservedAnalyses {
67 public:
68   // We have to explicitly define all the special member functions because MSVC
69   // refuses to generate them.
70   PreservedAnalyses() {}
71   PreservedAnalyses(const PreservedAnalyses &Arg)
72       : PreservedPassIDs(Arg.PreservedPassIDs) {}
73   PreservedAnalyses(PreservedAnalyses &&Arg)
74       : PreservedPassIDs(std::move(Arg.PreservedPassIDs)) {}
75   friend void swap(PreservedAnalyses &LHS, PreservedAnalyses &RHS) {
76     using std::swap;
77     swap(LHS.PreservedPassIDs, RHS.PreservedPassIDs);
78   }
79   PreservedAnalyses &operator=(PreservedAnalyses RHS) {
80     swap(*this, RHS);
81     return *this;
82   }
83
84   /// \brief Convenience factory function for the empty preserved set.
85   static PreservedAnalyses none() { return PreservedAnalyses(); }
86
87   /// \brief Construct a special preserved set that preserves all passes.
88   static PreservedAnalyses all() {
89     PreservedAnalyses PA;
90     PA.PreservedPassIDs.insert((void *)AllPassesID);
91     return PA;
92   }
93
94   /// \brief Mark a particular pass as preserved, adding it to the set.
95   template <typename PassT> void preserve() { preserve(PassT::ID()); }
96
97   /// \brief Mark an abstract PassID as preserved, adding it to the set.
98   void preserve(void *PassID) {
99     if (!areAllPreserved())
100       PreservedPassIDs.insert(PassID);
101   }
102
103   /// \brief Intersect this set with another in place.
104   ///
105   /// This is a mutating operation on this preserved set, removing all
106   /// preserved passes which are not also preserved in the argument.
107   void intersect(const PreservedAnalyses &Arg) {
108     if (Arg.areAllPreserved())
109       return;
110     if (areAllPreserved()) {
111       PreservedPassIDs = Arg.PreservedPassIDs;
112       return;
113     }
114     for (void *P : PreservedPassIDs)
115       if (!Arg.PreservedPassIDs.count(P))
116         PreservedPassIDs.erase(P);
117   }
118
119   /// \brief Intersect this set with a temporary other set in place.
120   ///
121   /// This is a mutating operation on this preserved set, removing all
122   /// preserved passes which are not also preserved in the argument.
123   void intersect(PreservedAnalyses &&Arg) {
124     if (Arg.areAllPreserved())
125       return;
126     if (areAllPreserved()) {
127       PreservedPassIDs = std::move(Arg.PreservedPassIDs);
128       return;
129     }
130     for (void *P : PreservedPassIDs)
131       if (!Arg.PreservedPassIDs.count(P))
132         PreservedPassIDs.erase(P);
133   }
134
135   /// \brief Query whether a pass is marked as preserved by this set.
136   template <typename PassT> bool preserved() const {
137     return preserved(PassT::ID());
138   }
139
140   /// \brief Query whether an abstract pass ID is marked as preserved by this
141   /// set.
142   bool preserved(void *PassID) const {
143     return PreservedPassIDs.count((void *)AllPassesID) ||
144            PreservedPassIDs.count(PassID);
145   }
146
147   /// \brief Test whether all passes are preserved.
148   ///
149   /// This is used primarily to optimize for the case of no changes which will
150   /// common in many scenarios.
151   bool areAllPreserved() const {
152     return PreservedPassIDs.count((void *)AllPassesID);
153   }
154
155 private:
156   // Note that this must not be -1 or -2 as those are already used by the
157   // SmallPtrSet.
158   static const uintptr_t AllPassesID = (intptr_t)(-3);
159
160   SmallPtrSet<void *, 2> PreservedPassIDs;
161 };
162
163 // We define the pass managers prior to the analysis managers that they use.
164 class ModuleAnalysisManager;
165
166 /// \brief Manages a sequence of passes over Modules of IR.
167 ///
168 /// A module pass manager contains a sequence of module passes. It is also
169 /// itself a module pass. When it is run over a module of LLVM IR, it will
170 /// sequentially run each pass it contains over that module.
171 ///
172 /// If it is run with a \c ModuleAnalysisManager argument, it will propagate
173 /// that analysis manager to each pass it runs, as well as calling the analysis
174 /// manager's invalidation routine with the PreservedAnalyses of each pass it
175 /// runs.
176 ///
177 /// Module passes can rely on having exclusive access to the module they are
178 /// run over. No other threads will access that module, and they can mutate it
179 /// freely. However, they must not mutate other LLVM IR modules.
180 class ModulePassManager {
181 public:
182   // We have to explicitly define all the special member functions because MSVC
183   // refuses to generate them.
184   ModulePassManager() {}
185   ModulePassManager(ModulePassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
186   ModulePassManager &operator=(ModulePassManager &&RHS) {
187     Passes = std::move(RHS.Passes);
188     return *this;
189   }
190
191   /// \brief Run all of the module passes in this module pass manager over
192   /// a module.
193   ///
194   /// This method should only be called for a single module as there is the
195   /// expectation that the lifetime of a pass is bounded to that of a module.
196   PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM = nullptr);
197
198   template <typename ModulePassT> void addPass(ModulePassT Pass) {
199     Passes.emplace_back(new ModulePassModel<ModulePassT>(std::move(Pass)));
200   }
201
202   static StringRef name() { return "ModulePassManager"; }
203
204 private:
205   // Pull in the concept type and model template specialized for modules.
206   typedef detail::PassConcept<Module &, ModuleAnalysisManager>
207       ModulePassConcept;
208   template <typename PassT>
209   struct ModulePassModel
210       : detail::PassModel<Module &, ModuleAnalysisManager, PassT> {
211     ModulePassModel(PassT Pass)
212         : detail::PassModel<Module &, ModuleAnalysisManager, PassT>(
213               std::move(Pass)) {}
214   };
215
216   ModulePassManager(const ModulePassManager &) LLVM_DELETED_FUNCTION;
217   ModulePassManager &operator=(const ModulePassManager &) LLVM_DELETED_FUNCTION;
218
219   std::vector<std::unique_ptr<ModulePassConcept>> Passes;
220 };
221
222 // We define the pass managers prior to the analysis managers that they use.
223 class FunctionAnalysisManager;
224
225 /// \brief Manages a sequence of passes over a Function of IR.
226 ///
227 /// A function pass manager contains a sequence of function passes. It is also
228 /// itself a function pass. When it is run over a function of LLVM IR, it will
229 /// sequentially run each pass it contains over that function.
230 ///
231 /// If it is run with a \c FunctionAnalysisManager argument, it will propagate
232 /// that analysis manager to each pass it runs, as well as calling the analysis
233 /// manager's invalidation routine with the PreservedAnalyses of each pass it
234 /// runs.
235 ///
236 /// Function passes can rely on having exclusive access to the function they
237 /// are run over. They should not read or modify any other functions! Other
238 /// threads or systems may be manipulating other functions in the module, and
239 /// so their state should never be relied on.
240 /// FIXME: Make the above true for all of LLVM's actual passes, some still
241 /// violate this principle.
242 ///
243 /// Function passes can also read the module containing the function, but they
244 /// should not modify that module outside of the use lists of various globals.
245 /// For example, a function pass is not permitted to add functions to the
246 /// module.
247 /// FIXME: Make the above true for all of LLVM's actual passes, some still
248 /// violate this principle.
249 class FunctionPassManager {
250 public:
251   // We have to explicitly define all the special member functions because MSVC
252   // refuses to generate them.
253   FunctionPassManager() {}
254   FunctionPassManager(FunctionPassManager &&Arg)
255       : Passes(std::move(Arg.Passes)) {}
256   FunctionPassManager &operator=(FunctionPassManager &&RHS) {
257     Passes = std::move(RHS.Passes);
258     return *this;
259   }
260
261   template <typename FunctionPassT> void addPass(FunctionPassT Pass) {
262     Passes.emplace_back(new FunctionPassModel<FunctionPassT>(std::move(Pass)));
263   }
264
265   PreservedAnalyses run(Function &F, FunctionAnalysisManager *AM = nullptr);
266
267   static StringRef name() { return "FunctionPassManager"; }
268
269 private:
270   // Pull in the concept type and model template specialized for functions.
271   typedef detail::PassConcept<Function &, FunctionAnalysisManager>
272       FunctionPassConcept;
273   template <typename PassT>
274   struct FunctionPassModel
275       : detail::PassModel<Function &, FunctionAnalysisManager, PassT> {
276     FunctionPassModel(PassT Pass)
277         : detail::PassModel<Function &, FunctionAnalysisManager, PassT>(
278               std::move(Pass)) {}
279   };
280
281   FunctionPassManager(const FunctionPassManager &) LLVM_DELETED_FUNCTION;
282   FunctionPassManager &
283   operator=(const FunctionPassManager &) LLVM_DELETED_FUNCTION;
284
285   std::vector<std::unique_ptr<FunctionPassConcept>> Passes;
286 };
287
288 namespace detail {
289
290 /// \brief A CRTP base used to implement analysis managers.
291 ///
292 /// This class template serves as the boiler plate of an analysis manager. Any
293 /// analysis manager can be implemented on top of this base class. Any
294 /// implementation will be required to provide specific hooks:
295 ///
296 /// - getResultImpl
297 /// - getCachedResultImpl
298 /// - invalidateImpl
299 ///
300 /// The details of the call pattern are within.
301 template <typename DerivedT, typename IRUnitT> class AnalysisManagerBase {
302   DerivedT *derived_this() { return static_cast<DerivedT *>(this); }
303   const DerivedT *derived_this() const {
304     return static_cast<const DerivedT *>(this);
305   }
306
307   AnalysisManagerBase(const AnalysisManagerBase &) LLVM_DELETED_FUNCTION;
308   AnalysisManagerBase &
309   operator=(const AnalysisManagerBase &) LLVM_DELETED_FUNCTION;
310
311 protected:
312   typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT;
313   typedef detail::AnalysisPassConcept<IRUnitT, DerivedT> PassConceptT;
314
315   // FIXME: Provide template aliases for the models when we're using C++11 in
316   // a mode supporting them.
317
318   // We have to explicitly define all the special member functions because MSVC
319   // refuses to generate them.
320   AnalysisManagerBase() {}
321   AnalysisManagerBase(AnalysisManagerBase &&Arg)
322       : AnalysisPasses(std::move(Arg.AnalysisPasses)) {}
323   AnalysisManagerBase &operator=(AnalysisManagerBase &&RHS) {
324     AnalysisPasses = std::move(RHS.AnalysisPasses);
325     return *this;
326   }
327
328 public:
329   /// \brief Get the result of an analysis pass for this module.
330   ///
331   /// If there is not a valid cached result in the manager already, this will
332   /// re-run the analysis to produce a valid result.
333   template <typename PassT> typename PassT::Result &getResult(IRUnitT IR) {
334     assert(AnalysisPasses.count(PassT::ID()) &&
335            "This analysis pass was not registered prior to being queried");
336
337     ResultConceptT &ResultConcept =
338         derived_this()->getResultImpl(PassT::ID(), IR);
339     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
340         ResultModelT;
341     return static_cast<ResultModelT &>(ResultConcept).Result;
342   }
343
344   /// \brief Get the cached result of an analysis pass for this module.
345   ///
346   /// This method never runs the analysis.
347   ///
348   /// \returns null if there is no cached result.
349   template <typename PassT>
350   typename PassT::Result *getCachedResult(IRUnitT IR) const {
351     assert(AnalysisPasses.count(PassT::ID()) &&
352            "This analysis pass was not registered prior to being queried");
353
354     ResultConceptT *ResultConcept =
355         derived_this()->getCachedResultImpl(PassT::ID(), IR);
356     if (!ResultConcept)
357       return nullptr;
358
359     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
360         ResultModelT;
361     return &static_cast<ResultModelT *>(ResultConcept)->Result;
362   }
363
364   /// \brief Register an analysis pass with the manager.
365   ///
366   /// This provides an initialized and set-up analysis pass to the analysis
367   /// manager. Whomever is setting up analysis passes must use this to populate
368   /// the manager with all of the analysis passes available.
369   template <typename PassT> void registerPass(PassT Pass) {
370     assert(!AnalysisPasses.count(PassT::ID()) &&
371            "Registered the same analysis pass twice!");
372     typedef detail::AnalysisPassModel<IRUnitT, DerivedT, PassT> PassModelT;
373     AnalysisPasses[PassT::ID()].reset(new PassModelT(std::move(Pass)));
374   }
375
376   /// \brief Invalidate a specific analysis pass for an IR module.
377   ///
378   /// Note that the analysis result can disregard invalidation.
379   template <typename PassT> void invalidate(IRUnitT IR) {
380     assert(AnalysisPasses.count(PassT::ID()) &&
381            "This analysis pass was not registered prior to being invalidated");
382     derived_this()->invalidateImpl(PassT::ID(), IR);
383   }
384
385   /// \brief Invalidate analyses cached for an IR unit.
386   ///
387   /// Walk through all of the analyses pertaining to this unit of IR and
388   /// invalidate them unless they are preserved by the PreservedAnalyses set.
389   /// We accept the PreservedAnalyses set by value and update it with each
390   /// analyis pass which has been successfully invalidated and thus can be
391   /// preserved going forward. The updated set is returned.
392   PreservedAnalyses invalidate(IRUnitT IR, PreservedAnalyses PA) {
393     return derived_this()->invalidateImpl(IR, std::move(PA));
394   }
395
396 protected:
397   /// \brief Lookup a registered analysis pass.
398   PassConceptT &lookupPass(void *PassID) {
399     typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(PassID);
400     assert(PI != AnalysisPasses.end() &&
401            "Analysis passes must be registered prior to being queried!");
402     return *PI->second;
403   }
404
405   /// \brief Lookup a registered analysis pass.
406   const PassConceptT &lookupPass(void *PassID) const {
407     typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(PassID);
408     assert(PI != AnalysisPasses.end() &&
409            "Analysis passes must be registered prior to being queried!");
410     return *PI->second;
411   }
412
413 private:
414   /// \brief Map type from module analysis pass ID to pass concept pointer.
415   typedef DenseMap<void *, std::unique_ptr<PassConceptT>> AnalysisPassMapT;
416
417   /// \brief Collection of module analysis passes, indexed by ID.
418   AnalysisPassMapT AnalysisPasses;
419 };
420
421 } // End namespace detail
422
423 /// \brief A module analysis pass manager with lazy running and caching of
424 /// results.
425 class ModuleAnalysisManager
426     : public detail::AnalysisManagerBase<ModuleAnalysisManager, Module &> {
427   friend class detail::AnalysisManagerBase<ModuleAnalysisManager, Module &>;
428   typedef detail::AnalysisManagerBase<ModuleAnalysisManager, Module &> BaseT;
429   typedef BaseT::ResultConceptT ResultConceptT;
430   typedef BaseT::PassConceptT PassConceptT;
431
432 public:
433   // We have to explicitly define all the special member functions because MSVC
434   // refuses to generate them.
435   ModuleAnalysisManager() {}
436   ModuleAnalysisManager(ModuleAnalysisManager &&Arg)
437       : BaseT(std::move(static_cast<BaseT &>(Arg))),
438         ModuleAnalysisResults(std::move(Arg.ModuleAnalysisResults)) {}
439   ModuleAnalysisManager &operator=(ModuleAnalysisManager &&RHS) {
440     BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
441     ModuleAnalysisResults = std::move(RHS.ModuleAnalysisResults);
442     return *this;
443   }
444
445 private:
446   ModuleAnalysisManager(const ModuleAnalysisManager &) LLVM_DELETED_FUNCTION;
447   ModuleAnalysisManager &
448   operator=(const ModuleAnalysisManager &) LLVM_DELETED_FUNCTION;
449
450   /// \brief Get a module pass result, running the pass if necessary.
451   ResultConceptT &getResultImpl(void *PassID, Module &M);
452
453   /// \brief Get a cached module pass result or return null.
454   ResultConceptT *getCachedResultImpl(void *PassID, Module &M) const;
455
456   /// \brief Invalidate a module pass result.
457   void invalidateImpl(void *PassID, Module &M);
458
459   /// \brief Invalidate results across a module.
460   PreservedAnalyses invalidateImpl(Module &M, PreservedAnalyses PA);
461
462   /// \brief Map type from module analysis pass ID to pass result concept
463   /// pointer.
464   typedef DenseMap<void *,
465                    std::unique_ptr<detail::AnalysisResultConcept<Module &>>>
466       ModuleAnalysisResultMapT;
467
468   /// \brief Cache of computed module analysis results for this module.
469   ModuleAnalysisResultMapT ModuleAnalysisResults;
470 };
471
472 /// \brief A function analysis manager to coordinate and cache analyses run over
473 /// a module.
474 class FunctionAnalysisManager
475     : public detail::AnalysisManagerBase<FunctionAnalysisManager, Function &> {
476   friend class detail::AnalysisManagerBase<FunctionAnalysisManager, Function &>;
477   typedef detail::AnalysisManagerBase<FunctionAnalysisManager, Function &>
478       BaseT;
479   typedef BaseT::ResultConceptT ResultConceptT;
480   typedef BaseT::PassConceptT PassConceptT;
481
482 public:
483   // Most public APIs are inherited from the CRTP base class.
484
485   // We have to explicitly define all the special member functions because MSVC
486   // refuses to generate them.
487   FunctionAnalysisManager() {}
488   FunctionAnalysisManager(FunctionAnalysisManager &&Arg)
489       : BaseT(std::move(static_cast<BaseT &>(Arg))),
490         FunctionAnalysisResults(std::move(Arg.FunctionAnalysisResults)) {}
491   FunctionAnalysisManager &operator=(FunctionAnalysisManager &&RHS) {
492     BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
493     FunctionAnalysisResults = std::move(RHS.FunctionAnalysisResults);
494     return *this;
495   }
496
497   /// \brief Returns true if the analysis manager has an empty results cache.
498   bool empty() const;
499
500   /// \brief Clear the function analysis result cache.
501   ///
502   /// This routine allows cleaning up when the set of functions itself has
503   /// potentially changed, and thus we can't even look up a a result and
504   /// invalidate it directly. Notably, this does *not* call invalidate
505   /// functions as there is nothing to be done for them.
506   void clear();
507
508 private:
509   FunctionAnalysisManager(const FunctionAnalysisManager &)
510       LLVM_DELETED_FUNCTION;
511   FunctionAnalysisManager &
512   operator=(const FunctionAnalysisManager &) LLVM_DELETED_FUNCTION;
513
514   /// \brief Get a function pass result, running the pass if necessary.
515   ResultConceptT &getResultImpl(void *PassID, Function &F);
516
517   /// \brief Get a cached function pass result or return null.
518   ResultConceptT *getCachedResultImpl(void *PassID, Function &F) const;
519
520   /// \brief Invalidate a function pass result.
521   void invalidateImpl(void *PassID, Function &F);
522
523   /// \brief Invalidate the results for a function..
524   PreservedAnalyses invalidateImpl(Function &F, PreservedAnalyses PA);
525
526   /// \brief List of function analysis pass IDs and associated concept pointers.
527   ///
528   /// Requires iterators to be valid across appending new entries and arbitrary
529   /// erases. Provides both the pass ID and concept pointer such that it is
530   /// half of a bijection and provides storage for the actual result concept.
531   typedef std::list<std::pair<
532       void *, std::unique_ptr<detail::AnalysisResultConcept<Function &>>>>
533       FunctionAnalysisResultListT;
534
535   /// \brief Map type from function pointer to our custom list type.
536   typedef DenseMap<Function *, FunctionAnalysisResultListT>
537       FunctionAnalysisResultListMapT;
538
539   /// \brief Map from function to a list of function analysis results.
540   ///
541   /// Provides linear time removal of all analysis results for a function and
542   /// the ultimate storage for a particular cached analysis result.
543   FunctionAnalysisResultListMapT FunctionAnalysisResultLists;
544
545   /// \brief Map type from a pair of analysis ID and function pointer to an
546   /// iterator into a particular result list.
547   typedef DenseMap<std::pair<void *, Function *>,
548                    FunctionAnalysisResultListT::iterator>
549       FunctionAnalysisResultMapT;
550
551   /// \brief Map from an analysis ID and function to a particular cached
552   /// analysis result.
553   FunctionAnalysisResultMapT FunctionAnalysisResults;
554 };
555
556 /// \brief A module analysis which acts as a proxy for a function analysis
557 /// manager.
558 ///
559 /// This primarily proxies invalidation information from the module analysis
560 /// manager and module pass manager to a function analysis manager. You should
561 /// never use a function analysis manager from within (transitively) a module
562 /// pass manager unless your parent module pass has received a proxy result
563 /// object for it.
564 class FunctionAnalysisManagerModuleProxy {
565 public:
566   class Result;
567
568   static void *ID() { return (void *)&PassID; }
569
570   static StringRef name() { return "FunctionAnalysisManagerModuleProxy"; }
571
572   explicit FunctionAnalysisManagerModuleProxy(FunctionAnalysisManager &FAM)
573       : FAM(&FAM) {}
574   // We have to explicitly define all the special member functions because MSVC
575   // refuses to generate them.
576   FunctionAnalysisManagerModuleProxy(
577       const FunctionAnalysisManagerModuleProxy &Arg)
578       : FAM(Arg.FAM) {}
579   FunctionAnalysisManagerModuleProxy(FunctionAnalysisManagerModuleProxy &&Arg)
580       : FAM(std::move(Arg.FAM)) {}
581   FunctionAnalysisManagerModuleProxy &
582   operator=(FunctionAnalysisManagerModuleProxy RHS) {
583     std::swap(FAM, RHS.FAM);
584     return *this;
585   }
586
587   /// \brief Run the analysis pass and create our proxy result object.
588   ///
589   /// This doesn't do any interesting work, it is primarily used to insert our
590   /// proxy result object into the module analysis cache so that we can proxy
591   /// invalidation to the function analysis manager.
592   ///
593   /// In debug builds, it will also assert that the analysis manager is empty
594   /// as no queries should arrive at the function analysis manager prior to
595   /// this analysis being requested.
596   Result run(Module &M);
597
598 private:
599   static char PassID;
600
601   FunctionAnalysisManager *FAM;
602 };
603
604 /// \brief The result proxy object for the
605 /// \c FunctionAnalysisManagerModuleProxy.
606 ///
607 /// See its documentation for more information.
608 class FunctionAnalysisManagerModuleProxy::Result {
609 public:
610   explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
611   // We have to explicitly define all the special member functions because MSVC
612   // refuses to generate them.
613   Result(const Result &Arg) : FAM(Arg.FAM) {}
614   Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
615   Result &operator=(Result RHS) {
616     std::swap(FAM, RHS.FAM);
617     return *this;
618   }
619   ~Result();
620
621   /// \brief Accessor for the \c FunctionAnalysisManager.
622   FunctionAnalysisManager &getManager() { return *FAM; }
623
624   /// \brief Handler for invalidation of the module.
625   ///
626   /// If this analysis itself is preserved, then we assume that the set of \c
627   /// Function objects in the \c Module hasn't changed and thus we don't need
628   /// to invalidate *all* cached data associated with a \c Function* in the \c
629   /// FunctionAnalysisManager.
630   ///
631   /// Regardless of whether this analysis is marked as preserved, all of the
632   /// analyses in the \c FunctionAnalysisManager are potentially invalidated
633   /// based on the set of preserved analyses.
634   bool invalidate(Module &M, const PreservedAnalyses &PA);
635
636 private:
637   FunctionAnalysisManager *FAM;
638 };
639
640 /// \brief A function analysis which acts as a proxy for a module analysis
641 /// manager.
642 ///
643 /// This primarily provides an accessor to a parent module analysis manager to
644 /// function passes. Only the const interface of the module analysis manager is
645 /// provided to indicate that once inside of a function analysis pass you
646 /// cannot request a module analysis to actually run. Instead, the user must
647 /// rely on the \c getCachedResult API.
648 ///
649 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
650 /// the recursive return path of each layer of the pass manager and the
651 /// returned PreservedAnalysis set.
652 class ModuleAnalysisManagerFunctionProxy {
653 public:
654   /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
655   class Result {
656   public:
657     explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
658     // We have to explicitly define all the special member functions because
659     // MSVC refuses to generate them.
660     Result(const Result &Arg) : MAM(Arg.MAM) {}
661     Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
662     Result &operator=(Result RHS) {
663       std::swap(MAM, RHS.MAM);
664       return *this;
665     }
666
667     const ModuleAnalysisManager &getManager() const { return *MAM; }
668
669     /// \brief Handle invalidation by ignoring it, this pass is immutable.
670     bool invalidate(Function &) { return false; }
671
672   private:
673     const ModuleAnalysisManager *MAM;
674   };
675
676   static void *ID() { return (void *)&PassID; }
677
678   static StringRef name() { return "ModuleAnalysisManagerFunctionProxy"; }
679
680   ModuleAnalysisManagerFunctionProxy(const ModuleAnalysisManager &MAM)
681       : MAM(&MAM) {}
682   // We have to explicitly define all the special member functions because MSVC
683   // refuses to generate them.
684   ModuleAnalysisManagerFunctionProxy(
685       const ModuleAnalysisManagerFunctionProxy &Arg)
686       : MAM(Arg.MAM) {}
687   ModuleAnalysisManagerFunctionProxy(ModuleAnalysisManagerFunctionProxy &&Arg)
688       : MAM(std::move(Arg.MAM)) {}
689   ModuleAnalysisManagerFunctionProxy &
690   operator=(ModuleAnalysisManagerFunctionProxy RHS) {
691     std::swap(MAM, RHS.MAM);
692     return *this;
693   }
694
695   /// \brief Run the analysis pass and create our proxy result object.
696   /// Nothing to see here, it just forwards the \c MAM reference into the
697   /// result.
698   Result run(Function &) { return Result(*MAM); }
699
700 private:
701   static char PassID;
702
703   const ModuleAnalysisManager *MAM;
704 };
705
706 /// \brief Trivial adaptor that maps from a module to its functions.
707 ///
708 /// Designed to allow composition of a FunctionPass(Manager) and
709 /// a ModulePassManager. Note that if this pass is constructed with a pointer
710 /// to a \c ModuleAnalysisManager it will run the
711 /// \c FunctionAnalysisManagerModuleProxy analysis prior to running the function
712 /// pass over the module to enable a \c FunctionAnalysisManager to be used
713 /// within this run safely.
714 template <typename FunctionPassT> class ModuleToFunctionPassAdaptor {
715 public:
716   explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
717       : Pass(std::move(Pass)) {}
718   // We have to explicitly define all the special member functions because MSVC
719   // refuses to generate them.
720   ModuleToFunctionPassAdaptor(const ModuleToFunctionPassAdaptor &Arg)
721       : Pass(Arg.Pass) {}
722   ModuleToFunctionPassAdaptor(ModuleToFunctionPassAdaptor &&Arg)
723       : Pass(std::move(Arg.Pass)) {}
724   friend void swap(ModuleToFunctionPassAdaptor &LHS,
725                    ModuleToFunctionPassAdaptor &RHS) {
726     using std::swap;
727     swap(LHS.Pass, RHS.Pass);
728   }
729   ModuleToFunctionPassAdaptor &operator=(ModuleToFunctionPassAdaptor RHS) {
730     swap(*this, RHS);
731     return *this;
732   }
733
734   /// \brief Runs the function pass across every function in the module.
735   PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) {
736     FunctionAnalysisManager *FAM = nullptr;
737     if (AM)
738       // Setup the function analysis manager from its proxy.
739       FAM = &AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
740
741     PreservedAnalyses PA = PreservedAnalyses::all();
742     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
743       PreservedAnalyses PassPA = Pass.run(*I, FAM);
744
745       // We know that the function pass couldn't have invalidated any other
746       // function's analyses (that's the contract of a function pass), so
747       // directly handle the function analysis manager's invalidation here and
748       // update our preserved set to reflect that these have already been
749       // handled.
750       if (FAM)
751         PassPA = FAM->invalidate(*I, std::move(PassPA));
752
753       // Then intersect the preserved set so that invalidation of module
754       // analyses will eventually occur when the module pass completes.
755       PA.intersect(std::move(PassPA));
756     }
757
758     // By definition we preserve the proxy. This precludes *any* invalidation
759     // of function analyses by the proxy, but that's OK because we've taken
760     // care to invalidate analyses in the function analysis manager
761     // incrementally above.
762     PA.preserve<FunctionAnalysisManagerModuleProxy>();
763     return PA;
764   }
765
766   static StringRef name() { return "ModuleToFunctionPassAdaptor"; }
767
768 private:
769   FunctionPassT Pass;
770 };
771
772 /// \brief A function to deduce a function pass type and wrap it in the
773 /// templated adaptor.
774 template <typename FunctionPassT>
775 ModuleToFunctionPassAdaptor<FunctionPassT>
776 createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
777   return std::move(ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));
778 }
779
780 /// \brief A template utility pass to force an analysis result to be available.
781 ///
782 /// This is a no-op pass which simply forces a specific analysis pass's result
783 /// to be available when it is run.
784 template <typename AnalysisT> struct NoopAnalysisRequirementPass {
785   /// \brief Run this pass over some unit of IR.
786   ///
787   /// This pass can be run over any unit of IR and use any analysis manager
788   /// provided they satisfy the basic API requirements. When this pass is
789   /// created, these methods can be instantiated to satisfy whatever the
790   /// context requires.
791   template <typename T, typename AnalysisManagerT>
792   PreservedAnalyses run(T &&Arg, AnalysisManagerT *AM) {
793     if (AM)
794       (void)AM->template getResult<AnalysisT>(std::forward<T>(Arg));
795
796     return PreservedAnalyses::all();
797   }
798
799   static StringRef name() { return "No-op Analysis Requirement Pass"; }
800 };
801
802 /// \brief A template utility pass to force an analysis result to be
803 /// invalidated.
804 ///
805 /// This is a no-op pass which simply forces a specific analysis result to be
806 /// invalidated when it is run.
807 template <typename AnalysisT> struct NoopAnalysisInvalidationPass {
808   /// \brief Run this pass over some unit of IR.
809   ///
810   /// This pass can be run over any unit of IR and use any analysis manager
811   /// provided they satisfy the basic API requirements. When this pass is
812   /// created, these methods can be instantiated to satisfy whatever the
813   /// context requires.
814   template <typename T, typename AnalysisManagerT>
815   PreservedAnalyses run(T &&Arg, AnalysisManagerT *AM) {
816     if (AM)
817       // We have to directly invalidate the analysis result as we can't
818       // enumerate all other analyses and use the preserved set to control it.
819       (void)AM->template invalidate<AnalysisT>(std::forward<T>(Arg));
820
821     return PreservedAnalyses::all();
822   }
823
824   static StringRef name() { return "No-op Analysis Invalidation Pass"; }
825 };
826
827 /// \brief A utility pass that does nothing but preserves no analyses.
828 ///
829 /// As a consequence fo not preserving any analyses, this pass will force all
830 /// analysis passes to be re-run to produce fresh results if any are needed.
831 struct InvalidateAllAnalysesPass {
832   /// \brief Run this pass over some unit of IR.
833   template <typename T>
834   PreservedAnalyses run(T &&Arg) {
835     return PreservedAnalyses::none();
836   }
837
838   static StringRef name() { return "InvalidateAllAnalysesPass"; }
839 };
840
841 }
842
843 #endif