24,422 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__________________.

Other static single assignment questions: https://gateoverflow.in/118292/gate2017-1-12 and https://gateoverflow.in/39675/gate2016-1-19

4 temprorary variables are required if SSA is not asked

The least number of temporary variables required to create a three-address code in static single assignment form: $8$

The least number of total variables required to create a three-address code in static single assignment form: $8 + 7(q,r,s,t,u,v,w) = 15$

Problem related to total variables: GATE2016-1-19

Answer is $8$.

In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once, and every variable is defined before it is used. Existing variables in the original IR are split into versions, new variables.

We will need a temporary variable for storing the result of each binary operation as SSA (Static Single Assignment) implies the variable cannot be repeated on LHS of assignment.

$q + r / 3 + s - t * 5 + u * v/w$

$t1 = r/3;$
$t2 = t*5;$
$t3 = u*v;$
$t4 = t3/w;$
$t5 = q + t1;$
$t6 = t5 + s;$
$t7 = t6 - t2;$
$t8 = t7 + t4$

http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/240%20TAC%20Examples.pdf

by

no of temporary variables is equal to no of operators in the expression for SSA.

Here SSO is mentioned.So can we say that it is similar to Register Spilling? As because Register Spilling means intermediate result stored into temporary location?

In Question if “Register Spilling” is mentioned can we treat it as an SSO concept?

@Arjun Sir why are we not assigning numbers 3 and 5 in the temporary variables before using them ?

Temporary variable 8

Total variable= 8+7=15

* / Have same precedence and left associative same as +,- and left associative Simple and different approach....
This should be the best answer

The given expression is

q  + r / 3 + s - t * 5 + u * v/w

To store result of each binary operation , we need a temporary variable. Three Address Code (TAC) and  Static Single Assignment  form (SSA)  implies the variable cannot be repeated.

So,

t1 = r/3;
t2 = t*5;
t3 = u*v;
t4 = t3/w;
t5 = q + t1;
t6 = t5 + s;
t7 = t5 - t2;
t8 = t7 + t4

There should be at least 8 temporary variables  required  to create TAC.

by

Why are we not storing u,v,q,w,s before using them?
t7=t6-t2

To simply put, Static Single Assignment is a modification of Three-Address Code, such that no temporaries are re-assignable.

PS: An address can be a:-

1. name
2. constant
3. temporary variable generated by compiler.

It is common knowledge that $+$ and $-$ have equal priorities. And so do $*$ and $/$. And they both have left associativity to break the tie.

$$q+r/3+s−t∗5+u∗v/w$$

So, $r/3$ is done first. Then $t*5$... so on.

I'll use $a,b,c,d...$ for temporaries instead of $t_1,t_2...$ to avoid using subscripts repeatedly.

Here's, the $SSA$ code:

$a=r/3$
$b=t∗5$
$c=u∗v$
$d=c/w$
$e=q+a$
$f=e+s$
$g=f−b$
$h=g+d$

8 temporaries are used.