AliveInLean: A Verified LLVM Peephole Optimization Verifier

Juneyoung Lee, Chung-Kil Hur, Nuno P. Lopes

 

Abstract:


Ensuring that compiler optimizations are correct is important for the reliability of the entire software ecosystem, since all software is compiled. Alive is a tool for verifying LLVM's peephole optimizations. Since Alive was released, it has helped compiler developers proactively find dozens of bugs in LLVM, avoiding potentially hazardous miscompilations. Despite having verified many LLVM optimizations so far, Alive is itself not verified, which has led to at least once declaring an optimization correct when it was not.
We introduce AliveInLean, a formally verified peephole optimization verifier for LLVM. As the name suggests, AliveInLean is a reengineered version of Alive developed in the Lean theorem prover. Assuming that the proof obligations are correctly discharged by an SMT solver, AliveInLean gives the same level of correctness guarantees as state-of-the-art formal frameworks such as CompCert, Peek, and Vellvm, while inheriting the advantages of Alive (significantly more automation and easy adoption by compiler developers).

 

Published:

J. Lee, C. Hur, N. P. Lopes. AliveInLean: A Verified LLVM Peephole Optimization Verifier. In Proc. of the 31st International Conference on Computer-Aided Verification (CAV), July 2019.

 

Download:

 

Bibtex:

@inproceedings{aliveinlean-cav19,
  title =	{{AliveInLean}: A Verified {LLVM} Peephole Optimization Verifier},
  author =	{Juneyoung Lee and Chung-Kil Hur and Nuno P. Lopes},
  booktitle =	{Proc. of the 31st International Conference on Computer-Aided Verification (CAV)},
  doi =		{10.1007/978-3-030-25543-5_25},
  month =	jul,
  year =	2019
}

 

Copyright notice:

The final authenticated version is available online at https://doi.org/10.1007/978-3-030-25543-5_25.

 

<-- Return