At 05:29 PM 09/24/2001, Boehm, Hans wrote:
> > 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."
I think what happened is that we started considering transformations that
depended on the set of possible threads that might exist in the
program. This got into a self-referential bind because if we know that
only Thread A and B might be looking at x, then what thread B might do
would depend on what thread A might do which in turn might depend on what
thread B might do, ....
My sense is that this is where Cliff doesn't want to go.
Put another way, the semantics of code is defined by the possible sequences
of memory actions it might perform in the presence of unknown, but possible
threads. A thread is possible if it executes code from the program. For
example, if no code sets x to a negative value, then the transformation can
assume that x is non-negative.
>Hans
>-------------------------------
>JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
-------------------------------
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