Register allocation and spilling, the easy way?

Question

I'm looking for a way to allocate local variables to registers. I'm aware of a couple of serious methods for doing it (namely, those mentioned on Wikipedia), but I'm stuck on how "spilling" is accomplished. Also, the relevant literature is quite intimidating. I'm hoping there's something simpler that will satisfy my priorities:

1. Correctness -- an algorithm that will generate correct code regardless of how many local variables there are.
2. Simplicity -- something I can understand without having to read too much literature.
3. Efficiency -- it needs to be better than the current method, which is:

Translate an operation x = y # z to:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

As I'm targeting Intel 386, some relevant constraints are:

• Binary operations take two arguments, one of which is a source and destination. Unary operations take a single argument.
• Operations can only access one memory location; binary operations therefore need at least one argument in a register.
• There is a maximum of six registers available: %eax %ebx %ecx %edx %esi %edi. (%ebp could also be included as a last resort.)
• There are special cases such as for integer division and return registers, but I can ignore them for now.

There are three steps the compiler gets through at the moment:

• i386ification: all operations are converted to a form a = a # b (or a = #a for unary operations).
• Liveness analysis: the sets of live variables before and after each operation are determined.
• Register allocation: an interference graph is built and coloured.

And then the compiler throws its crayons in the air and doesn't know what to do next.

Example

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Here's the rather pretty interference graph for the function, and the CFG with liveness information. The CFG image does require some vertical scrolling, unfortunately.

• Interference graph for a function on 14 variables
• Control-flow graph for a function, with liveness information

Seven colours were used. I would like to spill one of them (or the set of variables assigned that colour). The method of choosing which isn't too important. What gets tricky is how to deal with the spilt variables.

Let's say I spill "pink", which is the set of variables t, $t4, $t7. This means that those operations referring to one of these variables will access it from its position on the stack frame, rather than through a register. This should work for this example.

But what if the program was:

...
a = a + b
...

and both a and b had to be spilled? I can't emit an instruction addl b, a with two memory addresses. I would need another spare register to temporarily hold one of the operands, and that means spilling another colour. This suggests a general method of:

1. If all variables can be coloured with r colours, great!
2. Otherwise, spill some colours and their associated variables.
3. If an operation exists that accesses two spilled variables, spill another colour and use the spare register for temporary storage for all such operations.

At this point I would suspect that a lot more stuff is being spilled than necessary, and wonder if there is some smarter way to spill things, such as spilling part of a variable's lifetime, rather than the whole variable itself. Are there some simple(ish) techniques that I could use here? Again, I'm not aiming particularly high -- certainly not high enough to require reading anything too deep. ;-)

Specific problems

The main specific problem is: when a variable is spilled, how does this affect the instructions generated? Do all instructions using that variable need to access it directly in memory (from its stack position) ? How will this work if an operation uses two spilled variables? (The architecture does not permit instructions to access two distinct memory locations.)

Secondary problems are:

• How do I determine where to insert load/store instructions, for correctness (and less importantly, efficiency) ?
• Can I spill a variable for only that part of its lifetime when it is not in immediate use, and unspill it later? So that all instructions act on unspilled registers. A variable might live in different registers at different times.
• Can I be a little more efficient with special cases. For example, %eax is used for the return value, so it would be nice if the variable to be returned happened to be allocated to that register by the time the return was encountered. Similarly, some registers are "callee-save", so if fewer variables happened to be live at the time of a function call, having them allocated to non-callee-save registers would mean I can avoid storing those registers.
• Would SSA form help much (if at all) ? Being able to eliminate common subexpressions and evaluate constants might reduce(?) register pressure, but otherwise would it have any effect?

The aspects I'm not concerned about (right now) are:

• Stack allocation and optimisation: it's implemented naively already, and can be optimised using the interference graph if need be.
• Compile-time efficiency, just as long as it terminates. (NP-completeness does not imply a given algorithm should be avoided.)

Update

Sorry about the downtime -- I've been thinking about the answers given and trying to find an easy approach to take to start implementing some of the ideas. To be honest, I've been procrastinating... :-\

I found the very nice presentation (PPT, sadly):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

Which answers the question about how to deal with specific operation needs (like using the same register for source and destination; or needing a certain register for some operations). What I'm not sure about is whether the Liveness-Colouring-Allocation cycle terminates.

I'll try to do some actual work soon and hopefully close the question.

Answer 1

I've used a greedy approach in a JVM allocator once, which worked pretty well. Basically start at the top of a basic block with all values stored on the stack. Then just scan the instructions forward, maintaining a list of registers which contain a value, and whether the value is dirty (needs to be written back). If an instruction uses a value which is not in a register (or not in the correct register), issue a load (or move) to put it in a free register before the instruction. If an instruction writes a value, ensure it is in a register and mark it dirty after the instruction.

If you ever need a register, spill a used register by deallocating the value from it, and writing it to the stack if it is dirty and live. At the end of the basic block, write back any dirty and live registers.

This scheme makes it clear exactly where all the loads/stores go, you generate them as you go. It is easily adaptable to instructions which take a value in memory, or which can take either of two arguments in memory, but not both.

If you're OK with having all data on the stack at every basic block boundary, this scheme works pretty well. It should give results similar to linear scan within a basic block, as it basically does very similar things.

You can get arbitrarily complicated about how to decide which values to spill and which registers to allocate. Some lookahead can be useful, for example by marking each value with a specific register it needs to be in at some point in the basic block (e.g. eax for a return value, or ecx for a shift amount) and preferring that register when the value is first allocated (and avoiding that register for other allocations). But it is easy to separate out the correctness of the algorithm from the improvement heuristics.

I've used this allocator in an SSA compiler, YMMV.