Compiling by Proving: Language-Agnostic Automatic Optimization from Formal Semantics
Preprint
Abstract
Verification proofs encode complete program behavior, yet we discard them after checking correctness. We present compiling by proving, a paradigm that transforms these proofs into optimized execution rules. By constructing All-Path Reachability Proofs through symbolic execution and compiling their graph structure, we consolidate many semantic rewrites into single rules while preserving correctness by construction. We implement this as a language-agnostic extension to the K framework. Evaluation demonstrates performance improvements across different compilation scopes: opcode-level optimizations show consistent speedups, while whole-program compilation achieves orders of magnitude greater performance gains.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Modular, compositional, and executable formal semantics for LLVM IRProceedings of the ACM on Programming Languages, 2021
- The Lean 4 Theorem Prover and Programming Language2021
- Matching logic explainedJournal of Logical and Algebraic Methods in Programming, 2021
- Dependent types and multi-monadic effects in F*2016
- A positive supercompilerJournal of Functional Programming, 1996