Roach Motels and The Java Memory Model

I've been asked by a couple of people lately about what a compiler can do with code motion around synchronized blocks. The first person asked me about the following example, so let's run with it:

x = 1;
synchronized(o) {
 z = z + 1;
}
y = 1;

I may have answered this already (at some point), but I feel free to repeat myself.

The JMM has what we call "roach motel" ordering. "Roach Motel" is Black Flag's name for their cockroach trap; in grad school, my apartment had lots and lots and lots of cockroaches, so I find it particularly salient (although I think it was probably Bill Pugh who came up with this association).

In the 1980s, the slogan for Black Flag Roach Motels was "Roaches check in, but they don't check out". The memory model is the same: accesses can be moved into synchronized blocks, but they can't be moved out. So, in this case, you can get:

x = 1;
synchronized(o) {
 z = z + 1;
}
y = 1;

if we want to move the write to y early, this code transforms to:

x = 1;
synchronized(o) {
 z = z + 1;
 y = 1; // code motion
}

and transforms to:

x = 1;
synchronized(o) {
 y = 1; // code motion
 z = z + 1;
}

and can't be transformed any more, because the write to y has been moved into the
synchronized block, but can't move out.

Similarly, if we want to move the write to x down:

x = 1;
synchronized(o) {
 z = z + 1;
}
y = 1;

transforms to:

synchronized(o) {
 x = 1; // code motion
 z = z + 1;
}
y = 1

transforms to:

synchronized(o) {
 z = z + 1;
 x = 1; // code motion
}
y = 1

.. but the write to x can't move any further.

At the end of these sorts of transformations, you can end up with something that looks like this:

synchronized(o){
 y = 1;
 z = z + 1;
 x = 1;
}

... so the accesses to x, y and z can happen in any order, but once you move them into the synchronized block, you can't move them out again.

This is a tiny bit misleading, of course, because they can go out the direction they came in. But there is no difference between that and not having entered the synchronized block in the first place.

Now, if the compiler can remove the synchronized block altogether, then all the accesses can be moved about freely. This can happen, for example, if o is an object only accessed by a single thread -- the compiler will know that no other thread can lock on it, so it can feel free to remove the synchronization. That's a tale for another day, of course.