Equirecursive type canonicalization (#3717)

* Equirecursive type canonicalization

Use Hopcroft's DFA minimization algorithm to properly canonicalize and
deduplicate recursive types. Type canonicalization has two stages:

1. Shape canonicalization

 - The top-level structure of HeapTypes is used to split the declared HeapTypes
   into their initial partitions.

 - Hopcroft's algorithm refines the partitions such that all pairs of
   distinguishable types end up in different partitions.

 - A fresh HeapTypeInfo is created for each final partition. Each new
   HeapTypeInfo is linked to other new HeapTypeInfos to create a minimal type
   definition graph that defines the same types as the original graph.

2. Global canonicalization

 - Each new minimal HeapTypeInfo that does not have the same finite
   shape as an existing globally canonical HeapTypeInfo is moved to the
   global heap type store to become the new canonical HeapTypeInfo.

 - Each temporary Type referenced by the newly canonical HeapTypeInfos is
   replaced in-place with the equivalent canonical Type to avoid leaking
   temporary Types into the global stores.

3 files changed, 65 insertions, 23 deletions

diff --git a/test/example/type-builder.cpp b/test/example/type-builder.cpp
index 59222775b..0ac13f974 100644
--- a/test/example/type-builder.cpp
+++ b/test/example/type-builder.cpp
@@ -132,6 +132,7 @@ void test_recursive() {
     std::cout << built[1] << "\n\n";
     assert(built[0].getSignature().results.getHeapType() == built[1]);
     assert(built[1].getSignature().results.getHeapType() == built[0]);
+    assert(built[0] == built[1]);
   }
 
   {
@@ -161,6 +162,10 @@ void test_recursive() {
     assert(built[2].getSignature().results.getHeapType() == built[3]);
     assert(built[3].getSignature().results.getHeapType() == built[4]);
     assert(built[4].getSignature().results.getHeapType() == built[0]);
+    assert(built[0] == built[1]);
+    assert(built[1] == built[2]);
+    assert(built[2] == built[3]);
+    assert(built[3] == built[4]);
   }
 
   {
@@ -189,9 +194,9 @@ void test_recursive() {
     std::cout << built[3] << "\n";
     std::cout << built[4] << "\n";
     std::cout << built[5] << "\n\n";
-    assert(built[0] != built[1]); // TODO: canonicalize recursive types
+    assert(built[0] == built[1]);
     assert(built[2] == built[3]);
-    assert(built[4] != built[5]); // Contain "different" recursive types
+    assert(built[4] == built[5]);
     assert(built[4].getSignature().results.getHeapType() == built[0]);
     assert(built[5].getSignature().results.getHeapType() == built[1]);
     assert(built[0].getSignature().results ==
@@ -199,6 +204,23 @@ void test_recursive() {
     assert(built[1].getSignature().results ==
            Type({Type(built[1], Nullable), Type(built[3], Nullable)}));
   }
+
+  {
+    // Folded and unfolded
+    std::vector<HeapType> built;
+    {
+      TypeBuilder builder(2);
+      Type temp0 = builder.getTempRefType(0, Nullable);
+      builder.setHeapType(0, Signature(Type::none, temp0));
+      builder.setHeapType(1, Signature(Type::none, temp0));
+      built = builder.build();
+    }
+    std::cout << built[0] << "\n";
+    std::cout << built[1] << "\n\n";
+    assert(built[0].getSignature().results.getHeapType() == built[0]);
+    assert(built[1].getSignature().results.getHeapType() == built[0]);
+    assert(built[0] == built[1]);
+  }
 }
 
 int main() {
diff --git a/test/example/type-builder.txt b/test/example/type-builder.txt
index 6b42ade8c..a2985c2ed 100644
--- a/test/example/type-builder.txt
+++ b/test/example/type-builder.txt
@@ -1,17 +1,17 @@
 ;; Test TypeBuilder
 Before setting heap types:
-(ref $sig) => (ref (func))
-(ref $struct) => (ref (func))
-(ref $array) => (ref (func))
-(ref null $array) => (ref null (func))
-(rtt 0 $array) => (rtt 0 (func))
+(ref $sig) => [T](ref [T](func))
+(ref $struct) => [T](ref [T](func))
+(ref $array) => [T](ref [T](func))
+(ref null $array) => [T](ref null [T](func))
+(rtt 0 $array) => [T](rtt 0 [T](func))
 
 After setting heap types:
-(ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))) (result (ref (array (mut externref))) i32)))
-(ref $struct) => (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))
-(ref $array) => (ref (array (mut externref)))
-(ref null $array) => (ref null (array (mut externref)))
-(rtt 0 $array) => (rtt 0 (array (mut externref)))
+(ref $sig) => [T](ref [T](func (param [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))) (result [T](ref [T](array (mut externref))) i32)))
+(ref $struct) => [T](ref [T](struct (field [T](ref null [T](array (mut externref))) (mut [T](rtt 0 [T](array (mut externref)))))))
+(ref $array) => [T](ref [T](array (mut externref)))
+(ref null $array) => [T](ref null [T](array (mut externref)))
+(rtt 0 $array) => [T](rtt 0 [T](array (mut externref)))
 
 After building types:
 (ref $sig) => (ref (func (param (ref (struct (field (ref null (array (mut externref))) (mut (rtt 0 (array (mut externref)))))))) (result (ref (array (mut externref))) i32)))
