Homework 4: Dataflow Analysis
due: Monday, April 1, in class
 Consider we would like to build a dataflow analysis which computes dead
variables instead of live variables. By definition, a variable is dead a
program point the value of the variable at that point is never used later,
in any execution of the program.
 What is the lattice for dead variable
analysis?
 What is the bottom element and the meet operator?
 Write the transfer functions and the dataflow equations for this analysis.
 Is this a forward or a backward analysis? Is this a may or a must
analysis?
 Show how the analysis algorithm computes the dead variables at each
point in the following program. Assume v is the only
live variable at the end of this program.
v = 2*n;
t = 0;
while (t<n) {
y = t*2;
if (n>10) y = t*3;
t = t+1;
}
t = y;
v = z*y;
 Use the computed information about dead variables to remove dead code
from the program. Show the optimized program after dead code elimination.
 Several common optimization include constant propagation, copy
propagation, constant folding, dead code elimination, common subexpression
elimination, induction variable elimination, and loop invariant hoisting.
Repeatedly apply these optimizations for the following code fragment. Assume
here that all variables are live at the end of this code fragment. Explain the transformation of the program at each step and show the final,
optimized program.
step = 2;
x = y = z = 1;
t = u = 0;
v = u;
while (x<10*max) {
y = (2*step1)*x + 5;
if (x>10) t = z+1;
x = x + step;
z = (yu)*(y+z);
t = (y+z)*u*u;
}
u = v*u;
t = u+1;
 We would like to design a dataflow analysis to compute ranges for integer
variables in the program. A simple approach for this dataflow analysis would
be to extend the set N of integer numbers with plus and minus infinity
symbols N* = N U {+inf, inf}, such that inf < n, and n < +inf for
any integer number n. We would then use a lattice over the set L={ [l, u] 
l and u in N* and l <= u}. Assume that every range of the form [n,n] is
less than any other range in L.

Define the partial order and the meet operator for this lattice.

Using this lattice to compute ranges of variables will fail. Why?

Consider a different lattice L'={ [l, u]  l and u are
inf, 1, 0, 1, or +inf and l <= u} U {Top}. Draw the Hasse diagram for this lattice.
Can we successfully use this lattice for our dataflow range analysis?

Assuming we use lattice L', show the transfer functions for statements of
the form x = y binop z, x =  y, and x = y. Here binop is an arithmetic
binary operator in the set {+,,*}. Then show how the dataflow
analysis works for the following program:
x = 0;
y = 1;
while (c) {
y = x;
x = x +1;
y = y 1;
}