[cpp-threads] Visible sequence of side effects and coherence requirements

[Alan Stern]

Given the coherence requirements expressed in D3196 ("New Paragraphs
Following 1.10.p13"), the definition of "visible sequence of side
effects" (VSSE) in 1.10.p13 is too broad.  That is, the VSSE on an
atomic object M with respect to a value computation B of M may include
side effects which could not possibly be the value determined by B.

For example, suppose that side effects A1 and A2 both modify M, where
A1 occurs before A2 in the modification order of M.  Further suppose
that A1 and A2 both happen before B, but neither happens before the
other.

Then the VSSE on M with respect to B includes both A1 and A2, because
A1 is visible with respect to B and B does not happen before either A1
or A2.  But the write-read coherence requirement for A2 and B does not
allow B to take its value from A1.  Hence A1 shouldn't be in the VSSE,
even though the current definition puts it there.

In short, although the current definition of VSSE is not incorrect, it
could be improved.  For instance, it might be stated as:

	The visible sequence of side effects on an atomic object M,
	with respect to a value computation B of M, is the contiguous
	sub-sequence of side effects in the modification order of M
	beginning with the last side effect that happens before B and
	continuing up to, but not including, the first side effect
	that B happens before, if any.

However I'm not going to advocate changing the definition of VSSE.  
Instead, I suggest removing the whole concept from the formal part of
the standard entirely!

The VSSE is defined solely for the purpose of this specification:

	The value of an atomic object M, as determined by evaluation
	B, shall be the value stored by some operation in the visible
	sequence of M with respect to B.

This does not need to be stated expicitly, because it follows directly
from the new coherence requirements.  Here's how:

Let X be the last side effect in the modification order of M that 
happens before B, let Y be the side effect from which B determines the 
value of M, and let Z the first side effect in the modification order 
of M that B happens before (if any).

The write-read coherence requirement, applied to X and B, states that Y
either is X or follows X in the modification order.  The read-write
coherence requirement, applied to B and Z, states that Y precedes Z in
the modification order.  Together these facts imply that Y belongs to
the maximal contiguous sub-sequence defined above (or the sub-sequence
defined as in 1.10.p13).

(As a special case, if Z doesn't exist then the only requirement is
that Y is X or follows X, again agreeing with the definition of the
VSSE.  If X doesn't exist then the behavior is undefined or
unspecified, because B could read an uninitialized value.)

This argument shows that the only reason for introducing the VSSE into
the standard has now been superseded.  Therefore I suggest that the
existing text of 1.10.p13 be removed completely, leaving only the new
coherence requirements.

Alan Stern