Atomic fence support

[aheejin]

C++ 11 provides std::atomic_signal_fence and std::atomic_thread_fence, and LLVM IR's fence instruction also takes a syncscope argument, which can be either "singlethread" (for a single thread, such as signal handlers) or "<target-scope>" (for multiple threads). And there are people who use asm volatile(""::: "memory") with a similar usage to fences. How do we support these fences in wasm? Some discussions have been going on in this CL, but the CL itself was not very much related to the topic.

---

std::atomic_thread_fence / LLVM's fence syncscope("<target-scope>")

Wasm does not have a fence instruction, and currently all atomic memory instructions are sequentially consistent, but we still need something because fences also order non-atomic instructions. I submitted a CL that converts a fence into a sequence of

get_global $__stack_pointer
i32.atomic.rmw.or 0

which is basically an idempotent atomic RMW instruction.

---

std::atomic_signal_fence / LLVM's fence syncscope("singlethread")

Currently the fence CL does not distinguish syncscopes, treating both of them the same way conservatively. But for fences that work only within a thread, we may not need to emit an atomic idempotent RMW instruction; preventing instruction reordering across it during the backend compilation (using a pseudo instruction or something) would be sufficient, and it can eventually be lowered down to 0 instruction. What do you think?

---

asm volatile(""::: "memory")

We are currently doing nothing for this, but how about treating this as the same way as a signal fence, meaning it will become a pseudo instruction that prevents reordering within the compiler backend but eventually be converted to 0 instruction?

[aheejin]

@dschuff @jfbastien @sunfishcode @conrad-watt
I guess not adding CC list in the issue post itself would be neater...

[conrad-watt]

From reading this, https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence, my interpretation is that memory fences do not impose any extra ordering constraints on non-atomics unless the atomic actions with Y reads-from X (bullet 2 of the first two subheadings, for example) exist and do not themselves synchronize (i.e. are memory_order_relaxed/memory_order_consume(?)). Since all same-location Wasm atomic actions Y reads-from X create a synchronize edge, I believe that if the compilation scheme turns all C++ atomics into Wasm SeqCst atomics, memory fences can be no-ops.

As a caveat, I'm not an expert in C++ fence semantics and real-world usage.

[aheejin]

@conrad-watt It was unclear in the thread proposal, but it seems like, unlike in C++, atomic operations cannot be reordered with respect to non-atomic operations in wasm. There had been a similar discussion thread in binaryen repo, starting from WebAssembly/binaryen#1094 (comment). So, I guess we need something to prevent reordering, and that's why I inserted an idempotent atomicrmw instruction in the CL.

[conrad-watt]

Yeah, Wasm definitely has stricter rules for atomic + non-atomic ordering. The issue linked above looks like a discussion on Wasm -> Wasm transformations, where this would be a disallowed reordering.

The current issue seems to be about the correct translation for llvm -> Wasm. Here, we start in a semantics where the reordering is allowed(? not sure.) (llvm/C++) and (potentially after some llvm -> llvm transformations) move to one where it definitely isn't (Wasm/JS). Once we move to Wasm-world, this naturally disallows further reorderings, even without the inserted atomic.rmw.

I'd expect to see such an instruction inserted when going in the opposite direction, from a semantics where the reordering is disallowed, to one where it is allowed. In any case, the atomic.rmw seems to have been mainly motivated in the CL linked above by the concern that C++ fences cause an ordering restriction on non-atomics which must be preserved when moving to Wasm. But if I'm reading this correctly, an additional ordering restriction on non-atomics is only imposed if they are related by sequenced-before to a particular relaxed atomic operation that does not otherwise synchronize until forced to by the fence. But such an atomic operation, when translated to a Wasm atomic, is strengthened to the point that it will synchronize anyway, so fences could be no-ops. Consider that the synchronizes-with edges specified involving the fence here induce ordering constraints that are weaker than those that would be introduced if the atomic actions Y and X already synchronized.

