The Gateway to Computer Science Excellence
+43 votes
9.8k 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 (7.2k points)
edited by | 9.8k views
–6
i got 4
–4
i got 7 y, u, t, v, w, t, z.
+1
0

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

+1
+3
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 ?

12 Answers

+49 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 (2.3k points)
edited by
0
Can we do any minimization in static single assignment code if possible?
+7
@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
+8

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.

+44 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 (25.5k points)
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
+37 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 (107 points)
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

+32
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 (3.5k points)
+1
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 (3.4k points)
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 (523 points)
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 (121 points)
+1 vote
I got 6. Plz comment
by Active (3.8k points)
+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
50,666 questions
56,159 answers
193,768 comments
93,763 users