Re: JavaMemoryModel: Why I am resisting putting data/control dependences into the semantics

From: Victor Luchangco (
Date: Fri Aug 10 2001 - 11:03:02 EDT

> Can't we define control dependence along the lines of "if there is any
> possible execution of the program in which a statement is not
> executed, then it is dependent on the values of variables controlling
> whether it is executed". This needs some work to get exactly right,
> but offhand, it doesn't seem like that much work.

I agree with Bill that distinguishing control from data dependencies
is hard in general. Some refinement of this definition may work for
sequential programs, eliminating problems like the one Bill points out.
But in concurrent systems, the possible executions of the program
depend on the memory model. Consider the following pseudo-code:

x,y,z initially 0

  P1 P2

x = 1; wait until y == 1;
y = 1; if x == 1
                  ... = z

Under sequential consistency, z will always be read. A compiler that
assumes SC could then remove the conditional check. But under most
weak consistency models (including all JMM proposals), there are
executions in which z is not read. Does that operation depend on
the value for x?

I too would like to have a clean split between data and control
dependencies. I would prefer that this split not depend on the memory
model--that it should be derivable from the program structure. Adve
and Gharachorloo resolve this circularity by defining data
dependencies based only on sequentially consistent executions. In the
case above implies that the read of z does *not* depend on the value
of x, which is counter to my intuition. I don't know of any better
proposals though. Until I see one, I think it's best to leave any
distinction between data and control dependencies out of the memory
model defnition.

JavaMemoryModel mailing list -

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