NICOLAS GUARINI — M. 918670 — [email protected]

Exercise 1

Consider the problem of identifying live (and dead) variables, that is, definitions of variables that may (and may not) be used on any path, for the following program:

public int compute(int n) {
    int x, y, z;
    if (n <= 0) {
        return 0;
    }
    else if (n == 1) {
        x = 1;
    } else {
        x = 1;
        y = 2;
        while (x <= n) {
            z = x;
            x = z * y;
            y = z;
            if (x == y * z) {
             return x;
           }
        }
    }
    return x;
}

• Identify an appropriate type of data flow analysis, indicating its characteristics (forward/backward, all/any path)

  The data flow analysis identified is “Live”, which is a backward, any-path analysis.

• Define $kill$ and $gen$ operations

  The gen sets are variables used at a node, and the kill sets are variables whose values are replaced.

  $$ gen(n) = \{v \ | \ v \text{ is used at } n\} $$

  $$ kill(n) = \{v \ | \ v \text{ is modified at } n\} $$

• identify the kill and gen sets for the code

• reports the results of the analysis for each statement in the code

Exercise 2

Consider the problem of identifying the availability of expressions, that is, the areas of the code where the value of an expression is valid, for the following program:

public static int foo(int number1, int number2){
        if(number1 == 1 || number2 == 2){
            return 1;
        }
        int tmp1 = number1 + number2;
       int tmp2 = number1 + tmp1;
       if(tmp1 <= 100) {
           number2 = number2 + 1;
           int tmp3 = number2 * number1;
            number1 = number1 + 2;
            int tmp = number2 * tmp3 * number1;
            return tmp;
       }
       return number1 + number2;
    }

• Identify an appropriate type of data flow analysis, indicating its characteristics (forward/backward, all/any path)

  The data flow analysis identified is “Avail”, which is a forward, all-paths analysis.

• define kill and gen operations

  The $gen$ set contains the expressions that become available at each node.

  The $kill$ set contains the expressions that change and cease to be available at each node.

  $$ gen(n) = \{exp \ | \ exp \ \text{ is computed at } n\} $$

  $$ kill(n) = \{exp \ | \ exp \text{ has variables assigned at } n\} $$

• identify the kill and gen sets for the code

• reports the results of the analysis for each statement in the code