Machine-Independent Optimizations in Compiler Design
Machine-Independent Optimizations
The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code.
Eliminating unwanted code from the object code or replacing one set of code with another set of code, which makes the object code faster without changing the result of object code, is generally called code improvement or code optimization.
A high-level language can have run-time overhead. Writing a program in a high-level language can cause redundancy. Code optimization will allow us to remove these inefficiencies.
Optimized code will use less space and makes the program execution fast. The optimized code can be re-used.
Code optimization can be performed in the following ways:
Compile Time Evaluation
- a = 4*(19/0.5)*r
Perform 4*(19/0.5)*r at compile time
2) a = 5
b = a/6
Perform a/6 as 5/6 at compile time
Global Common Subexpressions
Any expression can be known as a common subexpression if the value of an expression is previously computed. And the value of the variable in expression has not changed since the previous computation.
Example
p = x * y
q = x
r = q * y + 9
After the optimization of code:
p = x * y
q = x
r = x * y + 9
Here, after variable propagation, x * y and q * y identified as common sub-expression.
Dead-Code Elimination
If any variable's value can be used anywhere in the program, then the variable will be called live at a point in a program; otherwise, it will be termed as dead code. A dead code is not added intentionally by the programmer in any program. It may be the result of the previous computation.
Example
Before the elimination of code:
p = x * y
q = x
r = q * y + 9
After the elimination of code:
p = x * y
r = q * y + 9
In this example, q = x is a dead code because there is no use of this code in the program.
Code Motion
Loops have a very important place for optimizations, mostly in the inner loops where programs tend to spend a lot of their time. A program's run time complexity may be improved by decreasing the amount of code in an inner loop, even if we increase the amount of code outside that loop.
Code motion reduces the number of code in a loop. This optimization computes a loop-invariant statement outside the loop.
Example
Evaluation of limit - 2 in the following while-statement:
while (i <= limit - 2)
This code will be further optimized as:
t = limit-2
while (i <= t)
After the optimization, limit-2 is computed only one time before entering the loop. Previously there would be n +1 calculations of limit-2 if we iterated the body of the loop n times.
Induction Variables and Reduction in Strength
Optimization of induction variables inside a loop is also an important optimization. Any variable of the form x = x + constant is induction variable.
Induction variables can be computed with a single increment per loop iteration.
Replacing an expensive operator with low strength is strength reduction.
Example
Before the reduction, code is:
i= 2;
while(i<10)
{
y = i * 6
}
Code, after the reduction:
i=2
x = 6
{
while(x<30)
y =x;
x = x +4:
}