PassManager

Project Infrastructure LLVM Dev List Archives
1

Hi All,

I am planning to re-implement PassManager in llvm 2.0. The goal is to address

   http://nondot.org/sabre/LLVMNotes/Inliner-PassManager.txt and
   http://nondot.org/sabre/LLVMNotes/LoopOptimizerNotes.txt

and other crazy ideas Chris has. Current implementation of PassManager is very complex. Initially I attempted to update it to address above notes but realized that redoing PassManager in simple way makes more sense, and Chris agreed. Instead of replacing current PassManager with new PassManager in one big scoop I'm going to follow these steps:

1) Rename existing Managers using _X suffix.
2) Introduce new PassManager skeleton
3) Add functionality in new Pass Manager
4) Start Using new Pass Manager
5) Remove existing Pass Manager
6) Implement LoopPassManager
7) Update existing Loop transformations to conform LoopPassManager

2

Hi Devang,

3

Chris and Devang,

Before you implement the LoopPassManager class, I'd like to discuss this a little bit. I have a suggestion and a question; we can discuss this now or later, as you wish:

1. The LoopPassManager might become much simpler if the more complex loop passes are given control over how they iterate over the loops, rather always rely on the manager to enumerate the loops in some fixed order. Then the pass could be responsible for making sure that it handles issues like loops that are deleted during the pass. For example, some algorithms make internal decisions about which loops to handle together and also what order to visit them. For example, the LoopFusion class may need to inspect loop headers to decide which subsets of loops to fuse and then fuse them as it goes.

I think you could do this just by adding an iterator method somewhere that enumerates sets of loops (i.e,. returns a vector of Loop objects). The bottom-up iterator could just be a default choice.

2. The question is how you plan to handle unimodular transformations. I think it's a very nice abstraction and a number of loop transforms should be implemented using that rather than more ad hoc code, e.g., interchange, reversal, skewing. But that requires implementing support for unimodular transforms before those passes are implemented.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

4

Hi Vikram,

Chris and Devang,

Before you implement the LoopPassManager class, I'd like to discuss
this a little bit. I have a suggestion and a question; we can
discuss this now or later, as you wish:

1. The LoopPassManager might become much simpler if the more complex
loop passes are given control over how they iterate over the loops,
rather always rely on the manager to enumerate the loops in some
fixed order. Then the pass could be responsible for making sure that
it handles issues like loops that are deleted during the pass.

LoopPassManager will manage the LoopInfo. It will maintain loop priority queue and expose APIs to add/remove loops that transformations can use.

For
example, some algorithms make internal decisions about which loops to
handle together and also what order to visit them. For example, the
LoopFusion class may need to inspect loop headers to decide which
subsets of loops to fuse and then fuse them as it goes.

LoopPassManager will expose two virtual methods.

1) runOnLoop(Loop &L, LoopPassManger &LPM)

      Loop transformation can override to process this particular loop.

2) runOnFunctionBody(Function &F, Loop&L, LoopPassManager &LPM)

     LoopFusion and others can override this to to analyze and process multiple loops.

I think you could do this just by adding an iterator method somewhere
that enumerates sets of loops (i.e,. returns a vector of Loop
objects). The bottom-up iterator could just be a default choice.

2. The question is how you plan to handle unimodular
transformations. I think it's a very nice abstraction and a number
of loop transforms should be implemented using that rather than more
ad hoc code, e.g., interchange, reversal, skewing. But that requires
implementing support for unimodular transforms before those passes
are implemented.

I have not yet spent enough time to think about unimodular transformation framework implementation.

5

Devang,

I read Chris's notes so I got all this information there already. My comments were in response to that.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

6

In that case I completely missed your question :slight_smile: Do you suggest that complex loop passes iterates of all loops in the function by themselves (instead of LPM handing them instance of loop to process)?

7

I read Chris's notes so I got all this information there already. My
comments were in response to that.

It's unclear what you're missing then: fusion can be easily handled by the framework. Unimodular transform support is orthogonal to the pass framework and could be built as a later step. Am I misunderstanding your question?

