Code Optimization | Principle Sources of Optimization





 Principle of Optimization

Principle of Optimization

The Principle Sources of Optimization

  • Preserve the semantics.
  • Apply relatively low-level semantic transformations.
    • Algebraic identities like i + 0 = i
    • Performing the same operation on the same values yields the same result => i *1 = 1 * i = i
 Compiler Design

Compiler Design

Quick Sort

void quicksort ( int m , int n )
{
/* recursively sorts a r[m] through a [n] */
   int i , j ;
   int v , x ;
       if ( n <= m) return ;
             i = m - 1 ;  j = n ; v = a [n] ;
             while ( 1 ) {
   do i = i + 1 ; while (a [i] < v) ;
   do j = j  - 1 ; while ( a [j ] > v) ;
      if ( i  >=  j ) break ;
	x = a [i] ; a [i] = a [j ] ; a [j ] = X ;  
             /* swap a [i] , a [j ] */
}
	x = a [i] ; a [i] = a [n] ; a [n] = X ;    
             /* swap a [i] , a [n] */
quicksort (m , j ) ;
quicksort ( i+ 1 , n) ;

 Quick Sort

Quick Sort

 Quick Sort

10 Randomly Ordered elements in Quick Sort

 Quick Sort

Best Quick Sorting Algorithm

 Quick Sort Code

Quick Sort Algorithm

Quicksort Implementation

Quicksort Implementation

 Quick Sort PseudoCode

Quick Sort PseudoCode

 Code Optimization

Code Optimization

Semantics-Preserving Transformations

  • A program will include several calculations of the same value , such as an offset in an array.
  • Examples of function-preserving (or semantics-preserving) transformations are,
    • Common-sub expression elimination,
    • Copy propagation,
    • Dead-code elimination, and
    • Constant folding
 Semantics Preserving Transformations

Semantics Preserving Transformations

 Semantics Preserving Transformations Before and After

Semantics Preserving Transformations Before and After

Global Common Subexpressions

 Global Common Subexpressions

Common Global Subexpressions in Code Optimization

 Global Common Subexpressions

Global Common Subexpressions

 Global Common Subexpressions in compiler design

Global Common Subexpressions in Compiler Design

 Common Subexpression Elimination

Common Subexpression Elimination

Global common subexpression elimination

Global common subexpression elimination

 common subexpression elimination in compiler design

common subexpression elimination in compiler design

common subexpression elimination algorithm

common subexpression elimination algorithm

Copy Propagation

 Copy Propagation

Copy Propagation

Dead- Code Elimination

Dead- Code Elimination

Dead- Code Elimination in Code Optimization

  • A variable is placed at a point in a program if its value can be used eventually or otherwise it is die at that point.
  • A related idea is dead (or useless) code statements that compute values that never get used.
 Dead- Code Elimination

Dead- Code Elimination

  • if ( debug) print . . .
  • debug = FALSE
    • Copy propagation changes debug by FALSE, then the print statement is dead because it never be reached.
  • Arriving at compile time that the value of an expression is constant instead using is known as constant folding.
  • One advantage of copy propagation turns the copy statement into dead code.
  • For example, copy propagation followed by dead-code elimination removes the assignment to x and transforms the code.

Code Motion

Code Motion in Code Optimization

Code Motion in Code Optimization

  • Loops are a very important place for optimizations particularly the inner loops where programs move to spend the bulk of their time.
  • The running time of a program may be upgrade if we reduce the number of instructions in an inner loop , even if we increase the amount of code outside that loop.
  • An important changes that decreases the number of code in a loop is code motion.
 Code Motion

Code Motion

  • This transformation capture expression that get the same result independent of the number of times a loop is executed (a loop-invariant computation) and calculate the expression before the loop.
  • Note that the motion "before the loop" assumes the existent of an entry for the loop, one basic block to which all jumps from outside the loop go.
 Code Motion

Loop Variant in Code Motion

Strength Reduction

 Strength Reduction

Strength Reduction in Code Optimization

  • Another important optimization is to find induction variables in loops and optimize their computation. A variable x is said to be an "induction variableā€œ if there is a positive or negative constant c such that each time x is assigned, its value increases by c.
  • For instance, i and t2 are induction variables in the loop containing B2. Induction variables can be computed with a single increment (addition or subtraction) per loop iteration.
  • The transformation of replacing an expensive operation, such as multiplication, by a cheaper one, such as addition, is known as strength reduction.
 Strength Reduction

Strength Reduction

  • But induction variables not only permit us sometimes to function a strength reduction; frequently it is possible to remove all but one of a group of induction variables whose values remain in lock step as we go everywhere the loop.
 Strength Reduction

Strength reduction example in compiler design

  • When processing loops, it is useful to work "inside-out" ; that is, we shall start with the inner loops and proceed to progressively larger, surrounding loops.
  • Thus, we shall see how this optimization applies to our quicksort example by beginning with one of the innermost loops: B3 by itself.
  • Note that the values of j and t4 remain in lock step; every time the value of j decreases by 1 , the value of t4 decreases by 4, because 4 * j is assigned to t4. These variables, j and t4, thus form a good example of a pair of induction variables.

Basic Blocks and Flow Graphs

Construction of the Representation

  • Partition the intermediate code into basic blocks.
  • The basic blocks get the nodes of a flow graph and the edges indicate the flow.
 Construction of the Representation

Construction of the Representation

Basic Blocks

  • The flow of control enter only the basic block among the first instruction.
  • Control will quit the block without halting or branching, except possibly, at the last instruction in the block.

Constructing Basic Blocks

  • Represent a group of leaders, the first instruction of blocks.
  • A basic block exist of a leader and all the following instructions until the next leader.


Related Searches to Code Optimization | Principle Sources of Optimization