Modular, compositional, and executable formal semantics for LLVM IR
Open Access
- 19 August 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 5 (ICFP) , 1-30
Abstract
This paper presents a novel formal semantics, mechanized in Coq, for a large, sequential subset of the LLVM IR. In contrast to previous approaches, which use relationally-specified operational semantics, this new semantics is based on monadic interpretation of interaction trees, a structure that provides a more compositional approach to defining language semantics while retaining the ability to extract an executable interpreter. Our semantics handles many of the LLVM IR's non-trivial language features and is constructed modularly in terms of event handlers, including those that deal with nondeterminism in the specification. We show how this semantics admits compositional reasoning principles derived from the interaction trees equational theory of weak bisimulation, which we extend here to better deal with nondeterminism, and we use them to prove that the extracted reference interpreter faithfully refines the semantic model. We validate the correctness of the semantics by evaluating it on unit tests and LLVM IR programs generated by HELIX.Keywords
Funding Information
- ONR (00014-17-1-2930)
- NSF (1521539)
This publication has 48 references indexed in Scilit:
- Provably correct peephole optimizations with aliveACM SIGPLAN Notices, 2015
- A formal C memory model supporting integer-pointer casts2015
- CompCertTSOJournal of the ACM, 2013
- Pretty-Big-Step SemanticsLecture Notes in Computer Science, 2013
- Formalizing the LLVM intermediate representation for verified program transformationsACM SIGPLAN Notices, 2012
- Verified Software Toolchain2011
- An overview of the K semantic frameworkThe Journal of Logic and Algebraic Programming, 2010
- Formal verification of a realistic compilerCommunications of the ACM, 2009
- Coinductive big-step operational semanticsInformation and Computation, 2009
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991