Redirected
edited by
1,929 views
0 votes
0 votes
The following program uses six different variables p, q, r, s, t and u. The code is:

p=6

q=7

t=p*q

s=t+p

u=8

u=s*p

s=p+u

r=r*q

t=t+p

return t

Assume that all operations take their operands from registers, the minimum number of registers needed to execute this program without spilling are _____________?

 

Given answer is 5, but my answer is 4.

I think that the step u=8 can be skipped since 'u' is being reinitialized in the next step.
edited by

2 Answers

Best answer
1 votes
1 votes

Here all the registers defined above the line... has future reference to the statements that are below the line and will be used in future. so we cannot use them to store other values before the line

 i have represented them in ovals with same color. so its 5 registers.

selected by
0 votes
0 votes

 

BOLD lines describe Live variable just before entering the next statement 

{ r }

p=6

{ p,r }

q=7

{ p,q,r }

t=p*q

{ p,q,r,t }

s=t+p

{ p,q,r,t,s }

u=8

{ p,q,r,t,s }

u=s*p

{ p,q,r,t,u }

s=p+u

{ p,q,r,t }

r=r*q

{ p,t }

t=t+p

{ t }

return t

Since we can see that at max 5 variables are live at any instance of time. Therefore we need 5 registers to avoid spilling.

 

edited by

Related questions

0 votes
0 votes
0 answers
3
nbhatt asked Jan 12, 2023
440 views
8 votes
8 votes
1 answer
4
Kapil asked Nov 2, 2016
3,007 views
How to draw register allocation interference graph ?Can anyone explain this along with " What is a live variable "?Explain with the example given below ?a = 1 b = 10 c = ...