GATE CS 2017 Set 1 Q12 — Intermediate Code Generation

In Static Single Assignment (SSA) form, the following two rules must be satisfied:

1. Each variable is assigned exactly once.
2. Every variable must be defined before it is used in any expression.

Let's convert the given intermediate code step-by-step by subscripting the variables to ensure unique definitions:

1. Statement 1: p = a - b
   This is the first definition of p. Let's name this version $p_3$.
   $$\mathbf{p_3 = a - b}$$
2. Statement 2: q = p * c
   This is the first definition of q. Let's name this version $q_4$. The p on the right-hand side refers to the most recent definition of p, which is $p_3$.
   $$\mathbf{q_4 = p_3 * c}$$
3. Statement 3: p = u * v
   This is a new definition of p. We must use a new version name, say $p_4$.
   $$\mathbf{p_4 = u * v}$$
4. Statement 4: q = p + q
   This is a new definition of q. We name this version $q_5$.
   • The p on the right-hand side refers to the most recent definition of p, which is $p_4$.
   • The q on the right-hand side refers to the most recent definition of q, which is $q_4$.
   $$\mathbf{q_5 = p_4 + q_4}$$

Combining these, the valid SSA form is:

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

This matches Option B.

Elimination of other options:

• Option A: Both p1 and q1 are assigned multiple times, violating the single assignment rule.
• Option C: Variables p2, p4, and q3 are used on the right-hand side without being defined first.
• Option D: The original un-subscripted variables p and q are used on the right-hand side instead of their SSA-defined versions.