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

registers; in fact, it is as effective as any other register allocation scheme in this case. Of
course, when there are many more virtual registers than physical registers, its performance
degrades rapidly as physical register values must be repeatedly spilled and reloaded.
7.3 Local Register Allocation
Local register allocation can involve allocating registers for a single statement or a single
basic block.
In [Aho et al., 2007], the authors provide an algorithm that allocates the minimal number
of registers required for processing the computation represented by an abstract syntax tree
(AST); the algorithm does a post-order traversal of the AST, determining the minimum
number of registers required, and assigns registers, re-using registers as appropriate, to the
computation 1 .
Another strategy is to compute, for each virtual register, a live interval (see Section
7.4.1) local to a block. Registers are allocated in the order of the intervals' start positions.
When a register must be spilled, we avoid spilling those registers whose values last the
longest in the block.
Yet another strategy mixes local and limited global information. It computes and applies
local liveness intervals to the allocation of registers, but in those blocks within the deepest
nested loops first, the payoff comes from the fact that instructions more deeply nested within
loops are executed much more often.
A more effective register allocation regime considers the entire control-flow graph for a
method's computation, that is, global register allocation.
7.4 Global Register Allocation
7.4.1 Computing Liveness Intervals
Liveness Intervals
Global register allocation works with a method's entire control-ow graph to map virtual
registers to physical registers. One wants to minimize spills to memory; where spills are
necessary, one wants to avoid using them within deeply nested loops. The basic tool in
global register allocation is the liveness interval, the sequence of instructions for which a
virtual register holds a meaningful value.
Liveness intervals are required by both of the global register algorithms that we consider:
linear scan register allocation and register allocation by graph coloring.
In its roughest form, a liveness interval for a virtual register extends from the first
instruction that assigns it a value to the last instruction that uses its value. A more accurate
liveness interval has \holes" in this sequence, where a virtual register does not contain a
useful value; for example, a hole occurs from where the previously assigned value was last
used (or read) to the next assignment (or write) of a new value.
1 The algorithm is similar to that used by CLEmitter for computing the minimum number of locations
to allocate to a JVM stack frame for computing expressions in the method.