passmanagert and co improvement...

[Saem_Ghani]

Okay, I've been studying passmanagert and company for quite a while.
Here are my conclusions.

It's actually not nearly as bad as I thought.

I'll outline the problem as I see it.

We want to be able to manage the way passes traverse things, in
particular a module's worth of functions. As was in your example, we
want inliner and mem2reg calls interleaved, as we traverse functions
in callgraphscc order. More generally, we want the ability to specify
traversals. And specify passes that should use these traversals.

Currently, when you tell a function pass to go to work on a module, it
iterates through the module, as it pleases. Now, this behaviour is
fine, but insufficient.

What we want is the ability to say, function pass, "run on traversal".
As in, we'll provide an iterator and you work on that instead, a
pseudo module if you like.

Now, for actually specifying the traversals, we want to tell the
passmanager, A, B, and C are traversal strategies that we wish to use.
This is a way of saying, not only run said passes, but use them for
traversal -- this has implications on life times. Now, when we add a
plain old pass, we CAN say, add a pass with traversal strategy A or B
or C, or it'll default to run on module/whatever.

Passmanager, would require a couple of extra methods to expose this
new traversal management flexibility.

Traversal strategies, this is controvertial, here I want to have all
analysis we wish to use as traversal strategies to inherit from some
class, which provides an accessor to get a simple forward iterator, or
something in that vein.

Now, unless I'm not seeing the difficulty in this, it shouldn't be TOO
bad to implement the logic. I could also be missing significant
design issues.

As for clean ups in passmanagert, I think the first thing might be
cutting down some of those insane multipage functions with private
helper functions, since they're one offs, we can easily inline them,
not to mention, they make things far more readable than large "code
barf". Maybe, it's just me, but I can't stand big methods/functions.
Overall, it's not all that bad.

[clattner]

Okay, I've been studying passmanagert and company for quite a while.
Here are my conclusions.
It's actually not nearly as bad as I thought.
I'll outline the problem as I see it.

ok.

We want to be able to manage the way passes traverse things, in
particular a module's worth of functions. As was in your example, we
want inliner and mem2reg calls interleaved, as we traverse functions
in callgraphscc order. More generally, we want the ability to specify
traversals. And specify passes that should use these traversals.

Yes sort of. I'm going to rearrange your email here a bit.

As for clean ups in passmanagert, I think the first thing might be
cutting down some of those insane multipage functions with private
helper functions, since they're one offs, we can easily inline them,
not to mention, they make things far more readable than large "code
barf". Maybe, it's just me, but I can't stand big methods/functions.
Overall, it's not all that bad.

Yes. To start with, I would suggest seriously refactoring PassManagerT.h into something that is object oriented instead of template instantiated.
Right now, there is the PassManagerT template class and the various traits classes it uses. This is instantiated three times for module function and basic blocks.

This design was due to the wrong-minded assumption that the performance of the PassManager was critical. As it turns out (and should have been obvious back in early 2002 when I wrote it), passes have enough granularity that a little bit of overhead in the PassManager (due to virtual function calls) is just fine.

As such, the first step is to start refactoring the pass manager into a common base class (PassManager) and three derived classes (ModulePassManager, FunctionPassManager, BasicBlockPassManager) and move the methods from the traits class to be pure virtual methods implemented by the derived classes.

If you take up this project, please do things incrementally in small chunks (e.g. a method at a time). This will make reviewing your changes much easier.

Once this is done, we can move on to making the pass manager better at what it does!

Currently, when you tell a function pass to go to work on a module, it
iterates through the module, as it pleases. Now, this behaviour is
fine, but insufficient.

Sort of. In reality, the FunctionPass's are all run by the FunctionPass manager that iterates over the functions in a module in a fixed order and calls the runOnFunction method of each at the right time. There are many future improvements (like extending this) that we want to do in the future, but are limited by the complexity of the current design.

What we want is the ability to say, function pass, "run on traversal".
As in, we'll provide an iterator and you work on that instead, a
pseudo module if you like.

Now, for actually specifying the traversals, we want to tell the
passmanager, A, B, and C are traversal strategies that we wish to use.
This is a way of saying, not only run said passes, but use them for
traversal -- this has implications on life times. Now, when we add a
plain old pass, we CAN say, add a pass with traversal strategy A or B
or C, or it'll default to run on module/whatever.

To me, I'd rather this be a new passmanager derived class than a traversal policy.

Passmanager, would require a couple of extra methods to expose this
new traversal management flexibility.

Yup.

Now, unless I'm not seeing the difficulty in this, it shouldn't be TOO
bad to implement the logic. I could also be missing significant
design issues.

There isn't anything necessarily super hard here, it's just that the code is needlessly complex and *very* critical to LLVM. As such, we should make lots of small steps instead of a couple big ones. It would be really cool if you started on this project!

-Chris