Difference between Machine Dependent and Independent Code Optimization
Machine Dependent code optimization
These techniques involve program transformations that improve the target code without taking into consideration any properties of the target machine. These techniques are either applied on source code and/or intermediate code
Machine Independent code optimization
- These techniques involve transformations that take into consideration properties of the target machine like registers and special machine instruction sequences available etc. these techniques are applied on target code generated.
- The optimization which is applied on an intermediate code called as machine independent code optimization
Machine independent code optimization is classified into three types based on the scope. They are
Local optimization
Loop optimization
Global optimization
Local Optimization:
- The optimization performed within a block is called local optimization
- When local optimization has to be performed, its scope is limited to specific block of statements
The following optimization techniques help a compiler improve a program without changing the meaning of the source code:
Common sub expression elimination
Copy Propagation
Dead code elimination
Constant folding
Common sub expression elimination
- An expression E is said to common sub expression if it was previously computed and the value of variable in E have not changed since the previous computation
- The common sub expression elimination avoids the recomputation of an expression if its value has already been completed
Example 1:
Consider the following three address code.
t1 = 4 * i
n = a[t1]
t2 = 4 * i
t3 = 4 * j
t4 = a[t3]
a[t2] = t4
t5 = 4 * j
a[t5] = n
in this three address code, 4 * i and 4 * j are common sub expressions. So they are eliminated by eliminating t2 and t4
After applying common sub expression elimination technique the optimized code is
t1 = 4 * i
n = a[t1]
t3 = 4 * j
t4 = a[t3]
a[t1] = t4
a[t3] = n
Copy Propagation:
Copy propagation helps the user to use one variable instead of another variable
It is of the form x:=y, copy value of y into x
Example 1:
a = b
t1 = a
c = t1
In the above code, value of variable b is assigned into variable a. Instead, assign value of variable b into variable c directly so that copy propagation is applied by eliminating first two assignment statements
The optimized code is
a = b
t1 = a
c = b
Example 2:
x = t3 x = t3
a[t2] = t5 after copy a[t2] = t5
a[t4] = x propagation a[t4] = t3
Dead Cod e Elimination:
- A variable is said to be live at a point in a program if its value can be used subsequently, otherwise it is dead at that point
- The dead code is basically an useless code. An optimization can be performed by eliminating such a dead code
- The dead code elimination can be done by eliminating the assignment statements. The assignment is called as dead code assignment
Example 1:
i = j;
r = I + 10;
The above code can be rewritten by applying copy propagation as:
i = j;
r = j + 10;
Now, the assignment statement i = j becomes dead code statement as there is no use of variable i once copy propagation has applied. The optimized code would be r = j + 10;
Example 2:
i = 0;
if (I == 1)
{
i++;
}
In the above code, if statement is a dead code as this condition never gets satisfied. So, optimization can be done by removing if statement
Note: Copy propagation technique turns the copy statements into dead code.
Constant folding:
- Constant folding is another optimization technique in which the constant expressions are calculated during compilation time
- When constant expressions are calculated during compilation time, efficiency is increase
Example: Consider the given code,
const int a = 1p;
int b;
i = 10 + a;
j = i * 3 + b;
- The variable a is declared as constant, i.e., the value of ‘a’ remains same when it calculates either at compile time or run time
- The statement i = 10 + a is a constant expression. Hence, it is calculate at runtime
- The optimized code
const int a = 10;
int b;
j = 60 + b;
0 comments:
Post a Comment