[WebAssembly] Add atomic.fence instruction

[aheejin]

Summary

This adds atomic.fence instruction:
https://github.com/WebAssembly/threads/blob/master/proposals/threads/Overview.md#fence-operator

And we now emit the new atomic.fence instruction for multithread
fences, rather than the prevous atomic.rmw hack.

[aheejin]

• Insert fence in the ascending order of opcode

[dschuff]

llvm/test/CodeGen/WebAssembly/atomic-fence.ll

6–7

This line can be removed.

32–33

how about CHECK-NOT: fence to catch any kind of fence output?
Even better, could we also come up with some sequence of instructions that would otherwise be reordered (e.g. by register stackification) that the fence would prevent?

[aheejin]

• Address comments

[aheejin]

• Remove a stray line

[aheejin]

• Fixed comments a little

llvm/test/CodeGen/WebAssembly/atomic-fence.ll

32–33

how about CHECK-NOT: fence to catch any kind of fence output?

CHECK-NOT: fence doesn't work because it accidentally matches with .functype singlethread_fence () -> () in the output. Added CHECK-NOT: atomic-fence additionally.

Even better, could we also come up with some sequence of instructions that would otherwise be reordered (e.g. by register stackification) that the fence would prevent?

I think it is not easy to show exactly that in this ll test... Added a mir test for that. (The reason I used atomic.notify is, that's one of the rare, maybe the only, instructions that returns a value and has a side effect that's not a trap, which is the condition that satisfies this line.)

[dschuff]

great, LGTM!

llvm/lib/Target/WebAssembly/WebAssemblyISelDAGToDAG.cpp

