[LLVMdev] Need advice on writing scheduling pass

[Andrew Trick]

On May 24, 2011, at 9:59 AM, Jakob Stoklund Olesen wrote:

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

This is only worth doing if these assumptions are valid:

- The SSA form embedded in liveintervals permits efficient DAG construction

- liveintervals are easy and cheap to update within an extended basic block (contiguously laid out blocks with no merges)

- Inserting copies to break interferences is easy to do prior to physical regalloc, and the corresponding liveinterval update is cheap. This is very different from creating physreg copies, when you may not have any free physregs!

Presenting the scheduler with coalesced virtual registers doesn't need to constrain the schedule. It really provides better information to the schedule. post-RA-sched is only left to cleanup split/spill code--a localized problem.

-Andy