Re: JavaMemoryModel: Dependences: [Fwd from Cliff]

From: Bill Pugh (
Date: Mon Aug 13 2001 - 11:46:31 EDT

Forwarded from Cliff.Click@Sun.COM, who is subscribed to the list
under -- Majordomo is very protective.

Bill Pugh wrote:
> At 8:48 PM -0700 8/12/01, Cliff Click wrote:
> >
> >I'd prefer you Don't Go There as it leads to a
> >nightmare of conflicting very slightly broken
> >implemenations.

Don't define the memory model semantics based on
control & data dependencies other than the textually
obvious ones. I.e., don't allow dependencies to
be removed (or added) based on a non-trivial
analysis (other than by the obvious AS-IF rule).

> I'm not quite sure what you mean by "Don't Go There". What is your
> reaction to my examples:
> At 12:39 PM -0400 8/12/01, Bill Pugh wrote:
> >* Does anyone disagree with my summary:
> > allow r1 = r2 = 1 in Example 1
> > prohibit r1 = r2 = -1 in Example 2.

I agree with them both, but I didn't like your
explanation for Example 2.

Assume a compiler that can analyze all possible thread
interleavings (with something more efficient than the
obvious exponential search) but it has to observe all
the standard intra-thread dependencies. The compiler
is allowed to generate code that can have observable
effects AS IF one or more of the thread interleavings
had occured (but perhaps not all possible interleavings
are possible!) and AS IF all intra-thread dependencies
have been honored. Example: quickest route to setting
y must have already read x in thread 1.

T1: r1 = x; r1 = x = y = 0; r2 = undef
T1: if( r1 >= 0 ) true
T1: y = -1; r1 = x = 0; r2 = undef; y = -1
T2: r2 = y; r1 = x = 0; r2 = y = -1
T2: x = r2; r1 = 0; r2 = x = y = -1

What I disagree with is the notion that a compiler can
first pick some thread interleaving, do some analysis,
remove some dependencies based on the AS-IF rule, then
pick a different thread interleaving in the new
optimized program and re-analyze or re-optimize. The
compiler will generate code that behaves AS-IF a
choosen set of the original program interleavings were


Cliff Click                  Compiler Designer and Researcher
cliffc at            Java Software
(408) 863-3266               MS UCUP02-302
JavaMemoryModel mailing list -

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