Atomicity Refinement for Verified Compilation

Abstract : We consider the verified compilation of high-level managed languages like Java or C# whose intermediate representations provide support for shared-memory synchronization and automatic memory management. Our development is framed in the context of the Total Store Order relaxed memory model. Ensuring com-plier correctness is challenging because high-level actions are translated into sequences of non-atomic ac-tions with compiler-injected snippets of racy code; the behavior of this code depends not only on the actions of other threads, but also on out-of-order executions performed by the processor. A naïve proof of correctness would require reasoning over all possible thread interleavings. In this paper we propose a refinement-based proof methodology that precisely relates concurrent code expressed at different abstraction levels, cognizant throughout of the relaxed memory semantics of the underlying processor. Our technique allows the compiler writer to reason compositionally about the atomicity of low-level concurrent code used to implement man-aged services. We illustrate our approach with examples taken from the verification of a concurrent garbage collector.
Type de document :
Article dans une revue
ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2014, pp.30
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
Contributeur : David Pichardie <>
Soumis le : mercredi 28 janvier 2015 - 23:46:12
Dernière modification le : jeudi 15 novembre 2018 - 11:57:41


  • HAL Id : hal-01102435, version 1


Suresh Jagannathan, Vincent Laporte, Gustavo Petri, David Pichardie, Jan Vitek. Atomicity Refinement for Verified Compilation. ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2014, pp.30. 〈hal-01102435〉



Consultations de la notice