Compiler code generation - register allocation inside conditional blocks

Question

I am writing a compiler for a course. I ran into some optimization problems, of which I'm not sure how to handle optimally. Suppose that from the input language there is a while loop that uses N local variables that should be stored in the register (or should be for quick calculations). Suppose that N> K, the number of registers. There is a chance that the conditional register will change at the end of the while loop.

For example, suppose a case for x (say% eax on i386) was defined before the following statement:

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

In more operational code, it is possible for x to be spilled back onto the stack. When the code moves to the beginning of the while loop to re-evaluate x, it will try to use% eax - but it may not even hold the value of x for now. So we could be 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 that I use is to force the code to spill all changed registers before the while statement (therefore, the registers are considered empty from the perspective of the code generator). After the label for the while loop, the code should load everything into the register as needed.

My solution looks 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 looks like my solution is a little extraneous or unnecessary. Is there some general optimization trick I forget here?

EDIT: I would also like to point out that something similar happens for conventions like if and if else. This happens to them, because a register can be allocated for a variable inside a block for a conditional expression, but the code generator assumes that it has been moved there for everything else after. I have almost the same approach to solving this case.

Answer 1

The general technique that you are looking for here is usually called "live range sharing." Google Search for this period will give you pointers to a bunch of different documents. Basically, the idea is that you want to split one variable (x in your example) into several variables with disjoint live ranges, each of which will be copied to the next split point. Thus, you must have x.0 in front of the loop, which is copied to x.1 just before while and used as in the loop. Then, right after the loop, you copy x.1 to x.2 and use this after the loop. Each of the split vars will potentially be allocated to a different register (or stack slot).

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