Contents    Page-10    Prev    Next    Page+10    Index   

Register Allocation

Used Use Number Token

An improved register allocation algorithm, which handles the case of running out of registers, is:

  1. At the beginning of a statement, mark all registers as not used; set use number to 0.

  2. When an operand is loaded into a register, record a pointer to its token in the register table.

  3. When a register is requested,
    1. 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 register number.

    2. Otherwise, find the register with the smallest use number. 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.
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.