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
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:34 EDT