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

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

Sir, the question is asking for least number of variables. I think 3 temporary variables are enough for this expression. Isn't, it?

---

how?

---

By drawing the syntax tree for the above expression, No?

---

I'm not getting any less than 8. Can you give using 3 like I gave for 8 above?

---

yupp, trying to upload pic of my solution, but facing a problem..its asking for URL..which URL 

---

this is what i think.

---

But question is not asking for min. number of registers required 

---

oh, yeah..right sir.
Lets say, here register denotes temporary variables.Then?

---

Then it is not in SSA form. In SSA form a variable can be assigned to only once.

---

By default, three address code is in SSA form. Is, it?

---

Nopes. SSA is a refined version of three address code. You can check compiler text or this wiki link. Though SSA is usually not there in B.Tech syllabus. 
http://en.wikipedia.org/wiki/Three_address_code

---

Okay, thank you sir. :)

---

got answer 3....

---

@Arjun Sir why are we not storing numbers 3 and 5 in the temporary variables before using them ?

---

This concept is not there in ulman book ,which book shall  we refer  ?@arjun sir

---

@arjun sir i m not getting that if they simply said create a 3 address coode and not mention  single static assignment in above question then also answer will remain same ?? if not then what we get   . i want to know what is the diffrence b/w SSA and TAC .  and one more thing if they ask  in place of  temporary variable  if they said register and also not mention SSA but can they use 3AC ??  then answer will be 3 ??

---

@Sultan SSA is not in Ullman? You are using latest edition?

@rajan Without SSA how's the answer 8?

---

In expression if a variable is used only once, then it can be used without assigning to a temporary variable like $q$ and $s$ in above question. But if a variable occurs more than once (or) airthematic op ($*,/$) then assign it (temp var) Suppose, expression is q + c/4*2 -q*2, then SSA $\Rightarrow$

t1 = q
t2 = c/4*2 
t3 = -2*t1 + t2 
t4 = t3 + t1

@Arjun sir, Is it correct ?

---

SSA implies "single" assignment only. Number of addresses is not restricted by it - like in register allocation. In your example, there is no need to use t1=q.

---

In answer above it is written each variable is assigned exactly once, and every variable is defined before it is used What does it mean??

t1 = c/4*2
t2 = -q*2
t3 = t1 + t2
t4 = t3 + q

What about above SSA?

---

Yes, "definition means" it should have a memory. But here, being an expression we can assume all given variables are defined.

SSA does not prohibit, "t1=q", so both the examples are in SSA. But neither is in 3 address form as "t1 = c/4*2" means it has 4 operands.

---

Sir, three-address form says $3$-addresses. I meant $3$ addresses( variables) till now.
Thanks Sir, (learned something new)

---

yes- I guess the terms are ambiguous here. Even "3" is an address. May be "operands" is a better term. I'll see the book what they use.

---

@arjun sir,i have a doubt

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 .

you said that LHS no variable is repeated .

so for the above 3 address code no of temporary variables are 5.

but given answer is 10.

---

total variables

---

Does each variable is assigned only once mean that a temporaray variable is used only once. means when $t1 = t2 +t3$ is done t1 cannot be used again.

---

@Arjun Sir. In the stanford slides you mentioned, constant values are assigned to variables first. I am getting 10 as answer due to these extra assignments: (t1=3, t2=5)

Why aren't we assigning the constant values of 3 and 5 to temporary variables? Why are we using them directly?

Is it because we have to find the minimum no temporary variables? Please clear this doubt.

---

Arjun sir i have a silly doubt, what are theser r,s,q,u and v. Why are they not counted in temporary variables??

in https://gateoverflow.in/39675/gate-2016-1-19 we considered every value as a temporary variable and solved SSA problem. I dont know what i am missing. PLZ PLZ clear my doubt.

---

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

---

yes..

---

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.

x=u-t

y=x*v

t1=y+w

t2=t-z

t3=t1*t2

---

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

t1=r

t1=t1/3

.

.

.

---

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

---

Shouldn’t the order be according to Precedence and associativity?

---

@Arjun Sir why we are not taking temporary variable to store r,t,u,v,w,q,s?

---

@tx3ha we have asked to find minimum no of variables for 3 address code …

if we do like this for eg. 

t1=r;

t2=t1/3

it would take 2 temp variables instead one i.e. t1=r/3 as both r,3 are available at i/p

---

@Arjun Sir , @Prashant 

(i) If the Question asked for Total variables, Will the answer be 15 ?

(8 Temporary + q,r,s,t,u,v,w)

(ii) As a quick strategy,

Can I think like, every variable on the LHS of an assignment should be considered as a Temporary variable & on the RHS of expression, we use the previously defined variables .

 

Is my understanding correct 

---

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.