Prophecy Variables, Program Analysis, Binding Times, and Staged Compilation in the BuildIt System
Ajay Brahmakshatriya, Saman Amarasinghe, Martin Rinard
cs.PL
Jan 6, 2026 · v3
TL;DR
Mechanizes the prophecy-variable reexecution formalism and its first- and second-stage correctness theorems in Lean 4, with a verified extension down to AArch64.
Abstract
BuildIt is a lightweight C++ library system for implementing domain specific languages (DSLs) and compilers through multi-stage execution. It uses partial evaluation to generate optimized code without requiring parsers, explicit intermediate representations (IRs), or custom code generators. History variables and forward execution support analyses of past computation, but optimizations such as data movement, operator fusion, and binding-time analysis also require information about future execution. We introduce prophecy variables into BuildIt to predict future program behavior and guide code generation. Repeated first-stage execution refines predictions until they satisfy the program's checks, extending BuildIt's existing reexecution machinery with little additional complexity. This approach obtains information typically computed by backwards dataflow analyses over an explicit IR while preserving BuildIt's lightweight implementation model. The cost of first-stage reexecution can be amortized over repeated executions of the generated code. We formalize the mechanism and mechanize its guarantees in Lean 4. We demonstrate prophecy variables in three applications: selective CPU-GPU data movement, neural-network operator fusion, and automatic binding-time analysis. These applications achieve performance improvements of up to 5.5x while simplifying the programming interface.
Problem
BuildIt, a lightweight C++ multi-stage library for building DSLs, has no explicit IR and so cannot run backwards dataflow analyses. Optimizations such as data movement, operator fusion and binding-time analysis need information about future execution.
Approach
Prophecy variables over lattices predict future program behavior. Repeated first-stage reexecution refines the predictions until they satisfy all checks. The mechanism is formalized for a core language with static, dynamic and prophecy variables, and its termination, least-upper-bound and correctness theorems are mechanized in Lean 4 with no sorry. A verified extension of about 7,700 lines and 425 theorems reaches down to an AArch64 machine model.
Results
Lean proofs establish that the first stage terminates and that it produces the least satisfying prophecy assignment with correct staged semantics. Three applications are demonstrated: CPU-GPU data movement, conv-ReLU fusion and automatic binding-time analysis. They achieve speedups of up to 5.5x.
| Size | Copy All | Unified Memory | Prophecy Enabled |
|---|
| 64x64 | 149 | 239 | 43 |
| 512x512 | 3053 | 1647 | 1059 |
| 4096x4096 | 380,378 | 316,443 | 307,830 |
Second-stage execution time for matrix multiply by data-movement strategy