Compiler code generation--register allocation inside conditional blocks.

Question

I'm writing a compiler for a course. I've run into some optimization issues of which I am unsure how to handle optimally. Suppose there is a while loop from the input language that uses N local variables which must be held in registers (or should be, for fast computations). Suppose N > K, the number of registers. There is a chance of the conditional register being changed near the end of the while loop.

For example, suppose the register for x (let's say %eax on i386) was determined before the following statement:

while ( x ) { x = x - 1 ; /* more statements */ }

In the more statements code, it is possible for x to be spilled back onto the stack. When the code jumps back to the beginning of the while loop to re-evaluate x, it will try to use %eax--but this may not even be holding the value of x now. So we could have something like

        movl -8(%ebp), %eax        # eax <- x
        ....                       # do stuff but let x stay in %eax
_LOOP1: cmpl $0, %eax
        ....
        movl -12(%ebp), %eax       #eax now holds something else
        ....
        jmp _LOOP1 

One solution I'm using is to force the code to spill all modified registers before the while statement (so the registers are viewed as empty from the code generator's perspective). After the label for the while loop, the code has to load everything into a register as necessary.

My solution is something like this:

        movl -8(%ebp), %eax        # eax <- x
        ....                       # do stuff but let x stay in %eax
        movl %eax, -8(%ebp)        # spilling and clearing all registers
_LOOP1: movl -8(%ebp), %eax        # get a register for x again
        cmpl $0, %eax
        ....
        movl -12(%ebp), %eax       # eax now holds something else
        ....
        movl %eax, -8(%ebp)        # spill to prevent overwrite
        jmp _LOOP1 

It seems like my solution is a little extraneous or unnecessary. Is there some general optimization trick I am forgetting here?

EDIT: I would also like to note something similar occurs for conditionals such as if and if else. This occurs for them because a register may be allocated for a variable inside the block for the conditional, but the code generator assumes it was moved in there for everything else after. I have almost the same approach for dealing with that case.

Answer 1

The general technique you're looking for here is usually called "live range splitting". A Google Search for that term will give you pointers to a bunch of different papers. Basically the idea is that you want to split a single variable (x in your example) into multiple variables with disjoint live ranges each of which gets copied to the next at the splitting point. So you'd have x.0 before the loop, which is copied into x.1 just before the while and used as that in the loop. Then right after the loop, you'd copy x.1 into x.2 and use that after the loop. Each of the split vars would be potentially allocated to a different register (or stack slot).

There are a lot of tradeoffs here -- too much splitting leads to (many) more variables in the code, making register allocation much slower, and potentially leading to unnecessary copies.