Code Optimization
The code optimization is the synthesis phase is a program transformation technique, which tries to
improve the intermediate code by making it consume fewer resources (i.e. CPU, Memory) so that
faster-running machine code will result. Compiler optimizing process should meet the following
objectives :
• The optimization must be correct, it must not, in any way, change the meaning of the
program.
• Optimization should increase the speed and performance of the program.
• The compilation time must be kept reasonable.
• The optimization process should not delay the overall compiling process.
When to Optimize?
Optimization of the code is often performed at the end of the development stage since it reduces
readability and adds code that is used to increase the performance.
Why Optimize?
Optimizing an algorithm is beyond the scope of the code optimization phase. So the program is
optimized. And it may involve reducing the size of the code. So, optimization helps to:
• Reduce the space consumed and increases the speed of compilation.
• Manually analyzing datasets involves a lot of time. Hence, we make use of software like
Tableau for data analysis. Similarly, manually performing the optimization is also tedious
and is better done using a code optimizer.
• An optimized code often promotes re-usability.
Types of Code Optimization: The optimization process can be broadly classified into two types:
1. 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. The process of intermediate code generation introduces much inefficiency like:
using variable instead of constants, extra copies of variable, repeated evaluation of
expression. Through the code optimization, you can remove such efficiencies and improves
code.
• It can change the structure of program sometimes of beyond recognition like: unrolls loops,
inline functions, eliminates some variables that are programmer defined.
• Code Optimization can perform in the following different ways:
(1) Compile Time Evaluation:
(a) z = 5*(45.0/5.0)*r
Perform 5*(45.0/5.0)*r at compile time.
(b) x = 5.7
y = x/3.6
Evaluate x/3.6 as 5.7/3.6 at compile time.
(2) Variable Propagation:
Before Optimization the code is:
c=a*b
x=a
till
Here, after variable propagation a*b
d=x*b+4 and x*b identified as common sub
After Optimization the code is: expression.
c=a*b
x=a
till
d = a* b + 4
(3) Dead code elimination or Unreachable Code Elimination:
• Copy propagation often leads to making assignment statements into dead code.
• A variable is said to be dead if it is never used after its last definition.
• In order to find the dead variables, a data flow analysis should be done.
Before elimination the code is: c = a * b
x=b
till
d=a*b+4
After elimination the code is: c = a * b
till
d=a*b+4
Here, x= b is a dead state because it will never subsequently used in the program. So,
we can eliminate this state.
Example-2 (Unreachable code Elimination)
• After constant propagation and constant folding, the unreachable branches can be
eliminated.
• First, Control Flow Graph should be constructed.
• The block which does not have an incoming edge is an Unreachable code block.
#include <iostream>
using namespace std;
int main() {
int num;
num=10;
cout << "GFG!";
return 0;
cout << num; //unreachable code
}
//after elimination of unreachable code
int main() {
int num;
num=10;
cout << "GFG!";
return 0;
}
(4) Code Motion (Frequency Reduction):
In frequency reduction, the amount of code in the loop is decreased. A statement or
expression, which can be moved outside the loop body without affecting the semantics of the
program, is moved outside the loop.
• It reduces the evaluation frequency of expression.
• It brings loop invariant statements out of the loop.
do
{
item = 10;
valuevalue = value + item;
} while(value<100);
//This code can be further optimized as
item = 10;
do
{
valuevalue = value + item;
} while(value<100);
(5). Induction Variable Elimination
If the value of any variable in any loop gets changed every time, then such a variable is known as an
induction variable. With each iteration, its value either gets incremented or decremented by some
constant value.
[An induction variable is used in the loop for the following kind of assignment i = i + constant.
It is a kind of Loop Optimization Technique. Strength reduction means replacing the high
strength operator with a low strength.]
Example:
Before optimization:
B1
i:= i+1
x:= 3*i
y:= a[x]
if y< 15, goto B2
In the above example, i and x are locked, if i is incremented by 1 then x is incremented by 3.
So, i and x are induction variables.
After optimization:
B1
i:= i+1
x:= x+4
y:= a[x]
if y< 15, goto B2
(6). Strength Reduction
Strength reduction deals with replacing expensive operations with cheaper ones like multiplication
is costlier than addition, so multiplication can be replaced by addition in the loop.
Example:
Before optimization:
while (x<10)
{
y := 3 * x+1;
a[y] := a[y]-2;
x := x+2;
}
After optimization:
t= 3 * x+1;
while (x<10)
{
y=t;
a[y]= a[y]-2;
x=x+2;
t=t+6;
}
(7). Loop Invariant Method
In the loop invariant method, the expression with computation is avoided inside the loop. That
computation is performed outside the loop as computing the same expression each time was
overhead to the system, and this reduces computation overhead and hence optimizes the code.
Example: Before optimization:
for (int i=0; i<10;i++)
t= i+(x/y);
...
end;
After optimization:
s = x/y;
for (int i=0; i<10;i++)
t= i+ s;
...
end;
8. Loop Unrolling
Loop unrolling is a loop transformation technique that helps to optimize the execution time of a
program. We basically remove or reduce iterations. Loop unrolling increases the program’s speed
by eliminating loop control instruction and loop test instructions.
Example:
Before optimization:
for (int i=0; i<5; i++)
printf("Pankaj\n");
After optimization:
printf("Pankaj\n");
printf("Pankaj\n");
printf("Pankaj\n");
printf("Pankaj\n");
printf("Pankaj\n");
9. Loop Jamming
Loop jamming is combining two or more loops in a single loop. It reduces the time taken to compile
the many loops.
Example: Before optimization:
for(int i=0; i<5; i++)
a = i + 5;
for(int i=0; i<5; i++)
b = i + 10;
After optimization:
for(int i=0; i<5; i++)
{
a = i + 5;
b = i + 10;
}
3. Constant Propagation:
If the value of a variable is a constant, then replace the variable with the constant. The variable
may not always be a constant.
(i) A = 2*(22.0/7.0)*r
Performs 2*(22.0/7.0)*r at compile time.
(ii) x = 12.4
y = x/2.3
Evaluates x/2.3 as 12.4/2.3 at compile time.
(iii) int k=2;
if(k) go to L3;
It is evaluated as :
go to L3 ( Because k = 2 which implies condition is always true)
4. Constant Folding:
• Consider an expression : a = b op c and the values b and c are constants, then the value of a
can be computed at compile time.
#define k 5
x=2*k
y=k+5
This can be computed at compile time and the values of x and y are :
x = 10
y = 10
Note: Difference between Constant Propagation and Constant Folding:
• In Constant Propagation, the variable is substituted with its assigned constant where as in
Constant Folding, the variables whose values can be computed at compile time are
considered and computed.
5. Copy Propagation:
• It is extension of constant propagation.
• After a is assigned to x, use a to replace x till a is assigned again to another variable or value
or expression.
• It helps in reducing the compile time as it reduces copying.
//Before Optimization
c=a*b
x=a
till
d=x*b+4
//After Optimization
d=a*b+4
6. Dead Code Elimination :
Dead code is a program snippet that is never executed or never reached in a program. It is a code
that can be efficiently removed from the program without affecting any other part of the program. In
case, a value is obtained and never used in the future, it is also regarded as dead code. Consider the
below dead code:
int x= a+23; //the variable x is never used
//in the program. Thus it is a dead
code.
z=a+y;
printf("%d,%d".z,y);
//After Optimization
z=a+y;
printf("%d,%d".z,y);
Another example of dead code is assign a value to a variable and changing that value just before
using it. The previous value assignment statement is dead code. Such dead code needs to be deleted
in order to achieve optimization.
2. 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 utilise absolute rather than relative memory addresses. Machine-
dependent optimizers put efforts to take maximum advantage of the memory hierarchy.
Peephole Optimization in Compiler Design
Peephole optimization is a type of code Optimization performed on a small part of the code. It is
performed on a very small set of instructions in a segment of code.
The small set of instructions or small part of code on which peephole optimization is
performed is known as peephole or window.
It basically works on the theory of replacement in which a part of code is replaced by shorter and
faster code without a change in output. The peephole is machine-dependent optimization.
Objectives of Peephole Optimization:
The objective of peephole optimization is as follows:
1. To improve performance
2. To reduce memory footprint
3. To reduce code size
Peephole Optimization Techniques
A. Redundant load and store elimination: In this technique, redundancy is eliminated.
Initial code:
y = x + 5;
i = y;
z = i;
w = z * 3;
Optimized code:
y = x + 5;
w = y * 3; //* there is no i now
//* We've removed two redundant variables i & z whose value were
just being copied from one another.
B. Constant folding: The code that can be simplified by the user itself, is simplified. Here
simplification to be done at runtime are replaced with simplified code to avoid additional
computation.
Initial code:
x = 2 * 3;
Optimized code:
x = 6;
C. Strength Reduction: The operators that consume higher execution time are replaced by the
operators consuming less execution time.
Initial code:
y = x * 2;
Optimized code:
y = x + x; or y = x << 1;
Initial code:
y = x / 2;
Optimized code:
y = x >> 1;
D. Null sequences/ Simplify Algebraic Expressions : Useless operations are deleted.
a := a + 0;
a := a * 1;
a := a/1;
a := a - 0;
E. Combine operations: Several operations are replaced by a single equivalent operation.
F. Deadcode Elimination:- Dead code refers to portions of the program that are never executed or
do not affect the program’s observable behavior. Eliminating dead code helps improve the
efficiency and performance of the compiled program by reducing unnecessary computations and
memory usage.
Initial Code:-
int Dead(void)
{
int a=10;
int z=50;
int c;
c=z*5;
printf(c);
a=20;
a=a*10; //No need of These Two Lines
return 0;
}
Optimized Code:-
int Dead(void)
{
int a=10;
int z=50;
int c;
c=z*5;
printf(c);
return 0;
}