Compilers routinely deal with such stuff. In your
example, you assume an analysis which isn't
monotonic, leading to a cycle in the obvious
implementation.
In a "real" analysis we'd force things to be
monotonic, probably by using a meet (or OR'ing)
operator: the guard can be true, which leads to
the guard being false so the guard is BOTH and
thus we cannot determine what the test does so we
can't float the write to y.
This all leads down a big black hole: you define
the memory semantics based on some reasonably
sane dataflow analysis. Now everybody has to do
analysis that's strictly weaker (so they don't
accidently remove a required dependence and float
things around illegally) OR do an exact analysis
to come up with the required dependencies, then
use the AS-IF rule and stronger analyses to try
and improve things by removing required dependencies
that do not lead to observable program behavior
changes.
I'd prefer you Don't Go There as it leads to a
nightmare of conflicting very slightly broken
implemenations.
Cliff
Bill Pugh wrote:
> Consider Example 1:
>
> Initially, x = y = 0
>
> Thread 1:
> r1 = x
> if r1 >= 0
> y = 1
>
> Thread 2:
> r2 = y
> x = r2
>
> Question: is it legal for this program to result in r1 = r2 = 1?
>
> In order for that to happen, the write y = 1 must be done before the
> read of x by thread 1. Is the write to y dependent on the read of x?
>
> If the compiler had performed some global analysis to determine that x
> was always non-negative, it could have replaced r1 >= 0 with true, and
> then reordered the read of x and write to y in thread 1.
>
> But consider the following Example 2:
>
> Initially, x = y = 0
>
> Thread 1:
> r1 = x
> if r1 >= 0
> y = -1
>
> Thread 2:
> r2 = y
> x = r2
>
> Now, if the compiler does not allow the reordering, the guard will
> always be true, which perhaps means that the write to y is not dependent
> upon the value read for x and the write can be performed early. However,
> if the write is performed early, then it is possible to get r1 = r2 = -1
> and have the guard be false. Which means the guard isn't always true,
> which means the write can't be done early; which means that is the guard
> is always true... (at this point, smoke should start coming out of the
> computer).
>
> Note: If you think the example is too contrived, consider if the guard
> were some run-time test mandated by the VM semantics: null-pointer test,
> checked-cast, bounds check or array store check. There will likely be a
> lot of work on global analysis to prove that those exceptions aren't
> thrown.
>
>
> Summary:
> I think the semantics need to allow r1 = r2 = 1 in Example 1 and
> prohibit r1 = r2 = -1 in Example 2.
>
> Questions for the mailing list:
>
> * Does anyone disagree with my summary:
> allow r1 = r2 = 1 in Example 1
> prohibit r1 = r2 = -1 in Example 2.
>
>
> * In the memory models that incorporate data/control dependences (e.g.,
> Location Consistency and CRF), how would these cases be handled?
>
>
>
> Bill
> -------------------------------
> JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:34 EDT