Introduction
Machine-independent optimization's major goal is to improve the generated intermediate code so that the compiler can generate better target code.
Code improvement or code optimization is the process of removing unneeded code from object code or substituting one piece of code with another to make the object code faster without changing the output of the object code.
Function Preserving Optimization
Function Preserving Optimization (FPO) is a technique in compiler design that aims to transform a program while preserving its functionality. The goal is to improve the program's performance without altering its behavior.
FPO achieves this by applying optimizations that do not change the output produced by the program. These optimizations can involve transformations like constant folding, loop unrolling, and common subexpression elimination. By applying FPO, compilers can generate more efficient code that executes faster and uses fewer resources.
The methods for achieving it can be followed -
- Common Subexpressions
- Copy Propagations
- Dead Code Elimination
- Folding
1. Common Subexpressions
A common subexpression is one that has been computed and does not change after the last computation but is frequently repeated throughout the program. Even if the value does not change, the compiler assesses it. This kind of review wastes both resources and time. As a result, it should be removed. Consider the following scenario:
Before Optimization
s1 = a + b ;
s2 = s1 % k ;
s3 = a + b ;
s4 = s1 % k ;
Here in the above code s1 and s3 are similar and s2 and s4 are similar. Hence on repetition, it must be eliminated. Now the optimized code is as follows
s1 = a + b ;
s2 = s1 % k ;
2. Copy Propagations
In circumstances where assignments of the form a=b are used, Copy Propagation proposes using one variable instead of the other. Copy statements are used in these assignments. Instead of assigning b to a, we can use it wherever it is needed. In a nutshell, Copy Propagation is the process of removing duplicates from a program.
For example,
a = c ;
d = a + b;
In the above code assigning c to a does not make any useful sense hence we can replace a to c.
d = c + b;
3. Dead Code Elimination
When a program snippet is never used in a program it is removed from the program without affecting the remaining program. This type of elimination is referred to as the dead code Elimination.
Before Optimization
int b = 24;
int c = b - 17;
int a = b;
printf(“%d”,b);
In the above code the integers c and a are never used hence they should be eliminated using the dead code elimination. The optimized code is as follows.
int b = 24;
printf(“%d”,b);
Also See, Top Down Parsing
Code Motion
In this mode of optimization of code, the statements that remain the same for every iteration and are included in the loop make the code slow as they run every time an iteration takes place. These types of statements can be excluded from the loop and written outside the loop which reduces the time spent in the loop. To understand these let's take a look at an example.
for(i = 0; i < (q + p); i++){
a = 15;
printf(“%d\n”,i);
}
In the above code the statement (a = 15) and the condition (i<(q+p)) runs each time loop runs and remains same every time hence it can be excluded to optimise the time of the loop.
a = 15;
t = q + p
for (i = 0; i < t ; i++){
printf(“%d\n”,i);
}
4. Folding
Folding, in the context of FPO (Function-Preserving Optimization), refers to a technique that simplifies constant expressions within a program without altering its functionality. This optimization reduces redundant calculations and improves program efficiency.
Here's how folding works:
Identifying Constant Expressions: The compiler identifies expressions that always evaluate to the same value, regardless of the program's input. These expressions typically involve constants, variables with assigned values, and basic arithmetic operations.
Simplification: The compiler replaces the identified constant expression with its pre-calculated result. This eliminates the need to re-evaluate the expression during program execution.
Example:
Consider the following code snippet:
int result = 2 * 5 + 3;
result = result + 1;
// After folding:
int result = 13; // (2 * 5 + 3) is pre-calculated and stored in result directly.
In this example, the expression 2 * 5 + 3 always evaluates to 13. Folding replaces this expression with its result (13) in both occurrences. This eliminates two redundant calculations and simplifies the code. Folding can be applied to various constant expressions, including:
- Simple arithmetic operations (addition, subtraction, multiplication, division)
- Boolean expressions (true or false)
- Comparisons (equal to, greater than, less than)
By applying folding and other FPO techniques, compilers can generate more efficient code that executes faster and reduces processing time.