# CS606 - Compiler Construction - Lecture Handout 44

User Rating:  / 0
PoorBest

Example: let us apply the algorithm to the following segment of 3-address code:

a = b + c
t1 = a * a
b = t1 + a
c = t1 * b
t2 = c + b
a = t2 + t2

live = {b,c}
a = b + c
live = {a}
t1 = a * a
live = {a,t1}
b = t1 + a
live = { b,t1}
c = t1 * b
live = {b,c}
t2 = c + b
live = {b,c,t2}
a = t2 + t2
live = {a,b,c}

## Basic Code Generation

With live/next use information computed, the basic code generation algorithm proceeds as follows. Process the 3-address instructions from beginning to end of a block. For each instruction, use machine registers to hold operands whenever possible. A non-live value in a register can be discarded, freeing that register. The code generator uses two data structures for keeping track of register usage:

1. Register descriptor - register status (empty, inuse) and contents (one or more "values")
2. Address descriptor - the location (or locations) where the current value for a variable can be found (register, stack, memory)

Instruction type: x = y op z

1. If y is non-live and in register R (alone) then generate
OP z’, R
where z’ = best location for z. i.e., lookup address descriptor for z. Prefer register location if z is present in a register.
2. If operation is commutative, z is non-live and is in register R (alone), generate
OP y’, R
(y’ = best location for y)
3. If there is a free register R, generate
MOV y’, R
OP z’, R
4. Use a memory location. Generate
MOV y’,x
OP z’,x

After generating machine instructions, update information about the current best location of x. If x is in a register, update that register’s information (descriptor). If y and/or z are not live after this instruction, update register and address descriptors according.

Let us return to the 3-address code example and apply the basic code generation algorithm. Recall the basic block with liveness information:

live = {b,c}
a = b + c
live = {a}
t1 = a * a
live = {a,t1}
b = t1 + a
live = { b,t1}
c = t1 * b
live = {b,c}
t2 = c + b
live = {b,c,t2}
a = t2 + t2
live = {a,b,c}

Initially
three registers:
( -, -, -) all empty
current values:
(a,b,c,t1,t2) = (m,m,m, -, -)

1. a = b + c,
Live = a
getreg(): L = R1
MOV b,R1
ADD c,R1 ; R1 := R1 + c
Registers: (a, -, -)
current values: (R1,m,m, -, -)
2. t1 = a * a,
Live = a,t1
L = R2 (since a is live)
MOV R1,R2
MUL R2,R2 ; R2 = R2* R2
Registers: (a,t1, -)
current values: (R1,m,m,R2, -)
3. b = t1 + a,
Live = b,t1
Since a is not live L = R1
ADD R2,R1 ; R1 = R1+R2
Registers: (b,t1, -)
current values: (m,R1,m,R2, -)
4. c = t1 * b,
Live = b,c
Since t1 is not live L = R2
MUL R1,R2 ; R2 = R1*R2
Registers: (b,c, -)
current values: (m,R1,R2, -, -)
5. t2 = c + b,
Live = b,c,t2
L = R3
MOV R2,R3
ADD R1,R3 ; R3 = R1+R2
Registers: (b,c,t2)
current values: (m,R1,R2, -,R3)
6. a = t2 + t2,
Live = a,b,c
Registers: (b,c,a)
current values: (R3,R1,R2,-,R3)

## End of block

move all live variables to memory:
MOV R3,a
MOV R1,b
MOV R2,c
all registers available

Thus the machine code (assembly language) generated is

; a := b + c
ADD c,R1 ; R1 := R1 + c
; t1 := a * a
MOV R1,R2
MUL R2,R2 ; R2 = R2* R2
; b := t1 + a
ADD R2,R1 ; R1 = R1+R2
; c := t1 * b
MUL R1,R2 ; R2 = R1*R2
; t2 := c + b
MOV R2,R3
ADD R1,R3 ; R3 = R1+R2
; a := t2 + t2