Implement a more powerful, simpler, pass system. This pass system can figure

out how to run a collection of passes optimially given their behaviors and
charactaristics.


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

1 files changed, 118 insertions, 87 deletions

diff --git a/include/llvm/Pass.h b/include/llvm/Pass.h
index c000927..06f0b74 100644
--- a/include/llvm/Pass.h
+++ b/include/llvm/Pass.h
@@ -3,30 +3,15 @@
 // This file defines a base class that indicates that a specified class is a
 // transformation pass implementation.
 //
-// Pass's are designed this way so that it is possible to apply N passes to a
-// module, by first doing N Pass specific initializations for the module, then
-// looping over all of the methods in the module, doing method specific work
-// N times for each method.  Like this:
+// Pass's are designed this way so that it is possible to run passes in a cache
+// and organizationally optimal order without having to specify it at the front
+// end.  This allows arbitrary passes to be strung together and have them
+// executed as effeciently as possible.
 //
-// for_each(Passes.begin(), Passes.end(), doPassInitialization(Module));
-// for_each(Method *M <- Module->begin(), Module->end())
-//   for_each(Passes.begin(), Passes.end(), doPerMethodWork(M));
-//
-// The other way to do things is like this:
-// for_each(Pass *P <- Passes.begin(), Passes.end()) {
-//   Passes->doPassInitialization(Module)
-//   for_each(Module->begin(), Module->end(), P->doPerMethodWork);
-// }
-//
-// But this can cause thrashing and poor cache performance, so we don't do it
-// that way.
-//
-// Because a transformation does not see all methods consecutively, it should
-// be careful about the state that it maintains... another pass may modify a
-// method between two invocatations of doPerMethodWork.
-//
-// Also, implementations of doMethodWork should not remove any methods from the
-// module.
+// Passes should extend one of the classes below, depending on the guarantees
+// that it can make about what will be modified as it is run.  For example, most
+// global optimizations should derive from MethodPass, because they do not add
+// or delete methods, they operate on the internals of the method.
 //
 //===----------------------------------------------------------------------===//
 
@@ -36,91 +21,137 @@
 #include "llvm/Module.h"
 #include "llvm/Method.h"
 
+class MethodPassBatcher;
+
 //===----------------------------------------------------------------------===//
