Code optimization

techniques
 CODE OPTIMISATION

Different Types of Optimization

Optimization is classified broadly into two types:

● Machine-Independent
● Machine-Dependent
 Machine-Independent Optimization
● It positively affects the efficiency of intermediate code by transforming a part of code not including
hardware.
● It usually optimises code by eliminating tediums and removing unneeded code.

Code before optimization:

do
{
item = 10;
amount= amount + item;
} while(amount<100);

Code after optimization:

item = 10;
do
{
amount= amount + item;
} while(amount<100
 Machine-Independent Optimization Techniques
1. Compile Time Evaluation
2. Common Subexpression Elimination
3. Variable Propagation
4. Dead Code Elimination
5. Code Movement
6. Strength Reduction
7. Redundant load and store elimination
8. Null sequence deletion
9. Loop unrolling
 Compile Time Evaluation
Two techniques that falls under compile time evaluation are-
A) Constant Folding
● Constant folding is an optimization technique in programming languages
where the compiler evaluates constant expressions at compile time,
rather than at runtime.
● This optimization helps to reduce the amount of work required during
execution by precomputing values that are constant.
Constant folding example
int main() {
int a = 5;
int b = 10; Code after Constant Folding:
int c = a + b;
int d = c * 2; int main() {
return d; int c = 15; // 5 + 10
}
int d = 30; // 15 * 2
return 30;
In this example: }
● The expressions a + b and c * 2
only involve constant values.
● Instead of calculating a + b and c *
2 at runtime, the compiler will
evaluate them at compile time.
 Compile Time Evaluation

B) Constant Propagation-

● If some variable has been assigned some constant value, then it replaces that variable with its
constant value in the further program during compilation.
● The condition is that the value of variable must not get alter in between.

pi = 3.14
● This technique substitutes the value of variables
radius = 10 ‘pi’ and ‘radius’ at compile time.
● It then evaluates the expression 3.14 x 10 x 10.
Area of circle = pi x radius x radius ● The expression is then replaced with its result 314.
● This saves the time at run time.
 Common Subexpression Elimination

● Common Subexpression Elimination (CSE) is an optimization technique used by compilers to

identify and eliminate duplicate expressions that are computed multiple times.
● If the same expression appears more than once and produces the same result, CSE
replaces it with a single computation, storing the result in a temporary variable.
● This reduces redundant calculations, potentially saving time and improving runtime efficiency.

AFTER:
BEFORE:
int main() {
int main() { int a = 5;
int a = 5; int b = 10;
int b = 10; int temp = a + b; // common sub-
int c = (a + b) * 2; expression
int d = (a + b) * 3; int c = temp * 2;
return c + d; int d = temp * 3;
} return c + d;
}
 Code Movement
● Code movement, also known as loop-invariant code motion or hoisting, is an optimization
technique used by compilers to improve efficiency by relocating pieces of code that do not
need to be executed multiple times.
● Specifically, this technique identifies computations within a loop that yield the same result on
each iteration and moves them outside the loop, reducing redundant calculations and
saving runtime.

Before Optimization After Optimization

for ( int j = 0 ; j < n ; j ++) x=y+z;

{ for ( int j = 0 ; j < n ; j ++)

x=y+z; {

a[j] = 6 x j; a[j] = 6 x j;

} }
 Dead Code Elimination
● Dead Code Elimination (DCE) is an optimization technique where the compiler removes code that
does not affect the program's outcome.
● This includes code that is never executed (unreachable code) and code that computes values
which are never used (useless code).
● By eliminating such dead code, the compiler reduces the size of the program and can also improve
its execution speed.

Before Optimization After Optimization

int main() { int main() {
int a = 5; int a = 5;
int b = 10; int b = 10;
return a + b; return a + b;
int c = a * b; // Dead code: }
unreachable after 'return'
}
 Strength Reduction
Strength reduction is an optimization technique where expensive operations (such as multiplication or
division) are replaced with equivalent but less costly operations (such as addition, subtraction, or
bit-shifting).
This optimization helps to improve performance by substituting complex calculations with simpler ones that
the CPU can execute more quickly.

Before Optimization After Optimization

int main() { int main() {

int x = 5; int x = 5;
int y = x * 8; int y = x << 3; // Strength
return y; reduction: replace multiplication
} with a shift
return y;
}
Example of useless code:

Before Optimization
After Optimization
int main() {
int main() {
int a = 5;
int a = 5;
int b = 10;
int b = 10;
int c = a + b;
int c = a + b;
int d = 20; // Dead code: 'd' is not
return c;
used
}
return c;
}
 Redundant load and store elimination
● If a value that has been loaded from memory is not modified afterward and is loaded
again, the second load is redundant.
● The compiler can replace the second load with a simple register reference to the
previously loaded value.
● Similarly If a variable is stored to memory but that stored value is never read (or is
overwritten before being read), the store operation is redundant.
● The compiler can safely eliminate such stores.

Before Optimization After Optimization

int x = arr[1]; // Load from arr[1] int x = arr[1]; // Load from arr[1]
x = x + 10; // Modify x x = x + 10; // Modify x
arr[1] = x; // Store back to arr[1] int y = x; // Reuse x directly
int y = arr[1]; // Load again from instead of reloading arr[1]
arr[1]
cont'd
a= b+c
d= a+e

Before Optimization
After Optimization
MOV b, R0;
ADD c, R0; MOV b, R0 ;
MOV R0, a; ADD c, R0 ;
MOV a, R0; MOV R0, a ;
ADD e, R0 ; ADD e, R0 ;
MOV R0, d; MOV R0, d;
 Null sequences deletion

● Useless operations are deleted.

x := x + 0; // Adding 0 does not

change x
x := x * 1; // Multiplying by 1 does
not change x
x := x / 1; // Dividing by 1 does not
change x
x := x - 0; // Subtracting 0 does
not change x
 Loop Unrolling
● Loop unrolling is a code optimization technique that involves expanding the loop body by
repeating its instructions multiple times within the same loop iteration.
● This reduces the overhead of loop control instructions (such as incrementing the loop counter
and checking the termination condition) and increases the loop's throughput by executing more
operations per iteration.
● Particularly in cases where the loop has a small, fixed number of iterations or when the loop
body contains computationally intensive tasks.

Before Optimization Unrolling by factor 2: Full Unrolling:

for (int i = 0; i < 4; i++) { for (int i = 0; i < 4; i += 2) { arr[0] = arr[0] * 2;

arr[i] = arr[i] * 2; arr[i] = arr[i] * 2; arr[1] = arr[1] * 2;
} arr[i+1] = arr[i+1] * 2; arr[2] = arr[2] * 2;
} arr[3] = arr[3] * 2;