The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
1.4k 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 in Compiler Design by Active (3.7k points)
retagged by | 1.4k views

1 Answer

+17 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 (359k 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:

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

41,147 questions
47,708 answers
147,683 comments
62,407 users