Formal Verification of Just-in-Time Compilation

Titre : Vérification Formelle de Compilation à la Volée

Résumé :

La compilation à la volée est une technique pour exécuter des programmes, où l'exécution est mélangée à des optimisations.
Les compilateurs à la volée se distinguent par leur efficacité, mais aussi par leur complexité.
Par exemple, ils réutilisent des techniques variées: certains contiennent des interprètes pour exécuter leur programme, mais aussi des compilateurs traditionnels pour générer du code machine optimisé.
Ils utilisent également des techniques qui leur sont propres comme la spéculation, qui consiste à prédire le comportement futur du programme et générer du code particulièrement rapide si cette prédiction s'avère vrai.

Cette grande complexité peut être à l'origine de bugs.
Cette thèse s'attelle à leur vérification formelle, dans le but de développer des compilateurs à la volée dont on peut prouver formellement qu'ils se comportent comme spécifié par la sémantique du programme qu'ils exécutent.
Nous présentons des preuves de correction des techniques principales qu'ils utilisent, comme la spéculation, les optimisations dynamiques ou la génération de code machine.
Nous réutilisons des techniques de preuves issues de compilateurs traditionnels vérifiés comme CompCert.
Nos preuves sont toutes vérifiées mécaniquement dans l'assistant de preuve Coq.

Mot clés : Vérification formelle, Compilation à la volée, Coq, CompCert

Formal Verification of Just-in-Time Compilation

Abstract:

Just-in-Time compilation is a technique to execute programs, where execution is interleaved with optimizations.
Just-in-Time compilers often produce fast executions, but are particularly complex.
For instance, they reuse various existing techniques: some contain both interpreters to execute programs and traditional compilers to generate optimized machine code.
They also use ad hoc techniques like speculation, which consists in predicting the future behavior of the program to generate specialized code that executes particularly fast if the prediction holds.

This great complexity can lead to bugs.
This thesis tackles their formal verification, to develop Just-in-Time compilers in such a way that one can formally prove that they behave as prescribed by the semantics of the program they execute.
We present correctness proofs for their main features, including speculation, dynamic optimizations and machine code generation.
We reuse proof techniques from formally verified traditional compilers like CompCert.
All our proofs have been mechanized in the Coq proof assistant.

Keywords: Formal Verification, Just-in-Time Compilation, Coq, CompCert