Static Single Assignment form

Question

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______

Comments

See here a,b,c,d require 1 temp variable and x is another variable which never used in storing result

So, total 5

---

Is this still part of the syllabus after 2016 updation?

---

it should be 7, and it is duplicate of

https://gateoverflow.in/228305/compiler-single-static-assignment#c260022

Answer 1

IN SSA RHS OF THE OPERATION CAN USE THE PREVIOUSLY USED VARIABLE ,BUT LHS IN SSA MUST BE UNIQUE.

SOLVING

a1=b1+c1;

c2=a1+x1;

d1=b1+c2;

b2=a1+x1;

the variable are a1,b1,c1,d1,x1,b2,c2 answer 7

Comments

@Shaik Masthan....brother This is the comment before I saw your solution to that question...now I got that!

---

@himgta

THEN SORRY !

it is recent question and you recently commented on this question... that's why i commented like that.

---

@Shaik Masthan sir...you are a true star,always ready for help!

Answer 2

Ans is 7

This can be converted to SSA as

a1 = b + c

c1 = a1 + x

d1 = b + c1

b1 = a1 + x

so total count of variables is 7

Comments

shouldn't the answer be 5 as the b+c,a1+x is repeated

---

No, if variable is repeated on LHS then it is replaced with new variable.

---

according to ME solution the answer is 6, the are using DAG as there solution.

Answer 3

In $SSA$ when we assign the values, the variable to which the values is being assigned should be unique.

RHS of the operation can use the previously used variables, but the LHS in SSA must always be unique.

$R1=b+c;$

$R2=R1+x;$

$R3=R1;$

$R4=R2;$

So total variables =$7$

Comments

But answer according to made easy  solution is 6.

---

sim1234 comment ME solution

---

Yes I attempted that test, their answer is wrong . They did a mistake /misprint in the last step.

Answer 4

Static single assignment means assignment to register can be done only one time-

a(temp3) = b(temp1) + c(temp2);

c(temp5) = a + x(temp4);

d(temp6) = b + c;

b(temp7) = a + x;

total 7 variables are required.

Comments

temp5 and temp7 are same. Do they need separate register allocation?

---

@MiNiPanda,Shouldn't be assignment of each variable unique? In SSA every definition gets its own version.

---

but answer given is 6