Register Allocation - Introduction to Compiler Construction in a Java World - page 263

Choosing an Optimal Split Position
Once we have burned through all of our registers, we will be forced to split intervals. As
we have seen above, we may split current to temporarily assign it a physical register that
is attached to an inactive interval. We may split and spill intervals that are active. Usually,
we are offered a range of positions where we may split an interval; the position where an
interval is spilled or reloaded can be moved to a lower position. Where exactly we choose
to split an interval can affect the quality of the code.
Wimmer [Wimmer, 2004] proposes the following three heuristics to apply when choosing
a split position:
1. Move the split position out of loops. Code in loops is executed much more often than
code outside of loops, so it is best to move register spills and register reloads outside
of these loops.
2. Move the split position to block boundaries. Data-flow resolution (in the next section)
takes care of spills and reloads at block boundaries automatically.
3. Move split positions to positions that are not multiples of five. These positions are
not occupied by normal LIR operations and so are available for spills and reloads.
These rules do not guarantee optimal code but they go a long way toward improving the
code quality.
Resolving the Data Flow, Again
The splitting of intervals that occurs as a result of register allocation may cause inconsis-
tencies in the resulting code.
For example, consider the follow of data in an if-then-else statement:
if(condition){
thenpart
}else{
elsepart
}
subsequentcode
Consider the case where the register allocator must spill a register (say, for example, $s5)
in allocating registers to the LIR code for the else part ; somewhere in the LIR code for the
else part is a move instruction (for example, a store) to spill the value of $s5 to a slot on
the run-time stack. If the subsequent code makes use of the value in $s5, then it will know
that the value has been spilled to the stack because the interval will extend at least to this
next use; it will use a move to load that value back into a (perhaps different) register.
But what if the flow of control passes through the then part code? Again, subsequent
code will expect the value of $s5 to have been spilled to the stack slot; it will load a value
that has not been stored there.
For this reason, an extra store of $s5 must be inserted at the end of the then part code
so that the (spilled) state of $s5 is consistent in the subsequent code.
Algorithm 7.7 ([Wimmer, 2004] and [Traub et al., 1998]) inserts all moves for spilling,
including these necessary extra moves.