GATE CS 2021 Set 2 Q.40 (CS Q.30): Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider the following 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 struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:

403 and 102

203 and 2

303 and 102

303 and 2

Official answer and solution

Official answer: D
From: Official GATE 2021 answer key

Solution

Apply common subexpression elimination (CSE) to hoist loop-invariant expressions and reuse precomputed results, then count total additions and pointer dereferences.

Variables x, y, z, p, q, and i are in registers. The pointer y is not modified inside the loop, nor is x. Therefore, the expressions $(x + 3)$ , $y\to f1$ , and $y\to f2$ are loop-invariant common subexpressions.

Before the loop, the compiler precomputes these subexpressions into registers:

$t_1 = x + 3$ (1 addition)
$t_2 = y\to f1$ (1 dereference)
$t_3 = y\to f2$ (1 dereference)
$z = t_1 + t_2 + t_3$ (2 additions)
Operations executed before the loop:

\text{Additions} = 1 + 2 = 3

\text{Dereferences} = 2

The loop header is for (i = 0; i < 200; i = i + 2). It executes for $i = 0, 2, 4, \dots, 198$ , which is exactly $\frac{200}{2} = 100$ iterations.
In each iteration, the loop increment i = i + 2 performs 1 addition:

\text{Loop increment additions} = 100 \times 1 = 100

Inside each iteration of the loop, exactly one branch of the if-else is executed:

If $z > i$ : $p = p + t_1$ (1 addition) and $q = q + t_2$ (1 addition), totaling 2 additions.
Else: $p = p + t_3$ (1 addition) and $q = q + t_1$ (1 addition), totaling 2 additions.
No dereferences occur inside the loop because the precomputed register values $t_2$ and $t_3$ are used directly.

\text{Loop body additions} = 100 \times 2 = 200

\text{Loop body dereferences} = 0

Summing all operations:

\text{Total additions} = 3 \text{ (before loop)} + 100 \text{ (increment)} + 200 \text{ (body)} = 303

\text{Total dereferences} = 2 \text{ (before loop)} + 0 = 2

This matches option D (303 and 2).

Final answer

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

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 40 of 65, printed as CS Q.30
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