Introduce an AnalysisManager which is like a pass manager but with a lot

more smarts in it. This is where most of the interesting logic that used
to live in the implicit-scheduling-hackery of the old pass manager will
live.

Like the previous commits, note that this is a very early prototype!
I expect substantial changes before this is ready to use.

The core of the design is the following:

- We have an AnalysisManager which can be used across a series of
  passes over a module.
- The code setting up a pass pipeline registers the analyses available
  with the manager.
- Individual transform passes can check than an analysis manager
  provides the analyses they require in order to fail-fast.
- There is *no* implicit registration or scheduling.
- Analysis passes are different from other passes: they produce an
  analysis result that is cached and made available via the analysis
  manager.
- Cached results are invalidated automatically by the pass managers.
- When a transform pass requests an analysis result, either the analysis
  is run to produce the result or a cached result is provided.

There are a few aspects of this design that I *know* will change in
subsequent commits:
- Currently there is no "preservation" system, that needs to be added.
- All of the analysis management should move up to the analysis library.
- The analysis management needs to support at least SCC passes. Maybe
  loop passes. Living in the analysis library will facilitate this.
- Need support for analyses which are *both* module and function passes.
- Need support for pro-actively running module analyses to have cached
  results within a function pass manager.
- Need a clear design for "immutable" passes.
- Need support for requesting cached results when available and not
  re-running the pass even if that would be necessary.
- Need more thorough testing of all of this infrastructure.

There are other aspects that I view as open questions I'm hoping to
resolve as I iterate a bit on the infrastructure, and especially as
I start writing actual passes against this.
- Should we have separate management layers for function, module, and
  SCC analyses? I think "yes", but I'm not yet ready to switch the code.
  Adding SCC support will likely resolve this definitively.
- How should the 'require' functionality work? Should *that* be the only
  way to request results to ensure that passes always require things?
- How should preservation work?
- Probably some other things I'm forgetting. =]

Look forward to more patches in shorter order now that this is in place.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194538 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 294 insertions, 12 deletions

diff --git a/include/llvm/IR/PassManager.h b/include/llvm/IR/PassManager.h
index aeadd41..5800e35 100644
--- a/include/llvm/IR/PassManager.h
+++ b/include/llvm/IR/PassManager.h
@@ -27,8 +27,12 @@
 ///
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/polymorphic_ptr.h"
+#include "llvm/Support/type_traits.h"
+#include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
+#include <list>
 #include <vector>
 
 namespace llvm {
@@ -64,18 +68,17 @@ template <typename T, typename PassT> struct PassModel : PassConcept<T> {
 
 }
 
+class AnalysisManager;
+
 class ModulePassManager {
 public:
-  ModulePassManager(Module *M) : M(M) {}
+  ModulePassManager(Module *M, AnalysisManager *AM = 0) : M(M), AM(AM) {}
 
   template <typename ModulePassT> void addPass(ModulePassT Pass) {
     Passes.push_back(new ModulePassModel<ModulePassT>(llvm_move(Pass)));
   }
 
-  void run() {
-    for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx)
-      Passes[Idx]->run(M);
-  }
+  void run();
 
 private:
   // Pull in the concept type and model template specialized for modules.
@@ -86,22 +89,19 @@ private:
   };
 
   Module *M;
+  AnalysisManager *AM;
   std::vector<polymorphic_ptr<ModulePassConcept> > Passes;
 };
 
 class FunctionPassManager {
 public:
+  FunctionPassManager(AnalysisManager *AM = 0) : AM(AM) {}
+
   template <typename FunctionPassT> void addPass(FunctionPassT Pass) {
     Passes.push_back(new FunctionPassModel<FunctionPassT>(llvm_move(Pass)));
   }
 
-  bool run(Module *M) {
-    bool Changed = false;
-    for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
-      for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx)
-        Changed |= Passes[Idx]->run(I);
-    return Changed;
-  }
+  bool run(Module *M);
 
 private:
   // Pull in the concept type and model template specialized for functions.
@@ -112,7 +112,289 @@ private:
         : detail::PassModel<Function *, PassT>(Pass) {}
   };
 
