Peephole Optimization

An important topic for Compiler Course.

1. Welcome to my Presentation Topic : Peephole Optimization Samrin Ahmed ID: 011142021

2. Contents Functioning of Peephole Optimization & Example Replacement Rules Working Flow of Peephole Optimization Introduction to Peephole Optimization What is an Optimization 2 Conclusion References

3. What is Optimization ?? Process of transforming a piece of code to make it more efficient (either in terms of time or space) without changing its output or side-effects. Tries to minimize or maximize some attributes of an executable computer program.

4. Introduction to Peephole Optimization ?? Optimization performed over a very small set of instructions in a segment of generated code. Works by recognizing sets of instructions that can be replaced by shorter or faster sets of instructions . Goals: improve performance reduce code size reduce memory footprint

5. Why it’s needed ?? After compilation, the code still has some flaws Scheduling & allocation really are NP-Complete Optimizer may not implement every needed transformation Curing the problem More work on scheduling and allocation Implement more optimizations — or — Optimize after compilation Peephole optimization Link-time optimization

6. Working Flow of Peephole Optimization

7. Replacement Rules Common techniques applied in peephole optimization:- Constant folding   – Evaluate constant sub-expressions in advance. Strength reduction – Replace slow operations with faster equivalents. Null sequences – Delete useless operations. Combine operations – Replace several operations with one equivalent. Algebraic laws – Use algebraic laws to simplify or reorder instructions. Special case instructions – Use instructions designed for special operand cases. Address mode operations – Use address modes to simplify code.

8. Functioning of Peephole Optimization Replacing slow instructions with faster ones Removing redundant code Removing redundant stack instructions

9. Functioning (Contd…) Replacing slow instructions with faster ones The following Java byteCode ... load 1 load 1 mul ... Can be replaced by ... load 1 dup mul ...

10. Functioning (Contd…) Removing redundant code Another example is to eliminate redundant load stores. a = b + c; d = a + e; is straightforwardly implemented as MOV b, R0 # Copy b to the register ADD c, R0 # Add c to the register, the register is now b+c MOV R0, a # Copy the register to a MOV a, R0 # Copy a to the register ADD e, R0 # Add e to the register, the register is now a+e [(b+c)+e] MOV R0, d # Copy the register to d

11. Functioning (Contd…) Removing redundant code but can be optimized to MOV b, R0 # Copy b to the register ADD c, R0 # Add c to the register, which is now b+c (a) MOV R0, a # Copy the register to a ADD e, R0 # Add e to the register, which is now b+c+e [(a)+e] MOV R0, d # Copy the register to d

12. Functioning (Contd…) Removing redundant stack instructions PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 POP HL POP DE POP BC POP AF PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR2 POP HL POP DE POP BC POP AF  PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 CALL _ADDR2 POP HL POP DE POP BC POP AF

13. Functioning (Contd…) Source Code: If ( a<b ) { a = a + b; } Peephole optimization of jumps Eliminate jumps to jumps Eliminate jumps after conditional branches “Adjacent” instructions = “Adjacent in control flow” IL Code: PUSH a PUSH b CMP a,b JUMP L1 EXIT L1: ADD a,b 

14. Other Considerations Control-flow operations Can clear simplifier’s window at branch or label More aggressive approach: combine across branches Same considerations arise with predication Physical versus logical windows Can run optimizer over a logical window Logical windows (within block) improve effectiveness

15. Conclusion So… Peephole optimization remains viable Post allocation improvements Cleans up rough edges Peephole technology works for selection Description driven matchers Used in several important systems All of this will work equally well in binary-to-binary translation

16. References https://en.wikipedia.org/wiki/Peephole_optimization http://www.iosrjournals.org/iosr-jce/papers/Vol9-Issue4/N0948086.pdf?id=255 https://class.coursera.org/compilers/lecture/76 https://www.slideshare.net/AnulChaudhary/peephole-optimization-techniques-in-compiler-design

17. That’s all Any Question