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

There are two physical registers here: $v0 and $a0 2 ; $a0 is the first argument to
computerIter() and the return value is in $v0. There are seven virtual registers: V32
to V38. Recall that, we begin numbering the virtual registers at 32 because 0 to 31 are
reserved for the 32 general-purpose (physical) registers.
An interval for a virtual register extends from where it is defined (it could be defined as
an argument; for example, $a0) to the last time it is used. For example, V37 is defined at
instruction position 30 and is last used at instruction position 45.
Some intervals have holes. A hole might extend from the instruction following the last
instruction using the register up until the next time it is defined. For example, consider
virtual register V33. It is defined at position 5 and used at positions 20, 30 and 35. But it
is not used again until after it is redefined at position 45 (notice the loop again). There is
a hole at position 40.
Loops can complicate determining an interval. For example, V34 is first defined at po-
sition 10, used at 35, and then redefined at 40. But there is a branch (at position 50) back
to basic block B2. At some point in the iteration, the conditional branch at position 20
will bring us to block B4, and V34 will be used a last time at position 55. So we say that
the interval for V34 extends from position 10 to position 55 inclusively; its value is always
meaningful over that interval.
Finally, the darker vertical segments in the intervals identify use positions: a use position
is a position in the interval where either the register is defined (that is, written) or the
register is being used (that is, read). For example, $v0 in Figure 7.2 is defined at position 55
and used at position 60, so there are two segments. But $a0 is never defined in the interval
(actually, we assume it was defined in the calling code) but is used at position 5. From the
same figure we can see that V34 is either defined or used at positions 10, 35, 40, and 55.
The compiler prints out these intervals using the following format:
v0: [55,60]
a0: [0,5]
V32:[0,10]
V33:[5,35] [45,50]
V34:[10,55]
V35:[15,20]
V36:[25,30]
V37:[30,45]
V38:[35,40]
Here, just the intervals (and not the use positions) are displayed for each register. The
notation
[<from><to>]
indicates that the register holds a meaningful value from position <from> to position <to> .
For example, the line
V37:[30,45]
says the liveness interval for register V37 ranges from position 30 to position 45. Notice that
register V33,
V33:[5,35] [45,50]
has an interval with two ranges: from position 5 to position 35, and from position 45 to
position 50; there is a hole in between.
2 The compiler's output leaves out the `$' prex here but we use it to distinguish physical registers.