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
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.)
Instructor: Max Hailperin