Re: JavaMemoryModel: What's "control dependence" mean?

From: Jan-Willem Maessen (jmaessen@alum.mit.edu)
Date: Thu Sep 13 2001 - 16:02:20 EDT


I 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.

And Bill Pugh <pugh@cs.umd.edu> replied:
> OK, a very important point regarding control dependences:
>
> *** Any operation is control dependent upon all preceding operations
> that could throw an exception.

Yes.

> So your rule (2) makes illegal any analysis that uses non-local
> information to determine that an operation cannot throw an exception.

Nonsense. The only thing that could possibly be prohibited in
practice is _reordering_ based on this information; we wouldn't be
able to tell if we did all sorts of other transformations (like
removing exception handlers and exception points, eliding tests,
etc.). We can simplify as much as we like.

Rules (1) and (2) together actually seem to be a bit _more_ permissive
than your suggestion of a month or so ago... Was I misreading your
intention? Your mention of giving memory semantics only for
transformed programs left me bewildered, but your responses to other
messages seemed to indicate that you wanted to preserve observable
ordering even in the face of optimization.

That said, I think it's a bit naive to look for a memory semantics
independent of data and control dependency. Java has a fairly
well-defined semantics for both data and control dependency already;
the memory model must exist in that context. Is a particular
transformation legal? Only if it preserves legal behavior in the
overall system. A transformation isn't legal wrt data and control
dependency but somehow illegal wrt memory semantics; that's silly.

That said, my notion that "local is special" is born of the idea that
simple and useful local transformations _should_ be permitted as much
as possible---IF we can assert that another thread can't stomp in and
mess things up.

-Jan-Willem Maessen
jmaessen@mit.edu

PS - I've been working on a version of CRF that's a bit less
alias-sensitive as part of my non-JMM-related thesis work. It should
permit somewhat more aggressive reordering of reads if used in the CRF
JMM; the big difference is that references obtained through two different
names would be considered different even if they happened to alias.
Is this of interest? I've given scant thought to JMM consequences
right now.
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



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