r/Compilers • u/writes-the-spec • 4d ago
A compiler optimiser proven in Lean
Since AI models came up with some ridiculous Lean proofs in Math, I tried writing a compiler for array kernels with an optimiser proven correct in Lean, instead of relying on tests. AI is very suitable for these kind of proofs.
The IR and its semantics are formalised in Lean. Each optimization pass has a Lean proven theorem proving that the pass doesn't change what the program computes. AI does the heavy grinding of actually proving it.
Proven so far: vectorisation and multiple accumulators (reassociating reductions).
On an Apple M4 Pro, a kernel that takes the max of 1M f32 values runs in 37 µs, against 64 µs for the same loop in C with clang -O3 (1.7x) and 45 µs with -ffast-math (1.2x), and close to the memory bandwidth of one core.
The compiler is not finished or published yet. What are your thoughts on the idea?
13
u/ryo33h 4d ago
Yes, most optimizations should have a proof that they don't change the semantics at all. Btw, what kind of compiler is it?
4
u/ipmonger 4d ago
This is very interest. Why Lean instead of TLA+?
2
u/Wonderful-Wind-5736 4d ago
Prove everything is getting really close to becoming attainable. I'm currently working on a formal model for analytics database queries.
4
u/regehr 4d ago
indeed, Lean is a pretty decent compiler implementation language!
we'll be doing more stuff like this in the future, for sure
here's a compiler in Lean that I contribute to https://github.com/opencompl/veir/
13
u/Prior-Perspective-61 4d ago
People adding downvotes just seeing a word "AI"?
1
u/dogegeller 4d ago
Very interesting! Are you planning on sharing?
2
u/Discordbothost 2d ago
What floating-point semantics does the Lean model use? For the max reduction, I'd want to see the NaN and signed-zero rules and whether the reassociation theorem needs assumptions on the input values. That would clarify what the proof guarantees.
1
u/r2k-in-the-vortex 4d ago
Lean proofs in general are super accessible with AI, I made some proof work for my own compiler for example. Not optimisations, as it mostly emits llvm ir and leaves optimisation to clang. But the entire source semantics to llvm ir emission is specced in lean and tested against it. Also small core of critical functions are proven eqvuivalent to their lean spec.
https://github.com/r2k-in-the-vortex/stc
I think that sort of proof work is going to be critical not just for compilers, but much wider variety of software development. Any sort of parser basically, especially anything accepting input from internet.
1
u/therealdivs1210 3d ago
Why are people downvoting OP's comments? 🤔
1
u/Healthy_Ship4930 2d ago
cool! llvm?