Replace the old topological sort everywhere (#6902)

To avoid having two separate topological sort utilities in the code
base, replace remaining uses of the old DFS-based, CRTP topological sort
with the newer Kahn's algorithm implementation.

This would be NFC, except that the new topological sort produces a
different order than the old topological sort, so the output of some
passes is reordered.

5 files changed, 48 insertions, 48 deletions

diff --git a/test/lit/passes/gto-mutability.wast b/test/lit/passes/gto-mutability.wast
index 47a9e2315..13b416b1b 100644
--- a/test/lit/passes/gto-mutability.wast
+++ b/test/lit/passes/gto-mutability.wast
@@ -429,10 +429,10 @@
   ;; optimize the field to be immutable.
 
   ;; CHECK:      (rec
-  ;; CHECK-NEXT:  (type $0 (func (param (ref null $super) (ref null $sub))))
-
-  ;; CHECK:       (type $super (sub (struct (field i32))))
+  ;; CHECK-NEXT:  (type $super (sub (struct (field i32))))
   (type $super (sub (struct (field (mut i32)))))
+  ;; CHECK:       (type $1 (func (param (ref null $super) (ref null $sub))))
+
   ;; CHECK:       (type $sub (sub $super (struct (field i32))))
   (type $sub (sub $super (struct (field (mut i32)))))
 
@@ -464,7 +464,7 @@
     )
   )
 
