Partial Redundancy Elimination in Compiler Design

Let’s Understand Partial Redundancy

Redundancy is basically unnecessary or repetitive code present in a program that does not contribute to the functionality of the program. When a computation is performed more than once along some of the execution paths but not along all execution paths, this condition is known as "partial redundancy."

An example of full redundancy is given below.

if(condition1) {
x = a + b;
}
else{
x = a + b;
}

You can also try this code with Online C++ Compiler

Run Code

As you can see in the above example, the computation of A+B is fully redundant, as it is performed along both execution paths.
But the condition of partial redundancy arrived if we modified the code as follows.

if(condition1) {
x = a + b;
}
if(condition2) {
y = a + b;
}

You can also try this code with Online C++ Compiler

Run Code

As you can see in the above example, A+B is only partially redundant because it is performed along some execution path(“given that both conditions are true”) but not along all execution paths.

The Source of Redundancy

Redundancy is due to the presence of one or multiple expressions from the following expressions.

1. Partially redundant expressions: It is an expression in which the value that is computed by the expression is already available on some of the paths but is not available on all the paths through a program to that expression.
    
2. Loop invariant expression: It is a condition that is necessarily true immediately before and immediately after each iteration of the loop.
    
3. Common sub-expression: A common sub-expression is an expression that has appeared and computed before and appears again during the computation of the code.

Can all Redundancies be Eliminated?

One of the questions that might arise in your mind while studying partial redundancy elimination is whether it is possible to remove all the redundant computations along every path. 
The answer depends on whether we are allowed to alter the flow graph by creating new blocks. All redundancies can be eliminated if we are allowed to change the flow graph. While if we are not permitted to change the flow graph, then all the redundancies cannot be eliminated.

What is the importance of PRE?

We can significantly improve the performance of a program by eliminating partial redundancies. By disposing of these redundancies in this system, the compiler can effortlessly reduce the number of instructions that are required to be executed. This will result in less execution time, and it will even make our system more power efficient. Lower power consumption is necessary in modern computing environments, where the energy efficiency and performance of our systems are critical factors.

Benefits of PRE:

• Execution Time: PRE will reduce the number of instructions that are needed to be executed to run a program. Since our system has fewer instructions to execute, it will result in a faster execution time.
   
• Power Consumption: PRE will reduce the number of instructions that are needed to be executed, which will save us power and make our system more power efficient.
   
• Readability: PRE will improve the readability of our program by removing repeated code and redundancies, which will make it easier for the developers to read and maintain the code.
   
• Debug: PRE will remove unwanted or unnecessary code from our code, which will make debugging easier and enable developers to find and correct any errors in the code.

How to perform PRE?

To implement PRE in modern compilers. There are various algorithms that are available in the market for our use. Some of the algorithms that are used worldwide are:

• Lazy Code Motion Algorithm (LCM)
   
• Global Value Numbering Algorithm (GVN).
   

These two algorithms have their own unique pros and cons. And which one we should use depends on the requirements of the compiler and the architecture that we are targeting.

The Lazy Code Motion Algorithm (LCM)

The Lazy code motion algorithm (LCM) is used for the purpose of PRE, which aims to minimize the total number of computations that is to be performed to execute a program. At the same time, it prevents the original semantics of the program from changing.
LCM is the algorithm that works by identifying partially redundant expressions. And then, it will move them to a point in the control flow graph where they are guaranteed to be executed at most once. This is achieved by placing the computation at a point, also known as the earliest point in the program, where it is safe to do so.

It is a Four-Step Algorithm:

1. Step 1: The first step uses anticipation to determine where the expression can be placed.
    
2. Step 2: The second step will be computing the earliest and latest points for each expression.
    
3. Step 3: The third step then pushes the cut set down to the point where any further delay would alter the semantics of the program and may even introduce redundancy in the program.
    
4. Step 4: The final step will be to clean up the pod, and we can do that by removing the assignment to temporary variables that were used previously.
    

Each step should be accomplished with a data flow. The first and fourth are backward flow programs. At the same time, the 2nd and the 3rd are forward flow problems.

