TL;DR
This paper presents a novel, lightweight approach to formally verify the correctness of separate compilation for the CompCert compiler. By recasting compositional verification in terms of whole-program compilation, they significantly simplify the proof effort, enabling them to reuse existing verification machinery and achieve the first verified separate compilation for the full CompCert compiler with minimal effort.
What Problem Does This Paper Address?
The CompCert project has achieved a significant milestone by providing a formally verified compiler, guaranteeing that the generated machine code behaves as prescribed by the source program's semantics. However, this verification has traditionally focused on whole-program compilation, meaning it only proves correctness when an entire C program is compiled at once. This is a significant limitation because, in practice, developers often compile modules separately and then link them. Ensuring that this separate compilation and subsequent linking process preserves program semantics is crucial for building reliable software. Previous attempts to address this "compositional compiler correctness" have often involved complex techniques and substantial modifications to existing compiler verifications. This paper aims to bridge this gap by developing a simpler, more lightweight method to verify separate compilation, specifically for a single compiler, by leveraging existing whole-program verification efforts.
Methods
The core contribution of this paper lies in developing two levels of lightweight techniques for verifying separate compilation:
- Level A: Compositional Correctness (Same Compiler): This level verifies that linking modules compiled with the exact same compiler preserves semantics. The key idea is to formulate a "contextual" correctness statement for a single module. This statement asserts that the module's behavior, when linked with arbitrary other modules, is sound. This contextual statement can then be proven using the familiar "closed simulation" style proofs used for whole-program compilation, allowing significant reuse of existing proofs. Many compiler passes naturally commute with linking, making their verification trivial. For non-trivial passes, the authors adapt existing simulation relations, primarily by ensuring that program analyses remain sound even when operating on a single module rather than the entire program.
- Level B: Compositional Correctness (Modulo Optimizations): This level strengthens Level A by allowing modules to be compiled with the same compiler but different optimization flags. The approach here is similar, but for RTL-to-RTL optimization passes, the verification involves proving that each pass, when applied to one module, simulates the identity transformation on other modules. This is achieved by adapting simulation relations to handle contexts where some modules are transformed and others are not. The authors found that much of the required proof effort was already present in the original CompCert verification, related to proving that individual instructions simulate themselves.
Datasets
Not discussed in the paper. The paper focuses on adapting the verification of an existing compiler (CompCert) rather than using external datasets for evaluation.
Key Insights and Ideas
- "Aiming lower" simplifies verification: By restricting the scope to verifying separate compilation for a single compiler (rather than multiple different compilers), the authors achieve significant simplification.
- Recasting compositional verification: The core innovation is to reformulate compositional correctness in terms of whole-program compilation, allowing the reuse of existing, well-understood proof techniques.
- Leveraging existing invariants: The lightweight nature of the approach stems from the ability to largely reuse the simulation invariants developed for the original whole-program verification of CompCert, rather than inventing entirely new ones.
- Monotonicity is key: For program analyses within the compiler, proving their monotonicity with respect to linking (i.e., they become more precise or equally precise when given more context) is crucial for establishing compositional correctness.
- Bugs hidden in plain sight: The process of adapting the verification uncovered two bugs in CompCert 2.4, one in an invalid axiom and another in the value analysis related to
extern constdeclarations, which only manifested with separate compilation.
Key Results
- SepCompCert: The authors successfully developed SepCompCert, the first verification of separate compilation for the full CompCert compiler.
- Minimal proof effort: The adaptation of CompCert 2.4 to support both Level A and Level B compositional correctness took less than two person-months.
- Small verification overhead: The resulting SepCompCert verification is only slightly larger than the original CompCert verification: 0.2% and 1.6% increase in lines of code for Level A (compiler & verification) and 0.2% and 2.8% for Level B, respectively.
- Two compiler bugs found and fixed: The verification process identified and led to the fixing of two bugs in CompCert 2.4.
Limitations and Future Work
- Scope of correctness: The current work verifies separate compilation for a single compiler. Extending this to support linking modules compiled by different verified compilers would require more advanced techniques.
- Syntactic linking: The current work relies on a specific definition of syntactic linking. Future work might need to revisit this definition, especially with the introduction of features like static variables in newer CompCert versions.
- Language generality: While the techniques are believed to be generally applicable, their application to other verified compilers (like CakeML) would require defining appropriate notions of separate compilation and linking for those languages.
- Machine code level: CompCert verifies compilation down to assembly. Extending this to machine code and the actual linking process performed by tools like
gccis outside the scope of this work.
Summary updated