Convert the given Three Address Code (TAC) into Static Single Assignment (SSA) ?

Question

$x=5$

$x=x-3$

$\textbf{if } x<3$

$\quad y=x*2$

$\quad w=y$

$\textbf{else}$

$\quad y=x-3$

$w=x-y$

$z=x+y$

Give Equivalent SSA.

Comments

@Arjun sir plz help here ...

---

what is SSA ?

---

Is this topic in syllabus ? If so under which portion ? My coaching institute didn't teach any questions like this :(

---

compiler ! in syllabus...

Answer 1

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         

Comments

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

---

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.  

---

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

---

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.

---

i think r8 should be r2+r3 . otherwise result will be wrong

---

How !! Any reason for that ?

---

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