In C, the order of evaluation of expressions is unspecified; further for expressions
that do not involve function calls, C semantics ensure that there
cannot be a data race between two evaluations that can proceed in
either order (or concurrently). We explore the
optimization opportunity enabled by these non-deterministic
expression evaluation semantics in C, and provide
a sound compile-time alias analysis to realize
the same.
Our algorithm is implemented as a part of the
Clang/LLVM infrastructure,
in a tool called {\em OOElala}.
Our experimental results demonstrate that
the untapped optimization opportunity is significant: code
patterns that enable such optimizations are
common; the enabled transformations can range from vectorization to
improved instruction selection and register allocation;
and the resulting speedups can be as high as 2.6x on already-optimized
code.