[LLVMdev] passmanager, significant rework idea...

[Chris Lattner]

On Mon, 9 Jan 2006, Saem Ghani wrote:

> The patch below basically hammers out some ideas as to where I'd like
> to take the passmanager in LLVM.  I've tried thinking things through,
> but I'm still a n00b, so some criticism would be more than welcome. =)
>
> Starting from line 191 down.  If you're wondering why I created a
> patch, well that's because I found thinking in passmanagert.h the most
> productive.

Interesting approach.  :)

For those who aren't aware, Saem has been actively refactoring the pass 
manager to make it easier to understand and improve.

Comments below, with ***'s before the notes:

Index: lib/VMCore/PassManagerT.h
===================================================================
RCS file: /var/cvs/llvm/llvm/lib/VMCore/PassManagerT.h,v
retrieving revision 1.65
diff -U3 -r1.65 PassManagerT.h
--- lib/VMCore/PassManagerT.h	8 Jan 2006 22:57:07 -0000	1.65
+++ lib/VMCore/PassManagerT.h	10 Jan 2006 06:45:36 -0000
@@ -31,6 +31,8 @@

  namespace llvm {

+class LoopPass : public Pass {}; // Temporary.

*** I wouldn't worry about loop passes yet.

  //===----------------------------------------------------------------------===//
  // Pass debugging information.  Often it is useful to find out what pass is
  // running when a crash occurs in a utility.  When this library is compiled with
@@ -186,6 +188,116 @@
    typedef ModulePassManager PMType;
  };

+// TODO: Start migration towards a single passmanagert.  This PMT will manage 
+// all passes as one, rather than having any sort of hierarchy.  The trick is 
+// to have all the passes wrapped into a single abstract PassUnit.  Each 
+// PassUnit will then have concrete implmentations for all the various 
+// passes, such as, module, function, basicblock, loop, callgraphscc, and 
+// immutable.  These PassUnit will provide a single point of entry as an 
+// interface while its concrete implementations will handle all the pass
+// specific details.  Then a two types of PassCollection will be required, 
+// one ordered and another unordered.  This will allow either batches of 
+// Passes which can be run in parallel (unordered) or a sequence of Passes 
+// which depend upon each other.
+
+//The following is the foundation for the above.
+
+class PassUnit {
+  Pass *pass;
+ 
+  enum Traversal { 
+    LINEAR,      // Standard top down traversal.
+    CALLGRAPHSCC // Bottom Up Traversal
+  };
+ 
+  Traversal traversal;

*** 'Traversals' as you have them here don't really make sense.  The 
notion of whether to run a Function pass in module order or in bottom-up- 
on-the-callgraph order is not a property of any pass.  Further, this idea 
is specific to function passes, so it shouldn't be captured in a place 
generic to all passes.  I'd much rather have this implemented as a new 
kind of "batcher" pass manager:

In the current pass manager, when you add a sequence of function passes to 
a "Module PassManager", a batcher is created.  This batcher happens to 
traverse the module from beginning to end, running each function pass on 
the functions in this order.  However, there is no specific reason to do 
this, it could run them from end to beginning, random order, or even 
callgraphscc order.

To handle this notion, I'd suggest two things: 1) having a batcher for 
CallGraphSCCPass'es and 2) having a new batcher class, some sort of 
"callgraphsccbatcher".

1) is important, because right now CallGraphSCCPass's are really just
    ModulePass'es to the pass manager.  If we have two CallGraphSCCPass'es
    (e.g. -prune-eh and -inline) being run in sequence, added to a "Module
    PassManager", we currently run the first one on each function
    bottom-up, then run the second on each function bottom up.

    Instead of this, it would be better to have a CallGraphSCCPassBatcher
    thing, that is added to the ModulePass.  Given this, for each function,
    bottom up, we can pipeline between then two passes.  This gives us the
    nice ABABABAB ordering instead of AAAABBBB ordering which is nice for
    cache behavior of the compiler.

2) Once 1) is implemented, if a Module PassManager currently has a
    "CallGraphSCCPassBatcher" active, it makes sense to use a new batcher
    for the function passes.  Since we don't need to run them in any
    specific order, we might as well run the function passes in the order
    that the callgraphsccpasses are being run in.  If there is no
    CallGraphSCCPassBatcher active, the passmanager would check to see if
    there is a FunctionPassBatcher active, and if not it would create one.

Finally, note that all of this behavior is specific to "Module 
PassManagers", so ideally none of the logic would be used/touched by the 
FunctionPassManager stuff etc.  Given this, it shouldn't be in something 
generic like the base PassUnit class, which is why I'm talking about it 
here. :)

+  std::vector<Pass*> RequiredPasses;

Why have the list of required passes here?  You can trivially get this 
from P->getAnalysisUsage(), likewise with the pass name.

