Re: basic question on register allocation (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Mon, 25 Feb 2008 11:29:11 +0100

          From comp.compilers

Related articles
basic question on register allocation (2008-02-20)
Re: basic question on register allocation (Max Hailperin) (2008-02-24)
Re: basic question on register allocation (2008-02-25)
Re: basic question on register allocation (2008-02-28)
| List of all articles for this month |

From: (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers
Date: Mon, 25 Feb 2008 11:29:11 +0100
Organization: Department of Computer Science, University of Copenhagen
References: 08-02-059
Keywords: registers
Posted-Date: 25 Feb 2008 09:56:59 EST 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 .

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.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.