[LLVMdev] Reviving the new LLVM concurrency model

[Eli Friedman]

On Mon, Aug 22, 2011 at 1:09 PM, Jianzhou Zhao <jianzhou at seas.upenn.edu> wrote:
> On Mon, Aug 22, 2011 at 3:02 PM, Eli Friedman <eli.friedman at gmail.com> wrote:
>> On Mon, Aug 22, 2011 at 11:17 AM, Jianzhou Zhao <jianzhou at seas.upenn.edu> wrote:
>>> On Mon, Aug 22, 2011 at 1:02 PM, Eli Friedman <eli.friedman at gmail.com> wrote:
>>>> On Mon, Aug 22, 2011 at 9:55 AM, Jianzhou Zhao <jianzhou at seas.upenn.edu> wrote:
>>>>> In the definition of 'monotonic' ordering,
>>>>> ... "If an address is written monotonically by one thread, and other
>>>>> threads monotonically read that address repeatedly, the other threads
>>>>> must eventually see the write"...
>>>>
>>>> It's supposed to mean that if you have a something like looks like a
>>>> spinloop with monotonic reads, it shouldn't spin forever if the value
>>>> changes.  I'll take another look at rewording that.
>>>>
>>>>> Does this mean if a thread does multi-writes monotonically, monotonic
>>>>> reads from other threads should see all of them? But intuitively, it
>>>>> seems to be fine for a read to ``miss'' some of the writes as long as
>>>>> the writes seen are monotonic in the sense that later reads should see
>>>>> the same write of earlier reads, or any write monotonically after the
>>>>> writes seen.
>>>>>
>>>>> In the case there is only one monotonic write, what does 'eventually'
>>>>> mean? Can we know a write must be seen when some condition holds, for
>>>>> example, a number of instructions executed, the thread that did the
>>>>> write executes a fence, ...?
>>>>>
>>>>> C++ memory model does not have ``unordered'', and "monotonic", but
>>>>> have "modification ordering" (is it same to the relaxed atomic
>>>>> variables the LLVM IR mentions?). If I am compiling C++ to LLVM, can
>>>>> all modification atomic be compiled to monotonic? And when should we
>>>>> use "unordered"?
>>>>
>>>> http://llvm.org/docs/Atomics.html is an attempt to make things much
>>>> more straightforward than the stuff in LangRef.
>>>
>>> This is cool.
>>>
>>> At the end of the "optimization outside atomic" section there are
>>> discussions about "returning undef". Is it the following correct?
>>> * a store/store data race in LLVM leads to undefined behaviors,
>>
>> What exactly is a store-store "race"?  That sounds wrong.
>>
>>> * a store/load data race does not result in undefined behavior, but
>>> the load returns undef
>>> * if two memory accesses are of data races, then at least one of them
>>> is NonAtomic.
>>
>> The model isn't really defined in terms of races, but these two sound
>> roughly correct.
>>
>>> My question is suppose a load L and a store S have a data race, and L
>>> runs earlier than S in an execution, L is well-ordered with earlier
>>> writes by happens-before, then at the point when L runs, but S has not
>>> run yet, should the L also return undef or what ever write it can see
>>> w/o races so far?
>>>
>>> Although non-synchronized writes from other threads may propagate to
>>> another thread in different orders, but the writes that a read from a
>>> different thread can see should have already executed before the read
>>> (in a global time). So in the above case, it seems fine to allow the
>>> load to return a 'defined' value. Is there any case that makes 'undef'
>>> possible?
>>
>> If there is a load and a store to the same address with no
>> happens-before relationship, the load returns undef.  "L runs earlier
>> than S in an execution" doesn't make sense; if the load and store
>> aren't atomic, the compiler is allowed to, for example, rematerialize
>> the load, so that it happens both before and after the store.
>
> I agree that if we consider all possible executions of the program,
> "L runs earlier
> than S in an execution" doesn't make sense, since L and S can run in any orders.
>
> My confusion was more about a concrete execution of the program. If
> the execution schedules S before L, then L is reasonable to return any
> values (at least the write from S, or the recent write happens before
> L), so undef is fine with me.
>
> If the execution runs L earlier than S, and L can only see one write
> till the point, can the L still return any value? L can return any
> value in term of the C++ DRF memory model because eventually the L has
> a data race with the future S, which makes the program behavior
> undefined--- so reading any value is a good behavior.
>
> At this case, LLVM only allows some particular behaviors--namely, the
> load can return any value, but returning a value that none earlier
> writes have does not seem to be consistent for the execution. Did I
> misunderstand any concept here?

For non-atomic loads, we don't guarantee that a load corresponds to a
single hardware memory access.  Fo example, a 64-bit load on x86-32
will generally be split. See also
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2176.html#undefined
.  Also,

-Eli