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

Thanks for adding 'out-of-syllabus-now' tag...! :)

---

Is it  now in syllabus for GATE 2022?

---

Compiler Design – > Code optimization → Machine Independent

Answer 1

4*j

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

i%2 

is loop invariant for the inner loop

5*i is also loop invariant for inner loop

x += 5*i
can be replaced by 

x += p;
p +=5; (p must be initialized to 0 before the loop).

Thus replacing * with +  gives strength reduction. 

So, only (D) is false here. 

Comments

please remove out of syllabus tag …..it is there in syllabus

---

https://en.wikipedia.org/wiki/Strength_reduction

this will help

---

Strength reduction:

4*j can be written as j<<2

Answer 2

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.