Features of Optimization

• Transformation of a computer program to maximize the efficiency of the executable program (ie, use fewer resources)
• Transformation is done by the compiler as well as the programmer.
• It is one of the important phases of the compiler
• Rarely guarantee that the resulting code is the best possible.
• Transformation must preserve the meaning of the program.

Two ways of Code Optimization

• Machine Dependent Optimization
  • It requires the knowledge of the target machine.
  • An attempt to generate object code that will utilize the target machine’s registers more efficiently is an example of machine-dependent code optimization.
• Machine Independent Optimization

  • Data Flow Optimization

    • Common Sub-expression elimination

      Eliminate re-computation of an expression

      

    • Constant folding and combining

      Eliminating Unnecessary operation

      

    • Strength reduction

      Replace expensive operations with cheaper ones.

      

    • Copy propagation

      The process of replacing the occurrences of targets of direct assignments with their values. It eliminates useless moves.

      

    • Dead Code Elimination

      Eliminating those code that are never used in a program

      This program calculates, the sum of numbers from 1 to 100, but the statement J = 5 is not being used in any part of the program is called Dead Code

      

  • Loop Optimization

    • Loop-invariant code motion

      If an expression inside a loop doesn’t change after the loop is entered (i.e., it’s invariant), calculate the value of the expression outside the loop and assign it to a temporary variable. Then use the temporary variable in the loop.

    • Loop unrolling

      We try to decrease the number of times the loop condition is tested.

      //Eg
      //In this code, the testing of i<=100 
      //will be performed 100 times.
      
      i = 1
      while(i<=100)
      {
      	X[i] = 0;
      	i++;
      }
      //After replication,
      //In this code, if we replicate the body of the loop, 
      //then the number of tests will be 50
      i = 1
      while(i<=100)
      {
      	X[i] = i;
      	i++;
      	X[i] = i;
      	i++;
      }
      

    • Loop fusion

      This technique merges the bodies of two loops if the two loops have the same number of iterations and they use the same indices.

      //Before:
      for(i = 0; i<10; i++){
      	for(i = 0; i<10; i++){
      		x[i,j] = 0;
      	}
      	for(i = 0; i<10; i++){
      		x[i,i] = 1;
      	}
      }
      //After:
      for(i = 0; i<10; i++)
      {
      	for(j = 0; j<10; j++){
      		x[i,j] = 0;
      		x[i,i] = 1;
      	}
      }