Catatan episode
This episode examines "Verifying Peephole Rewriting In SSA Compiler IRs," which uses the Lean proof assistant to give MLIR-style compilers a push-button workflow for proving small rewrites correct, without the cost of a fully verified compiler. It explains peephole rewrites and why SSA def-use chains let a matcher catch patterns that straight-line matching misses. It then compares the approach with Alive and Alive2, which rely on SMT solvers, and with CompCert-style end-to-end verification, which takes years of expert effort and is tied to one IR. The discussion covers MLIR dialects and regions, and why a ring-aware prover helps for domains like fully homomorphic encryption, where an algebraically trivial rewrite becomes a heroic proof at the LLVM level. It also covers refinement semantics with poison and undefined behavior. The episode adds a caveat from Csmith's results: proving local rewrites correct does not cover bugs in parsing, lowering, or pass ordering. Listeners get a clear picture of where formal compiler verification can reach into new domain-specific IRs and where it stops.
Sources:
1. Verifying Peephole Rewriting In SSA Compiler IRs — Siddharth Bhat, Alex Keizer, Chris Hughes, Andrés Goens, Tobias Grosser, 2024
http://arxiv.org/abs/2407.03685
2. Peephole Optimization — William M. McKeeman, 1965
https://scholar.google.com/scholar?q=Peephole+Optimization
3. Provably Correct Peephole Optimizations with Alive — Nuno P. Lopes, David Menendez, Santosh Nagarakatte, John Regehr, 2015
https://scholar.google.com/scholar?q=Provably+Correct+Peephole+Optimizations+with+Alive
4. Alive2: Bounded Translation Validation for LLVM — Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur, Zhengyang Liu, John Regehr, 2021
https://scholar.google.com/scholar?q=Alive2%3A+Bounded+Translation+Validation+for+LLVM
5. Verified Peephole Optimizations for CompCert — Eric Mullen, Daryl Zuniga, Zachary Tatlock, Dan Grossman, 2016
https://scholar.google.com/scholar?q=Verified+Peephole+Optimizations+for+CompCert
6. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation — Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, Oleksandr Zinenko, 2021
https://scholar.google.com/scholar?q=MLIR%3A+Scaling+Compiler+Infrastructure+for+Domain+Specific+Computation
7. Static Single Assignment Form and the Control Dependence Graph — Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck, 1991
https://scholar.google.com/scholar?q=Static+Single+Assignment+Form+and+the+Control+Dependence+Graph
8. Compiling Lean programs with MLIR / LEAN to MLIR (lz and lean-mlir) — Siddharth Bhat, Tobias Grosser and collaborators, 2022
https://scholar.google.com/scholar?q=Compiling+Lean+programs+with+MLIR+%2F+LEAN+to+MLIR+%28lz+and+lean-mlir%29
9. Verifying Peephole Rewriting In SSA Compiler IRs — Siddharth Bhat, Alex Keizer, Chris Hughes, Andrés Goens, Tobias Grosser…

