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

4 files changed, 259 insertions, 2 deletions

diff --git a/test/passes/remove-unused-names_merge-blocks.txt b/test/passes/remove-unused-names_merge-blocks.txt
index bc42f2766..6bd9d348e 100644
--- a/test/passes/remove-unused-names_merge-blocks.txt
+++ b/test/passes/remove-unused-names_merge-blocks.txt
@@ -7,7 +7,7 @@
  (type $5 (func (result f64)))
  (table 1 1 anyfunc)
  (elem (i32.const 0) $call-i)
- (memory $0 256 256)
+ (memory $0 256 256 shared)
  (func $call-i (type $i) (param $0 i32)
   (nop)
  )
@@ -735,6 +735,33 @@
    (unreachable)
   )
  )
+ (func $atomics (type $3)
+  (drop
+   (i32.const 10)
+  )
+  (drop
+   (i32.const 30)
+  )
+  (drop
+   (i32.const 50)
+  )
+  (drop
+   (i32.atomic.rmw.cmpxchg
+    (i32.const 20)
+    (i32.const 40)
+    (i32.const 60)
+   )
+  )
+  (drop
+   (i32.const 10)
+  )
+  (drop
+   (i32.atomic.rmw.add
+    (i32.const 20)
+    (i32.const 30)
+   )
+  )
+ )
  (func $mix-select (type $i) (param $x i32)
   (drop
    (select
diff --git a/test/passes/remove-unused-names_merge-blocks.wast b/test/passes/remove-unused-names_merge-blocks.wast
index 346dc78f8..c249a34dd 100644
--- a/test/passes/remove-unused-names_merge-blocks.wast
+++ b/test/passes/remove-unused-names_merge-blocks.wast
@@ -1,5 +1,5 @@
 (module
-  (memory 256 256)
+  (memory 256 256 shared)
   (type $i (func (param i32)))
   (type $ii (func (param i32 i32)))
   (type $iii (func (param i32 i32 i32)))
@@ -885,6 +885,41 @@
       (unreachable)
     )
   )
+  (func $atomics (type $3)
+    (drop
+      (i32.atomic.rmw.cmpxchg ;; mergeblock logic should be same as select
+        (block $block0 (result i32)
+          (drop
+            (i32.const 10)
+          )
+          (i32.const 20)
+        )
+        (block $block1 (result i32)
+          (drop
+            (i32.const 30)
+          )
+          (i32.const 40)
+        )
+        (block $block2 (result i32)
+          (drop
+            (i32.const 50)
+          )
+          (i32.const 60)
+        )
+      )
+    )
+    (drop
+      (i32.atomic.rmw.add ;; atomicrmw is like a binary
+        (block $block1 (result i32)
+          (drop
+            (i32.const 10)
+          )
+          (i32.const 20)
+        )
+        (i32.const 30)
+      )
+    )
+  )
   (func $mix-select (param $x i32)
     (drop
       (select
diff --git a/test/passes/simplify-locals.txt b/test/passes/simplify-locals.txt
index 2be81e8c6..a46f74c69 100644
--- a/test/passes/simplify-locals.txt
+++ b/test/passes/simplify-locals.txt
@@ -876,3 +876,140 @@
   )
  )
 )
+(module
+ (type $FUNCSIG$v (func))
+ (type $FUNCSIG$i (func (result i32)))
+ (type $FUNCSIG$iiiii (func (param i32 i32 i32 i32) (result i32)))
+ (type $FUNCSIG$iiiiii (func (param i32 i32 i32 i32 i32) (result i32)))
+ (type $4 (func (param i32)))
+ (type $5 (func (param i32) (result i32)))
+ (type $6 (func (param i32 i32 i32 i32 i32 i32)))
+ (memory $0 256 256 shared)
+ (func $nonatomics (type $FUNCSIG$i) (result i32)
+  (local $x i32)
+  (nop)
+  (drop
+   (i32.load
+    (i32.const 1028)
+   )
+  )
+  (i32.load
+   (i32.const 1024)
+  )
+ )
+ (func $nonatomic-growmem (type $FUNCSIG$i) (result i32)
+  (local $x i32)
+  (set_local $x
+   (i32.load
+    (grow_memory
+     (i32.const 1)
+    )
+   )
+  )
+  (drop
+   (i32.load
+    (i32.const 1028)
+   )
+  )
+  (get_local $x)
+ )
+ (func $atomics (type $FUNCSIG$v)
+  (local $x i32)
+  (set_local $x
+   (i32.atomic.load
+    (i32.const 1024)
+   )
+  )
+  (drop
+   (i32.atomic.load
+    (i32.const 1028)
+   )
+  )
+  (drop
+   (get_local $x)
+  )
+ )
+ (func $one-atomic (type $FUNCSIG$v)
+  (local $x i32)
+  (set_local $x
+   (i32.load
+    (i32.const 1024)
+   )
+  )
+  (drop
+   (i32.atomic.load
+    (i32.const 1028)
+   )
+  )
+  (drop
+   (get_local $x)
+  )
+ )
+ (func $other-atomic (type $FUNCSIG$v)
+  (local $x i32)
+  (set_local $x
+   (i32.atomic.load
+    (i32.const 1024)
+   )
+  )
+  (drop
+   (i32.load
+    (i32.const 1028)
+   )
+  )
+  (drop
+   (get_local $x)
+  )
+ )
+ (func $atomic-growmem (type $FUNCSIG$i) (result i32)
+  (local $x i32)
+  (set_local $x
+   (i32.load
+    (grow_memory
+     (i32.const 1)
+    )
+   )
+  )
+  (drop
+   (i32.atomic.load
+    (i32.const 1028)
+   )
+  )
+  (get_local $x)
+ )
+ (func $atomicrmw (type $FUNCSIG$v)
+  (local $x i32)
+  (set_local $x
+   (i32.atomic.rmw.add
+    (i32.const 1024)
+    (i32.const 1)
+   )
+  )
+  (drop
+   (i32.atomic.load
+    (i32.const 1028)
+   )
+  )
+  (drop
+   (get_local $x)
+  )
+ )
+ (func $atomic-cmpxchg (type $FUNCSIG$v)
+  (local $x i32)
+  (set_local $x
+   (i32.atomic.rmw.cmpxchg
+    (i32.const 1024)
+    (i32.const 1)
+    (i32.const 2)
+   )
+  )
+  (drop
+   (i32.atomic.load
+    (i32.const 1028)
+   )
+  )
+  (drop
+   (get_local $x)
+  )
+ )
+)
diff --git a/test/passes/simplify-locals.wast b/test/passes/simplify-locals.wast
index 534bd8883..344e0934e 100644
--- a/test/passes/simplify-locals.wast
+++ b/test/passes/simplify-locals.wast
@@ -872,3 +872,61 @@
     )
   )
 )
