MCS-388 Homework 6 (Spring 2006)

Due: May 8, 2006

For all of the following problems, refer to the flow graph shown in Figure 10.74 on page 713. In that flow graph, block B₁ is the initial block.

1. What are the back edges?

2. For each back edge, what set of blocks constitutes the natural loop of that back edge??

3. For each block, what definitions reach the start of that block? What definitions reach the end of the block? (Identify the definitions using the numbers shown in the figure.)

4. For each block, what variables are live at the end of that block? What variables are live at the start of the block?

5. For each block, which of the expressions listed below are available at the start of that block? Which of the expressions are available at the end of the block? (Identify the expressions using the numbers shown in the folloing list.)

   1. a+b
   2. c-a
   3. b*d
   4. e+1