1# Peepholes 2## Overview 3**Peepholes** - optimizations which try to apply some small rules for instruction. 4## Rationality 5 6Reducing the number of instructions. 7 8## Dependence 9 10* RPO analyze. 11 12## Algorithm 13 14Visit all instructions in PRO order. 15 16For instruction tried to apply some rules. 17 18Peephole not remove instruction, it's only replace it on another and replace users on new instruction. 19 20### Rules 21This some of the rules: 22* Constant folding 23* Partial constant instruction replace by constant (a *= 0 -> a = 0) 24* Putting constant input on second place for commutative instructions (ex. Add, Mul, ...) 25* Grouping instructions (ex. b=a+2, c=b-4 -> c=a-2) 26* Remove redundant instructions (ex. b=a+0, b=a&1) 27* Replace instructions for equal but more cheap (ex. a*=4 - > a<<=2, b*=-1 -> b = -b ) 28* De Morgan rules for `and` and `or` instructions. 29*... 30## Pseudocode 31``` 32for (auto inst: All insts in RPO order) { 33 try to apply rules 34} 35``` 36## Examples 37Before peepholes: 38``` 391.i64 Parameter -> v6 // x 402.i64 Parameter -> v8 // y 413.i64 Constant -1 -> v10 // -1 424.i64 Constant 1 -> v6, v7 // 1 435.i64 Constant 2 -> v8 // 2 44 456. Add v1, v4 -> v7 // x+1 467. Add v6, v4 -> v9 // (x+1)+1 478. Mul v2, v5 -> v9 // y*2 489. Mul v7, v8 -> v10 // ((x+1)+1)*(y*2) 4910. Mul v9, v3 -> v11 // (((x+1)+1)*(y*2))*-1 5011. Return v10 51``` 52After peepholes: 53``` 541.i64 Parameter -> v6, v12 // x 552.i64 Parameter -> v8, v13 // y 563.i64 Constant -1 -> v10 // -1 574.i64 Constant 1 -> v6, v7 // 1 585.i64 Constant 2 -> v8, v12 // 2 59 60// (x+1)+1 -> x+2 616. Add v1, v4 // x+1 627. Add v6, v4 // (x+1)+1 6312.Add v1, v5 -> v9 // x+2 64 65//y*2 -> y + y 668. Mul v2, v5 // y*2 6713.Add v2, v2 -> v9 // y+y 68 699. Mul v12, v13 -> v14 // (x+2)*(y+y) 70 71// z*-1 -> -z 7210.Mul v9, v3 // (x+2)*(y+y)*(-1) 7314.Neg v9 -> v11 // -((x+2)*(y+y)) 74 7511.Return v14 76``` 77## Links 78[constant folding](constant_folding_doc.md) 79 80Source code: 81[peepholes.cpp](../optimizer/optimizations/peepholes.cpp) 82[peepholes.h](../optimizer/optimizations/peepholes.h) 83 84Tests: 85[peepholes_test.cpp](../tests/peepholes_test.cpp) 86 87