Java Reference
In-Depth Information
At position 45, the move defines V33 so the range for V33 is shortened to start at 45;
V37 is used, so we add a range to V37 extending from (for now) the start of the block
to position 45. This is illustrated in Figure 7.4(b).
At position 40, the move defines V34 so its range is shortened to start at 40; V38 is
used so we add a range to V38 extending from (for now) the start of the block to
position 40. This is illustrated in Figure 7.4(c).
At position 35, the multiplication operation defines V38 so its range is shortened to
start at 35; V34 is used so we add a range extending from the start of the block to
35, and because it is adjacent to the next segment, we merge the two; V33 is used,
so we add a segment for V33 from the start of the block to 35. This is illustrated in
Figure 7.4(d).
At position 30, the add operation defines V37 so we shorten its range to start at 30;
V33 is used, so we add a use to its interval at 30; V36 is used so we add a range from
the start of the block to 30. This is illustrated in Figure 7.4(e).
At position 25 the load constant operation defines V36 so we define a use for V36
(definitions are considered uses) at position 25. This is illustrated in Figure 7.4 (f).
Once we have calculated the liveness intervals for a method, we can set about using them
to allocate registers.
7.4.2 Linear Scan Register Allocation
Introduction to Linear Scan
Linear scan [Poletto and Sarkar, 1999] is the first register allocation technique we look at,
and it is the one we have implemented in the JVM code to SPIM translator. Its principal
advantage is that it is fast|it really just does a linear scan through the liveness intervals,
in order of their starting positions (earliest first), and maps them to physical registers.
We follow a strategy laid out by Christopher Wimmer in his Master's thesis [Wimmer,
2004], which he used to implement a register allocator for the Oracle HotSpot client JIT
compiler. It is fast and it is also intuitive.
Linear Scan Allocation Algorithm
Algorithm 7.4 describes a linear scan register allocation algorithm based on that in [Wim-
mer, 2004].
First we sort the intervals in increasing order, based on their start positions. At any
time, the algorithm is working with one interval called the current interval; this interval has
a starting position, the from field of its first range. This position categorizes the remaining
intervals into four lists:
1. A list of unhandled intervals sorted on their start positions in increasing order. The
unhandled list contains intervals starting after position.
2. A list of active intervals, whose intervals cover position and so have a physical register
assigned to them.
3. A list of inactive intervals, each of which starts before position and ends after position
but do not cover position, because position lies in a lifetime hole.
4. A list of handled intervals, each of which ends before position or was spilled to memory.
These intervals are no longer needed.
 
Search WWH ::




Custom Search