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

From: Jerry Schwarz (
Date: Thu Sep 13 2001 - 19:09:11 EDT

At 07:23 AM 09/13/2001, Bill Pugh wrote:
>At 6:38 PM -0400 9/12/01, Jan-Willem Maessen 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.
>OK, a very important point regarding control dependences:
>*** Any operation is control dependent upon all preceding operations
> that could throw an exception.
>So your rule (2) makes illegal any analysis that uses non-local
>information to determine that an operation cannot throw an exception.

 From my naive perspective I think the only kinds of analysis that needs to
be disallowed to deal with the example are those that depend on the exact
list of threads that exist. Implicit in the example is the assumption that
the two threads are the only ones that can modify x.

Put another way, the transformation Bill is asking about is not a
transformation of the methods used by Thread 1, but of the code that
created Thread 1 and Thread 2 in which it replaces the Class(es)
implementing the threads by "equivalent" classes.

Example 1 (repeated for clarity)
  Initially, x = y = 0
  Thread 1:
   r1 = x
   if r1 >= 0
   y = 1
  Thread 2:
   r2 = y
   x = r2

>For example:

None of these analyses depend on knowing what threads exist, so none need
to be ruled out.

>* Analysis to determine that a heap variable is always non-null, and thus
> dereferencing the value loaded from that variable never throws a
> null-pointer
> exception.
>* Non-local analysis to determine that an array reference is in bounds. For
> example,
> "Related Field Analysis", Aneesh Aggarwal and Keith H. Randall, 2001
> ACM SIGPLAN Conference on Programming Language Design and
> Implementation
> (PLDI'01) Snowbird, Utah, June 20 - 22, 2001.
>* Analysis that proves that a checked check never throws an exception. For
> example, people have talked about being able to prove that the checked
> casts
> inserted by GJ are safe and removing them.
>Now of course, there are lots of hurdles to deal with as regards these
>kinds of analysis, such as how do you deal with reflection. However, I am
>rather uneasy about declaring these kinds of analysis to be fundamentally
> Bill
>JavaMemoryModel mailing list -

JavaMemoryModel mailing list -

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