Homework # 5
due November 7

Strongly Live Variable Analysis

Do Exercise 2.4 on page 133, defining a modification of live variable analysis: Strongly Live Variable Analysis (SLVA). SLVA requires that you initialize the set of strongly live variables at the end of the program. When we implement SLVA in Homework #6, we will use the program output variables for this purpose. For this Homework, assume the existence of a special ``return'' variable r to initialize the SLVA set. In all places other than the end of the program/statement, r should be treated the same as any other variable.

Here are some examples of SLVA:

• r := r + 1;
  
  Here r is strongly live before the assignment.
• x := 1;
  y := x + 1;
  z := y + 1;
  a := z + 1;
  r := x;
  
  Note that the assignments to y, z and a are all to faint variables.
• a := 1;
  r := 100;
  while b > 0 do
        a := a + 1;
        r := r - 1;
        b := b - 1;
  end;
  r := r + 1;
  
  Here b is strongly live until the loop is done; a is faint everywhere and r is strongly live after its first assignment.

Here's how you should do Exercise 2.4:

In particular, you may assume isolated exits.

Errors

The book's Live Variable Analysis (p. 47-50) requires isolated exits.

• Give a WHILE program for which the flow-graph has non-isolated exits. This program must also give the wrong results for LVA.
• Explain how the book's LVA goes wrong on this program.

In Homework #3, several students initialized reaching definitions with the empty set (rather than with the set ). Then whenever a use of a variable was found without any reaching definition, the definition was inferred. So, for example in the following code

y = 1;
x = y + z

The analysis would infer a reaching definition of for the use of z. This result is correct. Nevertheless, this approach does not work in general:

• Give an example for which this buggy analysis gives the wrong results.
• Explain why this error is unsafe: the error is in the wrong direction. (What is the safe direction for approximation for reaching definitions analysis?)
• Give an example of an ``optimization'' that a compiler using the buggy analysis might do. When would the symptom of the buggy analysis appear?

Several students, when implementing reaching definitions analysis, did not iterate to a fixed point and instead just ran the loop twice. The textbook does say that GEN-KILL analyses only require the loop to be analyzed twice, but there are some pitfalls which is why it was required to do fixed-point iteration.

• Some students just analyzed the body of the loop twice and then went on. That won't work, even for reaching definitions. Why? Give an example for which this algorithm gives the wrong (unsafe!) results.
• The statement only applies to GEN-KILL analysis. Give an example for which Constant Propagation Analysis gives an unsafe answer if a loop is only analyzed twice.
• Are three iterations enough in general? Why or why not?

Programming

Implement two additional worklists that make use of reverse postorder ordering:

• One which uses a priority queue in which nodes are ordered by (reverse) post-order numbers.
• One in which the flow graph is analyzed into strongly-connected components (SCCs). The worklist will only return nodes from one strongly-connected component (SCC) at a time, and the SCCs are processed in reverse post-order (RPO).

  Within each SCC, the nodes are processed round-robin: in order from the first to the last in reverse post-order. Then, if any nodes in this SCC were ``added'', the SCC is processed again (all nodes in RPO). The ``add'' method doesn't actually add the node to some data structure. It merely means we will need to process the SCC again.

  Once all the SCCs are processed and the last time the last SCC was processed, ``add'' was never called, then (and only then) the worklist's ``hasNext'' method should return false.

Optional: Measure which technique is more efficient.

Submission

As with all homeworks, please turn in your homework on paper at the beginning of lecture.

About this document