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 __________.

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

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

what will be the answer for this question

@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?
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
+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

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.

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?
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!!
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
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
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
+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;$

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