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 (355k 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?
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

37,996 questions
45,492 answers
131,517 comments
48,591 users