Optimizer support for atomic instructions (#1094)

* Teach EffectAnalyzer not to reorder atomics wrt other memory operations.
* Teach EffectAnalyzer not to reorder host operations with memory operations
* Teach various passes about the operands of AtomicRMW and AtomicCmpxchg
* Factor out some functions in DeadCodeElimination and MergeBlocks

1 files changed, 31 insertions, 4 deletions

diff --git a/src/ast/effects.h b/src/ast/effects.h
index 6e4bb617e..5392c0e50 100644
--- a/src/ast/effects.h
+++ b/src/ast/effects.h
@@ -53,12 +53,14 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer> {
                              // (so a trap may occur later or earlier, if it is
                              // going to occur anyhow), but we can't remove them,
                              // they count as side effects
+  bool isAtomic = false; // An atomic load/store/RMW/Cmpxchg or an operator that
+                         // has a defined ordering wrt atomics (e.g. grow_memory)
 
   bool accessesLocal() { return localsRead.size() + localsWritten.size() > 0; }
   bool accessesGlobal() { return globalsRead.size() + globalsWritten.size() > 0; }
   bool accessesMemory() { return calls || readsMemory || writesMemory; }
-  bool hasSideEffects() { return calls || localsWritten.size() > 0 || writesMemory || branches || globalsWritten.size() > 0 || implicitTrap; }
-  bool hasAnything() { return branches || calls || accessesLocal() || readsMemory || writesMemory || accessesGlobal() || implicitTrap; }
+  bool hasSideEffects() { return calls || localsWritten.size() > 0 || writesMemory || branches || globalsWritten.size() > 0 || implicitTrap || isAtomic; }
+  bool hasAnything() { return branches || calls || accessesLocal() || readsMemory || writesMemory || accessesGlobal() || implicitTrap || isAtomic; }
 
   // checks if these effects would invalidate another set (e.g., if we write, we invalidate someone that reads, they can't be moved past us)
   bool invalidates(EffectAnalyzer& other) {
@@ -67,6 +69,12 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer> {
                  || (accessesMemory() && (other.writesMemory || other.calls))) {
       return true;
     }
+    // All atomics are sequentially consistent for now, and ordered wrt other
+    // memory references.
+    if ((isAtomic && other.accessesMemory()) ||
+        (other.isAtomic && accessesMemory())) {
+      return true;
+    }
     for (auto local : localsWritten) {
       if (other.localsWritten.count(local) || other.localsRead.count(local)) {
         return true;
@@ -176,10 +184,24 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer> {
   }
   void visitLoad(Load *curr) {
     readsMemory = true;
+    isAtomic |= curr->isAtomic;
     if (!ignoreImplicitTraps) implicitTrap = true;
   }
   void visitStore(Store *curr) {
     writesMemory = true;
+    isAtomic |= curr->isAtomic;
+    if (!ignoreImplicitTraps) implicitTrap = true;
+  }
+  void visitAtomicRMW(AtomicRMW* curr) {
+    readsMemory = true;
+    writesMemory = true;
+    isAtomic = true;
+    if (!ignoreImplicitTraps) implicitTrap = true;
+  }
+  void visitAtomicCmpxchg(AtomicCmpxchg* curr) {
+    readsMemory = true;
+    writesMemory = true;
+    isAtomic = true;
     if (!ignoreImplicitTraps) implicitTrap = true;
   }
   void visitUnary(Unary *curr) {
@@ -219,11 +241,16 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer> {
     }
   }
   void visitReturn(Return *curr) { branches = true; }
-  void visitHost(Host *curr) { calls = true; }
+  void visitHost(Host *curr) {
+    calls = true;
+    // grow_memory modifies the set of valid addresses, and thus can be modeled as modifying memory
+    writesMemory = true;
+    // Atomics are also sequentially consistent with grow_memory.
+    isAtomic = true;
+  }
   void visitUnreachable(Unreachable *curr) { branches = true; }
 };
 
 } // namespace wasm
 
 #endif // wasm_ast_effects_h
-