-  ;; CHECK:      (func $field-keepalive (type $0) (param $super (ref null $super)) (param $sub (ref null $sub))
+  ;; CHECK:      (func $field-keepalive (type $1) (param $super (ref null $super)) (param $sub (ref null $sub))
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (struct.get $super 0
   ;; CHECK-NEXT:    (local.get $super)
diff --git a/test/lit/passes/signature-pruning.wast b/test/lit/passes/signature-pruning.wast
index 8754c8189..57dd78362 100644
--- a/test/lit/passes/signature-pruning.wast
+++ b/test/lit/passes/signature-pruning.wast
@@ -1161,9 +1161,9 @@
 (module
   (rec
    ;; CHECK:      (rec
-   ;; CHECK-NEXT:  (type $much (func))
+   ;; CHECK-NEXT:  (type $0 (func))
 
-   ;; CHECK:       (type $1 (func))
+   ;; CHECK:       (type $much (func))
 
    ;; CHECK:      (rec
    ;; CHECK-NEXT:  (type $none (func))
@@ -1191,7 +1191,7 @@
   (func $unused-param (type $much) (param $param i32)
   )
 
-  ;; CHECK:      (func $caller (type $1)
+  ;; CHECK:      (func $caller (type $0)
   ;; CHECK-NEXT:  (call $unused-param)
   ;; CHECK-NEXT: )
   (func $caller
diff --git a/test/lit/passes/signature-refining.wast b/test/lit/passes/signature-refining.wast
index fdddbe4ed..7a5020e29 100644
--- a/test/lit/passes/signature-refining.wast
+++ b/test/lit/passes/signature-refining.wast
@@ -1068,11 +1068,11 @@
 (module
  (rec
   ;; CHECK:      (rec
-  ;; CHECK-NEXT:  (type $0 (func (param (ref $B))))
-
-  ;; CHECK:       (type $A (sub (struct)))
+  ;; CHECK-NEXT:  (type $A (sub (struct)))
   (type $A (sub (struct)))
 
+  ;; CHECK:       (type $1 (func (param (ref $B))))
+
   ;; CHECK:       (type $B (sub $A (struct)))
   (type $B (sub $A (struct)))
  )
@@ -1108,7 +1108,7 @@
   )
  )
 
- ;; CHECK:      (func $target (type $0) (param $x (ref $B))
+ ;; CHECK:      (func $target (type $1) (param $x (ref $B))
  ;; CHECK-NEXT:  (nop)
  ;; CHECK-NEXT: )
  (func $target (param $x (ref $A))
diff --git a/test/lit/passes/type-merging.wast b/test/lit/passes/type-merging.wast
index d6d117a05..b8d602863 100644
--- a/test/lit/passes/type-merging.wast
+++ b/test/lit/passes/type-merging.wast
@@ -234,10 +234,10 @@
 
 (module
   (rec
-    ;; CHECK:      (rec
-    ;; CHECK-NEXT:  (type $A (sub (struct (field (ref null $A)))))
     (type $A (sub (struct    (ref null $X))))
     (type $B (sub $A (struct (ref null $Y))))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $X (sub (struct (field (ref null $X)))))
     (type $X (sub (struct    (ref null $A))))
     (type $Y (sub $X (struct (ref null $B))))
   )
@@ -245,10 +245,10 @@
   ;; CHECK:       (type $1 (func))
 
   ;; CHECK:      (func $foo (type $1)
-  ;; CHECK-NEXT:  (local $a (ref null $A))
-  ;; CHECK-NEXT:  (local $b (ref null $A))
-  ;; CHECK-NEXT:  (local $x (ref null $A))
-  ;; CHECK-NEXT:  (local $y (ref null $A))
+  ;; CHECK-NEXT:  (local $a (ref null $X))
+  ;; CHECK-NEXT:  (local $b (ref null $X))
+  ;; CHECK-NEXT:  (local $x (ref null $X))
+  ;; CHECK-NEXT:  (local $y (ref null $X))
   ;; CHECK-NEXT:  (nop)
   ;; CHECK-NEXT: )
   (func $foo
@@ -263,21 +263,21 @@
 
 (module
   (rec
-    (type $A (struct (ref null $X) i32))
     ;; CHECK:      (rec
-    ;; CHECK-NEXT:  (type $B (struct (field (ref null $Y)) (field i32)))
+    ;; CHECK-NEXT:  (type $A (struct (field (ref null $X)) (field i32)))
+    (type $A (struct (ref null $X) i32))
     (type $B (struct (ref null $Y) i32))
+    ;; CHECK:       (type $X (struct (field (ref null $A)) (field f32)))
     (type $X (struct (ref null $A) f32))
-    ;; CHECK:       (type $Y (struct (field (ref null $B)) (field f32)))
     (type $Y (struct (ref null $B) f32))
   )
   ;; CHECK:       (type $2 (func))
 
   ;; CHECK:      (func $foo (type $2)
-  ;; CHECK-NEXT:  (local $a (ref null $B))
-  ;; CHECK-NEXT:  (local $b (ref null $B))
-  ;; CHECK-NEXT:  (local $x (ref null $Y))
-  ;; CHECK-NEXT:  (local $y (ref null $Y))
+  ;; 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
@@ -293,19 +293,19 @@
 (module
   (rec
     (type $A (struct (ref null $X)))
-    ;; CHECK:      (rec
-    ;; CHECK-NEXT:  (type $B (struct (field (ref null $B))))
     (type $B (struct (ref null $Y)))
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $X (struct (field (ref null $X))))
     (type $X (struct (ref null $A)))
     (type $Y (struct (ref null $B)))
   )
   ;; CHECK:       (type $1 (func))
 
   ;; CHECK:      (func $foo (type $1)
-  ;; CHECK-NEXT:  (local $a (ref null $B))
-  ;; CHECK-NEXT:  (local $b (ref null $B))
-  ;; CHECK-NEXT:  (local $x (ref null $B))
-  ;; CHECK-NEXT:  (local $y (ref null $B))
+  ;; CHECK-NEXT:  (local $a (ref null $X))
+  ;; CHECK-NEXT:  (local $b (ref null $X))
+  ;; CHECK-NEXT:  (local $x (ref null $X))
+  ;; CHECK-NEXT:  (local $y (ref null $X))
   ;; CHECK-NEXT:  (nop)
   ;; CHECK-NEXT: )
   (func $foo
@@ -495,8 +495,8 @@
     ;; CHECK:      (rec
     ;; CHECK-NEXT:  (type $A (sub (struct (field anyref))))
     (type $A (sub (struct    anyref)))
+    ;; CHECK:       (type $B (sub $A (struct (field eqref))))
     (type $B (sub $A (struct eqref)))
-    ;; CHECK:       (type $C (sub $A (struct (field eqref))))
     (type $C (sub $A (struct eqref)))
   )
 
@@ -504,8 +504,8 @@
 
   ;; CHECK:      (func $foo (type $2)
   ;; CHECK-NEXT:  (local $a (ref null $A))
-  ;; CHECK-NEXT:  (local $b (ref null $C))
-  ;; CHECK-NEXT:  (local $c (ref null $C))
+  ;; CHECK-NEXT:  (local $b (ref null $B))
+  ;; CHECK-NEXT:  (local $c (ref null $B))
   ;; CHECK-NEXT:  (nop)
   ;; CHECK-NEXT: )
   (func $foo
@@ -524,8 +524,8 @@
     (type $A (sub (struct    anyref)))
     (type $B (sub $A (struct anyref)))
     (type $C (sub $A (struct anyref)))
+    ;; CHECK:       (type $D (sub $A (struct (field eqref))))
     (type $D (sub $B (struct eqref)))
-    ;; CHECK:       (type $E (sub $A (struct (field eqref))))
     (type $E (sub $C (struct eqref)))
   )
 
@@ -535,8 +535,8 @@
   ;; CHECK-NEXT:  (local $a (ref null $A))
   ;; CHECK-NEXT:  (local $b (ref null $A))
   ;; CHECK-NEXT:  (local $c (ref null $A))
-  ;; CHECK-NEXT:  (local $d (ref null $E))
-  ;; CHECK-NEXT:  (local $e (ref null $E))
+  ;; CHECK-NEXT:  (local $d (ref null $D))
+  ;; CHECK-NEXT:  (local $e (ref null $D))
   ;; CHECK-NEXT:  (nop)
   ;; CHECK-NEXT: )
   (func $foo
@@ -561,18 +561,18 @@
     (type $A' (sub $A (struct)))
 
     ;; These siblings will be merged only after $a and $a' are merged.
+    ;; CHECK:       (type $B (sub (struct (field (ref $A)))))
     (type $B (sub (struct (ref $A))))
-    ;; CHECK:       (type $B' (sub (struct (field (ref $A)))))
     (type $B' (sub (struct (ref $A'))))
 
     ;; These will get merged only after $b and $b' are merged.
-    ;; CHECK:       (type $C (sub $B' (struct (field (ref $A)) (field i32))))
+    ;; CHECK:       (type $C (sub $B (struct (field (ref $A)) (field i32))))
     (type $C (sub $B (struct (ref $A) i32)))
     (type $C' (sub $B' (struct (ref $A') i32)))
 
     ;; These will get merged only after $c and $c' are merged.
+    ;; CHECK:       (type $D (sub $C (struct (field (ref $A)) (field i32) (field i32))))
     (type $D (sub $C (struct (ref $A) i32 i32)))
-    ;; CHECK:       (type $D' (sub $C (struct (field (ref $A)) (field i32) (field i32))))
     (type $D' (sub $C' (struct (ref $A') i32 i32)))
   )
 
@@ -581,12 +581,12 @@
   ;; CHECK:      (func $foo (type $4)
   ;; CHECK-NEXT:  (local $a (ref null $A))
   ;; CHECK-NEXT:  (local $a' (ref null $A))
-  ;; CHECK-NEXT:  (local $b (ref null $B'))
-  ;; CHECK-NEXT:  (local $b' (ref null $B'))
+  ;; CHECK-NEXT:  (local $b (ref null $B))
+  ;; CHECK-NEXT:  (local $b' (ref null $B))
   ;; CHECK-NEXT:  (local $c (ref null $C))
   ;; CHECK-NEXT:  (local $c' (ref null $C))
-  ;; CHECK-NEXT:  (local $d (ref null $D'))
-  ;; CHECK-NEXT:  (local $d' (ref null $D'))
+  ;; CHECK-NEXT:  (local $d (ref null $D))
+  ;; CHECK-NEXT:  (local $d' (ref null $D))
   ;; CHECK-NEXT:  (nop)
   ;; CHECK-NEXT: )
   (func $foo
diff --git a/test/lit/passes/type-ssa_and_merging.wast b/test/lit/passes/type-ssa_and_merging.wast
index 8e84cf5c4..4a772763b 100644
--- a/test/lit/passes/type-ssa_and_merging.wast
+++ b/test/lit/passes/type-ssa_and_merging.wast
@@ -14,14 +14,14 @@
   ;; YES:      (type $0 (func (result i32)))
 
   ;; YES:      (rec
-  ;; YES-NEXT:  (type $1 (func (param (ref $A))))
-
-  ;; YES:       (type $A (sub (struct)))
+  ;; YES-NEXT:  (type $A (sub (struct)))
   (type $A (sub (struct (field (mut i32)))))
 
   ;; NOP:      (type $2 (func (result i32)))
 
   ;; NOP:      (import "a" "b" (func $import (type $2) (result i32)))
+  ;; YES:       (type $2 (func (param (ref $A))))
+
   ;; YES:       (type $A_2 (sub $A (struct)))
 
   ;; YES:       (type $A_1 (sub $A (struct)))
@@ -92,7 +92,7 @@
   ;; NOP-NEXT:   (local.get $0)
   ;; NOP-NEXT:  )
   ;; NOP-NEXT: )
-  ;; YES:      (func $get-a-1 (type $1) (param $0 (ref $A))
+  ;; YES:      (func $get-a-1 (type $2) (param $0 (ref $A))
   ;; YES-NEXT:  (if
   ;; YES-NEXT:   (call $import)
   ;; YES-NEXT:   (then
@@ -134,7 +134,7 @@
   ;; NOP-NEXT:   (local.get $0)
   ;; NOP-NEXT:  )
   ;; NOP-NEXT: )
-  ;; YES:      (func $get-a-2 (type $1) (param $0 (ref $A))
+  ;; YES:      (func $get-a-2 (type $2) (param $0 (ref $A))
   ;; YES-NEXT:  (if
   ;; YES-NEXT:   (call $import)
   ;; YES-NEXT:   (then