From 26d0df73150e0207e6ce6262214bba1453a740d7 Mon Sep 17 00:00:00 2001
From: Thomas Lively <7121787+tlively@users.noreply.github.com>
Date: Fri, 21 Jan 2022 15:58:27 -0800
Subject: Parse, create, and print isorecursive recursion groups (#4464)

In `--hybrid` isorecursive mode, associate each defined type with a recursion
group, represented as a `(rec ...)` wrapping the type definitions in the text
format. Parse that text format, create the rec groups using a new TypeBuilder
method, and print the rec groups in the printer.

The only semantic difference rec groups currently make is that if one type in a
rec group will be included in the output, all the types in that rec group will
be included. This is because changing a rec group in any way (for example by
removing a type) changes the identity of the types in that group in the
isorecursive type system. Notably, rec groups do not yet participate in
validation, so `--hybrid` is largely equivalent to `--nominal` for now.
---
 src/ir/module-utils.cpp | 55 ++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 50 insertions(+), 5 deletions(-)

(limited to 'src/ir/module-utils.cpp')

diff --git a/src/ir/module-utils.cpp b/src/ir/module-utils.cpp
index 9b2293984..0d0ec531c 100644
--- a/src/ir/module-utils.cpp
+++ b/src/ir/module-utils.cpp
@@ -159,11 +159,51 @@ Counts getHeapTypeCounts(Module& wasm) {
         counts.note(*super);
       }
     }
+
+    // Make sure we've noted the complete recursion group of each type as well.
+    auto recGroup = ht.getRecGroup();
+    for (auto type : recGroup) {
+      if (!counts.count(type)) {
+        newTypes.insert(type);
+        counts.note(type);
+      }
+    }
   }
 
   return counts;
 }
 
+void coalesceRecGroups(IndexedHeapTypes& indexedTypes) {
+  if (getTypeSystem() != TypeSystem::Isorecursive) {
+    // No rec groups to coalesce.
+    return;
+  }
+
+  // TODO: Perform a topological sort of the recursion groups to create a valid
+  // ordering rather than this hack that just gets all the types in a group to
+  // be adjacent.
+  assert(indexedTypes.indices.empty());
+  std::unordered_set<HeapType> seen;
+  std::vector<HeapType> grouped;
+  grouped.reserve(indexedTypes.types.size());
+  for (auto type : indexedTypes.types) {
+    if (seen.insert(type).second) {
+      for (auto member : type.getRecGroup()) {
+        grouped.push_back(member);
+        seen.insert(member);
+      }
+    }
+  }
+  assert(grouped.size() == indexedTypes.types.size());
+  indexedTypes.types = grouped;
+}
+
+void setIndices(IndexedHeapTypes& indexedTypes) {
+  for (Index i = 0; i < indexedTypes.types.size(); i++) {
+    indexedTypes.indices[indexedTypes.types[i]] = i;
+  }
+}
+
 } // anonymous namespace
 
 std::vector<HeapType> collectHeapTypes(Module& wasm) {
@@ -179,11 +219,12 @@ std::vector<HeapType> collectHeapTypes(Module& wasm) {
 IndexedHeapTypes getIndexedHeapTypes(Module& wasm) {
   Counts counts = getHeapTypeCounts(wasm);
   IndexedHeapTypes indexedTypes;
-  Index i = 0;
   for (auto& [type, _] : counts) {
     indexedTypes.types.push_back(type);
-    indexedTypes.indices[type] = i++;
   }
+
+  coalesceRecGroups(indexedTypes);
+  setIndices(indexedTypes);
   return indexedTypes;
 }
 
@@ -199,10 +240,14 @@ IndexedHeapTypes getOptimizedIndexedHeapTypes(Module& wasm) {
   // Collect the results.
   IndexedHeapTypes indexedTypes;
   for (Index i = 0; i < sorted.size(); ++i) {
-    HeapType type = sorted[i].first;
-    indexedTypes.types.push_back(type);
-    indexedTypes.indices[type] = i;
+    indexedTypes.types.push_back(sorted[i].first);
   }
+
+  // TODO: Explicitly construct a linear extension of the partial order of
+  // recursion groups by adding edges between unrelated groups according to
+  // their use counts.
+  coalesceRecGroups(indexedTypes);
+  setIndices(indexedTypes);
   return indexedTypes;
 }
 
-- 
cgit v1.2.3