Fix extra unreachable generation (#2266)

Currently various expressions handle this differently, and now we
consistently follow this rules:

---
For all non-control-flow value-returning instructions, if a type of an
expression is unreachable, we emit an unreachable and don't emit the
instruction itself. If we don't emit an unreachable, instructions that
follow can have validation failure in wasm binary format. For example:
```
[unreachable] (f32.add
[unreachable]   (i32.eqz
[unreachable]     (unreachable)
                )
                ...
              )
```
This is a valid prgram in binaryen IR, because the unreachable type
propagates out of an expression, making both i32.eqz and f32.add
unreachable. But in binary format, this becomes:
```
unreachable
i32.eqz
f32.add       ;; validation failure; it expects f32 but takes an i32!
```
And here f32.add causes validation failure in wasm validation. So in this
case we add an unreachable to prevent following instructions to consume
the current value (here i32.eqz).

In actual tests, I used `global.get` to an f32 global, which does not
return a value, instead of `f32.add`, because `f32.add` itself will not
be emitted if one of argument is unreachable.

---

So the changes are:
- For instructions that don't return a value, removes unreachable
  emitting code if it exists.
- Add the unreachable emitting code for value-returning instructions if
  there isn't one.
- Check for unreachability only once after emitting all children for
  atomic instructions. Currently only atomic instructions check
  unreachability after visiting each children and bail out right after,
  which is valid, but not consistent with others.
- Don't emit an extra unreachable after a return (and return_call). I
  guess it is unnecessary.

6 files changed, 357 insertions, 1 deletions

diff --git a/test/extra-unreachable.wast b/test/extra-unreachable.wast
new file mode 100644
index 000000000..441498de6
--- /dev/null
+++ b/test/extra-unreachable.wast
@@ -0,0 +1,180 @@
+(module
+  (type $ii (param i32) (result i32))
+  (memory (shared 1 1))
+  (table 0 funcref)
+  (global $g (mut f32) (f32.const 0))
+
+  (func $foo (param i32) (result i32) (i32.const 0))
+
+  (func $test_function_block
+    ;; block, which has unreachable type, can be omitted here because it is the
+    ;; only expression within a function. We emit an extra unreachable at the
+    ;; end.
+    (block
+      (unreachable)
+      (nop)
+    )
+  )
+
+  (func $test
+    ;; block has unreachable type. We emit an unreachable at the end of the
+    ;; block and also outside the block too.
+    (block
+      (i32.eqz (unreachable))
+    )
+
+    ;; If an if's condition is unreachable, don't emit the if and emit an
+    ;; unreachable instead.
+    (if
+      (unreachable)
+      (nop)
+      (nop)
+    )
+
+    ;; If an if is unreachable, i.e., the both sides are unreachable, we emit
+    ;; an extra unreachable after the if.
+    (if
+      (i32.const 1)
+      (unreachable)
+      (unreachable)
+    )
+
+    ;; If a br_if's type is unreachable, emit an extra unreachable after it
+    (block
+      (br_if 0 (unreachable))
+    )
+
+    ;; If a br_table is not reachable, emit an unreachable instead
+    (block $l
+      (block $default
+        (br_table $l $default
+          (unreachable)
+        )
+      )
+    )
+
+    ;; For all tests below, when a value-returning expression is unreachable,
+    ;; emit an unreachable instead of the operation, to prevent it from being
+    ;; consumed by the next operation.
+    ;;
+    ;; Here global.set is used to consume the value. If an unreachable is not
+    ;; emitted, the instruction itself will be consumed by global.set and will
+    ;; result in a type validation failure, because it expects a f32 but gets an
+    ;; i32. The reason we use global.set is the instruction does not return a
+    ;; value, so it will be emitted even if its argument is unreachable.
+
+    ;; call / call_indirect
+    (global.set $g
+      (call $foo (unreachable))
+    )
+    (global.set $g
+      (call_indirect (type $ii) (unreachable))
+    )
+
+    ;; unary
+    (global.set $g
+      (i32.eqz (unreachable))
+    )
+
+    ;; binary
+    (global.set $g
+      (i32.add
+        (unreachable)
+        (i32.const 0)
+      )
+    )
+
+    ;; select
+    (global.set $g
+      (select
+        (unreachable)
+        (i32.const 0)
+        (i32.const 0)
+      )
+    )
+
+    ;; load
+    (global.set $g
+      (i32.load (unreachable))
+    )
+    (global.set $g
+      (i32.atomic.load (unreachable))
+    )
+
+    ;; atomic.rmw
+    (global.set $g
+      (i32.atomic.rmw.add
+        (unreachable)
+        (i32.const 0)
+      )
+    )
+
+    ;; atomic.cmpxchg
+    (global.set $g
+      (i32.atomic.rmw.cmpxchg
+        (unreachable)
+        (i32.const 0)
+        (i32.const 0)
+      )
+    )
+
+    ;; atomic.wait
+    (global.set $g
+      (i32.atomic.wait
+        (unreachable)
+        (i32.const 0)
+        (i64.const 0)
+      )
+    )
+
+    ;; atomic.notify
+    (global.set $g
+      (atomic.notify
+        (unreachable)
+        (i32.const 0)
+      )
+    )
+
+    ;; SIMD extract
+    (global.set $g
+      (i32x4.extract_lane 0
+        (unreachable)
+      )
+    )
+
+    ;; SIMD replace
+    (global.set $g
+      (i32x4.replace_lane 0
+        (unreachable)
+        (i32.const 0)
+      )
+    )
+
+    ;; SIMD shuffle
+    (global.set $g
+      (v8x16.shuffle 0 17 2 19 4 21 6 23 8 25 10 27 12 29 14 31
+        (unreachable)
+        (unreachable)
+      )
+    )
+
+    ;; SIMD bitselect
+    (global.set $g
+      (v128.bitselect
+        (unreachable)
+        (unreachable)
+        (unreachable)
+      )
+    )
+
+    ;; SIMD shift
+    (global.set $g
+      (i32x4.shl
+        (unreachable)
+        (i32.const 0)
+      )
+    )
+
+    ;; TODO Add exception handling instructions
+  )
+)
diff --git a/test/extra-unreachable.wast.from-wast b/test/extra-unreachable.wast.from-wast
new file mode 100644
index 000000000..5d794148e
--- /dev/null
+++ b/test/extra-unreachable.wast.from-wast
@@ -0,0 +1,139 @@
+(module
+ (type $ii (func))
+ (type $FUNCSIG$ii (func (param i32) (result i32)))
+ (memory $0 (shared 1 1))
+ (table $0 0 funcref)
+ (global $g (mut f32) (f32.const 0))
+ (func $foo (; 0 ;) (type $FUNCSIG$ii) (param $0 i32) (result i32)
+  (i32.const 0)
+ )
+ (func $test_function_block (; 1 ;) (type $ii)
+  (block $block
+   (unreachable)
+   (nop)
+  )
+ )
+ (func $test (; 2 ;) (type $ii)
+  (block $block
+   (i32.eqz
+    (unreachable)
+   )
+  )
+  (if
+   (unreachable)
+   (nop)
+   (nop)
+  )
+  (if
+   (i32.const 1)
+   (unreachable)
+   (unreachable)
+  )
+  (block $block1
+   (br_if $block1
+    (unreachable)
+   )
+  )
+  (block $l
+   (block $default
+    (br_table $l $default
+     (unreachable)
+    )
+   )
+  )
+  (global.set $g
+   (call $foo
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (call_indirect (type $ii)
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (i32.eqz
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (i32.add
+    (unreachable)
+    (i32.const 0)
+   )
+  )
+  (global.set $g
+   (select
+    (unreachable)
+    (i32.const 0)
+    (i32.const 0)
+   )
+  )
+  (global.set $g
+   (i32.load
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (i32.atomic.load
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (i32.atomic.rmw.add
+    (unreachable)
+    (i32.const 0)
+   )
+  )
+  (global.set $g
+   (i32.atomic.rmw.cmpxchg
+    (unreachable)
+    (i32.const 0)
+    (i32.const 0)
+   )
+  )
+  (global.set $g
+   (i32.atomic.wait
+    (unreachable)
+    (i32.const 0)
+    (i64.const 0)
+   )
+  )
+  (global.set $g
+   (atomic.notify
+    (unreachable)
+    (i32.const 0)
+   )
+  )
+  (global.set $g
+   (i32x4.extract_lane 0
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (i32x4.replace_lane 0
+    (unreachable)
+    (i32.const 0)
+   )
+  )
+  (global.set $g
+   (v8x16.shuffle 0 17 2 19 4 21 6 23 8 25 10 27 12 29 14 31
+    (unreachable)
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (v128.bitselect
+    (unreachable)
+    (unreachable)
+    (unreachable)
+   )
+  )
+  (global.set $g
+   (i32x4.shl
+    (unreachable)
+    (i32.const 0)
+   )
+  )
+ )
+)
diff --git a/test/extra-unreachable.wast.fromBinary b/test/extra-unreachable.wast.fromBinary
new file mode 100644
index 000000000..11c23e009
--- /dev/null
+++ b/test/extra-unreachable.wast.fromBinary
@@ -0,0 +1,19 @@
+(module
+ (type $0 (func))
+ (type $1 (func (param i32) (result i32)))
+ (memory $0 (shared 1 1))
+ (table $0 0 funcref)
+ (global $global$0 (mut f32) (f32.const 0))
+ (func $foo (; 0 ;) (type $1) (param $0 i32) (result i32)
+  (i32.const 0)
+ )
+ (func $test_function_block (; 1 ;) (type $0)
+  (unreachable)
+ )
+ (func $test (; 2 ;) (type $0)
+  (block $label$1
+   (unreachable)
+  )
+ )
+)
+
diff --git a/test/extra-unreachable.wast.fromBinary.noDebugInfo b/test/extra-unreachable.wast.fromBinary.noDebugInfo
new file mode 100644
index 000000000..1daf0114c
--- /dev/null
+++ b/test/extra-unreachable.wast.fromBinary.noDebugInfo
@@ -0,0 +1,19 @@
+(module
+ (type $0 (func))
+ (type $1 (func (param i32) (result i32)))
+ (memory $0 (shared 1 1))
+ (table $0 0 funcref)
+ (global $global$0 (mut f32) (f32.const 0))
+ (func $0 (; 0 ;) (type $1) (param $0 i32) (result i32)
+  (i32.const 0)
+ )
+ (func $1 (; 1 ;) (type $0)
+  (unreachable)
+ )
+ (func $2 (; 2 ;) (type $0)
+  (block $label$1
+   (unreachable)
+  )
+ )
+)
+
diff --git a/test/passes/remove-unused-brs_generate-stack-ir_print-stack-ir.txt b/test/passes/remove-unused-brs_generate-stack-ir_print-stack-ir.txt
index 80c850db5..937fe59a3 100644
--- a/test/passes/remove-unused-brs_generate-stack-ir_print-stack-ir.txt
+++ b/test/passes/remove-unused-brs_generate-stack-ir_print-stack-ir.txt
@@ -9,7 +9,6 @@
       unreachable
      end
      unreachable
-     local.tee $var$0
      unreachable
      unreachable
     end
diff --git a/test/unit/input/tail_call_target_feature.wasm b/test/unit/input/tail_call_target_feature.wasm
index 651c92ec8..be4b73caf 100755
--- a/test/unit/input/tail_call_target_feature.wasm
+++ b/test/unit/input/tail_call_target_feature.wasm