Code Optimization Techniques in Compiler Construction by Kindson Munonye

Code Optimization Techniques in Compilers
We would discuss various code optimization techniques which includes the following:

1. Dead Code Elimination
2. Constant Folding
3. Copy Propagation
4. Strength Reduction
5. Common Sub-Expression Elimination
6. Code Motion
7. Inlining

1. Dead Code Elimination
Eliminates code that cannot be reached or where the results are not subsequently used.

For example, consider the following unoptimized code fragment:

After applying dead code elimination we have the optimized code below:

2. Constant Folding
This refers to the technique of evaluating ate compile time, expressions whose operands are known to be constant.
It involves the determining that all of the operands in an expression are constant values, performing the evaluation of the expression at compile time and then replacing the expression by its value.

For example, the expression
12 + 4 * 3
can be replaced by its result of 24 at compile time and omit the code as if the input contained the results rather than the original expression

3. Constant Propagation
In constant propagation, if a variable is assigned a constant value, then subsequent use of that variable can be replaced by a constant as long as no intervening assignment has changed the value of the variable.

For Example, consider the code:
int x = 12;
int y = 7 – x /2;
return y * (24 / x + 2)

Applying constant propagation to x, we have:
int x = 12;
int y = 7 – 12 / 2;
return y * (24 / 12 + 2);

Applying constant folding , we have:
int x = 12;
int y = 1;
return y * 4;

4. Strength Reduction
This is also called operator strength reduction. It is the replacement of expressions that are expensive with cheaper and simple ones.
For example an add instruction can be used to replace a multiply instruction.

The code:
T2 = T2 * 2
Can be replaced with:
T2 = T2 + T2

5. Common Sub Expression Elimination
This is a code optimization technique that scans the code to find identical expressions and replaces redundant expression each time it is encountered.
For example, consider the following fragment:
a = b * c + g;
d = b * c * e;
Here we see that the sub-expression b * c repeats, so we can transform the code to:
t = b * c;
a = t + g;
d = t + e;
6. Code Motion
Also called loop-invariant code motion has to do with moving a block of code outside a loop if it wont have any difference if it is executed outside or inside the loop.
Consider the example:
for (int i = 0; i < n; i++) {
x = y + z;
a[i] = 6 * i;
}
In the code fragment, the expression x = y + z has no effect inside the loop and can safely be moved outside of the loop.
The resulting code would be:
x = y + z;
for (int i = 0; i < n; i++) {
a[i] = 6 * i;
}

7. Inlining
This is also referred to as function inlining or inline expansion, is a technique of replacing a function call with the actual body of the function.
This technique eliminates the overhead associated with expanding the body of the function inline.

Consider the code fragment below:
int add ( int x, int y)
{
z = x + y;
return z;
}
int sub (int x, int y) {
return add(x, -y)
}
We can expand the second function without calling the add function, so we have:

int sub (int x, int y) {
return x + -y;
}
This is also referred to as function inlining or inline expansion. It is a technique of replacing a function call with the actual body of the function.
This technique eliminates the overhead associated with expanding the body of the function inline.

Consider the fragment:
int add ( int x, int y)
{
z = x + y;
return z;
}
int sub (int x, int y) {
return add(x, -y)
}
We can expand the second function without calling the add function, so we have:
int sub (int x, int y) {
return x + -y;
}

Example
Lets apply these code optimization technique we discussed to the unoptimized code fragment below

Resulting Optimization Code
After applying the various optimization technniques discussed, the resulting optimized code is shown below.

If you find this article helpful, you can leave a comment. You can also view the video explanation on the link below:

Code Optimization Techniques by Kindson The Tech Pro