[LLVMdev] Need advice on writing scheduling pass

[Jakob Stoklund Olesen]

On May 24, 2011, at 8:22 AM, Jonas Paulsson wrote:

> Hi (Jakob),
> 
> in reference to the prior message below, I have the following follow-up questions, as I also need a scheduling pass 
> prior to regalloc. I need to do this in order to set VLIW-flags, so that the RA is aware of several MI's
> per cycle with a redefined LiveRange::overlap-function. On a multiple-issue cycle, a register that gets killed
> can be reused by another MI - these live ranges do not then overlap.

Redefining overlap() won't work for that. There is other code assuming that overlap means overlap, for example the LiveIntervalUnion used by the new register allocators.

For VLIW, you probably want to number your packets instead of individual instructions. We don't have any VLIW support, so nobody has thought about how best to do it.

> Well, I would like to schedule the VLIW code after SimpleRegisterCoalescer, so that I get more or less the 
> final code to work with. As the instructions are rearrange, I suppose I must run the SlotIndexes and 
> LiveIntervals again. LiveVariables should also be refreshed as a register might get killed with a different
> MI if two users change place, etc, I suppose.
> 
> I would like to just rerun these passes, but you said below that LiveIntervals do not work after SSA form is
> abandoned.
> 
> I wonder how you mean to update the live intervals after scheduling -- the slot indexes must surely be useless
> with a changed order of MI's?
> 
> Do you know of a scheme to rewrite these passes so that they can be rerun as needed? Is all but LiveIntervals
> ok with this as of now?

So the good news is that we are slowly moving towards a similar design. The bad news is that we are *slowly* moving...

Currently, the register allocator super-pass contains these passes:

- LiveVars
- PhiElim
- TwoAddr
- LiveIntervals
- Coalescing
- RegAlloc

Currently, LiveVars requires SSA form, and LiveIntervals only works with simple multi-defs as produced by PhiElim and TwoAddr. That means the pass order is fixed.

The plan is to teach PhiELim and TwoAddr how to update LiveIntervals so it can run earlier:

- LiveVars
- LiveIntervals
- PhiElim
- TwoAddr
- Coalescing
- RegAlloc

Then we can eliminate LiveVars completely:

- LiveIntervals
- PhiElim
- TwoAddr
- Coalescing
- RegAlloc

This version of LiveIntervals will compute liveness autonomously, but it is very likely to also require SSA form because of the possible speedups.

The next step is to merge PhiElim and TwoAddr into a SuperCoalescer pass:

- LiveIntervals
- SuperCoalescing
- RegAlloc

Finally, Andy also wants to schedule after coalescing:

- LiveIntervals
- SuperCoalescing
- Schedule
- RegAlloc

We don't have any concrete plans for how that scheduler would look. It would likely benefit from the existing LiveIntervals, at least the embedded SSA form is essential.

It is not clear if such a scheduler should preserve live intervals or if everything should be recomputed. There are also phase ordering issues; the scheduler would be severely constrained by our very aggressive coalescing, and it would expose further coalescing opportunities that RegAlloc probably wouldn't be able to exploit fully.


But if you want to add a VLIW scheduler tomorrow, I don't know what to tell you. It's a big project.

/jakob