Search papers, labs, and topics across Lattice.
This paper addresses the limitations of modern optimizing compilers that utilize heuristic search algorithms, which can lead to suboptimal code performance and unpredictable compile times. By verifying performance and compile time properties of compiler passes, the authors present a proof-of-concept focused on inline expansion, employing a cost model that estimates instruction-cache performance. The results demonstrate semantic preservation of the inlining transformation alongside guarantees on monotonic improvement and convergence-time bounds, enhancing the reliability of compiler optimizations.
Verifying compiler optimizations can transform the reliability of code generation, ensuring both performance and predictable compile times.
Modern optimizing compilers rely on heuristic search algorithms for NP-hard optimization problems, which can result in poor generated-code performance and long or unpredictable compile times. These are considered bugs by users, but verified compilers rarely reason beyond semantic preservation. We propose verifying performance and compile time properties of compiler passes. As a proof-of-concept, we formulate inline expansion using a cost model estimating instruction-cache performance. We mechanize this in Rocq, prove semantic preservation of the inlining transformation, and verify the algorithm's monotone improvement, convergence-time bound, and performance bounds for intermediate and final solutions.
