Compiler Design and Construction - Old Questions
8. What is the purpose of code optimization? Explain different types of loop optimization techniques with example.
Code optimization is used to improve the intermediate code so that the output of the program could run faster and takes less space. It removes the unnecessary lines of the code and arranges the sequence of statements in order to speed up the program execution without wasting resources. It tries to improve the code by making it consume less resources (i.e. CPU, Memory) and deliver high speed.
Loop Optimization techniques are given below:
1. Frequency Reduction (Code Motion): In frequency reduction, the amount of code in loop is decreased. A statement or expression, which can be moved outside the loop body without affecting the semantics of the program, is moved outside the loop. For e.g.
Before optimization: while(i<100) { a = Sin(x)/Cos(x) + i; i++; } | After optimization: t = Sin(x)/Cos(x); while(i<100) { a = t + i; i++; } |
2. Loop Unrolling: In this technique the number of jumps and tests can be optimized by writing the code to times without changing the meaning of a code. For e.g.
Before optimization: int i = 1; while(i<100) { a[i] = b[i]; i++; }
| After optimization: int i = 1; while(i<100) { a[i] = b[i]; i++; a[i] = b[i]; i++; } |
The first code loop repeats 50 times whereas second code loop repeats 25 times. Hence, optimization is done.
3. Loop Fusion/Loop Jamming: This technique combines the bodies of two loops whenever the same index variable and number of iterations are shared. For e.g.
Before optimization: for(i=0;i<=10;i++) { Printf(“Jayanta”); } for(i=0;i<=10;i++) { Printf(“Poudel”); } | After optimization: for(i=0;i<=10;i++) { Printf(“Jayanta”); Printf(“Poudel”); }
|
4. Reduction in Strength: The strength of certain operators is higher than other operators. For example, strength of * is higher than +. Usually, compiler takes more time for higher strength operators and execution speed is less. Replacement of higher strength operator by lower strength operator is called a strength reduction technique
Optimization can be done by applying strength reduction technique where higher strength can be replaced by lower strength operators. For e.g.
Before optimization: for (i=1;i<=10;i++) { sum = i * 7; printf(“%d”, sum); }
| After optimization: temp = 7; for(i=1;i<=10;i++) { temp = temp + 7; sum = temp; printf(“%d”, sum) } |