[cpp-threads] Yet another visibility question

[Boehm, Hans]

So, could we say (in non-standardese) that if,

1) in an execution E in which x.load_raw() returns x1 in thread t1, the
nth subsequent store to y in t1 stores y1 to object o1, and

there exists an x2 such that

2) in no execution E' in which x.load_raw returns x2, but which agrees
with E on everything that happens-before or is sequenced-before the
load_raw, does the nth store to y store y1 to o1

then the nth subsequent store to y in t1 is dependent on the x.load_raw?

(This is starting to look a bit like the Java formulation ...)

Actually, I think that doesn't quite work.

In the example

r1 = x.load_raw();
if (r1) {
     y = 1;
}
y = 1;

It would declare the second store to y as dependent.  Somehow we need to
distinguish this example from

r1 = x.load_raw();
y = 1;
if (r1) {
     y = 1;
}

which should allow the first store to become visible before the
load_raw.  But this again seems fundamentally broken, since we've now
associated different behavior with program pieces that a normal
optimizer would consider equivalent, and which can be separated into a
different compilation unit from the load_raw().

If y is an ordinary variable, it might not matter, because both would
result in a race, as Peter points out.  But if we use atomic raw stores,
and we have per-variable TSO, I think they are observably different.
(If we use fetch_add_acquire instead of assignment, they clearly should
be different.)

So I'm still not sure how we progress along these lines.

> -----Original Message-----
> From: cpp-threads-bounces at decadentplace.org.uk 
> [mailto:cpp-threads-bounces at decadentplace.org.uk] On Behalf 
> Of Peter Dimov
> Sent: Wednesday, December 20, 2006 6:16 AM
> To: C++ threads standardisation
> Subject: Re: [cpp-threads] Yet another visibility question
> 
> Boehm, Hans wrote:
> 
> > If I have
> >
> > if (x.load_raw()) {
> >     y = 1;
> > }
> > y = 1;
> >
> > Is there a dependence?
> 
> To answer the question: yes, there is a dependence. Different 
> values of x can cause one of the two executions
> 
> y = 1;
> 
> or
> 
> y = 1;
> y = 1;
> 
> to take place. So the first store to y is dependent on the x 
> load. This variation is more subtle:
> 
> r1 = x.load_raw();
> 
> if( r1 )
> {
>     y = 1;
> }
> 
> if( !r1 )
> {
>     y = 1;
> }
> 
> assuming that the two ifs can be hidden away in function 
> calls. The store to y is not dependent.
> 
> The refcounting example doesn't have this problem; the 
> actions that are taken when the count drops to zero are 
> provably dependent since the result of the atomic is not 
> available to other portions of the code and can't cancel the 
> dependence.
That's not completely clear to me.  If one of the zero refcount actions
is to clear a field in the object, and that same field happens to be
cleared in the other case, could the compiler combine them and move them
up to before the decrement?

The argument would have to rely on other intervening synchronization
operations, I think.

> This relies on atomic loads being somewhat "volatile" 
> as far as data flow analysis is concerned, though. That is, 
> it relies on:
> 
> if( x.load_raw() )
> {
>     y = 1;
> }
> 
> if( !x.load_raw() )
> {
>     y = 1;
> }
> 
> not being equivalent to the above example, even if the 
> compiler can prove that x is not modified during the 
> execution of this snippet.
> 
> All this seems more trouble than it's worth. :-)
Does that mean that you agree we should forget about dependency-based
ordering and I should get back to figuring out how to prohibit just "out
of thin air" results?

> 
> 
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads
>