Remove FunctionType from Event (#2466)

This is the start of a larger refactoring to remove FunctionType entirely and
store types and signatures directly on the entities that use them. This PR
updates BrOnExn and Events to remove their use of FunctionType and makes the
BinaryWriter traverse the module and collect types rather than using the global
FunctionType list. While we are collecting types, we also sort them by frequency
as an optimization. Remaining uses of FunctionType in Function, CallIndirect,
and parsing will be removed in a future PR.

22 files changed, 252 insertions, 223 deletions

diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index d33f40cdb..509e9b569 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -3262,19 +3262,18 @@ void BinaryenRemoveGlobal(BinaryenModuleRef module, const char* name) {
 BinaryenEventRef BinaryenAddEvent(BinaryenModuleRef module,
                                   const char* name,
                                   uint32_t attribute,
-                                  BinaryenFunctionTypeRef type) {
+                                  BinaryenType params,
+                                  BinaryenType results) {
   if (tracing) {
     std::cout << "  BinaryenAddEvent(the_module, \"" << name << "\", "
-              << attribute << ", functionTypes[" << functionTypes[type]
-              << "]);\n";
+              << attribute << ", " << params << ", " << results << ");\n";
   }
 
   auto* wasm = (Module*)module;
   auto* ret = new Event();
   ret->name = name;
   ret->attribute = attribute;
-  ret->type = ((FunctionType*)type)->name;
-  ret->params = ((FunctionType*)type)->params;
+  ret->sig = Signature(Type(params), Type(results));
   wasm->addEvent(ret);
   return ret;
 }
@@ -3378,22 +3377,22 @@ void BinaryenAddEventImport(BinaryenModuleRef module,
                             const char* externalModuleName,
                             const char* externalBaseName,
                             uint32_t attribute,
-                            BinaryenFunctionTypeRef eventType) {
+                            BinaryenType params,
+                            BinaryenType results) {
   auto* wasm = (Module*)module;
   auto* ret = new Event();
 
   if (tracing) {
     std::cout << "  BinaryenAddEventImport(the_module, \"" << internalName
               << "\", \"" << externalModuleName << "\", \"" << externalBaseName
-              << "\", " << attribute << ", functionTypes["
-              << functionTypes[eventType] << "]);\n";
+              << "\", " << attribute << ", " << params << ", " << results
+              << ");\n";
   }
 
   ret->name = internalName;
   ret->module = externalModuleName;
   ret->base = externalBaseName;
-  ret->type = ((FunctionType*)eventType)->name;
-  ret->params = ((FunctionType*)eventType)->params;
+  ret->sig = Signature(Type(params), Type(results));
   wasm->addEvent(ret);
 }
 
@@ -4315,31 +4314,21 @@ int BinaryenEventGetAttribute(BinaryenEventRef event) {
 
   return ((Event*)event)->attribute;
 }
-const char* BinaryenEventGetType(BinaryenEventRef event) {
+BinaryenType BinaryenEventGetParams(BinaryenEventRef event) {
   if (tracing) {
-    std::cout << "  BinaryenEventGetType(events[" << events[event] << "]);\n";
+    std::cout << "  BinaryenEventGetParams(events[" << events[event] << "]);\n";
   }
 
-  return ((Event*)event)->type.c_str();
+  return ((Event*)event)->sig.params;
 }
-BinaryenIndex BinaryenEventGetNumParams(BinaryenEventRef event) {
-  if (tracing) {
-    std::cout << "  BinaryenEventGetNumParams(events[" << events[event]
-              << "]);\n";
-  }
 
-  return ((Event*)event)->params.size();
-}
-BinaryenType BinaryenEventGetParam(BinaryenEventRef event,
-                                   BinaryenIndex index) {
+BinaryenType BinaryenEventGetResults(BinaryenEventRef event) {
   if (tracing) {
-    std::cout << "  BinaryenEventGetParam(events[" << events[event] << "], "
-              << index << ");\n";
+    std::cout << "  BinaryenEventGetResults(events[" << events[event]
+              << "]);\n";
   }
 
-  auto* fn = (Event*)event;
-  assert(index < fn->params.size());
-  return fn->params[index];
+  return ((Event*)event)->sig.results;
 }
 
 //
diff --git a/src/binaryen-c.h b/src/binaryen-c.h
index 726129983..b5d023400 100644
--- a/src/binaryen-c.h
+++ b/src/binaryen-c.h
@@ -1118,7 +1118,8 @@ BINARYEN_API void BinaryenAddEventImport(BinaryenModuleRef module,
                                          const char* externalModuleName,
                                          const char* externalBaseName,
                                          uint32_t attribute,
-                                         BinaryenFunctionTypeRef eventType);
+                                         BinaryenType params,
+                                         BinaryenType results);
 
 // Exports
 
@@ -1164,7 +1165,8 @@ typedef void* BinaryenEventRef;
 BINARYEN_API BinaryenEventRef BinaryenAddEvent(BinaryenModuleRef module,
                                                const char* name,
                                                uint32_t attribute,
-                                               BinaryenFunctionTypeRef type);
+                                               BinaryenType params,
+                                               BinaryenType results);
 BINARYEN_API BinaryenEventRef BinaryenGetEvent(BinaryenModuleRef module,
                                                const char* name);
 BINARYEN_API void BinaryenRemoveEvent(BinaryenModuleRef module,
@@ -1437,14 +1439,10 @@ BinaryenGlobalGetInitExpr(BinaryenGlobalRef global);
 BINARYEN_API const char* BinaryenEventGetName(BinaryenEventRef event);
 // Gets the attribute of the specified `Event`.
 BINARYEN_API int BinaryenEventGetAttribute(BinaryenEventRef event);
-// Gets the name of the `FunctionType` associated with the specified `Event`.
-BINARYEN_API const char* BinaryenEventGetType(BinaryenEventRef event);
-// Gets the number of parameters of the specified `Event`.
-BINARYEN_API BinaryenIndex BinaryenEventGetNumParams(BinaryenEventRef event);
-// Gets the type of the parameter at the specified index of the specified
-// `Event`.
-BINARYEN_API BinaryenType BinaryenEventGetParam(BinaryenEventRef event,
-                                                BinaryenIndex index);
+// Gets the parameters type of the specified `Event`.
+BINARYEN_API BinaryenType BinaryenEventGetParams(BinaryenEventRef event);
+// Gets the results type of the specified `Event`.
+BINARYEN_API BinaryenType BinaryenEventGetResults(BinaryenEventRef event);
 
 //
 // ========== Import Operations ==========
diff --git a/src/ir/ExpressionManipulator.cpp b/src/ir/ExpressionManipulator.cpp
index fdefbb2e0..2542e5743 100644
--- a/src/ir/ExpressionManipulator.cpp
+++ b/src/ir/ExpressionManipulator.cpp
@@ -242,7 +242,7 @@ flexibleCopy(Expression* original, Module& wasm, CustomCopier custom) {
     }
     Expression* visitBrOnExn(BrOnExn* curr) {
       return builder.makeBrOnExn(
-        curr->name, curr->event, copy(curr->exnref), curr->eventParams);
+        curr->name, curr->event, copy(curr->exnref), curr->sent);
     }
     Expression* visitNop(Nop* curr) { return builder.makeNop(); }
     Expression* visitUnreachable(Unreachable* curr) {
diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index 9ee109f5e..007a7ee55 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -164,7 +164,7 @@ void ReFinalize::visitThrow(Throw* curr) { curr->finalize(); }
 void ReFinalize::visitRethrow(Rethrow* curr) { curr->finalize(); }
 void ReFinalize::visitBrOnExn(BrOnExn* curr) {
   curr->finalize();
-  updateBreakValueType(curr->name, curr->getSingleSentType());
+  updateBreakValueType(curr->name, curr->sent);
 }
 void ReFinalize::visitNop(Nop* curr) { curr->finalize(); }
 void ReFinalize::visitUnreachable(Unreachable* curr) { curr->finalize(); }
diff --git a/src/ir/branch-utils.h b/src/ir/branch-utils.h
index 976dd72ec..c4ff26c0c 100644
--- a/src/ir/branch-utils.h
+++ b/src/ir/branch-utils.h
@@ -221,7 +221,7 @@ struct BranchSeeker : public PostWalker<BranchSeeker> {
     }
     // check the br_on_exn
     if (curr->name == target) {
-      noteFound(curr->getSingleSentType());
+      noteFound(curr->sent);
     }
   }
 
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 52765035c..0fd478551 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -38,51 +38,25 @@ struct BinaryIndexes {
   std::unordered_map<Name, Index> eventIndexes;
 
   BinaryIndexes(Module& wasm) {
-    auto addGlobal = [&](Global* curr) {
-      auto index = globalIndexes.size();
-      globalIndexes[curr->name] = index;
-    };
-    for (auto& curr : wasm.globals) {
-      if (curr->imported()) {
-        addGlobal(curr.get());
-      }
-    }
-    for (auto& curr : wasm.globals) {
-      if (!curr->imported()) {
-        addGlobal(curr.get());
-      }
-    }
-    assert(globalIndexes.size() == wasm.globals.size());
-    auto addFunction = [&](Function* curr) {
-      auto index = functionIndexes.size();
-      functionIndexes[curr->name] = index;
-    };
-    for (auto& curr : wasm.functions) {
-      if (curr->imported()) {
-        addFunction(curr.get());
+    auto addIndexes = [&](auto& source, auto& indexes) {
+      auto addIndex = [&](auto* curr) {
+        auto index = indexes.size();
+        indexes[curr->name] = index;
+      };
+      for (auto& curr : source) {
+        if (curr->imported()) {
+          addIndex(curr.get());
+        }
       }
-    }
-    for (auto& curr : wasm.functions) {
-      if (!curr->imported()) {
-        addFunction(curr.get());
+      for (auto& curr : source) {
+        if (!curr->imported()) {
+          addIndex(curr.get());
+        }
       }
-    }
-    assert(functionIndexes.size() == wasm.functions.size());
-    auto addEvent = [&](Event* curr) {
-      auto index = eventIndexes.size();
-      eventIndexes[curr->name] = index;
     };
-    for (auto& curr : wasm.events) {
-      if (curr->imported()) {
-        addEvent(curr.get());
-      }
-    }
-    for (auto& curr : wasm.events) {
-      if (!curr->imported()) {
-        addEvent(curr.get());
-      }
-    }
-    assert(eventIndexes.size() == wasm.events.size());
+    addIndexes(wasm.functions, functionIndexes);
+    addIndexes(wasm.globals, globalIndexes);
+    addIndexes(wasm.events, eventIndexes);
   }
 };
 
@@ -126,8 +100,7 @@ inline Event* copyEvent(Event* event, Module& out) {
   auto* ret = new Event();
   ret->name = event->name;
   ret->attribute = event->attribute;
-  ret->type = event->type;
-  ret->params = event->params;
+  ret->sig = event->sig;
   out.addEvent(ret);
   return ret;
 }
diff --git a/src/ir/type-updating.h b/src/ir/type-updating.h
index 1fa891ec1..d64ae0158 100644
--- a/src/ir/type-updating.h
+++ b/src/ir/type-updating.h
@@ -154,7 +154,7 @@ struct TypeUpdater
     } else if (auto* sw = curr->dynCast<Switch>()) {
       applySwitchChanges(sw, change);
     } else if (auto* br = curr->dynCast<BrOnExn>()) {
-      noteBreakChange(br->name, change, br->getSingleSentType());
+      noteBreakChange(br->name, change, br->sent);
     }
   }
 
diff --git a/src/js/binaryen.js-post.js b/src/js/binaryen.js-post.js
index 1f2c414e5..d5943176e 100644
--- a/src/js/binaryen.js-post.js
+++ b/src/js/binaryen.js-post.js
@@ -2057,9 +2057,9 @@ function wrapModule(module, self) {
       return Module['_BinaryenRemoveGlobal'](module, strToStack(name));
     });
   }
-  self['addEvent'] = function(name, attribute, eventType) {
+  self['addEvent'] = function(name, attribute, params, results) {
     return preserveStack(function() {
-      return Module['_BinaryenAddEvent'](module, strToStack(name), attribute, eventType);
+      return Module['_BinaryenAddEvent'](module, strToStack(name), attribute, params, results);
     });
   };
   self['getEvent'] = function(name) {
@@ -2092,9 +2092,9 @@ function wrapModule(module, self) {
       return Module['_BinaryenAddGlobalImport'](module, strToStack(internalName), strToStack(externalModuleName), strToStack(externalBaseName), globalType, mutable);
     });
   };
-  self['addEventImport'] = function(internalName, externalModuleName, externalBaseName, attribute, eventType) {
+  self['addEventImport'] = function(internalName, externalModuleName, externalBaseName, attribute, params, results) {
     return preserveStack(function() {
-      return Module['_BinaryenAddEventImport'](module, strToStack(internalName), strToStack(externalModuleName), strToStack(externalBaseName), attribute, eventType);
+      return Module['_BinaryenAddEventImport'](module, strToStack(internalName), strToStack(externalModuleName), strToStack(externalBaseName), attribute, params, results);
     });
   };
   self['addExport'] = // deprecated
@@ -2740,7 +2740,8 @@ Module['getEventInfo'] = function(event_) {
     'module': UTF8ToString(Module['_BinaryenEventImportGetModule'](event_)),
     'base': UTF8ToString(Module['_BinaryenEventImportGetBase'](event_)),
     'attribute': Module['_BinaryenEventGetAttribute'](event_),
-    'type': UTF8ToString(Module['_BinaryenEventGetType'](event_))
+    'params': Module['_BinaryenEventGetParams'](event_),
+    'results': Module['_BinaryenEventGetResults'](event_)
   };
 };
 
diff --git a/src/pass.h b/src/pass.h
index 0d0b14883..46b603f00 100644
--- a/src/pass.h
+++ b/src/pass.h
@@ -268,7 +268,7 @@ public:
   // should always be safe *unless* you do something in the pass that makes it
   // not thread-safe; in other words, the Module and Function objects and
   // so forth are set up so that Functions can be processed in parallel, so
-  // if you do not ad global state that could be raced on, your pass could be
+  // if you do not add global state that could be raced on, your pass could be
   // function-parallel.
   //
   // Function-parallel passes create an instance of the Walker class per
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index f51bccf27..fef4ac01d 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -2056,7 +2056,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     o << "(event ";
     printName(curr->name, o);
     o << maybeSpace << "(attr " << curr->attribute << ')' << maybeSpace;
-    o << ParamType(Type(curr->params));
+    o << ParamType(curr->sig.params);
     o << "))";
     o << maybeNewLine;
   }
