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

Cite as @paraskevopoulou-2021-compositional (helia, typst) · \cite{paraskevopoulou-2021-compositional} (LaTeX)
BibTeX
bibtex · 1 line
@article{paraskevopoulou-2021-compositional, title={Compositional optimizations for CertiCoq}, volume={5}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3473591}, DOI={10.1145/3473591}, number={ICFP}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Paraskevopoulou, Zoe and Li, John M. and Appel, Andrew W.}, year={2021}, month=Aug, pages={1–30} }
hayagriva YAML (typst)
yaml · 19 lines
paraskevopoulou-2021-compositional:
  type: article
  title: Compositional optimizations for CertiCoq
  author:
  - Paraskevopoulou, Zoe
  - Li, John M.
  - Appel, Andrew W.
  date: 2021-08
  page-range: 1-30
  url: http://dx.doi.org/10.1145/3473591
  serial-number:
    doi: 10.1145/3473591
    issn: 2475-1421
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: ICFP
    volume: 5
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.
PDF · DOI · pldb

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.
PDF · DOI · pldb

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.
DOI
External (61)
paraskevopoulou-2021-compositional reference entries/refs/paraskevopoulou-2021-compositional/paraskevopoulou-2021-compositional.hel