**Related Content:** CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

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}

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:

- Register descriptor - register status (empty, inuse) and contents (one or more "values")
- 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

- 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. - If operation is commutative, z is non-live and is in register R (alone), generate

OP y’, R

(y’ = best location for y) - If there is a free register R, generate

MOV y’, R

OP z’, R - 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, -, -)

**a = b + c,**

Live = a

getreg(): L = R1

MOV b,R1

ADD c,R1 ; R1 := R1 + c

Registers: (a, -, -)

current values: (R1,m,m, -, -)-
**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, -) **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, -)**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, -, -)**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)**a = t2 + t2,**

Live = a,b,c

ADD R3,R3

Registers: (b,c,a)

current values: (R3,R1,R2,-,R3)

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

LOAD b,R1

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

ADD R3,R3

MOV R3,a ; mov live

MOV R1,b ; var to memory

MOV R2,c