- Prove that the Chaotic iteration algorithm is partially correct, i.e., if the algorithm terminates while analyzing a given system of equations, it yields the simultaneous least fixed point
- Give an example of bad evaluation order in Chaotic iterations in which the number of iterations will be large.
- Formulate the data flow equations for reaching definitions and in particular define the gen and kill functions. Apply Chaotic iterations to two programs: one in which the analysis is precise and another one in which the analysis includes too many definitions
- Apply the Live Variable Analysis to the following program x :=1 while y >0 do x := x -1 ; x :=2
- A variable x is
**faint variable**if it is either dead or used to calculate values of other faint variables. For example, in the program "x := x -1 ; y ::=x" all the variables are faint. Notice that every dead variable is faint but there are faint variables who are not dead - Explain the utility of faint variables in compilers
- Give the data flow equations for faint variables
- Are the equations of the kill/gen form? Are they monotone? Distributive?
- In order to compute faint variables it was suggested to compute dead variables in the usual way and then rewrite the program to eliminate assignments to dead variables. Will this procedure yield the same result as the one obtained by the Chaotic Iteration Procedure applied to the system of equations defined in subsection 2?
- Show that points-to analysis functions are distributive for one level pointers
- Show that the points-to analysis functions are monotone for arbitrary levels of pointer indirections. Show an example program in which the least fixed point is less precise than the JOP.
- Show an example program which demonstrates that in the assignment *p = x, it is impossible to remove elements when the points to set of p includes more than one element. What happens when this set includes a single element?
- Show that any solution to the forward set of equations is less precise than the JOP.
- Show that when the functions are distributive (additive) the JOP and the least solution coincide..
- Copy constants are special class of constants which have the for x := y or x:=c where x and y are variables and c is a literal. Show that the class of copy constants is defined by distributive functions and show to code these constants in the IFDS framework. Bonus: describe a more efficient solution.