[LLVMdev] Reviving the new LLVM concurrency model

[Jeffrey Yasskin]

On Sun, Jul 31, 2011 at 5:22 PM, Jianzhou Zhao <jianzhou at seas.upenn.edu> wrote:
> On Sun, Jul 31, 2011 at 7:11 PM, Eli Friedman <eli.friedman at gmail.com> wrote:
>> On Sun, Jul 31, 2011 at 3:04 PM, Jianzhou Zhao <jianzhou at seas.upenn.edu> wrote:
>>> The current memory model section ends with the following discussions:
>>>
>>> "Note that in cases where none of the atomic intrinsics are used, this
>>> model places only one restriction on IR transformations on top of what
>>> is required for single-threaded execution: introducing a store to a
>>> byte which might not otherwise be stored to can introduce undefined
>>> behavior.... "
>>>
>>> Why is introducing additional loads allowed? For example, in a program
>>> that already contains two unordered stores to a location l, if we
>>> introduced an unordered load to l, then the load cannot see more than
>>> one stores, it must return undef.
>>
>> The intent of the model is that if the behavior of a program doesn't
>> depend on the value of a load, it's okay if it is undef.  This allows,
>> for example, hoisting loads which are conditionally executed out of
>> loops.
>
> In C++0x, if a program has a data race, then its behavior is
> undefined. Does the LLVM memory model design define programs'
> behaviors in the similar ideas? If so, hosting additional loads out of
> a loop that may not execute at runtime --- say the loop counter is 0,
> can turn a program from defined to undefined, which makes the later
> compilations transform the program arbitrarily, since their input
> programs are undefined. Is it expected? Although I am not sure if the
> existing LLVM transformations do so.

Hoisting loads out of non-executing loops is intended to preserve
defined behavior. This is intentionally different from the C++0x
memory model, along the lines that Hans Boehm suggested in
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html: "a
compiler that introduces a racing load at the machine code level, and
then discards the result of the load, generally will not have changed
the semantics of the program. … The author of C++ source code provides
an implicit promise to the compiler: There are no data races on
ordinary variables. This allows the compiler to safely perform some
common optimizations that would otherwise be invalid. If the compiler
itself introduces potentially racing loads in intermediate code, it
can, and has to, remember that these loads may race, and have to be
treated as such by subsequent optimizations."

In LLVM, we've decided to say that all loads may race rather than
tracking which loads were in the original source vs. were introduced
by optimizations. If that causes optimization problems in the future,
it could be revisited, but for now it provides a simpler model for the
IR.

>>> My second question is whether the "undefined behavior" in "...
>>> introducing a store to a byte which might not otherwise be stored to
>>> can introduce undefined behavior.... " is same to the ``undef'' in the
>>> definition of R_{byte} that can be undef in several cases. Does the
>>> undef mean the LLVM undef values
>>> (http://llvm.org/docs/LangRef.html#undefvalues)? If "undefined
>>> behavior" means a program can do anything, why does R_{byte}  have to
>>> return undef? Thanks.
>>
>> "can introduce undefined behavior", I meant "Specifically, in the case
>> where another thread might write to and read from an address,
>> introducing a store can change a load that may see exactly one write
>> into a load that may see multiple writes."  Any suggestion for how to
>> phrase that paragraph more clearly?
>
> Undefined behavior usually means any possible behavior is legal, while
> that a load returns undef (by the definition) because of seeing more
> than one writes is a much more precise behavior than undefined
> behavior. It helps to understanding the specification, if this point
> can be made more precisely, which is consistent with the discussion
> from
>  https://docs.google.com/View?docID=ddb4mhxz_24gh4ksvgh&revision=_latest