RE: JavaMemoryModel: Semantics musings

From: Boehm, Hans (hans_boehm@hp.com)
Date: Mon Sep 24 2001 - 20:29:05 EDT


> From: Keith Randall [mailto:randall@src.dec.com]
> You are right, most of the win comes from just eliminating
> instructions. For array bounds checks, you can eliminate not only the
> compare and branch, but possibly also the array length load and index
> calculation. On modern out-of-order processors, instruction
> scheduling normally doesn't buy you much.

It seems to me that this is likely to be highly architecture specific. Some
modern processors, notably Itanium (and SPARCs, as Cliff pointed out) issue
instructions in order, and are very sensitive to scheduling.

Isn't there also still the potential issue that if the semantics guarantees
the ordering due to the potential (but actually impossible) exception, you
need some sort of memory barrier instruction, which is likely to be
expensive on some architectures.
>
> Jan 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.
>
> A clarifying question about this semantics - consider the following
> program fragment:
>
> r1 = x
> r2 = x
> if (r1 == r2)
> y = 42
>
> Is "y = 42" allowed to be reordered across the control-flow boundary?
> On first reading, I thought it couldn't, because r1 and r2 may contain
> different values, depending on the behavior of other threads.
> However, in an implementation I'm always allowed to choose a subset of
> behaviors, and let me choose the subset that does both "r1 = x" and
> "r2 = x" atomically (otherwise known as redundant load elimination).
> This optimization requires no knowledge of the existence of other
> threads or their behavior. Am I now allowed to reorder "y = 42"
> across the control flow boundary?
>
> More generally, do I need to show that the write will occur in any
> execution, over ALL possible interleavings, or only the interleavings
> that might actually occur?
>
It seems to me it has to be the latter.

But while we're at it, can someone summarize how we got here? I'm having
trouble reconstructing the big picture from reading through recent messages.
Why do we need a control dependence to enforce an ordering in the semantics?
My intuition agrees with Cliff's: "Let's not go there."

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