in Compiler Design retagged by
24,422 views
76 votes
76 votes
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__________________.
in Compiler Design retagged by
24.4k views

4 Comments

Admins, please add "static-single-assignment" as a tag of this question.

 

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

12
12
4 temprorary variables are required if SSA is not asked
1
1

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

0
0

7 Answers

135 votes
135 votes
Best answer

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

edited by
by

4 Comments

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

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?

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

Temporary variable 8

Total variable= 8+7=15

* / Have same precedence and left associative same as +,- and left associative

2 Comments

Simple and different approach....
1
1
This should be the best answer
0
0
8 votes
8 votes

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.

2 Comments

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

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.

edited by