MCS-388 Homework 6 (Spring 2009)

Due: May 8, 2009

All questions in this assignment concern applying the lazy code motion partial-redundancy elimination algorithm described in Section 9.5 of the dragon book to the flow graph shown at the end of this assignment. All of the questions except the last one ask you to give a set of block numbers. Please list the block numbers in numerical order. If you want to list all the numbers 0 to 15 in order and then cross out the ones that don't belong in the set, that is fine too. And if you want to present all the sets in a combined table, that is fine too.

  1. At which blocks is the expression a+b anticipated-in?

  2. At which blocks is the expression a+b "available"-in, using Section 9.5's peculiar definition of "available"?

  3. Which blocks are earliest for the expression a+b?

  4. At which blocks is the expression a+b postponable-in?

  5. Which blocks are latest for the expression a+b?

  6. For each block that would be altered by Algorithm 9.36, give the block number and what the new contents of the block would be. To answer this question using the algorithm, you would need to first do one more dataflow analysis (the one named "used"). If you want, you can do that analysis. Or, you can just use your understanding of the algorithm's goal to figure out the end result.

flowgraph for PRE homework

Course web site:
Instructor: Max Hailperin <>