llvm dev - Jan 2006 - [LLVMdev] passmanager, significant rework idea...

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.

--
Regards.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: passmanager_idea.diff
Type: text/x-diff
Size: 4465 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20060109/87b4a550/attachment.diff>

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.

On 1/9/06, Saem Ghani <saemghani at gmail.com>
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.
>
> --
> Regards.
>
>
>

--
Regards.

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/

On 1/10/06, Chris Lattner <sabre at nondot.org>
wrote:
> Interesting approach.  :)
Thanks.
> Comments below, with ***'s before the notes:
> +class LoopPass : public Pass {}; // Temporary.
>
> *** I wouldn't worry about loop passes yet.
Sure.
> +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:
You're the expert, so I gather you're right.  I was thinking that a
generic traversal facility would be nice, since basicblocks might get
something in the future or what have you.  But that can be fixed by
putting this in the FUnitType and having that handle it behind the
scenes.  There is something about batchers that doesn't quite sit
right with me, I think it stems from the fact that you can only batch
one type.  It doesn't seem like a huge problem, but it either paints
you into a corner or forces you to riddle the classes with extra
methods to handle items that don't neatly fit into the hierarchy.  eg.
CGSCC, Immutable, loop and reverse dependencies (module -> function).
> 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.
Yup.
> 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".
So callgraphsccpasses would be (for example) inline and mem2reg and
then those would be tossed into the batcher.
> 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.
Yup, interleaving would be far more efficient.
> 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.
As stated in the inliner improvements notes on your site, there seems
to be a significant effect based on the order of application and
traversal method used, wouldn't this hold true for other passes?  I
could be wrong, but this seems weird to me.  This is all speaking in
general terms.
> 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. :)
Makes sense.
> +  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.
My idea was to add dependencies as the passes were being organised,
such as a functionpass depending upon callgraphscc as part of the
traversal bit.  Now that I think about it, the traversal variable is
all that's needed.  So chalk it upto brainfart!
> +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?
The idea is to provide a wrapper to hide any pass specific logic
that's required for pass management.  They don't really capture a lot
of information right now but that's because they're more geared
towards being method heavy.
> +// 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.
So, batchers are pseudo passes, basically, if a batcher inherits from
x, then it runs at the same strata as the parent, thus the
inheritance.  Mind you, that's basically the current state of affairs.
> 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.
I would think having a single PassManager which has an overloaded set
of methods to handle the various passes that could be added to it
might be better.
> 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?
I think the key points here is that we group passes, order those
groups of passes and then finally run those ordered groups of passes. 
The batcher hierarchy you presented makes sense.  I'm simply trying to
shake the gut feeling that I have, relating to how extensible this
will be if a new passtype is desired, for instance.

--
Regards.