# Exercises on Code generation and Dataflow analysis

## Exercise 1 (Warm up): Bytecode generation

Translate the following function to JVM instructions.

def middle(small: Int, big: Int): Int = {
val mid = small + (big - small) / 2
return mid
}

## Exercise 2: Branch Instruction

• Translate the for-loop and if-condition to branch instructions. You can keep all the other statements in . You can also assume that the for loop is translated into the corresponding while loop.
• Now convert the following code fragments to byte code:
• loop stopping condition from line 3
• if-statement condition on line 4
• line 7
 1: def bubblesort( xs : Array[Int]) : Array[Int] = {
2:  for( i <- 0 until (xs.length - 1))
3:    for( j <- 0 until (xs.length - i - 1))
4:      if( xs(j) > xs(j+1)) {
5:        var tmp = xs(j)
6:        xs(j) = xs(j + 1)
7:        xs(j + 1) = tmp
8:      }
9:  xs
10:}

The JVM instructions for getting the length of the array in the local slot x are

1: aload_x
2: arraylength

and the instruction to access the ith element of the array xs, i.e. xs(i) is

1: aload_x
3: iaload

where x is the slot of the array and y the slot of the index i.

## Exercise 3: Range analysis

Draw the control-flow graph for the following program.

x := 0;
while (x < 10) {
x := x + 3;
}
if (x >= 0) {
if (x <= 15) {
a[x]=7; // made sure index is within range
} else {
// v1
error;
}
} else {
// v2
error;
}

Run range analysis that maintains an interval for at each program point in the control flow graph. Assume that the ranges that the integers can take are [-128, 127] for simplicity, i.e. all intervals within this range are allow, for instance [-1, 3].

What are the fixpoint values at program points marked and ?

## Exercise 4: Live variables analysis

The GCD of two numbers can be computed using the Euclid algorithm.

We can implement the GCD algorithm with temporary variables as the following.

x1 := a
x2 := b
Start: if x2 = 0 jump Done
x3 := x1 % x2
x1 := x2
x2 := x3
jump Start
Done: return x1
• Construct the control-flow graph
• Determine the set of live variables before and after the execution of each instruction.