@@ -24,14 +24,14 @@ After building types:
 ;; Test recursive types
 (func (result (ref null ...1)))
 
-(func (result (ref null (func (result (ref null ...3))))))
-(func (result (ref null (func (result (ref null ...3))))))
+(func (result (ref null ...1)))
+(func (result (ref null ...1)))
 
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
-(func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null (func (result (ref null ...9)))))))))))))))
+(func (result (ref null ...1)))
+(func (result (ref null ...1)))
+(func (result (ref null ...1)))
+(func (result (ref null ...1)))
+(func (result (ref null ...1)))
 
 (func (result (ref null ...1) (ref null (func))))
 (func (result (ref null ...1) (ref null (func))))
@@ -40,3 +40,6 @@ After building types:
 (func (result (ref null (func (result ...1 (ref null (func)))))))
 (func (result (ref null (func (result ...1 (ref null (func)))))))
 
+(func (result (ref null ...1)))
+(func (result (ref null ...1)))
+
diff --git a/test/lit/recursive-types.wast b/test/lit/recursive-types.wast
index 7f719a359..a5d301006 100644
--- a/test/lit/recursive-types.wast
+++ b/test/lit/recursive-types.wast
@@ -2,27 +2,44 @@
 
 ;; RUN: wasm-opt %s -all -S -o - | filecheck %s
 
-;; TODO: Fix the bug where structurally identical types are given the same
-;; generated name, making the wast invalid due to duplicate names.
-
 ;; CHECK:      (module
 ;; CHECK-NEXT:   (type $ref?|...0|_=>_ref?|...0| (func (param (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))))
-;; CHECK-NEXT:   (type $ref?|...0|_=>_ref?|...0| (func (param (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))))
 ;; CHECK-NEXT:   (func $foo (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
 ;; CHECK-NEXT:     (unreachable)
 ;; CHECK-NEXT:   )
 ;; CHECK-NEXT:   (func $bar (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
 ;; CHECK-NEXT:     (unreachable)
 ;; CHECK-NEXT:   )
+;; CHECK-NEXT:   (func $baz (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
+;; CHECK-NEXT:     (unreachable)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:   (func $qux (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
+;; CHECK-NEXT:     (unreachable)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:   (func $quux (param $0 (ref null $ref?|...0|_=>_ref?|...0|)) (result (ref null $ref?|...0|_=>_ref?|...0|))
+;; CHECK-NEXT:     (unreachable)
+;; CHECK-NEXT:   )
 ;; CHECK-NEXT: )
 
 (module
   (type (func (param (ref null 0)) (result (ref null 0))))
   (type (func (param (ref null 1)) (result (ref null 1))))
+  (type (func (param (ref null 0)) (result (ref null 1))))
+  (type (func (param (ref null 3)) (result (ref null 4))))
+  (type (func (param (ref null 4)) (result (ref null 3))))
   (func $foo (type 0)
     (unreachable)
   )
   (func $bar (type 1)
     (unreachable)
   )
+  (func $baz (type 2)
+    (unreachable)
+  )
+  (func $qux (type 3)
+    (unreachable)
+  )
+  (func $quux (type 4)
+    (unreachable)
+  )
 )