MadeEasy Test Series 2018: Compiler Design - Intermediate Code

Question

The following program uses six temporary variables p, q, r, s, t and u. The code is :

Assuming that all operations take their operands from registers. The minimum number of registers needed to execute this program without spilling are __________.

The answer given is 5, but I think all lines except the first three lines and the last line are dead code. So the answer should be 2. Please correct me if wrong.

Comments

i agree with you

---

I am getting 4 reg,

---

https://gateoverflow.in/79627/compiler-register-allocation

---

But why should we allocate registers for dead code? In that question, options were provided that's why the legitimate answer should be 5.

---

@Saikat Dutta I think since it isn't mentioned that we could use any of the optimizations thats why we will have to go through the complete code and store all the variables although they may be a part of a Dead Code. It it would have been mentioned that we can use any Optimisation then your answer would have been correct.

---

@Mk Utkarsh

when we have to tell the minimum no. of registers that will be needed w/t spilling ;

the correct procedure that we have to chk from bottom to top, right!!\

and maximum no. of registers that will be present in any instruction will be taken as minimum registers needed right??

am getting 3

---

why bottom up approach is not followed here???thats the standard approach right??

i was getting 3 as answer!

BOTTOM TO TOP APPROACH IS USED!!

p=6 

q=7              {p} 

t=p*q            {p,q} 

s=t+p           {p,q,t} 

u=8              {p,q,s} 

u=s*p          {p,q,s} 

s=p+u       {p,q,u} 

r=r*q          {p,q} 

t=t+p          {p} 

return t       {t}

 

Answer 1

The operation of moving a variable from a register to memory is called spilling

So we will have to allocate only registers we can't store the result in memory

p=6  => lets save value of p in register R1

q=7  => since we need value of p in future instructions we cant save it in R1, so let us use R2 for q

t=p*q => now both p and q are used in future instructions, so we will have to store t in R3

s=t*p => p, q and t, all 3 are being used in future instructions so we will have to store s in R4

u=8  =>  p, q, t and s all 4 are being used in future instructions so we will have to store u in R5

u=s*p  => no need of extra register. The operation is being performed on u that is R5

s=p+u  => since we are updating value of s, again we dont need extra register this will be done in R4

r=r*q  => now only t and p are being used in future instruction so we can store r in any of R2,R4 or R5. So no need of extra register

t=t+p  => since we are updating value of t, again we dont need extra register this will be done in R3

Hence we need only 5 registers R1, R2, R3, R4 and R5

Hence answer should be 5

Answer 2

Not sure how the given variables are temporary. Also since return statement is given we can assume all other code is dead that doesn't determine the return value.

So, the compiler will do just this:

return 48;

As it will be doing constant propagation and dead code elimination. So no. of registers required will be 0.

If constant propagation is not done, then we need to count the number of live variables at each statement. And then take the maximum value of it. At line 2, p and q are live and after line 3, q becomes dead and t becomes live. So, maximum number of live variables at any point is 2.