Example for LCM:
 

Before applying LCM:

for (int i = 0; i < n; i++) {
int x = a[i] * b[i];
int y = x + c[i];
sum += y;
}

You can also try this code with Online C++ Compiler

Run Code

And in this code, we are calculating the value of ‘x’, only to be used to compute the value ‘y’ and the value is only used to update the ‘sum’ variable.
Now we will use lazy code motion. We will move the computation of ‘x’ outside the loop because it does not depend on the loop variable ‘i’. This will reduce the number of multiplications performed and also improve the performance of the code.

After applying LCM:

int x = 0;
for (int i = 0; i < n; i++) {
x += a[i] * b[i];
int y = x + c[i];
sum += y;
}

You can also try this code with Online C++ Compiler

Run Code

As you can see in the above-modified code, we compute acts only once before the loop. And then, we will accumulate its value inside the loop. And by doing this, we will avoid the redundant computation of ‘a[i]*b[i]’ for each iteration of the loop.

Global Value Numbering Algorithm

It is an optimization algorithm utilized during compiling processes and focuses on identifying redundant computations within programs. To eliminate operations that do not add any extra value or information, GVN assigns unique values for any expression representing similar values, henceforth replacing repetitive calculations with only one computation. For maximum efficiency of GVN's application on programs, it operates solely on their intermediate representations(IR), resulting in advancements in their performances over time.

GVN is a Three-Step Algorithm:

1. Step 1: In the first step, GVN will assign the value number to the expression.
    
2. Step 2: In the second step, GVN will identify expressions that are equivalent.
    
3. Step 3: In the third and final step, the GVN will replace the redundant expression, which is equivalent to a single computation.
    

Example of GVM:

x = 2 + 3;
y = 4 + 5;
z = x + y;
w = x + y;

You can also try this code with Online C++ Compiler

Run Code

Solution:
1. It will assign value numbers to each of the expressions.

x = 2 + 3;    // 1
y = 4 + 5;    // 2
z = x + y;    // 3
w = x + y;    // 3

You can also try this code with Online C++ Compiler

Run Code

2. Then it will replace the occurrence of identical expressions with their value number:

x = 2 + 3;    // 1
y = 4 + 5;    // 2
z = 1 + 2;    // 3 (1 + 2)
w = 1 + 2;    // 3 (1 + 2)

You can also try this code with Online C++ Compiler

Run Code

As we can see, this algorithm has identified the expression ‘x+y’ in lines 3 and 4 as identical. So it has replaced them both with the value "3”. This optimization will reduce the number of computations required to be performed in the program, which will lead to faster and more efficient execution of our code.

Also check out - Phases of Compiler

Frequently Asked Questions

Can all redundancies be eliminated using PRE?

The answer depends on whether the flow graph can be changed by creating new blocks. If we cannot change the flow graph, then we cannot eliminate all redundancies using PRE. But if we are allowed to change the flow graph, then we can remove all redundancies.

What are loop invariant expressions?

In programming terms, there are certain expressions that retain their value throughout the execution of a loop. But we can remove these expressions from the loop without changing the functionality of our program.

Is it possible to use PRE on code with side effects? 

We can use PRE on code if the side effects are only related to the value of the variable within the current basic block. But the program fails when the side effects have an impact on other parts of the program. Then it will not be possible to perform a PRE.

What are some limitations of PRE?

One of the limitations of PRE is that it is highly dependent on the structure of the given program, and another is that there are chances that it might introduce new redundancy in the program.

Conclusion

PRE is an important optimization technique that is required by most modern compilers. It is required because it will significantly improve the performance and energy efficiency of a program. There are various algorithms available in the market for the implementation of PRE. Some examples are lazy code motion and global value numbering. The developer should choose the most suitable approach based on the specific requirements and the structure of the targeted architecture.

If you want to learn about Code Optimization in Compiler Design, you can refer to our article.
For more information, refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Python, Data Structures and Algorithms, Competitive Programming, System Design, and many more! Head over to our practice platform, Coding Ninjas Studio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more! Nevertheless, consider our paid courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!