Code Optimization
What is Code Optimization
Optimization is the process of transforming a piece of code to make more efficient (either in terms of time or space) without changing its output or side-effects. Code Optimization refers to techniques a compiler can employ in an attempt to produce a better object language program than for the given source program. Code Optimization phase improves the intermediate code i.e., it reduces the code and removes the repeated or unwanted instructions from the intermediate code.
16 May 2013
ChonuChinnu's
Code Optimization
The transformations provided by an optimizing the compiler should have the following properties:
Must preserve the meaning of the program. That is, an optimization must not change the output produced by a program for a given input. Must speed up program by a measurable amount. The places for potential improvements by the user and the compiler:
Source Code Front End Intermediate Code Code Generator Target Code
User can Change Algorithm Transform Loops
Compiler can Improve Loops Procedure Calls Address Calculations
Compiler can Use Registers Select Instructions Do Peephole Transformation
Places for Potential Improvements By User & Compiler
16 May 2013 ChonuChinnu's 3
Code Optimization
(Contd..)
Code improvement phase consists of control-flow and dataflow analysis followed by the applications of transformations. The organization of the code optimizer is shown:
Front End Code Optimizer Code Generator
Control-Flow Analysis
Data-Flow Analysis
Transformations
Organization of the Code Optimizer
16 May 2013 ChonuChinnu's 4
Basic Block
A basic block is a sequence of consecutive statements in which the flow of control enters at the beginning and leaves at the end without halt or possibility of branching except at the end. For example, the following sequence of three address statements forms a basic block.
t1:= a * a t2:= a * b t3:= 2 * t2 t4:= t1* t3 t5:= b * b t6:= t1+ t5
A name in a basic block is said to be live at a given point if its value is used after that point in the program i.e., in another basic block.
16 May 2013
ChonuChinnu's
Partition into Basic Blocks
The procedure to partition a sequence of three address statements into basic blocks is as given below: We first determine the set of Leaders, the first statements of basic blocks. The rules are:
The first statement is a leader. Any statement that is the target of a conditional or unconditional goto is a leader. Any statement that immediately follows a goto or conditional goto statement is a leader.
For each leader, its basic block consists of the leader and all statements up to but not including the next leader or the end of the program.
16 May 2013 ChonuChinnu's 6
Example
void quicksort(int m, int n) { int i, j; int v, x; if(n<=m) return; /* fragment begins here*/ i=m-1; j=n; v=a[n]; while(1) { do i=i+1; while (a[i]<v); do j=j-1; while (a[i]>v); if(i>=j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[j]; a[j]=x; /* fragment ends here*/ quicksort(m,j); quicksort(i+1,n); } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. i:=m-1 j:=n t1=4*n v:=a[t1] i:=i+1 t2=4*i t3:=a[t2] if t3 < v goto (5) j:=j-1 t4=4*j t5:=a[t4] if t5 < v goto (9) if i >= j goto (23) t6=4*i x:=a[t6] 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. t7=4*i t8=4*j t9:=a[t8] a[t7] :=t9 t10=4*j a[t10] :=x goto (5) t11=4*i x:=a[t11] t12=4*i t13=4*n t14:=a[t13] a[t12] :=t14 t15=4*n a[t15] :=x
Three-Address code for Mentioned Quick Sort C Code
C Code for Quick Sort
16 May 2013 ChonuChinnu's 7
Flow Graphs
Flow graphs is a directed graph which gives the flow of control of information to the set of basic blocks making up a program. The nodes of the flow graph are the basic blocks. One node is distinguished as initial. It is the block whose leader is the first statement. There is a directed edge from block B1 to block B2, if B2 can immediately follow B1 in some execution sequence. That is, if
There is a conditional or unconditional jump from the last statement opf B1 to the first statement of B2 or B2 immediately follows B1 in the order of the program, and B1 does not end in an unconditional jump. We say that B1 is the predecessor of B2 and B2 is the successor of B1
16 May 2013
ChonuChinnu's
Flow Graph for Example
i:=m-1 j:=n t1=4*n v:=a[t1]
i:=i+1 t2=4*i t3:=a[t2] if t3 < v goto B2
j:=j-1 t4=4*j t5:=a[t4] if t5 < v goto B3
if i >= j goto B6
16 May 2013
t6=4*i x:=a[t6] t7=4*i t8=4*j t9:=a[t8] a[t7] :=t9 t10=4*j a[t10] :=x goto B2
t11=4*i x:=a[t11] t12=4*i t13=4*n t14:=a[t13] a[t12] :=t14 t15=4*n ChonuChinnu's a[t15] :=x
Principle Sources of Optimization
A transformation of a program is called local if it can be performed by looking only at the statements in a basic block, otherwise, it is called global. Function Preserving Transformation: Compiler can improve a program without changing its function in several ways. They are :
o o o o Common Subexpressions Elimination Copy Propagation Dead-code Elimination Constant Folding
16 May 2013
ChonuChinnu's
10
Common Subexpressions Elimination
An expression E is called a common subexpression if E was computed, and the values of variables in E have not changed since the previous computation. In other words, if an expression appears more than one time it is said to be repeated and is called as the common expression. Consider basic block B5
t6=4*i x:=a[t6] t7=4*i t8=4*j t9:=a[t8] a[t7] :=t9 t10=4*j a[t10] :=x goto B2
Before Subexpressions Elimination
Expressions 4*i and 4*j are repeated. That means t6=t7 and t8=t10. Eliminating t7 and t10 and using t6 and t8 instead of them.
t6=4*i x:=a[t6] t8=4*j t9:=a[t8] a[t6] :=t9 a[t8] :=x goto B2
After Subexpressions Elimination
16 May 2013
ChonuChinnu's
11
Common Subexpressions Elimination
Considering basic block B6
t11=4*i x:=a[t11] t12=4*i t13=4*n t14:=a[t13] a[t12] :=t14 t15=4*n a[t15] :=x
Before Subexpressions Elimination
Expressions 4*i and 4*n are repeated. That means t11=t12 and t13=t15. Eliminating t12 and t15 and using t11 and t13 instead of them.
t11=4*i x:=a[t11] t13=4*n t14:=a[t13] a[t11] :=t14 a[t13] :=x
After Subexpressions Elimination
These eliminations are local since it is only within a block. If the same is done between different blocks it is said to be global.
16 May 2013
ChonuChinnu's
12
Flow Graph for Example
i:=m-1 j:=n t1=4*n v:=a[t1]
i:=i+1 t2=4*i t3:=a[t2] if t3 < v goto B2
j:=j-1 t4=4*j t5:=a[t4] if t5 < v goto B3
if i >= j goto B6
16 May 2013
t6=4*i x:=a[t6] t7=4*i t8=4*j t9:=a[t8] a[t7] :=t9 t10=4*j a[t10] :=x goto B2
t11=4*i x:=a[t11] x:=t3 t12=4*i a[t2] :=t5 t13=4*n a[t4] :=x t14:=a[t13] goto B2 a[t12] :=t14 t15=4*n ChonuChinnu's a[t15] :=x
x:=t3 t14 :=a[t1] a[t2] :=t14 a[t1] :=x 13
i:=m-1 j:=n t1=4*n v:=a[t1]
i:=i+1 t2=4*i t3:=a[t2] if t3 < v goto B2
j:=j-1 t4=4*j t5:=a[t4] if t5 < v goto B3
Flow Graph After Local & Global Subexpressions Elimination
x:=t3 t14 :=a[t1] a[t2] :=t14 a[t1] :=x
if i >= j goto B6
x:=t3 a[t2] :=t5 a[t4] :=x goto B2
16 May 2013
ChonuChinnu's
14
Copy Propagation
Assignments of the form p:=q is called copy statements. Consider the copy statements shown below:
a:= d+e b:= d+e
t:= d+e a=:=e t:= d+e a=:=e
c:= d+e
c:= d+e
Thus the idea behind the copy propagation transformation is to use p and q whenever possible after the copy statement p:= q
For example, the assignment statement x:=t3 in block B5 is a copy. Copy Propagation applied to B5 yields: x:=t3 a[t2] :=t5 a[t4] :=t3 goto B2
16 May 2013
ChonuChinnu's
15
Dead-Code Elimination
A variable is said to be live at a point if its value can be used subsequently. Otherwise it is said to be dead at that point. For example, consider a part of any program flag = false; if(flag) print. In the above statements flag is always set to false before checking for the condition. Since it is always false the print statement is never executed. Thus, the print statement is dead because it is never reached. One advantage of copy propagation is that often the copy statement into dead code. For example, copy propagation followed by dead-code elimination removes the assignment to x and transforms the basic block B5 statements to: a[t ] :=t
16 May 2013 ChonuChinnu's
a[t4] :=t3 goto B2
2 5
16
Loop Optimization
Optimizations has to be done within loops especially within inner loops. The running time of a program may be improved if we decrease the number of instructions in an inner loop, even if we decrease the amount of code outside the loop. The three techniques for loop optimization are:
o Code Motion o Induction Variable Elimination o Reduction in Strength
16 May 2013
ChonuChinnu's
17
Code Motion
An important modification that decreases the amount of code in a loop is code motion. This transformation takes an expression that yields the same result independent of the number of times a loop is executed (loop invariant computation) and places the expression before the loop. For example,
while(i<=limit-2) /* the value of limit-2 will not change forever*/ Code motion will result in the equivalent of t=limit-2 while(i<=t)
16 May 2013
ChonuChinnu's
18
Induction Variables and Reduction in Strength
Induction variables are those whose values doesnt change forever. If these are placed as statements or conditions within some language constructs they take much time for evaluation of its value. Thus they can be removed out of the construct and can be placed out of the construct, whose value can be used directly for the condition and the statement. Reduction in strength is the method of replacing the complex operation by simple operations to speed up the processing of the object code.
16 May 2013
ChonuChinnu's
19
i:=m-1 j:=n t1=4*n v:=a[t1] t2=4*I t4=4*j
t2:=t2 + 4 t3:=a[t2] if t3 < v goto B2
t4:=t4 - 4 t5:=a[t4] if t5 < v goto B3
Flow Graph After Induction Variable Elimination
if i >= j goto B6
x:=t3 a[t2] :=t5 a[t4] :=x goto B2
x:=t3 t14 :=a[t1] a[t2] :=t14 a[t1] :=x
16 May 2013
ChonuChinnu's
20
Data Flow Analysis
Data Flow Analysis collect information about the various parts (block) of the program and disseminate the information to the blocks in the flow The information collected during this process may not be used in the optimization when it does not retain the semantics of the program The information collected are kept in four sets as: Spawn or Generated Destroy Input Output
16 May 2013
ChonuChinnu's
21
Data Flow Analysis
(Contd..)
The information about When a variable is defined When it is redefined How it is available How it is used etc are required from the perception of optimization
16 May 2013
ChonuChinnu's
22
Data Flow Analysis
Algorithm maintainDataFlowInformation( ) initInput( ); initOutput( ); initSpawn( ); initDelete( ); for each block B { Do the flow analysis in a block Do the flow analysis across the blocks }
(Contd..)
16 May 2013
ChonuChinnu's
23
Data Flow Analysis
(Contd..)
The various kind of information that requires attentions is: Reaching definitions finds all definitions that reach it Upward exposed uses find all uses that it reaches Live Variables decides whether the variable is alive at that point Available Expressions decides whether the result of this expression is available at a point in the program flow
16 May 2013
ChonuChinnu's
24
Reachable Definitions
X = 10; X = 20; X = 30; Each variable is defined and is reachable at the appropriate places. The set of definitions available for a statement could be extended to a basic block since the basic block is the aggregation of the statements
16 May 2013
ChonuChinnu's
25
Reachable Definitions
(Contd..)
Spawn[S]: The set of definitions generated from the statement S Delete[S]: The set of definitions that are killed as a result of realizing the statement S Input[S]: The set of definitions that are available at the input of the statement S Output[S]: The set of definitions that are available at the output of the statement S Output[S] = Spawn[S] U (Input[S] Delete[S])
16 May 2013
ChonuChinnu's
26
Reachable Definitions
Case 1: Simple Statement
(Contd..)
Different Cases of Flow Diagram
Spawn[S] = r = p op q Delete[S] = {the set of definitions for r} r= p op q Output[S] = Spawn[S] U (Input[S] Delete[S]) Here U is the confluence operator.
Here Spawn[S] is the set of generated definitions in the statement S. Delete[S] is the set of definitions defined earlier to this statement but not the current definition generated in the statement S. Also the definitions available at the output of the statement S is the set of definitions generated in the statement and the set of definitions available at the input of the statement S but that are not destroyed in the statement S
ChonuChinnu's
16 May 2013
27
Reachable Definitions
Case 2: Sequential Statement S1
(Contd..)
Different Cases of Flow Diagram
S2
Spawn[S] = Spawn [S2] U (Spawn [S1]-Destroy [S2]) Delete[S] = Delete[S2] U (Delete[S1]-Spawn[S2] Input[S1] = Input[S] Input[S2] = Output[S1] Output[S] = Output[S2]
16 May 2013
ChonuChinnu's
28
Reachable Definitions
Case 3: Selective Statement S1
(Contd..)
Different Cases of Flow Diagram
S2 Spawn[S] = Spawn[S1] U Spawn[S2] Delete[S] = Delete[S1] Delete[S2] Input[S1] = Input[S] Input[S2] = Input[S] Output[S] = Output [S1] U Output [S2]
16 May 2013
ChonuChinnu's
29
Reachable Definitions
Case 4: Iterative Statement S1
(Contd..)
Different Cases of Flow Diagram
Spawn[S] = Spawn[S1] Delete[S] = Delete[S1] Input[S1] = Input[S] U Spawn[S1] Output[S] = Output[S1]
16 May 2013
ChonuChinnu's
30
Reachable Definitions
(Contd..)
A convenient way to access/use reaching definition information is: Used-Defined Chains (UD chains) Defined-Used Chains (DU chains) Used-Defined chains (UD chains): The list (chain) of definitions reaching at the point of its use. If the definitions are ambiguous, the list is the set of ambiguous definitions and In[B]. If there are unambiguous definitions then the recent definition will be applicable Defined-Used chains (DU chains): For a given definition of a variable, DU chain is the list of uses of the variables from its definitions up to its redefinition
16 May 2013
ChonuChinnu's
31
Computing Definitions Example
Spawn [B1] = {d1, d2, d3} d 1 i = i + 1 d 2 j = j 1 d3 k = t1 Spawn [B2] = {d4, d5} d4 i = i -1 d 5 j = j + 1 B2 B1
Delete [B1] = {d4, d5, d6}
Delete [B2] = {d1, d2}
Spawn [B3] = {d6}
Delete [B3] = {d3}
d6k = t2
B3
16 May 2013
ChonuChinnu's
32
Computing Definitions Iterative Process
At initial Stage For each block B, Input[B] is empty. Output of each block is given by: Output[B1] = Spawn[B1] = {d1, d2, d3} Output[B2] = Spawn[B2] = {d4, d5} Output[B3] = Spawn[B3] = {d6}
16 May 2013
ChonuChinnu's
33
Computing Definitions Iterative Process
At the end of first iteration: Input[B1] ={} Output[B1] = Spawn[B1] U (Input(B1) Delete[B1]) = {d1, d2, d3} U ( { } - {d4, d5, d6} ) = {d1, d2, d3} Input[B2] = Output[B1] U Output[B3] = {d1, d2, d3} U {d6 } = {d1, d2, d3, d6 } Output[B2] = Spawn[B2] U (Input[B2] Delete[B2]) = {d4, d5} U ({d1, d2, d3, d6} - {d1, d2}) = { d3, d4, d5, d6} Input[B3] = Output[B2]
= { d3 , d 4 , d5 , d6 }
Output[B3] = Spawn[B3] U (Input[B3] Delete[B3]) = {d6} U ({ d3, d4, d5, d6} - {d3}) = {d4, d5, d6}
ChonuChinnu's 34
16 May 2013
Computing Definitions Iterative Process
At the end of Second iteration: Input[B1] ={} Output[B1] = Spawn[B1] U (Input(B1) Delete[B1]) = {d1, d2, d3} U ( { } - {d4, d5, d6} ) = {d1, d2, d3} Input[B2] = Output[B1] U Output[B3] = {d1, d2, d3} U {d4, d5, d6 } = {d1, d2, d3, d4, d5, d6} Output[B2] = Spawn[B2] U (Input[B2] Delete[B2]) = {d4, d5} U ({d1, d2, d3, d4, d5, d6} - {d1, d2}) = { d3, d4, d5, d6} Input[B3] = Output[B2] = { d3, d4, d5, d6} Output[B3] = Spawn[B3] U (Input[B3] Delete[B3]) = {d6} U ({ d3, d4, d5, d6} - {d3}) = {d4, d5, d6}
16 May 2013 ChonuChinnu's 35
Live Variables
Input[B] set of live variables at the beginning of the block B Output[B] set of live variables at the end of the block B Defined[B] - set of variables defined in B before they are used Used[B] - set of variables that are used in B before their definition
Equations Input[B] = Used[B] U (Output[B] Defined[B]) Output[B] = U Input[S], where S is the set of blocks following block B
16 May 2013
ChonuChinnu's
36
Live Variables-Algorithm computeLiveVariables( )
//Input: A flow graph with the sets Defined and Used for each block //Output: The set of live variable at each block output { For each block B { Input[B] = { } PrevInput[B] = Input[B] } Do { For each block B { Output[B] = U Input[S] Input[B] = Used[B] U (Output[B] Defined[B]) } } while PrevInput[B] != Input[B] }
16 May 2013
ChonuChinnu's
37
Live Variables: Example
A=B+C P=Q*R Q =10 P = 20 P = B+ C X=Q*R
Here the variables B, C, Q and R are live variables since they are used later in the flow diagram.
16 May 2013
ChonuChinnu's
38
Loops in Flow Graph
Identification of the loop is mandatory in optimization. Loop is a sequence of statements with a beginning and the last statement that has a control statement such that it may go to beginning once again based on some condition.
16 May 2013
ChonuChinnu's
39
Dominator d dom n of Graph G
Every node dominates itself. The initial node dominates all nodes in G. The node at the beginning of a loop dominates all nodes in the loop. Each node may have more than one dominator. However, each node n has a unique immediate dominator m, which is the last dominator of this node n on any path in G from the initial node to n. The Dominator information in a path of a flow graph can be visualized as Dominator tree (TD) so that the root node of TD is the initial node of G and a node d in TD dominates all node in its sub-tree
16 May 2013
ChonuChinnu's
40
Dominator: Example
Dom(0) = {1,2,3,4,5,6} 0 1 2 4 3
Dom(1) = {2,3,4,5,6}
Dom(2) = { } Dom(3) = { }
Dom(4) = {5,6}
Dom(5) = {6} Dom(6) = { }
6
16 May 2013 ChonuChinnu's 41
Detection of Loop
Source T Sink H Source T Sink H
Forward Edge T dom H
Back Edge - H dom T
16 May 2013
ChonuChinnu's
42