Re: JavaMemoryModel: required reads and writes (was: The choice we need to make on test cases 5 and 10)

From: Joseph Bowbeer (jozart@csi.com)
Date: Sat Aug 02 2003 - 18:16:31 EDT


I'm not sure I made myself clear in the follow-up to Hans' message.

The question I was trying to raise is:

=> Are all compiler transformations that lead to allowed executions legal?

Asked another way, To what extent can prescient knowledge be used to "fix"
the outcome? Or must the races be run?

Take case 11, for example.

Knowing that x = 1 will occur, or simply knowing that r1 = r2 = r3 = r4 = 1
is an allowed outcome, can the compiler rewrite this case as:

T1:
r1 = 1
r2 = 1

T2:
r3 = 1
r4 = 1

( Then, as a final step, remove even these assignments, since they're not
used for anything? )

----- Original Message -----
From: "Joseph Bowbeer" <jozart@csi.com>
To: <javamemorymodel@cs.umd.edu>
Sent: Friday, August 01, 2003 8:24 PM
Subject: JavaMemoryModel: required reads and writes (was: The choice we need
to make on test cases 5 and 10)

I'm wondering what the current thinking is concerning required reads and
writes. (I don't see where this is specified in the most recent docs.)

Hans writes:

> On the other side, there's some argument that a compiler should,
> aside from introducing extra reads and writes, be allowed to make
> favorable scheduling assumptions when compiling synchronization-
> free code, i.e. effectively assume that there are no races. [...]
>
> If you buy that, the compiler, while compiling x = r3, could reason
> that since there is no synchronization, it's safe to assume that
> thread 3 gets scheduled first, and z will be one. Thus r3 can be
> assumed to be one, and hence x = r3 can be optimized to x = 1.
> But there is no rule against stupidly failing to optimize r3 = z in
> the same way.
>
> x = 1
> r3 = z
>

Extrapolating further, does the JMM force any of the threads in any of these
cases to do anything?

That is, is the following result allowed in every case?

  r1 = r2 = ... = rN = unassigned

----- Original Message -----
From: "Boehm, Hans" <hans_boehm@hp.com>
To: "'Bill Pugh'" <pugh@cs.umd.edu>; <javamemorymodel@cs.umd.edu>
Sent: Friday, August 01, 2003 4:44 PM
Subject: RE: JavaMemoryModel: The choice we need to make on test cases 5 and
10

I agree with Bill's and Jeremy's choices for all the test cases other than 5
and 10. (I even agree if A and B are initially zero in test case 6, as I
assume they were supposed to be. )

I don't really care very much about 5 and 10.

On one side, intuitively they should be disallowed for the reasons given in
the web page, and because it's harder to reason about some programs if they
are allowed. But I have a hard time coming up with a real program for which
it matters.

On the other side, there's some argument that a compiler should, aside from
introducing extra reads and writes, be allowed to make favorable scheduling
assumptions when compiling synchronization-free code, i.e. effectively
assume that there are no races. This is a bit of a generalization of the
rules about compiling synchronization free code in a single thread.

If you buy that, the compiler, while compiling x = r3, could reason that
since there is no synchronization, it's safe to assume that thread 3 gets
scheduled first, and z will be one. Thus r3 can be assumed to be one, and
hence x = r3 can be optimized to x = 1. There is no rule against stupidly
failing to optimize r3 = z in the same way. (Or perhaps it ends up getting
scheduled in some other context in which z is cheaper to load then the
constant one.) Thus we could conceivably justify transforming thread 4 to:

x = 1;
r3 = z;

which clearly makes the result possible.

As far as I'm concerned, the arguments in both directions are rather weak.
I'd be happy to decide based on simplicity of the model.

Hans

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



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