[aheejin]

(Sorry for previous notifications for deleted comments)

I think you have a valid point. We still have to make sure reordering around a fence does not happen in the compiler, but yes, according to C++'s and LLVM's spec, I guess it is not necessary to emit an atomicrmw instruction in the wasm code, right?

But it might be user friendly thing to do still, because some people might expect fences to work as a full memory barrier, including with respect to non-atomic operations. @jfbastien, when we discussed about this in the other CL, did you have user-friendliness in mind? Or am I missing something?

[lars-t-hansen]

As a practical matter, for asm.js a fence was translated as Atomics.add(0,0), since address 0 is always writeable, ie we don't need to mess around with reading the stack pointer, unlike what Linux does for fences on older systems, and what @aheejin suggested for LLVM.

[aheejin]

@lars-t-hansen You mean, even wasm atomic semantics guarantees every atomic and non-atomic instructions' ordering is preserved wrt every atomic instructions, it emits Atomics.add(0,0)? Is that for user-friendliness?
And I used the value stored in __stack_pointer global because it is likely to be in the cache, while the address 0 is not.

[lars-t-hansen]

@aheejin, what I meant was that when the C++ source program contains an explicit fence operation, emscripten compiling to asm.js would emit Atomics.add(0,0); on current JS/asm.js implementations this would have the desired ordering effect even though the idea of a fence has no meaning in the JS memory model.

We discussed actually recognizing Atomics.add(0,0) as a special case and emitting a native fence instruction for it. In that case, it is better for the arguments to be (0,0) since it is easy to recognize that. But we didn't implement it for asm.js, and last week we removed atomics support from our asm.js implementation.

(What you say about the cache locality of the stack memory makes sense, of course.)

[sunfishcode]

asm volatile(""::: "memory")

I think we all agree codegen should translate this to zero wasm instructions.

std::atomic_signal_fence

One of the arguments against adding a volatile flag to wasm itself was that wasm doesn't (currently) have signals, so the volatile sig_atomic_t construct doesn't need special treatment. By similar reasoning, it seems codegen can translate atomic_signal_fence into zero wasm instructions too.

std::atomic_thread_fence

If I'm reading @conrad-watt's comments, LLVM LangRef, and C++ correctly, this seems analogous to the situation with volatile loads and stores: even if we might wish to be "friendly" and emit something to prevent additional reorderings, such code is already at risk of being reordered by LLVM, so the better place for such a feature is the front-end, where we can get consistent semantics through the optimizer as well as the wasm code.

So with what I know right now, having the backend translate atomic_thread_fence to zero instructions also seems best. That way it won't add any extra overhead to code that does follow the rules.

[dschuff]

I agree regarding asm volatile(""::: "memory") and std::atomic_signal_fence. We'll still need to prevent the backend from moving memory ops across the fence (e.g. MachineLICM and register stackification).

I'm a bit more on the fence regarding std::atomic_thread_fence. One concern I have is that if there is a mistake in usage (e.g. the user expects the fence to prevent motion of non-atomic operations), then it's much much harder to debug or understand what's happening when it's the VM that violates the user's assumption. If the compiler does so, then the user can always disassemble the wasm binary and see what has happened to their loads and stores. However if it's the VM, then there might not be any way to see what has happened; and indeed it may be non-deterministic (e.g. based on tiering). That sounds like a bit of a nightmare.
Still, the C++11 memory model is pretty clear on what the semantics are and a user using std::atomic_thread_fence is writing new code and opting into that, so it seems ok to actually implement the C++11 memory model and generate no instructions. This "new code opting-in" idea is why my opinion on this case is sort of the opposite of my opinion on volatiles, which are almost certainly legacy code.

It might be worth having some kind of debug option in either the compiler (where we would insert extra atomic RMWs or something) or the VM (disabling optimizations) to help debug in situations like this.

