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;
