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

Chapter7
RegisterAllocation
7.1 Introduction
Register allocation is the process of assigning as many local variables and temporaries to
physical registers as possible. The more values that we can keep in registers instead of in
memory, the faster our programs will run. This makes register allocation the most effective
optimization technique that we have.
With respect to our LIR discussed in Chapter 6, we wish to assign physical registers
to each of the virtual registers that serve as operands to instructions. The problem is that
there are often many fewer physical registers than there are virtual registers. Sometimes,
as program execution progresses, some values in physical registers will have to be spilled
to memory while the register is used for another purpose, and then reloaded when those
values are needed again. Code must be generated for storing spilled values and then for
reloading those values at appropriate places. Of course, we wish to minimize this spilling
(and reloading) of values to and from memory.
So, any register allocation strategy must determine how to most effectively allocate
physical registers to virtual registers and, when spilling is necessary, which physical registers
to spill to make room for assignment to other virtual registers. This problem has been shown
to be NP-complete in general [Sethi, 1973] but there are several allocation strategies that
do a reasonable job in near-linear time.
Register allocation that focuses on just a single basic block, or even just a single state-
ment, is said to be local. Register allocation that considers the entire flow graph of a method
is said to be global.
In this chapter we look briefly at some local register allocation strategies but we fo-
cus most of our attention on two global register allocation strategies: linear scan register
allocation and graph coloring register allocation.
7.2 Na ve Register Allocation
A na ve register allocation strategy simply sequences through the operations in the (LIR)
code, assigning global registers to virtual registers. Once all physical registers have been
assigned, and if there are additional virtual registers to deal with, we begin spilling physical
registers to memory. There is no strategy for determining which registers to spill; for ex-
ample, one might simply sequence through the physical registers a second time in the same
order they were assigned the first time, spilling each to memory as it is re-needed. When
a spilled value is used again, it must be reloaded into a (possibly different) register. Such
a regimen works just fine when there are as many physical registers as there are virtual
245