Java Reference
In-Depth Information
(d) B1 has the single successor B2 and it gets its liveOut (V33 and V34) from B2's
liveIn. V33 and V34 are not added to B1's liveIn, even though they are in its
liveOut, because they are in its liveDef (dened in B1). Because $a0 is in B1's
liveUse, it is added to its liveIn.
(e) B0 has the single successor B1 and gets its liveOut ($a0) from B1's liveIn. Because
$a0 is not redened in B0 (nothing is dened in B0), it is also in B0's liveIn.
Of course, there have been changes to at least one of the sets and we need another
iteration.
2. In the second iteration, we again go through the blocks in reverse order to get the
following sets:
B4liveIn: V34
B4liveOut:
B3liveIn: V33V34
B3liveOut:V33V34
B2liveIn: V33V34
B2liveOut:V33V34
B1liveIn: $a0
B1liveOut:V33V34
B0liveIn: $a0
B0liveOut:$a0
(a) Nothing has changed for B4.
(b) But B3's liveOut changes because one of its successor's liveIn changed in the rst
iteration; V33 and V34 are added to B3's liveOut.
(c) Nothing has changed for B2.
(d) Nothing has changed for B1.
(e) Nothing has changed for B2.
Because there was a change to liveOut in processing B3, we must iterate yet again.
3. But no changes are made to any of the sets in the third iteration, so we can stop. The
final global liveness sets are those computed in the second iteration:
B4liveIn: V34
B4liveOut:
B3liveIn: V33V34
B3liveOut:V33V34
B2liveIn: V33V34
B2liveOut:V33V34
B1liveIn: $a0
B1liveOut:V33V34
B0liveIn: $a0
B0liveOut:$a0
We can now use this global live in and live out information to compute accurate liveness
intervals.
Building the Intervals
To build the intervals, we make a single pass over the blocks and instructions, again in
reverse order. Algorithm 7.3 computes these intervals with both the ranges and the use
positions.
Search WWH ::
Custom Search