CS 412/413
Introduction to Compilers
Spring 2002

Homework 4: Dataflow Analysis

due: Monday, April 1, in class

  1. 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.
    1. What is the lattice for dead variable analysis? 
    2. What is the bottom element and the meet operator?
    3. Write the transfer functions and the dataflow equations for this analysis.
    4. Is this a forward or a backward analysis? Is this a may or a must analysis?
    5. 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;

    6. Use the computed information about dead variables to remove dead code from the program. Show the optimized program after dead code elimination.
     
  2. 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.

    3.   step = 2;
        x = y = z = 1;
      t = u = 0;
      v = u;
      while (x<10*max) {
        y = (2*step-1)*x + 5;
        if (x>10) t = z+1;
        x = x + step;
        z = (y-u)*(y+z);
        t = (y+z)*u*u;
      }
     u = v*u;
     t = u+1;

  3. 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.
    1. Define the partial order and the meet operator for this lattice.
    2. Using this lattice to compute ranges of variables will fail. Why?
    3. 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?
    4. 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;
      }