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

[Chris Lattner]

On Tue, 10 Jan 2006, Saem Ghani wrote:
> 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

I wouldn't worry too much about BasicBlockPass's.  In practice, they 
operate at too fine of a granularity to be worth pipelining.  In practice, 
I wouldn't mind very much if we just got rid of passmanager awareness of 
BasicBlockPasses, and just made them normal FunctionPasses that have some 
traversal logic in the BasicBlockPass class to simplify the 
implementations.

> 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.

Ok.

> 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).

I don't see how this is related.  Given the organization I emailed about 
yesterday, consider something like the ModulePassBatcher.  Its 
implementation is actually *simplified* by the knowledge that all of the 
things that it "contains" are ModulePasses that just have a single run 
method.

Consider again, CallGraphSCCPassBatcher.  It is simplified by knowing that 
all things it contains conform to the CallGraphSCCPass interface.  Due to 
(careful forethought leading to) the fact that all FunctionPasses are 
defined to be CallGraphSCCPasses, we can have a simple adapter class (with 
the hypothetical name in the previous email of 
"FunctionPassBatcherForCGSCCPass") that serves this purpose and keeps 
everything simple.

The hierarchy and the interfaces have nothing to do with the pass 
dependency relationships, they relate to the structure of the pass 
managers and the order the passes get run.  The dependencies can *change* 
the structure, but the structure is not directly based on the 
dependencies.

>> 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.

s/mem2reg/pruneeh.  mem2reg is a FunctionPass.

>> 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.

And intrinsically more powerful/effective (solving some phase ordering 
issues), which is the basic idea behind the inliner improvement notes.

>> 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.

I don't understand your point 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.
>
> 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!

No problem.

>> *** 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.

That's fine, but it appears that they don't capture anything that cannot 
be extracted directly from the pass already.  Why not just use the pass 
objects?

>> 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
>> ...

> 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.

Yes, the batchers actually *are* passes, they just happen to be private 
implementation details of the pass manager.

> Mind you, that's basically the current state of affairs.

True, and the concept works well.  What doesn't work well is the nasty 
implementation using layers of templates and other goop :(

>> 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.

I disagree for the high level "PassManager" implementation.  PassManager 
and FunctionPassManager are used very differently.  The first one want a 
whole module, the second wants a function at a time.  Aside from the 
"addPass" method, the method for using them (run*) has a completely 
different interface.  I don't see why they should be the same class.

The *implementation* OTOH should be shared, as I sketched out before.

>> 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.

Ok.

-Chris

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