Compiler -Register Allocation

Question

Any one please explain the concept of without spilling

The following program uses six temporary variables $p, q, f, s, t$ and $u$. The code is :
\[
\begin{array}{l}
p=6 \\
q=7 \\
t=p * q \\
s=t+p \\
u=8 \\
u=s * p \\
s=p+u \\
r=r * q \\
t=t+p \\
\text { return } t
\end{array}
\]

Assuming that all operations take their operands from registers. What is the minimum number of registers needed to execute this program without spilling?

• A. 4
  
• B. $\vee 5$
  
• C. 6
  
• D. 3

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

Comments

Though your answer comes out to be right liveness analysis is always carried in bottom up fashion

Reference:-

https://www.youtube.com/watch?v=mPNZAUa54hs

---

Why is u alive after statement 5 when it is being redeclared in statement 6?

---

akb1115 

exactly, they have used the wrong approach,bottom up fashion is used!!