← All papers
First page of Prophecy Variables, Program Analysis, Binding Times, and Staged Compilation in the BuildIt System

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
Mechanizes the prophecy-variable reexecution formalism and its first- and second-stage correctness theorems in Lean 4, with a verified extension down to AArch64.
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.

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.

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.

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.

SizeCopy AllUnified MemoryProphecy Enabled
64x6414923943
512x512305316471059
4096x4096380,378316,443307,830
Second-stage execution time for matrix multiply by data-movement strategy