diff options
Diffstat (limited to 'test/lit/passes/minimize-rec-groups.wast')
| -rw-r--r-- | test/lit/passes/minimize-rec-groups.wast | 486 |
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)) +) |