Happens before and program order in Java Memory Model

You're missing this part of the JLS:

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

In your case, since 1 and 2 are unrelated, they can be flipped. Now if 2 had been y = r1, then 1 must happen before 2 for the right result.

The real problem occurs with multi-processor execution. Without any happen-before boundaries, T2 may observe 2 happening before 1, regardless of execution order.

This is because of CPU caching. Let's say T1 executed 1 and 2, in any order. Since no happen-before boundary exist, these actions are still in CPU cache, and depending on other needs, the part of the cache containing the result of 2 may be flushed before the part of the cache that contains the result of 1.

If T2 executes between those two cache flush events, it'll observe 2 has happened and 1 hasn't, i.e. 2 happened before 1, as far as T2 knows.

If this is not allowed, then T1 must establish a happens-before boundary between 1 and 2.

In Java there are various ways of doing that. The old style would be to put 1 and 2 into separate synchronized blocks, because the start and end of a synchronized block is a happens-before boundary, i.e. any action before the block happens before actions inside the block, and any action inside the block happens before actions coming after the block.

I think a key issue is with your construction P'. It implies that the way re-ordering works is that re-ordering is global - the entire program is re-ordered in single way (on each execution) which obeys the memory model. Then you are trying to reason about this P' and find out that no interesting re-orderings are possible!

What actually occurs is that there is no particular global order for statements not related by a hb relationship, so different threads can see different apparent orders on the same execution. In your example, there are no edges between {1,2} and {3,4} statements in one set can see those in the other set in any order. For example, it is possible that T2 observes 2 before 1, but that then T3, which is identical to T2 (with its own private variables), observes the opposite! So there is no single reordering P' - each thread may observe their own reorderings, as long as they are consistent with the JMM rules.

What you have described as P', is in fact not a different program, but an execution trace of the same program P. It could be a different program, but then it would have different po, and therefore different hb.

Happens-before relation restricts statement reordering with regards to their observable effect, not their execution order. Action 1 happens-before 2, but they don't observe each other's result, so they are allowed to be reordered.hb guarantees that you will observe that two actions were executed in-order, but only from synchronized context (i.e. from other actions forming hb with 1 and 2). You may think of 1 and 2 saying: Let's swap. No one's watching!.

Here is a good example from JLS that reflects happens-before idea quite well:

For example, the write of a default value to every field of an object constructed by a thread need not happen before the beginning of that thread, as long as no read ever observes that fact

In practice, it is rarely possible to order default-value writes of all objects constructed by a thread before it starts, even though they form synchronized-with edge with every action in that thread. A starting thread may not know what, and how many objects it will construct in run time. But once you have a reference to an object, you will observe that default value writes have already happened. Ordering default writes of an object not yet constructed (or known to be constructed) often cannot be reflected in execution, but it still does not violate happens-before relation, because it is all about observable effect.