johnhull2008@[EMAIL PROTECTED]
writes:
> I have a very basic question on register allocation, the answer to
> which I cannot find in any textbook.
>
> Suppose you have a code that consists of 4 instructions before
> register allocation, and registers are all virtual, like in SSA
> format. The first operand is the destination, the remaining two
> operands are the sources. The architecture I have in mind is a
> textbook pipelined RISC, like the one you find in H&P architecture
> books.
>
> 1. add R0, R1, R2
> 2. add R3, R4, R5
> 3. add R6, R7, R8
> 4. add R9, R0, R10
>
> Suppose after constructing an interference graph, the register
> allocator decided R0 must be spilled, since it interferes with at
> least 5 registers.
> R0 - R4, R5, R7, R8, R10
>
> Here is the code after insertion of spill and fill codes:
> 1. add R0, R1, R2
> (1-spill.) store (loc), R0
> 2. add R3, R4, R5
> 3. add R6, R7, R8
> (1-fill.) load R0, (loc)
> 4.add R9, R1, R10
>
> My question is, how does this code remove the interference between R0
> and the other registers? When instruction 1. completes and writes back
> to the register file, it still consumes a physical register (although
> just for one cycle), so there should be interferences remaining.
When you do register allocation, you assign variables to registers, so
saying register 0 is spilled is a bit misleading -- you spill
variables, not registers. You can argue that your names R0, ..., R10
are variable names and not register names, so your register allocation
assigns these to registers. These need not be registers 0 - 10.
When spilling the variable R0, you can do two things:
1. Keep the name R0 for all occurences of the original variable and
insert the required load/stores before and after these occurences.
R0 will (with normal colouring allocation) be assigned to the same
register throughout. It is live at fewer points in the code, so
it might be possible to colour it when it was not possible before.
But you can get into situations where even spilling all variables
isn't enough to permit colouring, as every variable may still
interfere with each other.
2. Rename all occurences of R0 to different names (and still add
load/stores, but now to these renames variables). After spilling
the variable R0, the code will, hence, look like this:
1. add R0_1, R1, R2
(1-spill.) store (loc), R0_1
2. add R3, R4, R5
3. add R6, R7, R8
(1-fill.) load R0_2, (loc)
4.add R9, R0_2, R10
R0_1 will only interfere with variables live at instruction 1 and
R0_2 will only interfere with variables live at instruction 4, and
it is possible to allocate these in different registers. Spilling
all variables bounds the required colours to the number of input
registers to one instruction, so it is always possible to allocate
after spilling.
Option 2, generally, makes successful colouring much more likely.
It is the technique described in my compiler book, which you can
download from http://www.diku.dk/~torbenm/Basics
.
Note that SSA form gives the same benefit, as it _will_ give the
different occurrences of R0 different names after spilling. SSA often
reduces spill in the first place, as the renamed variables have
shorter live ranges and can be allocated to different registers. The
cost is that some phi-nodes need move-instructions (where they are
no-ops if the renamed variants are allocated in the same register).
Generally, it is useful to do some kind of conservative coalescing or
biased colouring when register allocating SSA code to keep as many
phi-nodes as possible as no-ops.
Torben
|
