Spring 2003 Programming Languages Qualifier

Answer 3 of the 4 questions below.

1. Convert the following control-flow graph into one that obeys the constraints of SSA form. You will need to introduce extra variables and to insert "phi" functions to make this transformation. Describe some advantages of using SSA as a compiler intermediate form.

2. Data-flow analyses are essential for enabling many compiler optimizations.   
a.  Define a monotone data-flow framework for

1) Available expressions
2) Constant propagation

b.   Are these monotone data-flow frameworks also distributive? Justify your answer.
c. Prove that the algorithm defined by the reaching-definitions framework converges.
d. One requirement for rapid convergence of a data-flow algorithm is the ordering of the visiting of the nodes (basic blocks).  How would you order the nodes in the available-expressions algorithm for such convergence?

3. After optimizations are performed, data-flow information must be updated to reflect the transformation changes.  The use of "incremental" algorithms to update the data-flow information avoids complete reanalysis.  Given a control-flow graph G whose IN and OUT sets for reaching definitions have been computed,
a. Give an incremental algorithm to update the IN and OUT sets for G. Consider possible changes to be either insertion or deletion of statements.  Be sure to consider all possible changes to the reaching-definitions information that could be caused by the insertion/deletion of statements.
b. Show how your algorithm works by applying it to the insertion of S1: x = y + 1, the deletion of r = s*t, and the modification S3: if (a > b) to S3': if (a>=b).

4. Graph coloring for register allocation: Chaitin proposed a graph coloring algorithm which was later improved upon by Briggs. Briggs proposed an algorithm which is called Optimistic Coloring which postpones spill decisions until the coloring pass by storing potential spill values on the stack. Give an example of an interference graph which results in spill due to Chaitin's approach but which leads to zero spill due to Briggs. You can assume a suitable number of available registers to illustrate your point.