1. The Denotational Semantics of SSA
- Author
-
Ghalayini, Jad Elkhaleq and Krishnaswami, Neel
- Subjects
Computer Science - Programming Languages ,Computer Science - Logic in Computer Science ,F.3.2 ,D.3.4 ,D.3.1 - Abstract
Static single assignment form, or SSA, has been the dominant compiler intermediate representation for decades. In this paper, we give a type theory for a variant of SSA, including its equational theory, which are strong enough to validate a variety of control and data flow transformations. We also give a categorical semantics for SSA, and show that the type theory is sound and complete with respect to the categorical axiomatization. We demonstrate the utility of our model by exhibiting a variety of concrete models satisfying our axioms, including in particular a model of TSO weak memory. The correctness of the syntactic metatheory, as well as the completeness proof has been mechanized in the Lean proof assistant., Comment: 94 pages, 38 figures, mechanization available at https://github.com/imbrem/debruijn-ssa/tree/toplas-artifact
- Published
- 2024