void WebAssemblyDAGToDAGISel::Select(SDNode *Node) {
   MachineFunction &MF = CurDAG->getMachineFunction();
   switch (Node->getOpcode()) {
   case ISD::ATOMIC_FENCE: {
     if (!MF.getSubtarget<WebAssemblySubtarget>().hasAtomics())
       break;
 
     uint64_t SyncScopeID =
         cast<ConstantSDNode>(Node->getOperand(2).getNode())->getZExtValue();
+    MachineSDNode *Fence = nullptr;
     switch (SyncScopeID) {
-    case SyncScope::SingleThread: {
+    case SyncScope::SingleThread:
       // We lower a single-thread fence to a pseudo compiler barrier instruction
       // preventing instruction reordering. This will not be emitted in final
       // binary.
-      MachineSDNode *Fence =
-          CurDAG->getMachineNode(WebAssembly::COMPILER_FENCE,
+      Fence = CurDAG->getMachineNode(WebAssembly::COMPILER_FENCE,
                                      DL,                 // debug loc
                                      MVT::Other,         // outchain type
                                      Node->getOperand(0) // inchain
-          );
-      ReplaceNode(Node, Fence);
-      CurDAG->RemoveDeadNode(Node);
-      return;
-    }
-
-    case SyncScope::System: {
-      // For non-emscripten systems, we have not decided on what we should
-      // traslate fences to yet.
-      if (!Subtarget->getTargetTriple().isOSEmscripten())
-        report_fatal_error(
-            "ATOMIC_FENCE is not yet supported in non-emscripten OSes");
-
-      // 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. All atomic instructions in wasm are sequentially consistent,
-      // but this is to ensure a fence also prevents reordering of non-atomic
-      // instructions in the VM. Even though LLVM IR's fence instruction does
-      // not say anything about its relationship with non-atomic instructions,
-      // we think this is more user-friendly.
-      //
-      // 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
-      //   %0 = i32.const 0
-      //   i32.atomic.rmw.or %addr, %0
-      SDValue StackPtrSym = CurDAG->getTargetExternalSymbol(
-          "__stack_pointer", TLI->getPointerTy(CurDAG->getDataLayout()));
-      MachineSDNode *GetGlobal =
-          CurDAG->getMachineNode(WebAssembly::GLOBAL_GET_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 *Const0 =
-          CurDAG->getMachineNode(WebAssembly::CONST_I32, DL, MVT::i32, Zero);
-      MachineSDNode *AtomicRMW = CurDAG->getMachineNode(
-          WebAssembly::ATOMIC_RMW_OR_I32, // opcode
-          DL,                             // debug loc
-          MVT::i32,                       // result type
-          MVT::Other,                     // outchain type
-          {
-              Zero,                  // alignment
-              Zero,                  // offset
-              SDValue(GetGlobal, 0), // __stack_pointer
-              SDValue(Const0, 0),    // OR with 0 to make it idempotent
-              Node->getOperand(0)    // inchain
-          });
-
-      CurDAG->setNodeMemRefs(AtomicRMW, {MMO});
-      ReplaceUses(SDValue(Node, 0), SDValue(AtomicRMW, 1));
-      CurDAG->RemoveDeadNode(Node);
-      return;
-    }
+      break;
+    case SyncScope::System:
+      // Currently wasm only supports sequentially consistent atomics, so we
+      // always set the order to 0 (sequentially consistent).
+      Fence = CurDAG->getMachineNode(
+          WebAssembly::ATOMIC_FENCE,
+          DL,                                         // debug loc
+          MVT::Other,                                 // outchain type
+          CurDAG->getTargetConstant(0, DL, MVT::i32), // order
+          Node->getOperand(0)                         // inchain
+      );
+      break;
     default:
       llvm_unreachable("Unknown scope!");
     }
+
+    ReplaceNode(Node, Fence);
+    CurDAG->RemoveDeadNode(Node);
+    return;
   }
 
   case ISD::GlobalTLSAddress: {
     const auto *GA = cast<GlobalAddressSDNode>(Node);
 
     if (!MF.getSubtarget<WebAssemblySubtarget>().hasBulkMemory())
       report_fatal_error("cannot use thread-local storage without bulk memory",
                          false);

llvm/lib/Target/WebAssembly/WebAssemblyInstrAtomics.td

 class WaitPatGlobalAddrOffOnly<ValueType ty, Intrinsic kind, NI inst> :
   Pat<(i32 (kind (WebAssemblywrapper tglobaladdr:$off), ty:$exp, I64:$timeout)),
       (inst 0, tglobaladdr:$off, (CONST_I32 0), ty:$exp, I64:$timeout)>;
 def : WaitPatGlobalAddrOffOnly<i32, int_wasm_atomic_wait_i32, ATOMIC_WAIT_I32>;
 def : WaitPatGlobalAddrOffOnly<i64, int_wasm_atomic_wait_i64, ATOMIC_WAIT_I64>;
 } // Predicates = [HasAtomics]
 
 //===----------------------------------------------------------------------===//
+// Atomic fences
+//===----------------------------------------------------------------------===//
+
+// A compiler fence instruction that prevents reordering of instructions.
+let Defs = [ARGUMENTS] in {
+let isPseudo = 1, hasSideEffects = 1 in
+defm COMPILER_FENCE : ATOMIC_NRI<(outs), (ins), [], "compiler_fence">;
+let hasSideEffects = 1 in
+defm ATOMIC_FENCE : ATOMIC_NRI<(outs), (ins i8imm:$flags), [], "atomic.fence",
+                               0x03>;
+} // Defs = [ARGUMENTS]
+
+//===----------------------------------------------------------------------===//
 // Atomic loads
 //===----------------------------------------------------------------------===//
 
 multiclass AtomicLoad<WebAssemblyRegClass rc, string name, int atomic_op> {
   defm "" : WebAssemblyLoad<rc, name, !or(0xfe00, !and(0xff, atomic_op))>,
             Requires<[HasAtomics]>;
 }
 

 }
 
 let Predicates = [HasAtomics] in
 defm : TerRMWTruncExtPattern<
   atomic_cmp_swap_8, atomic_cmp_swap_16, atomic_cmp_swap_32, atomic_cmp_swap_64,
   ATOMIC_RMW8_U_CMPXCHG_I32, ATOMIC_RMW16_U_CMPXCHG_I32,
   ATOMIC_RMW8_U_CMPXCHG_I64, ATOMIC_RMW16_U_CMPXCHG_I64,
   ATOMIC_RMW32_U_CMPXCHG_I64>;
-
-//===----------------------------------------------------------------------===//
-// Atomic fences
-//===----------------------------------------------------------------------===//
-
-// A compiler fence instruction that prevents reordering of instructions.
-let Defs = [ARGUMENTS] in {
-let isPseudo = 1, hasSideEffects = 1 in
-defm COMPILER_FENCE : ATOMIC_NRI<(outs), (ins), [], "compiler_fence">;
-} // Defs = [ARGUMENTS]

llvm/test/CodeGen/WebAssembly/atomic-fence.ll

 ; RUN: llc < %s | FileCheck %s --check-prefix NOATOMIC
-; RUN: not llc < %s -mtriple=wasm32-unknown-unknown -mattr=+atomics,+sign-ext 2>&1 | FileCheck %s --check-prefixes NOEMSCRIPTEN
-; RUN: not llc < %s -mtriple=wasm32-unknown-wasi -mattr=+atomics,+sign-ext 2>&1 | FileCheck %s --check-prefixes NOEMSCRIPTEN
-; RUN: llc < %s -mtriple=wasm32-unknown-emscripten -asm-verbose=false -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers -mattr=+atomics,+sign-ext | FileCheck %s
+; RUN: llc < %s -asm-verbose=false -wasm-disable-explicit-locals -wasm-keep-registers -mattr=+atomics | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
-; NOEMSCRIPTEN: LLVM ERROR: ATOMIC_FENCE is not yet supported in non-emscripten OSes
-
-; A multithread fence turns into 'global.get $__stack_pointer' followed by an
-; idempotent atomicrmw instruction.
+; A multithread fence is lowered to an atomic.fence instruction.
 ; CHECK-LABEL: multithread_fence:
-; CHECK:      global.get  $push[[SP:[0-9]+]]=, __stack_pointer
-; CHECK-NEXT: i32.const $push[[ZERO:[0-9]+]]=, 0
-; CHECK-NEXT: i32.atomic.rmw.or  $drop=, 0($pop[[SP]]), $pop[[ZERO]]
+; CHECK:  atomic.fence
 ; NOATOMIC-NOT: i32.atomic.rmw.or
 define void @multithread_fence() {
   fence seq_cst
   ret void
 }
 
 ; Fences with weaker memory orderings than seq_cst should be treated the same
 ; because atomic memory access in wasm are sequentially consistent.
 ; CHECK-LABEL: multithread_weak_fence:
-; CHECK:  global.get  $push{{.+}}=, __stack_pointer
-; CHECK:  i32.atomic.rmw.or
-; CHECK:  i32.atomic.rmw.or
-; CHECK:  i32.atomic.rmw.or
+; CHECK:       atomic.fence
+; CHECK-NEXT:  atomic.fence
+; CHECK-NEXT:  atomic.fence
 define void @multithread_weak_fence() {
   fence acquire
   fence release
   fence acq_rel
   ret void
 }
 
 ; A singlethread fence becomes compiler_fence instruction, a pseudo instruction
 ; that acts as a compiler barrier. The barrier should not be emitted to .s file.
 ; CHECK-LABEL: singlethread_fence:
-; CHECK-NOT:  compiler_fence
+; CHECK-NOT: compiler_fence
+; CHECK-NOT: atomic_fence
 define void @singlethread_fence() {
   fence syncscope("singlethread") seq_cst
   fence syncscope("singlethread") acquire
   fence syncscope("singlethread") release
   fence syncscope("singlethread") acq_rel
   ret void
 }

llvm/test/CodeGen/WebAssembly/atomic-fence.mir

+# RUN: llc -mtriple=wasm32-unknown-unknown -run-pass wasm-reg-stackify -run-pass wasm-explicit-locals %s -o - | FileCheck %s
+
+# In the two tests below, without compiler_fence or atomic.fence in between,
+# atomic.notify and i32.add will be reordered by register stackify pass to meet
+# 'call @foo''s requirement. But because we have fences in between atomic.notify
+# and i32.add, they cannot be reordered and local.set and local.get are used to
+# save and load atomic.notify's return value.
+
+--- |
+  target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+  target triple = "wasm32-unknown-unknown"
+
+  declare void @foo(i32, i32)
+  define void @compiler_fence_test(i32) {
+    ret void
+  }
+  define void @atomic_fence_test(i32) {
+    ret void
+  }
+...
+---
+# CHECK-LABEL: name: compiler_fence_test
+name: compiler_fence_test
+liveins:
+  - { reg: '$arguments' }
+tracksRegLiveness: true
+body: |
+  bb.0:
+    ; CHECK: %[[REG:[0-9]+]]:i32 = ATOMIC_NOTIFY
+    ; CHECK: LOCAL_SET_I32 [[LOCAL:[0-9]+]], %[[REG]]
+    ; CHECK: COMPILER_FENCE
+    ; CHECK: ADD_I32
+    ; CHECK: LOCAL_GET_I32 [[LOCAL]]
+    ; CHECK: CALL_VOID @foo
+
+    liveins: $arguments
+    %0:i32 = CONST_I32 0, implicit-def $arguments
+    %1:i32 = ATOMIC_NOTIFY 2, 0, %0:i32, %0:i32, implicit-def $arguments
+    COMPILER_FENCE implicit-def $arguments
+    %2:i32 = ADD_I32 %0:i32, %0:i32, implicit-def $arguments
+    CALL_VOID @foo, %2:i32, %1:i32, implicit-def $arguments
+    RETURN_VOID implicit-def $arguments
+...
+
+---
+# CHECK-LABEL: name: atomic_fence_test
+name: atomic_fence_test
+liveins:
+  - { reg: '$arguments' }
+tracksRegLiveness: true
+body: |
+  bb.0:
+    ; CHECK: %[[REG:[0-9]+]]:i32 = ATOMIC_NOTIFY
+    ; CHECK: LOCAL_SET_I32 [[LOCAL:[0-9]+]], %[[REG]]
+    ; CHECK: ATOMIC_FENCE
+    ; CHECK: ADD_I32
+    ; CHECK: LOCAL_GET_I32 [[LOCAL]]
+    ; CHECK: CALL_VOID @foo
+
+    liveins: $arguments
+    %0:i32 = CONST_I32 0, implicit-def $arguments
+    %1:i32 = ATOMIC_NOTIFY 2, 0, %0:i32, %0:i32, implicit-def $arguments
+    ATOMIC_FENCE 0, implicit-def $arguments
+    %2:i32 = ADD_I32 %0:i32, %0:i32, implicit-def $arguments
+    CALL_VOID @foo, %2:i32, %1:i32, implicit-def $arguments
+    RETURN_VOID implicit-def $arguments
+...
+

llvm/test/MC/WebAssembly/atomics-encodings.s

 # RUN: llvm-mc -show-encoding -triple=wasm32-unkown-unknown -mattr=+atomics < %s | FileCheck %s
 
 main:
   .functype main () -> ()
 
   # CHECK:  atomic.notify 0 # encoding: [0xfe,0x00,0x02,0x00]
   atomic.notify 0
   # CHECK:  i32.atomic.wait 0 # encoding: [0xfe,0x01,0x02,0x00]
   i32.atomic.wait 0
   # CHECK:  i64.atomic.wait 0 # encoding: [0xfe,0x02,0x03,0x00]
   i64.atomic.wait 0
 
+  # CHECK: atomic.fence # encoding: [0xfe,0x03,0x00]
+  atomic.fence
+
   # CHECK: i32.atomic.load 0 # encoding: [0xfe,0x10,0x02,0x00]
   i32.atomic.load 0
   # CHECK: i64.atomic.load 4 # encoding: [0xfe,0x11,0x03,0x04]
   i64.atomic.load 4
   # CHECK:  i32.atomic.load8_u 48 # encoding: [0xfe,0x12,0x00,0x30]
   i32.atomic.load8_u 48
   # CHECK:  i32.atomic.load16_u 0 # encoding: [0xfe,0x13,0x01,0x00]
   i32.atomic.load16_u 0