Add a pass for minimizing recursion groups (#6832)

Most of our type optimization passes emit all non-public types as a
single large rec group, which trivially ensures that different types
remain different, even if they are optimized to have the same structure.
Usually emitting a single large rec group is fine, but it also means
that if the module is split, all of the types will need to be repeated
in all of the split modules. To better support this use case, add a pass
that can split the large rec group back into minimal rec groups, taking
care to preserve separate type identities by emitting different
permutations of the same group where possible or by inserting unused
brand types to differentiate them.

1 files changed, 486 insertions, 0 deletions

diff --git a/test/lit/passes/minimize-rec-groups.wast b/test/lit/passes/minimize-rec-groups.wast
new file mode 100644
index 000000000..b1c1b1467
--- /dev/null
+++ b/test/lit/passes/minimize-rec-groups.wast
@@ -0,0 +1,486 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: foreach %s %t wasm-opt -all --minimize-rec-groups -S -o - | filecheck %s
+
+;; A module with no heap types at all should be ok.
+(module
+  ;; CHECK:      (global $g i32 (i32.const 0))
+  (global $g i32 (i32.const 0))
+)
+
+;; A module with a single heap type should be ok.
+(module
+  ;; CHECK:      (type $t (struct))
+  (type $t (struct))
+  ;; CHECK:      (global $g (ref null $t) (ref.null none))
+  (global $g (ref null $t) (ref.null none))
+)
+
+;; Split a rec group containing independent types
+(module
+  (rec
+    ;; CHECK:      (type $a (struct (field i32)))
+    (type $a (struct (field i32)))
+    ;; CHECK:      (type $b (struct (field i64)))
+    (type $b (struct (field i64)))
+    ;; CHECK:      (type $c (struct (field f32)))
+    (type $c (struct (field f32)))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+  ;; CHECK:      (global $c (ref null $c) (ref.null none))
+  (global $c (ref null $c) (ref.null none))
+)
+
+;; Split a rec group containing types that depend on each other but belong to
+;; different SCCs.
+(module
+  (rec
+    ;; CHECK:      (type $a (struct))
+    (type $a (struct))
+    ;; CHECK:      (type $b (struct (field (ref $a))))
+    (type $b (struct (field (ref $a))))
+    ;; CHECK:      (type $c (struct (field (ref $b))))
+    (type $c (struct (field (ref $b))))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+  ;; CHECK:      (global $c (ref null $c) (ref.null none))
+  (global $c (ref null $c) (ref.null none))
+)
+
+;; Reverse the order of the previous case. The output should still be in a valid
+;; order.
+(module
+  (rec
+    ;; CHECK:      (type $a (struct))
+
+    ;; CHECK:      (type $b (struct (field (ref $a))))
+
+    ;; CHECK:      (type $c (struct (field (ref $b))))
+    (type $c (struct (field (ref $b))))
+    (type $b (struct (field (ref $a))))
+    (type $a (struct))
+  )
+
+  ;; CHECK:      (global $c (ref null $c) (ref.null none))
+  (global $c (ref null $c) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+)
+
+;; Now all the types are in the same SCC.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $c (struct (field (ref $a))))
+
+    ;; CHECK:       (type $b (struct (field (ref $c))))
+
+    ;; CHECK:       (type $a (struct (field (ref $b))))
+    (type $a (struct (field (ref $b))))
+    (type $b (struct (field (ref $c))))
+    (type $c (struct (field (ref $a))))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+)
+
+;; Only two of the types are in the same SCC.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $b (struct (field (ref $a))))
+
+    ;; CHECK:       (type $a (struct (field (ref $b))))
+    (type $a (struct (field (ref $b))))
+    (type $b (struct (field (ref $a))))
+    ;; CHECK:      (type $c (struct (field (ref $a))))
+    (type $c (struct (field (ref $a))))
+  )
+
+  ;; CHECK:      (global $c (ref null $c) (ref.null none))
+  (global $c (ref null $c) (ref.null none))
+)
+
+;; Same, but change which two are in the SCC. The output order should still be
+;; valid.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $c (struct (field (ref $b))))
+
+    ;; CHECK:       (type $b (struct (field (ref $c))))
+
+    ;; CHECK:      (type $a (struct (field (ref $b))))
+    (type $a (struct (field (ref $b))))
+    (type $b (struct (field (ref $c))))
+    (type $c (struct (field (ref $b))))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+)
+
+;; Two types that are in conflicting SCCs should be disambiguated. In this case
+;; there are no different permutations, so we use a brand.
+(module
+  (rec
+    ;; CHECK:      (type $a (func))
+    (type $a (func))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $1 (struct))
+
+    ;; CHECK:       (type $b (func))
+    (type $b (func))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null nofunc))
+  (global $a (ref null $a) (ref.null nofunc))
+  ;; CHECK:      (global $b (ref null $b) (ref.null nofunc))
+  (global $b (ref null $b) (ref.null nofunc))
+)
+
+;; Same as above, but now the types match the initial brand, so we have to skip
+;; to the next one.
+(module
+  (rec
+    ;; CHECK:      (type $a (struct))
+    (type $a (struct))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $1 (array (mut i8)))
+
+    ;; CHECK:       (type $b (struct))
+    (type $b (struct))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+)
+
+;; Now we have groups that match both the initial brand and the next one, so
+;; adding the brand will cause a conflict. We will have to go to the next brand.
+(module
+  (rec
+    ;; CHECK:      (type $a1 (struct))
+    (type $a1 (struct))
+    ;; CHECK:      (type $b1 (array (mut i8)))
+
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $2 (array (mut i8)))
+
+    ;; CHECK:       (type $a2 (struct))
+    (type $a2 (struct))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a3 (struct))
+    (type $a3 (struct))
+    (type $b1 (array (mut i8)))
+    ;; CHECK:       (type $5 (array (mut i8)))
+
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $6 (array i8))
+
+    ;; CHECK:       (type $b2 (array (mut i8)))
+    (type $b2 (array (mut i8)))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
+  (global $a2 (ref null $a2) (ref.null none))
+  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
+  (global $a3 (ref null $a3) (ref.null none))
+  ;; CHECK:      (global $b1 (ref null $b1) (ref.null none))
+  (global $b1 (ref null $b1) (ref.null none))
+  ;; CHECK:      (global $b2 (ref null $b2) (ref.null none))
+  (global $b2 (ref null $b2) (ref.null none))
+)
+
+;; Now the types have more fields, including one referring to a previous SCC.
+(module
+  (rec
+    ;; CHECK:      (type $other (struct (field i32)))
+    (type $other (struct (field i32)))
+    ;; CHECK:      (type $a (struct (field anyref) (field i32) (field (ref $other))))
+    (type $a (struct (field anyref i32 (ref $other))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $2 (struct))
+
+    ;; CHECK:       (type $b (struct (field anyref) (field i32) (field (ref $other))))
+    (type $b (struct (field anyref i32 (ref $other))))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+)
+
+;; Now there is a third type and we can disambiguate it by using a different
+;; permutation with the same brand.
+(module
+  (rec
+    ;; CHECK:      (type $a (struct))
+    (type $a (struct))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $1 (array (mut i8)))
+
+    ;; CHECK:       (type $b (struct))
+    (type $b (struct))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $c (struct))
+    (type $c (struct))
+  )
+
+  ;; CHECK:       (type $4 (array (mut i8)))
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+  ;; CHECK:      (global $c (ref null $c) (ref.null none))
+  (global $c (ref null $c) (ref.null none))
+)
+
+;; Adding a fourth type requires using yet another brand.
+(module
+  (rec
+    ;; CHECK:      (type $a (struct))
+    (type $a (struct))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $1 (array (mut i8)))
+
+    ;; CHECK:       (type $b (struct))
+    (type $b (struct))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $c (struct))
+    (type $c (struct))
+    ;; CHECK:       (type $4 (array (mut i8)))
+
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $5 (array i8))
+
+    ;; CHECK:       (type $d (struct))
+    (type $d (struct))
+  )
+
+  ;; CHECK:      (global $a (ref null $a) (ref.null none))
+  (global $a (ref null $a) (ref.null none))
+  ;; CHECK:      (global $b (ref null $b) (ref.null none))
+  (global $b (ref null $b) (ref.null none))
+  ;; CHECK:      (global $c (ref null $c) (ref.null none))
+  (global $c (ref null $c) (ref.null none))
+  ;; CHECK:      (global $d (ref null $d) (ref.null none))
+  (global $d (ref null $d) (ref.null none))
+)
+
+;; After $a1 and $a2 are dismabiguated with a brand, $b1 and $b2 require no
+;; further disambiguation.
+(module
+  (rec
+    ;; CHECK:      (type $a1 (struct))
+    (type $a1 (struct))
+    ;; CHECK:      (type $b1 (struct (field (ref $a1))))
+
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $2 (array (mut i8)))
+
+    ;; CHECK:       (type $a2 (struct))
+    (type $a2 (struct))
+    (type $b1 (struct (field (ref $a1))))
+    ;; CHECK:      (type $b2 (struct (field (ref $a2))))
+    (type $b2 (struct (field (ref $a2))))
+  )
+
+  ;; CHECK:      (global $b1 (ref null $b1) (ref.null none))
+  (global $b1 (ref null $b1) (ref.null none))
+  ;; CHECK:      (global $b2 (ref null $b2) (ref.null none))
+  (global $b2 (ref null $b2) (ref.null none))
+)
+
+;; Now we can disambiguate by permuting without a brand.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))
+
+    ;; CHECK:       (type $a1 (struct (field (ref $b1)) (field i32)))
+    (type $a1 (struct (field (ref $b1) i32)))
+    (type $b1 (struct (field (ref $a1))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a2 (struct (field (ref $b2)) (field i32)))
+    (type $a2 (struct (field (ref $b2) i32)))
+    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
+    (type $b2 (struct (field (ref $a2))))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
+  (global $a2 (ref null $a2) (ref.null none))
+)
+
+;; But when we run out of permutations, we need a brand again.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))
+
+    ;; CHECK:       (type $a1 (struct (field (ref $b1)) (field i32)))
+    (type $a1 (struct (field (ref $b1) i32)))
+    (type $b1 (struct (field (ref $a1))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a2 (struct (field (ref $b2)) (field i32)))
+    (type $a2 (struct (field (ref $b2) i32)))
+    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
+    (type $b2 (struct (field (ref $a2))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $4 (struct))
+
+    ;; CHECK:       (type $b3 (struct (field (ref $a3))))
+
+    ;; CHECK:       (type $a3 (struct (field (ref $b3)) (field i32)))
+    (type $a3 (struct (field (ref $b3) i32)))
+    (type $b3 (struct (field (ref $a3))))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
+  (global $a2 (ref null $a2) (ref.null none))
+  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
+  (global $a3 (ref null $a3) (ref.null none))
+)
+
+;; Same as above, except the middle global now refers to $b2 instead of $a2,
+;; changing the initial order of types in the middle SCC. We arrive at the same
+;; result by a different path.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))
+
+    ;; CHECK:       (type $a1 (struct (field (ref $b1)) (field i32)))
+    (type $a1 (struct (field (ref $b1) i32)))
+    (type $b1 (struct (field (ref $a1))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a2 (struct (field (ref $b2)) (field i32)))
+    (type $a2 (struct (field (ref $b2) i32)))
+    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
+    (type $b2 (struct (field (ref $a2))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $4 (struct))
+
+    ;; CHECK:       (type $b3 (struct (field (ref $a3))))
+
+    ;; CHECK:       (type $a3 (struct (field (ref $b3)) (field i32)))
+    (type $a3 (struct (field (ref $b3) i32)))
+    (type $b3 (struct (field (ref $a3))))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $b2 (ref null $b2) (ref.null none))
+  (global $b2 (ref null $b2) (ref.null none))
+  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
+  (global $a3 (ref null $a3) (ref.null none))
+)
+
+;; Now we can't differentiate by permutation because of automorphisms.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $b1 (struct (field (ref $a1))))
+
+    ;; CHECK:       (type $a1 (struct (field (ref $b1))))
+    (type $a1 (struct (field (ref $b1))))
+    (type $b1 (struct (field (ref $a1))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $2 (struct))
+
+    ;; CHECK:       (type $b2 (struct (field (ref $a2))))
+
+    ;; CHECK:       (type $a2 (struct (field (ref $b2))))
+    (type $a2 (struct (field (ref $b2))))
+    (type $b2 (struct (field (ref $a2))))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
+  (global $a2 (ref null $a2) (ref.null none))
+)
+
+;; Now we can't differentiate by permutation because the subtyping constraint
+;; admits only one ordering.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a1 (sub (struct (field (ref $b1)))))
+    (type $a1 (sub (struct (field (ref $b1)))))
+    ;; CHECK:       (type $b1 (sub $a1 (struct (field (ref $b1)))))
+    (type $b1 (sub $a1 (struct (field (ref $b1)))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $2 (struct))
+
+    ;; CHECK:       (type $a2 (sub (struct (field (ref $b2)))))
+    (type $a2 (sub (struct (field (ref $b2)))))
+    ;; CHECK:       (type $b2 (sub $a2 (struct (field (ref $b2)))))
+    (type $b2 (sub $a2 (struct (field (ref $b2)))))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
+  (global $a2 (ref null $a2) (ref.null none))
+)
+
+
+;; Now there are only two possible orderings admitted by the subtyping
+;; constraint.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a1 (sub (struct (field (ref $b1)))))
+    (type $a1 (sub (struct (field (ref $b1)))))
+    ;; CHECK:       (type $c1 (sub $a1 (struct (field (ref $b1)))))
+
+    ;; CHECK:       (type $b1 (sub $a1 (struct (field (ref $b1)) (field (ref $c1)))))
+    (type $b1 (sub $a1 (struct (field (ref $b1)) (ref $c1))))
+    (type $c1 (sub $a1 (struct (field (ref $b1)))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $a2 (sub (struct (field (ref $b2)))))
+    (type $a2 (sub (struct (field (ref $b2)))))
+    ;; CHECK:       (type $b2 (sub $a2 (struct (field (ref $b2)) (field (ref $c2)))))
+    (type $b2 (sub $a2 (struct (field (ref $b2)) (ref $c2))))
+    ;; CHECK:       (type $c2 (sub $a2 (struct (field (ref $b2)))))
+    (type $c2 (sub $a2 (struct (field (ref $b2)))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $6 (struct))
+
+    ;; CHECK:       (type $a3 (sub (struct (field (ref $b3)))))
+    (type $a3 (sub (struct (field (ref $b3)))))
+    ;; CHECK:       (type $c3 (sub $a3 (struct (field (ref $b3)))))
+
+    ;; CHECK:       (type $b3 (sub $a3 (struct (field (ref $b3)) (field (ref $c3)))))
+    (type $b3 (sub $a3 (struct (field (ref $b3)) (ref $c3))))
+    (type $c3 (sub $a3 (struct (field (ref $b3)))))
+  )
+
+  ;; CHECK:      (global $a1 (ref null $a1) (ref.null none))
+  (global $a1 (ref null $a1) (ref.null none))
+  ;; CHECK:      (global $a2 (ref null $a2) (ref.null none))
+  (global $a2 (ref null $a2) (ref.null none))
+  ;; CHECK:      (global $a3 (ref null $a3) (ref.null none))
+  (global $a3 (ref null $a3) (ref.null none))
+)