Compilers: Principles, Techniques, and Tools by ALFRED Aho

Question

Find the minimum number of total variables in SSA form:
a = b + m
m = a + e
d = b + m
b = a + e

Answer 1

In SSA or Single Static Assignment form, each assignment needs to be done to a distinct variable name. This is used in intermediate representation.

Given:

a = b + m ---- (1)

m = a + e ---- (2)

d = b + m ---- (3)

b = a + e ---- (4)

In the question, notice that b has been reassigned a value in equation (4) after being used a couple of times previously. So we can denote this with 2 variables as b1 and b2. Similarly, m is also reassigned in equation (2). So, use m1 and m2 to denote it.

Then, in SSA form,

a = b1 + m1

m2 = a + e

d = b1 + m2

b2 = a + e

We are using the following variables in SSA form: a, b1, b2, d, e, m1, m2. Hence, minimum number of variables needed are 7.

Comments

Using the same concept I did this question of SSA to find the minimum total variables. This question was asked in made easy test series.
Consider the following C code:
d=a+b
e=a-b
f=c+d
g=c-e
a=f+g
b=f-g
c=d+c The minimum number of total variables required to convert the above code segment to a static single assignment form is?

Here also ‘a’ is being used several times before equation 5 and so as per your concept different variables for ‘a’ must be used in equation 5 but in the answer provided by made easy they have used the same variable for ‘a’ everywhere. In short, they have provided the answer for this question as 7 but I think that it should be 10. So please clarify it.

---

My answer for this question comes to be 10 (min number of total variables). If the question asked for minimum number of temporary variables, my answer would be 7. Did they provide an explanation?

Well, what was the answer for the main question? Is 7 the answer?

---

In the actual question, they have asked for the minimum number of total variables and they have provided the answer as 7 but I also think it must be 10. Please see the solution which they have provided.

What concept shall I keep in mind for the future? Please guide.