Topological sorting of types in isorecursive output (#4492)

Generally we try to order types by decreasing use count so that frequently used
types get smaller indices. For the equirecursive and nominal systems, there are
no contraints on the ordering of types, so we just have to sort them according
to their use counts. For the isorecursive type system, however, there are a
number of ordering constraints that have to be met for the type section to be
valid. First, types in the same recursion group must be adjacent so they can be
grouped together. Second, groups must be ordered topologically so that they only
refer to types in themselves or prior groups.

Update type ordering to produce a valid isorecursive output by performing a
topological sort on the recursion groups. While performing the sort, prefer to
visit and finish processing the most used groups first as a heuristic to improve
the final ordering.

Do not reorder types within groups, since doing so would change type identity
and could affect the external interface of the module. Leave that reordering to
an optimization pass (not yet implemented) that users can explicitly opt in to.

1 files changed, 100 insertions, 0 deletions

diff --git a/test/lit/isorecursive-output-ordering.wast b/test/lit/isorecursive-output-ordering.wast
new file mode 100644
index 000000000..6aaa7ba39
--- /dev/null
+++ b/test/lit/isorecursive-output-ordering.wast
@@ -0,0 +1,100 @@
+;; TODO: Autogenerate these checks! The current script cannot handle `rec`.
+
+;; RUN: foreach %s %t wasm-opt -all --hybrid -S -o - | filecheck %s
+
+(module
+ ;; Test that we order groups by average uses.
+
+ ;; CHECK:      (rec
+ ;; CHECK-NEXT:  (type $unused-6 (struct_subtype data))
+ ;; CHECK-NEXT:  (type $used-a-bit (struct_subtype data))
+ ;; CHECK-NEXT: )
+
+ ;; CHECK-NEXT: (rec
+ ;; CHECK-NEXT:  (type $unused-1 (struct_subtype data))
+ ;; CHECK-NEXT:  (type $unused-2 (struct_subtype data))
+ ;; CHECK-NEXT:  (type $unused-3 (struct_subtype data))
+ ;; CHECK-NEXT:  (type $unused-4 (struct_subtype data))
+ ;; CHECK-NEXT:  (type $used-a-lot (struct_subtype data))
+ ;; CHECK-NEXT:  (type $unused-5 (struct_subtype data))
+ ;; CHECK-NEXT: )
+
+ (rec
+  (type $unused-1 (struct_subtype data))
+  (type $unused-2 (struct_subtype data))
+  (type $unused-3 (struct_subtype data))
+  (type $unused-4 (struct_subtype data))
+  (type $used-a-lot (struct_subtype data))
+  (type $unused-5 (struct_subtype data))
+ )
+
+ (rec
+  (type $unused-6 (struct_subtype data))
+  (type $used-a-bit (struct_subtype data))
+ )
+
+ (func $use (param (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot)) (result (ref $used-a-bit) (ref $used-a-bit) (ref $used-a-bit) (ref $used-a-bit))
+  (unreachable)
+ )
+)
+
+(module
+ ;; Test that we respect dependencies between groups before considering counts.
+
+ ;; CHECK:      (rec
+ ;; CHECK-NEXT:  (type $leaf (struct_subtype  data))
+ ;; CHECK-NEXT:  (type $unused (struct_subtype  data))
+ ;; CHECK-NEXT: )
+
+ ;; CHECK-NEXT: (rec
+ ;; CHECK-NEXT:  (type $shrub (struct_subtype  $leaf))
+ ;; CHECK-NEXT:  (type $used-a-ton (struct_subtype  data))
+ ;; CHECK-NEXT: )
+
+ ;; CHECK-NEXT: (rec
+ ;; CHECK-NEXT:  (type $twig (struct_subtype  data))
+ ;; CHECK-NEXT:  (type $used-a-bit (struct_subtype (field (ref $leaf)) data))
+ ;; CHECK-NEXT: )
+
+ ;; CHECK-NEXT: (rec
+ ;; CHECK-NEXT:  (type $root (struct_subtype  data))
+ ;; CHECK-NEXT:  (type $used-a-lot (struct_subtype  $twig))
+ ;; CHECK-NEXT: )
+
+ (rec
+  (type $leaf (struct_subtype data))
+  (type $unused (struct_subtype data))
+ )
+
+ (rec
+  (type $twig (struct_subtype data))
+  (type $used-a-bit (struct_subtype (ref $leaf) data))
+ )
+
+ (rec
+  (type $shrub (struct_subtype $leaf))
+  (type $used-a-ton (struct_subtype data))
+ )
+
+ (rec
+  (type $root (struct_subtype data))
+  (type $used-a-lot (struct_subtype $twig))
+ )
+
+ (func $use (param (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot) (ref $used-a-lot)) (result (ref $used-a-bit) (ref $used-a-bit) (ref $used-a-bit))
+  (local (ref null $used-a-ton) (ref null $used-a-ton) (ref null $used-a-ton) (ref null $used-a-ton) (ref null $used-a-ton) (ref null $used-a-ton) (ref null $used-a-ton))
+  (unreachable)
+ )
+)
+
+(module
+ ;; Test that basic heap type children do not trigger assertions.
+
+ (rec
+  (type $contains-basic (struct_subtype (ref any) data))
+ )
+
+ (func $use (param (ref $contains-basic))
+   (unreachable)
+ )
+)