Module 4b: Code Optimization
Optimization
Need for optimizers
• Some compilers either allow the optimizer to be turned off, or
require that optimization be requested explicitly.
• Reason for turning optimization off:
– Compilation may be faster
– If the optimizer produces error , the error can be avoided
• But, a slightly longer compilation time is almost always
compensated by the faster execution.
Types of Optimization
• Array Bounds Optimization
• Bitfield Optimization • Invarrant Expression Elimination
• Branch Elimination Loop • Block Mergin
• Collapsing Instruction Combining • Integer Mod Optimization
• Common Sub-expression Elimination • Integer Multiply Optimization
• Constant Folding • Narrowing
• Constant Propagation • Pointer Optimization
• Copy Propagation • Printf Optimization
• CSE Elimination • Value Range Optimization
• Dead Code Elimination • Register Allocation
• Integer Divide Optimization • Strength Reduction
• Expression Simplification • String Optimization
• Forward Store • Tail Recursion
• Loop Fusion • Try/Catch Block Optimization
• Garbage Collection • Loop Unrolling
• Hoisting • Un-switching
• If Optimization • Volatile Optimization
• Function Inlining • Cross Jump
Code Movement Optimization
• Move code outside the loop since there are
potential many iterations
• Look for expressions that yield the same result
independent of the iterations.
before after
t = limit – 2
While ( I <= limit – 2) While ( I <= t)
Constant folding
• The idea behind constant folding is simple but successful.
• Whenever there is a sub-expression that only involves constant operands
then we pre-compute the result of the arithmetic operation during
compilation and just use the result.
• That is, whenever we find a sub-expression n1(.)n2 for concrete number
constants n1 and n2 and some operator (.), we compute the numerical
result n of the expression n1(.) n2 and use n instead.
int f (void) int f (void)
{ {
return 3 + 5; return 8;
} }
Constant folding is a relatively easy optimization.
Common Sub-expression Elimination (CSE)
• An expression is a Common Sub-expression (CSE) if the
expression was previously computed and the values of the
operands have not changed since the previous computation.
• Recomputing the expression can be eliminated by using the
value of the previous computation.
i = x + y + 1; t1 = x + y;
j = x + y; i = t1 + 1;
j = t1;
Some compilers perform CSE Elimination within an expression and within
a basic block, while more sophisticated compilers can perform CSE
Elimination across basic blocks.
Constant propagation
• Constants assigned to a variable can be propagated through
the flow graph and substituted at the use of the variable.
x = 3; x = 3;
y = x + 4; y = 7;
* Goto CP slide
Variable Propagation
• Variable Propagation propagates values of copies like x = y to
all dominated occurrences of x.
• That is we just substitute x = y into all dominated occurrences
of x.
Dead Code Elimination
• Code that is unreachable or that does not affect the program
(e.g. dead stores) can be eliminated.
int global;
void f () int global;
{ void f ()
int i; /* dead code */ {
i = 1; /* dead code */ global = 2;
global = 1; /* dead code */ return;
global = 2; }
return;
global = 3; /* unreachable */
}
Strength Reduction
• An induction variable is used in loop for the following kind of
assignment i = i + constant.
• Strength reduction means replacing the high strength operator
by the low strength
i = 1; //After Reduction
while (i<10) t=4
{
{ while( t<40)
y = i * 4; y = t;
i++ Print(y)
} t = t + 4;
}
End