Re: JavaMemoryModel: Performing speculative writes ahead of loops that may not terminate

From: Bill Pugh (pugh@cs.umd.edu)
Date: Fri May 28 2004 - 13:34:58 EDT


Forwarded email from Ras Bodik on speculative writes:

An interesting question.

> The current JMM spec implies that x=1 must not be observed
> if the loop doesn't terminate (it has implied this
> for a long time; this isn't a recent change). And almost
> everyone in the discussion is absolutely convinced that this is
> the right answer.

I am not a JMM expert, but I side with the majority. 

  In fact, it seems clear that x=1 should not be observed prior to the
loop
  even if the loop _does_ terminate (because the loop may be a
  synchronization).  But you guys know this better than I do.

> However, there is some question as to whether or not
> there might be any compilers that would violate this.

In principle, there might be a compiler that violates this
restriction.  If
  several conditions are met, what you suggested is a legal
transformation:

        Condition 1: As far as I can tell, in any code that's
guaranteed to
  run only in a single-threaded environment (which some compiler may
assume),
  moving x:=1 prior to the loop is semantically harmless. 

  AND

        Condition 2: This "code motion" is semantics preserving only if
the
  compiler can prove that x:=1 doesn't raise an exception, such a page
fault;
  because otherwise the optimized program may raise an exception when the
  original program wouldn't.  If the compiler cannot prove this, it may
be
  able to delay such an exception to the original point of x:=1 (various
VLIW
  processors proposed such instructions.)

To put Cliff's example into this context, his very nice example assumes
  multiple threads.

> Does anyone know if any compiler analysis or transformation
> might make this transformation? For example, if an analysis
> assumed "the only way to exit this loop is to take this
> branch, so this branch must be taken in all executions",
> then it might allow such a transformation.

I can think of one optimization that may perform this powerful code
motion:
  Region Scheduling by Gupta and Soffa.   The "region" here is a program
  dependence graph region; the regions before and after the loop are
control
  equivalent, there are no data dependences, and so x:=1 may be
movable.  Not
sure though, if the move across loops.

On an "inverse" theme, if you are concerned about moving x:=1 from
before
  the to after the loop, then partial dead code elimination is an
optimization
  that may perform this code motion, which may also be illegal in a
  multithreaded environment.

I don't know (personally) of any compiler that implements either of 
these
  two transformations so I don't know whether and how they ensure
correctness
  for multi-threaded code.

To conclude, I don't know of any compiler that does what you asked
about but
  I wouldn't be surprised if there was one.

--Ras

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



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