Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Peephole Optimization in Compiler Design?
3.
Objectives of Peephole Optimization in Compiler Design
4.
Working of Peephole Optimization in Compiler design
4.1.
Identification
4.2.
Optimization
4.3.
Analysis
4.4.
Iteration
5.
Peephole Optimization Techniques 
5.1.
Redundant Load and Store
5.2.
Strength Reduction
5.3.
Simply Algebraic Expressions
5.4.
Replace Slower Instructions With Faster
5.5.
Dead code Elimination
6.
Frequently Asked Questions
6.1.
Is peephole optimization machine-dependent? 
6.2.
How is peephole optimization used to eliminate unreachable code? 
6.3.
What is peephole optimization?
6.4.
What is the difference between peephole optimization and normal optimization?
6.5.
What is the peephole theory?
6.6.
Characteristics of peephole optimization
7.
Conclusion
Last Updated: Apr 27, 2024
Medium

Peephole Optimization in Compiler Design

Author Apoorv Dixit
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Welcome to our blog on peephole optimization in compiler design! While compilers may seem like mysterious machines, they're essentially translators, turning human-readable code into computer-understandable instructions. And within these compilers lies a clever tool called peephole optimization.

Think of peephole optimization as a detail-oriented editor, constantly scanning through the code, looking for ways to make it better. In this blog, we'll take a closer look at what peephole optimization is, how it works, and why it's essential for creating faster and more efficient software.

peephole optimization

Peephole optimization is an optimization technique by which code is optimized to improve the machine's performance. More formally,

What is Peephole Optimization in Compiler Design?

Peephole optimization is an optimization technique performed on a small set of compiler-generated instructions; the small set is known as the peephole optimization in compiler design or window.

Some important aspects regarding peephole optimization:

  1. It is applied to the source code after it has been converted to the target code.
     
  2. Peephole optimization comes under machine-dependent optimization. Machine-dependent optimization occurs after the target code has been generated and transformed to fit the target machine architecture. It makes use of CPU registers and may make use of absolute memory references rather than relative memory references.
     
  3. It is applied to a small piece of code, repeatedly.
     

The objectives of peephole optimization are as follows:

  1. Improve performance
  2. Reduce memory footprint
  3. Reduce code size.
     
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

Objectives of Peephole Optimization in Compiler Design

The objectives of Peephole optimization in compiler design are:

  • It makes the generated machine code smaller,  improving cache usage and saving memory.
  • Improve the performance of instructions arranged to make the program run faster.
  • Get rid of operations that are not needed or are repeated to make things work better and smoother.
  • It calculates fixed values in advance and substitutes variables with already known numbers.
  • Improve how choices are made to control the program's flow more effectively.
  • Replace slower instructions with quicker options for better performance.
  • Optimize memory operations for better data handling.
  • Use specific hardware features for better performance on the target platform.

Working of Peephole Optimization in Compiler design

There are mainly four steps in Peephole Optimization in Compiler Design. The steps are as follows:

Identification

  • The first step says that you must identify the code section where you need the Peephole Optimization.
     
  • Peephole is an instruction with a fixed window size, so the window size depends on the specific optimization being performed.
     
  • The compiler helps to define the instructions within the window.

Optimization

  • In the next step, you must apply the rules of optimizations pre-defined in the Peephole.
     
  • The compiler will search for the specific pattern of instructions in the window.
     
  • There can be many types of patterns, such as insufficient code, series of loads and stores or complex patterns like branches.

Analysis

  • After the pattern is identified, the compiler will make the changes in the instructions.
     
  • Now the compiler will cross-check the codes to determine whether the changes improved the code. 
     
  • It will check the improvement based on size, speed and memory usage.

Iteration

  • The above steps will go on a loop by finding the Peephole repeatedly until no more optimisation is left in the code. 
     
  • The compiler will go to each instruction one at a time and make the changes and reanalyse it for the best result.

Peephole Optimization Techniques 

There are various peephole optimization techniques.

Redundant Load and Store

In this optimization, the redundant operations are removed. For example, loading and storing values on registers can be optimized.

For example, 

a= b+c

d= a+e

It is implemented on the register(R0) as

