[WebAssembly] Support for atomic fences

[aheejin]

Summary

This adds support for translation of LLVM IR fence instruction. We
convert a singlethread fence to a pseudo compiler barrier which becomes
0 instructions in final binary, and a thread fence to an idempotent
atomicrmw instruction to a memory address.

[aheejin]

comment fix

[jfb]

What do you expect for relaxed, as well as for signal fences?
Could you also check in with Conrad, since he's been working on the WebAssembly memory model?

[aheejin]

What do you expect for relaxed, as well as for signal fences?

Here I actually translated both a signal fence and a thread fence to the same thing. I think this will be conservatively correct, but maybe we should treat them differently. What if we translate a signal fence to a nothing but prevent reordering of instructions across it, and we might do the same thing for asm volatile("" ::: "memory") too. That can be something like making a pseudo instruction that eventually becomes nothing and prevents reordering across the pseudo instruction in the backend passes. What do you think?

Oh and for weaker fences, I added tests for them. They all translate to the same sequentially consistent atomicrmw or instruction.

Could you also check in with Conrad, since he's been working on the WebAssembly memory model?

I don't think Conrad is in the LLVM Phabricator here. Should we move the discussion to a github issue?

[aheejin]

• Add support for singlethread fences
• Fixed handling of MachineMemOperand according to changes in rL339740

[aheejin]

Don't emit the pseudo compiler_fence instruction in .s file

[aheejin]

Use a target external symbol with MO_SYMBOL_GLOBAL

[aheejin]

We discussed how to implement fences here, and I think the general consensus was even though it may not be strictly necessary to emit atomicrmw for some cases, it can be user friendly and also might help support legacy builtins like __sync_synchronize(). And IMHO it is a single instruction anyway and fences are generally expected to be expensive, so no significant harm will be done. Does anyone have more concerns on this? If not, can we land this?

[sunfish]

In D50277#1210237, @aheejin wrote:

We discussed how to implement fences here, and I think the general consensus was even though it may not be strictly necessary to emit atomicrmw for some cases, it can be user friendly and also might help support legacy builtins like __sync_synchronize(). And IMHO it is a single instruction anyway and fences are generally expected to be expensive, so no significant harm will be done. Does anyone have more concerns on this? If not, can we land this?

I have concerns which I expressed here: https://github.com/WebAssembly/tool-conventions/issues/59#issuecomment-413620669

[aheejin]

• rebase

[aheejin]

• Fix bug: 0 should be i32.const 0 and not an immediate

[aheejin]

• Use ATOMIC_NRI for the fence + test fix

[tlively]

What is the status of the discussion here? We've gotten to the point where I have to manually add this patch to my local checkout in order to debug unrelated issues and it looks like the conversation fizzled out a while ago, so it would be great if we could land something.

[sunfish]

I've now made an updated post on https://github.com/WebAssembly/tool-conventions/issues/59.

[dschuff]

Given the discussion on the github issues, we have scheduled a discussion at the in-person CG meeting that should resolve the outstanding memory model issues, possibly with a change to the spec.

