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!
63+ registered