GATE CSE 2015 Set 1 | Question: 55

Question

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__________________.

Comments

Is it 15? 8 temporary + 7 memory variables.

---

I have this doubt only whether we will take 5 and 3 to be stored in variables or as constants?

If constants then ans=15

else 17

---

No. The numbers are not counted.

The numbers are immediate (if you remember from CO, in the instruction set architecture). But these variables like 'u' and 'v' need to be accessed from the memory and thus need to be stored in a variable.

---

Are u sure?

Because In one of the questions :

eg: x=2*3*w

is considered as a 4 addr code because here we consider the no. of operands.

---

x=2*3*w is a four address code because it uses 4 operands. And operands != variables.

operands is anythin on which any operation is done (LOAD,STORE,ADD etc)

---

Can u elaborate a bit more?

---

What I mean is, a variable is required to store a value presented in the memory so that we don't have to access it again. In the given address codes when we say "a = b * 3", a is a temporary variable which will store the operation between the operands 'b' and '3'. Here b is a variable where as '3' is not fetched from memory but in fact directly available from the input.

So if they ask number of total variables, we count all those that are not Immediate values (temporary variables are just the storage after operation is done on the operands i.e 'a' in the previous example).
And as for operands and variables, they don't mean the same. I have already stated what variable is.
In a 3-address code we use 3 operands (not variables) such as  "a = b+3". a,b and 3 are operands.

---

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

---

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

---

Detailed Video Solution: GATE CSE 2015 - Static Single Assignment Form SSA Question

Static Single Assignment Form SSA Complete Lecture: https://www.youtube.com/watch?v=CQV8hSeMrx8  

Answer 1

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

Comments

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 ?

Answer 2

Temporary variable 8

Total variable= 8+7=15

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

Comments

Simple and different approach....

---

This should be the best answer

---

Best Answer

Answer 3

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.

Comments

Why are we not storing u,v,q,w,s before using them?

---

t7=t6-t2

Answer 4

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.