GATE CS 2016 Set 1 Q19 — Data Flow Analyses: Constant Propagation, Liveness, CSE

To convert the given code segment into Static Single Assignment (SSA) form, every variable must be assigned exactly once, and every variable must be defined before it is used.

Step 1: Identify the Input Variables

The variables that are read but not defined within this block are the input variables:

• $u, t, v, w, z$

This gives 5 input variables.

Step 2: Version the Assigned Variables

We now version each assignment to $x$ and $y$ so that each version is assigned exactly once:

1. x = u - t; → $x_1 = u - t$
2. y = x * v; → $y_1 = x_1 imes v$
3. x = y + w; → $x_2 = y_1 + w$
4. y = t - z; → $y_2 = t - z$
5. y = x * y; → $y_3 = x_2 imes y_2$

Step 3: Count the Total Variables

Let's list all the distinct variables present in the SSA form:

• Inputs: $u, t, v, w, z$ (5 variables)
• SSA versions of $x$: $x_1, x_2$ (2 variables)
• SSA versions of $y$: $y_1, y_2, y_3$ (3 variables)

$$\text{Total variables} = 5 + 2 + 3 = 10$$

Thus, the minimum number of total variables required is 10.