Compilation Methods SS 2013 - Assignment 6
Kastens, Pfahler, June 27, 2013
Exercise 1 (Register optimal evaluation of expression trees)
For each of the following two expressions
a * b + c * (d + e) a + (b + (c + (d + e)))
- Draw a tree in the style of Slide C-4.5.
- Compute the attribute values: need, first, res, avail. Assume that 3 registers are available.
- Write the generated instruction sequence, using machine instructions as given below.
load var, reg // value of var ist loaded to register reg add reg1, reg2 // reg2 = reg1 + reg2 mul reg1, reg2 // reg2 = reg1 * reg2
Exercise 2 (Register Allocation by Belady's Technique)
Consider the following piece of straight line code where xi denotes a variable allocated in memory, and a to e denote symbolic registers that are to be mapped to real registers r1, r2, ....
a := x1;
b := x2;
c := a+b;
d := c*a;
e := b+d;
- a)
- Determine the lifetime of the values in a to e.
Draw the interval graph for lifetimes.
How many registers are needed to execute this sequence of assignments?
Assign that number of registers to a to e and rewrite the
sequence of assignments.
- b)
- Assume that the above code needs n registers, but only n-1 are available. Which register do you choose for spilling? Assign n-1 to a to e, and rewrite the sequence of assignments with spill-code inserted.
Exercise 3 (Register Allocation by Graph Coloring)
Consider the following CFG. The basic blocks contain definitions and uses
of the variables a to f:
- a)
- Analyze the lifetimes of the variables, and represent overlapping
lifetimes by an interference graph (see Slide 408).
Determine k, i.e. the minimum number of registers needed to
allocate each of a to f to a register.
- b)
- Color the interference graph with k colors. That is, assign k physical registers to the symbolic registers a to f.
Generiert mit Camelot | Probleme mit Camelot? | Geändert am: 13.06.2017