• English only

# Lab for Automated Reasoning and Analysis LARA

## Exercises 10

In the following problems assume that we have a machine with the registers .
All the registers and the integer numbers consist of 2 bytes.

We use the temporary variables x1 … x31 to implement our intermediate code. The goal is to assign each temporary variable xi to a register and to minimize the exploited registers.

## Problem 1

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.
• Construct the interference graph.
• Can coalescing help us to remove any move instructions?

## Problem 2

Given a set of numbers the variance is defined by the following formula. where is the average of the numbers.

The following Scala function computes the variance of n numbers which is passed through the array a.

def variance(a: Array[Int], n: Int): Int = {
var sum = 0
var squares = 0
for (i <- 0 until n) {
sum += a(i)
squares += a(i) * a(i) }
val average: Int = sum / n
val result: Int = (squares / n) - (average * average)
return result
}

We can sketch the translation of the variance function to instruction level with temporary variables as the following.

Instruction Explanation
x1 := &a // pointing to the beginning of the array: a(0)
x2 := 0 // sum
x3 := 0 // squares
x4 := 0 // loop counter: i
x5 := n // the length of the array: n
L: x6 := *x1 // beginning of the loop
x2 := x2 + x6 // accumulate sum
x7 := x6 * x6
x3 := x3 + x7 // accumulate average
x1 := x1 + 2 // pointer to the next element
x4 := x4 + 1
if(x4 < x5) jump L // closing of the loop
x8 := x2 / x5 // average
x9 := x3 / x5 // average of squares
x10 := x8 * x8 // square of averages
x11 := x9 - x10 // result
return x11
• Construct the control-flow graph
• Determine the set of live variables before and after the execution of each instruction.
• Construct the corresponding interference graph.
• How many colors is needed to color the graph without spilling?
• Give a minimal register allocation.

cc10/exercises_10.txt · Last modified: 2015/04/21 17:35 (external edit)

© EPFL 2018 - Legal notice 