The Gateway to Computer Science Excellence
+58 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 by Boss (30.7k points)
edited by | 9.7k views

4 Answers

+107 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$

by Veteran (430k points)
edited by
They are "variables" which are defined (hence no longer temporary). In the 2016 question they asked explicitly for "total variables".
in 2016 if they had asked for temporary variables then answer is 5?? All the variables which will be mentioned in expression will be taken as defined??
thanku so much sir.
All the variables mentioned in the expression will be taken as defined and defined means they all are assigned memory and treated as variables. Right??
@Arjun , @sushmita , In normal 3 address code representation, we could reuse the temporaries at the LHS right (or LHS can be repeated)?
@arjun Sir why the temporary variables will be 5. If we do like this then they will be 3.





And what is that calculating?

@arjun sir, This was gate 2016 question.

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

I want to ask the number of minimum temporary variables required to do so.

temp1 = u - t;
temp2 = temp1 * v;
temp3 = temp2 + w;
temp4 = t - z;
temp5 = temp3 * temp4;

5 are needed. Use temporary variable just to store the result not for variables and just see dependancy.

Since it is single static assignment , so use different temporary variable every time when u find new result.


@arjun sir @prashant. Why have you used temp1 and temp2?  We can use a variable on LHS atmost once in SSA. Why can't we use x and y on LHS to store the results?

x = u - t;
y = x * v;
temp1 = y + w;
temp2 = t - z;
temp3 = temp1 * temp2; 

Why is it necessary to store the result in a temporary variable when we have a permanent variable for it?


one resoning is how u know x is used in next instruction when you executing first instruction. like variable t is always used as input not as output. 

so we used a temporary variable just for those variables who are updated.

Second point :

x = u - t;
y = x * v;

if at all 2nd instruction executing 1st before x is actualy updated then 2nd instruction will take old value of x not new. so compiler remove these conflicts by using temporary variables.

@prashant. Thank you :D
Won't the DMAS Rule be applicable in

t3 = u*v;
t4 = t3/w?

I mean Division should be performed before Multiplication?
No, it's based on the operator precedence rules.
nice explanation @Arjun sir this static single assignment form problem was very confusing ,but your solution clearify it thanks sir
@thor t1 can be used again but further assignment in t1 is not allow
why can't we use like






@Abhisek Tiwari 4  question is for least no. of temporary variables..


From the dragon book -:

They have not reused variable names like in ordinary three address code. So the answer should be 8.

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


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 Active (1.8k points)
Why are we not storing u,v,q,w,s before using them?
+3 votes

Temporary variable 8

Total variable= 8+7=15

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

by Loyal (5.3k points)
Simple and different approach....
–3 votes
Answer is 3.
by (15 points)
Answer is 8. It was given by official GATE key.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
104,735 users