Register

GATE CSE 2015 | Set 1 | Question: 55

• retagged by
43,895 views
97 97 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__________________.

9 Answers

Best answer
171 171 votes

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
46 46 votes

Temporary variable 8

Total variable= 8+7=15

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

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

6 6 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
1 1 vote

8 variables are required.

Static Single Assignment(SSA)

A variable cannot appear more than one on the left hand side of assignment operator. 

Lets try this definition for the given expression: 

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

here, we have 3 operators, multiplication, addition & division. We have to keep in mind the precedence & associativity of them. 

Associativity: left to right

precedence: 1. * & /  2. +

A=r/3

B=t×5

C=u×v

C1=C/w

A1=A+q

A2=A1+s

A3=A2-B

A4= A3+C1

SSA variable set: {A,B,C,A1,A2,A3,A4,C1}

Minimum number of variables=8.

 

 

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2015 | Set ...Next → · GATE CSE 2015 | Set ...
← Previous in category · GATE CSE 2015 | Set ...Next in category → · GATE CSE 2015 | Set ...
Position:
Show:

Related questions

73 73 votes
5 answers 5 answers
29.5k
29.5k views
Misbah Ghaya asked Feb 12, 2015
29,536 views
GATE CSE 2015 | Set 1 | Question: 8
For computer based on three-address instruction formats, each address field can be used to specify which of the following:(S1) A memory operand(S2) A processor register(S...
48 48 votes
5 answers 5 answers
17.5k
17.5k views
Arjun asked Feb 14, 2017
17,485 views
GATE CSE 2017 | Set 1 | Question: 12
Consider the following intermediate program in three address codep = a - b q = p * c p = u * v q = p + qWhich one of the following corresponds to a static single assignme...