Mon 16 Jan 2023 15:07 - 15:30 at Studio 1 - Languages and Compilers Chair(s): Cody Roux

Our objective is to formally verify the correctness of the hundreds of expression optimization rules used within the GraalVM compiler. When defining the semantics of a programming language, expressions naturally form abstract syntax trees, or, terms. However, in order to facilitate sharing of common subexpressions, modern compilers represent expressions as term graphs. Defining the semantics of term graphs is more complicated than defining the semantics of their equivalent term representations. More significantly, defining optimizations directly on term graphs and proving semantics preservation is considerably more complicated than on the equivalent term representations. On terms, optimizations can be expressed as conditional term rewriting rules, and proofs that the rewrites are semantics preserving are relatively straightforward. In this paper, we explore an approach to using term rewrites to verify term graph transformations of optimizations within the GraalVM compiler. This approach significantly reduces the overall verification effort and allows for simpler encoding of optimization rules.

Mon 16 Jan

Displayed time zone: Eastern Time (US & Canada) change

14:00 - 15:30
Languages and CompilersCPP at Studio 1
Chair(s): Cody Roux AWS
14:00
22m
Talk
A First Complete Algorithm for Real Quantifier Elimination in Isabelle/HOL
CPP
Katherine Kosaian Carnegie Mellon University, Yong Kiam Tan Carnegie Mellon University, André Platzer Karlsruhe Institute of Technology
14:22
22m
Talk
P4Cub: A Little Language for Big Routers
CPP
Rudy Peterson Cornell University, Eric Campbell Cornell University, John Chen Cornell University, Natalie Isak Microsoft, Calvin Shyu Cornell University, Ryan Doenges Cornell University, Parsia Ataei Cornell University, Nate Foster Cornell University
14:45
22m
Talk
ASN1*: Provably Correct, Non-Malleable Parsing for ASN.1 DER
CPP
Haobin Ni Cornell University, Antoine Delignat-Lavaud Microsoft Research, n.n., Cédric Fournet Microsoft Research, Tahina Ramananandro Microsoft Research, Nikhil Swamy Microsoft Research
15:07
22m
Talk
Verifying term graph optimizations using Isabelle/HOL
CPP
Brae J. Webb The University of Queensland, Ian J. Hayes The University of Queensland, Mark Utting The University of Queensland