In C++ atomic operations, are the generated values allowed to circularly depend on their own computations?

Interesting. Without optimization, each store has a control dependency on the preceding load. But both possible load results in Thread1 make the condition true so that branch could be optimized away at compile time.

I don't think I'd call this an "out of thin air" value, because local optimizations (allowed by the as-if rule) can potentially create r1 == 2 on real hardware by optimizing away the branch in Thread1. No inter-thread analysis or cross-confirming speculation shenanigans necessary, just normal optimizations and LoadStore reordering.

From another way of looking at it, r1 == 2 does look a lot like an out-of-thin-air value.

This optimization is possible because the if(r1...) condition is true even without the Thread2 store having happened yet. This potentially allows x.store(1, relaxed) to become visible to other threads without waiting for the load. But that would produce r1 == 0 if we look at an execution in the abstract-machine which does that.

Still, there's a mechanism that produces this result without hardware having to do cross-confirming speculation by making speculative values visible to other logical cores. (Real hardware never does that because it would require rolling back multiple logical cores on detection of mis-speculation, defeating the benefit of SMT, and being impractical as well as disastrously slow across physical cores.)

TL:DR: Optimization makes x.store non-speculative so it can reorder with the load since the control dependency goes away. (C++'s formal memory model doesn't work in terms of reordering, but their prohibition of OoTA values isn't part of the formalism either.)

If r1 is unsigned, then compilers will in practice optimize away the if(r1 >= 0) to if(true). If x and y are in different cache-lines, then LoadStore reordering in Thread1 is possible in practice, e.g. if the cache line holding y is already hot but the line holding y isn't.

If r1 is a signed integer type, then compilers won't in practice optimize away the compare, but in theory could with whole-program optimization. (Especially if x is static int x so it's actually just analysis of the compilation unit, not whole program including libraries, although in practice GCC and Clang still don't do value-range analysis here, probably treating atomic loads more like volatile internally, so not assuming anything about possible values.)

Godbolt with signed int vs. unsigned for r1, showing no branching. r1 == 2 would be possible in practice on AArch64 in that version. (Not on x86-64 where LoadStore reordering isn't allowed, but the asm is simpler since no extra instructions are needed to address static storage or set up immediates, so I included GCC x86-64 output too.)

If the load/branch still exists in the asm, it will prevent reordering of dependent stores with earlier loads on all real-world ISAs. (i.e. conditional stores won't reorder.) The C++ memory model doesn't forbid that, but other memory models such as the Linux kernel's model do. See Can the hardware reorder an atomic load followed by an atomic store, if the store is conditional on the load? where my answer quotes Linux's memory-barriers.txt.

BTW, the C++ standard says "should" only because the C++ committee can't find a way to formalize it as a requirement. I wonder if cases like this are part of what makes that difficult to formalize, because they almost certainly wouldn't want to make optimizations like unsigned >= 0 == true context-dependent. That was the sort of thing that made compiler devs give up on implementing memoryorder_consume efficiently, and just promote it to acquire, but that wouldn't be an option here.

See also

• What formally guarantees that non-atomic variables can't see out-of-thin-air values and create a data race like atomic relaxed theoretically can? for some quotes from C++ committee discussions about the intent to make the no-OoTA guarantee formal.
• How to verify a possible execution is OOTA?

You haven't specified what version of the standard you're interested in here, so I'm basing this on C++23 (N4950), which is still officiallly the standard, even though the committee has voted to submit C++26 to the ISO.

The big thing to keep mind here is that in the standard, the "no 'out of thin air' values" is a recommendation, not a requirement:

[atomics.order]/8:

Implementations should ensure that no “out-of-thin-air” values are computed that circularly depend on their own computation.

[emphasis added]

The example they show on cpp reference looks nearly identical to the example from note 7, in [atomics.order]/9:

[Note 7 : The recommendation similarly disallows r1 == r2 == 42 in the following example, with x and y again initially zero:

// Thread 1:
r1 = x.load(memoryorder::relaxed);
if (r1 == 42) y.store(42, memoryorder::relaxed);
// Thread 2:
r2 = y.load(memoryorder::relaxed);
if (r2 == 42) x.store(42, memoryorder::relaxed);

So all of this is purely recommendations, not requirements (they seem to say it's been a requirement since C++14, but that looks incorrect to me--the "should" quote above was copied and pasted from N4950, which is date 2023-05-10).

In your example, storing 1 into x effectively happens unconditionally--it happens when we load a value >= 0, but the value is always >= 0.

The relevant part of the standard in this case is [intro.races]/4:

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M.

[Note 3 : There is a separate order for each atomic object. There is no requirement that these can be combined into a single total order for all objects. In general this will be impossible since different threads can observe modifications to different objects in inconsistent orders. — end note]

Since we're using memoryorderrelaxed, we aren't imposing any synchronization either. So no, we can't deduce anything about how one thread sees the order of modifications to x from the order of modifications to y in another thread (or vice versa).

As to whether there's any hardware on which this could happen...I'm uncertain. The main place to look would be DEC Alpha processors, which were pretty well known for minimizing cache coherency, even at the expense of allowing things that seemed logically impossible.