GATE CS 2017 Set 1 Q.12 (CS Q.12): Intermediate Code Generation, Data Flow Analysis and Code Optimization

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?

$p_1 = a - b$
$q_1 = p_1 * c$
$p_1 = u * v$
$q_1 = p_1 + q_1$

$p_3 = a - b$
$q_4 = p_3 * c$
$p_4 = u * v$
$q_5 = p_4 + q_4$

$p_1 = a - b$
$q_1 = p_2 * c$
$p_3 = u * v$
$q_2 = p_4 + q_3$

$p_1 = a - b$
$q_1 = p * c$
$p_2 = u * v$
$q_2 = p + q$

Official answer and solution

Solution

Apply the principles of Static Single Assignment (SSA) form, where every variable is assigned exactly once and uses refer to the most recent version.

In Static Single Assignment (SSA) form:

Every assigned variable must have a unique name/subscript (each variable is defined exactly once).
Every use of a variable must refer to the specific definition that reaches that use.

Let us trace the original code:

p = a - b: First assignment to p. Introduce a new subscript, say $p_3$ .
q = p * c: First assignment to q. This uses the current definition of p ( $p_3$ ) and assigns to a new version of q, say $q_4$ : $q_4 = p_3 * c$ .
p = u * v: Second assignment to p. Because p cannot be assigned twice in SSA, introduce a new subscript, say $p_4$ : $p_4 = u * v$ .
q = p + q: Second assignment to q. This must define a new version, say $q_5$ . The use of p must refer to the latest definition ( $p_4$ ), and the use of q must refer to the latest definition ( $q_4$ ): $q_5 = p_4 + q_4$ .

Option B represents this exact progression:

p_3 = a - b

q_4 = p_3 * c

p_4 = u * v

q_5 = p_4 + q_4

All four targets ( $p_3, q_4, p_4, q_5$ ) are distinct, and all uses reference their correct reaching definitions.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.