Peephole Optimization Example
2024-07-17
Example 1
‘1 + x’
Rewrite as ‘x + 1’
Pattern match ‘<var> + 1’ and replace by ‘inc(<var>)’
(Assuming that ‘inc(<var>)’ is somehow more efficient than ‘<var> + 1’)
Example 2
( x + y * z) * 0
Match ‘<expr> * 0’ and replace by 0.
Example 3
1 + 2
Match ‘<constant> + <constant>’ and replace by the value calculated at compile-time, in this case 3.
Decision Trees
In his Thesis, Cordy shows how to express such rewrites declaratively as trees, which he calls MISTs.
Such rewrites can be modernized using OhmJS, PEG, etc. PEGs, including OhmJS, perform parsing and backtracking, which is a major portion of what you need to write peephole optimizers. Once input has been parsed, you need to rewrite the matches. It is relatively simple to create little DSLs to handle the rewriting.
Normalization
Peepholers can be simplified by ensuring that input is normalized in some convenient way that reduces the number of edge cases.
For example, if an operand to ‘+’ or ‘*’ is a constant, ensure that the constant appears on the right hand side of the expression.
In essence, you only need text-to-text transpilation, which I call t2t[1]. A simple phrase rewriter is in the ‘fraze’ repository. The code in fraze transpiles a DSL to Common Lisp
https://github.com/guitarvydas/fraze
See Also
References: https://guitarvydas.github.io/2024/01/06/References.html
Blog: https://www.guitarvydas.github.io
Videos: https://www.youtube.com/@programmingsimplicity2980
Discord: https://discord.gg/65YZUh6Jpq
Leanpub: [WIP] https://leanpub.com/u/paul-tarvydas
Gumroad: https://tarvydas.gumroad.com
Twitter: @paul_tarvydas
Bibliography
[1] t2t from https://github.com/guitarvydas/t2t