[Wasm GC] Use DFA minimization to merge types (#5432)

Analyze type merging candidates as states in a DFA, using a partition refining
DFA minimization algorithm to more aggressively find sets of mergeable types.
The new implementation can merge types that the previous iteration would have
taken an arbitrary number of iterations to merge or would not have been able to
merge at all.

The new implementation is also careful in its treatment of private and public
types and should work as-is under an open world assumption or a relaxed
closed-world assumption that admits more public types. Specifically, the new
code avoids merging public types into their supertypes, but still allows
private subtypes to be merged into their public supertypes.

The new implementation supports merging function types, which the old
implementation did not.

Finally, the new implementation is able to merge identical sibling types even
when the analysis determines that they cannot be merged into their common
supertype. Extending this capability to sibling top-level types without
nontrivial supertypes is left to a follow-on PR.

2 files changed, 285 insertions, 71 deletions

diff --git a/test/lit/passes/type-merging-tnh.wast b/test/lit/passes/type-merging-tnh.wast
index 5099760de..fefdb00e3 100644
--- a/test/lit/passes/type-merging-tnh.wast
+++ b/test/lit/passes/type-merging-tnh.wast
@@ -88,12 +88,10 @@
   )
 )
 
-;; call_indirect should not inhibit merging if traps never happen, but we
-;; haven't implemented function type merging yet TODO.
+;; call_indirect should not inhibit merging if traps never happen.
 (module
   ;; CHECK:      (type $A (func))
   (type $A (func))
-  ;; CHECK:      (type $B (func_subtype $A))
   (type $B (func_subtype $A))
 
   (table 1 1 (ref null $A))
@@ -101,7 +99,7 @@
   ;; CHECK:      (table $0 1 1 (ref null $A))
 
   ;; CHECK:      (func $test (type $A)
-  ;; CHECK-NEXT:  (call_indirect $0 (type $B)
+  ;; CHECK-NEXT:  (call_indirect $0 (type $A)
   ;; CHECK-NEXT:   (i32.const 0)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT: )
diff --git a/test/lit/passes/type-merging.wast b/test/lit/passes/type-merging.wast
index b4b84f94a..578d84ebb 100644
--- a/test/lit/passes/type-merging.wast
+++ b/test/lit/passes/type-merging.wast
@@ -1,30 +1,41 @@
 ;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
-;; RUN: foreach %s %t wasm-opt --nominal --closed-world --type-merging -all -S -o - | filecheck %s
+;; RUN: foreach %s %t wasm-opt --hybrid --closed-world --type-merging --remove-unused-types -all -S -o - | filecheck %s
 
 (module
-  ;; CHECK:      (type $A (struct (field i32)))
-  (type $A (struct_subtype (field i32) data))
-  (type $B (struct_subtype (field i32) $A))
-  ;; CHECK:      (type $D (struct_subtype (field i32) $A))
-
-  ;; CHECK:      (type $none_=>_none (func))
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $A (struct (field anyref)))
+    (type $A (struct_subtype (field anyref) data))
+    (type $B (struct_subtype (field anyref) $A))
+    ;; CHECK:       (type $F (struct_subtype (field anyref) $A))
+
+    ;; CHECK:       (type $E (struct_subtype (field eqref) $A))
+
+    ;; CHECK:       (type $D (struct_subtype (field (ref any)) $A))
+
+    ;; CHECK:       (type $C (struct_subtype (field anyref) (field f64) $A))
+    (type $C (struct_subtype (field anyref) (field f64) $A))
+    (type $D (struct_subtype (field (ref any)) $A))
+    (type $E (struct_subtype (field eqref) $A))
+    (type $F (struct_subtype (field anyref) $A))
+  )
 
-  ;; CHECK:      (type $C (struct_subtype (field i32) (field f64) $A))
-  (type $C (struct_subtype (field i32) (field f64) $A))
-  (type $D (struct_subtype (field i32) $A))
+  ;; CHECK:       (type $none_=>_none (func))
 
   ;; CHECK:      (func $foo (type $none_=>_none)
   ;; CHECK-NEXT:  (local $a (ref null $A))
   ;; CHECK-NEXT:  (local $b (ref null $A))
   ;; CHECK-NEXT:  (local $c (ref null $C))
   ;; CHECK-NEXT:  (local $d (ref null $D))
+  ;; CHECK-NEXT:  (local $e (ref null $E))
+  ;; CHECK-NEXT:  (local $f (ref null $F))
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (ref.cast null $A
   ;; CHECK-NEXT:    (local.get $a)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (drop
-  ;; CHECK-NEXT:   (ref.cast null $D
+  ;; CHECK-NEXT:   (ref.cast null $F
   ;; CHECK-NEXT:    (local.get $a)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:  )
@@ -36,8 +47,12 @@
     (local $b (ref null $B))
     ;; $C cannot because it adds a field.
     (local $c (ref null $C))
-    ;; $D cannot because it has a cast.
+    ;; $D cannot because it refines a field's nullability.
     (local $d (ref null $D))
+    ;; $E cannot because it refines a field's heap type.
+    (local $e (ref null $E))
+    ;; $F cannot because it has a cast.
+    (local $f (ref null $F))
 
     ;; A cast of $A has no effect.
     (drop
@@ -45,9 +60,9 @@
         (local.get $a)
       )
     )
-    ;; A cast of $D prevents it from being merged.
+    ;; A cast of $F prevents it from being merged.
     (drop
-      (ref.cast null $D
+      (ref.cast null $F
         (local.get $a)
       )
     )
@@ -56,17 +71,18 @@
 
 ;; Multiple levels of merging.
 (module
-  ;; CHECK:      (type $A (struct (field i32)))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field i32)))
   (type $A (struct_subtype (field i32) data))
   (type $B (struct_subtype (field i32) $A))
   (type $C (struct_subtype (field i32) $B))
-  ;; CHECK:      (type $D (struct_subtype (field i32) (field f64) $A))
+  ;; CHECK:       (type $D (struct_subtype (field i32) (field f64) $A))
   (type $D (struct_subtype (field i32) (field f64) $A))
   (type $E (struct_subtype (field i32) (field f64) $D))
   (type $F (struct_subtype (field i32) (field f64) $E))
   (type $G (struct_subtype (field i32) (field f64) $F))
 
-  ;; CHECK:      (type $none_=>_none (func))
+  ;; CHECK:       (type $none_=>_none (func))
 
   ;; CHECK:      (func $foo (type $none_=>_none)
   ;; CHECK-NEXT:  (local $a (ref null $A))
@@ -99,19 +115,18 @@
 ;; in which we have two "merge points" that things get merged into. The results
 ;; should remain the same as before, everything merged into either $A or $D.
 (module
-  ;; CHECK:      (type $A (struct (field i32)))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field i32)))
   (type $A (struct_subtype (field i32) data))
-  ;; CHECK:      (type $B (struct_subtype (field i32) $A))
   (type $B (struct_subtype (field i32) $A))
-  ;; CHECK:      (type $C (struct_subtype (field i32) $B))
   (type $C (struct_subtype (field i32) $B))
-  ;; CHECK:      (type $D (struct_subtype (field i32) (field f64) $C))
+  ;; CHECK:       (type $D (struct_subtype (field i32) (field f64) $A))
   (type $D (struct_subtype (field i32) (field f64) $C)) ;; this line changed
   (type $E (struct_subtype (field i32) (field f64) $D))
   (type $F (struct_subtype (field i32) (field f64) $E))
   (type $G (struct_subtype (field i32) (field f64) $F))
 
-  ;; CHECK:      (type $none_=>_none (func))
+  ;; CHECK:       (type $none_=>_none (func))
 
   ;; CHECK:      (func $foo (type $none_=>_none)
   ;; CHECK-NEXT:  (local $a (ref null $A))
@@ -135,13 +150,17 @@
 )
 
 (module
-  ;; CHECK:      (type $A (struct (field (ref null $A))))
-  (type $A (struct_subtype (field (ref null $A)) data))
-  (type $B (struct_subtype (field (ref null $A)) $A))
-  ;; CHECK:      (type $none_=>_none (func))
-
-  ;; CHECK:      (type $C (struct_subtype (field (ref null $A)) $A))
-  (type $C (struct_subtype (field (ref null $B)) $A))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $X (struct ))
+  (type $X (struct))
+  (type $Y (struct_subtype $X))
+  ;; CHECK:       (type $A (struct (field (ref null $X))))
+  (type $A (struct (field (ref null $X))))
+  (type $B (struct_subtype (field (ref null $Y)) $A))
+  ;; CHECK:       (type $C (struct_subtype (field (ref $X)) $A))
+  (type $C (struct_subtype (field (ref $Y)) $A))
+
+  ;; CHECK:       (type $none_=>_none (func))
 
   ;; CHECK:      (func $foo (type $none_=>_none)
   ;; CHECK-NEXT:  (local $a (ref null $A))
@@ -150,24 +169,136 @@
   ;; CHECK-NEXT:  (nop)
   ;; CHECK-NEXT: )
   (func $foo
-    ;; $A will remain the same.
+    ;; B can be merged into A even though it refines A's field because that
+    ;; refinement will no longer happen after X and Y are also merged.
+    (local $a (ref null $A))
+    (local $b (ref null $B))
+    ;; C cannot be merged because it refines the field's nullability.
+    (local $c (ref null $C))
+  )
+)
+
+(module
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct (field (ref null $A))))
+  (type $A (struct         (ref null $A)))
+  (type $B (struct_subtype (ref null $B) $A))
+
+  ;; CHECK:       (type $none_=>_none (func))
+
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (local $a (ref null $A))
+  ;; CHECK-NEXT:  (local $b (ref null $A))
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $foo
+    ;; A recursive subtype can be merged even though its field is a refinement
+    ;; as well.
+    (local $a (ref null $A))
+    (local $b (ref null $B))
+  )
+)
+
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $X (struct (field (ref null $A)) (field f32)))
+
+    ;; CHECK:       (type $A (struct (field (ref null $X)) (field i32)))
+    (type $A (struct         (ref null $X) i32))
+    (type $B (struct_subtype (ref null $Y) i32 $A))
+    (type $X (struct         (ref null $A) f32))
+    (type $Y (struct_subtype (ref null $B) f32 $X))
+  )
+
+  ;; CHECK:       (type $none_=>_none (func))
+
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (local $a (ref null $A))
+  ;; CHECK-NEXT:  (local $b (ref null $A))
+  ;; CHECK-NEXT:  (local $x (ref null $X))
+  ;; CHECK-NEXT:  (local $y (ref null $X))
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $foo
+    ;; Two mutually referential chains, A->B and X->Y, can be merged into a pair
+    ;; of mutually referential types.
+    (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 $X (struct (field (ref null $A))))
+
+    ;; CHECK:       (type $A (struct (field (ref null $X))))
+    (type $A (struct         (ref null $X)))
+    (type $B (struct_subtype (ref null $Y) $A))
+    (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 $A))
+  ;; CHECK-NEXT:  (local $b (ref null $A))
+  ;; 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.
+    ;; TODO: This is not yet implemented. Merge the top level types.
+    (local $a (ref null $A))
+    (local $b (ref null $B))
+    (local $x (ref null $X))
+    (local $y (ref null $Y))
+  )
+)
+
+(module
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $X (struct (field anyref)))
+  (type $X (struct anyref))
+  ;; CHECK:       (type $Y (struct_subtype (field eqref) $X))
+  (type $Y (struct_subtype eqref $X))
+  ;; CHECK:       (type $A (struct (field (ref null $X))))
+  (type $A (struct         (ref null $X)))
+  ;; CHECK:       (type $B (struct_subtype (field (ref null $Y)) $A))
+  (type $B (struct_subtype (ref null $Y) $A))
+  (type $C (struct_subtype (ref null $Y) $A))
+
+  ;; CHECK:       (type $none_=>_none (func))
+
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (local $a (ref null $A))
+  ;; CHECK-NEXT:  (local $b (ref null $B))
+  ;; CHECK-NEXT:  (local $c (ref null $B))
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $foo
+    ;; B and C cannot be merged into A because they refine A's field, but B and
+    ;; C can still be merged with each other even though they are siblings.
     (local $a (ref null $A))
