ISRO-DEC2017-67

Question

Consider the code segment

int i,j,x,y,m,n;
n = 20;
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        if(i%2)
        {
            x += ((4*j)+5*i);
            y += (7+4*j)
        }
    }
}
m=x+y;

Which one of the following is false?

• A. The code contains loop invariant computation
• B. There is scope of common sub-expression elimination in this code
• C. There is scope of strength reduction in this code
• D. There is scope of dead code elimination in this code

Comments

I mean D is correct ! It is false among all

---

Question image has not loaded it seems

---

What is dead code elimination????

Answer 1

• loop invariant: A fragment of code that resides in the loop and computes the same value in all iterations. In given loop if $\text{(i%2)}$ computes same value within loop of $j$. This code can be moved out of the loop.

 for(i=0;i<n;i++) {
if(i%2)
   {
    for(j=0;j<n;j++)
    {
       ......

This movement is called code hoisting

$A$ is true 

• The sub expression  $4*j$ is used at two places which can be eliminated.

$B$ is true

• Strength reduction: Operations that consume more time and space can be replaced by simple operations that produce the same result.

  $4*j$ can be replaced by $j << 2$

$C$ is true

• There is no dead / Unreachable code.

$D$ is false

Answer is $D.$

Comments

the variable m is not usead so cant it be considered as dead code

---

The3_Phenomenon see the last line m=x+y .

Answer 2

option D

There is no scope of dead code elimination.

Answer 3

Option A : Why the code 

x+=((4*j)+5*i);
y+=(7+4*j);

is loop invariant ? x and y get updated with with change in values of i,j for every iteration

Option D: Also if we use constant propogation for n the loop headers become .. i<20... and j<20... respectively.

Hence n = 20 is a possible candidate for dead code elimination 

So isnt A the right option ?