As we've discussed before, Coherence prohibits reads of the same variable
by the same thread seeing a new value, and then an old value. Requiring
that the spec enforce Coherence means that reads kill. All current VM's
that do any optimization violate Coherence, and there had seemed to be
general agreement that we should drop Coherence.
However, consider the following single-check idiom example:
int v;
int getValue() {
if (v != 0)
v = computeValue();
return v;
}
Assume that computeValue has no side-effects, and always returns the same
non-zero value.
Now, if we drop Coherence, the following could happen:
Thread 1 invokes getValue, resulting in a call to computeValue and a store
into v. Then thread 2 invokes getValue. It reads v twice: When it reads it
the first time, in the if statement, it sees the non-zero value set by
thread 1. When it reads it the second time, in the return statement, it
reads the initial zero value. As a result, the function returns zero.
Oops. That means that even simple single-check idioms don't work.
Now we could fix it by writing it as:
int v;
int getValue() {
int tmp = v;
if (tmp != 0)
tmp = v = computeValue();
return tmp;
}
But that coding style is ugly, and it would be nice if we weren't force to
write code that way. Secondly, it would normally be a legal (although
dubious) compiler transformation to use forward substitution to transform
the second version of getValue into the first. Now, that becomes illegal.
OK, now we have a couple of choices. I've ordered these from least
constrained to most constrained.
-----
1) Go beyond dropping coherence. Right now, my proposal (and others) say
that the value returned by a read is non-deterministic, but that some
specific value is returned by each read. An alternative is to say that
"quantum wave function" of the non determinism doesn't collapse at the
read. In order words, if a read could return 0 or 1, then it doesn't return
either a zero or a one. Instead, it returns a value that is both a zero and
a one.
2) Stick with the proposal to drop Coherence. This means that a lot of
idioms for avoid synchronization become littered with land mines, and also
that there are tricky new requirements for compiler/jit transformations.
3) Retain only a weaken form of coherence, that says it is legal to reorder
reads of the same value only if they are refereed to by different names. Of
course, defining this correctly could be very hard, create substantial new
difficulties for compiler writers and make it difficult/impossible for
programmers to understand when an idiom is guaranteed to work and when it
isn't.
4) Retain coherence. This makes life pure hell for compiler writers
(phi-nodes for reads - yuck!), and will impose substantial performance
penalties.
-----
On the surface, I suspect that (3) may seem the most attractive on the
surface, so let me show some of the complications under the surface of (3).
First, any compiler transformation that could cause two references using
the same name to be consider as being referred to by two names would be
illegal. Also, consider the following example:
use x
use x+y // save x+y in register
use x+y // reuse value in register
use x+y // reuse value in register
use x // not available in register, reload
use x+y // reuse value in register
In this example, the common subexpression x+y has been kept in a register.
But for whatever reason (not enough registers?), we don't also keep x in a
register and have to reload it in the second to last statement.
But this would be illegal under (3), because we might see a new value for x
on the second to last statement, and (in the value of x+y) the old value in
the last statement. Thus, a read becomes a kill for partial
redundancy/common subexpression elimination.
Bill
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:21 EDT