+(module
+  (memory 256 256 shared)
+  (type $FUNCSIG$v (func))
+  (type $FUNCSIG$i (func (result i32)))
+  (type $FUNCSIG$iiiii (func (param i32 i32 i32 i32) (result i32)))
+  (type $FUNCSIG$iiiiii (func (param i32 i32 i32 i32 i32) (result i32)))
+  (type $4 (func (param i32)))
+  (type $5 (func (param i32) (result i32)))
+  (type $6 (func (param i32 i32 i32 i32 i32 i32)))
+  (func $nonatomics (result i32) ;; loads are reordered
+    (local $x i32)
+    (set_local $x (i32.load (i32.const 1024)))
+    (drop (i32.load (i32.const 1028)))
+    (get_local $x)
+  )
+  (func $nonatomic-growmem (result i32) ;; grow_memory is modeled as modifying memory
+    (local $x i32)
+    (set_local $x (i32.load (grow_memory (i32.const 1))))
+    (drop (i32.load (i32.const 1028)))
+    (get_local $x)
+  )
+  (func $atomics ;; atomic loads don't pass each other
+    (local $x i32)
+    (set_local $x (i32.atomic.load (i32.const 1024)))
+    (drop (i32.atomic.load (i32.const 1028)))
+    (drop (get_local $x))
+  )
+  (func $one-atomic ;; atomic loads don't pass other loads
+    (local $x i32)
+    (set_local $x (i32.load (i32.const 1024)))
+    (drop (i32.atomic.load (i32.const 1028)))
+    (drop (get_local $x))
+  )
+  (func $other-atomic ;; atomic loads don't pass other loads
+    (local $x i32)
+    (set_local $x (i32.atomic.load (i32.const 1024)))
+    (drop (i32.load (i32.const 1028)))
+    (drop (get_local $x))
+  )
+  (func $atomic-growmem (result i32) ;; grow_memory is modeled as modifying memory
+    (local $x i32)
+    (set_local $x (i32.load (grow_memory (i32.const 1))))
+    (drop (i32.atomic.load (i32.const 1028)))
+    (get_local $x)
+  )
+  (func $atomicrmw ;; atomic rmw don't pass loads
+    (local $x i32)
+    (set_local $x (i32.atomic.rmw.add (i32.const 1024) (i32.const 1)))
+    (drop (i32.atomic.load (i32.const 1028)))
+    (drop (get_local $x))
+  )
+  (func $atomic-cmpxchg ;; cmpxchg don't pass loads
+    (local $x i32)
+    (set_local $x (i32.atomic.rmw.cmpxchg (i32.const 1024) (i32.const 1) (i32.const 2)))
+    (drop (i32.atomic.load (i32.const 1028)))
+    (drop (get_local $x))
+  )
+)
\ No newline at end of file