Consider the following ANSI C code segment: Assume that the variable y… — GATE CS 2021 Set 2 Q30

Consider the following $\text{ANSI C}$ code segment:

z=x + 3 + y->f1 + y->f2;
for (i = 0; i < 200; i = i + 2) 
{
    if (z > i) 
    {
        p = p + x + 3;
        q = q + y->f1;
    } else 
    {
        p = p + y->f2;
        q = q + x + 3;
    }
}

Assume that the variable $y$ points to a $\textsf{struct}$ (allocated on the heap) containing two fields $\textsf{f1}$ and $\textsf{f2}$ , and the local variables $\textsf{x, y, z, p, q,}$ and $\textsf{i}$ are allotted registers. Common sub-expression elimination $\text{(CSE)}$ optimization is applied on the code. The number of addition and the dereference operations (of the form $\textsf{ y ->f1}$ or $\textsf{y ->f2}$ ) in the optimized code, respectively, are:

View worked solution

Answer: D

To optimize the code using Common Sub-expression Elimination (CSE), we identify expressions that are computed multiple times without their operands being modified:

x + 3 is computed in the initialization of z and inside both branches of the if-else statement. Since x is not modified, we can compute it once: t1 = x + 3.
The dereferences y->f1 and y->f2 are accessed in the initialization of z and inside the loop. Since y and its fields are not modified, they can be evaluated once and stored in registers: t2 = y->f1 and t3 = y->f2.

The optimized code becomes:

t1 = x + 3;          // 1 addition, 0 dereferences
t2 = y->f1;          // 0 additions, 1 dereference
t3 = y->f2;          // 0 additions, 1 dereference
z = t1 + t2 + t3;    // 2 additions

for (i = 0; i < 200; i = i + 2) { // 1 addition per iteration (i = i + 2)
    if (z > i) {
        p = p + t1;  // 1 addition
        q = q + t2;  // 1 addition
    } else {
        p = p + t3;  // 1 addition
        q = q + t1;  // 1 addition
    }
}

Now, let us count the operations:

Dereference Operations:
- Only $2$ dereferences are performed outside the loop (one for y->f1 and one for y->f2).
Addition Operations:
- Outside the loop: $1$ (for t1) + $2$ (for z) = $3$ additions.
- Inside the loop: The loop runs for $i = 0, 2, 4, \dots, 198$ $i = 0, 2, 4, \dots, 198$ , which is exactly $100$ $100$ iterations.
  - In each iteration, the increment i = i + 2 takes $1$ addition.
  - Regardless of the branch taken in the if-else block, exactly $2$ additions are executed.
  - Additions per iteration = $1 + 2 = 3$ additions.
  Total additions inside the loop = $100 \times 3 = 300$ $100 \times 3 = 300$ additions.
- Total additions: $3 + 300 = 303$ additions.

Thus, the number of additions is $303$ and the number of dereferences is $2$ .

Free practice · Your answers on this page are not saved.

GATE CS 2021 Set 2 Q30 — Local Optimization

Related questions