GATE CSE 2006 | Question: 60

Question

Consider the following C code segment. 

for (i = 0, i < n; i++)
{ 
    for (j = 0; j < n; j++)
    { 
        if (i%2)
        { 
            x += (4*j + 5*i); 
            y += (7 + 4*j); 
        } 
    } 
}

Which one of the following is false? 

• A. The code contains loop invariant computation 
• B. There is scope of common sub-expression elimination in this code 
• C. There is scope of strength reduction in this code 
• D. There is scope of dead code elimination in this code 

Comments

In syllabus now*

---

It is still in the syllabus of GATE 2026.

 

---

@65-Tarun yes that is in compiler design sub.

Answer 1

4*j

is used at two places- so common subexpression elimination is possible

$\text{i%2}$ is loop invariant for the inner loop

$5*i$ is also loop invariant for inner loop

$\text{x += 5 * i}$     can be replaced by  $\text{x += p;}$
$\text{p += 5;}$ ($p$ must be initialized to $0$ before the loop).

Thus replacing $*$ with $+$  gives strength reduction. 

The code does not contain unreachable or dead code. because all statements inside the loops are reachable during the execution of the loops.

So, only $(D)$ is false here. 

Comments

awesome answer sir

 

---

In the given code, loop jamming is not possible because both the loop variables are different, right??

---

is loop jamming in syllabus? @Hira Thakur

Answer 2

Answer=

For Option A : The code contains loop invariant computation  = TRUE 

for (i = 0, i < n; i++)                              
{           

if (i%2)

  for (j = 0; j < n; j++)
    {
           if (i%2)

Now the i%2 will be computer for only 1 for loop

For Option B : There is scope of common sub-expression elimination in this code : TRUE

     {

       m = 4*j 

            x += (4*j + 5*i); // it becomes  x += (  m + 5*i); 

            y += (7 + 4*j); //it becomes y += (7 +  m ); 

        } 

• Now We only have to compute only 1 time 4*j (later it will be strength reduced by the way )     rather computing it two times 

For Option C : There is scope of strength reduction in this code : TRUE

1. 4*j = j<<4.

• we can use left shift operator as compared to the multiply operator.

• Because  modern compilers often optimize x * 2 to x << 1,because left shift operation is more   efficienct to multiply operators in terms of   (* 2^n) 

  For Option D: There is scope of dead code elimination in this code : FALSE

•   Because All statements inside the loops are reachable during the execution of the loops.

 

 

Comments

Thanks for the amazing Explanation

---

Ans = D

A      loop invarient

     i % 2 is evaluated once per outer-loop iteration instead of n times.

     5 * i is computed once instead of n times.

B    Common sub-expression is 4*j

C   Strength reduction - done by

     t = 0;
     for (j = 0; j < n; j++) {
         t += 4; // instead of t=4*j
    }

D   

Dead code elimination removes code whose result is never used.

Here:

• x is updated.
• y is updated.
• The if condition affects execution.

---

best answeer thankkk uuu tarun!

Answer 3

There is scope for dead code elimination in this code.

Explanation:

1. The code contains loop invariant computation:

   • True. The expressions (4*j + 5*i) and (7 + 4*j) are computed inside the inner loop but do not depend on the inner loop variable j. They can be moved outside the inner loop to improve efficiency.

2. There is scope for common sub-expression elimination in this code:

   • True. The expression (4*j + 5*i) is computed twice with the same values of i and j inside the inner loop. Common sub-expression elimination can be applied to avoid redundant computations.

3. There is scope for strength reduction in this code:

   • True. The expression (4*j + 5*i) involves multiplication and addition. Strength reduction could be applied by replacing the multiplication with a series of cheaper operations.

4. There is scope for dead code elimination in this code:

   • False. The code does not contain unreachable or dead code. All statements inside the loops are reachable during the execution of the loops.

Comments

Yes and at the end we can add 7*n^2 to j as there woule be total n^2 computations of j. But how come the subexpression 4*i + 5*j be an invariant. Because here if you see we are actually using the value of both i and j right.