However, the lack of fence lowering is now AFAIK the only thing that holds us back from declaring the wasm backend as the primary/only supported codegen path and staring the process of removing fastcomp.
Given that, I'm going to propose that we apply this patch as-is, to match the current behavior of the existing emscripten pipeline, with the understanding that we can consider the issue still open and change LLVM's behavior based on the outcome of the discussions (and we can in any case ensure that we don't declare any stable ABIs or allow this change to get branched). We can even put it behind the emscripten triple if people feel strongly about that.
Any objections?

[aheejin]

I agree; this matches the current behavior, so it does not change anything from users' standpoint, and we ever decide do something else in the CG meeting, we can always land another patch later.

[sunfish]

If I follow the discussion correctly, there are subtle ABI issues either way, so making fence a RMW now doesn't give us fully a future-proof ABI anyway. Consequently, I would prefer to make this patch conditional on the Emscripten triple, as wasm32-wasi and wasm32-unknown-unknown don't require Emscripten compatibility.

[dschuff]

Yeah I agree with your assessment that this doesn't give us a future-proof ABI; that's why I want to revisit it later. Mostly this is to unblock removing fastcomp.

[aheejin]

OK I'll predicate this under emscripten triple. But anyway someone please approve this!

[tlively]

LGTM ship it! (behind emscripten flag)

[aheejin]

• Predicate behind wasm32-unknown-emscripten flag.
• Add tests for non-emscripten flags

[aheejin]

• test cosmetic change

[tlively]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

111

This looks over-indented. Am I missing something?

[dschuff]

LGTM modulo the indentation thing.

[aheejin]

• Fix a typo and indentations

[aheejin]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

111

Thanks! How did it happen...??

[sunfish]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

109

My understanding of https://github.com/WebAssembly/tool-conventions/issues/59 is that we can lower fence to zero instructions here, rather than aborting.

[aheejin]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

109

Sorry I didn't see this before committing. This is just to ensure the current crashing behavior for non-emscripten OSes. This does not change anything for them. Didn't we decide that we should commit this CL only for emscripten triple and wait for other OSes until we make a final decision on fences?

[sunfish]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

109

The behavior before this patch is to emit zero instructions, and not crash. So this patch does change the behavior. I'm asking to restore this previous behavior for non-Emscripten OS's.

[aheejin]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

109

Really? Without this patch, it crashes for me. Of course, only when we have -mattr=+atomics; if we don't have atomics enabled all atomic instructions become normal instructions and fences become nothing for all triples. This behavior is still the same.
This is when I enabled -mattr=+atomics with wasi triple, before this patch landed:

$ llc atomic-fence.ll -mtriple=wasm32-unknown-wasi -mattr=+atomics,+sign-ext
LLVM ERROR: Cannot select: t3: ch = AtomicFence t0, Constant:i32<7>, Constant:i32<1>
  t1: i32 = Constant<7>
  t2: i32 = Constant<1>
In function: multithread_fence

[sunfish]

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

109

Ah, you're right, I did a quick test without -mattr=+atomics, which I forget is now the thing which determines whether operations like fence are lowered by LowerAtomic.

lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

 void WebAssemblyDAGToDAGISel::Select(SDNode *Node) {
   // If we have a custom node, we already have selected!
   if (Node->isMachineOpcode()) {
     LLVM_DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
     Node->setNodeId(-1);
     return;
   }
 
-  // Few custom selection stuff. If we need WebAssembly-specific selection,
-  // uncomment this block add corresponding case statements.
-  /*
+  // Few custom selection stuff.
+  SDLoc DL(Node);
+  MachineFunction &MF = CurDAG->getMachineFunction();
   switch (Node->getOpcode()) {
+  case ISD::ATOMIC_FENCE: {
+    if (!MF.getSubtarget<WebAssemblySubtarget>().hasAtomics())
+      break;
+
+    // Wasm does not have a fence instruction, but because all atomic
+    // instructions in wasm are sequentially consistent, we translate a fence to
+    // an idempotent atomic RMW instruction to a linear memory address. While
+    // any address can work, here we use a value stored in __stack_pointer wasm
+    // global because there's high chance that area is in cache.
+    //
+    // So the selected instructions will be in the form of:
+    //   %addr = get_global $__stack_pointer
+    //   i32.atomic.rmw.or %addr, 0
+    SDValue StackPtrSym = CurDAG->getExternalSymbol(
+        "__stack_pointer", TLI->getPointerTy(CurDAG->getDataLayout()));
+    MachineSDNode *GetGlobal =
+        CurDAG->getMachineNode(WebAssembly::GET_GLOBAL_I32, // opcode
+                               DL,                          // debug loc
+                               MVT::i32,                    // result type
+                               StackPtrSym // __stack_pointer symbol
+        );
+
+    SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
+    auto *MMO = MF.getMachineMemOperand(
+        MachinePointerInfo::getUnknownStack(MF),
+        // FIXME Volatile isn't really correct, but currently all LLVM atomic
+        // instructions are treated as volatiles in the backend, so we should be
+        // consistent.
+        MachineMemOperand::MOVolatile | MachineMemOperand::MOLoad |
+            MachineMemOperand::MOStore,
+        4, 4, AAMDNodes(), nullptr, SyncScope::System,
+        AtomicOrdering::SequentiallyConsistent);
+    MachineSDNode *AtomicRMW =
+        CurDAG->getMachineNode(WebAssembly::ATOMIC_RMW_OR_I32, // opcode
+                               DL,                             // debug loc
+                               MVT::i32,                       // result type
+                               MVT::Other,                     // outchain
+                               {
+                                   Zero,                  // alignment
+                                   Zero,                  // offset
+                                   SDValue(GetGlobal, 0), // __stack_pointer
+                                   Zero, // OR with 0 to make it idempotent
+                                   Node->getOperand(0) // inchain
+                               });
+    MachineSDNode::mmo_iterator MemOp = MF.allocateMemRefsArray(1);
+    MemOp[0] = MMO;
+    AtomicRMW->setMemRefs(MemOp, MemOp + 1);
+
+    ReplaceUses(SDValue(Node, 0), SDValue(AtomicRMW, 1));
+    CurDAG->RemoveDeadNode(Node);
+    return;
+  }
+
   default:
     break;
   }
-  */
 
   // Select the default instruction.
   SelectCode(Node);
 }
 
 bool WebAssemblyDAGToDAGISel::SelectInlineAsmMemoryOperand(
     const SDValue &Op, unsigned ConstraintID, std::vector<SDValue> &OutOps) {
   switch (ConstraintID) {

test/CodeGen/WebAssembly/atomic-fence.ll

+; RUN: not llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt
+; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -disable-wasm-explicit-locals -mattr=+atomics,+sign-ext | FileCheck %s
+
+; Test atomic RMW (read-modify-write) instructions are assembled properly.
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; CHECK-LABEL: fence_seq_cst:
+; CHECK:  get_global  $push0=, __stack_pointer
+; CHECK-NEXT:  i32.atomic.rmw.or  $drop=, 0($pop0), 0
+define void @fence_seq_cst() {
+  fence seq_cst
+  ret void
+}
+
+; Fences with weaker memory orderings should be treated the same because atomic
+; memory access in wasm are sequentially consistent.
+
+; CHECK-LABEL: fence_weak:
+; CHECK:  get_global  $push{{[0-9]+}}=, __stack_pointer
+; CHECK:  i32.atomic.rmw.or
+; CHECK:  i32.atomic.rmw.or
+; CHECK:  i32.atomic.rmw.or
+define void @fence_weak() {
+  fence acquire
+  fence release
+  fence acq_rel
+  ret void
+}