GATE CSE 2017 Set 1 | Question: 12

Question

Consider the following intermediate program in three address code

p = a - b
q = p * c
p = u * v
q = p + q

Which one of the following corresponds to a static single assignment form of the above code?

• A.

  p1 = a  - b
  q1 = p1 * c
  p1 = u  * v
  q1 = p1 + q1

• B.

  p3 = a  - b
  q4 = p3 * c
  p4 = u  * v
  q5 = p4 + q4

• C.

  p1 = a  - b
  q1 = p2 * c
  p3 = u  * v
  q2 = p4 + q3

• D.

  p1 = a - b
  q1 = p * c
  p2 = u * v
  q2 = p + q
  

Comments

A answer.i think

---

@Uddipto no its b)

---

why? we can clear p1 and load u-v to p1 again

---

Yes but Static Single Assignment says that a variable cannot be used more than once in the LHS, and it is to be initialised atmost once.

---

In static single assigment we can assign only once bu read many times

---

yes but cant we completely clear the variable.. then reassign again

---

till I didn't understand what is static single assignment??

---

a = b;

a = 5;

This is not SSA because a is assigned value more than once. More detailed explanation is given in the selected answer.

---

In option B , in the last line, rightmost var should be q4 not q.

Correct me?

---

B IS CORRECT A IS WRONG 

---

In option A – the 3^rd expression is overridden when again p1 is used.

In option C – the 2^nd expression is wrong as p2 is not initialized before but used.

In option D – the 2^nd  expression is wrong as p is not initialized before but used.

Here each and every variable used are distinct. So the answer is (B).

---

Detailed Video Solution: GATE CSE 2017 - Static Single Assignment Form SSA Question

Static Single Assignment Form SSA Complete Lecture: https://www.youtube.com/watch?v=CQV8hSeMrx8  

Answer 1

References:

• https://en.wikipedia.org/wiki/Static_single_assignment_form
• http://www.cse.iitd.ernet.in/~nvkrishna/courses/winter07/ssa.pdf
• https://www.cs.cmu.edu/~fp/courses/15411-f08/lectures/09-ssa.pdf
• http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf

So, B is ans.

Comments

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. Thus option B only satisfies the above criteria.

Answer 2

Option D INCORRECT because in last line we are directly adding P+Q without moving it to register

option C INCORRECT because in last line Q3+P4 is done however they dont even contain any value

Option A INCORRECT because P1 has been assigned value twice

So OPTION (B) is CORRECT

Answer 3

Answer is B.

Answer 4

OPTION B becoz in option A same variable is used p1 , q1 which creates ambiguity also bt in option B different variable is used .

Comments

But in option B, last line q5= p4 + q

instead of it should be q5= p4+ q4 because q is pointing to value  of statement 2

Please correct me if i am wrong