The Gateway to Computer Science Excellence
+1 vote
316 views
What is the Static Single Assignment (SSA) form for the following code segment:

a = b+c;

c = a+x;

d = b+c;

d = a+x;

Should we use only 1 temporary variable for c=a+x and d=a+x because both of them evaluate the same expression finally?
in Compiler Design by (201 points)
edited by | 316 views
0
nopes. That is code optimization. SSA just requires a single variable to be assigned only once.
0
But in made easy test series, answer is given as 6 total variables (because of code optimization) whereas my answer is 7. so which one is correct sir?
0
I would like to make it more precise that you can assign a single variable once, only in the LHS, though you can make use of it any number of time in the RHS.
0
Yes, 6 should be the answer.

Here is my approach:

t1 = b + c;

t2 = a + x;

b = b + c;

a = a + x;
0

They have provided this solution:

0
Yes, even mine is correct.

The only trick was in the question is not using the same variables in equation 1 and 2 otherwise the value may change.
0
Wait..

How they have used the same variable twice in the LHS?
0
Yes exactly... That is why I was confused
0
That is actually wrong. You cannot use the same variable on the LHS side. It looks completely wrong to me this way.

Check out mine I did it in 6 variables.

A small trick was not using the same variable of RHS in lines 1 and 2 as they are again changing in line 3rd and 4th.

I hope u got it this way.
0
It should be t3= b+ t2 and not b=b+c because the value of c has changed to a+x
0
Due to this reason in the second line I have written t2 = a + x and didn't use c over here as its changing.

Didn't get you?
0
Ah that is correct, but in the third line you wrote b=b+c which is wrong... It should be b=b+t2
+1
According to me the SSA form should be:

t1=b+c

t2=t1+x

t3=b+t2

t4=t1+x

So total 7 variables
0
Why is that wrong?

I didn't change my c initially and I am changing my b in b = b + c, because this way b will not be used after that.

So, do you mean I can't use b in LHS and RHS simultaneously?
0
Your approach is similar to finding minimum number of registers. But that is not how it is done in SSA.
+2
a1=b+c

c1=a1+x

d1=b+c1

d2=a1+x

temp variables: a1 c1 d1 d2---> 4

variables: b c x----> 3

total variables = 4+3 ==> 7
+1
So, 7 is the correct answer.

Anybody confirm plz...
0
So, @Heena What's the correct answer.

Is the solution given by made easy correct.

I mean so can be use same temporary variable twice in the LHS?

Please confirm, if found out.
+1
@`JEET what i feel is we cannot have same value on LHS because static variables cannot be reintialized.
So the answer should be 7
Correct me if I'm wrong
0
@JEET we definitely cannot have two same variables on the left.... So i feel the answer should be 7. But I'm not sure whether we can optimize the code prior to converting it to SSA form. If we can, then the answer would be 6 otherwise 7 (according to me)
0
A guy told me that you can't optimize in SSA and but can optimize in DAG.
Do someone have any authenticate content to read this topic.
I didn't found anything in the Ulman as well.
+4

But I'm not sure whether we can optimize the code prior to converting it to SSA form.

No, You can not do the optimization before converting into SSA form. Optimization is a next phase of Intermediate Representation and SSA is a Type of IR which is widely used by various compilers because it makes various types of Optimizations easy like Dead Code Elimination, Constant Propagation etc.  

Answer will be :

$a_0 = b_0+c_0;$

$c_1 = a_0+x_0;$

$d_0 = b_0+c_1;$

$d_1 = a_0+x_0;$

Please log in or register to answer this question.

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,648 questions
56,430 answers
195,210 comments
99,924 users