The GATE Grind

GATE 2017 CS – Question 22

Compiler Design · Intermediate Code Generation · 1 mark · Multiple choice

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?

  1. $p_1 = a - b$; $q_1 = p_1 * c$; $p_1 = u * v$; $q_1 = p_1 + q_1$
  2. $p_3 = a - b$; $q_4 = p_3 * c$; $p_4 = u * v$; $q_5 = p_4 + q_4$
  3. $p_1 = a - b$; $q_1 = p_2 * c$; $p_3 = u * v$; $q_2 = p_4 + q_3$
  4. $p_1 = a - b$; $q_1 = p * c$; $p_2 = u * v$; $q_2 = p + q$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $p_3 = a - b$; $q_4 = p_3 * c$; $p_4 = u * v$; $q_5 = p_4 + q_4$

Explanation

In static single assignment form every variable is assigned only once, and each use refers to the latest assignment. Option A assigns $p_1$ and $q_1$ twice. Option C uses names such as $p_2$ and $p_4$ that were never assigned. Option D uses $p$ and $q$ without any number. Option B gives each assignment a new name and each use refers to the right earlier one, so it is correct.