-Chris

8

I think I see the issue here. The point of the pass manager (in general) is for passes to *give up control* over iteration order in order for obtain something else. For example, function passes give up control over which order functions are processed in. This allows pipelining of a function through multiple function passes before the next function is processed. If each functionpass could define its own iteration order, this wouldn't work. Note that no generality is lost here: passes that don't fit the FunctionPass mold can be made into ModulePasses.

The LoopPassManager is the same thing. The idea is that the LPM provides structured iteration among loop pass classes. I believe that most loop transformations will fit into the framework, and will thus enjoy the benefits of it. Those that don't can alway be FunctionPasses.

-Chris

9

1. The LoopPassManager might become much simpler if the more complex
loop passes are given control over how they iterate over the loops,
rather always rely on the manager to enumerate the loops in some
fixed order. Then the pass could be responsible for making sure that
it handles issues like loops that are deleted during the pass. For
example, some algorithms make internal decisions about which loops to
handle together and also what order to visit them. For example, the
LoopFusion class may need to inspect loop headers to decide which
subsets of loops to fuse and then fuse them as it goes.

I think I see the issue here. The point of the pass manager (in general)
is for passes to *give up control* over iteration order in order for
obtain something else.

Right, I understand that. I think that works fine in most cases. For loop passes, though, this approach is causing some of the complexity issues you talked about in your notes. You could avoid them, and also make some loop passes, more natural to write if you relaxed this policy and allow a transformation algorithm to choose what subsets of loops to visit at a time.

For example, function passes give up control over
which order functions are processed in. This allows pipelining of
a function through multiple function passes before the next function is
processed. If each functionpass could define its own iteration order,
this wouldn't work. Note that no generality is lost here: passes that
don't fit the FunctionPass mold can be made into ModulePasses.

The LoopPassManager is the same thing. The idea is that the LPM provides
structured iteration among loop pass classes. I believe that most loop
transformations will fit into the framework, and will thus enjoy the
benefits of it. Those that don't can alway be FunctionPasses.

Yes, I agree -- you can't and shouldn't try to make LPM handle all possible cases. But if you can make the LoopPassManager more flexible and simpler at the same time, that seems worthwhile.

--Vikram

10

The idea is that the LPM (roughly) runs *all* the loop passes on an inner loop, then runs them all on an outer loop.

How could it allow individual passes to control order of loop visitation?

-Chris

11

I think I see the issue here. The point of the pass manager (in
general)
is for passes to *give up control* over iteration order in order for
obtain something else.

Right, I understand that. I think that works fine in most cases.
For loop passes, though, this approach is causing some of the
complexity issues you talked about in your notes. You could avoid
them, and also make some loop passes, more natural to write if you
relaxed this policy and allow a transformation algorithm to choose
what subsets of loops to visit at a time.

The idea is that the LPM (roughly) runs *all* the loop passes on an inner
loop, then runs them all on an outer loop.

Right, I understand that is the normal policy, but ...

How could it allow individual passes to control order of loop visitation?

... you would relax that policy for cases where the pass wants control over its order of visitation. In fact , some passes (e.g., loop tiling) may want to do two or more transforms on a set of loops at a time. E.g., loop tiling needs to do strip-mining on a loop, then interchange one of the resulting loops with *some* outer loop (which one depends on the pattern of accesses in the code). It would be nice for the LPM to have the flexibility to accommodate such passes better than just requiring them to always work at the outermost loop level.

Note that this is just one example. All that is needed is an optional iterator method or callback method of some kind in the loop pass. If unimplemented, it uses the default order.

12

I think that the design will handle this. This isn't a matter of changing order of iteration. This is a matter of making sure that the new loops that are created get revisited. This is exactly what the worklist is design for.

In any case, Devang has plenty of things to do to the current pass mgr and the current loop optimizations before we start worrying about new optzns. When that happens we'll have experience from moving the extant loop optimizers over to guide the right design.

-Chris

13

Yes, I agree. Let's talk about this when he gets to the stage of writing the LPM or adding new loop optimizations.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/