llvm dev - Aug 2004 - [LLVMdev] How to get LoopInfo within Pass subclass?

On Aug 5, 2004, at 8:11 PM, Chris Lattner wrote:
>
> Sure, you can do that.  Just use F->getParent() to get to the Module.
D'oh. OK, so I can do what I need with a hack for now.
>> Also, out of curiosity, why the stateless restriction - is it because
>> passes may someday be run in parallel?
>
> Yup, exactly.  That and we want to be able to make multiple instances 
> of a
> function pass at the same time (e.g. loop info for a module pass) 
> without
> the function pass breaking.
Right.
> We have no problem with people asking questions.  :)  The PassManager 
> is
> actually do for a rewrite.  The current implementation is a nasty
> templated monster in lib/VMCore/PassManagerT.h.  If you'd like to work 
> on
> it, all you need are some C++ experience, little shame in asking
> questions, and an understanding of the passmanager.  Also, there is 
> some
> info in this bug that may be useful:  http://llvm.cs.uiuc.edu/PR36
Well, I took a look at it a bit over the weekend. I am probably not the 
right person to do the complete rewrite, for instance reworking the 
Pass class hierarchy doesn't sound like something I'd want to do. Just 
getting to this point has been a bit of an education in real C++.

However, I would be willing to try just adding support for Module 
passes requiring Function passes, and hopefully that work wouldn't be 
wasted when the eventual rewrite does occur.

Here's what I see: We have a modulepass MP that needs a functionpass 
FP. We need a copy of that FP (and every pass it depends on) for each 
function in the module that MP is being run on.

Currently, in add() we only create one instance of FP, on which we then 
call addToPassManager() so we can get the right call to addPass(FP, 
...), which adds FP to a single Batcher, in this case, a 
PassManagerT<FunctionPass>. In addPass(MP, ...) we see the FP in the 
required set, and attempt to mark it as used by the MP. We don't find 
it in markPassUsed though, because FP was never added to 
CurrentAnalyses. It was just added to the Batcher.

So here's some changes that look necessary. This is likely to be an 
oversimplified view, but hopefully it's a start.

1 - in add(), discover that the pass we're requiring is a subpass, and 
create more of them.
This is the natural place to do it, but can we do this here, or do we 
not know enough about the passes?

2 - in addPass(SubPassClass, ...), add those FPs to CurrentAnalyses.
Should we have a map of BatcherClasses - (function, BatcherClass) pairs 
instead of just one BatcherClass?

3 - Provide API for the MP to get an analysis per function. (generally, 
for the PassClass to get analysis per SubPassClass):

Instead of this:
getAnalysis<PassType>()
the natural thing would seem to be (for PassClass = MP and SubPassClass 
= FP):
getAnalysis<PassType>(Function)

This simple change does mean some big moving in the background, though, 
since (for starters) the PassInfoMap can't just key on the TypeInfo 
anymore.
It will need to key on something like a structure with TypeInfo and the 
unit of code that the pass is attached to. I have a feeling there are 
similar instances where PassInfo needs code-unit info attached to it...

Any comments/clarifications/suggestions?

-mike

On Mon, 9 Aug 2004, Michael McCracken wrote:
> On Aug 5, 2004, at 8:11 PM, Chris Lattner wrote:
> > Sure, you can do that.  Just use F->getParent() to get to the
Module.
>
> D'oh. OK, so I can do what I need with a hack for now.
Ok.
> > We have no problem with people asking questions.  :)  The PassManager
> > is actually do for a rewrite.  The current implementation is a nasty
>
> Well, I took a look at it a bit over the weekend. I am probably not the
> right person to do the complete rewrite, for instance reworking the
> Pass class hierarchy doesn't sound like something I'd want to do.
Just
> getting to this point has been a bit of an education in real C++.
Ok, fair enough.  It's a pretty big piece of work.  I would recommend
starting a bit smaller in the world of LLVM, then working up to the big
stuff. :)
> Here's what I see: We have a modulepass MP that needs a functionpass
> FP. We need a copy of that FP (and every pass it depends on) for each
> function in the module that MP is being run on.
Yup.
> Currently, in add() we only create one instance of FP, on which we then
> call addToPassManager() so we can get the right call to addPass(FP,
> ...), which adds FP to a single Batcher, in this case, a
> PassManagerT<FunctionPass>. In addPass(MP, ...) we see the FP in the
> required set, and attempt to mark it as used by the MP. We don't find
> it in markPassUsed though, because FP was never added to
> CurrentAnalyses. It was just added to the Batcher.
Yeah, this is the problem.
> So here's some changes that look necessary. This is likely to be an
> oversimplified view, but hopefully it's a start.
>
> 1 - in add(), discover that the pass we're requiring is a subpass, and
> create more of them. This is the natural place to do it, but can we do
> this here, or do we not know enough about the passes?
I think this should work, the problem is that you might have to recurse
and do some other funky stuff.  Imagine you have the following situation:

PM.add(functionpass A)
PM.add(functionpass B, which uses A)
PM.add(modulepass C, which uses B)

In this situation, the pass manager would have to clone not just the B
objects, but also the A objects for every function.

The other tricky thing is that we don't know how many pass objects to
create until we actuall start running the pass manager (it depends on the
module being run on).
> 2 - in addPass(SubPassClass, ...), add those FPs to CurrentAnalyses.
> Should we have a map of BatcherClasses - (function, BatcherClass) pairs
> instead of just one BatcherClass?
I'm not sure about this.  At the time add is called, you don't know what
the functions are.  I think that the correct solution is to just build up
more-or-less what we already have, but when a functionpass is marked used
by a pass, the funciton pass should be marked as clonable.