+public:
+  PassUnit(Traversal traversal = LINEAR, Pass *Pass) : 
+    traversal(traversal),
+ 
+  virtual const char *getPMName() const =0;
+ 
+  virtual const char *getPassName() const =0;
+
+  virtual bool runPass(PassClass *P, UnitType *M) =0;
+};
+
+class BBPassUnit : public PassUnit {
+  BasicBlockPass *BBPass;
+ 
+public:
+  BBPassUnit(Traversal traversal = LINEAR, BasicBlockPass *Pass) : 
+    PassUnit::traversal(traversal), 
+    PassUnit::Pass(static_cast<Pass*>(Pass))
+    BBPassUnit::BBPass(Pass) {}
+};
+
+class LPassUnit : public PassUnit {
+  LoopPass *LPass;
+ 
+public:
+  LPassUnit(Traversal traversal = LINEAR, LoopPass *Pass) : 
+    PassUnit::traversal(traversal), 
+    PassUnit::Pass(static_cast<Pass*>(Pass))
+    LPassUnit::LPass(Pass) {}
+};
+
+class FPassUnit : public PassUnit {
+  FunctionPass *FPass;
+ 
+public:
+  FPassUnit(Traversal traversal = LINEAR, FunctionPass *Pass) : 
+    PassUnit::traversal(traversal), 
+    PassUnit::Pass(static_cast<Pass*>(Pass))
+    FPassUnit::FPass(Pass) {}
+};
+
+// For CallGraphSCC passes, really they're a FunctionPass for instance told to 
+// change traversal methods, this adds to their requiredPasses CallGraphSCC 
+// and when told to run, simply checks the traversal and uses CGSCC bottom-up.
+
+class MPassUnit : public PassUnit {
+  ModulePass *MPass;
+ 
+public:
+  MPassUnit(Traversal traversal = LINEAR, ModulePass *Pass) : 
+    PassUnit::traversal(traversal), 
+    PassUnit::Pass(static_cast<Pass*>(Pass))
+    MPassUnit::MPass(Pass) {}
+};

*** I don't think I really understand what the idea is behind the PassUnit 
instances here.  It appears to capture the same information that passes 
already capture themselves.  Can you explain a bit more?

+// PassCollection and its implmentations will actually posses a significant 
+// amount of the logic in terms of handling passes.  The passmanager will in 
+// fact be a simple interface and entry point.

"Just a quick little tid bit, that's rather important.  The
PassCollection class should inherit from PassUnit.  THis allows one to
embedd PassCollections within one another to get the appropriate
runtime hierarchy."

+class PassCollection {
+public:
+  enum Ordering {
+    ORDERED,
+    UNORDERED
+  };
+ 
+private:
+  Ordering order;
+ 
+public:
+  PassCollection(Ordering order) : order(order) {}
+  virtual void add(PassUnit pass) = 0;
+  virtual bool remove(PassUnit pass) = 0; // false if pass is not present.
+  virtual void runPasses() = 0;
+ 
+  // TODO: Figure out a reasonable data access strategy, might just be 
+  // iterators and potentionally returning vectors.  The actual storage 
+  // is thankfully flexible, so for instance in the case of LoopPasses, we 
+  // should be able to use a PriorityQueue and not have that explode in our 
+  // faces.
+};

To me, the most logical class hierarchy looks like this:

   Pass
     ModulePass
     CallGraphSCCPass
     FunctionPass
     BasicBlockPass
     ...

All of the high-level behaviors of passes are captured by which Pass class 
they inherit from.  The "Pass" class itself has basic pass support and 
interfaces, e.g. getting the pass name, the getAnalysisUsage method, the 
getAnalysis<> method, etc.  Pass does *not* contain any run* methods, only 
the derived classes (like ModulePass) do.  User passes extend things like 
FunctionPass as they currently do.  Expanding this hierarchy, I'd propose 
to have these built-in (but internal/private to VMCore):

   Pass
     ModulePass
       CallGraphSCCPassBatcher
       FunctionPassBatcher
     CallGraphSCCPass
       FunctionPassBatcherForCGSCCPass
     FunctionPass
       BasicBlockPassBatcher
     ModulePassBatcher
     ...

The batcher classes I wrote about above.  Basically they are the adapters 
that allow "small" passes to be embedded in "big" pass managers.  For 
example, CallGraphSCCPassBatcher would allow CallGraphSCCPass's to be 
added to a ModulePassManagerT.  As such, they have to conform to the 
interface that the outer PassManagerT object expects.  ModulePassBatcher 
is a funny one: it contains ModulePasses, and exposes a single 'run' 
interface.

Finally, the passmanagers themselves are implemented with:

   ModulePassManager
   FunctionPassManager

There is no inheritance here, and these classes are implemented using the 
pImpl idiom as they currently are.  However, instead of using 
PassManagerT<foo> to implement them, they are actually wrappers around 
ModulePassBatcher and FunctionPassBatcher, respectively.  Both of these 
'batcher' passes provide a simple interface to be used by the *PassManager 
classes.

The only question left (to me at least :) ), is where to factor out the 
commonality between the Batcher classes.  To me, the best solution appears 
to be to have a completely independent class "PassBatcher" which the 
*PassBatcher classes (which derive from Pass) contain an instance of to do 
the heavy lifting.

Does any of this make sense?

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/