Study Notes on Code Optimization

 Types of Code Optimization

The code optimization process is mainly classified into two different types:

1. Machine Independent Optimization – This code optimization phase attempts to improve the intermediate code to get a better target code as the output. The part of the intermediate code which is transformed here does not involve any CPU registers or absolute memory locations.
2. Machine Dependent Optimization – Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of the memory hierarchy.

Code Optimization is done in the following different ways

1. Compile Time Evaluation :
   (i)  A = 2*(22.0/7.0)*r
        Perform 2*(22.0/7.0)*r at compile time.
   (ii)  x = 12.4
         y = x/2.3
         Evaluate x/2.3 as 12.4/2.3 at compile time.
2. Variable Propagation :
   /Before Optimization
   c = a * b
   x = a

   till
   d = x * b + 4
    
   /After Optimization
   c = a * b 
   x = a
   till
   d = a * b + 4

    

   Hence, after variable propagation, a*b and x*b will be identified as common sub-expression.
3. Dead code elimination : Variable propagation often leads to making assignment statement into dead code
      c = a * b
      x = a
      till
      d = a * b + 4  
      
       /After elimination :
       c = a * b
       till
       d = a * b + 4
4. Code Motion :
   1. Reduce the evaluation frequency of expression.
   2. Bring loop invariant statements out of the loop.
      a = 200;
      while(a>0)
       {
           b = x + y;
           if (a % b == 0}
                 printf(“%d”, a);
         }
      /This code can be further optimized as
      a = 200;
      b = x + y;
      while(a>0)
       {
           if (a % b == 0}
           printf(“%d”, a);
         }
      
5. Induction Variable and Strength Reduction :
   1.  An induction variable is used in the loop for the following kind of assignment i = i + constant.
   2. Strength reduction means replacing the high strength operator with the low strength.
      i = 1;
      while (i<10)                                                         
      {                                                                            
          y = i * 4;
      }
       
      /After Reduction
      i = 1
      t = 4
      {
         while( t<40)
         y = t;
         t = t + 4;
      }