What is the lattice used for the Reaching Definitions analysis? What are the elements and what is the operation?
Draw the flow-graph for the following WHILE program:
z = 1;
while z < x do
if z * (x / z) = x then
y = y + 1
else
skip
end;
z = z + 1;
end
What def-use chains are there in this example?
(Optional: what does this program do?)
Implement a lattice class that extends ArrayLattice with the same type parameters. The class must model lattices where each element of the array is reserved for one variable in the program. You will need helper code to collect the variables in a program. You may use your solution to Homework #1, or else modify the posted solution.
Implement public functions
T get(T[] value, Variable v); T[] put(T[] value, Variable v, T newValue)Remember not to update any existing array!
Next use this class to implement a ReachingDefinitions lattice class, and a ReachingDefinitionsAnalysis analysis class. Your analysis should not construct a flow graph. Instead, it should be a TreeVisitor that updates its state (lattice) on assignments and records def-use chains (Assignment and UseVariable pairs) at every variable use. Use ``null'' as the ? definition. You must be careful to evaluate both sides of an ``if'' starting with the same lattice value and to evaluate a while loop until a fixed point is obtained. The def-use chains should be printed after the analysis is done.
As with all homeworks, please turn in your homework on paper at the beginning of lecture.