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

edited | 9.7k views

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 Veteran (430k points)
edited by
+8
They are "variables" which are defined (hence no longer temporary). In the 2016 question they asked explicitly for "total variables".
+5
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??
+5
yes..
0
thanku so much sir.
0
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??
+1
@Arjun , @sushmita , In normal 3 address code representation, we could reuse the temporaries at the LHS right (or LHS can be repeated)?
0
@arjun Sir why the temporary variables will be 5. If we do like this then they will be 3.

x=u-t

y=x*v

t1=y+w

t2=t-z

t3=t1*t2
0
And what is that calculating?
+4

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

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

+1

@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?

+12

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.

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

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

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

t1=r

t1=t1/3

.

.

.
0

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

+1

From the dragon book -:

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

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 Active (1.8k points)
+4
Why are we not storing u,v,q,w,s before using them?
0
t7=t6-t2

Temporary variable 8

Total variable= 8+7=15

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

by Loyal (5.3k points)
+1
Simple and different approach....
by (15 points)
0
how?
–2
+8
Answer is 8. It was given by official GATE key.