Reference. Compositional optimizations for CertiCoq
Compositional compiler verification is a difficult problem that focuses on separate compilation of program components with possibly different verified compilers. Logical relations are widely used in proving correctness of program transformations in higher-order languages; however, they do not scale to compositional verification of multi-pass compilers due to their lack of transitivity. The only known technique to apply to compositional verification of multi-pass compilers for higher-order languages is parametric inter-language simulations (PILS), which is however significantly more complicated than traditional proof techniques for compiler correctness. In this paper, we present a novel verification framework for lightweight compositional compiler correctness . We demonstrate that by imposing the additional restriction that program components are compiled by pipelines that go through the same sequence of intermediate representations , logical relation proofs can be transitively composed in order to derive an end-to-end compositional specification for multi-pass compiler pipelines. Unlike traditional logical-relation frameworks, our framework supports divergence preservation—even when transformations reduce the number of program steps. We achieve this by parameterizing our logical relations with a pair of relational invariants . We apply this technique to verify a multi-pass, optimizing middle-end pipeline for CertiCoq, a compiler from Gallina (Coq’s specification language) to C. The pipeline optimizes and closure-converts an untyped functional intermediate language (ANF or CPS) to a subset of that language without nested functions, which can be easily code-generated to low-level languages. Notably, our pipeline performs more complex closure-allocation optimizations than the state of the art in verified compilation. Using our novel verification framework, we prove an end-to-end theorem for our pipeline that covers both termination and divergence and applies to whole-program and separate compilation, even when different modules are compiled with different optimizations. Our results are mechanized in the Coq proof assistant.
Cite
Cites 64 works (3 here)
With notes (3)
A logical relation for monadic encapsulation of state: proving contextual equivalences in the presence of runST timany-2017-a
We present a logical relations model of a higher-order functional programming language with impredicative polymorphism, recursive types, and a Haskell-style ST monad type with runST. We use our logical relations model to show that runST provides proper encapsulation of state, by showing that effectful computations encapsulated by runST are heap independent. Furthermore, we show that contextual refinements and equivalences that are expected to hold for pure computations do indeed hold in the presence of runST. This is the first time such relational results have been proven for a language with monadic encapsulation of state. We have formalized all the technical development and results in Coq.
CakeML: A verified implementation of ML kumar_cakeml_2014
We have developed and mechanically verified an ML system called CakeML, which supports a substantial subset of Standard ML. CakeML is implemented as an interactive read-eval-print loop (REPL) in x86-64 machine code. Our correctness theorem ensures that this REPL implementation prints only those results permitted by the semantics of CakeML. Our verification effort touches on a breadth of topics including lexing, parsing, type checking, incremental and dynamic compilation, garbage collection, arbitraryprecision arithmetic, and compiler bootstrapping.
Formal verification of a realistic compiler leroy_formal_2009
This paper reports on the development and formal verification (proof of semantic preservation) of CompCert, a compiler from Clight (a large subset of the C programming language) to PowerPC assembly code, using the Coq proof assistant both for programming the compiler and for proving its correctness. Such a verified compiler is useful in the context of critical software and its formal verification: the verification of the compiler guarantees that the safety properties proved on the source code hold for the executable compiled code as well.
External (61)
- Efficient and provable local capability revocation using uninitialized capabilities (2021)
- Compiling with continuations, correctly (2021)
- Verified Functional Algorithms (Software Foundations vol. 3), version 1.4 (2020)
- The OCaml system release 4.11 (2020)
- Formal verification of a constant-time preserving C compiler (2019)
- Selective Lambda Lifting (2019)
- Closure conversion is safe for space (2019)
- The next 700 compiler correctness theorems (functional pearl) (2019)
- CompCertM: CompCert with C-assembly linking and lightweight modular verification (2019)
- Coq Coq correct! verification of type checking and erasure for Coq, in Coq (2019)
- The verified CakeML compiler backend (2019)
- An abstract stack based approach to verified compositional compilation to machine code (2019)
- Certified Code Generation from CPS to C (2019)
- Œuf: minimizing the Coq extraction TCB (2018)
- CoqPL’17: The Third International Workshop on Coq for Programming Languages (2017)
- Compiling without continuations (2017)
- Verifying efficient function calls in CakeML (2017)
- Shrink fast correctly! (2017)
- Lightweight verification of separate compilation (2016)
- Functional Big-Step Semantics (2016)
- Proving Correctness of a Compiler Using Step-indexed Logical Relations (2016)
- A new verified compiler backend for CakeML (2016)
- Verification of a Cryptographic Primitive: SHA-256 (2015)
- Deep Specifications and Certified Abstraction Layers (2015)
- Pilsner: a compositionally verified compiler for a higher-order imperative language (2015)
- A Compositional Semantics for Verified Separate Compilation and Linking (2015)
- Compositional CompCert (2015)
- Parametric Bisimulations: A Logical Step Forward (2014)
- Verifying an Open Compiler Using Multi-language Semantics (2014)
- The marriage of bisimulations and Kripke logical relations (2012)
- Verified heap theorem prover by paramodulation (2012)
- A kripke logical relation between ML and assembly (2011)
- Separation logic + superposition calculus = heap theorem prover (2011)
- A verified compiler for an impure functional language (2010)
- Biorthogonality, step-indexing and compiler correctness (2009)
- A Formally Verified Compiler Back-end (2009)
- Coinductive big-step operational semantics (2009)
- Imperative self-adjusting computation (2008)
- Mechanized Verification of CPS Transformations (2007)
- Compiling with continuations, continued (2007)
- Operational semantics for multi-language programs (2007)
- Step-Indexed Syntactic Logical Relations for Recursive and Quantified Types (2006)
- Shrinking Reductions in SML.NET (2005)
- An indexed model of recursive types for foundational proof-carrying code (2001)
- Efficient and safe-for-space closure conversion (2000)
- Shrinking lambda expressions in linear time (1997)
- Compilation by transformation for non-strict functional languages (1995)
- Functional Programming, Glasgow (1994)
- Space-efficient closure representations (1994)
- The essence of compiling with continuations (1993)
- Compiling with Continuations (1992)
- Compilation of functional languages by program transformation (1991)
- Realistic compilation by program transformation (detailed summary) (1989)
- ORBIT: an optimizing compiler for scheme (1986)
- Lambda lifting: Transforming programs to recursive equations (1985)
- Super-Combinators: A New Implementation Method for Applicative Languages (1982)
- Register allocation via coloring. Computer languages, 6, 1 (1981)
- Rabbit: A Compiler for Scheme (1978)
- A data structure for manipulating priority queues (1978)
- Call-by-Name, Call-by-Value and the lambda-Calculus (1975)
- Programming Languages and Systems — ESOP ’96