[LLVMdev] Register Pressure Computation during Pre-Allocation Scheduling

[Jakob Stoklund Olesen]

On Aug 16, 2011, at 2:08 AM, Ghassan Shobaki wrote:

> I know that phase ordering is a non-trivial problem that does not have a perfect solution (like most compiler optimization problems!), but I wonder why LLVM runs such passes between scheduling and allocation. One would expect a register pressure reduction pass to be placed as close as possible to the register allocation pass.

Since SelectionDAG is a graph and MachineInstr is linear, some kind of scheduling needs to take place when converting the intermediate representation.

We are looking at placing a scheduler between coalescing and register allocation. There are complications such as keeping the  LiveIntervals data structure updated, and dealing with code that is no longer in SSA form.

Compile time is also a major concern. Out-of-order processors don't benefit much from ILP scheduling except in special cases, so it is not clear that an extra scheduler is worth the compile time. That depends on the target machine, of course.

> Ideally, you would like to have an integrated algorithm that does allocation and scheduling simultaneously, but such an integrated solution is usually not implemented due to its complexity. So, my questions are:
> (1) CSE naturally tends to increase reg pressure. Is there any particular reason for doing CSE between scheduling and allocation instead of doing it, say before scheduling?

CSE and LICM are generally performed on the LLVM IR before instruction selection. The late passes exist to exploit opportunities created by instruction selection.

SelectionDAG is a per-block data structure, so these global passes must run on the MachineInstr representation.

> (2) How easy will it be to change the phase ordering in LLVM without breaking things? Where is the phase ordering done? How do we know if there are dependencies among certain phases?

You cannot reorder passes that work on different intermediate representations.

> >These DAG nodes are also used to copy to/from physical registers before and after calls.
> >Virtual registers defined by PHI instructions will also appear as CopyFromReg operands.
> 
> Ghassan: So, is there a way to distinguish the ones that represent live-in and live-out regs?

Look for virtual registers.

/jakob

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110816/f1014c47/attachment.html>