JavaMemoryModel: Dependences: a concrete example

From: Bill Pugh (
Date: Sun Aug 12 2001 - 12:39:02 EDT

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.

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

JavaMemoryModel mailing list -

This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:34 EDT