- 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.