Redirected
in Compiler Design edited by
1,916 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.
in Compiler Design edited by
1.9k views

2 Comments

i think we can use graph coloring.
0
0
i am getting 5 as answer.
0
0

2 Answers

1 vote
1 vote
Best answer

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
by

4 Comments

ha these are different .. i just want to know 7 is correct na
0
0
yes. its correct
1
1

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}

0
0
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