The Gateway to Computer Science Excellence

+52 votes

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

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

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

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

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

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.

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.

+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.**

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 ?

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

0

*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

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

It is not giving correct answer

+18 votes

+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

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

+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

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

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

https://gateoverflow.in/8365/gate2015-1_55

here in above we are not using temporaries for variables

please clarify??

+1 vote

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

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

52,218 questions

59,895 answers

201,086 comments

118,134 users