@@ -2066,7 +2066,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     printMedium(o, "event ");
     printName(curr->name, o);
     o << maybeSpace << "(attr " << curr->attribute << ')' << maybeSpace;
-    o << ParamType(Type(curr->params));
+    o << ParamType(curr->sig.params);
     o << ")" << maybeNewLine;
   }
   void printTableHeader(Table* curr) {
diff --git a/src/passes/RemoveUnusedModuleElements.cpp b/src/passes/RemoveUnusedModuleElements.cpp
index 806545adf..20ce284f7 100644
--- a/src/passes/RemoveUnusedModuleElements.cpp
+++ b/src/passes/RemoveUnusedModuleElements.cpp
@@ -301,9 +301,6 @@ struct RemoveUnusedModuleElements : public Pass {
     for (auto* call : analyzer.indirectCalls) {
       call->fullType = canonicalize(call->fullType);
     }
-    for (auto* event : analyzer.events) {
-      event->type = canonicalize(event->type);
-    }
     // remove no-longer used types
     module->functionTypes.erase(
       std::remove_if(module->functionTypes.begin(),
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index fe4a3955a..571dad79e 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -406,20 +406,14 @@ private:
     Index num = upTo(3);
     for (size_t i = 0; i < num; i++) {
       // Events should have void return type and at least one param type
-      Type type = pick(i32, i64, f32, f64);
-      std::string sig = std::string("v") + getSig(type);
       std::vector<Type> params;
-      params.push_back(type);
       Index numValues = upToSquared(MAX_PARAMS - 1);
-      for (Index i = 0; i < numValues; i++) {
-        type = pick(i32, i64, f32, f64);
-        sig += getSig(type);
-        params.push_back(type);
+      for (Index i = 0; i < numValues + 1; i++) {
+        params.push_back(pick(i32, i64, f32, f64));
       }
       auto* event = builder.makeEvent(std::string("event$") + std::to_string(i),
                                       WASM_EVENT_ATTRIBUTE_EXCEPTION,
-                                      ensureFunctionType(sig, &wasm)->name,
-                                      std::move(params));
+                                      Signature(Type(params), Type::none));
       wasm.addEvent(event);
     }
   }
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 7014fd875..78fd72e38 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1002,7 +1002,6 @@ public:
   void writeStart();
   void writeMemory();
   void writeTypes();
-  int32_t getFunctionTypeIndex(Name type);
   void writeImports();
 
   void writeFunctionSignatures();
@@ -1014,9 +1013,10 @@ public:
   void writeDataSegments();
   void writeEvents();
 
-  uint32_t getFunctionIndex(Name name);
-  uint32_t getGlobalIndex(Name name);
-  uint32_t getEventIndex(Name name);
+  uint32_t getFunctionIndex(Name name) const;
+  uint32_t getGlobalIndex(Name name) const;
+  uint32_t getEventIndex(Name name) const;
+  uint32_t getTypeIndex(Signature sig) const;
 
   void writeFunctionTableDeclaration();
   void writeTableElements();
@@ -1060,6 +1060,8 @@ private:
   BufferWithRandomAccess& o;
   bool debug;
   ModuleUtils::BinaryIndexes indexes;
+  std::unordered_map<Signature, Index> typeIndexes;
+  std::vector<Signature> types;
 
   bool debugInfo = true;
   std::ostream* sourceMap = nullptr;
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 87b1f0306..533f83d94 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -541,19 +541,16 @@ public:
     return ret;
   }
   BrOnExn* makeBrOnExn(Name name, Event* event, Expression* exnref) {
-    return makeBrOnExn(name, event->name, exnref, event->params);
+    return makeBrOnExn(name, event->name, exnref, event->sig.params);
   }
-  BrOnExn* makeBrOnExn(Name name,
-                       Name event,
-                       Expression* exnref,
-                       std::vector<Type>& eventParams) {
+  BrOnExn* makeBrOnExn(Name name, Name event, Expression* exnref, Type sent) {
     auto* ret = allocator.alloc<BrOnExn>();
     ret->name = name;
     ret->event = event;
     ret->exnref = exnref;
     // Copy params info into BrOnExn, because it is necessary when BrOnExn is
     // refinalized without the module.
-    ret->eventParams = eventParams;
+    ret->sent = sent;
     ret->finalize();
     return ret;
   }
@@ -765,16 +762,11 @@ public:
     return glob;
   }
 
-  // TODO Remove 'type' parameter once we remove FunctionType
-  static Event* makeEvent(Name name,
-                          uint32_t attribute,
-                          Name type,
-                          std::vector<Type>&& params) {
+  static Event* makeEvent(Name name, uint32_t attribute, Signature sig) {
     auto* event = new Event;
     event->name = name;
     event->attribute = attribute;
-    event->type = type;
-    event->params = params;
+    event->sig = sig;
     return event;
   }
 };
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 371d3216f..7b3845aec 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -74,6 +74,9 @@ public:
   bool operator!=(const Type& other) const { return id != other.id; }
   bool operator!=(const ValueType& other) const { return id != other; }
 
+  // Order types by some notion of simplicity
+  bool operator<(const Type& other) const;
+
   // Allows for using Types in switch statements
   constexpr operator uint32_t() const { return id; }
   std::string toString() const;
@@ -97,6 +100,18 @@ std::ostream& operator<<(std::ostream& os, Type t);
 std::ostream& operator<<(std::ostream& os, ParamType t);
 std::ostream& operator<<(std::ostream& os, ResultType t);
 
+struct Signature {
+  Type params;
+  Type results;
+  Signature() = default;
+  Signature(Type params, Type results) : params(params), results(results) {}
+  bool operator==(const Signature& other) const {
+    return params == other.params && results == other.results;
+  }
+  bool operator!=(const Signature& other) const { return !(*this == other); }
+  bool operator<(const Signature& other) const;
+};
+
 constexpr Type none = Type::none;
 constexpr Type i32 = Type::i32;
 constexpr Type i64 = Type::i64;
@@ -114,4 +129,9 @@ Type reinterpretType(Type type);
 
 } // namespace wasm
 
+template<> class std::hash<wasm::Signature> {
+public:
+  size_t operator()(const wasm::Signature& sig) const;
+};
+
 #endif // wasm_wasm_type_h
diff --git a/src/wasm.h b/src/wasm.h
index 77eeea5d3..08b85402e 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -1123,10 +1123,9 @@ public:
   Expression* exnref;
   // This is duplicate info of param types stored in Event, but this is required
   // for us to know the type of the value sent to the target block.
-  std::vector<Type> eventParams;
+  Type sent;
 
   void finalize();
-  Type getSingleSentType();
 };
 
 // Globals