At function-pass-run-time, we should call clone() (a new method on
function passes), to create one copy of each marked function pass for each
non-external function in the module (only if the function pass is marked
as being used by a Pass obviously :) )

These clones can be stored in in a map from Function* -> FunctionPass*.

Writing the clone() method for FunctionPass objects is an annoying thing
to have to do, but is purely mechanical.
> 3 - Provide API for the MP to get an analysis per function. (generally,
> for the PassClass to get analysis per SubPassClass):
>
> Instead of this:
> getAnalysis<PassType>()
> the natural thing would seem to be (for PassClass = MP and SubPassClass
> = FP):
> getAnalysis<PassType>(Function)
Yes.  This makes a lot of sense.  In the future, only the "ModulePass"
class will have this new getAnalysis<T>(Function*) method, but for now it
will go into the Pass class (where everyone will get it).
> This simple change does mean some big moving in the background, though,
> since (for starters) the PassInfoMap can't just key on the TypeInfo
> anymore. It will need to key on something like a structure with TypeInfo
> and the unit of code that the pass is attached to. I have a feeling
> there are similar instances where PassInfo needs code-unit info attached
> to it...
>
> Any comments/clarifications/suggestions?
I think that a lot of this can be moved to runtime.  In particular, when
the PM is constructed, we only need to (and only can) create one instance
of each pass.  At runtime, they need to be cloned and destroyed as
appropriate.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://nondot.org/sabre/

On Aug 9, 2004, at 1:46 PM, Chris Lattner wrote:
>> Well, I took a look at it a bit over the weekend. I am probably not 
>> the
>> right person to do the complete rewrite, for instance reworking the
>> Pass class hierarchy doesn't sound like something I'd want to
do. Just
>> getting to this point has been a bit of an education in real C++.
>
> Ok, fair enough.  It's a pretty big piece of work.  I would recommend
> starting a bit smaller in the world of LLVM, then working up to the big
> stuff. :)
Sounds like good advice. I've been advised to hold off working on this 
problem as long as it isn't on my critical path. However, some free 
time spent on it can't hurt. Maybe if I talk about it enough I'll 
inspire someone else to work on it. :)
>>
>> 1 - in add(), discover that the pass we're requiring is a subpass,
and
>> create more of them. This is the natural place to do it, but can we do
>> this here, or do we not know enough about the passes?
>
> I think this should work, the problem is that you might have to recurse
> and do some other funky stuff.  Imagine you have the following 
> situation:
>
> PM.add(functionpass A)
> PM.add(functionpass B, which uses A)
> PM.add(modulepass C, which uses B)
>
> In this situation, the pass manager would have to clone not just the B
> objects, but also the A objects for every function.
>
> The other tricky thing is that we don't know how many pass objects to
> create until we actuall start running the pass manager (it depends on 
> the
> module being run on).
Yeah, this sounds like the key problem.
>> 2 - in addPass(SubPassClass, ...), add those FPs to CurrentAnalyses.
>> Should we have a map of BatcherClasses - (function, BatcherClass) 
>> pairs
>> instead of just one BatcherClass?
>
> I'm not sure about this.  At the time add is called, you don't know
> what
> the functions are.  I think that the correct solution is to just build 
> up
> more-or-less what we already have, but when a functionpass is marked 
> used
> by a pass, the funciton pass should be marked as clonable.
>
> At function-pass-run-time, we should call clone() (a new method on
> function passes), to create one copy of each marked function pass for 
> each
> non-external function in the module (only if the function pass is 
> marked
> as being used by a Pass obviously :) )
>
> These clones can be stored in in a map from Function* -> FunctionPass*.
>
> Writing the clone() method for FunctionPass objects is an annoying 
> thing
> to have to do, but is purely mechanical.
Would you have to write clone() for every FunctionPass subclass?
It's not clear to me why cloning would have to be different from
just creating a new Pass with the default constructor...
>> 3 - Provide API for the MP to get an analysis per function. 
>> (generally,
>> for the PassClass to get analysis per SubPassClass):
>>
>> Instead of this:
>> getAnalysis<PassType>()
>> the natural thing would seem to be (for PassClass = MP and 
>> SubPassClass
>> = FP):
>> getAnalysis<PassType>(Function)
>
> Yes.  This makes a lot of sense.  In the future, only the
"ModulePass"
> class will have this new getAnalysis<T>(Function*) method, but for
now
> it
> will go into the Pass class (where everyone will get it).
alright.
>> This simple change does mean some big moving in the background, 
>> though,
>> since (for starters) the PassInfoMap can't just key on the TypeInfo
>> anymore. It will need to key on something like a structure with 
>> TypeInfo
>> and the unit of code that the pass is attached to. I have a feeling
>> there are similar instances where PassInfo needs code-unit info 
>> attached
>> to it...
>>
>> Any comments/clarifications/suggestions?
>
> I think that a lot of this can be moved to runtime.  In particular, 
> when
> the PM is constructed, we only need to (and only can) create one 
> instance
> of each pass.  At runtime, they need to be cloned and destroyed as
> appropriate.
>
Do we really need to instantiate the passes when the PM is constructed?
If we have to do some pass creation and scheduling at runtime anyway,
it seems conceptually simpler to just do it all then - have add() be
really simple, then do all the work in run().

I'm not aware of all the issues surrounding why it is the way it is now,
but it doesn't seem like there's an efficiency issue with doing it at a
different step, and it might be simpler to implement by doing all the
instantiation of Passes in one place. Also, it might help avoid a
distinction between creation and cloning.

What do you think?

-mike