+  AnalysisManager *AM;
   std::vector<polymorphic_ptr<FunctionPassConcept> > Passes;
 };
 
+
+/// \brief An analysis manager to coordinate and cache analyses run over
+/// a module.
+///
+/// The analysis manager is typically used by passes in a pass pipeline
+/// (consisting potentially of several individual pass managers) over a module
+/// of IR. It provides registration of available analyses, declaring
+/// requirements on support for specific analyses, running of an specific
+/// analysis over a specific unit of IR to compute an analysis result, and
+/// caching of the analysis results to reuse them across multiple passes.
+///
+/// It is the responsibility of callers to use the invalidation API to
+/// invalidate analysis results when the IR they correspond to changes. The
+/// \c ModulePassManager and \c FunctionPassManager do this automatically.
+class AnalysisManager {
+public:
+  AnalysisManager(Module *M) : M(M) {}
+
+  /// \brief Get the result of an analysis pass for this module.
+  ///
+  /// If there is not a valid cached result in the manager already, this will
+  /// re-run the analysis to produce a valid result.
+  ///
+  /// The module passed in must be the same module as the analysis manager was
+  /// constructed around.
+  template <typename PassT>
+  const typename PassT::Result &getResult(Module *M) {
+    const AnalysisResultConcept<Module> &ResultConcept =
+        getResultImpl(PassT::ID(), M);
+    typedef AnalysisResultModel<Module, typename PassT::Result> ResultModelT;
+    return static_cast<const ResultModelT &>(ResultConcept).Result;
+  }
+
+  /// \brief Get the result of an analysis pass for a function.
+  ///
+  /// If there is not a valid cached result in the manager already, this will
+  /// re-run the analysis to produce a valid result.
+  template <typename PassT>
+  const typename PassT::Result &getResult(Function *F) {
+    const AnalysisResultConcept<Function> &ResultConcept =
+        getResultImpl(PassT::ID(), F);
+    typedef AnalysisResultModel<Function, typename PassT::Result> ResultModelT;
+    return static_cast<const ResultModelT &>(ResultConcept).Result;
+  }
+
+  /// \brief Register an analysis pass with the manager.
+  ///
+  /// This provides an initialized and set-up analysis pass to the
+  /// analysis
+  /// manager. Whomever is setting up analysis passes must use this to
+  /// populate
+  /// the manager with all of the analysis passes available.
+  template <typename PassT> void registerAnalysisPass(PassT Pass) {
+    registerAnalysisPassImpl<PassT>(llvm_move(Pass));
+  }
+
+  /// \brief Require that a particular analysis pass is provided by the manager.
+  ///
+  /// This allows transform passes to assert ther requirements during
+  /// construction and fail fast if the analysis manager doesn't provide the
+  /// needed facilities.
+  ///
+  /// We force the analysis manager to have these passes explicitly registered
+  /// first to ensure that there is exactly one place in the code responsible
+  /// for adding an analysis pass to the manager as all transforms will share
+  /// a single pass within the manager and each may not be the canonical place
+  /// to initialize such a pass.
+  template <typename PassT> void requireAnalysisPass() {
+    requireAnalysisPassImpl<PassT>();
+  }
+
+  /// \brief Invalidate a specific analysis pass for an IR module.
+  ///
+  /// Note that the analysis result can disregard invalidation.
+  template <typename PassT> void invalidate(Module *M) {
+    invalidateImpl(PassT::ID(), M);
+  }
+
+  /// \brief Invalidate a specific analysis pass for an IR function.
+  ///
+  /// Note that the analysis result can disregard invalidation.
+  template <typename PassT> void invalidate(Function *F) {
+    invalidateImpl(PassT::ID(), F);
+  }
+
+  /// \brief Invalidate analyses cached for an IR Module.
+  ///
+  /// Note that specific analysis results can disregard invalidation by
+  /// overriding their invalidate method.
+  ///
+  /// The module must be the module this analysis manager was constructed
+  /// around.
+  void invalidateAll(Module *M);
+
+  /// \brief Invalidate analyses cached for an IR Function.
+  ///
+  /// Note that specific analysis results can disregard invalidation by
+  /// overriding the invalidate method.
+  void invalidateAll(Function *F);
+
+private:
+  /// \brief Abstract concept of an analysis result.
+  ///
+  /// This concept is parameterized over the IR unit that this result pertains
+  /// to.
+  template <typename IRUnitT> struct AnalysisResultConcept {
+    virtual ~AnalysisResultConcept() {}
+    virtual AnalysisResultConcept *clone() = 0;
+
+    /// \brief Method to try and mark a result as invalid.
+    ///
+    /// When the outer \c AnalysisManager detects a change in some underlying
+    /// unit of the IR, it will call this method on all of the results cached.
+    ///
+    /// \returns true if the result should indeed be invalidated (the default).
+    virtual bool invalidate(IRUnitT *IR) = 0;
+  };
+
+  /// \brief Wrapper to model the analysis result concept.
+  ///
+  /// Can wrap any type which implements a suitable invalidate member and model
+  /// the AnalysisResultConcept for the AnalysisManager.
+  template <typename IRUnitT, typename ResultT>
+  struct AnalysisResultModel : AnalysisResultConcept<IRUnitT> {
+    AnalysisResultModel(ResultT Result) : Result(llvm_move(Result)) {}
+    virtual AnalysisResultModel *clone() {
+      return new AnalysisResultModel(Result);
+    }
+
+    /// \brief The model delegates to the \c ResultT method.
+    virtual bool invalidate(IRUnitT *IR) { return Result.invalidate(IR); }
+
+    ResultT Result;
+  };
+
+  /// \brief Abstract concept of an analysis pass.
+  ///
+  /// This concept is parameterized over the IR unit that it can run over and
+  /// produce an analysis result.
+  template <typename IRUnitT> struct AnalysisPassConcept {
+    virtual ~AnalysisPassConcept() {}
+    virtual AnalysisPassConcept *clone() = 0;
+
+    /// \brief Method to run this analysis over a unit of IR.
+    /// \returns The analysis result object to be queried by users, the caller
+    /// takes ownership.
+    virtual AnalysisResultConcept<IRUnitT> *run(IRUnitT *IR) = 0;
+  };
+
+  /// \brief Wrapper to model the analysis pass concept.
+  ///
+  /// Can wrap any type which implements a suitable \c run method. The method
+  /// must accept the IRUnitT as an argument and produce an object which can be
+  /// wrapped in a \c AnalysisResultModel.
+  template <typename PassT>
+  struct AnalysisPassModel : AnalysisPassConcept<typename PassT::IRUnitT> {
+    AnalysisPassModel(PassT Pass) : Pass(llvm_move(Pass)) {}
+    virtual AnalysisPassModel *clone() { return new AnalysisPassModel(Pass); }
+
+    // FIXME: Replace PassT::IRUnitT with type traits when we use C++11.
+    typedef typename PassT::IRUnitT IRUnitT;
+
+    // FIXME: Replace PassT::Result with type traits when we use C++11.
+    typedef AnalysisResultModel<IRUnitT, typename PassT::Result> ResultModelT;
+
+    /// \brief The model delegates to the \c PassT::run method.
+    ///
+    /// The return is wrapped in an \c AnalysisResultModel.
+    virtual ResultModelT *run(IRUnitT *IR) {
+      return new ResultModelT(Pass.run(IR));
+    }
+
+    PassT Pass;
+  };
+
+
+  /// \brief Get a module pass result, running the pass if necessary.
+  const AnalysisResultConcept<Module> &getResultImpl(void *PassID, Module *M);
+
+  /// \brief Get a function pass result, running the pass if necessary.
+  const AnalysisResultConcept<Function> &getResultImpl(void *PassID,
+                                                       Function *F);
+
+  /// \brief Invalidate a module pass result.
+  void invalidateImpl(void *PassID, Module *M);
+
+  /// \brief Invalidate a function pass result.
+  void invalidateImpl(void *PassID, Function *F);
+
+
+  /// \brief Module pass specific implementation of registration.
+  template <typename PassT>
+  typename enable_if<is_same<typename PassT::IRUnitT, Module> >::type
+  registerAnalysisPassImpl(PassT Pass) {
+    assert(!ModuleAnalysisPasses.count(PassT::ID()) &&
+           "Registered the same analysis pass twice!");
+    ModuleAnalysisPasses[PassT::ID()] =
+        new AnalysisPassModel<PassT>(llvm_move(Pass));
+  }
+
+  /// \brief Function pass specific implementation of registration.
+  template <typename PassT>
+  typename enable_if<is_same<typename PassT::IRUnitT, Function> >::type
+  registerAnalysisPassImpl(PassT Pass) {
+    assert(!FunctionAnalysisPasses.count(PassT::ID()) &&
+           "Registered the same analysis pass twice!");
+    FunctionAnalysisPasses[PassT::ID()] =
+        new AnalysisPassModel<PassT>(llvm_move(Pass));
+  }
+
+  /// \brief Module pass specific implementation of requirement declaration.
+  template <typename PassT>
+  typename enable_if<is_same<typename PassT::IRUnitT, Module> >::type
+  requireAnalysisPassImpl() {
+    assert(ModuleAnalysisPasses.count(PassT::ID()) &&
+           "This analysis pass was not registered prior to being required");
+  }
+
+  /// \brief Function pass specific implementation of requirement declaration.
+  template <typename PassT>
+  typename enable_if<is_same<typename PassT::IRUnitT, Function> >::type
+  requireAnalysisPassImpl() {
+    assert(FunctionAnalysisPasses.count(PassT::ID()) &&
+           "This analysis pass was not registered prior to being required");
+  }
+
+
+  /// \brief Map type from module analysis pass ID to pass concept pointer.
+  typedef DenseMap<void *, polymorphic_ptr<AnalysisPassConcept<Module> > >
+  ModuleAnalysisPassMapT;
+
+  /// \brief Collection of module analysis passes, indexed by ID.
+  ModuleAnalysisPassMapT ModuleAnalysisPasses;
+
+  /// \brief Map type from module analysis pass ID to pass result concept pointer.
+  typedef DenseMap<void *, polymorphic_ptr<AnalysisResultConcept<Module> > >
+  ModuleAnalysisResultMapT;
+
+  /// \brief Cache of computed module analysis results for this module.
+  ModuleAnalysisResultMapT ModuleAnalysisResults;
+
+
+  /// \brief Map type from function analysis pass ID to pass concept pointer.
+  typedef DenseMap<void *, polymorphic_ptr<AnalysisPassConcept<Function> > >
+  FunctionAnalysisPassMapT;
+
+  /// \brief Collection of function analysis passes, indexed by ID.
+  FunctionAnalysisPassMapT FunctionAnalysisPasses;
+
+  /// \brief List of function analysis pass IDs and associated concept pointers.
+  ///
+  /// Requires iterators to be valid across appending new entries and arbitrary
+  /// erases. Provides both the pass ID and concept pointer such that it is
+  /// half of a bijection and provides storage for the actual result concept.
+  typedef std::list<
+      std::pair<void *, polymorphic_ptr<AnalysisResultConcept<Function> > > >
+  FunctionAnalysisResultListT;
+
+  /// \brief Map type from function pointer to our custom list type.
+  typedef DenseMap<Function *, FunctionAnalysisResultListT> FunctionAnalysisResultListMapT;
+
+  /// \brief Map from function to a list of function analysis results.
+  ///
+  /// Provides linear time removal of all analysis results for a function and
+  /// the ultimate storage for a particular cached analysis result.
+  FunctionAnalysisResultListMapT FunctionAnalysisResultLists;
+
+  /// \brief Map type from a pair of analysis ID and function pointer to an
+  /// iterator into a particular result list.
+  typedef DenseMap<std::pair<void *, Function *>,
+                   FunctionAnalysisResultListT::iterator>
+  FunctionAnalysisResultMapT;
+
+  /// \brief Map from an analysis ID and function to a particular cached
+  /// analysis result.
+  FunctionAnalysisResultMapT FunctionAnalysisResults;
+
+  /// \brief Module handle for the \c AnalysisManager.
+  Module *M;
+};
+
 }