UNIT IV -Code optimization (Part A)
Code optimization is used to improve the intermediate code so that the output of the program
could run faster and takes less space. It removes the unnecessary lines of the code and arranges the
sequence of statements in order to speed up the program execution without wasting resources.
It tries to improve the code by making it consume less resources (i.e. CPU, Memory) and deliver high
speed.
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. Many transformations can be performed at both the
local and global levels. Local transformations are usually performed first.
There are a number of ways in which a compiler can improve a program without changing the
function its computes.
Classification of Optimization:
Optimization can be categorized broadly into two types : machine independent and machine
dependent.
Machine-independent Optimization
In this optimization, the compiler takes in the intermediate code and transforms a part of the code
that does not involve any CPU registers and/or absolute memory locations. For example:
do
item = 10;
value = value + item;
} while(value<100);
This code involves repeated assignment of the identifier item, which if we put this way:
Item = 10;
do
value = value + item;
} while(value<100);
should not only save the CPU cycles, but can be used on any processor.
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 memory hierarchy.
Principal sources of code optimization
1. Common-Subexpression Elimination: In the common sub-expression, we don't need to be
computed it over and over again. Instead of this we can compute it once and kept in store from
where it's referenced when encountered again. For e.g.
2. Copy Propagation: Assignments of the form f : = g called copy statements, or copies for short. The
idea behind the copy-propagation transformation is to use g for f, whenever possible after the copy
statement f: = g. Copy propagation means use of one variable instead of another. This may not
appear to be an improvement, but as we shall see it gives us an opportunity to eliminate x. For e.g.
x = Pi;
A=x*r*r;
The optimization using copy propagation can be done as follows: A=Pi*r*r;
Here the variable x is eliminated.
3. Dead Code Elimination: The dead code may be a variable or the result of some expression
computed by the programmer that may not have any further uses. By eliminating these useless
things from a code, the code will get optimized. For e.g.
4. Constant folding: Deducing at compile time that the value of an expression is a constant and using
the constant instead is known as constant folding. The code that can be simplified by user itself, is
simplified. For e.g.
Initial code:
x = 2 * 3;
Optimized code:
x = 6;
5. Loop Optimizations: In loops, especially in the inner loops, programs tend to spend the bulk of
their time. The running time of a program may be improved if the number of instructions in an inner
loop is decreased, even if we increase the amount of code outside that loop. Some loop optimization
techniques are:
i) Frequency Reduction (Code Motion): In frequency reduction, the amount of code in 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. For e.g.
Before optimization: After optimization:
while(i<100) t = Sin(x)/Cos(x);
{ while(i<100)
a = Sin(x)/Cos(x) + i; {
i++; a = t + i;
} i++;
ii) Induction-variable elimination, which we apply to replace variables from inner loop.
iii) Reduction in Strength: The strength of certain operators is higher than other operators. For
example, strength of * is higher than +. Usually, compiler takes more time for higher strength
operators and execution speed is less. Replacement of higher strength operator by lower strength
operator is called a strength reduction technique
Optimization can be done by applying strength reduction technique where higher strength can be
replaced by lower strength operators. For e.g.
Before optimization: After optimization:
for (i=1;i<=10;i++) temp = 0;
{ for(i=1;i<=10;i++)
sum = i * 7; {
printf(“%d”, sum); temp = temp + 7;
} sum = temp;
printf(“%d”, sum)
Basic Blocks
Basic Block is a straight line code sequence that has no branches in and out branches except to the
entry and at the end respectively. Basic Block is a set of statements that always executes one after
other, in a sequence.
The first task is to partition a sequence of three-address code into basic blocks. A new basic block is
begun with the first instruction and instructions are added until a jump or a label is met. In the
absence of a jump, control moves further consecutively from one instruction to another. The idea is
standardized in the algorithm below:
Algorithm:
Partitioning three-address code into basic blocks.
Input: A sequence of three address instructions.
Process: Instructions from intermediate code which are leaders are determined. Following are the
rules used for finding a leader:
1. The first three-address instruction of the intermediate code is a leader.
2. Instructions that are targets of unconditional or conditional jump/goto statements are
leaders.
3. Instructions that immediately follow unconditional or conditional jump/goto statements are
considered leaders.
For each leader thus determined its basic block contains itself and all instructions up to excluding the
next leader.
Example 1:
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 := t4 +t5
A three address statement x:= y+z is said to define x and to use y and z. 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, perhaps in another
basic block.
Example 2:
Intermediate code to set a 10*10 matrix to an identity matrix:
1) i=1 //Leader 1 (First statement)
2) j=1 //Leader 2 (Target of 11th statement)
3) t1 = 10 * i //Leader 3 (Target of 9th statement)
4) t2 = t1 + j
5) t3 = 8 * t2
6) t4 = t3 - 88
7) a[t4] = 0.0
8) j = j + 1
9) if j <= goto (3)
10) i = i + 1 //Leader 4 (Immediately following Conditional goto statement)
11) if i <= 10 goto (2)
12) i = 1 //Leader 5 (Immediately following Conditional goto statement)
13) t5 = i - 1 //Leader 6 (Target of 17th statement)
14) t6 = 88 * t5
15) a[t6] = 1.0
16) i = i + 1
17) if i <= 10 goto (13)
The given algorithm is used to convert a matrix into identity matrix i.e. a matrix with all diagonal
elements 1 and all other elements as 0.
Steps (3)-(6) are used to make elements 0, step (14) is used to make an element 1. These steps are
used recursively by goto statements.
There are 6 Basic Blocks in the above code :
B1) Statement 1
B2) Statement 2
B3) Statement 3-9
B4) Statement 10-11
B5) Statement 12
B6) Statement 13-17
Optimization of Basic Blocks
Optimization is applied to the basic blocks after the intermediate code generation phase of the
compiler. Optimization is the process of transforming a program that improves the code by
consuming fewer resources and delivering high speed. In optimization, high-level codes are replaced
by their equivalent efficient low-level codes. Optimization of basic blocks can be machine-dependent
or machine-independent. These transformations are useful for improving the quality of code that
will be ultimately generated from basic block.
There are two types of basic block optimizations:
1. Structure preserving transformations
2. Algebraic transformations
Structure-Preserving Transformations:
The structure-preserving transformation on basic blocks includes:
1. Dead Code Elimination
2. Common Subexpression Elimination
3. Renaming of Temporary variables
4. Interchange of two independent adjacent statements
[Link] Code Elimination:
Dead code is defined as that part of the code that never executes during the program execution. So,
for optimization, such code or dead code is eliminated. The code which is never executed during the
program (Dead code) takes time so, for optimization and speed, it is eliminated from the code.
Eliminating the dead code increases the speed of the program as the compiler does not have to
translate the dead code.
Example:
// Program with Dead code
int main()
x=2
if (x > 2)
cout << "code"; // Dead code
else
cout << "Optimization";
return 0;
// Optimized Program without dead code
int main()
x = 2;
cout << "Optimization"; // Dead Code Eliminated
return 0;
[Link] Subexpression Elimination:
In this technique, the sub-expression which are common are used frequently are calculated only
once and reused when needed. DAG ( Directed Acyclic Graph ) is used to eliminate common
subexpressions.
Example:
[Link] of Temporary Variables:
Statements containing instances of a temporary variable can be changed to instances of a new
temporary variable without changing the basic block value.
Example: Statement t = a + b can be changed to x = a + b where t is a temporary variable and x is a
new temporary variable without changing the value of the basic block.
[Link] of Two Independent Adjacent Statements:
If a block has two adjacent statements which are independent can be interchanged without affecting
the basic block value.
Example:
t1 = a + b
t2 = c + d
These two independent statements of a block can be interchanged without affecting the value of the
block.
Algebraic Transformation:
Countless algebraic transformations can be used to change the set of expressions computed by a
basic block into an algebraically equivalent set. Some of the algebraic transformation on basic blocks
includes:
1. Constant Folding
2. Copy Propagation
3. Strength Reduction
1. Constant Folding:
Solve the constant terms which are continuous so that compiler does not need to solve this
expression.
Example:
x = 2 * 3 + y ⇒ x = 6 + y (Optimized code)
2. Copy Propagation:
It is of two types, Variable Propagation, and Constant Propagation.
Variable Propagation:
x=y ⇒ z = y + 2 (Optimized code)
z=x+2
Constant Propagation:
x=3 ⇒ z = 3 + a (Optimized code)
z=x+a
3. Strength Reduction:
Replace expensive statement/ instruction with cheaper ones.
x = 2 * y (costly) ⇒ x = y + y (cheaper)
x = 2 * y (costly) ⇒ x = y << 1 (cheaper)
Loop Optimization:
Loop optimization includes the following strategies:
1. Code motion & Frequency Reduction
2. Induction variable elimination
3. Loop merging/combining
4. Loop Unrolling
1. Code Motion & Frequency Reduction
Move loop invariant code outside of the loop.
// Program with loop variant inside loop
int main()
for (i = 0; i < n; i++) {
x = 10;
y = y + i;
return 0;
// Program with loop variant outside loop
int main()
x = 10;
for (i = 0; i < n; i++)
y = y + i;
return 0;
}
2. Induction Variable Elimination:
Eliminate various unnecessary induction variables used in the loop.
// Program with multiple induction variables
int main()
i1 = 0;
i2 = 0;
for (i = 0; i < n; i++) {
A[i1++] = B[i2++];
return 0;
// Program with one induction variable
int main()
for (i = 0; i < n; i++) {
A[i] = B[i]; // Only one induction variable
return 0;
3. Loop Merging/Combining:
If the operations performed can be done in a single loop then, merge or combine the loops.
// Program with multiple loops
int main()
{
for (i = 0; i < n; i++)
A[i] = i + 1;
for (j = 0; j < n; j++)
B[j] = j - 1;
return 0;
// Program with one loop when multiple loops are merged
int main()
for (i = 0; i < n; i++) {
A[i] = i + 1;
B[i] = i - 1;
return 0;
4. Loop Unrolling:
If there exists simple code which can reduce the number of times the loop executes then, the loop
can be replaced with these codes.
// Program with loops
int main()
for (i = 0; i < 3; i++)
cout << "Cd";
return 0;
}
// Program with simple code without loops
int main()
cout << "Cd";
cout << "Cd";
cout << "Cd";
return 0;
Peephole optimization
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: A part of the code which can never be executed, eliminating it will improve
processing time and reduces set of instruction.
G. 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;