Code Optimization in Compiler Design

Code optimization is a crucial phase in compiler design aimed at enhancing the performance and
efficiency of the executable code. By improving the quality of the generated machine code
optimizations can reduce execution time, minimize resource usage, and improve overall system
performance. This process involves the various techniques and strategies applied during
compilation to produce more efficient code without altering the program’s functionality.

The code optimization in 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. The 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 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:

 Machine Independent Optimization

 Machine Dependent Optimization

Machine-Independent Optimization
 o Machine independent optimization attempts to improve the intermediate code to get a
better target code. The part of the code which is transformed here does not involve any
absolute memory location or any CPU registers.

o 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.

o 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:

1. c = a * b
2. x = a
3. till
4. d = x * b + 4
After Optimization the code is:

1. c = a * b
2. x = a
3. till
4. d=a*b+4
Here, after variable propagation a*b and x*b identified as common sub expression.

(3) Dead code elimination:

Before elimination the code is:

1. c = a * b
2. x = b
3. till
4. d = a * b + 4
After elimination the code is:
 1. c = a * b
2. till
3. 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.

(4) Code Motion:

o It reduces the evaluation frequency of expression.

o 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 and Strength Reduction:

o Strength reduction is used to replace the high strength operator by the low strength.

o An induction variable is used in loop for the following kind of assignment like i = i +
constant.
Before reduction the code is:

i = 1;
while(i<10)
{
y = i * 4;
}
After Reduction the code is:

i=1
t=4
{
while( t<40)
 y = t;
t = t + 4;
}
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
1.Code 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*/
2.Induction-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.
3.Reduction in Strength
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:
while (i<10)
{
j= 3 * i+1;
a[j]=a[j]-2;
i=i+2;
}

After strength reduction the code will be:

s= 3*i+1;
while (i<10)
{
j=s;
a[j]= a[j]-2;
i=i+2;
s=s+6;
}

In the above code, it is cheaper to compute s=s+6 than j=3 *i

DAG representation for basic blocks

A DAG for basic block is a directed acyclic graph with the following labels on nodes:

1. The leaves of graph are labeled by unique identifier and that identifier can be variable
names or constants.
2. Interior nodes of the graph is labeled by an operator symbol.
3. Nodes are also given a sequence of identifiers for labels to store the computed value.

o DAGs are a type of data structure. It is used to implement transformations on basic

blocks.

o DAG provides a good way to determine the common sub-expression.

o It gives a picture representation of how the value computed by the statement is used in
subsequent statements.

Algorithm for construction of DAG

Input:It contains a basic block

Output: It contains the following information:

o Each node contains a label. For leaves, the label is an identifier.

o Each node contains a list of attached identifiers to hold the computed values.

1. Case (i) x:= y OP z

2. Case (ii) x:= OP y
3. Case (iii) x:= y
Method:

Step 1:

If y operand is undefined then create node(y).

If z operand is undefined then for case(i) create node(z).

Step 2:

For case(i), create node(OP) whose right child is node(z) and left child is node(y).

For case(ii), check whether there is node(OP) with one child node(y).

For case(iii), node n will be node(y).

Output:

For node(x) delete x from the list of identifiers. Append x to attached identifiers list for the node
n found in step 2. Finally set node(x) to n.

Example:

Consider the following three address statement:

1. S1:= 4 * i
2. S2:= a[S1]
3. S3:= 4 * i
4. S4:= b[S3]
5. S5:= s2 * S4
6. S6:= prod + S5
7. Prod:= s6
8. S7:= i+1
9. i := S7
10. if i<= 20 goto (1)

Stages in DAG Construction:

Application of Directed Acyclic Graph

 Directed acyclic graph determines the subexpressions that are commonly used.

 Directed acyclic graph determines the names used within the block as well as the names
computed outside the block.

 Determines which statements in the block may have their computed value outside the
block.

 Code can be represented by a Directed acyclic graph that describes the inputs and outputs
of each of the arithmetic operations performed within the code; this representation allows
the compiler to perform common subexpression elimination efficiently.

 Several programming languages describe value systems that are linked together by a
directed acyclic graph. When one value changes, its successors are recalculated; each
value in the DAG is evaluated as a function of its predecessors.

Unreachable Code Elimination

Unreachable Code is also known as dead code in Compiler Design that points to the portion of a
program that is never executed under any condition or scenario. This dead code doesn’t do any
functionality in the program but unnecessarily occupies the space in the application memory, and
also due to this there are different problems of unnecessary computation, that describe the
program’s performance. So, to avoid this issue in Compiler Design, we can use the technique of
Unreachable Code Elimination. In this Compiler Design article, we will see Unreachable Code
Elimination with its techniques, practical examples, and advantages.

Techniques for Unreachable Code Detection

Below mentioned are the techniques for Unreachable Code Detection.

 Static Analysis Techniques

 Dynamic Analysis Techniques

Static Analysis Techniques

Static Analysis techniques analyze the program’s code or the intermediate outlined
representation of code without actually executing it. Static Analysis helps to properly understand
the control flow and the data flow of the survey program so that it will be easy to detect the
potential Unreachable Code in the program.

 Control Flow Analysis: Control Flow Analysis measures the program’s control flow
