Code Optimization | Principle Sources 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
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
10 Randomly Ordered elements in Quick Sort
Best Quick Sorting Algorithm
Quick Sort Algorithm
Quicksort Implementation
Quick Sort PseudoCode
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 Before and After
Global Common Subexpressions
Common Global Subexpressions in Code Optimization
Global Common Subexpressions
Global Common Subexpressions in Compiler Design
Common Subexpression Elimination
Global common subexpression elimination
common subexpression elimination in compiler design
common subexpression elimination algorithm
Copy Propagation
Copy Propagation
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
- 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
- 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
- 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.
Loop Variant in Code Motion
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
- 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 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
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.