Loop Invariant Computation In Compiler Design

Loop Invariants Code

Loop Invariant Example in Java is as follows:

// Find the maximum value in an array
public static int findMax(int[] arr) {
    // Initialize max to the first element of the array
    int max = arr[0];
    
    // Loop through the rest of the array and update max if necessary
    for (int i = 1; i < arr.length; i++) {
        // Check if the current element is more significant than max
        if (arr[i] > max) {
            // Update max to the current element if it is greater
            max = arr[i];
        }
    }
    
    // Return the maximum value found
    return max;
}

You can also try this code with Online Java Compiler

Run Code

In this code, we try to find out the max value in a given array “arr”. Here, “max” stores the maximum value after each iteration. So the “max” is a loop invariant since it is true before every iteration and after the iteration as well since the “max” tells us about the maximum value that is seen up to the current iteration of the loop. So the max has the maximum value after each iteration stored in it; thus, it is loop invariant.

In the above code, by using the “if” condition before updating the ”max” variable, we check if the current element is greater than the value stored in the “max” variable. Thus the loop runs efficiently, and we could avoid repeated checking of values that can’t be maximum.

Loop Invariant Computation

Loop Invariant Computation is used to optimize the performance of code in compiler design by moving loop invariant code out of the loop. So reiterating the fact that loop invariants are expressions with the same value in each iteration of the loop. Thus, it becomes essential for a developer to remove it so that the number of computations done gets reduced, which improves the program's overall performance. Therefore, optimization can be applied to all the programming languages CPP, JAVA, and Python.

Here we will see an example in the JAVA language:

public static void doSomething(int[] arr, int b, int c) {
       
    // Looping through the array and do something
    for (int i = 0; i < arr.length; i++) {
        int a = b + c;
        int result = arr[i] * a;
        // ... do something with the result ...
    }
}

You can also try this code with Online Java Compiler

Run Code

In the above example. “Int a = b + c” is loop invariant since the value for this expression does not change during any iteration of the loop. So, to optimize the code, we use the Loop Invariant Computation method to move to calculate the expression’s value out of the loop.

public static void doSomething(int[] arr, int b, int c) {
    // Move loop-invariant instruction outside the loop
    int a = b + c;
    
    // Loop through the array and do something with a
    for (int i = 0; i < arr.length; i++) {
        int result = arr[i] * a;
        // ... do something with the result ...
    }
}

By moving the expression out of the loop, we ensure that the value of the expression is computed only once in instead of previously doing it “n: times. This helps us reduce the computation time of the loop.

Loop Invariant Code Motion

The basic idea behind Code Motion is to move calculations or computations outside of a loop so that they are performed only once instead of on every iteration of the loop. This can help reduce the overall running time of the loop. Code motion identifies loop-invariant expressions, meaning their value does not change during the loop. These expressions can then be moved outside the loop to be computed only once before the loop begins.

This technique can also be done manually by inspecting the code and identifying loop-invariant expressions, or it can be done automatically by a compiler.

Benefits

There are many benefits to having loop invariant code, such as:

• Due to the loop invariant code, the loop is executed less often, which improves the efficiency of the code and reduces the time needed to execute the code.
   
• Due to the loop invariant, we can understand which statement needs to be moved out of the loop to be calculated only once, enhancing the loop's performance.
   
• It can also help reduce the memory usage required inside a loop by registering the constants out of the loop and not having to use them in every iteration.
   

Example:

int n = 1000000;
double[] arr = new double[n];
// Compute the sum of the array using a loop
double sum = 0;
for (int i = 0; i < n; i++) {
    sum += Math.sin(arr[i]);
}

You can also try this code with Online Java Compiler

Run Code

In this above code, the “Math.sin()” function is computed inside the loop for each element in the array “arr”. Thus the value of “Math.sin()” is a loop invariant, as it doesn't depend on the “for” loop index I.

int n = 1000000;
double[] arr = new double[n];
// Compute the sum of the array using Loop Invariant Computation
double sum2 = 0;
double sin;
for (int i = 0; i < n; i++) {
    sin = Math.sin(arr[i]);
    sum2 += sin;
}

You can also try this code with Online Java Compiler

Run Code

So by computing the value of the “Math.sin()” function outside and storing the result in a variable called “sin”, we can reduce the memory usage and thus improve the performance of the loop.
 

• However, too many variables can slow down the code since the compiler can register only limited variables. To solve this, we can use the optimization technique such as rematerialization.
   

Example:

int n = 1000000;
double[] arr = new double[n];
// Compute the sum of the array using Loop Invariant Computation
double sum = 0;
double sin;
for (int i = 0; i < n; i++) {
    sin = Math.sin(arr[i]);
    sum += sin * sin;
}

You can also try this code with Online Java Compiler

Run Code

The rematerialization technique is used to reduce the number of variables that are stored in as loop invariants. Instead of keeping the loop invariant in a variable, we simply recompute it when needed. This reduces the number of memory accesses and improves performance.

In this example, we compute the sum of the squares of the sines of the elements in the array arr. 

int n = 1000000;
double[] arr = new double[n];
// Compute the sum of the array using Rematerialization
double sum2 = 0;
for (int i = 0; i < n; i++) {
    sum2 += Math.sin(arr[i]) * Math.sin(arr[i]);
}

You can also try this code with Online Java Compiler

Run Code

So, instead of storing the value of Math.sin() in a variable sin, we simply recompute the value of Math.sin(arr[i]) when it is needed. This reduces the number of variables registered as loop invariants and can improve performance.

Also see,  cousins of compiler

Frequently Asked Questions

What are loop-invariant instructions?

Loop invariant instructions are the expression that remains constant in each iteration of the loop. The final result before the loop starts, during each iteration, and after the loop terminates, the loop invariant expression value remains the same.

What are some common examples of Loop Invariant?

Some common examples of using loop invariants include expressions and constants since their calculations need not be done in every iteration. We can perform various optimization methods (like LICM) to reduce time and memory consumption through loop invariants.

What are the benefits of using Loop Invariant Computation?

The Loop Invariant Computation method is one of the optimization techniques used to optimize the code inside the loop. It h=move out the entire expression whose value remains the same throughout the loop being run in order to save computation time and memory usage.

Conclusion

Thus, in this blog, we saw that Loop Invariant codes are those expressions that remain the same in every iteration of the code and thus need to be removed from the loop to save computation time and memory. Also, we saw optimization methods to save time and memory.

We understand that this topic is related to Compiler Design, and one needs to have basic knowledge before going through the blog. Thus, we have added various links which might be helpful for you to go through once or revise.

To refer to more articles like this on Coding Ninjas, you can visit the following blogs to understand more about Loop Optimization methods:

Loop Optimization

Phases of Compiler

Peephole Optimization in Compiler Design

Code Optimization in Compiler Design

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles,  interview experiences, and interview bundle for placement preparations. Read our blogs on aptitude, competitive programming, interview questions, IT certifications, and data structures and algorithms for the best practice.

Happy Learning!