Loop Optimization Techniques in Compiler Design
Loop optimization can be performed by using the following techniques-
- Code Motion
- Induction Variable Elimination
- Strength Reduction
- Loop Fusion
- Loop Unrolling
- Loop Invariant Method
- Loop Jamming
- Loop Fission
- Loop Interchange
- Loop Peeling
- Unswitched
We will discuss these techniques one by one.
1. Code Motion
Also known as Frequency Reduction or Loop Invariant, this technique reduces the number of lines of code in a loop by moving some statements outside the loop.
Only those statements or expressions that do not affect a program's semantics and give the same result even after not shifting the statements can be placed just before the loop.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a = 50;
int x, y = 10, z = 10;
while(a>0) {
x = y + z;
if(a%x==0)
printf("%d",a);
a--;
}
}
You can also try this code with Online C Compiler
In the above code, a variable a is initialized to 50. Then a loop is there, running till a > 0 means 50 times in which a variable x is assigned to y + z and a condition checking if a divided by x leaves remainder 0 then prints the value of a.
In the loop, the only variable whose value is getting updated is a. The value of x, y, and z is not getting changed. So, we can optimize this code by placing the statement x = y + z outside the loop.
Hence, the optimized code will be
#include <stdio.h>
void main() {
int a = 50;
int x, y = 10, z = 10;
x = y + z;
while(a>0) {
if(a%x==0)
printf("%d",a);
a--;
}
}
You can also try this code with Online C Compiler
2. Induction Variable Elimination
In the induction variable elimination technique, there is an induction variable. A variable x is called an induction variable in a loop L; if in every round of the loop, the value of x changes, it either gets incremented or decremented.
The aim of the induction variable elimination method is to replace the induction variable from the loop. This technique improves the execution time of a program.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a[20], b[20];
int i, j, k;
for (i = 0, j = 0, k = 0; i < 20; i++)
a[j++] = b[k++];
}
You can also try this code with Online C Compiler
In the above code, there are three induction variables i, j, and k. The variable i is a counter variable that is running a loop to copy the values from array b to array a while the variables j and k are just pointing to the current indices of the two arrays. Thus, we can eliminate the induction variables j and k to optimize our code.
Hence, the optimized code will be
#include <stdio.h>
void main() {
int a[20], b[20];
int i;
for (i = 0; i < 20; i++)
a[i] = b[i];
}
You can also try this code with Online C Compiler
3. Strength Reduction
Strength reduction or reduction in strength is a technique in which we replace expensive operations with cheaper operations. For example, the strength of the * operator is higher than the + operator. So, the compiler takes more time to execute the multiplication operation than the addition operation. To optimize the code, we will simply try to replace the *, i.e., high strength or expensive operator, with the +, i.e., low strength or cheap operator.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a = 1, b;
while (a<10) {
b = a * 2;
a++;
}
}
You can also try this code with Online C Compiler
In the above code, there are 2 variables a and b. Variable a is a loop variable. Inside the loop, a multiplication operation is being performed in which variable a and the digit 2 are multiplied, and the result is stored in variable b. Since * is a high-strength operator, we will replace it with the + operator.
Hence, the optimized code will be
#include <stdio.h>
void main() {
int a = 1, b;
while (a<10) {
b = a + a;
a++;
}
}
You can also try this code with Online C Compiler
4. Loop Fusion
Also known as Loop Jamming, this technique combines two or more loops which have the same index variable and number of iterations.
This technique reduces the time taken in compiling all the loops.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int a[10], b[10], i;
for(i = 0; i < 10; i++)
a[i] = 1;
for(i = 0; i < 10; i++)
b[i] = 2;
}
You can also try this code with Online C Compiler
In the above code, there are two loops. The first loop running ten times assigns the value 1 at each index of the array a while the second loop also runs ten times, assigning the value 2 at each index of the array b. We can observe that the work of both these loops is almost the same. Both are running ten times and assigning a value to an array. Thus, we can combine both these loops to optimize our code.
Hence, the optimized code will be
#include <stdio.h>
void main() {
int a[10], b[10], i;
for(i = 0; i < 10; i++) {
a[i] = 1;
b[i] = 2;
}
}
You can also try this code with Online C Compiler
5. Loop Unrolling
The loop unrolling technique transforms the loop. In this technique, the number of jumps and tests can be optimized by writing the code to times without changing the meaning of the code. It reduces the number of iterations and increases the program’s speed by eliminating the loop control instructions and loop test instructions.
Let’s take an example to understand this technique.
Example:
Consider the following piece of code.
#include <stdio.h>
void main() {
int i = 1;
int a[100], b[100];
while(i<100) {
a[i] = b[i];
i++;
}
}
You can also try this code with Online C Compiler
In the above code, a loop is running 100 times. We can optimize this code by repeating the statements so that the loop runs only 50 times.
Hence, the optimized code will be
#include <stdio.h>
void main() {
int i = 1;
int a[100], b[100];
while(i<100) {
a[i] = b[i];
i++;
a[i] = b[i];
i++;
}
}
You can also try this code with Online C Compiler
6. Loop Invariant Method
The Loop Invariant Method involves moving calculations that do not change during loop iterations outside the loop to reduce redundant computations.
Example:
Original Code:
#include <stdio.h>
int main() {
int a = 5, b = 10, c = 20, d;
for (int i = 0; i < 10; i++) {
d = (a * b) + c; // a * b + c is invariant
printf("%d ", d);
}
return 0;
}
You can also try this code with Online C Compiler
Optimized Code:
#include <stdio.h>
int main() {
int a = 5, b = 10, c = 20, d;
d = (a * b) + c; // Move invariant calculation outside the loop
for (int i = 0; i < 10; i++) {
printf("%d ", d);
}
return 0;
}
You can also try this code with Online C Compiler
7. Loop Jamming
Loop Jamming combines multiple loops into one when they perform related tasks on the same data, reducing overhead.
Example:
Original Code:
#include <stdio.h>
int main() {
int a[10], b[10];
for (int i = 0; i < 10; i++) {
a[i] = 1;
}
for (int i = 0; i < 10; i++) {
b[i] = 2;
}
return 0;
}
You can also try this code with Online C Compiler
Optimized Code:
#include <stdio.h>
int main() {
int a[10], b[10];
for (int i = 0; i < 10; i++) {
a[i] = 1;
b[i] = 2; // Combine both loops
}
return 0;
}
You can also try this code with Online C Compiler
8. Loop Fission
Loop Fission involves breaking a loop into smaller loops to improve performance by isolating independent operations.
Example:
Original Code:
#include <stdio.h>
int main() {
int a[10], b[10];
for (int i = 0; i < 10; i++) {
a[i] = i;
b[i] = i * 2;
}
return 0;
}
You can also try this code with Online C Compiler
Optimized Code:
#include <stdio.h>
int main() {
int a[10], b[10];
for (int i = 0; i < 10; i++) {
a[i] = i; // First loop
}
for (int i = 0; i < 10; i++) {
b[i] = i * 2; // Second loop
}
return 0;
}
You can also try this code with Online C Compiler
9. Loop Interchange
Loop Interchange swaps nested loop order to improve memory access patterns, especially for multi-dimensional arrays.
Example:
Original Code:
#include <stdio.h>
int main() {
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
You can also try this code with Online C Compiler
Optimized Code:
#include <stdio.h>
int main() {
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
for (int j = 0; j < 3; j++) { // Interchange the loops
for (int i = 0; i < 3; i++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
You can also try this code with Online C Compiler
10. Loop Peeling
Loop Peeling handles the first few iterations of a loop separately, optimizing performance by reducing complex operations in the loop body.
Example:
Original Code:
#include <stdio.h>
int main() {
int a[10];
for (int i = 0; i < 10; i++) {
a[i] = i * 2;
}
return 0;
}
You can also try this code with Online C Compiler
Optimized Code:
#include <stdio.h>
int main() {
int a[10];
a[0] = 0; // Handle first iteration separately
a[1] = 2;
for (int i = 2; i < 10; i++) {
a[i] = i * 2;
}
return 0;
}
You can also try this code with Online C Compiler
11. Unswitched
Unswitched technique involves simplifying switch statements into if-else conditions when a small number of cases are involved.
Example:
Original Code:
#include <stdio.h>
int main() {
int x = 2;
switch (x) {
case 1: printf("One\n"); break;
case 2: printf("Two\n"); break;
case 3: printf("Three\n"); break;
}
return 0;
}
You can also try this code with Online C Compiler
Optimized Code:
#include <stdio.h>
int main() {
int x = 2;
if (x == 1) {
printf("One\n");
} else if (x == 2) {
printf("Two\n"); // Use if-else to avoid switch
} else if (x == 3) {
printf("Three\n");
}
return 0;
}
You can also try this code with Online C Compiler
Frequently Asked Questions
Is loop jamming a loop optimization technique?
Yes. Loop jamming is a loop optimization technique. It is a combination of two or more loops in a single loop. It is important because it is used to reduce the time taken to combine a large number of for loops.
How to optimize for loop in C?
To optimize for loops in C, consider techniques such as loop unrolling, reducing iterations, reusing values, loop invariant code motion, using cache-friendly data structures, and parallelization. Balance these optimizations with code readability and maintainability, and measure performance to ensure improvement.
Define loop optimization.
Loop optimization is a machine-independent optimization technique that increases a program's execution speed by decreasing the overhead of loops. Since the most time of a compiler is spent executing the loops, reducing the number of instructions in a loop will improve the program's running time and help execute the code faster.
What is a loop optimization technique?
A loop optimization technique improves the performance of loops in a program by minimizing redundant operations, reducing execution time, and enhancing efficiency.
What are the types of optimization in compiler design?
Compiler design optimization includes loop optimization, constant folding, dead code elimination, inlining, register allocation, and strength reduction, aimed at improving execution speed and reducing resource usage.
Conclusion
In this article, we have studied Loop Optimization in Compiler design. We went through the concept thoroughly, discussing various loop optimization techniques, including code motion, induction variable elimination, strength reduction, loop fusion, and loop unrolling, along with an example of each.
Recommended Reading:
569+ registered 
