Static Single Assignment

Question

Consider the following code segment

$a=b-c$

$d=a+d$

$a=d+e$

$d=c*f$

$d=a*d$

The minimum number of total variables required to convert the above code segment to static single assignment form is _________.

 
Answer given is 10. Should it be 9????

Comments

@Venkat Sai, correct there is no need of doing this way, i just want to show how temp variable are used.

---

the given code can be rewritten as

a1=b-c

d1=a1+d

a2=d1+e

d2=c*f

d3=a2*d2

also after expanding the R.H.S of every statement we are not getting the similarities of R.H.S of one statement with the R.H.S of any other statement so we can consider this is the minimal representation of the given code(in case if the R.H.S of any sttement matches with the R.H.S of any statement then we have to consider only single statement(since the question hasbeen asked about minimum number of variables  )).now in this code if we count the total number of variables present it becomes 10.

Also we can cross verify it by creating the DAG of that given code.

---

They updated the answer and now its 6 ..

Answer 1

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.

t1=b-c

t2=t1+d

t3=t2+e

t4=c*f

t5=t3*t4

temporary variable = t1,t2,t3,t4,t5

variable=b,c,d,e,f

total variable = 10

Comments

@ Gurdeep Saini can we proceed like this ,that first we find what the code is exactly doing and then generate its 3 address code ,it is also giving 10 as ans

 

---

I found a shortcut to find number of variables in static single assignment ie draw DAG for this code and count number of edges , those will be equal to number of variables required.

---

I think the slides numbered 15 and 16 might be useful in this

https://www.cs.cmu.edu/~fp/courses/15411-f08/lectures/09-ssa.pdf

It states that every variable and every computation of the program should have a unique assignment as per SSA.