Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2003-03-23 19:46:10 -0800 (Sun, 23 Mar 2003)
Revision: 4227
Log message:
| Whew! Fixed the register allocator, and completely rewrote the spill code.
| Current allocation performance is excellent. We might try to migrate these
| ideas into mcc, though it may not be as easy to express.
|
| The main spill algorithm is this.
|
| 1. Remember that the assembly has only one def for each var.
| Remember we are pretending that we have three-operand instructions.
|
| 2. When a variable $v$ is selected for spilling:
| a. add this code after the def:
|
| add src1,src2,%v // For example
| mov %v, spill[name] // This is a binding occurrence of name
|
| b. convert all following uses of the variable
| to the operand (SpillRegister (v, name)).
|
| c. add a mov before each use
|
| mov SpillRegister (v, name), v'
|
| and daisy-chain these mov's so that there is at most two
| uses for each spilled var (one for the real use, and one
| to copy the daisy-chain).
|
| The meaning of SpillRegister (v, name) is that the value is in _both_
| the register and the spill area. The reason for the daisy-chain is so
| the register allocator can now spill only part of a live range.
|
| 3. If the register allocator decides to spill part of a daisy-chain,
| that part looks like this:
|
| mov %v, spill[name]
| ...lots of code that does not use v...
| mov SpillRegister (v, name), v'
| add 'v, dst
|
| Convert this code to:
|
| mov %v, spill[name]
| ...lots of code that does not use v...
| mov spill[name], v'
| add v', dst
|
| That is, forget that the spill was ever in the register, and
| just fetch it from the memory area.
|
| Spill variables have to be coalesced just like registers, but I
| haven't gotten to it.