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

Some Improvements to the LIR
An examination of the LIR after register allocation (using any global allocation strategy)
makes it clear that many (often unnecessary) moves are generated.
Because we have not made fixed registers, for example, $a0 to $a3 and $v0 (and $v1),
available for allocation, there is much movement among these and virtual registers in the
original LIR; this leads to many meaningless moves from one register to another once
physical registers are allocated. Bringing these physical registers (modeled as fixed intervals)
into play should eliminate our overreliance on other general-purpose registers and eliminate
many moves among them.
There is much room for spill optimization. When a variable is defined once and then
used several times, it needs to be spilled just once even if the interval modeling the virtual
register holding the value is split several times. A dirty bit may be used to keep track of
definitions versus uses. Certain arguments to methods, for example, $a0 when it contains
the address of an object for this , needs to be spilled just once also.
If all of a block's predecessors end with the same sequence of move instructions, they
may be moved to the start of the block itself. Likewise, if all of a block's successors start with
the same sequence of move instructions, they can be moved to the end of the (predecessor)
block. Such moves are most likely to be introduced either by Phi-resolution (Chapter 6)
or by data-flow resolution. Wimmer makes the point that this is best done after virtual
registers have been replaced by physical registers because this allows us to combine moves
involving like physical registers even if they originated from differing virtual registers.
By examining the output of the register allocation process, one will find many places for
improvement. It is best to formulate algorithms that are as general as possible in making
these improvements.
What is in the Code Tree; What is Left Undone
Much of Wimmer's strategy, recounted above, is implemented in our code. The following
issues are not addressed and thus are left as exercises.
We do not deal with physical registers in the register allocation process. Although we
make use of particular fixed registers, for example, $a0 to $a3 for holding arguments
passed to methods and $v0 for holding return values, we do not otherwise make these
available for allocation to other computations. Moreover, when we allocate $t0 to $t9
and $s0 to $s7, we assume they are callee-saved. The Wimmer algorithms treat them
as caller-saved and depend on the (short) intervals at calls to insure they are spilled
before the calls, and reloaded after the calls; otherwise, they are treated like any other
general-purpose registers and are available to the allocator.
Our code does not use heuristics to find the optimal split position.
Our code does not optimize spills.
Our code does not move sequences of like moves between successors and predecessors.
7.4.3 Register Allocation by Graph Coloring
Introduction to Graph Coloring Register Allocation
In graph coloring register allocation, we start with an interference graph built from the
liveness intervals. An interference graph consists of a set of nodes, one for each virtual