The Gateway to Computer Science Excellence
+52 votes
11.7k views

Consider the following code segment.

x = u - t;
y = x * v; 
x = y + w;
y = t - z; 
y = x * y;

The minimum number of total variables required to convert the above code segment to static single assignment form is __________.

in Compiler Design by Loyal
edited by | 11.7k views
–6
i got 4
–4
i got 7 y, u, t, v, w, t, z.
+3
0

What if there was no "static single assignment " mentioned? Then the answer?

+1
+6
Total no of variable required = 10

and Total Temporary variable = 5
0
0

@Verma Ashish

Thanks, my concept was not clear .. :)

0
Can anyone explain why I can't get answer as 9, because in the last instruction we can reuse y space also , instead of using new temporary variable ?
0
@Ritwik -

I got answer as 3 minimum variables, if we are not using SSA

x=u-t

x=x*u

x=x+u

t=t-u

t=x*t

12 Answers

+67 votes
Best answer

In Static Single Assignment when we assign the values, the variables to which the value is being assigned should be unique.

$T1 = u - t$

$T2 = T1 * v$

$T3 = T2 +w$

$T4 = t-z$

$T5 = t3 * t4$

So $T1.....T5 =5 + (u,t,v,w,z)=5$

Total 10 variables.

Note: RHS of the operation can use the previously used variables, but LHS in SSA must always be unique.

by Active
edited by
0
Can we do any minimization in static single assignment code if possible?
+12
@Rahul,I dont think that we are allowed to do any kind of optimization before Intermediate representation.
for eg : if given code is $(a+b)-a$ then in SSA form we need two temporary variables.
$t1=a+b$
$t2=t1-a$
in me test series they are doing optimization before IR representation that i think is not correct..
0
nice explanation prateek
0
easy explanation thank you
+12

I also agree to @reena_kandari, following is the screenshot from Ullman and they have not done any optimization:

Though it helps in code optimization.

+1

@Prateek K@chauhansunil20th

what will be the answer for this question 

@Arjun@Pawan@Bikram 

@Ram Swaroop

 

 

+5

@PRK

It should be 7

4 temporary+3(b,c,x)

0
@PRK @Ram Swaroop

I think that given 3 address code is already in SSA form, since there is no variable which is assigned twice. So answer should be 5. Please correct me if i am wrong.

My doubt is why you are using two different variable for c, in 2nd statement c can be assigned to (a+x), since this is first time we are assigning something to c.
0
We already used c in first statement
0
Suppose if this question is like this

1) a=b+c

2) p=a+x    

3) d=b+c    ( b and c used here are not modified since last used )

4) b=a+x

 

so now is it necessary to assign (b + c) of line 3 to new temporary variable or we can use the temporary variable assigned for first line a=b+c?
+45 votes
x(temp3) = u(temp1) - t(temp2);
y(temp5) = x * v(temp4); 
x(temp7) = y + w(temp6);
y(temp9) = t - z(temp8); 
y(temp10) = x * y;

so ans should be 10.

by Boss
edited by
0

Why are we reassigining u and v to temp1 and temp2 ? In the previous year question solved here at https://gateoverflow.in/8365/gate2015-1_55 we did not do that ... What is the generic procedure that we can use to solve both the previous and this year question ?

+1
No need to assign ! Just assigned for counting purpose
+1
what would be the answer if they just asked temporary varuables?
+1
Check LHS and find which are repeated.so they need new temp variables!
0
why r u not counting t???
0
He has already counted 't' in the first line, that's why it is not being counted again.
0
Why do we need temp10?
0
Temporary variables 5
+38 votes

Static single assignment means assignment to register can be done one time only.

so, draw the GRAPH and count number of nodes which will give the number of register required.

Graphical  solution 

by
0

Why are we reassigining u and v to temp1 and temp2 ? In the previous year question solved here at https://gateoverflow.in/8365/gate2015-1_55 we did not do that ... What is the generic procedure that we can use to solve both the previous and this year question ?

0
Will it always give the correct answer?
0

Try this method on this question. https://gateoverflow.in/8365/gate2015-1_55

It is not giving correct answer

+36
I guess everyone requires a powerful lens during exam - see the word "total" and "temporary" in the 2 questions.
+2
Thank you Sir for bringing it in our notice :) Will take care further
0
@Arjun Sir . If it would have been 3 address code then it would require only 2 temporary variables and total 7 variables right?
+18 votes
I am getting 10. Static single assignment means temporary reg will be assigned only once.
by Active
+2
please explain how its 10?? What i am finding is min temporary registers required and getting only 5..
0
okok got it....
static single assignment plays key role!!
+10 votes
t0 = u - t;

t1 = to * v;

t2 = t1 + w;

t3 = t - z;

t4 = t2 * t3;

Total variables required will be 5(t, u, v, w, z) + 5(temp. variables) = 10
by Active
edited by
0
@arjun sir @ravi_ssj4 Why are you using t0 and t1 for x and y? They can atleast appear once on LHS.

If we do it like this then temporary variables will be 3 only. Correct me if I'm wrong.

x=u-t

y=x*v

t1=y+w

t2=t-z

t3=t1*t2
+9 votes
ans. is 10

here every variable can be assigned with a value only once.

t1 =  t2 - t3

t4 = t1 * t5

t6 = t4 + t7

t8 = t2 - t9

t10 = t6 - t8
by Junior
0
why are we using temporaries for variables u,v.w.x,y,z?

https://gateoverflow.in/8365/gate2015-1_55
here in above we are not using temporaries for variables
please clarify??
+9
The question here asks for total number of variables and not just temporary variables.
+1
And in another ques they are asking just for temporary variables.
got it
thanku sir
0

t8 = t2 - t9

This should be $t8 = t3 - t9; $

+5 votes
I got 5.
by
+1 vote
I got 6. Plz comment
by Active
+3
i got 10
0
I got 6 too
0
SSA- Static Single Assignment
Converting ordinary code into SSA form is primarily a simple matter of replacing the target of each assignment with a new variable
So from target u'll get 5 directly +  5 from right hand side which is use first time .
Static means yo can't change value for that particular variable
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,895 answers
201,086 comments
118,134 users