Optimization

• Optimization is a program transformation technique, which tries to improve the code by making it consume less resources (i.e. CPU, Memory) and deliver high speed.
• In optimization, high-level general programming constructs are replaced by very efficient low-level programming codes.
• A code optimizing process must follow the three rules given below:

1. The output code must not, in any way, change the meaning of the program.
2. Optimization should increase the speed of the program and if possible, the program should demand less number of resources.
3. Optimization should itself be fast and should not delay the overall compiling process.

• Efforts for an optimized code can be made at various levels of compiling the process.

1. At the beginning, users can change/rearrange the code or use better algorithms to write the code.
2. After generating intermediate code, the compiler can modify the intermediate code by address calculations and improving loops.
3. While producing the target machine code, the compiler can make use of memory hierarchy and CPU registers.

• Optimization can be categorized broadly into two types:

  Machine Independent and Machine Dependent.

Machine Independent Optimization

• In this optimization, the compiler takes in the intermediate code and transforms a part of the code that does not involve any CPU registers and/or absolute memory locations.

• For example:

      do
     {
        item = 10;
       value = value + item; 
       } while(value<100);
  

• This code involves repeated assignment of the identifier item, which if we put this way:

  Item = 10;
   do
     {
  value = value + item; 
     } while(value<100);
  

  should not only save the CPU cycles, but can be used on any processor.

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 memory hierarchy.

Machine independence includes two types

1. Function Preserving

2. Loop optimization

1. Loop Optimization

Most programs run as a loop in the system. It becomes necessary to optimize the loops in order to save CPU cycles and memory. Loops can be optimized by the following techniques:

• Invariant code: A fragment of code that resides in the loop and computes the same value at each iteration is called a loop-invariant code. This code can be moved out of the loop by saving it to be computed only once, rather than with each iteration.

  • Induction analysis: A variable is called an induction variable if its value is altered within the loop by a loop-invariant value.

  • Strength reduction: There are expressions that consume more CPU cycles, time, and memory. These expressions should be replaced with cheaper expressions without compromising the output of expression. For example, multiplication (x * 2) is expensive in terms of CPU cycles than (x << 1) and yields the same result.

  We are going to perform optimization on loops.

• Code Motion

  It specifies on a condition if we perform some operations to be carried out and then compare for a condition.

  Instead of that perform the calculation outside the loop and assign a value in the calculation.

• Strength Reduction

  It specifies the operators such as multiplication and division can be replaced by a addition and subtraction respectively.

  The multiplication operator can be easily replaced by left shift operator a<<1 Division can be replaced by a a>>1 operator.

• Frequency Reduction

  In this case if a expression inside a loop is not dynamically affected by a loop we calculate it outside the loop and use the value inside the loop.

• Loop Distribution

  It specifies the values in a particular loop to be assigned to a array keeps of varying i.e the array location in which a loop need to be work again and again. We can use two different loops which allows loop distribution