[LLVMdev] Re: passmanager, significant rework idea...

[Saem Ghani]

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.