Compiler Design and Construction - Old Questions
8. Explain different types of loop optimization techniques.
Answer
AI is thinking...
Loop Optimization is the process of increasing execution speed and reducing the overheads associated with loops. Loop Optimization is a machine independent optimization.
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++; } |
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) } |