A Case for an SC-Preserving Compiler
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2011), San Jose, CA, June 4-8, 2011.
Daniel Marino, Abhayendra Singh, Todd Millstein, Madanlal Musuvathi, Satish Narayanasamy
The most intuitive memory consistency model for shared-memory
multi-threaded programming is sequential consistency (SC). However,
current concurrent programming languages support a relaxed
model, as such relaxations are deemed necessary for enabling
important optimizations. This paper demonstrates that an
SC-preserving compiler, one that ensures that every SC behavior of
a compiler-generated binary is an SC behavior of the source program,
retains most of the performance benefits of an optimizing
compiler. The key observation is that a large class of optimizations
crucial for performance are either already SC-preserving or can be
modified to preserve SC while retaining much of their effectiveness.
An SC-preserving compiler, obtained by restricting the optimization
phases in LLVM, a state-of-the-art C/C++ compiler, incurs an
average slowdown of 3.8% and a maximum slowdown of 34% on
a set of 30 programs from the SPLASH-2, PARSEC, and SPEC
CINT2006 benchmark suites.
While the performance overhead of preserving SC in the compiler
is much less than previously assumed, it might still be unacceptable
for certain applications. We believe there are several avenues
for improving performance without giving up SC-preservation.
In this vein, we observe that the overhead of our SC-preserving compiler
arises mainly from its inability to aggressively perform a class
of optimizations we identify as eager-load optimizations. This class
includes common-subexpression elimination, constant propagation,
global value numbering, and common cases of loop-invariant code
motion. We propose a notion of interference checks in order to
enable eager-load optimizations while preserving SC. Interference
checks expose to the compiler a commonly used hardware speculation
mechanism that can efficiently detect whether a particular
variable has changed its value since last read.
[PDF | Implementation | Project Page]