search
Log In
9 votes
1.1k views

Give Equivalent SSA.

in Compiler Design
edited by
1.1k views
0
@Arjun sir plz help here ...
1
what is SSA ?
0
Is this topic in syllabus ? If so under which portion ? My coaching institute didn't teach any questions like this :(
0
compiler ! in syllabus...

1 Answer

7 votes
 
Best answer

SSA requires that each variable is assigned exactly once,i.e, the variable cannot be repeated on the LHS of assignment.

For the above Code Snippet, Equivalent SSA is

R1 = 5
R2 = R1 - 3

/* In the Below lines Y may have either R3 or R5 depending on which block executes,
But just that there blocks are different and at a time only one Block executes does not mean,
that they have a same value R3 in both the blocks */

if (R2 < 3)               // This is not LHS of assignment, hence same LHS
{
    R3 = R2 * 2        // Here, Y same but due to SSA, LHS must be different
    R4 = R3
}
else
{
    R5 = R2 - 3        //Here, Y same but due to SSA, LHS must be different
}

/* In the Below lines Y may have either R3 or R5 depending on which block executes */

R6 = (R3,R5) 
R7 = R2 - R6           
R8 = R2 + R7         

selected by
0
R6 = R2 - (R3,R5) but how to know which one should we need to take R3 or R5 ??

one more dout ,

int sum=0;

for (i=0;i<10;i++)

{

  sum =sum + i;         

}

how to convert into SSA ??
0

That depends on which block is accessed, either IF or ELSE and that respective value is used.


In your second question, if I write as

Sum 1 = 0 ;
Sum 2 = Sum 1 + i ;
Sum 3 = Sum 2 + i ;
..
..
..
..
Sum 9 = Sum 8 + i ;

Then, also Compiler will have no problem in evaluating the sum of 10 consecutive terms, just that it is now SSA, a refined version of TAC.  

0
"That depends on which block is accessed, either IF or ELSE and that respective value is used."

Since IF and ELSE both having different variable so how can we identify which need to use??

How can it track ??? I think here we need one more variable...
0

Yes, you can take one more variable, just care has to be taken that it does not violates SSA.

Something like R6 = (R3,R5) 

Now, R6 will have either value.

Actually, U R right, ẃriting it as

 R6 = R2 - (R3,R5) violates TAC. I''ll edit it.

0
i think r8 should be r2+r3 . otherwise result will be wrong
0
How !! Any reason for that ?
0

even though wiki says that its 8 register https://en.wikipedia.org/wiki/Static_single_assignment_form

I think we can actually use the same variabe for y in both block as only one case is going to hit at a time. so no need of the phi function, nor the defination of ssa is voilated. @arjun

Related questions

3 votes
0 answers
1
629 views
Consider the following code segment: $c=b+a$ $e=c-a$ $f=c*e$ $h=c+a$ $i=h+f$ The minimum number of temporary variable required to convert the above code segment to static single assignment form is ________. Doubt : Are we allowed to do minimizations in SSA? if YES then is it always the case, if NO when do we have to do it. Please clarify.
asked Dec 26, 2018 in Compiler Design shreyansh jain 629 views
1 vote
1 answer
2
264 views
X = A / b Y = C + D Y = Y - X X = D + Y Z = F + Y Z = Z + A MInimum number of total variables needed to convert above TAC to Static Single Assignment Answer given ==>11 My apporach X1 = A / b Y1 = C + D Y2 = Y1 - X1 X2 = D + Y2 Z1 = F + Y2 Z2 = Z1 + A Is above code in SSA ??
asked Nov 23, 2018 in Compiler Design jatin khachane 1 264 views
1 vote
0 answers
3
808 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?
asked Nov 15, 2018 in Compiler Design Heena Jain 808 views
1 vote
1 answer
4
948 views
Consider the following code generation: a=b+c; c=a+x; d=b+c; b=a+x; The minimum no. of total variables required to convert the above code to static single assignment form is______
asked Nov 1, 2018 in Compiler Design Sambhrant Maurya 948 views
...