Java Reference
In-Depth Information
main() {
a = f(x);
// Start of first live range
print(a);
// End of first live range
....
a = g(y)
// Start of second live range
print(a);
// End of second live range
}
Figure 13.13: Example of Live Ranges
At the procedure level, a register allocator usually has many values that
might profitably reside in registers: local and global variables, constants, tem-
poraries containing available expressions, parameters, and return values, etc.).
Each value that might profitably reside in a register is called a register candi-
date ; typically there aremanymore register candidates than there are registers.
Procedure-level register allocators do not usually allocate a register to a
single variable throughout the body of a subprogram. Rather, when possible,
variables that do not interferewith each other are assigned to the same register.
Thus, if variable a is used only at the top of a subprogram, and variable b is
used only at the bottomof the subprogram, a and bmaysharethesameregister.
To enhance sharing, register candidates are divided into live ranges. A live
range is the span of instructions in which a given value may be accessed, from
its initial creation to its last use. For variables, a live range runs from its point
of initialization or assignment to its last use. For expressions and constants,
a live range spans from their first to final use. In Figure 13.13, variable a is
broken into two separate and independent live ranges. Each is treated as a
separate register candidate.
A live range can be readily computed using the static single assign-
ment (SSA) form (described in Section 10.3 on page 410), since each use of
a variable is tied to unique assignment. More generally, livevariables can be
computed (as described in Chapter 14) to determine the set of variable names
or expressions that are live at any point in a program. Alternatively, one can
avoid live range computation and simply treat each variable, parameter, or
constant as a distinct register candidate.
The Interference Graph
One of the central problems in procedure-level register allocation is deciding
which live ranges may share the same register and which may not. A live
range l
is said to interfere with another live range m if
l 's definition point (or
 
Search WWH ::




Custom Search