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

7.5 Further Readings
The linear scan algorithm discussed in this chapter relies extensively on [Wimmer, 2004]
and [Traub et al., 1998]. [Wimmer and Franz, 2010] describe a version of the linear scan
that operates on code adhering to SSA.
Graph coloring register allocation was first introduced in [Chaitin et al., 1981] and
[Chaitin, 1982]. Two texts that describe graph coloring register allocation in great detail are
[Appel, 2002] and [Muchnick, 1997]. The performance of graph coloring register allocation
is addressed in [Cooper and Dasgupta, 2006].
7.6 Exercises
Exercise 7.1. Implement a local register allocation strategy that works with liveness in-
tervals computed only for local individual basic blocks.
Exercise 7.2. Implement a local register allocation strategy that works with individual
basic blocks but that gives preference to blocks that are most nested within loops.
Exercise 7.3. Modify the linear scan algorithm described in Section 7.3 so that it deals
effectively with virtual registers that are defined but are never used.
Exercise 7.4. In a footnote to the 6 th iteration in the second example of running Algorithm
7.4, we observe that we need not spill $t2. Rather, in the instruction
30:ADD$t1$t0$t2
we can re-use $t0 in place of $t2, as in
30:ADD$t1$t0$t0
Implement this modification using Algorithm 7.4. Note that this requires that intervals keep
track of the instruction that uses them, and distinguishes between reads and writes (two
reads cannot share the same physical register); this can be done in Algorithm 7.3, which
builds the intervals.
Exercise 7.5. Modify the code to deal with physical registers in the register allocation
process. Treat all registers as caller-saved registers and bring registers such as $a0{$a3 for
holding arguments passed to methods and $v0 for holding return values into the greater
allocation process.
Exercise 7.6. Modify the code to use the heuristics in Section 7.4.2 to find the optimal
split position.
Exercise 7.7. Modify the code to optimize spills as discussed in Section 7.4.2.
Exercise 7.8. Modify the code to move sequences of like moves between successors and
predecessors, as described in Section 7.4.2.
Exercise 7.9. Implement the linear scan register allocation algorithm that operates on
LIR in SSA form and is described in [Wimmer and Franz, 2010].