Canonicalize header guards into a common format.
[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/Support/type_traits.h"
47 #include <list>
48 #include <memory>
49 #include <vector>
50
51 namespace llvm {
52
53 class Module;
54 class Function;
55
56 /// \brief An abstract set of preserved analyses following a transformation pass
57 /// run.
58 ///
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.
62 ///
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 {
66 public:
67   // We have to explicitly define all the special member functions because MSVC
68   // refuses to generate them.
69   PreservedAnalyses() {}
70   PreservedAnalyses(const PreservedAnalyses &Arg)
71       : PreservedPassIDs(Arg.PreservedPassIDs) {}
72   PreservedAnalyses(PreservedAnalyses &&Arg)
73       : PreservedPassIDs(std::move(Arg.PreservedPassIDs)) {}
74   friend void swap(PreservedAnalyses &LHS, PreservedAnalyses &RHS) {
75     using std::swap;
76     swap(LHS.PreservedPassIDs, RHS.PreservedPassIDs);
77   }
78   PreservedAnalyses &operator=(PreservedAnalyses RHS) {
79     swap(*this, RHS);
80     return *this;
81   }
82
83   /// \brief Convenience factory function for the empty preserved set.
84   static PreservedAnalyses none() { return PreservedAnalyses(); }
85
86   /// \brief Construct a special preserved set that preserves all passes.
87   static PreservedAnalyses all() {
88     PreservedAnalyses PA;
89     PA.PreservedPassIDs.insert((void *)AllPassesID);
90     return PA;
91   }
92
93   /// \brief Mark a particular pass as preserved, adding it to the set.
94   template <typename PassT> void preserve() {
95     if (!areAllPreserved())
96       PreservedPassIDs.insert(PassT::ID());
97   }
98
99   /// \brief Intersect this set with another in place.
100   ///
101   /// This is a mutating operation on this preserved set, removing all
102   /// preserved passes which are not also preserved in the argument.
103   void intersect(const PreservedAnalyses &Arg) {
104     if (Arg.areAllPreserved())
105       return;
106     if (areAllPreserved()) {
107       PreservedPassIDs = Arg.PreservedPassIDs;
108       return;
109     }
110     for (SmallPtrSet<void *, 2>::const_iterator I = PreservedPassIDs.begin(),
111                                                 E = PreservedPassIDs.end();
112          I != E; ++I)
113       if (!Arg.PreservedPassIDs.count(*I))
114         PreservedPassIDs.erase(*I);
115   }
116
117   /// \brief Intersect this set with a temporary other set in place.
118   ///
119   /// This is a mutating operation on this preserved set, removing all
120   /// preserved passes which are not also preserved in the argument.
121   void intersect(PreservedAnalyses &&Arg) {
122     if (Arg.areAllPreserved())
123       return;
124     if (areAllPreserved()) {
125       PreservedPassIDs = std::move(Arg.PreservedPassIDs);
126       return;
127     }
128     for (SmallPtrSet<void *, 2>::const_iterator I = PreservedPassIDs.begin(),
129                                                 E = PreservedPassIDs.end();
130          I != E; ++I)
131       if (!Arg.PreservedPassIDs.count(*I))
132         PreservedPassIDs.erase(*I);
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 private:
148   // Note that this must not be -1 or -2 as those are already used by the
149   // SmallPtrSet.
150   static const uintptr_t AllPassesID = (intptr_t)(-3);
151
152   bool areAllPreserved() const {
153     return PreservedPassIDs.count((void *)AllPassesID);
154   }
155
156   SmallPtrSet<void *, 2> PreservedPassIDs;
157 };
158
159 /// \brief Implementation details of the pass manager interfaces.
160 namespace detail {
161
162 /// \brief Template for the abstract base class used to dispatch
163 /// polymorphically over pass objects.
164 template <typename IRUnitT, typename AnalysisManagerT> struct PassConcept {
165   // Boiler plate necessary for the container of derived classes.
166   virtual ~PassConcept() {}
167
168   /// \brief The polymorphic API which runs the pass over a given IR entity.
169   ///
170   /// Note that actual pass object can omit the analysis manager argument if
171   /// desired. Also that the analysis manager may be null if there is no
172   /// analysis manager in the pass pipeline.
173   virtual PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) = 0;
174
175   /// \brief Polymorphic method to access the name of a pass.
176   virtual StringRef name() = 0;
177 };
178
179 /// \brief SFINAE metafunction for computing whether \c PassT has a run method
180 /// accepting an \c AnalysisManagerT.
181 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
182           typename ResultT>
183 class PassRunAcceptsAnalysisManager {
184   typedef char SmallType;
185   struct BigType {
186     char a, b;
187   };
188
189   template <typename T, ResultT (T::*)(IRUnitT, AnalysisManagerT *)>
190   struct Checker;
191
192   template <typename T> static SmallType f(Checker<T, &T::run> *);
193   template <typename T> static BigType f(...);
194
195 public:
196   enum { Value = sizeof(f<PassT>(nullptr)) == sizeof(SmallType) };
197 };
198
199 /// \brief A template wrapper used to implement the polymorphic API.
200 ///
201 /// Can be instantiated for any object which provides a \c run method accepting
202 /// an \c IRUnitT. It requires the pass to be a copyable object. When the
203 /// \c run method also accepts an \c AnalysisManagerT*, we pass it along.
204 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
205           bool AcceptsAnalysisManager = PassRunAcceptsAnalysisManager<
206               IRUnitT, AnalysisManagerT, PassT, PreservedAnalyses>::Value>
207 struct PassModel;
208
209 /// \brief Specialization of \c PassModel for passes that accept an analyis
210 /// manager.
211 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
212 struct PassModel<IRUnitT, AnalysisManagerT, PassT, true>
213     : PassConcept<IRUnitT, AnalysisManagerT> {
214   explicit PassModel(PassT Pass) : Pass(std::move(Pass)) {}
215   // We have to explicitly define all the special member functions because MSVC
216   // refuses to generate them.
217   PassModel(const PassModel &Arg) : Pass(Arg.Pass) {}
218   PassModel(PassModel &&Arg) : Pass(std::move(Arg.Pass)) {}
219   friend void swap(PassModel &LHS, PassModel &RHS) {
220     using std::swap;
221     swap(LHS.Pass, RHS.Pass);
222   }
223   PassModel &operator=(PassModel RHS) {
224     swap(*this, RHS);
225     return *this;
226   }
227
228   PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) override {
229     return Pass.run(IR, AM);
230   }
231   StringRef name() override { return PassT::name(); }
232   PassT Pass;
233 };
234
235 /// \brief Specialization of \c PassModel for passes that accept an analyis
236 /// manager.
237 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
238 struct PassModel<IRUnitT, AnalysisManagerT, PassT, false>
239     : PassConcept<IRUnitT, AnalysisManagerT> {
240   explicit PassModel(PassT Pass) : Pass(std::move(Pass)) {}
241   // We have to explicitly define all the special member functions because MSVC
242   // refuses to generate them.
243   PassModel(const PassModel &Arg) : Pass(Arg.Pass) {}
244   PassModel(PassModel &&Arg) : Pass(std::move(Arg.Pass)) {}
245   friend void swap(PassModel &LHS, PassModel &RHS) {
246     using std::swap;
247     swap(LHS.Pass, RHS.Pass);
248   }
249   PassModel &operator=(PassModel RHS) {
250     swap(*this, RHS);
251     return *this;
252   }
253
254   PreservedAnalyses run(IRUnitT IR, AnalysisManagerT *AM) override {
255     return Pass.run(IR);
256   }
257   StringRef name() override { return PassT::name(); }
258   PassT Pass;
259 };
260
261 /// \brief Abstract concept of an analysis result.
262 ///
263 /// This concept is parameterized over the IR unit that this result pertains
264 /// to.
265 template <typename IRUnitT> struct AnalysisResultConcept {
266   virtual ~AnalysisResultConcept() {}
267
268   /// \brief Method to try and mark a result as invalid.
269   ///
270   /// When the outer analysis manager detects a change in some underlying
271   /// unit of the IR, it will call this method on all of the results cached.
272   ///
273   /// This method also receives a set of preserved analyses which can be used
274   /// to avoid invalidation because the pass which changed the underlying IR
275   /// took care to update or preserve the analysis result in some way.
276   ///
277   /// \returns true if the result is indeed invalid (the default).
278   virtual bool invalidate(IRUnitT IR, const PreservedAnalyses &PA) = 0;
279 };
280
281 /// \brief SFINAE metafunction for computing whether \c ResultT provides an
282 /// \c invalidate member function.
283 template <typename IRUnitT, typename ResultT> class ResultHasInvalidateMethod {
284   typedef char SmallType;
285   struct BigType {
286     char a, b;
287   };
288
289   template <typename T, bool (T::*)(IRUnitT, const PreservedAnalyses &)>
290   struct Checker;
291
292   template <typename T> static SmallType f(Checker<T, &T::invalidate> *);
293   template <typename T> static BigType f(...);
294
295 public:
296   enum { Value = sizeof(f<ResultT>(nullptr)) == sizeof(SmallType) };
297 };
298
299 /// \brief Wrapper to model the analysis result concept.
300 ///
301 /// By default, this will implement the invalidate method with a trivial
302 /// implementation so that the actual analysis result doesn't need to provide
303 /// an invalidation handler. It is only selected when the invalidation handler
304 /// is not part of the ResultT's interface.
305 template <typename IRUnitT, typename PassT, typename ResultT,
306           bool HasInvalidateHandler =
307               ResultHasInvalidateMethod<IRUnitT, ResultT>::Value>
308 struct AnalysisResultModel;
309
310 /// \brief Specialization of \c AnalysisResultModel which provides the default
311 /// invalidate functionality.
312 template <typename IRUnitT, typename PassT, typename ResultT>
313 struct AnalysisResultModel<IRUnitT, PassT, ResultT, false>
314     : AnalysisResultConcept<IRUnitT> {
315   explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
316   // We have to explicitly define all the special member functions because MSVC
317   // refuses to generate them.
318   AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
319   AnalysisResultModel(AnalysisResultModel &&Arg)
320       : Result(std::move(Arg.Result)) {}
321   friend void swap(AnalysisResultModel &LHS, AnalysisResultModel &RHS) {
322     using std::swap;
323     swap(LHS.Result, RHS.Result);
324   }
325   AnalysisResultModel &operator=(AnalysisResultModel RHS) {
326     swap(*this, RHS);
327     return *this;
328   }
329
330   /// \brief The model bases invalidation solely on being in the preserved set.
331   //
332   // FIXME: We should actually use two different concepts for analysis results
333   // rather than two different models, and avoid the indirect function call for
334   // ones that use the trivial behavior.
335   bool invalidate(IRUnitT, const PreservedAnalyses &PA) override {
336     return !PA.preserved(PassT::ID());
337   }
338
339   ResultT Result;
340 };
341
342 /// \brief Specialization of \c AnalysisResultModel which delegates invalidate
343 /// handling to \c ResultT.
344 template <typename IRUnitT, typename PassT, typename ResultT>
345 struct AnalysisResultModel<IRUnitT, PassT, ResultT, true>
346     : AnalysisResultConcept<IRUnitT> {
347   explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
348   // We have to explicitly define all the special member functions because MSVC
349   // refuses to generate them.
350   AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
351   AnalysisResultModel(AnalysisResultModel &&Arg)
352       : Result(std::move(Arg.Result)) {}
353   friend void swap(AnalysisResultModel &LHS, AnalysisResultModel &RHS) {
354     using std::swap;
355     swap(LHS.Result, RHS.Result);
356   }
357   AnalysisResultModel &operator=(AnalysisResultModel RHS) {
358     swap(*this, RHS);
359     return *this;
360   }
361
362   /// \brief The model delegates to the \c ResultT method.
363   bool invalidate(IRUnitT IR, const PreservedAnalyses &PA) override {
364     return Result.invalidate(IR, PA);
365   }
366
367   ResultT Result;
368 };
369
370 /// \brief Abstract concept of an analysis pass.
371 ///
372 /// This concept is parameterized over the IR unit that it can run over and
373 /// produce an analysis result.
374 template <typename IRUnitT, typename AnalysisManagerT>
375 struct AnalysisPassConcept {
376   virtual ~AnalysisPassConcept() {}
377
378   /// \brief Method to run this analysis over a unit of IR.
379   /// \returns A unique_ptr to the analysis result object to be queried by
380   /// users.
381   virtual std::unique_ptr<AnalysisResultConcept<IRUnitT>>
382   run(IRUnitT IR, AnalysisManagerT *AM) = 0;
383 };
384
385 /// \brief Wrapper to model the analysis pass concept.
386 ///
387 /// Can wrap any type which implements a suitable \c run method. The method
388 /// must accept the IRUnitT as an argument and produce an object which can be
389 /// wrapped in a \c AnalysisResultModel.
390 template <typename IRUnitT, typename AnalysisManagerT, typename PassT,
391           bool AcceptsAnalysisManager = PassRunAcceptsAnalysisManager<
392               IRUnitT, AnalysisManagerT, PassT, typename PassT::Result>::Value>
393 struct AnalysisPassModel;
394
395 /// \brief Specialization of \c AnalysisPassModel which passes an
396 /// \c AnalysisManager to PassT's run method.
397 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
398 struct AnalysisPassModel<IRUnitT, AnalysisManagerT, PassT, true>
399     : AnalysisPassConcept<IRUnitT, AnalysisManagerT> {
400   explicit AnalysisPassModel(PassT Pass) : Pass(std::move(Pass)) {}
401   // We have to explicitly define all the special member functions because MSVC
402   // refuses to generate them.
403   AnalysisPassModel(const AnalysisPassModel &Arg) : Pass(Arg.Pass) {}
404   AnalysisPassModel(AnalysisPassModel &&Arg) : Pass(std::move(Arg.Pass)) {}
405   friend void swap(AnalysisPassModel &LHS, AnalysisPassModel &RHS) {
406     using std::swap;
407     swap(LHS.Pass, RHS.Pass);
408   }
409   AnalysisPassModel &operator=(AnalysisPassModel RHS) {
410     swap(*this, RHS);
411     return *this;
412   }
413
414   // FIXME: Replace PassT::Result with type traits when we use C++11.
415   typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
416       ResultModelT;
417
418   /// \brief The model delegates to the \c PassT::run method.
419   ///
420   /// The return is wrapped in an \c AnalysisResultModel.
421   std::unique_ptr<AnalysisResultConcept<IRUnitT>>
422   run(IRUnitT IR, AnalysisManagerT *AM) override {
423     return make_unique<ResultModelT>(Pass.run(IR, AM));
424   }
425
426   PassT Pass;
427 };
428
429 /// \brief Specialization of \c AnalysisPassModel which does not pass an
430 /// \c AnalysisManager to PassT's run method.
431 template <typename IRUnitT, typename AnalysisManagerT, typename PassT>
432 struct AnalysisPassModel<IRUnitT, AnalysisManagerT, PassT, false>
433     : AnalysisPassConcept<IRUnitT, AnalysisManagerT> {
434   explicit AnalysisPassModel(PassT Pass) : Pass(std::move(Pass)) {}
435   // We have to explicitly define all the special member functions because MSVC
436   // refuses to generate them.
437   AnalysisPassModel(const AnalysisPassModel &Arg) : Pass(Arg.Pass) {}
438   AnalysisPassModel(AnalysisPassModel &&Arg) : Pass(std::move(Arg.Pass)) {}
439   friend void swap(AnalysisPassModel &LHS, AnalysisPassModel &RHS) {
440     using std::swap;
441     swap(LHS.Pass, RHS.Pass);
442   }
443   AnalysisPassModel &operator=(AnalysisPassModel RHS) {
444     swap(*this, RHS);
445     return *this;
446   }
447
448   // FIXME: Replace PassT::Result with type traits when we use C++11.
449   typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
450       ResultModelT;
451
452   /// \brief The model delegates to the \c PassT::run method.
453   ///
454   /// The return is wrapped in an \c AnalysisResultModel.
455   std::unique_ptr<AnalysisResultConcept<IRUnitT>>
456   run(IRUnitT IR, AnalysisManagerT *) override {
457     return make_unique<ResultModelT>(Pass.run(IR));
458   }
459
460   PassT Pass;
461 };
462
463 } // End namespace detail
464
465 class ModuleAnalysisManager;
466
467 class ModulePassManager {
468 public:
469   // We have to explicitly define all the special member functions because MSVC
470   // refuses to generate them.
471   ModulePassManager() {}
472   ModulePassManager(ModulePassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
473   ModulePassManager &operator=(ModulePassManager &&RHS) {
474     Passes = std::move(RHS.Passes);
475     return *this;
476   }
477
478   /// \brief Run all of the module passes in this module pass manager over
479   /// a module.
480   ///
481   /// This method should only be called for a single module as there is the
482   /// expectation that the lifetime of a pass is bounded to that of a module.
483   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM = nullptr);
484
485   template <typename ModulePassT> void addPass(ModulePassT Pass) {
486     Passes.emplace_back(new ModulePassModel<ModulePassT>(std::move(Pass)));
487   }
488
489   static StringRef name() { return "ModulePassManager"; }
490
491 private:
492   // Pull in the concept type and model template specialized for modules.
493   typedef detail::PassConcept<Module *, ModuleAnalysisManager>
494   ModulePassConcept;
495   template <typename PassT>
496   struct ModulePassModel
497       : detail::PassModel<Module *, ModuleAnalysisManager, PassT> {
498     ModulePassModel(PassT Pass)
499         : detail::PassModel<Module *, ModuleAnalysisManager, PassT>(
500               std::move(Pass)) {}
501   };
502
503   ModulePassManager(const ModulePassManager &) LLVM_DELETED_FUNCTION;
504   ModulePassManager &operator=(const ModulePassManager &) LLVM_DELETED_FUNCTION;
505
506   std::vector<std::unique_ptr<ModulePassConcept>> Passes;
507 };
508
509 class FunctionAnalysisManager;
510
511 class FunctionPassManager {
512 public:
513   // We have to explicitly define all the special member functions because MSVC
514   // refuses to generate them.
515   FunctionPassManager() {}
516   FunctionPassManager(FunctionPassManager &&Arg)
517       : Passes(std::move(Arg.Passes)) {}
518   FunctionPassManager &operator=(FunctionPassManager &&RHS) {
519     Passes = std::move(RHS.Passes);
520     return *this;
521   }
522
523   template <typename FunctionPassT> void addPass(FunctionPassT Pass) {
524     Passes.emplace_back(new FunctionPassModel<FunctionPassT>(std::move(Pass)));
525   }
526
527   PreservedAnalyses run(Function *F, FunctionAnalysisManager *AM = nullptr);
528
529   static StringRef name() { return "FunctionPassManager"; }
530
531 private:
532   // Pull in the concept type and model template specialized for functions.
533   typedef detail::PassConcept<Function *, FunctionAnalysisManager>
534   FunctionPassConcept;
535   template <typename PassT>
536   struct FunctionPassModel
537       : detail::PassModel<Function *, FunctionAnalysisManager, PassT> {
538     FunctionPassModel(PassT Pass)
539         : detail::PassModel<Function *, FunctionAnalysisManager, PassT>(
540               std::move(Pass)) {}
541   };
542
543   FunctionPassManager(const FunctionPassManager &) LLVM_DELETED_FUNCTION;
544   FunctionPassManager &
545   operator=(const FunctionPassManager &) LLVM_DELETED_FUNCTION;
546
547   std::vector<std::unique_ptr<FunctionPassConcept>> Passes;
548 };
549
550 namespace detail {
551
552 /// \brief A CRTP base used to implement analysis managers.
553 ///
554 /// This class template serves as the boiler plate of an analysis manager. Any
555 /// analysis manager can be implemented on top of this base class. Any
556 /// implementation will be required to provide specific hooks:
557 ///
558 /// - getResultImpl
559 /// - getCachedResultImpl
560 /// - invalidateImpl
561 ///
562 /// The details of the call pattern are within.
563 template <typename DerivedT, typename IRUnitT> class AnalysisManagerBase {
564   DerivedT *derived_this() { return static_cast<DerivedT *>(this); }
565   const DerivedT *derived_this() const {
566     return static_cast<const DerivedT *>(this);
567   }
568
569   AnalysisManagerBase(const AnalysisManagerBase &) LLVM_DELETED_FUNCTION;
570   AnalysisManagerBase &
571   operator=(const AnalysisManagerBase &) LLVM_DELETED_FUNCTION;
572
573 protected:
574   typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT;
575   typedef detail::AnalysisPassConcept<IRUnitT, DerivedT> PassConceptT;
576
577   // FIXME: Provide template aliases for the models when we're using C++11 in
578   // a mode supporting them.
579
580   // We have to explicitly define all the special member functions because MSVC
581   // refuses to generate them.
582   AnalysisManagerBase() {}
583   AnalysisManagerBase(AnalysisManagerBase &&Arg)
584       : AnalysisPasses(std::move(Arg.AnalysisPasses)) {}
585   AnalysisManagerBase &operator=(AnalysisManagerBase &&RHS) {
586     AnalysisPasses = std::move(RHS.AnalysisPasses);
587     return *this;
588   }
589
590 public:
591   /// \brief Get the result of an analysis pass for this module.
592   ///
593   /// If there is not a valid cached result in the manager already, this will
594   /// re-run the analysis to produce a valid result.
595   template <typename PassT> typename PassT::Result &getResult(IRUnitT IR) {
596     assert(AnalysisPasses.count(PassT::ID()) &&
597            "This analysis pass was not registered prior to being queried");
598
599     ResultConceptT &ResultConcept =
600         derived_this()->getResultImpl(PassT::ID(), IR);
601     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
602         ResultModelT;
603     return static_cast<ResultModelT &>(ResultConcept).Result;
604   }
605
606   /// \brief Get the cached result of an analysis pass for this module.
607   ///
608   /// This method never runs the analysis.
609   ///
610   /// \returns null if there is no cached result.
611   template <typename PassT>
612   typename PassT::Result *getCachedResult(IRUnitT IR) const {
613     assert(AnalysisPasses.count(PassT::ID()) &&
614            "This analysis pass was not registered prior to being queried");
615
616     ResultConceptT *ResultConcept =
617         derived_this()->getCachedResultImpl(PassT::ID(), IR);
618     if (!ResultConcept)
619       return nullptr;
620
621     typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
622         ResultModelT;
623     return &static_cast<ResultModelT *>(ResultConcept)->Result;
624   }
625
626   /// \brief Register an analysis pass with the manager.
627   ///
628   /// This provides an initialized and set-up analysis pass to the analysis
629   /// manager. Whomever is setting up analysis passes must use this to populate
630   /// the manager with all of the analysis passes available.
631   template <typename PassT> void registerPass(PassT Pass) {
632     assert(!AnalysisPasses.count(PassT::ID()) &&
633            "Registered the same analysis pass twice!");
634     typedef detail::AnalysisPassModel<IRUnitT, DerivedT, PassT> PassModelT;
635     AnalysisPasses[PassT::ID()].reset(new PassModelT(std::move(Pass)));
636   }
637
638   /// \brief Invalidate a specific analysis pass for an IR module.
639   ///
640   /// Note that the analysis result can disregard invalidation.
641   template <typename PassT> void invalidate(Module *M) {
642     assert(AnalysisPasses.count(PassT::ID()) &&
643            "This analysis pass was not registered prior to being invalidated");
644     derived_this()->invalidateImpl(PassT::ID(), M);
645   }
646
647   /// \brief Invalidate analyses cached for an IR unit.
648   ///
649   /// Walk through all of the analyses pertaining to this unit of IR and
650   /// invalidate them unless they are preserved by the PreservedAnalyses set.
651   void invalidate(IRUnitT IR, const PreservedAnalyses &PA) {
652     derived_this()->invalidateImpl(IR, PA);
653   }
654
655 protected:
656   /// \brief Lookup a registered analysis pass.
657   PassConceptT &lookupPass(void *PassID) {
658     typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(PassID);
659     assert(PI != AnalysisPasses.end() &&
660            "Analysis passes must be registered prior to being queried!");
661     return *PI->second;
662   }
663
664   /// \brief Lookup a registered analysis pass.
665   const PassConceptT &lookupPass(void *PassID) const {
666     typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(PassID);
667     assert(PI != AnalysisPasses.end() &&
668            "Analysis passes must be registered prior to being queried!");
669     return *PI->second;
670   }
671
672 private:
673   /// \brief Map type from module analysis pass ID to pass concept pointer.
674   typedef DenseMap<void *, std::unique_ptr<PassConceptT>> AnalysisPassMapT;
675
676   /// \brief Collection of module analysis passes, indexed by ID.
677   AnalysisPassMapT AnalysisPasses;
678 };
679
680 } // End namespace detail
681
682 /// \brief A module analysis pass manager with lazy running and caching of
683 /// results.
684 class ModuleAnalysisManager
685     : public detail::AnalysisManagerBase<ModuleAnalysisManager, Module *> {
686   friend class detail::AnalysisManagerBase<ModuleAnalysisManager, Module *>;
687   typedef detail::AnalysisManagerBase<ModuleAnalysisManager, Module *> BaseT;
688   typedef BaseT::ResultConceptT ResultConceptT;
689   typedef BaseT::PassConceptT PassConceptT;
690
691 public:
692   // We have to explicitly define all the special member functions because MSVC
693   // refuses to generate them.
694   ModuleAnalysisManager() {}
695   ModuleAnalysisManager(ModuleAnalysisManager &&Arg)
696       : BaseT(std::move(static_cast<BaseT &>(Arg))),
697         ModuleAnalysisResults(std::move(Arg.ModuleAnalysisResults)) {}
698   ModuleAnalysisManager &operator=(ModuleAnalysisManager &&RHS) {
699     BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
700     ModuleAnalysisResults = std::move(RHS.ModuleAnalysisResults);
701     return *this;
702   }
703
704 private:
705   ModuleAnalysisManager(const ModuleAnalysisManager &) LLVM_DELETED_FUNCTION;
706   ModuleAnalysisManager &
707   operator=(const ModuleAnalysisManager &) LLVM_DELETED_FUNCTION;
708
709   /// \brief Get a module pass result, running the pass if necessary.
710   ResultConceptT &getResultImpl(void *PassID, Module *M);
711
712   /// \brief Get a cached module pass result or return null.
713   ResultConceptT *getCachedResultImpl(void *PassID, Module *M) const;
714
715   /// \brief Invalidate a module pass result.
716   void invalidateImpl(void *PassID, Module *M);
717
718   /// \brief Invalidate results across a module.
719   void invalidateImpl(Module *M, const PreservedAnalyses &PA);
720
721   /// \brief Map type from module analysis pass ID to pass result concept
722   /// pointer.
723   typedef DenseMap<void *,
724                    std::unique_ptr<detail::AnalysisResultConcept<Module *>>>
725       ModuleAnalysisResultMapT;
726
727   /// \brief Cache of computed module analysis results for this module.
728   ModuleAnalysisResultMapT ModuleAnalysisResults;
729 };
730
731 /// \brief A function analysis manager to coordinate and cache analyses run over
732 /// a module.
733 class FunctionAnalysisManager
734     : public detail::AnalysisManagerBase<FunctionAnalysisManager, Function *> {
735   friend class detail::AnalysisManagerBase<FunctionAnalysisManager, Function *>;
736   typedef detail::AnalysisManagerBase<FunctionAnalysisManager, Function *>
737       BaseT;
738   typedef BaseT::ResultConceptT ResultConceptT;
739   typedef BaseT::PassConceptT PassConceptT;
740
741 public:
742   // Most public APIs are inherited from the CRTP base class.
743
744   // We have to explicitly define all the special member functions because MSVC
745   // refuses to generate them.
746   FunctionAnalysisManager() {}
747   FunctionAnalysisManager(FunctionAnalysisManager &&Arg)
748       : BaseT(std::move(static_cast<BaseT &>(Arg))),
749         FunctionAnalysisResults(std::move(Arg.FunctionAnalysisResults)) {}
750   FunctionAnalysisManager &operator=(FunctionAnalysisManager &&RHS) {
751     BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
752     FunctionAnalysisResults = std::move(RHS.FunctionAnalysisResults);
753     return *this;
754   }
755
756   /// \brief Returns true if the analysis manager has an empty results cache.
757   bool empty() const;
758
759   /// \brief Clear the function analysis result cache.
760   ///
761   /// This routine allows cleaning up when the set of functions itself has
762   /// potentially changed, and thus we can't even look up a a result and
763   /// invalidate it directly. Notably, this does *not* call invalidate
764   /// functions as there is nothing to be done for them.
765   void clear();
766
767 private:
768   FunctionAnalysisManager(const FunctionAnalysisManager &)
769       LLVM_DELETED_FUNCTION;
770   FunctionAnalysisManager &
771   operator=(const FunctionAnalysisManager &) LLVM_DELETED_FUNCTION;
772
773   /// \brief Get a function pass result, running the pass if necessary.
774   ResultConceptT &getResultImpl(void *PassID, Function *F);
775
776   /// \brief Get a cached function pass result or return null.
777   ResultConceptT *getCachedResultImpl(void *PassID, Function *F) const;
778
779   /// \brief Invalidate a function pass result.
780   void invalidateImpl(void *PassID, Function *F);
781
782   /// \brief Invalidate the results for a function..
783   void invalidateImpl(Function *F, const PreservedAnalyses &PA);
784
785   /// \brief List of function analysis pass IDs and associated concept pointers.
786   ///
787   /// Requires iterators to be valid across appending new entries and arbitrary
788   /// erases. Provides both the pass ID and concept pointer such that it is
789   /// half of a bijection and provides storage for the actual result concept.
790   typedef std::list<std::pair<
791       void *, std::unique_ptr<detail::AnalysisResultConcept<Function *>>>>
792           FunctionAnalysisResultListT;
793
794   /// \brief Map type from function pointer to our custom list type.
795   typedef DenseMap<Function *, FunctionAnalysisResultListT>
796       FunctionAnalysisResultListMapT;
797
798   /// \brief Map from function to a list of function analysis results.
799   ///
800   /// Provides linear time removal of all analysis results for a function and
801   /// the ultimate storage for a particular cached analysis result.
802   FunctionAnalysisResultListMapT FunctionAnalysisResultLists;
803
804   /// \brief Map type from a pair of analysis ID and function pointer to an
805   /// iterator into a particular result list.
806   typedef DenseMap<std::pair<void *, Function *>,
807                    FunctionAnalysisResultListT::iterator>
808       FunctionAnalysisResultMapT;
809
810   /// \brief Map from an analysis ID and function to a particular cached
811   /// analysis result.
812   FunctionAnalysisResultMapT FunctionAnalysisResults;
813 };
814
815 /// \brief A module analysis which acts as a proxy for a function analysis
816 /// manager.
817 ///
818 /// This primarily proxies invalidation information from the module analysis
819 /// manager and module pass manager to a function analysis manager. You should
820 /// never use a function analysis manager from within (transitively) a module
821 /// pass manager unless your parent module pass has received a proxy result
822 /// object for it.
823 class FunctionAnalysisManagerModuleProxy {
824 public:
825   class Result;
826
827   static void *ID() { return (void *)&PassID; }
828
829   explicit FunctionAnalysisManagerModuleProxy(FunctionAnalysisManager &FAM)
830       : FAM(&FAM) {}
831   // We have to explicitly define all the special member functions because MSVC
832   // refuses to generate them.
833   FunctionAnalysisManagerModuleProxy(
834       const FunctionAnalysisManagerModuleProxy &Arg)
835       : FAM(Arg.FAM) {}
836   FunctionAnalysisManagerModuleProxy(FunctionAnalysisManagerModuleProxy &&Arg)
837       : FAM(std::move(Arg.FAM)) {}
838   FunctionAnalysisManagerModuleProxy &
839   operator=(FunctionAnalysisManagerModuleProxy RHS) {
840     std::swap(FAM, RHS.FAM);
841     return *this;
842   }
843
844   /// \brief Run the analysis pass and create our proxy result object.
845   ///
846   /// This doesn't do any interesting work, it is primarily used to insert our
847   /// proxy result object into the module analysis cache so that we can proxy
848   /// invalidation to the function analysis manager.
849   ///
850   /// In debug builds, it will also assert that the analysis manager is empty
851   /// as no queries should arrive at the function analysis manager prior to
852   /// this analysis being requested.
853   Result run(Module *M);
854
855 private:
856   static char PassID;
857
858   FunctionAnalysisManager *FAM;
859 };
860
861 /// \brief The result proxy object for the
862 /// \c FunctionAnalysisManagerModuleProxy.
863 ///
864 /// See its documentation for more information.
865 class FunctionAnalysisManagerModuleProxy::Result {
866 public:
867   explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
868   // We have to explicitly define all the special member functions because MSVC
869   // refuses to generate them.
870   Result(const Result &Arg) : FAM(Arg.FAM) {}
871   Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
872   Result &operator=(Result RHS) {
873     std::swap(FAM, RHS.FAM);
874     return *this;
875   }
876   ~Result();
877
878   /// \brief Accessor for the \c FunctionAnalysisManager.
879   FunctionAnalysisManager &getManager() { return *FAM; }
880
881   /// \brief Handler for invalidation of the module.
882   ///
883   /// If this analysis itself is preserved, then we assume that the set of \c
884   /// Function objects in the \c Module hasn't changed and thus we don't need
885   /// to invalidate *all* cached data associated with a \c Function* in the \c
886   /// FunctionAnalysisManager.
887   ///
888   /// Regardless of whether this analysis is marked as preserved, all of the
889   /// analyses in the \c FunctionAnalysisManager are potentially invalidated
890   /// based on the set of preserved analyses.
891   bool invalidate(Module *M, const PreservedAnalyses &PA);
892
893 private:
894   FunctionAnalysisManager *FAM;
895 };
896
897 /// \brief A function analysis which acts as a proxy for a module analysis
898 /// manager.
899 ///
900 /// This primarily provides an accessor to a parent module analysis manager to
901 /// function passes. Only the const interface of the module analysis manager is
902 /// provided to indicate that once inside of a function analysis pass you
903 /// cannot request a module analysis to actually run. Instead, the user must
904 /// rely on the \c getCachedResult API.
905 ///
906 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
907 /// the recursive return path of each layer of the pass manager and the
908 /// returned PreservedAnalysis set.
909 class ModuleAnalysisManagerFunctionProxy {
910 public:
911   /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
912   class Result {
913   public:
914     explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
915     // We have to explicitly define all the special member functions because
916     // MSVC refuses to generate them.
917     Result(const Result &Arg) : MAM(Arg.MAM) {}
918     Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
919     Result &operator=(Result RHS) {
920       std::swap(MAM, RHS.MAM);
921       return *this;
922     }
923
924     const ModuleAnalysisManager &getManager() const { return *MAM; }
925
926     /// \brief Handle invalidation by ignoring it, this pass is immutable.
927     bool invalidate(Function *) { return false; }
928
929   private:
930     const ModuleAnalysisManager *MAM;
931   };
932
933   static void *ID() { return (void *)&PassID; }
934
935   ModuleAnalysisManagerFunctionProxy(const ModuleAnalysisManager &MAM)
936       : MAM(&MAM) {}
937   // We have to explicitly define all the special member functions because MSVC
938   // refuses to generate them.
939   ModuleAnalysisManagerFunctionProxy(
940       const ModuleAnalysisManagerFunctionProxy &Arg)
941       : MAM(Arg.MAM) {}
942   ModuleAnalysisManagerFunctionProxy(ModuleAnalysisManagerFunctionProxy &&Arg)
943       : MAM(std::move(Arg.MAM)) {}
944   ModuleAnalysisManagerFunctionProxy &
945   operator=(ModuleAnalysisManagerFunctionProxy RHS) {
946     std::swap(MAM, RHS.MAM);
947     return *this;
948   }
949
950   /// \brief Run the analysis pass and create our proxy result object.
951   /// Nothing to see here, it just forwards the \c MAM reference into the
952   /// result.
953   Result run(Function *) { return Result(*MAM); }
954
955 private:
956   static char PassID;
957
958   const ModuleAnalysisManager *MAM;
959 };
960
961 /// \brief Trivial adaptor that maps from a module to its functions.
962 ///
963 /// Designed to allow composition of a FunctionPass(Manager) and
964 /// a ModulePassManager. Note that if this pass is constructed with a pointer
965 /// to a \c ModuleAnalysisManager it will run the
966 /// \c FunctionAnalysisManagerModuleProxy analysis prior to running the function
967 /// pass over the module to enable a \c FunctionAnalysisManager to be used
968 /// within this run safely.
969 template <typename FunctionPassT> class ModuleToFunctionPassAdaptor {
970 public:
971   explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
972       : Pass(std::move(Pass)) {}
973   // We have to explicitly define all the special member functions because MSVC
974   // refuses to generate them.
975   ModuleToFunctionPassAdaptor(const ModuleToFunctionPassAdaptor &Arg)
976       : Pass(Arg.Pass) {}
977   ModuleToFunctionPassAdaptor(ModuleToFunctionPassAdaptor &&Arg)
978       : Pass(std::move(Arg.Pass)) {}
979   friend void swap(ModuleToFunctionPassAdaptor &LHS, ModuleToFunctionPassAdaptor &RHS) {
980     using std::swap;
981     swap(LHS.Pass, RHS.Pass);
982   }
983   ModuleToFunctionPassAdaptor &operator=(ModuleToFunctionPassAdaptor RHS) {
984     swap(*this, RHS);
985     return *this;
986   }
987
988   /// \brief Runs the function pass across every function in the module.
989   PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) {
990     FunctionAnalysisManager *FAM = nullptr;
991     if (AM)
992       // Setup the function analysis manager from its proxy.
993       FAM = &AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
994
995     PreservedAnalyses PA = PreservedAnalyses::all();
996     for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
997       PreservedAnalyses PassPA = Pass.run(I, FAM);
998
999       // We know that the function pass couldn't have invalidated any other
1000       // function's analyses (that's the contract of a function pass), so
1001       // directly handle the function analysis manager's invalidation here.
1002       if (FAM)
1003         FAM->invalidate(I, PassPA);
1004
1005       // Then intersect the preserved set so that invalidation of module
1006       // analyses will eventually occur when the module pass completes.
1007       PA.intersect(std::move(PassPA));
1008     }
1009
1010     // By definition we preserve the proxy. This precludes *any* invalidation
1011     // of function analyses by the proxy, but that's OK because we've taken
1012     // care to invalidate analyses in the function analysis manager
1013     // incrementally above.
1014     PA.preserve<FunctionAnalysisManagerModuleProxy>();
1015     return PA;
1016   }
1017
1018   static StringRef name() { return "ModuleToFunctionPassAdaptor"; }
1019
1020 private:
1021   FunctionPassT Pass;
1022 };
1023
1024 /// \brief A function to deduce a function pass type and wrap it in the
1025 /// templated adaptor.
1026 template <typename FunctionPassT>
1027 ModuleToFunctionPassAdaptor<FunctionPassT>
1028 createModuleToFunctionPassAdaptor(FunctionPassT Pass) {
1029   return std::move(ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));
1030 }
1031
1032 }
1033
1034 #endif