Made easy test series

Question

The minimum number of registers required by an optimal code generation algorithm (intermediate results can be stored in memory). And if possible solve it using Sethi-Ullman Algorithm.

Comments

4????

---

If intermediate result can be stored in memory then only 3 registers required otherwise 4

---

@Priyanka Agarwal Can you show me the method? And can the answer be 2?

---

@Deepanshu That's for the case if the result can't be stored in the memory

---

@Ajit J possible with 2 registers also

---

how 2 possible?

---

srestha mam

 explain me terms like spilling , no intermediate results stored in memory and  intermediate results stored in memory

difference....

---

@Deepanshu

No, intermediate result will store, but we can use one register more than once

right?

I too think 4 registers are required

for p,q,u,s

right?

 

---

i think 2 registers are enough,here we using  spilling -

$r1=p*q$

$r2 =r1+t$

$STORE\; M,r2$ {storing content of r2 to memory location M(spilling)}

$r1=t-u$

$r2=r*s$

$r1=r1*r2$

$ADD \;r2 ,M,r2$

here nothing is mention that operation done only register data so we can use directly p,q,t,u.no need to store them first in registers.

---

Prateek Raghuvanshi u r wrong if u assign r1=t -u then previous r1 will be erased . then how will u get p*q

---

 Deepanshu r1=p*q is added to t and stored in r2 then what is wrong in that??now r1 also available .

---

@Prateek Raghuvanshi

then where p,q,t,r,s stored

Those are also need registers 

right?

---

Here 4 reg needed

 

Load R1 r

Load R2 s

Mul R1 R1 R2

Load R2 t

Load R3 u

Sub R3 R2 R3

Add R1 R1 R3

 

Load R3 p

Load R4 q

Mul R3 R3 R4

Add R3 R3 R2

Add R3 R3 R1

---

 @ srestha ma'am ,  p,q,t,r,s may be memory location where we can directly access the content of p,q,t,r,s.No need  to store them first in registers.nothing is specified 

---

@Prateek Raghuvanshi, I think if you store p,q,r,s,t,u then also you can do in 2 registers but with the help of 2 times spilling whenever required you can store result into memory.

Load R1 r

Load R2 s

Mul R1 R1 R2

Load M R1 (Storing R1 value in Memory)

Load R1 t

Load R2 u

Sub R1 R1 R2

Load R2 M (Storing back result from memory)

Mul R1 R1 R2

Load M R1 (Again storing result in memory)

Load R1 p

Load R2 q

Mul R1 R1 R2

Load R2 t

Add R1 R1 R2

Load R2 M (Storing back the result from memory)

Add R1 R1 R2

---

ultimately we required only 2 registers.

---

No 2 is fine but you were saying that nothing mentioned about p,q,r,s,t then no need to store in registers. I am clarifying that only..:)

---

Shubhgupta what does spilling means ?? plzz explain

---

@Deepanshu, Spilling means store in memory from register for future use and Filling is the reverse operation of spilling , where we are moving a variable from memory to a register is called filling.

read spilling paragraph https://en.wikipedia.org/wiki/Register_allocatio

---

@Prateek Raghuvanshi

@Shubhgupta

where this question is differ from this question https://gateoverflow.in/2138/gate2011-36

In that gate question a,b,c,d,e stored in memory, still 3 reg

right?

then why this question require less registers because of storing?

---

@srestha, you have mistakenly put the same link in comment.

---

ohh sorry, now chk :)

---

in that question its clearly mentioned that you can not store intermediate result in memory but in this question you can store result in memory whenever required(spilling).

---

@Shubhgupta

I think t need filling, not spilling

---

in a nutshell here without spilling we need 4 registers here

and with spilling 2 okkk....

Answer 1

4 register needed.

Comments

@GovindYadav29 any standard resource to study this topic ?

---

Please explain using Sethi Ullman

---

@shikhar500 bro just once you go through spilling and filling of registers,then this topic can easily be understood. For that you can follow GFG .

https://www.geeksforgeeks.org/what-is-spilling/