MOV b, R0; instruction to copy b to the register
ADD c, R0; instruction to Add c to the register, the register is now b+c
MOV R0, a; instruction to Copy the register(b+c) to a
MOV a, R0; instruction to Copy a to the register
ADD e, R0  ;instruction to  Add e to the register, the register is now a(b+c)+e
MOV R0, d; instruction to Copy the register to d


This can be optimized by removing load and store operation, like in third instruction value in register R0 is copied to a, and it again loaded to R0 in the next step for further operation. The optimized implementation will be:

MOV b, R0; instruction to Copy b to the register
ADD c, R0; instruction to Add c to the register, which is now b+c (a)
MOV R0, a; instruction to Copy the register to a
ADD e, R0; instruction to Add e to the register, which is now b+c+e [(a)+e]
MOV R0, d; instruction to Copy the register to d

Strength Reduction

In strength reduction optimization, operators that consume higher execution time are replaced by the operators consuming less execution time. Like multiplication and division, operators can be replaced by shift operators.

Initial code:
n = a * 2;
Optimized code:
 b= a << 1;
//left shifting the bit
Initial code:
b = a / 2;
Optimized code:
b = a >> 1; 
// right shifting the bit by one will give the same result

Simply Algebraic Expressions

The algebraic expressions that are useless or written inefficiently are transformed.

For example:

a=a+0
a=a*1
a=a/1
a=a-0
//All these above expression are causing calculation overhead.
// These can be removed for optimization

Replace Slower Instructions With Faster

Slower instructions can be replaced with faster ones, and registers play an important role. For example, a register supporting unit increment operation will perform better than adding one to the register. The same can be done with many other operations, like multiplication.

Add #1
SUB #1
//The above instruction can be replaced with
// INC R
// DEC R
//If the register supports increment and decrement


Let’s see another example of Java bytecode:

Here X is loaded on ‘a’ twice and then multiplied. We can use dup function, it will copy the value on the top of the stack( ‘X’ need not be loaded again), and then we can perform our operation. It works faster and can be preferred over slower operations.

a load X
a load X
Mul
// The above instructions can be replaced with
a load X 
dup 
Mul

Dead code Elimination

The dead code can be eliminated to improve the system's performance; resources will be free and less memory will be needed.

int dead(void)
{
    int a=1;
    int b=5;
    int c=a+b;
    return c;
// c will be returned 
// The remaining part of code is dead code, never reachable
    int k=1;     
    k=k*2;
    k=k+b;
    return k;
// This dead code can be removed for optimization
} 


Moreover, null sequences and user less operations can be deleted too.

Frequently Asked Questions

Is peephole optimization machine-dependent? 

Yes, peephole optimization can be machine-dependent because it focuses on specific patterns of instructions. It looks at certain instruction patterns and makes changes to work better on that computer. This makes the computer run faster and smoother.

How is peephole optimization used to eliminate unreachable code? 

Peephole optimization eliminates unreachable code by removing and recognizing instruction sequences that can never be executed. It streamlines the program and improves efficiency.

What is peephole optimization?

Peephole optimization is a technique in compiler design where a small window of code, known as the "peephole," is examined for patterns that can be replaced with more efficient code, resulting in improved performance.

What is the difference between peephole optimization and normal optimization?

Peephole optimization differs from normal optimization in its localized approach. While normal optimization considers larger sections of code, peephole optimization focuses on small sequences of instructions, making it suitable for fine-tuning.

What is the peephole theory?

The peephole theory posits that within a limited window of code, certain patterns or sequences frequently occur, offering opportunities for optimization. By identifying and replacing these patterns, the overall efficiency of the code can be enhanced.

Characteristics of peephole optimization

Characteristics of peephole optimization include its localized scope, reliance on pattern recognition within small code sequences, and ability to achieve incremental improvements in code efficiency without major structural changes.

Conclusion

In this article, we have extensively discussed peephole optimization in Compiler design and various optimization techniques involved in it. These techniques improve performance and memory reduction, reducing the size of code. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning Ninja!

Previous article
DAG Representation in Compiler Design
Next article
Partial Redundancy Elimination in Compiler Design
Live masterclass