Question 14290 – Compiler-Design

 In compiler theory, common subexpression elimination is a compiler optimization that searches for instances for identical expressions (i.e, they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.

For example: Consider the following block of code

a=x+y+z;  

r=p+q; 

b=x+y+r; 

The code after common subexpression elimination.

t=x+y;

a=t+z;  

r=p+q; 

b=t+r; 

In the given code

z = x + 3 + y -> f1 + y -> f2;

for (i = 0; i < 200; i = i+2)  {

      if (z > i)  {

             p = p + x + 3;

             q = q + y -> f1;

      }  else  {

             p = p + y -> f2;

             q = q + x + 3;

      }

  }    

X+3 is common subexpression, also  y -> f1 & y -> f2  is found in first line itself so they are also like common subexpression.

Hence the code after common subexpression

t1=x+3; t2=y -> f1 ; t3= y -> f2; 

z = t1 + t2 + t3;

for (i = 0; i < 200; i = i+2)  {

      if (z > i)  {

             p = p + t1;

             q = q + t2;

      }  else  {

             p = p + t3;

             q = q + t1;

      }

  }    

Hence two dereference operations (of the form y->f1 or y->f2) in the optimized code.

The number of addition in the optimized code are:

Loop will execute for 100 times and in loop one addition (i+2)

So 100 additions.

Inside loop we have two additions (either in if block or in else block) so 200 additions inside loop

Hence 300 additions in loop (loop body as well as inside)

First 2 lines contains 3 additions

t1=x+3; 

z = t1 + t2 + t3;

Hence total 303 additions.

So 303 and 2 are the answer.