graph which traces all possible execution routes. Using the Code Flow Analysis we can
identify the route that is not reached while executing the source program. Conditional
 Statements, Loops, Functional Calls, and branching constructs are taken into
consideration in Control Flow Analysis.

 Data Flow Analysis: Data Flow Analysis traces variable values and their assignments
throughout the program. The main purpose of using the Data Flow analysis is that it helps
us to properly identify the variables that are just declared but not used in the source code.
By analyzing the data dependencies, Data Flow analysis techniques easily detect dead
code and also help to eliminate it from the code.

Dynamic Analysis Techniques

Dynamic Analysis Techniques are used to analyze the execution of the program with user testing
inputs and tracking the test cases. The aim is to observe the behavior during the runtime
execution of the program or source code. Dynamic Analysis Techniques detect the Unreachbele
Code in the source program according to the execution route and Code Coverage data.

 Code Coverage Analysis: Code Code Analysis calculates the extent to which the
program’s code is trained by a given set of test cases. Code Coverage Analysis identifies
the code that is unexecuted in the source program execution. Some of the most used
Common Code Coverage Metrics are Statement Coverage, Branch Coverage, and Path
Coverage.

 Program Profiling: Program Profiling technique consists of collecting runtime data

during program execution. This analysis of the execution tracks identifies the Code
Routes that are never reached for execution. By Profiling the program’s behavior,
Unreachable Code can be easily identified and subsequently eliminated.

Example of Unreachable Code Elimination

Consider the below C++ code snippet as an Example of Unreachable Code Elimination.

Before Optimization

#include <iostream>
void exampleFunction(int x)
{
if (x > 10) {
std::cout <<"x is greater than 10" << std::endl;
}
else {
std::cout <<"x is less than or equal to 10" << std::endl;
return;
std::cout<<"This line is unreachable" << std::endl;
}
}
 int main()
{
exampleFunction(15);
return 0;
}

In the above code, there is a function called the example function that takes an integer x as input.
It checks if x is greater than 10. If it is, it prints ” x is greater than 10 ” to the console. Otherwise,
it prints “x is less than or equal to 10” and has an extra line that will never be executed due to the
return statement before it.

After Optimization

#include <iostream>;
void exampleFunction(int x)
{
if (x > 10) {
std::cout << "x is greater than 10" << std::endl;
}
else {
std::cout << "x is less than or equal to 10"
<< std::endl;
return;
}
}
int main()
{
exampleFunction(15);
return 0;
}

After optimization, the unreachable line of code std::cout << “This line is unreachable” <<
std::endl; is removed. The resulting optimized code still prints the appropriate message based on
the value of x , but it eliminates the unnecessary and unreachable line.

Advantages/Benefits of Unreachable Code Elimination

 Performance Improvement: The compiler reduces pointless computations and

instructions, which improves program performance by removing unreachable code. Dead
code should be removed because it makes the program work less and completes
operations more quickly.

 Reduced Memory Usage: The compiled program uses memory to store unreachable
code. So if we eliminate this unreachable code, then the memory usage is minimized and
 we can use the memory for other computations. In some systems, the memory is limited
for the operations, so unreachable code elimination is more useful for these systems.

 Improved Readability and Maintainability: Removing inaccessible code makes the

codebase easier to read and maintain. The program is simpler to comprehend and modify
because developers can concentrate on pertinent code.

 Optimization of Resource Utilisation: By eliminating unreachable code, less

computation, and memory usage is required, which leads to optimized resource use.
When aiming for devices with low processing power or memory, or in resource-
constrained systems, this optimization is especially beneficial.

Dead Code Elimination

In the world of software development, optimizing program efficiency and maintaining clean
code are crucial goals. Dead code elimination, an essential technique employed by compilers and
interpreters, plays a significant role in achieving these objectives. This article explores the
concept of dead code elimination, its importance in program optimization, and its benefits. We
will delve into the process of identifying and eliminating dead code, emphasizing original
content to ensure a plagiarism-free article.

Understanding Dead Code

Dead code refers to sections of code within a program that is never executed during runtime and
has no impact on the program’s output or behavior. Identifying and removing dead code is
essential for improving program efficiency, reducing complexity, and enhancing maintainability.

Benefits of Dead Code Elimination

 Enhanced Program Efficiency: By removing dead code, unnecessary computations

and memory usage are eliminated, resulting in faster and more efficient program
execution.

 Improved Maintainability: Dead code complicates the understanding and maintenance

of software systems. By eliminating it, developers can focus on relevant code, improving
code readability, and facilitating future updates and bug fixes.

 Reduced Program Size: Dead code elimination significantly reduces the size of
executable files, optimizing resource usage and improving software distribution.

Process of Dead Code Elimination

Dead code elimination is primarily performed by compilers or interpreters during

the compilation or interpretation process. Here’s an overview of the process:
  Static Analysis: The compiler or interpreter analyzes the program’s source code or
intermediate representation using various techniques, including control flow analysis and
data flow analysis.

 Identification of Dead Code: Through static analysis, the compiler identifies sections of
