The Compcert back-end is a compiler that generates PowerPC assembly code from a low-level intermediate language called Cminor and a slightly more expressive intermediate language called Csharpminor. The particularity of this compiler is that it is written mostly within the specification language of the Coq proof assistant, and its correctness --- the fact that the generated assembly code is semantically equivalent to its source program --- was entirely proved within the Coq proof assistant.
A high-level overview of the Compcert back-end and its proof of correctness can be found in the following paper:
Xavier Leroy, Formal certification of a compiler back-end, or: programming a compiler with a proof assistant. Proceedings of the POPL 2006 symposium.This Web site gives a commented listing of the underlying Coq specifications and proofs. Proof scripts and the parts of the compiler written directly in Caml are omitted. This development is a work in progress; some parts may have changed since the overview paper above was written.
This document and all Coq source files referenced from it are copyright 2005, 2006 Institut National de Recherche en Informatique et en Automatique (INRIA) and distributed under the terms of the GNU General Public License version 2.
Coqlib.v
.)
Maps.v
.)
union_find.v
.)
AST.v
.)
Integers.v
.)
Pass | Source & target | Compiler code | Correctness proof |
---|---|---|---|
Recognition of operators and addressing modes | Csharpminor to Cminor | Cmconstr | Cmconstrproof |
Stack allocation of local variables whose address is taken |
Csharpminor to Cminor | Cminorgen | Cminorgenproof |
Construction of the CFG, 3-address code generation |
Cminor to RTL | RTLgen | RTLgenproof1 RTLgenproof |
Constant propagation | RTL to RTL | Constprop | Constpropproof |
Common subexpression elimination | RTL to RTL | CSE | CSEproof |
Register allocation by coloring of an interference graph |
RTL to LTL | Conventions InterfGraph Coloring Parallelmove Allocation |
Coloringproof Allocproof_aux Allocproof |
Branch tunneling | LTL to LTL | Tunneling | Tunnelingproof |
Linearization of the CFG | LTL to Linear | Linearize | Linearizeproof |
Laying out the activation records | Linear to Mach | Stacking | Stackingproof |
Storing the activation records in memory | Mach to Mach | (none) | Machabstr2mach |
Emission of PowerPC assembly | Mach to PPC | PPCgen | PPCgenproof1 PPCgenproof |