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

From: Bill Pugh (
Date: Fri Aug 10 2001 - 11:32:20 EDT

At 11:03 AM -0400 8/10/01, Victor Luchangco wrote:
> > 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.

Actually, that wasn't my primary point.

I believe that neither data nor control dependences should be used in
defining the semantics, because it would be a circular definition.

For example:

x, y and z initially zero

T1 T2
r1 = x r3 = x
r2 = z r4 = y
y = 1 + r1*r2 z = 1 + r3*r4

Assume the compiler determines through some kind of global analysis
that x is always zero. Is it legal for the compiler to determine that
the writes to y and z are always 1 and perform those writes early,
allowing for an execution that sees r2 = r4 = 1?

Analysis can allow a compiler to eliminate a potential data
dependence through any number of mechanisms, including:
        * arithmetic identities
        * constant propagation
        * dead code elimination
        * alias analysis

Since the analysis depends on the semantics, allowing the semantics
to depend on data dependences introduces a circularity.

> Until I see one, I think it's best to leave any
>distinction between data and control dependencies out of the memory
>model defnition.

More importantly, I think we need to leave them out altogether.

JavaMemoryModel mailing list -

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