JavaMemoryModel: How relaxed should our memory model be?

From: Bill Pugh (pugh@cs.umd.edu)
Date: Fri Oct 05 2001 - 14:00:52 EDT


I'd like to try once again to come to some understanding on the
issues I've been raising over the past few weeks.

We've been trying to devise a denotational and executable semantics
for multithreaded Java that is as relaxed/weak as possible, with the
idea of allowing more compiler transformations.

Jan-Willem suggest not allowing the use of any information inferred
about the heap in reordering past potential control flow boundaries.

At 6:38 PM -0400 9/12/01, Jan-Willem Maessen wrote:
>2) A write may be reordered across a control flow boundary iff it can
> be shown that the particular write will occur in any execution,
> regardless of the existence or behavior of other threads in the
> system.

Consider the following example:

Initially, p = new Point(0,0), q = new Point(0,0);

Thread 1:
r1 = p
r2 = q
r3 = r1.x
r2.y = 1

Thread 2
r4 = p
r5 = q
r6 = r5.y
r4.x = 2

Can this program result in r3 = 2 and r6 = 1? If a VM determined that
reads of p and q never returned null, and thus the reads of r1.x and
r5.y could never throw an exception, it might decide to reorder the
last two statements in each thread. This reordering would allow the
result r3 = 1 and r6 = 2. But as far as I can tell, any semantics
that respected Jan-Willem's proposed rule (2) would make this
execution illegal. Therefore, any compiler analysis that inferred
that p and q always held non-null values could only be used with
great care.

At 8:48 PM -0700 8/12/01, Cliff Click wrote:
>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.

A weaker semantics is intended to provide more options for for
compiler writers. If you want to perform analysis/transformations
under a model where you make no assumptions/inferences about the
heap, you are perfectly free to do so. That will be completely legal.

I will admit that if you want to do compiler analysis that makes
inferences about the heap, it will be tricky. Among other things, you
will have to take into account the memory model. For example, in
proving that p and q are never null, you would have to prove that the
reads of p and q could not see the initial null values stored in
those variables.

On the other hand, if we argue that you can't make inferences about
the heap, it isn't clear we should be doing things like determining
that objects are thread local.

So life is hard. But a lot of people have been arguing for the
freedom to perform "all reasonable" compiler optimizations. Although
they may not be used or important now, I don't think we should be
ruling out large categories of seemingly reasonable compiler
optimizations.

For the example above, I believe r3 = 2 and r6 = 1 should be a legal execution.
Does anyone wish to argue that it should not?

        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:35 EDT