I guess we haven't also discussed __sync_synchronize(). That's intended to be a full barrier, and I think we do want to have the no-op Atomic RMW for that.

[jfbastien]

Maybe it'll be helpful to review this summary of the semantics of fence operations:
https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence

[aheejin]

@dschuff

I guess we haven't also discussed __sync_synchronize(). That's intended to be a full barrier, and I think we do want to have the no-op Atomic RMW for that.

C++11's std::atomic_thread_fence, gcc's __atomic_thread_fence, and gcc's __sync_synchronize all translate to LLVM's fence with no syncscope (meaning it syncs with all other threads). (And it is not really important here anyway, but unlike others, __sync_synchronize does not take a memory order argument, and it is translated to a seq_cst fence.)

So, If we want to treat at least __sync_synchronize as a full memory barrier, we should treat all of these the same, which is also one reason why I'm inclined to translate these to an idempotent atomicrmw instruction.

And C++11's std::atomic_signal_fence and gcc's __atomic_signal_fence translate to LLVM's fence with syncscope("singlethread"), which the current CL translates to a pseudo compiler barrier that eventually becomes 0 instruction.

[conrad-watt]

LLVM fence (my ref) seems to take the C++11 semantics as does __atomic_thread_fence (my ref). So the story between all of them in relation to std::atomic_thread_fence is uncomplicated.

EDIT: see @sunfishcode's response below

__sync_synchronize is weird. Going by this ref, it describes itself as legacy and compatible with the Intel Itanium Processor-specific Application Binary Interface. Looking at 7.4 of this, it appears to intend to guarantee a full compiler and hardware memory barrier, even for C++ non-atomics. This is hard to square with C++11's treatment of non-atomic data races. I imagine there are some really hairy legacy code issues here. I'd speculate there are even theoretically possible nutty LLVM link-time optimisations which could break the guarantee it wants to give if it's translated to an LLVM seq_cst fence (like no-oping a fence if no atomic op can be related to it by sequence-before).

More immediately, I can totally understand why it's desirable to make sure __sync_synchronize ultimately gets compiled to an atomicrmw for Wasm. LLVM fence. in isolation, semantically, doesn't need to be - but the friendliness argument seems pretty strong if __sync_synchronize becomes an LLVM fence.

[aheejin]

@sunfishcode

std::atomic_thread_fence

If I'm reading @conrad-watt's comments, LLVM LangRef, and C++ correctly, this seems analogous to the situation with volatile loads and stores: even if we might wish to be "friendly" and emit something to prevent additional reorderings, such code is already at risk of being reordered by LLVM, so the better place for such a feature is the front-end, where we can get consistent semantics through the optimizer as well as the wasm code.

So with what I know right now, having the backend translate atomic_thread_fence to zero instructions also seems best. That way it won't add any extra overhead to code that does follow the rules.

I think this situation might be a little different from that of volatile's, because, for volatiles what we can do to be user-friendly (even though it is not strictly required from the spec) is treating them as atomic instructions, whereas here what we can do to be user-friendly (even though it is not strictly required form the spec) is making them as a full barrier not only for atomics but also non-atomics, which requires emitting an atomic instruction in wasm.

And in this case I don't think we can do or need to do something from the frontend, because std::atomic_thread_fence becomes LLVM's fence, which provides sufficient guarantees to prevent code reordering during compilation in the middle end.

[sunfishcode]

I'm not currently deeply familiar with the semantics for fences here.

My observations here are:

• The main problem here is not wasm's problem alone, so we should generally prefer solutions that can be shared with other targets in clang.
• This problem doesn't affect all users of LLVM.
• Having an LLVM backend go out of its way to be friendlier than LLVM's optimizer is ultimately not that friendly, and it makes the backend harder to maintain over time.

So, I'm skeptical about doing anything "friendly" in the wasm backend.

LLVM seems pretty clear that it wants to treat __sync_synchronize as a seq_cst fence. That's what clang does with it, and that's what it says here.