-// Pass interface - Implemented by all 'passes'.
+// Pass interface - Implemented by all 'passes'.  Subclass this if you are an
+// interprocedural optimization or you do not fit into any of the more
+// constrained passes described below.
 //
 struct Pass {
-  //===--------------------------------------------------------------------===//
-  // The externally useful entry points
+  // Destructor - Virtual so we can be subclassed
+  inline virtual ~Pass() {}
+
+  virtual bool run(Module *M) = 0;
+};
+
+
+//===----------------------------------------------------------------------===//
+// MethodPass class - This class is used to implement most global optimizations.
+// Optimizations should subclass this class if they meet the following
+// constraints:
+//  1. Optimizations are organized globally, ie a method at a time
+//  2. Optimizing a method does not cause the addition or removal of any methods
+//     in the module
+//
+struct MethodPass : public Pass {
+  // doInitialization - Virtual method overridden by subclasses to do
+  // any neccesary per-module initialization.
   //
+  virtual bool doInitialization(Module *M) { return false; }
 
-  // runAllPasses - Run a bunch of passes on the specified module, efficiently.
-  static bool runAllPasses(Module *M, std::vector<Pass*> &Passes) {
-    bool MadeChanges = false;
-    // Run all of the pass initializers
-    for (unsigned i = 0; i < Passes.size(); ++i)
-      MadeChanges |= Passes[i]->doPassInitialization(M);
-    
-    // Loop over all of the methods, applying all of the passes to them
-    for (unsigned m = 0; m < M->size(); ++m)
-      for (unsigned i = 0; i < Passes.size(); ++i)
-        MadeChanges |= Passes[i]->doPerMethodWork(*(M->begin()+m));
-
-    // Run all of the pass finalizers...
-    for (unsigned i = 0; i < Passes.size(); ++i)
-      MadeChanges |= Passes[i]->doPassFinalization(M);
-    return MadeChanges;
-  }
+  // runOnMethod - Virtual method overriden by subclasses to do the per-method
+  // processing of the pass.
+  //
+  virtual bool runOnMethod(Method *M) = 0;
 
-  // runAllPassesAndFree - Run a bunch of passes on the specified module,
-  // efficiently.  When done, delete all of the passes.
+  // doFinalization - Virtual method overriden by subclasses to do any post
+  // processing needed after all passes have run.
   //
-  static bool runAllPassesAndFree(Module *M, std::vector<Pass*> &Passes) {
-    // First run all of the passes
-    bool MadeChanges = runAllPasses(M, Passes);
+  virtual bool doFinalization(Module *M) { return false; }
 
-    // Free all of the passes.
-    for (unsigned i = 0; i < Passes.size(); ++i)
-      delete Passes[i];
-    return MadeChanges;
-  }
 
+  virtual bool run(Module *M) {
+    bool Changed = doInitialization(M);
 
-  // run(Module*) - Run this pass on a module and all of the methods contained
-  // within it.  Returns true if any of the contained passes returned true.
-  //
-  bool run(Module *M) {
-    bool MadeChanges = doPassInitialization(M);
-
-    // Loop over methods in the module.  doPerMethodWork could add a method to
-    // the Module, so we have to keep checking for end of method list condition.
-    //
-    for (unsigned m = 0; m < M->size(); ++m)
-      MadeChanges |= doPerMethodWork(*(M->begin()+m));
-    return MadeChanges | doPassFinalization(M);
+    for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
+      Changed |= runOnMethod(*I);
+
+    return Changed | doFinalization(M);
   }
 
-  // run(Method*) - Run this pass on a module and one specific method.  Returns
-  // false on success.
-  //
-  bool run(Method *M) {
-    return doPassInitialization(M->getParent()) | doPerMethodWork(M) |
-           doPassFinalization(M->getParent());
+ bool run(Method *M) {
+   return doInitialization(M->getParent()) | runOnMethod(M)
+        | doFinalization(M->getParent());
   }
+};
 
 
-  //===--------------------------------------------------------------------===//
-  // Functions to be implemented by subclasses
-  //
 
-  // Destructor - Virtual so we can be subclassed
-  inline virtual ~Pass() {}
+//===----------------------------------------------------------------------===//
+// CFGSafeMethodPass class - This class is used to implement global
+// optimizations that do not modify the CFG of a method.  Optimizations should
+// subclass this class if they meet the following constraints:
+//   1. Optimizations are global, operating on a method at a time.
+//   2. Optimizations do not modify the CFG of the contained method, by adding,
+//      removing, or changing the order of basic blocks in a method.
+//   3. Optimizations conform to all of the contstraints of MethodPass's.
+//
+struct CFGSafeMethodPass : public MethodPass {
+
+  // TODO: Differentiation from MethodPass will come later
+
+};
 
-  // doPassInitialization - Virtual method overridden by subclasses to do
-  // any neccesary per-module initialization.
-  //
-  virtual bool doPassInitialization(Module *M) { return false; }
 
-  // doPerMethodWork - Virtual method overriden by subclasses to do the
-  // per-method processing of the pass.
+//===----------------------------------------------------------------------===//
+// BasicBlockPass class - This class is used to implement most local
+// optimizations.  Optimizations should subclass this class if they
+// meet the following constraints:
+//   1. Optimizations are local, operating on either a basic block or
+//      instruction at a time.
+//   2. Optimizations do not modify the CFG of the contained method, or any
+//      other basic block in the method.
+//   3. Optimizations conform to all of the contstraints of CFGSafeMethodPass's.
+//
+struct BasicBlockPass : public CFGSafeMethodPass {
+  // runOnBasicBlock - Virtual method overriden by subclasses to do the
+  // per-basicblock processing of the pass.
   //
-  virtual bool doPerMethodWork(Method *M) { return false; }
+  virtual bool runOnBasicBlock(BasicBlock *M) = 0;
 
-  // doPassFinalization - Virtual method overriden by subclasses to do any post
-  // processing needed after all passes have run.
+  virtual bool runOnMethod(Method *M) {
+    bool Changed = false;
+    for (Method::iterator I = M->begin(), E = M->end(); I != E; ++I)
+      Changed |= runOnBasicBlock(*I);
+    return Changed;
+  }
+
+  bool run(BasicBlock *BB) {
+    Module *M = BB->getParent()->getParent();
+    return doInitialization(M) | runOnBasicBlock(BB) | doFinalization(M);
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+// PassManager - Container object for passes.  The PassManager destructor
+// deletes all passes contained inside of the PassManager, so you shouldn't 
+// delete passes manually, and all passes should be dynamically allocated.
+//
+class PassManager {
+  std::vector<Pass*> Passes;
+  MethodPassBatcher *Batcher;
+public:
+  PassManager() : Batcher(0) {}
+  ~PassManager();
+
+  bool run(Module *M) {
+    bool MadeChanges = false;
+    // Run all of the pass initializers
+    for (unsigned i = 0, e = Passes.size(); i < e; ++i)
+      MadeChanges |= Passes[i]->run(M);
+    return MadeChanges;
+  }
+
+  // add - Add a pass to the queue of passes to run.  This passes ownership of
+  // the Pass to the PassManager.  When the PassManager is destroyed, the pass
+  // will be destroyed as well, so there is no need to delete the pass.  Also,
+  // all passes MUST be new'd.
   //
-  virtual bool doPassFinalization(Module *M) { return false; }
+  void add(Pass *P);
+  void add(MethodPass *P);
+  void add(BasicBlockPass *P);
 };
 
 #endif
-