How to get LoopInfo within Pass subclass?

[Michael_McCracken1]

Hi, I have a hopefully quick question. I'm writing a Pass that needs to see a whole module at a time and keep some state, so I subclassed Pass. However, I want to be able to see the Loops in each Function. Roughly, here's what I want:

virtual bool run(Module &M){
     // do stuff...
     for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I){
      if(! I->isExternal()) visitFunction(*I);
     }
  // ...
       return false;
}

virtual void visitFunction(Function &F){
     LoopInfo *LI = &getAnalysis<LoopInfo>();
     std::vector<Loop*> SubLoops(LI->begin(), LI->end());
     for(unsigned i = 0, e = SubLoops.size(); i != e; ++i){
     // visit SubLoops[i];
     }
}

So, I add LoopInfo as a required analysis:

virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesAll();
       AU.addRequired<LoopInfo>();
};

However, when running I'm informed that:

PassManagerT.h:421: failed assertion `getAnalysisOrNullUp(P) && dynamic_cast<ImmutablePass*>(getAnalysisOrNullUp(P)) && "Pass available but not found! " "Perhaps this is a module pass requiring a function pass?"'

I couldn't find a clear explanation of which passes can require which other ones, and I'm a little confused as to whether what I want is even possible. How can I say that I want LoopInfo for each Function in my Module?

PS, if I'm not just missing it, and this is a gap in the docs, I'd be glad to try writing something to fill the gap. It'd probably be a good way to learn more about LLVM.

Thanks,
-mike

[clattner]

Hi, I have a hopefully quick question. I'm writing a Pass that needs to
see a whole module at a time and keep some state, so I subclassed Pass.
However, I want to be able to see the Loops in each Function. Roughly,

ok.

However, when running I'm informed that:

PassManagerT.h:421: failed assertion `getAnalysisOrNullUp(P) &&
dynamic_cast<ImmutablePass*>(getAnalysisOrNullUp(P)) && "Pass available
but not found! " "Perhaps this is a module pass requiring a function
pass?"'

I couldn't find a clear explanation of which passes can require which
other ones, and I'm a little confused as to whether what I want is even
possible. How can I say that I want LoopInfo for each Function in my
Module?

Unfortunately this is a big missing feature in the pass management system.
In particular, as the assertion says, a "Pass" cannot yet require a
"FunctionPass". The reason this is tricky is that each (e.g.) LoopInfo
instance contains loop information for one function. When we allow Pass
objects to require FunctionPass objects, the PassManager will have to
instantiate one FunctionPass for each function in the module.

This is clearly something that we want to do, but unfortunately we can't
do it yet. This is actually mentioned here, though I'm not suprised you
missed it:
http://llvm.org/docs/WritingAnLLVMPass.html#PassFunctionPass

As a work-around you can make your "Pass" object work as a FunctionPass.
I don't know what this will do to the logic in the pass, but if this is an
option, it would be the best way to go.

You're right that FunctionPass's are not supposed to have state (something
that many people overlook ), however, for now, nothing will break if it
does have state, and this is really the only way around this. However, if
you want to work on the PassManager, please let us know!

-Chris

[Michael_McCracken1]

Hi, I have a hopefully quick question. I'm writing a Pass that needs to
see a whole module at a time and keep some state, so I subclassed Pass.
However, I want to be able to see the Loops in each Function. Roughly,

ok.

However, when running I'm informed that:

PassManagerT.h:421: failed assertion `getAnalysisOrNullUp(P) &&
dynamic_cast<ImmutablePass*>(getAnalysisOrNullUp(P)) && "Pass available
but not found! " "Perhaps this is a module pass requiring a function
pass?"'

I couldn't find a clear explanation of which passes can require which
other ones, and I'm a little confused as to whether what I want is even
possible. How can I say that I want LoopInfo for each Function in my
Module?

Unfortunately this is a big missing feature in the pass management system.
In particular, as the assertion says, a "Pass" cannot yet require a
"FunctionPass". The reason this is tricky is that each (e.g.) LoopInfo
instance contains loop information for one function. When we allow Pass
objects to require FunctionPass objects, the PassManager will have to
instantiate one FunctionPass for each function in the module.

This is clearly something that we want to do, but unfortunately we can't
do it yet. This is actually mentioned here, though I'm not suprised you
missed it:
Writing an LLVM Pass — LLVM 18.0.0git documentation

OK. Yeah, I stopped reading after I saw the first 'future extension'. Woops.

As a work-around you can make your "Pass" object work as a FunctionPass.
I don't know what this will do to the logic in the pass, but if this is an
option, it would be the best way to go.

You're right that FunctionPass's are not supposed to have state (something
that many people overlook ), however, for now, nothing will break if it
does have state, and this is really the only way around this.

I'm not sure if I can do this. The pass I'm writing is writing info about the module and its parts to a file, so I need to see the module, if only to print its moduleIdentifier.

I'm not sure if there's a way to get the Module that a Function belongs to from within a FunctionPass. If I could do that, and cheat by keeping some state, I could do what I want as a FunctionPass. Am I missing something, or is that not possible?

Also, out of curiosity, why the stateless restriction - is it because passes may someday be run in parallel?

However, if you want to work on the PassManager, please let us know!

This depends. If it's really in my way, I may have little choice. I would like to make a contribution, though, and it didn't actually sound too bad. Any guess what amount of work that'd be?
Assume I have a passing familiarity with the LLVM architecture, slightly rusty average C++ skills, and little shame in asking questions.

-mike

[clattner]

> You're right that FunctionPass's are not supposed to have state
> (something that many people overlook ), however, for now, nothing
> will break if it does have state, and this is really the only way
> around this.

I'm not sure if I can do this. The pass I'm writing is writing info
about the module and its parts to a file, so I need to see the module,
if only to print its moduleIdentifier.

Ok

I'm not sure if there's a way to get the Module that a Function belongs
to from within a FunctionPass. If I could do that, and cheat by keeping
some state, I could do what I want as a FunctionPass. Am I missing
something, or is that not possible?

Sure, you can do that. Just use F->getParent() to get to the Module.

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.

> However, if you want to work on the PassManager, please let us know!

This depends. If it's really in my way, I may have little choice. I
would like to make a contribution, though, and it didn't actually sound
too bad. Any guess what amount of work that'd be? Assume I have a
passing familiarity with the LLVM architecture, slightly rusty average
C++ skills, and little shame in asking questions.

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

If you'd rather not work on it, that's also cool. Someone will eventually
get to it, though it's not on anyones "short list" AFAIK.

-Chris

[Michael_McCracken1]

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

[clattner]

> 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

[Michael_McCracken1]

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

[clattner]

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.

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

Yes, we would need them. Most passes are created with a default ctor (in
fact, all those that are "required" are, which might be enough to get
around this, but...), but there are some that are created with ctor
arguments when added to the pass manager. In particular, it's perfectly
legal to do stuff like this:

PM.add(new FunkyPass(1, 2, 3, 4));

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

Yup, we do that. In particular, the passes explicitly added to the pass
manager are. The passes implicitly required could potentially be deferred
to run-time, but I'm not sure what the gain would be. In particular, if B
requires A, you could have:

PM.add(B);

or you could have:

PM.add(A);
PM.add(B);

which should run exactly the same stuff (A should not be run twice).

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.

I don't think it would be an efficiency issue, but we have to handle cases
like the above anyway, so I don't think it would save us anything...

-Chris