+11 votes
1.9k views

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
asked
retagged | 1.9k views
0
Thanks for adding 'out-of-syllabus-now' tag...! :)

## 1 Answer

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

answered by Veteran (399k points)
selected by
0
4*j is not loop invariant?
+1
Is this removed from curr syllabus?
+2
Yes, not in current syllabus. @srestha "j" is changing for each iteration. A loop invariant is a condition which is true across each iteration, during entry as well as exit from a loop.
0
4*j is not loop invariant as it's value will be different in each loop iteration. But i%2 and 5*i results same till the inner loop executes.
0
Not able to imagine/get changes needed to perform strength reduction. Can you please post the whole optimized code?
0
How do we check that a loop invariant is there?
Answer: