The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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 
asked in Compiler Design by Active (3.7k points)
retagged by | 1.9k views
Thanks for adding 'out-of-syllabus-now' tag...! :)

1 Answer

+19 votes
Best answer

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


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
4*j is not loop invariant?
Is this removed from curr syllabus?
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.
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.
Not able to imagine/get changes needed to perform strength reduction. Can you please post the whole optimized code?
How do we check that a loop invariant is there?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,403 questions
53,576 answers
70,852 users