CS606 - Compiler Construction - Lecture Handout 44

User Rating:  / 0
PoorBest 

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}

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
    ADD R3,R3
    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
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