[Wasm GC] Fix supertype ordering bug in GlobalTypeRewriter (#5442)

GlobalTypeRewriter made sure to order supertypes before their subtypes so that
type building would succeed, but this ordering previously did not account for
the fact that supertypes might be replaced by the type updating. When a
supertype is replaced, the replacement might not previously have had a
supertype/subtype relationship with the subtype, so it might have happened to be
ordered after the subtype.

Fix the problem by taking supertype replacements into account when ordering
types in the GlobalTypeRewriter. This requires generalizing the
`SupertypesFirst` utility in wasm-type-ordering.h to allow users to modify how
supertypes are found.

1 files changed, 26 insertions, 0 deletions

diff --git a/test/lit/passes/type-merging.wast b/test/lit/passes/type-merging.wast
index 4a58ca2d0..d45bed3c6 100644
--- a/test/lit/passes/type-merging.wast
+++ b/test/lit/passes/type-merging.wast
@@ -690,6 +690,32 @@
   )
 )
 
+;; Regresssion test for a bug in which we merged A into A', but
+;; type-updating.cpp ordered B before A', so the supertype ordering was
+;; incorrect.
+(module
+ (rec
+  (type $A (struct))
+  (type $B (struct_subtype $A))
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $X (struct (field (ref $A'))))
+  (type $X (struct (ref $B)))
+  ;; CHECK:       (type $A' (struct ))
+  (type $A' (struct))
+ )
+ ;; CHECK:       (type $none_=>_none (func))
+
+ ;; CHECK:      (func $foo (type $none_=>_none)
+ ;; CHECK-NEXT:  (local $b (ref null $A'))
+ ;; CHECK-NEXT:  (local $x (ref null $X))
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT: )
+ (func $foo
+   (local $b (ref null $A'))
+   (local $x (ref null $X))
+ )
+)
+
 ;; Check that a ref.test inhibits merging (ref.cast is already checked above).
 (module
   ;; CHECK:      (rec