**Next message:**Bill Pugh: "JavaMemoryModel: We need your litmus tests"**Previous message:**Richard Jones: "Re: JavaMemoryModel: What's "control dependence" mean?"**In reply to:**Clifford Click: "Re: JavaMemoryModel: What's "control dependence" mean?"**Next in thread:**Bill Pugh: "Re: JavaMemoryModel: What's "control dependence" mean?"**Reply:**Bill Pugh: "Re: JavaMemoryModel: What's "control dependence" mean?"**Reply:**Clifford Click: "Re: JavaMemoryModel: What's "control dependence" mean?"**Reply:**Roly Perera: "RE: JavaMemoryModel: What's "control dependence" mean?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Mail actions:**[ respond to this message ] [ mail a new topic ]

At 11:04 AM -0700 9/14/01, Clifford Click wrote:

*>I certainly agree with Jan that we need a semantics independent of
*

*>optimizations.
*

I'm sorry, but that is completely impossible. Semantics define the

set of allowed transformations/optimizations. They cannot be

independent.

For example, here are two transformations everyone would like to

allow: forward substitution and redundant load elimination.

If you make prescient writes dependent upon only local information,

those transformations are illegal.

Example 1: redundant load elimination is illegal:

Initially:

x = 0 and y = 1

Thread 1:

r1 = x

r2 = x

if (r1 == r2)

y = 2

Thread 2:

r3 = y

x = r3

The write y=2 cannot be done early; you can't determine if the write

will always occur from purely thread local information. This

disallows the result r1 = r2 = r3 = 2

However, if you perform redundant load elimination you get:

Initially:

x = 0 and y = 1

Thread 1:

r1 = x

r2 = r1

if (r1 == r2)

y = 2

Thread 2:

r3 = y

x = r3

Local analysis now allows you to determine that the write y=2 is

always performed and can be performed early, allowing r1 = r2 = r3 =

2.

-----

Example 2 - forward substitution is illegal

Initially:

x = 0 and y = 1 and z = 0

Thread 1:

r1 = z

x = r1

r2 = x

if (r1 == r2)

y = 2

Thread 2:

r3 = y

z = r3

The write y=2 cannot be done early; you can't determine if the write

y=2 will always occur from purely thread local information. This

disallows the result r1 = r2 = r3 = 2

Applying forward substitution to example 2 yields:

Initially:

x = 0 and y = 1 and z = 0

Thread 1:

r1 = z

x = r1

r2 = r1

if (r1 == r2)

y = 2

Thread 2:

r3 = y

z = r3

For this transformed code, the write y = 2 can be done early,

allowing r1 = r2 = r3 = 2.

This isn't to say that you can't fix the problem by adjusting the

semantics. However, the semantics have to allow it. If the semantics

don't allow the behavior it can produce, it isn't a legal program

transformation.

At 10:18 AM -0400 9/14/01, Jan-Willem Maessen wrote:

*>Next week, a new program transformation will be invented; Java programmers
*

*>will be none the wiser, and the system still needs to behave explicably.
*

I wish things were that simple. Unfortunately, they aren't. A

semantics has to be able to tell you whether a particular behavior is

legal. Given a particular execution model (e.g., TSO), program

transformations affect which behaviors can be perceived.

It turns out that in our model, we have needed to adjust the model to

account for the interaction between forward substitution, redundant

load elimination and prescient writes. I wasn't thrilled about having

to do this adjustment, but I didn't see any alternative.

How can we be 100% certain that some transformation won't be invented

later that will be ruled invalid by our model? I don't see how we

could be 100% certain. But we spend a lot of time trying to break our

model, and I hope the readers of this list will too. Sometimes, 99

44/100% certain will have to do.

Bill

-------------------------------

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

**Next message:**Bill Pugh: "JavaMemoryModel: We need your litmus tests"**Previous message:**Richard Jones: "Re: JavaMemoryModel: What's "control dependence" mean?"**In reply to:**Clifford Click: "Re: JavaMemoryModel: What's "control dependence" mean?"**Next in thread:**Bill Pugh: "Re: JavaMemoryModel: What's "control dependence" mean?"**Reply:**Bill Pugh: "Re: JavaMemoryModel: What's "control dependence" mean?"**Reply:**Clifford Click: "Re: JavaMemoryModel: What's "control dependence" mean?"**Reply:**Roly Perera: "RE: JavaMemoryModel: What's "control dependence" mean?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Mail actions:**[ respond to this message ] [ mail a new topic ]

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