[Wasm GC] Do not merge supertypes into subtypes (#5439)

In TypeMerging we previously merged all subsequent types in a refined partition
into whichever type happened to be first in the partition, but when that first
type happened to be a subtype of one of the other types in the partition, that
would cause type-updating.cpp to try to update that subtype's supertype to be
itself, causing an assertion failure.

Fix the problem by ensuring that the merge target is not a subtype of any other
types in the partition.

2 files changed, 54 insertions, 3 deletions

diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
index 6f39d586f..5623ecdb9 100644
--- a/src/passes/TypeMerging.cpp
+++ b/src/passes/TypeMerging.cpp
@@ -280,10 +280,15 @@ void TypeMerging::run(Module* module_) {
   // The types we can merge mapped to the type we are merging them into.
   TypeUpdates merges;
 
-  // Merge each refined partition into a single type.
+  // Merge each refined partition into a single type. We should only merge into
+  // supertypes or siblings because if we try to merge into a subtype then we
+  // will accidentally set that subtype to be its own supertype.
   for (const auto& partition : refinedPartitions) {
-    for (size_t i = 1; i < partition.size(); ++i) {
-      merges[partition[i]] = partition[0];
+    auto target = *HeapTypeOrdering::SupertypesFirst(partition).begin();
+    for (auto type : partition) {
+      if (type != target) {
+        merges[type] = target;
+      }
     }
   }
 
diff --git a/test/lit/passes/type-merging.wast b/test/lit/passes/type-merging.wast
index c20e212c3..6be3b05ee 100644
--- a/test/lit/passes/type-merging.wast
+++ b/test/lit/passes/type-merging.wast
@@ -232,6 +232,35 @@
 
 (module
   (rec
+    (type $A (struct         (ref null $X)))
+    (type $B (struct_subtype (ref null $Y) $A))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $X (struct (field (ref null $X))))
+    (type $X (struct         (ref null $A)))
+    (type $Y (struct_subtype (ref null $B) $X))
+  )
+
+  ;; CHECK:       (type $none_=>_none (func))
+
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (local $a (ref null $X))
+  ;; CHECK-NEXT:  (local $b (ref null $X))
+  ;; CHECK-NEXT:  (local $x (ref null $X))
+  ;; CHECK-NEXT:  (local $y (ref null $X))
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $foo
+    ;; As above, but now the A->B and X->Y chains are not differentiated by the
+    ;; i32 and f32, so all four types can be merged into a single type.
+    (local $a (ref null $A))
+    (local $b (ref null $B))
+    (local $x (ref null $X))
+    (local $y (ref null $Y))
+  )
+)
+
+(module
+  (rec
     ;; CHECK:      (rec
     ;; CHECK-NEXT:  (type $A (struct (field (ref null $A))))
     (type $A (struct         (ref null $X)))
@@ -644,6 +673,23 @@
   )
 )
 
+;; Regression test for a bug in which we tried to merge A into B instead of the
+;; other way around, causing an assertion failure in type-updating.cpp.
+(module
+  (rec
+    ;; CHECK:      (type $A (func (param (ref null $A)) (result (ref null $A))))
+    (type $A (func (param (ref null $B)) (result (ref null $A))))
+    (type $B (func_subtype (param (ref null $A)) (result (ref null $B)) $A))
+  )
+
+  ;; CHECK:      (func $0 (type $A) (param $0 (ref null $A)) (result (ref null $A))
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $0 (type $B) (param $0 (ref null $A)) (result (ref null $B))
+    (unreachable)
+  )
+)
+
 ;; Check that a ref.test inhibits merging (ref.cast is already checked above).
 (module
   ;; CHECK:      (rec