Lab for Automated Reasoning and Analysis LARA

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
2: iload_y
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 $x$ 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 $v_1$ and $v_2$?

Exercise 4: Live variables analysis

Live-Variable Analysis

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

\begin{equation*} 
   \text{GCD}(a,b) = \left\{
   \begin{array}{l l}
    a & \quad \text{if $b = 0$}\\
    \text{GCD}(b, a\text{ mod } b) & \quad \text{otherwise}\\
   \end{array} \right.
\end{equation*}

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.
 
cc11/exercises_03.txt · Last modified: 2015/04/21 17:35 (external edit)