Register Allocation | Made Easy Full Syllabus Test

Question

Given problem and answer :
 

 

I am getting 3 minimum registers as answer, can anyone verify?

here's how I am getting 3 :

T1 = r
T2 = s
T1 = T1 * T2
T2 = t
T3 = u
T2 = T2 – T3
T1 = T1 * T2       // T2 and T3 are free now

 

T2 = p
T3 = q
T2 = T2 * T3
T3 = t
T2 = T2 + T3

 
T2 = T1 + T2

Comments

Yours is correct, if not for the multiple loading of $t$ value in the register. I guess they didn’t account for your #1000IQ move. lol

---

> if not for the multiple loading of t.
What is wrong with it, exactly?

---

I think it’s debatable. Yours is technically correct and doesn’t violate the rules of the question(I think so). But there might be some caveats associated with the compilers themselves on allocation policies on whether to load the loaded variable again.
You can search online but, I presume you won’t have the exact answer unless it’s answered by someone who studies compiler extensively. I wouldn’t worry about it, but then again, it’s I.

Answer 1

I am getting 4 min number of registers .

Given expression : ((p X q) + t) + ((t – u) X (r X s))

Let r1, r2, r3, r4 as registers 

r1 = p

r2 = q

r1 = p X q

r2 = t

r1 = r1 + r2

r3 = u

r2 = r2 – r3

r3 = r

r4 = s

r3 = r3 X r4

r2 = r2 X r3

r1= r1 + r2

 

Comments

@palashbehra5  Are we allowed to load t multiple times ?

---

Isha_99 I mean, that's the complete question I have posted. I don't even know if we are supposed to optimize memory references or the number of register storage. If that was the case, maybe they should have mentioned that.

Edit: Could you also possibly add why multiple LOAD is not allowed under default conditions?

---

Generally while replacing any block in cache memory or pages in main memory we replace those pages that are not going to be used in near future instead of those which we have to access recently , so as to save time of loading same thing multiple times. We can think the same for registers also. Variable t is needed in evaluating expression again so why to remove its value once stored and then reloading it again (if we consider time as a factor ). @palashbehra5 I don’t know exact reason this is just something I thought that might be a reason.

---

Generally while replacing any block in cache memory or pages in main memory we replace those pages that are not going to be used in near future instead of those which we have to access recently , so as to save time of loading same thing multiple times.

What if what we are seeing right now is just a small part of a loop, which will be reiterated over and over (Because then it would be needed in the cache, hence it seems fair to be able to refer to it again).
 

Variable t is needed in evaluating expression again so why to remove its value once stored and then reloading it again (if we consider time as a factor )

Time is not a factor though, right? space is. 

I am not saying you are wrong, it just seems if it is asked about minimizing registers, maybe the problem setter should also clear out other constraints as well.

Answer 2

Here it is given that no spilling can be done so we can’t the result in the memory.

now i am picking new register only when it requires.

we want to multiply p and q both are in memory so we load them both in register from memory.

Load R1,p  (R1← p)

Load R2,q (R2-<q)

mul R1,R1,R2(R1← R1*R2)

now we need to add these value with t.

now t is in memory so we need to bring it back and we have R2 empty.

Load R2,t (R2← t)

now just add them both.

add R1,R1,R2 (R1← R1+R2)

now i need the value of u but R1 store the value of the sum and R2 store t which need next operation so we need to assign another register R3 for u.

load R3,u (R3<-u)

sub R3,R2,R3 (R3← R2-R3)

now we only have R2 left to store the value of r and we need another register for s as R1,R2 store the result of our calculation which needed in future.

Load R2,r (R2<-r)

Load R4,s (R4<-s)

mul R4,R4,R2(R4<-R4*R2)

mul R3,R3,R4(R3<-R3*R4)

add R1,R1,R3(R1-<R1+R3)

Hence answer is 4.