System Programming and Compiler
construction (SPCC)
MODULE NO. 6
SYNTHESIS PHASE
TOPIC NAME
CODE OPTIMIZATION
Mrs. Prajakta S. Khelkar
13/04/20
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.
The quality of the object program is generally
measured by its size (for small computation) or its
running time (for large computation).
It is theoretically impassible for a compiler to produce
the best possible object program for every source
program under any reasonable cast function.
The accurate term for “code optimization” is ”code
improvement”.
13/04/20
The Principal Sources Of Optimization
The code optimization techniques consist of detecting
patterns in the program and replacing these patterns by
equivalent but more efficient construct.
Patterns may be local or global and replacement strategy
may be machine dependent or machine dependent.
13/04/20
Optimization can be categorized broadly into two types
Machine Independent Optimization – This code optimization
phase attempts to improve the intermediate code to get a better
target code as the output. The part of the intermediate code which is
transformed here does not involve any CPU registers or absolute
memory locations. do { Item = 10;
item = 10; do
{
value = value + item ; value = value + item ;
} while(value<100); } while(value<100);
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 the
memory hierarchy.
13/04/20
Intermediat Code
Font end Target code
e code generation
Programmer apply transformation in Use register
should use select
loop, procedure appropriate
efficient call, address inst do
algorithm calculator peephole opt
13/04/20
Classification/Techniques of Optimization
1) Local optimization-Apply on Basic Block
2) Global optimization –Apply on across the Basic
Block/Data Flow Block
3) Peep-hole optimization-Apply on across the boundaries
13/04/20
1. Local optimization Technique
Local code optimization performs optimize local to a
function definition. Therefore it is also called Function
preserving transformation. It has following types
1) Compiler time
A) constant folding
B)constant propagation
2) Algebraic simplification /Re-association
3) Operator strength reduction
4) Dead code elimination
5) Copy propagation
13/04/20
1 . Compile Time Evaluation
Shifting of computation from run time to compile time
a) Constant folding
area=(22.0/7.0)*r*r → area=3.14*r*r
a) Constant propagation
pi=3.14
area=pi*r*r → area=3.14*r*r
13/04/20
2) Algebraic simplification /Re-association
Some statement can be deleted while some can be
simplified
Ex: x=x+0
x=x*1
x=x*0
13/04/20
3) Operator strength reduction
Replacement of an operator with less expensive one
multiplication /division operator can be replaced by
addition /shift operator. It usually occurs in address
calculation of array reference
Ex:
r1=r2*2 ---→ r1=r1+r2
r1=r2/2 ---→ r1=r1>>1
13/04/20
4) Dead code elimination
Dead code is a portion of the program which will not be
executed in any path of the program
Dead code elimination :
c=a*b //After elimination :
x=a c=a*b
till till
d=a*b+4 d=a*b+4
13/04/20
5) Copy propagation
It is same as constant propagation but generalized to non
constant value.
before removing
temp2=temp1
temp3=temp2*temp1
After removing
temp3=temp1*temp1
13/04/20
2. Global optimization(Apply on global
box)/Loop Optimization
1. Code motion /code movement
2. Induction variable
3. Loop invariant method
4. Loop unrolling
5. Loop fusion/loop faming
13/04/20
1) Code Motion
✓ There are two basic goals of code movement: To reduce the size of the
code. To reduce the frequency of execution of code
a = 200;
while(a>0)
{
b = x + y;
if (a % b == 0}
printf(“%d”, a);
}
//This code can be further optimized as
a = 200;
b = x + y;
while(a>0)
{
if (a % b == 0}
printf(“%d”, a);
}
13/04/20
2) Induction Variable and 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
i=1
while (i<10)
t=4
{ {
while( t<40)
y = i * 4; y = t;
t = t + 4;
}
}
13/04/20
3)Loop invariant method
Loop invariant optimization can be obtained by moving some
amount of code outside the loop and placing it just before
entering in the loop.
This method is also called code motion.
Example: N=max-1;
While(i<=N)
while(i<=max-1) {
sum=sum+a[i];
{
}
sum=sum+a[i];
}
13/04/20
4)Loop unrolling
In this method number of jumps and test can be reduced by writing the
code two times. loop overhead can be reduced by reducing no. of
iteration and placing no. of code in loop.
int i=1; int i=1;
while(i<=100)
while(i<=100)
{ {
A[i]=b[i]; A[i]=b[i];
i++; i++;
} A[i]=b[i];
i++;
}
13/04/20
5)Loop fusion/loop faming
In loop fusion method several loop are merged
one loop.
Example: for i=1 to n do
for j=1 to m do
A[i,j]=10
Can be written as
for i=1,j=1 to n*m do
13/04/20
3. Peephole optimization
Peephole optimization is a simple and effective technique for locally
improving target code. This technique is applied to improve the
performance of the target program by examining the short sequence of
target instructions and replacing these instructions by shorter or faster
sequence.
Characteristics /Technique of Peephole Optimization
1.Elimination of redundant instruction
2.Removal of unreachable code
3. Flow control optimal
4. Algebraic simplification/strength reduction
5. Use of machine idioms
13/04/20
1.Elimination of redundant instruction
Redundant instruction elimination.
• Especially the redundant loads and stores can be eliminated in this type
of transformations.
• Example :
MOV R0,x MOV
x,R0
• We can eliminate the second instruction since x is already in
R0. But if (MOV x, RO) is a label statement then we cannot
remove it
13/04/20
2.Removal of unreachable code
13/04/20
3. Flow control optimal
13/04/20
4. Algebraic simplification/strength reduction
13/04/20
5. Use of machine idioms
13/04/20
