[TypedFunctionReferences] Add Typed Function References feature and use the types (#3388)

This adds the new feature and starts to use the new types where relevant. We
use them even without the feature being enabled, as we don't know the features
during wasm loading - but the hope is that given the type is a subtype, it should
all work out. In practice, if you print out the internal type you may see a typed
function reference-specific type for a ref.func for example, instead of a generic
funcref, but it should not affect anything else.

This PR does not support non-nullable types, that is, everything is nullable
for now. As suggested by @tlively this is simpler for now and leaves nullability
for later work (which will apparently require let or something else, and many
passes may need to be changed).

To allow this PR to work, we need to provide a type on creating a RefFunc. The
wasm-builder.h internal API is updated for this, as are the C and JS APIs,
which are breaking changes. cc @dcodeIO

We must also write and read function types properly. This PR improves
collectSignatures to find all the types, and also to sort them by the
dependencies between them (as we can't emit X in the binary if it depends
on Y, and Y has not been emitted - we need to give Y's index). This sorting
ends up changing a few test outputs.

InstrumentLocals support for printing function types that are not funcref
is disabled for now, until we figure out how to make that work and/or
decide if it's important enough to work on.

The fuzzer has various fixes to emit valid types for things (mostly
whitespace there). Also two drive-by fixes to call makeTrivial where it
should be (when we fail to create a specific node, we can't just try to make
another node, in theory it could infinitely recurse).

Binary writing changes here to replace calls to a standalone function to
write out a type with one that is called on the binary writer object itself,
which maintains a mapping of type indexes (getFunctionSignatureByIndex).

1 files changed, 75 insertions, 3 deletions

diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index a2d256073..c8776297c 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -414,16 +414,29 @@ collectSignatures(Module& wasm,
       Counts& counts;
 
       TypeCounter(Counts& counts) : counts(counts) {}
+
       void visitExpression(Expression* curr) {
-        if (auto* call = curr->dynCast<CallIndirect>()) {
+        if (curr->is<RefNull>()) {
+          maybeNote(curr->type);
+        } else if (auto* call = curr->dynCast<CallIndirect>()) {
           counts[call->sig]++;
         } else if (Properties::isControlFlowStructure(curr)) {
-          // TODO: Allow control flow to have input types as well
+          maybeNote(curr->type);
           if (curr->type.isTuple()) {
+            // TODO: Allow control flow to have input types as well
             counts[Signature(Type::none, curr->type)]++;
           }
         }
       }
+
+      void maybeNote(Type type) {
+        if (type.isRef()) {
+          auto heapType = type.getHeapType();
+          if (heapType.isSignature()) {
+            counts[heapType.getSignature()]++;
+          }
+        }
+      }
     };
     TypeCounter(counts).walk(func->body);
   };
@@ -434,6 +447,14 @@ collectSignatures(Module& wasm,
   Counts counts;
   for (auto& curr : wasm.functions) {
     counts[curr->sig]++;
+    for (auto type : curr->vars) {
+      if (type.isRef()) {
+        auto heapType = type.getHeapType();
+        if (heapType.isSignature()) {
+          counts[heapType.getSignature()]++;
+        }
+      }
+    }
   }
   for (auto& curr : wasm.events) {
     counts[curr->sig]++;
@@ -444,10 +465,61 @@ collectSignatures(Module& wasm,
       counts[innerPair.first] += innerPair.second;
     }
   }
+
+  // TODO: recursively traverse each reference type, which may have a child type
+  //       this is itself a reference type.
+
+  // We must sort all the dependencies of a signature before it. For example,
+  // (func (param (ref (func)))) must appear after (func). To do that, find the
+  // depth of dependencies of each signature. For example, if A depends on B
+  // which depends on C, then A's depth is 2, B's is 1, and C's is 0 (assuming
+  // no other dependencies).
+  Counts depthOfDependencies;
+  std::unordered_map<Signature, std::unordered_set<Signature>> isDependencyOf;
+  // To calculate the depth of dependencies, we'll do a flow analysis, visiting
+  // each signature as we find out new things about it.
+  std::set<Signature> toVisit;
+  for (auto& pair : counts) {
+    auto sig = pair.first;
+    depthOfDependencies[sig] = 0;
+    toVisit.insert(sig);
+    for (Type type : {sig.params, sig.results}) {
+      for (auto element : type) {
+        if (element.isRef()) {
+          auto heapType = element.getHeapType();
+          if (heapType.isSignature()) {
+            isDependencyOf[heapType.getSignature()].insert(sig);
+          }
+        }
+      }
+    }
+  }
+  while (!toVisit.empty()) {
+    auto iter = toVisit.begin();
+    auto sig = *iter;
+    toVisit.erase(iter);
+    // Anything that depends on this has a depth of dependencies equal to this
+    // signature's, plus this signature itself.
+    auto newDepth = depthOfDependencies[sig] + 1;
+    if (newDepth > counts.size()) {
+      Fatal() << "Cyclic signatures detected, cannot sort them.";
+    }
+    for (auto& other : isDependencyOf[sig]) {
+      if (depthOfDependencies[other] < newDepth) {
+        // We found something new to propagate.
+        depthOfDependencies[other] = newDepth;
+        toVisit.insert(other);
+      }
+    }
+  }
+  // Sort by frequency and then simplicity, and also keeping every signature
+  // before things that depend on it.
   std::vector<std::pair<Signature, size_t>> sorted(counts.begin(),
                                                    counts.end());
   std::sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
-    // order by frequency then simplicity
+    if (depthOfDependencies[a.first] != depthOfDependencies[b.first]) {
+      return depthOfDependencies[a.first] < depthOfDependencies[b.first];
+    }
     if (a.second != b.second) {
       return a.second > b.second;
     }