Difference between Machine Dependent and Independent Code Optimization

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;



Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment