Java Reference
In-Depth Information
Now let us re-run Algorithm 7.4, but with three registers. The first five iterations go
exactly as for four registers in our previous example.
1. unhandled: [V32, V33, V34, V35, V36, V37, V38]
current = V32
active: []
inactive: []
free registers: [$t0, $t1, $t2]
Interval V32 is allocated physical register $t0
2. unhandled: [V33, V34, V35, V36, V37, V38]
current = V33
active: [V32]
inactive: []
free registers: [$t1, $t2]
Interval V33 is allocated physical register $t1
3. unhandled: [V34, V35, V36, V37, V38]
current = V34
active: [V32, V33]
inactive: []
free registers: [$t2]
Interval V34 is allocated physical register $t2
4. unhandled: [V35, V36, V37, V38]
current = V35
active: [V33, V34]
inactive: []
free registers: [$t0]
Interval V35 is allocated physical register $t0
5. unhandled: [V36, V37, V38]
current = V36
active: [V33, V34]
inactive: []
free registers: [$t0]
Interval V36 is allocated physical register $t0
6. But in the sixth iteration, we have used up our three registers ($t1 for V33, $t2 for
V34, and $t0 for V36). We decide to spill $t2 because its next use position is the
furthest away. 4
unhandled: [V37, V38]
4 Actually, a close reading of the instruction at position 30 in the LIR suggests that we might re-use $t0
for V37 because it can be used as the target in the same ADD instruction that it is used in as the input
V36. We leave this improvement to Algorithm 7.4 as an exercise.
 
Search WWH ::




Custom Search