Java Reference
In-Depth Information
procedure
(
T
)
if
T
.
kind
=
Identi f ier
or
T
.
kind
=
IntegerLiteral
then
T
.
regCount
←
register
N
eeds
1
else
call
register
N
eeds
(
T
.
le f tChild
)
call
(
T
.
rightChild
)
if
T
.
le f tChild
.
regCount
=
T
.
rightChild
.
regCount
then
T
.
regCount
←
T
.
rightChild
.
regCount
+
register
N
eeds
1
else
T
.
regCount
← max
(
T
.
le f tChild
.
regCount
,
T
.
rightChild
.
regCount
)
end
Figure 13.9: An Algorithm to Label Expression Trees with Register
Needs
In the case considered here, that other subtree also requires
r
registers.
Thus
r
+
1 registers are required to cover the other subtree's computation
as well as to hold the result from the already computed subtree.
Node
n
can therefore be evaluated using
r
+
1 registers in this case.
•
If
n
's subtrees require a di
erent number of registers, say
r
le f t
and
r
right
,
then the tree rooted at
n
can be evaluated as follows. Suppose
r
right
>
r
le f t
.
We evaluate the right subtree first, with the result held in one register.
Because the left subtree needs fewer registers than the right subtree, we
can reuse the right subtree's registers for evaluation of the left subtree,
except for the register holding the right subtree's result.
ff
Node
n
can therefore be evaluated using max(
r
le f t
,
r
right
) registers in this
case. A symmetric argument can be applied when
r
right
<
r
le f t
.
This analysis leads to the algorithm shown in Figure 13.9.
As an example of this algorithm,
would label the expression
tree for (a-b) + ((c+d)+(e*f)) as shown in Figure 13.10 (
regCount
for each
node is shown at its bottom).
We can use t he
register
N
eeds
regCount
labeling to drive a simple, but optimal, code
generator,
CG takes a labeled expression
tree and a list of registers it may use. It generates code to evaluate the tree,
leaving the result of the expression in the first register on the list. If
tree
C
g
, defined in Figure 13.12.
tree
CG
is given too few registers, it will spill registers, as necessary, into storage
temporaries. (We use the standard list manipulation functions
tree
head
and
tail
.
head
returns all but the first list element.
Neither changes the list parameter it uses.)
returns the first element of a list;
tail
