Compilers: Principles and Practice by Pearson

Code Generation and Machine-dependent Optimization 297

Now we are using only one register and also fewer instructions. These improvements would be

particularly important if we were dealing with a subexpression of some larger statements where more

registers were needed.

Minimizing Depth

It can be proved that we use fewest registers if we evaluate the subexpression with greatest depth first.

The syntax tree for our example is:

+

t

*

c c

and the corresponding depth values are:

2

0

1

0 0

Note that application of the above rule will force evaluation of the RHS subtree, c * c first and

then addition to t. If instead of addition we had subtraction and we evaluate ...