code that are provably unreachable or have no impact on the program’s output.

 Removal of Dead Code: The identified dead code segments are eliminated from the final
generated executable, resulting in a more streamlined and efficient program.

Global data flow analysis

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:

1. 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:

1. a = 1;
2. b = 2;
3. c = 3;
4. if (....) x = a + 5;
5. else x = b + 4;
6. 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:

o Which variables are guaranteed to have constant values

o Which variables will be used before being redefined

Data flow analysis is used to discover this kind of property. The data flow analysis can be
performed on the program's control flow graph (CFG).

The control flow graph of a program is used to determine those parts of a program to which a
particular value assigned to a variable might propagate.

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;
}

Machine Dependent Code Optimization:

In computing, machine dependent refers to features of a program or system that are specific to a
particular hardware platform or operating system, and are not portable across different
hardware or software environments.

Advantages of machine-dependent code:

 Improved performance
 Greater control
 Reduced portability
 Higher maintenance costs
Disadvantages of machine-dependent code:
 Lack of portability
 Increased development and maintenance effort
 Limited flexibility and scalability
 Vulnerability to hardware-specific attacks
 Reduced performance: Machine-dependent

If Simplication , Loop Simplification , Loop Inversion :

These are important code optimization and transformation techniques in compiler design, often
employed during the intermediate code generation or optimization phase to improve
performance and efficiency.
1. If Simplification
  Definition: Simplifies conditional statements (if-else) to reduce complexity and improve
execution efficiency.
 Purpose:
o To reduce the number of conditional branches.
o To enable further optimizations by the compiler.

Example:
Before:
if (a == 0) {
b = 1;
} else {
b = 0;
}
After:
b = (a == 0);
This eliminates the branching entirely by using a direct assignment based on the condition.
2. Loop Simplification
 Definition: A technique to simplify loop structures by ensuring they are easier to analyze
and optimize.
 Purpose:
o Makes loops more amenable to transformations like loop unrolling,
vectorization, or parallelization.
o Helps remove redundant operations inside loops.
 Techniques:
o Hoisting loop-invariant code (moving calculations that don't depend on the loop
variable outside the loop).
o Standardizing loop structure (e.g., ensuring a loop starts at zero and increments
by one).

Example:
Before:
for (i = 1; i <= n; i++) {
x = y + z; // Loop-invariant
a[i] = x * i;
}
After:
x = y + z; // Hoisted outside the loop
for (i = 1; i <= n; i++) {
a[i] = x * i;
}
3. Loop Inversion
 Definition: Converts a while or do-while loop into a for loop or vice versa by changing
the control flow structure to simplify analysis or improve execution efficiency.
 Purpose:
o Avoid unnecessary branching or condition checks.
o Often used to improve pipeline efficiency in CPUs.

Example:
Before (while loop):
while (condition) {
// body
}
After (using a do-while loop):
if (condition) {
do {
// body
} while (condition);
}
In this transformation:
o The initial condition check is replaced by an if, potentially reducing redundant
checks.

Branch Optimization and Prediction in Compiler Design

Branch optimization and prediction are critical aspects of compiler design that aim to improve
the performance of programs by minimizing the impact of branching instructions (e.g., if, else,
switch, loops) on modern processors.
Branch Optimization
Branch optimization focuses on improving the efficiency of branching instructions by
restructuring or eliminating them where possible.
Techniques:
1)Branch Elimination:
o Replace conditional branches with equivalent logic that avoids branching.
Example:
Before:
if (x > 0)
y = x;
else
y = 0;
After:
y = (x > 0) ? x : 0; // Or y = max(x, 0);

2)Loop Unrolling:
o Reduces branching within loops by executing multiple iterations in a single
iteration.

Example:
Before:
for (i = 0; i < 4; i++)
a[i] = b[i] + c[i];
After:
a[0] = b[0] + c[0];
a[1] = b[1] + c[1];
a[2] = b[2] + c[2];
a[3] = b[3] + c[3];

3)Inline Expansion:
o Inline frequently called functions to reduce the overhead of branching due to
function calls.
4)Reordering Instructions:
o Rearrange instructions to make the common case (frequently executed path) fall
through without a branch.
2. Branch Prediction
Branch prediction is a runtime optimization that predicts the outcome of a branch instruction
(e.g., whether a condition will be true or false) to minimize stalls in the processor's execution
pipeline.
Types of Branch Predictors:
1)Static Branch Prediction:
o Predictions are made at compile time.
o Assumes:
 Forward branches are not taken.
 Backward branches (loops) are taken.

o Compiler Role:
 Arrange code layout to match these assumptions and reduce
mispredictions.
2)Dynamic Branch Prediction:
o Predictions are made at runtime based on execution history.
o Modern processors use techniques like:
 1-bit Predictor: Tracks whether the branch was taken or not in the last
execution.
 2-bit Predictor: Requires two consecutive mispredictions before changing
the prediction.
 Branch Target Buffer (BTB): Remembers the target addresses of
previously taken branches.
 Global History Predictors: Use patterns of recent branches to predict the
current branch.