Safety of Program Transformations in Shared-memory Concurrency

50 views · Published 7 September 2016 · 1:05:01 · Indexed 30 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

Most programmers assume an interleaved semantics when reasoning about shared-memory concurrent programs. Unfortunately, even simple and widely implemented optimisations, such as constant propagation, violate the interleaved semantics. In this talk, I will argue that in absence of data races, interleaved semantics can be recovered for common classes of optimisations. My argument focuses on two classes of program transformations - eliminations and reorderings - which seem to explain most of the optimisations performed by realistic compilers.    The core of the proof technique is trace semantic: programs are viewed as sets of action traces and transformations as relations on tracesets.   This makes the proof largely independent of concrete language details.

More from this channel