2014 · 111 citations · 21 references
ComputingComputer ScienceCompilersFormal MethodsProgramming LanguagesAbstract Syntax TreesCompiler ConstructionControl-flow AnalysisData-flow AnalysisIntermediate RepresentationMemory Consistency ModelsCompiler DesignStandardsTransformations
We show that the weak memory model introduced by the 2011 C and C++ standards does not permit many common source-to-source program transformations (such as expression linearisation and "roach motel" reorderings) that modern compilers perform and that are deemed to be correct. As such it cannot be used to define the semantics of intermediate languages of compilers, as, for instance, LLVM aimed to. We consider a number of possible local fixes, some strengthening and some weakening the model. We evaluate the proposed fixes by determining which program transformations are valid with respect to each of the patched models. We provide formal Coq proofs of their correctness or counterexamples as appropriate.
21
Formal verification of a realistic compiler
Xavier Leroy · Communications of the ACM · 2009 · 1.1K citations
Jeremy Manson, William Pugh, Sarita V. Adve · 2005 · 732 citations · Full text
Jade Alglave, Luc Maranget, Michael Tautschnig · ACM Transactions on Programming Languages and Systems · 2014 · 335 citations · Full text
Mark Batty, Scott Owens, Susmit Sarkar et al. · 2011 · 267 citations