-    ;; $B can be merged into $A.
     (local $b (ref null $B))
-    ;; $C refines the field, so it cannot be merged. However, separately, in
-    ;; the type definition of $C, its field of type $B should become $A. That
-    ;; is, $B should no longer be used anywhere.
     (local $c (ref null $C))
   )
 )
 
 ;; Check that we refinalize properly.
 (module
-  ;; CHECK:      (type $A (struct ))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct ))
   (type $A (struct))
   (type $B (struct_subtype $A))
 
-  ;; CHECK:      (type $none_=>_ref?|$A| (func (result (ref null $A))))
+  ;; CHECK:       (type $none_=>_ref?|$A| (func (result (ref null $A))))
 
   ;; CHECK:      (func $returner (type $none_=>_ref?|$A|) (result (ref null $A))
   ;; CHECK-NEXT:  (local $local (ref null $A))
@@ -189,24 +320,29 @@
 ;; into $D. While doing so we must update the fields and the expressions that
 ;; they appear in, and not error.
 (module
-  ;; CHECK:      (type $C (struct (field (mut i32))))
-
-  ;; CHECK:      (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C))
-
-  ;; CHECK:      (type $I (array (mut (ref null $C))))
-  (type $I (array (mut (ref null $C))))
-  (type $C (struct (field (mut i32))))
-  (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C))
-  (type $E (struct_subtype (field (mut i32)) (field (mut i32)) $D))
-  (type $F (struct_subtype (field (mut i32)) (field (mut i32)) $E))
-  (type $D$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) $F))
-  ;; CHECK:      (type $G (func (param (ref $C)) (result (ref $D))))
-  (type $G (func (param (ref $C)) (result (ref $D))))
-  ;; CHECK:      (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) $D))
-  (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) $D))
-  ;; CHECK:      (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) (field (mut i64)) (field (mut (ref null $I))) $H))
-  (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $H))
-  (type $A$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $A))
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $C (struct (field (mut i32))))
+
+    ;; CHECK:       (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C))
+
+    ;; CHECK:       (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) $D))
+
+    ;; CHECK:       (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) (field (mut i64)) (field (mut (ref null $I))) $H))
+
+    ;; CHECK:       (type $I (array (mut (ref null $C))))
+    (type $I (array (mut (ref null $C))))
+    (type $C (struct (field (mut i32))))
+    (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C))
+    (type $E (struct_subtype (field (mut i32)) (field (mut i32)) $D))
+    (type $F (struct_subtype (field (mut i32)) (field (mut i32)) $E))
+    (type $D$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) $F))
+    ;; CHECK:       (type $G (func (param (ref $C)) (result (ref $D))))
+    (type $G (func (param (ref $C)) (result (ref $D))))
+    (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) $D))
+    (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $H))
+    (type $A$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $A))
+  )
 
   ;; CHECK:      (global $global$0 (ref $D) (struct.new $D
   ;; CHECK-NEXT:  (i32.const 1705)
@@ -238,18 +374,21 @@
 
 ;; Arrays
 (module
-  ;; CHECK:      (type $none_=>_none (func))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $refarray (array anyref))
 
-  ;; CHECK:      (type $intarray (array (mut i32)))
+  ;; CHECK:       (type $sub-refarray-nn (array_subtype (ref any) $refarray))
+
+  ;; CHECK:       (type $intarray (array (mut i32)))
   (type $intarray (array (mut i32)))
   (type $sub-intarray (array_subtype (mut i32) $intarray))
 
-  ;; CHECK:      (type $refarray (array anyref))
   (type $refarray (array (ref null any)))
   (type $sub-refarray    (array_subtype (ref null any) $refarray))
-  ;; CHECK:      (type $sub-refarray-nn (array_subtype (ref any) $refarray))
   (type $sub-refarray-nn (array_subtype (ref      any) $refarray))
 
+  ;; CHECK:       (type $none_=>_none (func))
+
   ;; CHECK:      (func $foo (type $none_=>_none)
   ;; CHECK-NEXT:  (local $a (ref null $intarray))
   ;; CHECK-NEXT:  (local $b (ref null $intarray))
@@ -277,15 +416,90 @@
   )
 )
 
-;; Check that a ref.test inhibits merging (ref.cast is already checked above).
+;; Function types
 (module
-  ;; CHECK:      (type $ref|$A|_=>_i32 (func (param (ref $A)) (result i32)))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $func (func (param eqref)))
+  (type $func (func (param eqref)))
+  (type $sub-func (func_subtype (param eqref) $func))
+  ;; CHECK:       (type $sub-func-refined (func_subtype (param anyref) $func))
+  (type $sub-func-refined (func_subtype (param anyref) $func))
+
+  ;; CHECK:       (type $none_=>_none (func))
 
-  ;; CHECK:      (type $A (struct ))
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (local $a (ref null $func))
+  ;; CHECK-NEXT:  (local $b (ref null $func))
+  ;; CHECK-NEXT:  (local $c (ref null $sub-func-refined))
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $foo
+    ;; $func will remain the same.
+    (local $a (ref null $func))
+    ;; $sub-func will be merged into $func.
+    (local $b (ref null $sub-func))
+    ;; $sub-func-refined will not be merged into $func because it refines a result.
+    (local $c (ref null $sub-func-refined))
+  )
+)
+
+;; Check that public types are not merged.
+(module
+  ;; CHECK:      (type $A (func))
+  (type $A (func))            ;; public
+  ;; CHECK:      (type $B (func_subtype $A))
+  (type $B (func_subtype $A)) ;; public
+  (type $C (func_subtype $B)) ;; private
+
+  ;; CHECK:      (type $ref|$A|_ref|$B|_ref|$B|_=>_none (func (param (ref $A) (ref $B) (ref $B))))
+
+  ;; CHECK:      (export "foo" (func $foo))
+  (export "foo" (func $foo))
+  ;; CHECK:      (export "bar" (func $bar))
+  (export "bar" (func $bar))
+
+  ;; A stays the same.
+  ;; CHECK:      (func $foo (type $A)
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $foo (type $A)
+    (unreachable)
+  )
+
+  ;; B is not merged because it is public.
+  ;; CHECK:      (func $bar (type $B)
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $bar (type $B)
+    (unreachable)
+  )
+
+  ;; C can be merged into B because it is private.
+  ;; CHECK:      (func $baz (type $B)
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $baz (type $C)
+    (unreachable)
+  )
+
+  ;; CHECK:      (func $quux (type $ref|$A|_ref|$B|_ref|$B|_=>_none) (param $0 (ref $A)) (param $1 (ref $B)) (param $2 (ref $B))
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $quux (param (ref $A) (ref $B) (ref $C))
+    (unreachable)
+  )
+)
+
+;; Check that a ref.test inhibits merging (ref.cast is already checked above).
+(module
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct ))
   (type $A (struct))
