UNIT 4 CODE OPTIMIZATION
THE PRINCIPLE SOURCES OF OPTIMIZATION
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.
In optimization, high-level general programming constructs
are replaced by very efficient low-level programming codes.
A code optimizing process must follow the three rules given
below:
The output code must not, in any way, change the
meaning of the program.
Optimization should increase the speed of the program
and if possible, the program should demand less
number of resources.
Optimization should itself be fast and should not delay
the overall compiling process.
Efforts for an optimized code can be made at various levels
of compiling the process.
At the beginning, users can change/rearrange the code
or use better algorithms to write the code.
After generating intermediate code, the compiler can
modify the intermediate code by address calculations
and improving loops.
While producing the target machine code, the compiler
can make use of memory hierarchy and CPU registers.
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.
Basic Blocks
Source codes generally have a number of instructions, which
are always executed in sequence and are considered as the
basic blocks of the code. These basic blocks do not have any
jump statements among them, i.e., when the first instruction
is executed, all the instructions in the same basic block will
be executed in their sequence of appearance without losing
the flow control of the program.
A program can have various constructs as basic blocks, like
IF-THEN-ELSE, SWITCH-CASE conditional statements and
loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks
in a program:
Search header statements of all the basic blocks from
where a basic block starts:
First statement of a program.
Statements that are target of any branch
(conditional/unconditional).
Statements that follow any branch statement.
Header statements and the statements following them
form a basic block.
A basic block does not include any header statement of
any other basic block.
Basic blocks are important concepts from both code
generation and optimization point of view.
Basic blocks play an important role in identifying variables,
which are being used more than once in a single basic block.
If any variable is being used more than once, the register
memory allocated to that variable need not be emptied
unless the block finishes execution.
Control Flow Graph
Basic blocks in a program can be represented by means of
control flow graphs. A control flow graph depicts how the
program control is being passed among the blocks. It is a
useful tool that helps in optimization by help locating any
unwanted loops in the program.
Loop Optimization
Most programs run as a loop in the system. It becomes
necessary to optimize the loops in order to save CPU cycles
and memory. Loops can be optimized by the following
techniques:
Invariant code : A fragment of code that resides in
the loop and computes the same value at each
iteration is called a loop-invariant code. This code can
be moved out of the loop by saving it to be computed
only once, rather than with each iteration.
Induction analysis : A variable is called an induction
variable if its value is altered within the loop by a loop-
invariant value.
Strength reduction : There are expressions that
consume more CPU cycles, time, and memory. These
expressions should be replaced with cheaper
expressions without compromising the output of
expression. For example, multiplication (x * 2) is
expensive in terms of CPU cycles than (x << 1) and
yields the same result.
Dead-code Elimination
Dead code is one or more than one code statements, which
are:
Either never executed or unreachable,
Or if executed, their output is never used.
Thus, dead code plays no role in any program operation and
therefore it can simply be eliminated.
Partially dead code
There are some code statements whose computed values
are used only under certain circumstances, i.e., sometimes
the values are used and sometimes they are not. Such codes
are known as partially dead-code.
The above control flow graph depicts a chunk of program
where variable ‘a’ is used to assign the output of expression
‘x * y’. Let us assume that the value assigned to ‘a’ is never
used inside the [Link] after the control leaves the
loop, ‘a’ is assigned the value of variable ‘z’, which would be
used later in the program. We conclude here that the
assignment code of ‘a’ is never used anywhere, therefore it
is eligible to be eliminated.
Likewise, the picture above depicts that the conditional
statement is always false, implying that the code, written in
true case, will never be executed, hence it can be removed.
Partial Redundancy
Redundant expressions are computed more than once in
parallel path, without any change in [Link]
partial-redundant expressions are computed more than once
in a path, without any change in operands. For example,
[redundant
expression]
[partially redundant
expression]
Loop-invariant code is partially redundant and can be
eliminated by using a code-motion technique.
Another example of a partially redundant code can be:
If (condition){
a = y OP z;}else{
...}
c = y OP z;
We assume that the values of operands (y and z) are not
changed from assignment of variable a to variable c. Here, if
the condition statement is true, then y OP z is computed
twice, otherwise once. Code motion can be used to eliminate
this redundancy, as shown below:
If (condition){
...
tmp = y OP z;
a = tmp;
...}else{
...
tmp = y OP z;}
c = tmp;
Here, whether the condition is true or false; y OP z should be
computed only once.
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 codes 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.
The 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.
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 <= 10 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
Basic Blocks
Source codes generally have a number of instructions, which
are always executed in sequence and are considered as the
basic blocks of the code. These basic blocks do not have any
jump statements among them, i.e., when the first instruction
is executed, all the instructions in the same basic block will
be executed in their sequence of appearance without losing
the flow control of the program.
A program can have various constructs as basic blocks, like
IF-THEN-ELSE, SWITCH-CASE conditional statements and
loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks
in a program:
Search header statements of all the basic blocks from
where a basic block starts:
First statement of a program.
Statements that are target of any branch
(conditional/unconditional).
Statements that follow any branch statement.
Header statements and the statements following them
form a basic block.
A basic block does not include any header statement of
any other basic block.
Basic blocks are important concepts from both code
generation and optimization point of view.
Basic blocks play an important role in identifying variables,
which are being used more than once in a single basic block.
If any variable is being used more than once, the register
memory allocated to that variable need not be emptied
unless the block finishes execution.
Control Flow Graph
Basic blocks in a program can be represented by means of
control flow graphs. A control flow graph depicts how the
program control is being passed among the blocks. It is a
useful tool that helps in optimization by help locating any
unwanted loops in the program.
Loop Optimization
Most programs run as a loop in the system. It becomes
necessary to optimize the loops in order to save CPU cycles
and memory. Loops can be optimized by the following
techniques:
Invariant code : A fragment of code that resides in
the loop and computes the same value at each
iteration is called a loop-invariant code. This code can
be moved out of the loop by saving it to be computed
only once, rather than with each iteration.
Induction analysis : A variable is called an induction
variable if its value is altered within the loop by a loop-
invariant value.
Strength reduction : There are expressions that
consume more CPU cycles, time, and memory. These
expressions should be replaced with cheaper
expressions without compromising the output of
expression. For example, multiplication (x * 2) is
expensive in terms of CPU cycles than (x << 1) and
yields the same result.
Dead-code Elimination
Dead code is one or more than one code statements, which
are:
Either never executed or unreachable,
Or if executed, their output is never used.
Thus, dead code plays no role in any program operation and
therefore it can simply be eliminated.
Partially dead code
There are some code statements whose computed values
are used only under certain circumstances, i.e., sometimes
the values are used and sometimes they are not. Such codes
are known as partially dead-code.
The above control flow graph depicts a chunk of program
where variable ‘a’ is used to assign the output of expression
‘x * y’. Let us assume that the value assigned to ‘a’ is never
used inside the [Link] after the control leaves the
loop, ‘a’ is assigned the value of variable ‘z’, which would be
used later in the program. We conclude here that the
assignment code of ‘a’ is never used anywhere, therefore it
is eligible to be eliminated.
Likewise, the picture above depicts that the conditional
statement is always false, implying that the code, written in
true case, will never be executed, hence it can be removed.
Partial Redundancy
Redundant expressions are computed more than once in
parallel path, without any change in [Link]
partial-redundant expressions are computed more than once
in a path, without any change in operands. For example,
[partially redundant
[redundant expression]
expression]
Loop-invariant code is partially redundant and can be
eliminated by using a code-motion technique.
Another example of a partially redundant code can be:
If (condition){
a = y OP z;}else{
...}
c = y OP z;
We assume that the values of operands (y and z) are not
changed from assignment of variable a to variable c. Here, if
the condition statement is true, then y OP z is computed
twice, otherwise once. Code motion can be used to eliminate
this redundancy, as shown below:
If (condition){
...
tmp = y OP z;
a = tmp;
...}else{
...
tmp = y OP z;}
c = tmp;
Here, whether the condition is true or false; y OP z should be
computed only once.
Structure preventing transformations
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;
}
Flow graphs
Flow graph is a directed graph. It contains the flow of control information for the set of
basic block.
A control flow graph is used to depict that how the program control is being parsed
among the blocks. It is useful in the loop optimization.
Flow graph for the vector dot product is given as follows:
ADVERTISEMENT
ADVERTISEMENT
o Block B1 is the initial node. Block B2 immediately follows B1, so from B2 to B1
there is an edge.
o The target of jump from last statement of B1 is the first statement B2, so from
B1 to B2 there is an edge.
o B2 is a successor of B1 and B1 is the predecessor of B2.
Loop optimization
Loop optimization is most valuable machine-independent optimization because
program's inner loop takes bulk to time of a programmer.
If we decrease the number of instructions in an inner loop then the running time of a
program may be improved even if we increase the amount of code outside that loop.
For loop optimization the following three techniques are important:
1. Code motion
2. Induction-variable elimination
3. Strength reduction
[Link] Motion:
Code motion is used to decrease the amount of code in loop. This transformation
takes a statement or expression which can be moved outside the loop body without
affecting the semantics of the program.
For example
In the while statement, the limit-2 equation is a loop invariant equation.
1. while (i<=limit-2) /*statement does not change limit*/
2. After code motion the result is as follows:
3. a= limit-2;
4. while(i<=a) /*statement does not change limit or a*/
[Link]-Variable Elimination
Induction variable elimination is used to replace variable from inner loop.
It can reduce the number of additions in a loop. It improves both code space and run
time performance.
In this figure, we can replace the assignment t4:=4*j by t4:=t4-4. The only problem
which will be arose that t4 does not have a value when we enter block B2 for the first
time. So we place a relation t4=4*j on entry to the block B2.
[Link] in Strength
ADVERTISEMENT
ADVERTISEMENT
o Strength reduction is used to replace the expensive operation by the cheaper
once on the target machine.
o Addition of a constant is cheaper than a multiplication. So we can replace
multiplication with an addition within the loop.
o Multiplication is cheaper than exponentiation. So we can replace
exponentiation with multiplication within the loop.
Example:
1. while (i<10)
2. {
3. j= 3 * i+1;
4. a[j]=a[j]-2;
5. i=i+2;
6. }
After strength reduction the code will be:
1. s= 3*i+1;
2. while (i<10)
3. {
4. j=s;
5. a[j]= a[j]-2;
6. i=i+2;
7. s=s+6;
8. }
In the above code, it is cheaper to compute s=s+6 than j=3 *i
DATA FLOW ANALASIS
o To efficiently optimize the code compiler collects all the
information about the program and distribute this information to
each block of the flow graph. This process is known as data-flow
graph analysis.
o Certain optimization can only be achieved by examining the
entire program. It can't be achieve by examining just a portion of
the program.
o For this kind of optimization user defined chaining is one
particular problem.
o Here using the value of the variable, we try to find out that which
definition of a variable is applicable in a statement.
Based on the local information a compiler can perform some
optimizations. For example, consider the following code:
x = a + b;
2. x=6*3
o In this code, the first assignment of x is useless. The value
computer for x is never used in the program.
o At compile time the expression 6*3 will be computed, simplifying
the second assignment statement to x = 18;
Some optimization needs more global information. For example, consider
the following code:
a = 1;
b = 2;
c = 3;
if (....) x = a + 5;
else x = b + 4;
c = x + 1;
In this code, at line 3 the initial assignment is useless and x +1
expression can be simplified as 7.
But it is less obvious that how a compiler can discover these facts by
looking only at one or two consecutive statements. A more global
analysis is required so that the compiler knows the following things at
each point in the program:
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:- 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;
}