CompCert (ACM Software System Award 2021) is the first industrial-strength compiler with a mechanically checked proof of correctness. Yet, CompCert remains a moderately optimizing C compiler.
Indeed, some optimizations of ``\texttt{gcc~-O1}'' such as \emph{Lazy Code Motion} (LCM) or \emph{Strength Reduction} (SR) were still missing: developing these efficient optimizations together with their formal proofs remained a challenge.
Cyril Six et al. have developed efficient formally verified translation validators for certifying the results of superblock schedulers and peephole optimizations. We revisit and generalize their approach into a framework (integrated into CompCert) able to validate many more optimizations: an enhanced superblock scheduler, but also \emph{Dead Code Elimination} (DCE), \emph{Constant Propagation} (CP), and more noticeably, LCM and SR. In contrast to other approaches to translation validation, we co-design our untrusted optimizations and their validators. Our optimizations provide hints, in the forms of \emph{invariants} or \emph{CFG morphisms}, that help keep the formally verified validators both simple and efficient. Such designs seem applicable beyond CompCert.
Fri 27 OctDisplayed time zone: Lisbon change
14:00 - 15:30 | |||
14:00 18mTalk | Formally Verifying Optimizations with Block Simulations OOPSLA Léo Gourdin Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, Benjamin Bonneau Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, Sylvain Boulmé Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, David Monniaux Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, Alexandre Bérard Université Grenoble Alpes - CNRS - Grenoble INP - Verimag DOI Pre-print | ||
14:18 18mTalk | Back to Direct Style: Typed and Tight OOPSLA Marius Müller University of Tübingen, Philipp Schuster University of Tübingen, Jonathan Immanuel Brachthäuser University of Tübingen, Klaus Ostermann University of Tübingen DOI Pre-print | ||
14:36 18mTalk | Hardware-Aware Static Optimization of Hyperdimensional Computations OOPSLA DOI | ||
14:54 18mTalk | Rapid: Region-Based Pointer Disambiguation OOPSLA DOI | ||
15:12 18mTalk | Automated Ambiguity Detection in Layout-Sensitive Grammars OOPSLA Jiangyi Liu Tsinghua University, Fengmin Zhu CISPA - Helmholtz Center for Information Security, Fei He Tsinghua University DOI Pre-print |