in Compiler Design edited by
21,552 views
62 votes
62 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 __________.

in Compiler Design edited by
21.6k views

4 Comments

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

my approach is right or wrong?? correct me if I'm wrong.

0
0

@Abhishek Tank your approach and the answer both are correct . 

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.

0
0

11 Answers

89 votes
89 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 \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.

edited by

4 Comments

Typo..

T5=T3*T4;
1
1

https://gateoverflow.in/260068/3-address-code?show=260091#c260091

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

0
0

 cause in that question SSA is not asked

0
0
48 votes
48 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.

edited by

4 Comments

He has already counted 't' in the first line, that's why it is not being counted again.
0
0
Why do we need temp10?
0
0
Temporary variables 5
0
0
38 votes
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 

4 Comments

I guess everyone requires a powerful lens during exam - see the word "total" and "temporary" in the 2 questions.
40
40
Thank you Sir for bringing it in our notice :) Will take care further
2
2
@Arjun Sir . If it would have been 3 address code then it would require only 2 temporary variables and total 7 variables right?
0
0
18 votes
18 votes
I am getting 10. Static single assignment means temporary reg will be assigned only once.

2 Comments

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

Related questions