> -----Original Message-----
> From: owner-javamemorymodel@cs.umd.edu
> [mailto:owner-javamemorymodel@cs.umd.edu]On Behalf Of Bill Pugh
> Sent: Monday, July 01, 2002 10:48 AM
> To: javamemorymodel@cs.umd.edu; jsr-133-eg@jcp.org
> Cc: Jeremy Manson
> Subject: JavaMemoryModel: JSR 133 Status report
>
>
> Sarita's "not out of thin air" proposal has the problem that it
> depends upon being able to statically determine when one statement is
> dependent upon another, without any reference to the memory model or
> semantics.
>
> For example, consider:
>
> Ex3
> Thread 1:
> r1 = x
> r2 = r1*r1 - r1 + 1
> y = r2
>
> Thread 2:
> r3 = y
> r4 = r4*r4 - r4 + 1
> x = r4
>
> Can this program result in r1 = r3 = 1?
>
> If the compiler performs an analysis that shows that x and y can only
> have the value 0 or 1, then the compiler can determine that r2 and r4
> are always 1, reorder the writes to x and y, and get the result r1 =
> r3 = 1.
This is a valid point although I wouldn't describe the problem in the same
way. Anyway, here's a simple solution. It requires explicitly defining the
term "execution," analogous to an implicit assumption made in the MansonPugh
model as well.
Define an execution as a set of instruction instances from the program,
including values read and written by the operands of the instruction
instances. We do not place any restrictions on these instruction instances
except that (1) a memory read should return the value of some write to the
same location in the execution, and (2) given the values returned by shared
memory reads in the execution, a correct uniprocessor should be able to
generate the set of instruction instances of any single thread.
Intuitively, the above represents all executions that could possibly occur
if the system were not constrained by a memory model and the uniprocessor
did not have faults. In other words, this can be viewed as the weakest
possible memory model we are willing to consider.
Now define the flow dependence relation (on instruction instances in an
execution), denoted fd, as follows: I fd J if:
- I fd K fd J for some K or
- J reads a value written by I, unless J writes the same value in all
possible executions (regardless of the value written by I). ("All possible
executions" is as defined above.)
An execution obeys the not-out-of-thin-air requirement if its flow
dependence relation is acyclic.
Explanation:
------------
The only difference from the previous proposal is a relaxation of the notion
of a flow dependence as follows. Intuitively, if we have:
I1: r1 = ...
I2: r2 = r1*r3
we would normally say I2 is flow dependent on I1 due to r1. However, if we
know that r1*r3 is independent of r1 in all cases (e.g., r3 is 0), then
there is no real flow dependence. The tricky part here is to formalize what
we mean by "all cases." The definition of an execution given above gives us
"all cases." We cannot use the memory model semantics to determine "all
cases" since that would introduce a circularity in the semantics. The idea,
therefore, is to use a broader class of executions, including anything that
could possibly happen on any hardware or with any compiler.
Going back to Bill's example, there is no longer a flow dependence between
the first two instructions of each thread and the compiler transformation is
legal.
Comments?
Sarita
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:40 EDT