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