edited by
27,256 views
69 votes
69 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 __________.

edited by

12 Answers

Best answer
98 votes
98 votes

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
49 votes
49 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
39 votes
39 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 

18 votes
18 votes
I am getting 10. Static single assignment means temporary reg will be assigned only once.
Answer:

Related questions

35 votes
35 votes
4 answers
1
Sandeep Singh asked Feb 12, 2016
10,023 views
The attribute of three arithmetic operators in some programming language are given below.$$\begin{array}{|c|l|}\hline \textbf{OPERATOR} & \textbf{PRECEDENCE} & \textbf{...
80 votes
80 votes
7 answers
2
makhdoom ghaya asked Feb 13, 2015
28,737 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...