Question 9051 – Compiler-Design

 
    a = 1
    b = 10
    c = 20
    d = a+b
    e = c+d
    f = c+e
    b = c+e
    e = b+f
    d = 5+e
    return d+f

Here a, b, and c all have 3 different values so we need atleast 3 registers r1, r2 and r3.
Assume ‘a’ is mapped to r1, ‘b’ to r2 and ‘c’ to r3.
d = a + b, after this line if u notice ‘a’ is never present on right hand side, so we can map ‘d’ to r1.
e = c + d, after this line ‘d’ is never present on rhs, so we can map ‘e’ to r1.
at this time mapping is
r1 — e
r2 — b

r3 — c
We have 3 registers for e, b and c.
f = c + e
b = c + e
These two are essentially doing same thing, after these two line ‘b’ and ‘f’ are same so we can skip computing ‘f’ or need not give any new register for ‘f’. And wherever ‘f’ is present we can replace it with ‘b’, because neither of ‘f’ and ‘b’ are changing after these two lines, so value of these will be ‘c+e’ till the end of the program.
At second last line “d = 5 + e”
here ‘d’ is introduced, we can map it to any of the register r1 or r3, because after this line neither of ‘e’ or ‘c’ is required. Value of ‘b’ is required because we need to return ‘d+f’, and ‘f’ is essentially equal to ‘b’
finally code becomes
r1 = 1
r2 = 10
r3 = 20
r1 = r1 + r2
r1 = r3 + r1
r2 = r3 + r1
r2 = r3 + r1

r1 = r2 + r2
r3 = 5 + r1
return r3 + r2
Therefore minimum 3 registers needed.