An improved register allocation algorithm, which handles the case of
running out of registers, is:
Now, it will be necessary to test whether an operand is a temporary
before doing an operation, and if so, to reload it. Note that temporaries
must be part of the stack frame.
- At the beginning of a statement, mark all registers as not used;
set use number to 0.
- When an operand is loaded into a register, record a pointer to
its token in the register table.
- When a register is requested,
- If there is an unused register: mark it used, set its use number
to the current use number, increment the use number, and return the
- Otherwise, find the register with the smallest use
Get a temporary data cell. Generate a Store instruction ( spill
code) to save the register contents into the temporary. Change the
token to indicate the temporary.