MC97 Homework 4 (Spring 1999)

Due: May 13, 1999

Consider evaluating ((7-8)-9)-(10-(11-12)). Draw a tree representation of this expression, with the numbers 7, 8, 9, 10, 11, and 12 as leaves and - at the internal nodes.
Assume an architecture with two registers, r0 and r1, and the following four instruction formats:
```
rd := n
rd := rs - rt
push rs
pop rd
```
where rd, rs, and rt can in each case be either of r0 and r1, and where n can be any number. The push and pop instructions operate on a stack stored in memory.
Label the nodes in your tree (both the constant leaves and the internal subtractions) with need values. Then give the list of instructions the Sethi-Ullman algorithm would generate for evaluating this expression into r0.
We can refer to the definitions of h in the following flow graph by the number of the blocks in which they appear; that is, there are definitons numbered 4, 5, 12, and 13. Which of these four definitions reach the start of block 7? Block 13? Block 16?

(This flowgraph is reproduced from my paper "Cost-Optimal Code Motion," ACM Transactions on Programming Languages and Systems, Voluume 20, Number 6 (November, 1998), pp. 1297-1322.)