Code optimization is technique used by compiler to produce efficient code.Intermediate code is replace by equivalent more efficient construct. Reduce Execution time or space taken by object after optimization.
Requirement of Intermediate code optimization
- Reduce execution time.
- Increase program efficiency.
- Program after optimization occupy less memory space.
- Produce better object language code.
Type of code optimization
code optimization classified into two type.
- Machine Dependent.(Platform Dependent)
- Machine Independent(Platform Independent).
Machine Dependent optimization
In Machine dependent Optimization require knowledge of machine.Addressing mode and instruction set used by machine to produce efficient code.Machine Register are Involve in machine dependent optimization.Peephole optimization is type of machine dependent optimization.
Machine Independent optimization
Machine Independent optimization to improve the intermediate code to get better target code.Here does not involve any CPU register and memory location.Elimination of common sub expression,elimination of unreachable code,elimination of loop invariant etc.
Sources of optimization
Local optimization
- Common Sub-expression Elimination.
- Constant Folding.
- Dead Code Elimination.
Common Sub Expression
Expression E is previously computed avoid recomputing of the expression if it is already computed.
A=P+Q+R
B=P+Q+S
P+Q is common Sub Expression
A1=P+Q
A=A1+R
B=A1+S
Constant Folding
Constant expression is calculated during optimization that is called constant folding.
const p=2;
q=p+4;
After constant folding
q=6;
Dead code Elimination
Remove useless code from the program is called Dead code elimination.
Example
int main()
{
int a=10;
int b=20;
int c;
c=a+b;
return c;
b=5;
b=b+2;
return 0;
}
In this program
b=5;
b=b+2;
is dead code .
Loop optimization
- Code Motion.
- Loop Fusion.
- Loop Unrolling.
Code Motion
If Expression in loop remain unchanged after executing the loop .That expression can be placed outside the loop is called code Motion.
Example
p=10
while(p>1)
{
c=a+b;
p=p-1;
}
Here c=a+b is unchanged code after loop execution so placed outside from the loop.
Loop Fusion
That is also called loop jamming. In which replace multiple loops with single one.
Example
int main()
{
int i,p[10],q[10];
for(i=1;i<10;i++)
p[i]=i;
for(i=1;i<10;i++)
q[i]=i;
}
After Loop Fusion
int main()
{
int i,p[10],q[10];
for(i=1;i<10;i++)
{
a[i]=i;
b[i]=i;
}
Loop Unrolling
Loop unrolling is loop transformation technique that optimize execution time of program by remove iterations.
For Example
int main()
{
for(j=1;j<=3;j++)
{
print("compiler");
}
}
After Loop Unrolling
int main()
{
Printf("compiler");
Printf("compiler");
Printf("compiler");
}
Algorithmic Optimization
We cant achieve optimization until we dont have good algorithm.A good Algorithm take less time to solve problem thats why time good algorithm have less time complexity. After Analysis of the Algorithm find Time Complexity than choose Algorithm.
Complexity of Bubble sort is n2
complexity of Quick sort is nLogn.
Here Time complexity of Quick sort is less than Bubble sort.
Data Flow Analysis
Analyze the flow of data from one block to another block of a program.The whole program is divided into BLOCK and block joined to make a FLOW-GRAPH .After find BLOCK and Flow-Graph apply optimization called Data flow Analysis.
For Example
i=1;
j=1;
t1=2*i;
t2=t1+j;
t3=4*t2
t4=t3
a[t4]=1
j=J+1;
if j<=5 goto(3)
i=i+1
ifi<=10 goto(2)
Find Block and node and edge.
Solution
Block 1
i=1
Block 2
j=1
Block 3
t1=2*i;
t2=t1+j;
t3=4*t2
t4=t3
a[t4]=1
j=J+1;
if j<=5 goto(3)
Block 4
i=i+1
if i<=10 goto(2)
Here Block is 4
Nodes=4
Edges=5
'
0 Comments