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

  i. Function Preserving

  ii. Loop optimization

• Function preserving

• Common Sub Expression Elimination

  The expression that produces the same results should be removed out from the code

  Example

• Constant folding

  If expression generates a constant value then instead of performing its calculation again and again we calculate it once and assign it.

  Example

• Copy Propagation

  In this propagation a F value is been send to G and G value is been send to H We can eliminate G variable directly assigning the value of F to H.

• Dead Code Elimination

  Dead code is one or more than one code statements, which are:

  • Either never executed or unreachable,

  • Or if executed, their output is never used.

  Thus, dead code plays no role in any program operation and therefore it can simply be eliminated.

Partially dead code Elimination

• There are some code statements whose computed values are used only under certain circumstances, i.e., sometimes the values are used and sometimes they are not.
• Such codes are known as partially dead-code.

• The above control flow graph depicts a chunk of program where variable ‘a’ is used to assign the output of expression ‘x * y’.
• Let us assume that the value assigned to ‘a’ is never used inside the loop.
• Immediately after the control leaves the loop, ‘a’ is assigned the value of variable ‘z’, which would be used later in the program.
• We conclude here that the assignment code of ‘a’ is never used anywhere, therefore it is eligible to be eliminated.
• Likewise, the picture below depicts that the conditional statement is always false, implying that the code, written in true case, will never be executed, hence it can be removed.

3. Loop Optimization

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 varing 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

Peephole Optimization

• This optimization technique works locally on the source code to transform it into an optimized code. By locally, we mean a small portion of the code block at hand.
• These methods can be applied on intermediate codes as well as on target codes.
• A bunch of statements is analyzed and are checked for the following possible optimization:

1. Redundant instruction elimination

• At source code level, the following can be done by the user:

At compilation level, the compiler searches for instructions redundant in nature. Multiple loading and storing of instructions may carry the same meaning even if some of them are removed. For example:

• MOV x, R0
• MOV R0, R1

We can delete the first instruction and re-write the sentence as:

MOV x, R1

2. Unreachable code

• Unreachable code is a part of the program code that is never accessed because of programming constructs.
• Programmers may have accidently written a piece of code that can never be reached.

Example:

    void add_ten(int x)
   {
   return x + 10;
   printf(“value of x is %d”, x);
   }

• In this code segment, the printf statement will never be executed as the program control returns back before it can execute, hence printf can be removed.

• In this code segment, the printf statement will never be executed as the program control returns back before it can execute, hence printf can be removed.

3. Flow of control optimization

• There are instances in a code where the program control jumps back and forth without performing any significant task.

• These jumps can be removed. Consider the following chunk of code:

  ...     
  
  MOV R1, R2
  
  GOTO L1
  
   ...
  
   L1:   GOTO L2
  
  L2:   INC R1
  

• In this code, label L1 can be removed as it passes the control to L2. So instead of jumping to L1 and then to L2, the control can directly reach L2, as shown below:

                 ...      
                 MOV R1, R2
                 GOTO L2
                 ...
                  L2:   INC R1
  

4. Algebraic expression simplification

• There are occasions where algebraic expressions can be made simple. For example, the expression a = a + 0 can be replaced by a itself and the expression a = a + 1 can simply be replaced by INC a.

5. Strength reduction

• There are operations that consume more time and space. Their ‘strength’ can be reduced by replacing them with other operations that consume less time and space, but produce the same result.
• For example, x * 2 can be replaced by x << 1, which involves only one left shift. Though the output of a * a and a2 is same, a2 is much more efficient to implement.

6. Accessing machine instructions

• The target machine can deploy more sophisticated instructions, which can have the capability to perform specific operations much efficiently.
• If the target code can accommodate those instructions directly, that will not only improve the quality of code, but also yield more efficient results.