Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Partial Redundancy Elimination in Compiler Design
3.
Let’s Understand Partial Redundancy
4.
The Source of Redundancy
5.
Can all Redundancies be Eliminated?
6.
What is the importance of PRE?
6.1.
Benefits of PRE:
7.
How to perform PRE?
7.1.
The Lazy Code Motion Algorithm (LCM)
7.1.1.
It is a Four-Step Algorithm:
7.1.2.
Example for LCM: 
7.2.
Global Value Numbering Algorithm
8.
Frequently Asked Questions
8.1.
Can all redundancies be eliminated using PRE?
8.2.
What are loop invariant expressions?
8.3.
Is it possible to use PRE on code with side effects? 
8.4.
What are some limitations of PRE?
9.
Conclusion
Last Updated: Mar 27, 2024

Partial Redundancy Elimination in Compiler Design

Author Sourabh
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

One of the phases of the compilation process is code optimization. This phase also goes by the name of "machine-independent code optimization." In this phase, we use several techniques and procedures to reduce the runtime that is required to execute code. The compiler can optimize different types of code, such as dead code and partially redundant code.

Partial redundancy elimination in compiler design

Partial Redundancy Elimination in Compiler Design

PRE (Partial Redundancy Elimination) is a compiler optimization method. PRE aims to remove redundant computations from the program. Redundant computations are those that are achieved in more than one instance. However, it produces the same result every time. By removing these redundancies, PRE can enhance the overall performance of the program by reducing the number of instructions carried out.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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;
}

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;
}

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;
}

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;

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

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)

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 PythonData Structures and AlgorithmsCompetitive ProgrammingSystem 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!

Live masterclass