22,276 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 __________.

@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 my approach is right or wrong?? correct me if I'm wrong.

It can also be done like

x1 = u – t

y1 = x1 * v

x2 = y1 + w

y2 = t – z

y3 = x2 – y2

Note :- SSA form does not do common subexpression elimination.

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 \ast v$

$T3 = T2 +w$

$T4 = t-z$

$T5 = t3 \ast t4$

So $T1 \ldots 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.

Typo..

T5=T3*T4;

Why in question in above link they have not counted variables in rhs.

cause in that question SSA is not asked

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

He has already counted 't' in the first line, that's why it is not being counted again.
Why do we need temp10?
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. I guess everyone requires a powerful lens during exam - see the word "total" and "temporary" in the 2 questions.
Thank you Sir for bringing it in our notice :) Will take care further
@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

please explain how its 10?? What i am finding is min temporary registers required and getting only 5..
okok got it....
static single assignment plays key role!!