@@ -1320,14 +1319,7 @@ public:
   Name name;
   // Kind of event. Currently only WASM_EVENT_ATTRIBUTE_EXCEPTION is possible.
   uint32_t attribute = WASM_EVENT_ATTRIBUTE_EXCEPTION;
-  // Type string in the format of function type. Return type is considered as a
-  // void type. So if you have an event whose type is (i32, i32), the type
-  // string will be "vii".
-  Name type;
-  // This is duplicate info of 'Name type', but we store this anyway because
-  // we plan to remove FunctionType in future.
-  // TODO remove either this or FunctionType
-  std::vector<Type> params;
+  Signature sig;
 };
 
 // "Opaque" data, not part of the core wasm spec, that is held in binaries.
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 8f2fe3fe7..2336da912 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -16,6 +16,7 @@
 
 #include <algorithm>
 #include <fstream>
+#include <shared_mutex>
 
 #include "support/bits.h"
 #include "wasm-binary.h"
@@ -24,15 +25,74 @@
 namespace wasm {
 
 void WasmBinaryWriter::prepare() {
-  // we need function types for all our functions
-  for (auto& func : wasm->functions) {
-    if (func->type.isNull()) {
-      func->type = ensureFunctionType(getSig(func.get()), wasm)->name;
+  // Collect function types and their frequencies
+  using Counts = std::unordered_map<Signature, size_t>;
+  using AtomicCounts = std::unordered_map<Signature, std::atomic_size_t>;
+  Counts counts;
+  for (auto& curr : wasm->functions) {
+    counts[Signature(Type(curr->params), curr->result)]++;
+  }
+  for (auto& curr : wasm->events) {
+    counts[curr->sig]++;
+  }
+
+  // Parallelize collection of call_indirect type counts
+  struct TypeCounter : WalkerPass<PostWalker<TypeCounter>> {
+    AtomicCounts& counts;
+    std::shared_timed_mutex& mutex;
+    TypeCounter(AtomicCounts& counts, std::shared_timed_mutex& mutex)
+      : counts(counts), mutex(mutex) {}
+    bool isFunctionParallel() override { return true; }
+    bool modifiesBinaryenIR() override { return false; }
+    void visitCallIndirect(CallIndirect* curr) {
+      auto* type = getModule()->getFunctionType(curr->fullType);
+      Signature sig(Type(type->params), type->result);
+      {
+        std::shared_lock<std::shared_timed_mutex> lock(mutex);
+        auto it = counts.find(sig);
+        if (it != counts.end()) {
+          it->second++;
+          return;
+        }
+      }
+      {
+        std::lock_guard<std::shared_timed_mutex> lock(mutex);
+        counts[sig]++;
+      }
+    }
+    Pass* create() override { return new TypeCounter(counts, mutex); }
+  };
+
+  std::shared_timed_mutex mutex;
+  AtomicCounts parallelCounts;
+  for (auto& kv : counts) {
+    parallelCounts[kv.first] = 0;
+  }
+
+  TypeCounter counter(parallelCounts, mutex);
+  PassRunner runner(wasm);
+  runner.setIsNested(true);
+  counter.run(&runner, wasm);
+
+  for (auto& kv : parallelCounts) {
+    counts[kv.first] += kv.second;
+  }
+
+  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 (a.second != b.second) {
+      return a.second > b.second;
+    } else {
+      return a.first < b.first;
     }
-    // TODO: depending on upstream flux
-    // https://github.com/WebAssembly/spec/pull/301 might want this:
-    // assert(!func->type.isNull());
+  });
+  for (Index i = 0; i < sorted.size(); ++i) {
+    typeIndexes[sorted[i].first] = i;
+    types.push_back(sorted[i].first);
   }
+
   importInfo = wasm::make_unique<ImportInfo>(*wasm);
 }
 
@@ -173,43 +233,30 @@ void WasmBinaryWriter::writeMemory() {
 }
 
 void WasmBinaryWriter::writeTypes() {
-  if (wasm->functionTypes.size() == 0) {
+  if (types.size() == 0) {
     return;
   }
   if (debug) {
     std::cerr << "== writeTypes" << std::endl;
   }
   auto start = startSection(BinaryConsts::Section::Type);
-  o << U32LEB(wasm->functionTypes.size());
-  for (auto& type : wasm->functionTypes) {
+  o << U32LEB(types.size());
+  for (Index i = 0; i < types.size(); ++i) {
+    Signature& sig = types[i];
     if (debug) {
-      std::cerr << "write one" << std::endl;
+      std::cerr << "write " << sig.params << " -> " << sig.results << std::endl;
     }
     o << S32LEB(BinaryConsts::EncodedType::Func);
-    o << U32LEB(type->params.size());
-    for (auto param : type->params) {
-      o << binaryType(param);
-    }
-    if (type->result == none) {
-      o << U32LEB(0);
-    } else {
-      o << U32LEB(1);
-      o << binaryType(type->result);
+    for (auto& sigType : {sig.params, sig.results}) {
+      o << U32LEB(sigType.size());
+      for (auto type : sigType.expand()) {
+        o << binaryType(type);
+      }
     }
   }
   finishSection(start);
 }
 
-int32_t WasmBinaryWriter::getFunctionTypeIndex(Name type) {
-  // TODO: optimize
-  for (size_t i = 0; i < wasm->functionTypes.size(); i++) {
-    if (wasm->functionTypes[i]->name == type) {
-      return i;
-    }
-  }
-  abort();
-}
-
 void WasmBinaryWriter::writeImports() {
   auto num = importInfo->getNumImports();
   if (num == 0) {
@@ -230,7 +277,7 @@ void WasmBinaryWriter::writeImports() {
     }
     writeImportHeader(func);
     o << U32LEB(int32_t(ExternalKind::Function));
-    o << U32LEB(getFunctionTypeIndex(func->type));
+    o << U32LEB(getTypeIndex(Signature(Type(func->params), func->result)));
   });
   ModuleUtils::iterImportedGlobals(*wasm, [&](Global* global) {
     if (debug) {
@@ -248,7 +295,7 @@ void WasmBinaryWriter::writeImports() {
     writeImportHeader(event);
     o << U32LEB(int32_t(ExternalKind::Event));
     o << U32LEB(event->attribute);
-    o << U32LEB(getFunctionTypeIndex(event->type));
+    o << U32LEB(getTypeIndex(event->sig));
   });
   if (wasm->memory.imported()) {
     if (debug) {
@@ -289,7 +336,7 @@ void WasmBinaryWriter::writeFunctionSignatures() {
     if (debug) {
       std::cerr << "write one" << std::endl;
     }
-    o << U32LEB(getFunctionTypeIndex(func->type));
+    o << U32LEB(getTypeIndex(Signature(Type(func->params), func->result)));
   });
   finishSection(start);
 }
@@ -451,19 +498,28 @@ void WasmBinaryWriter::writeDataSegments() {
   finishSection(start);
 }
 
-uint32_t WasmBinaryWriter::getFunctionIndex(Name name) {
-  assert(indexes.functionIndexes.count(name));
-  return indexes.functionIndexes[name];
+uint32_t WasmBinaryWriter::getFunctionIndex(Name name) const {
+  auto it = indexes.functionIndexes.find(name);
+  assert(it != indexes.functionIndexes.end());
+  return it->second;
+}
+
+uint32_t WasmBinaryWriter::getGlobalIndex(Name name) const {
+  auto it = indexes.globalIndexes.find(name);
+  assert(it != indexes.globalIndexes.end());
+  return it->second;
 }
 
-uint32_t WasmBinaryWriter::getGlobalIndex(Name name) {
-  assert(indexes.globalIndexes.count(name));
-  return indexes.globalIndexes[name];
+uint32_t WasmBinaryWriter::getEventIndex(Name name) const {
+  auto it = indexes.eventIndexes.find(name);
+  assert(it != indexes.eventIndexes.end());
+  return it->second;
 }
 
-uint32_t WasmBinaryWriter::getEventIndex(Name name) {
-  assert(indexes.eventIndexes.count(name));
-  return indexes.eventIndexes[name];
+uint32_t WasmBinaryWriter::getTypeIndex(Signature sig) const {
+  auto it = typeIndexes.find(sig);
+  assert(it != typeIndexes.end());
+  return it->second;
 }
 
 void WasmBinaryWriter::writeFunctionTableDeclaration() {
@@ -521,7 +577,7 @@ void WasmBinaryWriter::writeEvents() {
       std::cerr << "write one" << std::endl;
     }
     o << U32LEB(event->attribute);
-    o << U32LEB(getFunctionTypeIndex(event->type));
+    o << U32LEB(getTypeIndex(event->sig));
   });
 
   finishSection(start);
@@ -1364,10 +1420,9 @@ void WasmBinaryBuilder::readImports() {
           throwError("invalid event index " + std::to_string(index) + " / " +
                      std::to_string(wasm.functionTypes.size()));
         }
-        Name type = wasm.functionTypes[index]->name;
-        std::vector<Type> params = wasm.functionTypes[index]->params;
+        Type params = Type(wasm.functionTypes[index]->params);
         auto* curr =
-          builder.makeEvent(name, attribute, type, std::move(params));
+          builder.makeEvent(name, attribute, Signature(params, Type::none));
         curr->module = module;
         curr->base = base;
         wasm.addEvent(curr);
@@ -2039,10 +2094,9 @@ void WasmBinaryBuilder::readEvents() {
       throwError("invalid event index " + std::to_string(typeIndex) + " / " +
                  std::to_string(wasm.functionTypes.size()));
     }
-    Name type = wasm.functionTypes[typeIndex]->name;
-    std::vector<Type> params = wasm.functionTypes[typeIndex]->params;
+    Type params = Type(wasm.functionTypes[typeIndex]->params);
     wasm.addEvent(Builder::makeEvent(
-      "event$" + std::to_string(i), attribute, type, std::move(params)));
+      "event$" + std::to_string(i), attribute, Signature(params, Type::none)));
   }
 }
 
@@ -4603,7 +4657,7 @@ void WasmBinaryBuilder::visitThrow(Throw* curr) {
   }
   auto* event = wasm.events[index].get();
   curr->event = event->name;
-  size_t num = event->params.size();
+  size_t num = event->sig.params.size();
   curr->operands.resize(num);
   for (size_t i = 0; i < num; i++) {
     curr->operands[num - i - 1] = popNonVoidExpression();
@@ -4637,7 +4691,7 @@ void WasmBinaryBuilder::visitBrOnExn(BrOnExn* curr) {
 
   // Copy params info into BrOnExn, because it is necessary when BrOnExn is
   // refinalized without the module.
-  curr->eventParams = event->params;
+  curr->sent = event->sig.params;
   curr->finalize();
 }
 
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 307c94375..3a761fd17 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1859,7 +1859,7 @@ Expression* SExpressionWasmBuilder::makeBrOnExn(Element& s) {
   assert(event && "br_on_exn's event must exist");
   // Copy params info into BrOnExn, because it is necessary when BrOnExn is
   // refinalized without the module.
-  ret->eventParams = event->params;
+  ret->sent = event->sig.params;
   ret->finalize();
   return ret;
 }
@@ -2193,7 +2193,6 @@ void SExpressionWasmBuilder::parseImport(Element& s) {
       j = parseMemoryLimits(inner, j);
     }
   } else if (kind == ExternalKind::Event) {
-    FunctionType* functionType = nullptr;
     auto event = make_unique<Event>();
     if (j >= inner.size()) {
       throw ParseException("event does not have an attribute", s.line, s.col);
@@ -2203,12 +2202,14 @@ void SExpressionWasmBuilder::parseImport(Element& s) {
       throw ParseException("invalid attribute", attrElem.line, attrElem.col);
     }
     event->attribute = atoi(attrElem[1]->c_str());
-    Type fakeResult; // just to call parseTypeUse
-    j = parseTypeUse(inner, j, functionType, event->params, fakeResult);
+    std::vector<Type> paramTypes;
+    FunctionType* fakeFunctionType; // just to call parseTypeUse
+    Type results;
+    j = parseTypeUse(inner, j, fakeFunctionType, paramTypes, results);
     event->name = name;
     event->module = module;
     event->base = base;
-    event->type = functionType->name;
+    event->sig = Signature(Type(paramTypes), results);
     wasm.addEvent(event.release());
   }
   // If there are more elements, they are invalid
@@ -2514,11 +2515,11 @@ void SExpressionWasmBuilder::parseEvent(Element& s, bool preParseImport) {
   event->attribute = atoi(attrElem[1]->c_str());
 
   // Parse typeuse
-  FunctionType* functionType = nullptr;
-  Type fakeResult; // just co call parseTypeUse
-  i = parseTypeUse(s, i, functionType, event->params, fakeResult);
-  assert(functionType && "functionType should've been set by parseTypeUse");
-  event->type = functionType->name;
+  std::vector<Type> paramTypes;
+  Type results;
+  FunctionType* fakeFunctionType; // just co call parseTypeUse
+  i = parseTypeUse(s, i, fakeFunctionType, paramTypes, results);
+  event->sig = Signature(Type(paramTypes), results);
 
   // If there are more elements, they are invalid
   if (i < s.size()) {
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index c1d4f1222..f1aaff93e 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -68,7 +68,9 @@ void BinaryInstWriter::visitCall(Call* curr) {
 void BinaryInstWriter::visitCallIndirect(CallIndirect* curr) {
   int8_t op =
     curr->isReturn ? BinaryConsts::RetCallIndirect : BinaryConsts::CallIndirect;
-  o << op << U32LEB(parent.getFunctionTypeIndex(curr->fullType))
+  auto* type = parent.getModule()->getFunctionType(curr->fullType);
+  Signature sig(Type(type->params), type->result);
+  o << op << U32LEB(parent.getTypeIndex(sig))
     << U32LEB(0); // Reserved flags field
 }
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 9d0f9b108..e114a5540 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -19,22 +19,28 @@
 #include <sstream>
 #include <unordered_map>
 
-#include "wasm-type.h"
-#include "wasm-features.h"
-
 #include "compiler-support.h"
+#include "support/hash.h"
+#include "wasm-features.h"
+#include "wasm-type.h"
 
 template<> class std::hash<std::vector<wasm::Type>> {
 public:
   size_t operator()(const std::vector<wasm::Type>& types) const {
-    size_t res = 0;
+    uint32_t res = wasm::rehash(0, uint32_t(types.size()));
     for (auto vt : types) {
-      res ^= std::hash<uint32_t>{}(vt);
+      res = wasm::rehash(res, uint32_t(vt));
     }
     return res;
   }
 };
 
+size_t std::hash<wasm::Signature>::
+operator()(const wasm::Signature& sig) const {
+  return std::hash<uint64_t>{}(uint64_t(sig.params) << 32 |
+                               uint64_t(sig.results));
+}
+
 namespace wasm {
 
 namespace {
@@ -123,6 +129,27 @@ const std::vector<Type>& Type::expand() const {
   return *typeLists[id].get();
 }
 
+bool Type::operator<(const Type& other) const {
+  const std::vector<Type>& these = expand();
+  const std::vector<Type>& others = other.expand();
+  return std::lexicographical_compare(
+    these.begin(),
+    these.end(),
+    others.begin(),
+    others.end(),
+    [](const Type& a, const Type& b) { return uint32_t(a) < uint32_t(b); });
+}
+
+bool Signature::operator<(const Signature& other) const {
+  if (results < other.results) {
+    return true;
+  } else if (other.results < results) {
+    return false;
+  } else {
+    return params < other.params;
+  }
+}
+
 namespace {
 
 std::ostream&
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 05cb45d25..d3f03b76c 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -1703,14 +1703,15 @@ void FunctionValidator::visitThrow(Throw* curr) {
   if (!shouldBeTrue(!!event, curr, "throw's event must exist")) {
     return;
   }
-  if (!shouldBeTrue(curr->operands.size() == event->params.size(),
+  if (!shouldBeTrue(curr->operands.size() == event->sig.params.size(),
                     curr,
                     "event's param numbers must match")) {
     return;
   }
+  const std::vector<Type>& paramTypes = event->sig.params.expand();
   for (size_t i = 0; i < curr->operands.size(); i++) {
     if (!shouldBeEqualOrFirstIsUnreachable(curr->operands[i]->type,
-                                           event->params[i],
+                                           paramTypes[i],
                                            curr->operands[i],
                                            "event param types must match") &&
         !info.quiet) {
@@ -1731,10 +1732,10 @@ void FunctionValidator::visitRethrow(Rethrow* curr) {
 void FunctionValidator::visitBrOnExn(BrOnExn* curr) {
   Event* event = getModule()->getEventOrNull(curr->event);
   shouldBeTrue(event != nullptr, curr, "br_on_exn's event must exist");
-  shouldBeTrue(event->params == curr->eventParams,
+  shouldBeTrue(event->sig.params == curr->sent,
                curr,
                "br_on_exn's event params and event's params are different");
-  noteBreak(curr->name, curr->getSingleSentType(), curr);
+  noteBreak(curr->name, curr->sent, curr);
   shouldBeTrue(curr->exnref->type == unreachable ||
                  curr->exnref->type == exnref,
                curr,
@@ -2110,23 +2111,19 @@ static void validateEvents(Module& module, ValidationInfo& info) {
                       "Module has events (event-handling is disabled)");
   }
   for (auto& curr : module.events) {
-    info.shouldBeTrue(
-      curr->type.is(), curr->name, "Event should have a valid type");
-    FunctionType* ft = module.getFunctionType(curr->type);
-    info.shouldBeEqual(
-      ft->result, none, curr->name, "Event type's result type should be none");
     info.shouldBeEqual(curr->attribute,
                        (unsigned)0,
                        curr->attribute,
                        "Currently only attribute 0 is supported");
-    for (auto type : curr->params) {
+    info.shouldBeEqual(curr->sig.results,
+                       Type(Type::none),
+                       curr->name,
+                       "Event type's result type should be none");
+    for (auto type : curr->sig.params.expand()) {
       info.shouldBeTrue(type.isInteger() || type.isFloat(),
                         curr->name,
                         "Values in an event should have integer or float type");
     }
-    info.shouldBeTrue(curr->params == ft->params,
-                      curr->name,
-                      "Event's function type and internal type should match");
   }
 }
 
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index b137044b2..b71f7d854 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -219,7 +219,7 @@ struct TypeSeeker : public PostWalker<TypeSeeker> {
 
   void visitBrOnExn(BrOnExn* curr) {
     if (curr->name == targetName) {
-      types.push_back(curr->getSingleSentType());
+      types.push_back(curr->sent);
     }
   }
 
@@ -924,16 +924,6 @@ void BrOnExn::finalize() {
   }
 }
 
-// br_on_exn's type is exnref, which it pushes onto the stack when it is not
-// taken, but the type of the value it pushes onto the stack when it is taken
-// should be the event type. So this is the type we 'send' to the block end when
-// it is taken. Currently we don't support multi value return from a block, we
-// pick the type of the first param from the event.
-// TODO Remove this function and generalize event type after multi-value support
-Type BrOnExn::getSingleSentType() {
-  return eventParams.empty() ? none : eventParams.front();
-}
-
 void Push::finalize() {
   if (value->type == unreachable) {
     type = unreachable;