Make validation of stale types stricter (#7097)

We previously allowed valid expressions to have stale types as long as
those stale types were supertypes of the most precise possible types for
the expressions. Allowing stale types like this could mask bugs where we
failed to propagate precise type information, though.

Make validation stricter by requiring all expressions except for control
flow structures to have the most precise possible types. Control flow
structures are exempt because many passes that can refine types wrap the
refined expressions in blocks with the old type to avoid the need for
refinalization. This pattern would be broken and we would need to
refinalize more frequently without this exception for control flow
structures.

Now that all non-control flow expressions must have precise types,
remove functionality relating to building select instructions with
non-precise types. Since finalization of selects now always calculates a
LUB rather than using a provided type, remove the type parameter from
BinaryenSelect in the C and JS APIs.

Now that stale types are no longer valid, fix a bug in TypeSSA where it
failed to refinalize module-level code. This bug previously would not
have caused problems on its own, but the stale types could cause
problems for later runs of Unsubtyping. Now the stale types would cause
TypeSSA output to fail validation.

Also fix a bug where Builder::replaceWithIdenticalType was in fact
replacing with refined types.

Fixes #7087.

10 files changed, 106 insertions, 66 deletions

diff --git a/test/binaryen.js/kitchen-sink.js b/test/binaryen.js/kitchen-sink.js
index da281910f..6e6808ab8 100644
--- a/test/binaryen.js/kitchen-sink.js
+++ b/test/binaryen.js/kitchen-sink.js
@@ -598,7 +598,7 @@ function test_core() {
     module.ref.is_null(module.ref.null(binaryen.externref)),
     module.ref.is_null(module.ref.null(binaryen.funcref)),
     module.ref.is_null(module.ref.func("kitchen()sinker", binaryen.funcref)),
-    module.select(temp10, module.ref.null(binaryen.funcref), module.ref.func("kitchen()sinker", binaryen.funcref), binaryen.funcref),
+    module.select(temp10, module.ref.null(binaryen.funcref), module.ref.func("kitchen()sinker", binaryen.funcref)),
 
     // GC
     module.ref.eq(module.ref.null(binaryen.eqref), module.ref.null(binaryen.eqref)),
diff --git a/test/example/c-api-kitchen-sink.c b/test/example/c-api-kitchen-sink.c
index d3f20e888..a6a196ae6 100644
--- a/test/example/c-api-kitchen-sink.c
+++ b/test/example/c-api-kitchen-sink.c
@@ -1021,7 +1021,7 @@ void test_core() {
       module, 8, 0, 2, 8, BinaryenTypeFloat64(), makeInt32(module, 9), "0"),
     BinaryenStore(module, 4, 0, 0, temp13, temp14, BinaryenTypeInt32(), "0"),
     BinaryenStore(module, 8, 2, 4, temp15, temp16, BinaryenTypeInt64(), "0"),
-    BinaryenSelect(module, temp10, temp11, temp12, BinaryenTypeAuto()),
+    BinaryenSelect(module, temp10, temp11, temp12),
     BinaryenReturn(module, makeInt32(module, 1337)),
     // Tail call
     BinaryenReturnCall(
@@ -1040,8 +1040,7 @@ void test_core() {
       module,
       temp10,
       BinaryenRefNull(module, BinaryenTypeNullFuncref()),
-      BinaryenRefFunc(module, "kitchen()sinker", BinaryenTypeFuncref()),
-      BinaryenTypeFuncref()),
+      BinaryenRefFunc(module, "kitchen()sinker", BinaryenTypeFuncref())),
     // GC
     BinaryenRefEq(module,
                   BinaryenRefNull(module, BinaryenTypeNullref()),
diff --git a/test/lit/basic/reference-types.wast b/test/lit/basic/reference-types.wast
index 44494c80d..22250c9a0 100644
--- a/test/lit/basic/reference-types.wast
+++ b/test/lit/basic/reference-types.wast
@@ -711,7 +711,7 @@
   ;; CHECK-TEXT-NEXT:   )
   ;; CHECK-TEXT-NEXT:  )
   ;; CHECK-TEXT-NEXT:  (drop
-  ;; CHECK-TEXT-NEXT:   (select (result anyref)
+  ;; CHECK-TEXT-NEXT:   (select (result eqref)
   ;; CHECK-TEXT-NEXT:    (local.get $local_eqref)
   ;; CHECK-TEXT-NEXT:    (ref.i31
   ;; CHECK-TEXT-NEXT:     (i32.const 0)
@@ -1314,7 +1314,7 @@
   ;; CHECK-BIN-NEXT:   )
   ;; CHECK-BIN-NEXT:  )
   ;; CHECK-BIN-NEXT:  (drop
-  ;; CHECK-BIN-NEXT:   (select (result anyref)
+  ;; CHECK-BIN-NEXT:   (select (result eqref)
   ;; CHECK-BIN-NEXT:    (local.get $local_eqref)
   ;; CHECK-BIN-NEXT:    (ref.i31
   ;; CHECK-BIN-NEXT:     (i32.const 0)
@@ -2651,7 +2651,7 @@
 ;; CHECK-BIN-NODEBUG-NEXT:   )
 ;; CHECK-BIN-NODEBUG-NEXT:  )
 ;; CHECK-BIN-NODEBUG-NEXT:  (drop
-;; CHECK-BIN-NODEBUG-NEXT:   (select (result anyref)
+;; CHECK-BIN-NODEBUG-NEXT:   (select (result eqref)
 ;; CHECK-BIN-NODEBUG-NEXT:    (local.get $0)
 ;; CHECK-BIN-NODEBUG-NEXT:    (ref.i31
 ;; CHECK-BIN-NODEBUG-NEXT:     (i32.const 0)
diff --git a/test/lit/passes/cfp.wast b/test/lit/passes/cfp.wast
index 461baa373..e70cfc639 100644
--- a/test/lit/passes/cfp.wast
+++ b/test/lit/passes/cfp.wast
@@ -2332,9 +2332,11 @@
   ;; CHECK-NEXT:  (struct.set $A 0
   ;; CHECK-NEXT:   (select (result (ref null $A))
   ;; CHECK-NEXT:    (ref.null none)
-  ;; CHECK-NEXT:    (local.tee $B
-  ;; CHECK-NEXT:     (struct.new $B
-  ;; CHECK-NEXT:      (i32.const 20)
+  ;; CHECK-NEXT:    (block (result (ref null $A))
+  ;; CHECK-NEXT:     (local.tee $B
+  ;; CHECK-NEXT:      (struct.new $B
+  ;; CHECK-NEXT:       (i32.const 20)
+  ;; CHECK-NEXT:      )
   ;; CHECK-NEXT:     )
   ;; CHECK-NEXT:    )
   ;; CHECK-NEXT:    (i32.const 0)
@@ -2361,10 +2363,12 @@
       ;; This select is used to keep the type that reaches the struct.set $A,
       ;; and not $B, so it looks like a perfect copy of $A->$A.
       (select (result (ref null $A))
-        (ref.null $A)
-        (local.tee $B
-          (struct.new $B
-            (i32.const 20)
+        (ref.null none)
+        (block (result (ref null $A))
+          (local.tee $B
+            (struct.new $B
+              (i32.const 20)
+            )
           )
         )
         (i32.const 0)
diff --git a/test/lit/passes/coalesce-locals-gc.wast b/test/lit/passes/coalesce-locals-gc.wast
index d2b6fcaeb..59232d1b4 100644
--- a/test/lit/passes/coalesce-locals-gc.wast
+++ b/test/lit/passes/coalesce-locals-gc.wast
@@ -25,7 +25,7 @@
  (global $nn-tuple-global (mut (tuple (ref any) i32)) (tuple.make 2 (ref.i31 (i32.const 0)) (i32.const 1)))
 
 
- ;; CHECK:      (func $test-dead-get-non-nullable (type $6) (param $0 (ref struct))
+ ;; CHECK:      (func $test-dead-get-non-nullable (type $7) (param $0 (ref struct))
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (block (result (ref struct))
@@ -43,7 +43,7 @@
   )
  )
 
- ;; CHECK:      (func $br_on_null (type $7) (param $0 (ref null $array)) (result (ref null $array))
+ ;; CHECK:      (func $br_on_null (type $8) (param $0 (ref null $array)) (result (ref null $array))
  ;; CHECK-NEXT:  (block $label$1 (result (ref null $array))
  ;; CHECK-NEXT:   (block $label$2
  ;; CHECK-NEXT:    (br $label$1
@@ -79,7 +79,7 @@
   )
  )
 
- ;; CHECK:      (func $nn-dead (type $4)
+ ;; CHECK:      (func $nn-dead (type $3)
  ;; CHECK-NEXT:  (local $0 funcref)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (ref.func $nn-dead)
@@ -118,7 +118,7 @@
   )
  )
 
- ;; CHECK:      (func $nn-dead-nameless (type $4)
+ ;; CHECK:      (func $nn-dead-nameless (type $3)
  ;; CHECK-NEXT:  (local $0 (ref func))
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (ref.func $nn-dead)
@@ -149,26 +149,24 @@
   )
  )
 
- ;; CHECK:      (func $unreachable-get-null (type $4)
+ ;; CHECK:      (func $unreachable-get-null (type $3)
  ;; CHECK-NEXT:  (local $0 anyref)
  ;; CHECK-NEXT:  (local $1 i31ref)
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (block (result anyref)
- ;; CHECK-NEXT:    (unreachable)
+ ;; CHECK-NEXT:    (ref.null none)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (block (result i31ref)
- ;; CHECK-NEXT:    (ref.i31
- ;; CHECK-NEXT:     (i32.const 0)
- ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (ref.null none)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $unreachable-get-null
-  ;; Check that we don't replace the local.get $null with a ref.null, which
-  ;; would have a more precise type.
+  ;; Check that we don't replace the local.get $null with just a ref.null, which
+  ;; would have a more precise type. We wrap the ref.null in a block instead.
   (local $null-any anyref)
   (local $null-i31 i31ref)
   (unreachable)
@@ -180,6 +178,32 @@
   )
  )
 
+ ;; CHECK:      (func $unreachable-get-tuple (type $3)
+ ;; CHECK-NEXT:  (local $0 (tuple anyref i32))
+ ;; CHECK-NEXT:  (unreachable)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (tuple.extract 2 0
+ ;; CHECK-NEXT:    (block (type $6) (result anyref i32)
+ ;; CHECK-NEXT:     (tuple.make 2
+ ;; CHECK-NEXT:      (ref.null none)
+ ;; CHECK-NEXT:      (i32.const 0)
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $unreachable-get-tuple
+  (local $tuple (tuple anyref i32))
+  (unreachable)
+  (drop
+   ;; If we replaced the get with something with a more refined type, this
+   ;; extract would end up with a stale type.
+   (tuple.extract 2 0
+    (local.get $tuple)
+   )
+  )
+ )
+
  ;; CHECK:      (func $remove-tee-refinalize (type $5) (param $0 (ref null $A)) (param $1 (ref null $B)) (result structref)
  ;; CHECK-NEXT:  (struct.get $B 0
  ;; CHECK-NEXT:   (local.get $1)
@@ -218,16 +242,14 @@
   )
  )
 
- ;; CHECK:      (func $replace-i31-local (type $8) (result i32)
+ ;; CHECK:      (func $replace-i31-local (type $9) (result i32)
  ;; CHECK-NEXT:  (local $0 i31ref)
  ;; CHECK-NEXT:  (i32.add
  ;; CHECK-NEXT:   (unreachable)
  ;; CHECK-NEXT:   (ref.test (ref i31)
  ;; CHECK-NEXT:    (ref.cast i31ref
  ;; CHECK-NEXT:     (block (result i31ref)
- ;; CHECK-NEXT:      (ref.i31
- ;; CHECK-NEXT:       (i32.const 0)
- ;; CHECK-NEXT:      )
+ ;; CHECK-NEXT:      (ref.null none)
  ;; CHECK-NEXT:     )
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
@@ -250,7 +272,7 @@
   )
  )
 
- ;; CHECK:      (func $replace-struct-param (type $9) (param $0 f64) (param $1 (ref null $A)) (result f32)
+ ;; CHECK:      (func $replace-struct-param (type $10) (param $0 f64) (param $1 (ref null $A)) (result f32)
  ;; CHECK-NEXT:  (call $replace-struct-param
  ;; CHECK-NEXT:   (block (result f64)
  ;; CHECK-NEXT:    (unreachable)
@@ -278,7 +300,7 @@
   )
  )
 
- ;; CHECK:      (func $test (type $10) (param $0 (ref any)) (result (ref any) i32)
+ ;; CHECK:      (func $test (type $11) (param $0 (ref any)) (result (ref any) i32)
  ;; CHECK-NEXT:  (local $1 (tuple anyref i32))
  ;; CHECK-NEXT:  (tuple.drop 2
  ;; CHECK-NEXT:   (tuple.make 2
diff --git a/test/lit/passes/issue-7087.wast b/test/lit/passes/issue-7087.wast
new file mode 100644
index 000000000..096c88e5d
--- /dev/null
+++ b/test/lit/passes/issue-7087.wast
@@ -0,0 +1,31 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; Regression test for a bug in TypeSSA. TypeSSA creates a new subtype, $t_1,
+;; for use in the struct.new in the global initializer, but ran ReFinalize only
+;; on function code, not on module-level code. As a result, the tuple.make
+;; result type still used $t instead of $t_1 after TypeSSA. This stale type
+;; caused Unsubtyping to incorrectly break the subtype relationship between $t
+;; and $t_1, leading to a validation error. The fix was to refinalize
+;; module-level code in TypeSSA and fix the validator so it would have caught
+;; the stale type.
+
+;; RUN: wasm-opt %s -all --type-ssa --unsubtyping -S -o - | filecheck %s
+
+(module
+ ;; CHECK:      (rec
+ ;; CHECK-NEXT:  (type $t (sub (struct)))
+ (type $t (sub (struct)))
+
+ ;; CHECK:       (type $t_1 (sub $t (struct)))
+
+ ;; CHECK:      (global $g (tuple i32 (ref null $t)) (tuple.make 2
+ ;; CHECK-NEXT:  (i32.const 0)
+ ;; CHECK-NEXT:  (struct.new_default $t_1)
+ ;; CHECK-NEXT: ))
+ (global $g (tuple i32 (ref null $t))
+  (tuple.make 2
+   (i32.const 0)
+   (struct.new $t)
+  )
+ )
+)
diff --git a/test/lit/passes/optimize-instructions-gc-tnh.wast b/test/lit/passes/optimize-instructions-gc-tnh.wast
index ff2975766..c930f2fc1 100644
--- a/test/lit/passes/optimize-instructions-gc-tnh.wast
+++ b/test/lit/passes/optimize-instructions-gc-tnh.wast
@@ -497,7 +497,7 @@
   )
 
   ;; TNH:      (func $null.arm.null.effects (type $void)
-  ;; TNH-NEXT:  (block ;; (replaces unreachable StructSet we can't emit)
+  ;; TNH-NEXT:  (block
   ;; TNH-NEXT:   (drop
   ;; TNH-NEXT:    (select
   ;; TNH-NEXT:     (unreachable)
@@ -505,9 +505,6 @@
   ;; TNH-NEXT:     (call $get-i32)
   ;; TNH-NEXT:    )
   ;; TNH-NEXT:   )
-  ;; TNH-NEXT:   (drop
-  ;; TNH-NEXT:    (i32.const 1)
-  ;; TNH-NEXT:   )
   ;; TNH-NEXT:   (unreachable)
   ;; TNH-NEXT:  )
   ;; TNH-NEXT:  (block
@@ -523,7 +520,7 @@
   ;; TNH-NEXT:  )
   ;; TNH-NEXT: )
   ;; NO_TNH:      (func $null.arm.null.effects (type $void)
-  ;; NO_TNH-NEXT:  (block ;; (replaces unreachable StructSet we can't emit)
+  ;; NO_TNH-NEXT:  (block
   ;; NO_TNH-NEXT:   (drop
   ;; NO_TNH-NEXT:    (select
   ;; NO_TNH-NEXT:     (unreachable)
@@ -531,9 +528,6 @@
   ;; NO_TNH-NEXT:     (call $get-i32)
   ;; NO_TNH-NEXT:    )
   ;; NO_TNH-NEXT:   )
-  ;; NO_TNH-NEXT:   (drop
-  ;; NO_TNH-NEXT:    (i32.const 1)
-  ;; NO_TNH-NEXT:   )
   ;; NO_TNH-NEXT:   (unreachable)
   ;; NO_TNH-NEXT:  )
   ;; NO_TNH-NEXT:  (block
diff --git a/test/lit/passes/remove-unused-brs_all-features.wast b/test/lit/passes/remove-unused-brs_all-features.wast
index 4e722a043..e2d89a5ea 100644
--- a/test/lit/passes/remove-unused-brs_all-features.wast
+++ b/test/lit/passes/remove-unused-brs_all-features.wast
@@ -119,7 +119,7 @@
  (func $i32_=>_none (param i32)
  )
  ;; CHECK:      (func $selectify (type $6) (param $x i32) (result funcref)
- ;; CHECK-NEXT:  (select (result funcref)
+ ;; CHECK-NEXT:  (select (result (ref func))
  ;; CHECK-NEXT:   (ref.func $none_=>_i32)
  ;; CHECK-NEXT:   (ref.func $i32_=>_none)
  ;; CHECK-NEXT:   (local.get $x)
diff --git a/test/lit/passes/ssa.wast b/test/lit/passes/ssa.wast
index b082cd888..0d696f75a 100644
--- a/test/lit/passes/ssa.wast
+++ b/test/lit/passes/ssa.wast
@@ -58,4 +58,20 @@
    (unreachable)
   )
  )
+
+ ;; CHECK:      (func $null-tuple (type $4) (result funcref)
+ ;; CHECK-NEXT:  (local $tuple (tuple i32 funcref))
+ ;; CHECK-NEXT:  (tuple.extract 2 1
+ ;; CHECK-NEXT:   (tuple.make 2
+ ;; CHECK-NEXT:    (i32.const 0)
+ ;; CHECK-NEXT:    (ref.null nofunc)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $null-tuple (result funcref)
+  (local $tuple (tuple i32 funcref))
+  (tuple.extract 2 1
+   (local.get $tuple)
+  )
+ )
 )
diff --git a/test/lit/select-gc.wat b/test/lit/select-gc.wat
deleted file mode 100644
index bd1394950..000000000
--- a/test/lit/select-gc.wat
+++ /dev/null
@@ -1,26 +0,0 @@
-;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
-
-;; RUN: wasm-opt -all --roundtrip %s -S -o - | filecheck %s
-
-;; Check that annotated select is propery roundtripped, even if the type is
-;; only used in that one place in the whole module.
-
-(module
-  ;; CHECK:      (type $struct (struct))
-  (type $struct (struct))
-
-  ;; CHECK:      (func $foo (type $0) (result anyref)
-  ;; CHECK-NEXT:  (select (result (ref null $struct))
-  ;; CHECK-NEXT:   (ref.null none)
-  ;; CHECK-NEXT:   (ref.null none)
-  ;; CHECK-NEXT:   (i32.const 1)
-  ;; CHECK-NEXT:  )
-  ;; CHECK-NEXT: )
-  (func $foo (result anyref)
-    (select (result (ref null $struct))
-      (ref.null any)
-      (ref.null eq)
-      (i32.const 1)
-    )
-  )
-)