-  ;; CHECK:      (type $B (struct_subtype  $A))
+  ;; CHECK:       (type $B (struct_subtype  $A))
   (type $B (struct_subtype $A))
 
+  ;; CHECK:       (type $ref|$A|_=>_i32 (func (param (ref $A)) (result i32)))
+
   ;; CHECK:      (func $test (type $ref|$A|_=>_i32) (param $a (ref $A)) (result i32)
   ;; CHECK-NEXT:  (ref.test $B
   ;; CHECK-NEXT:   (local.get $a)
@@ -300,12 +514,13 @@
 
 ;; Check that a br_on_cast inhibits merging.
 (module
-  ;; CHECK:      (type $A (struct ))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (struct ))
   (type $A (struct))
-  ;; CHECK:      (type $B (struct_subtype  $A))
+  ;; CHECK:       (type $B (struct_subtype  $A))
   (type $B (struct_subtype $A))
 
-  ;; CHECK:      (type $ref|$A|_=>_ref|$B| (func (param (ref $A)) (result (ref $B))))
+  ;; CHECK:       (type $ref|$A|_=>_ref|$B| (func (param (ref $A)) (result (ref $B))))
 
   ;; CHECK:      (func $test (type $ref|$A|_=>_ref|$B|) (param $a (ref $A)) (result (ref $B))
   ;; CHECK-NEXT:  (block $__binaryen_fake_return (result (ref $B))
@@ -346,9 +561,10 @@
 
 ;; Check that a call_indirect inhibits merging.
 (module
-  ;; CHECK:      (type $A (func))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $A (func))
   (type $A (func))
-  ;; CHECK:      (type $B (func_subtype $A))
+  ;; CHECK:       (type $B (func_subtype $A))
   (type $B (func_subtype $A))
 
   (table 1 1 (ref null $A))