Mechanizing conventional SSA for a verified destruction with coalescing

Delphine Demange 1 Yon Fernandez de Retana 1
1 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Modern optimizing compilers rely on the Static Single Assignment (SSA) form to make optimizations fast and simpler to implement. From a semantic perspective, the SSA form is nowadays fairly well understood, as witnessed by recent advances in the field of formally verified compilers. The destruction of the SSA form, however, remains a difficult problem, even in a non-verified environment. In fact, the out-of-SSA transformation has been revisited, for correctness and performance issues, up until recently. Unsurprisingly, state-of-the-art compiler formalizations thus either completely ignore, only partially handle, or implement naively the SSA destruction. This paper reports on the implementation of such a destruction within a verified compiler. We formally define and prove the properties of the generation of Conventional SSA (CSSA) which make its destruction simple to implement and prove. Second, we implement and prove correct a coalescing destruction of CSSA, à la Boissinot et al., where variables can be coalesced according to a refined notion of interference. This formalization work extends the CompCertSSA compiler, whose correctness proof is mechanized in the Coq proof assistant. Our CSSA-based, coalescing destruction removes, on average , more than 99% of introduced copies, and leads to encouraging results concerning spilling during post-SSA register allocation.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download
Contributor : Yon Fernández de Retana <>
Submitted on : Friday, October 14, 2016 - 4:08:53 PM
Last modification on : Thursday, February 7, 2019 - 3:46:33 PM
Long-term archiving on : Saturday, February 4, 2017 - 12:30:20 AM


Files produced by the author(s)


  • HAL Id : hal-01378393, version 1


Delphine Demange, Yon Fernandez de Retana. Mechanizing conventional SSA for a verified destruction with coalescing. 25th International Conference on Compiler Construction, Mar 2016, Barcelona, Spain. ⟨hal-01378393⟩



Record views


Files downloads