retagged by
9,831 views
19 votes
19 votes

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? 

  1. The code contains loop invariant computation 
  2. There is scope of common sub-expression elimination in this code 
  3. There is scope of strength reduction in this code 
  4. There is scope of dead code elimination in this code 
retagged by

2 Answers

Best answer
34 votes
34 votes
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. 

selected by
0 votes
0 votes

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.
Answer:

Related questions

33 votes
33 votes
4 answers
4