GATE CS 2016 Set 1 Q.29 (CS Q.19): Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider the following code segment.

x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;

The minimum number of total variables required to convert the above code segment to static single assignment form is _____.

Your answer

Official answer and solution

Official answer: 10
From: Official GATE 2016 answer key

Solution

Apply the Static Single Assignment rule that each variable is assigned exactly once, counting inputs and versions.

In Static Single Assignment (SSA) form, every variable must be defined (assigned a value) exactly once, and every use of a variable must refer to a unique definition.

Identify the distinct variables that are used as inputs without being defined in the block:

Variable $u$
Variable $t$
Variable $v$
Variable $w$
Variable $z$
These constitute 5 distinct input variables.

Now trace each assignment in the basic block, introducing a new unique variable name for each left-hand side assignment:

x = u - t $\implies x_1 = u - t$
y = x * v $\implies y_1 = x_1 * v$
x = y + w $\implies x_2 = y_1 + w$
y = t - z $\implies y_2 = t - z$
y = x * y $\implies y_3 = x_2 * y_2$

Count the total number of variables in the resulting SSA code:

Input variables: $u, t, v, w, z$ (5 variables)
Defined variable versions: $x_1, y_1, x_2, y_2, y_3$ (5 variables)

\text{Total variables} = 5 + 5 = 10

Final answer

Common trap

Counting only the 5 newly defined variable versions ( $x_1, x_2, y_1, y_2, y_3$ ) and forgetting the 5 input variables ( $u, t, v, w, z$ ).

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 29 of 65, printed as CS Q.19
Section: Computer Science and Information Technology

Report an error in this question

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

Question

Solution

Source