Simple register allocation scheme for x86

Question

I'm writing a simple toy compiler and I come to the part of generating machine code (x86-32 assembly in this case). This is what I have for now:

Given the assignment statement: d := (a-b)+(c-a)-(d+b)*(c+1)

I first generate the following intermediate code (3 address code in Triples form):

(0) sub, a, b
(1) sub, c, a
(2) add, (0), (1)
(3) add, d, b
(4) add, c, 1
(5) mul, (3), (4)
(6) sub, (2), (5)
(7) asn, d, (6)

I'm using an intermediate code with the hope of later perform some optimizations on it. For now, I don't manipulate the 3AC and directly generate assembly from it.

My scheme for register use is the following: I perform all the arithmetic operations using EAX and save intermediate results in the other registers EBX, ECX and EDX. For example, from the previous 3AC I generate the following assembly:

mov     eax, a
sub     eax, b      ; eax = (0)
mov     ebx, eax    ; ebx = (0) & eax = free
mov     eax, c
sub     eax, a      ; eax = (1)
add     ebx, eax    ; ebx = (2) & eax = free
mov     eax, d
add     eax, b      ; eax = (3)
mov     ecx, eax    ; ecx = (3) & eax = free
mov     eax, c
add     eax, 1      ; eax = (4)
imul    ecx         ; eax = (5) & ecx = free
sub     ebx, eax    ; ebx = (6) & eax = free
mov     eax, ebx    ; eax = (6) & ebx = free
mov     d, eax

My question is: what do I do when I need to spill the result of EAX but all the registers are busy (EBX, ECX and EDX are holding temporaries). Should I save the value of EAX in the stack and recover it later? If that is the case, should I reserve some extra space in the stack frame of every function for that extra temporaries?

I repeat, this is only what I have come to for now. If there is other simple scheme for allocate registers I would like to know (I'm aware of the existence of more complex solutions involving graph coloring, etc; but I'm looking only for something simple that just works).

Answer 1

Rather than computing the result always into EAX, think in terms of computing the result into a destination location that may be either a register or a memory location.

In pseudocode:

for each 3AC instruction I
   Look up the set S of places that hold operands of I
   R = allocate_place(I)  // register or memory for the result
   Emit code that uses S and puts the result of I into R
      // code emitted differs depending on whether R, S are registers or memory
   free_places S

You'll use an allocator that provides either a register name or a temporary memory location depending on what's available. The allocator keeps a "reverse map" that allows the lookup above of where each operand of an instruction lies. The allocator can use a variety of strategies. The simplest is to use up all the register first and then start allocating memory.

Note that when the code for an entire function has been generated, the allocator will know how many total temporary memory locations are needed for that function. The function preamble code must set these up when it creates the stack frame. You need a mechanism to "back patch" the preamble with the right number of locations. There are various possibilities for this. Ask if you need ideas. Afterward, reset the allocator before going on to compile the next function.

The algorithm above frees the corresponding resource (register or memory location) as soon as its value is used because your simple code generator allows this invariant. If you eliminate common subexpressions or do other optimizations, then deciding when to free a register gets more complicated because its value might be used more than once.

Function calls embedded in expressions raise other interesting cases to think through. How to save registers?

Answer 2

If you have more Data than Registers and push excess Data then you must pop it prior to using it. If you do not end up using it (due to branching) you must still pop it anyways.

Therefore, you are pushing and popping without even getting to use the Data.

You will be pushing the Data into the Stack and popping it back out when you need it.

You are also throwing out the Data that was held in the Register where that popped Data is to be moved to.

You must have the Compiler remember the depth of the Stack and ensure it is correct upon return from the Function.

Wouldn't be easier to simply have Local Storage before or after the Function. Instead of pushing you can mov(e), possibly with an offset, to bp or xchg, possibly with an offset, in and out of this Local Storage Area.

You can Ret(urn) from the Function at any time without having to pop back the same amount of Data that you pushed, just abandon it in the Local Storage.

Obviously this supports an almost unlimited number of 'Registers' quite easily whereas pushing and popping becomes a game of "3x3 (or more) Slider Puzzle".

Those Slider Puzzles (and Rubic's Cube for that matter) are faster to solve with a Screwdriver (for all except the World's Record Champion). Just tear into the thing where you want (access any Memory Location) and put it back together how you wish (do not pop stuff back out before Ret(urning)) -- without all that sliding back and forth 'Tower of Hanoi' style.

Use Local Varibles instead of the Stack (unless you are only one or two Registers short, then a smart Routine to push and pop may be faster than the Memory access; much as an almost solved Cube can be solved quicker than popping the thing open with a Screwdriver).

There will be a yield point at 2 or 3 (Registers short of what you would like to have) where Local Variables are faster than pushing and popping depending upon the Code and how it can be shuffled (Optimized).