Remove Type ordering (#3793)

As found in #3682, the current implementation of type ordering is not correct,
and although the immediate issue would be easy to fix, I don't think the current
intended comparison algorithm is correct in the first place. Rather than try to
switch to using a correct algorithm (which I am not sure I know how to
implement, although I have an idea) this PR removes Type ordering entirely. In
places that used Type ordering with std::set or std::map because they require
deterministic iteration order, this PR uses InsertOrdered{Set,Map} instead.

12 files changed, 76 insertions, 238 deletions

diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index ef6bc2bf6..486838aea 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -22,6 +22,7 @@
 #include "ir/manipulation.h"
 #include "ir/properties.h"
 #include "pass.h"
+#include "support/insert_ordered.h"
 #include "support/unique_deferring_queue.h"
 #include "wasm.h"
 
@@ -306,10 +307,12 @@ template<typename T> inline void iterImports(Module& wasm, T visitor) {
 // some computation that the operation performs.
 // The operation performend should not modify the wasm module in any way.
 // TODO: enforce this
-template<typename T> struct ParallelFunctionAnalysis {
+template<typename K, typename V> using DefaultMap = std::map<K, V>;
+template<typename T, template<typename, typename> class MapT = DefaultMap>
+struct ParallelFunctionAnalysis {
   Module& wasm;
 
-  typedef std::map<Function*, T> Map;
+  typedef MapT<Function*, T> Map;
   Map map;
 
   typedef std::function<void(Function*, T&)> Func;
@@ -467,7 +470,7 @@ template<typename T> struct CallGraphPropertyAnalysis {
 inline void collectHeapTypes(Module& wasm,
                              std::vector<HeapType>& types,
                              std::unordered_map<HeapType, Index>& typeIndices) {
-  struct Counts : public std::unordered_map<HeapType, size_t> {
+  struct Counts : public InsertOrderedMap<HeapType, size_t> {
     void note(HeapType type) {
       if (!type.isBasic()) {
         (*this)[type]++;
@@ -522,7 +525,7 @@ inline void collectHeapTypes(Module& wasm,
   }
 
   // Collect info from functions in parallel.
-  ModuleUtils::ParallelFunctionAnalysis<Counts> analysis(
+  ModuleUtils::ParallelFunctionAnalysis<Counts, InsertOrderedMap> analysis(
     wasm, [&](Function* func, Counts& counts) {
       counts.note(func->sig);
       for (auto type : func->vars) {
@@ -534,9 +537,9 @@ inline void collectHeapTypes(Module& wasm,
     });
 
   // Combine the function info with the module info.
-  for (auto& pair : analysis.map) {
-    Counts& functionCounts = pair.second;
-    for (auto& innerPair : functionCounts) {
+  for (const auto& pair : analysis.map) {
+    const Counts& functionCounts = pair.second;
+    for (const auto& innerPair : functionCounts) {
       counts[innerPair.first] += innerPair.second;
     }
   }
@@ -547,7 +550,7 @@ inline void collectHeapTypes(Module& wasm,
   // As we do this we may find more and more types, as nested children of
   // previous ones. Each such type will appear in the type section once, so
   // we just need to visit it once.
-  std::unordered_set<HeapType> newTypes;
+  InsertOrderedSet<HeapType> newTypes;
   for (auto& pair : counts) {
     newTypes.insert(pair.first);
   }
@@ -565,13 +568,10 @@ inline void collectHeapTypes(Module& wasm,
     }
   }
 
-  // Sort by frequency and then simplicity.
+  // Sort by frequency and then original insertion order.
   std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), counts.end());
   std::stable_sort(sorted.begin(), sorted.end(), [&](auto a, auto b) {
-    if (a.second != b.second) {
-      return a.second > b.second;
-    }
-    return a.first < b.first;
+    return a.second > b.second;
   });
   for (Index i = 0; i < sorted.size(); ++i) {
     typeIndices[sorted[i].first] = i;
diff --git a/src/literal.h b/src/literal.h
index a07e2597c..14281d66f 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -759,39 +759,7 @@ template<> struct hash<wasm::Literals> {
     return digest;
   }
 };
-template<> struct less<wasm::Literal> {
-  bool operator()(const wasm::Literal& a, const wasm::Literal& b) const {
-    if (a.type < b.type) {
-      return true;
-    }
-    if (b.type < a.type) {
-      return false;
-    }
-    TODO_SINGLE_COMPOUND(a.type);
-    switch (a.type.getBasic()) {
-      case wasm::Type::i32:
-        return a.geti32() < b.geti32();
-      case wasm::Type::f32:
-        return a.reinterpreti32() < b.reinterpreti32();
-      case wasm::Type::i64:
-        return a.geti64() < b.geti64();
-      case wasm::Type::f64:
-        return a.reinterpreti64() < b.reinterpreti64();
-      case wasm::Type::v128:
-        return memcmp(a.getv128Ptr(), b.getv128Ptr(), 16) < 0;
-      case wasm::Type::funcref:
-      case wasm::Type::externref:
-      case wasm::Type::anyref:
-      case wasm::Type::eqref:
-      case wasm::Type::i31ref:
-      case wasm::Type::dataref:
-      case wasm::Type::none:
-      case wasm::Type::unreachable:
-        return false;
-    }
-    WASM_UNREACHABLE("unexpected type");
-  }
-};
+
 } // namespace std
 
 #endif // wasm_literal_h
diff --git a/src/passes/Asyncify.cpp b/src/passes/Asyncify.cpp
index 1abfa9628..7ad3fab5d 100644
--- a/src/passes/Asyncify.cpp
+++ b/src/passes/Asyncify.cpp
@@ -380,8 +380,8 @@ public:
   }
 
 private:
-  std::map<Type, Name> map;
-  std::map<Name, Type> rev;
+  std::unordered_map<Type, Name> map;
+  std::unordered_map<Name, Type> rev;
 
   // Collect the types returned from all calls for which call support globals
   // may need to be generated.
@@ -1237,7 +1237,7 @@ private:
   std::unique_ptr<AsyncifyBuilder> builder;
 
   Index rewindIndex;
-  std::map<Type, Index> fakeCallLocals;
+  std::unordered_map<Type, Index> fakeCallLocals;
   std::set<Index> relevantLiveLocals;
 
   void findRelevantLiveLocals(Function* func) {
diff --git a/src/passes/ConstHoisting.cpp b/src/passes/ConstHoisting.cpp
index 8349e7234..1caf0eb28 100644
--- a/src/passes/ConstHoisting.cpp
+++ b/src/passes/ConstHoisting.cpp
@@ -30,12 +30,11 @@
 //       <= 1 byte to declare the local and 2-3 to use it!
 //
 
-#include <map>
-
-#include <pass.h>
-#include <wasm-binary.h>
-#include <wasm-builder.h>
-#include <wasm.h>
+#include "pass.h"
+#include "support/insert_ordered.h"
+#include "wasm-binary.h"
+#include "wasm-builder.h"
+#include "wasm.h"
 
 namespace wasm {
 
@@ -47,7 +46,7 @@ struct ConstHoisting : public WalkerPass<PostWalker<ConstHoisting>> {
 
   Pass* create() override { return new ConstHoisting; }
 
-  std::map<Literal, std::vector<Expression**>> uses;
+  InsertOrderedMap<Literal, std::vector<Expression**>> uses;
 
   void visitConst(Const* curr) {
     uses[curr->value].push_back(getCurrentPointer());
diff --git a/src/passes/GenerateDynCalls.cpp b/src/passes/GenerateDynCalls.cpp
index 8ed9ce8b4..0f4934c06 100644
--- a/src/passes/GenerateDynCalls.cpp
+++ b/src/passes/GenerateDynCalls.cpp
@@ -28,6 +28,7 @@
 #include "ir/import-utils.h"
 #include "pass.h"
 #include "support/debug.h"
+#include "support/insert_ordered.h"
 #include "wasm-builder.h"
 
 #define DEBUG_TYPE "generate-dyncalls"
@@ -81,7 +82,7 @@ struct GenerateDynCalls : public WalkerPass<PostWalker<GenerateDynCalls>> {
 
   bool onlyI64;
   // The set of all invokes' signatures
-  std::set<Signature> invokeSigs;
+  InsertOrderedSet<Signature> invokeSigs;
 };
 
 static bool hasI64(Signature sig) {
diff --git a/src/passes/RemoveNonJSOps.cpp b/src/passes/RemoveNonJSOps.cpp
index 08e6e6482..7c0a0e2ce 100644
--- a/src/passes/RemoveNonJSOps.cpp
+++ b/src/passes/RemoveNonJSOps.cpp
@@ -43,6 +43,7 @@
 #include "ir/memory-utils.h"
 #include "ir/module-utils.h"
 #include "passes/intrinsics-module.h"
+#include "support/insert_ordered.h"
 #include "wasm-builder.h"
 #include "wasm-s-parser.h"
 
@@ -51,7 +52,7 @@ namespace wasm {
 struct RemoveNonJSOpsPass : public WalkerPass<PostWalker<RemoveNonJSOpsPass>> {
   std::unique_ptr<Builder> builder;
   std::unordered_set<Name> neededIntrinsics;
-  std::set<std::pair<Name, Type>> neededImportedGlobals;
+  InsertOrderedSet<std::pair<Name, Type>> neededImportedGlobals;
 
   bool isFunctionParallel() override { return false; }
 
diff --git a/src/support/insert_ordered.h b/src/support/insert_ordered.h
index 5e3dec96b..d4905b945 100644
--- a/src/support/insert_ordered.h
+++ b/src/support/insert_ordered.h
@@ -83,24 +83,43 @@ template<typename T> struct InsertOrderedSet {
 // order that elements were added to the map (not in the order
 // of operator<(Key, Key))
 template<typename Key, typename T> struct InsertOrderedMap {
-  std::unordered_map<Key, typename std::list<std::pair<Key, T>>::iterator> Map;
-  std::list<std::pair<Key, T>> List;
+  std::unordered_map<Key, typename std::list<std::pair<const Key, T>>::iterator>
+    Map;
+  std::list<std::pair<const Key, T>> List;
+
+  typedef typename std::list<std::pair<const Key, T>>::iterator iterator;
+  iterator begin() { return List.begin(); }
+  iterator end() { return List.end(); }
+
+  typedef
+    typename std::list<std::pair<const Key, T>>::const_iterator const_iterator;
+  const_iterator begin() const { return List.begin(); }
+  const_iterator end() const { return List.end(); }
+
+  std::pair<iterator, bool> insert(std::pair<const Key, T>& kv) {
+    // Try inserting with a placeholder list iterator.
+    auto inserted = Map.insert({kv.first, List.end()});
+    if (inserted.second) {
+      // This is a new item; insert it in the list and update the iterator.
+      List.push_back(kv);
+      inserted.first->second = std::prev(List.end());
+    }
+    return {inserted.first->second, inserted.second};
+  }
 
   T& operator[](const Key& k) {
+    std::pair<const Key, T> kv = {k, {}};
+    return insert(kv).first->second;
+  }
+
+  iterator find(const Key& k) {
     auto it = Map.find(k);
     if (it == Map.end()) {
-      List.push_back(std::make_pair(k, T()));
-      auto e = --List.end();
-      Map.insert(std::make_pair(k, e));
-      return e->second;
+      return end();
     }
-    return it->second->second;
+    return it->second;
   }
 
-  typedef typename std::list<std::pair<Key, T>>::iterator iterator;
-  iterator begin() { return List.begin(); }
-  iterator end() { return List.end(); }
-
   void erase(const Key& k) {
     auto it = Map.find(k);
     if (it != Map.end()) {
@@ -126,14 +145,19 @@ template<typename Key, typename T> struct InsertOrderedMap {
   size_t count(const Key& k) const { return Map.count(k); }
 
   InsertOrderedMap() = default;
-  InsertOrderedMap(InsertOrderedMap& other) {
-    // TODO, watch out for iterators.
-    WASM_UNREACHABLE("unimp");
+  InsertOrderedMap(const InsertOrderedMap& other) {
+    for (auto kv : other) {
+      insert(kv);
+    }
   }
   InsertOrderedMap& operator=(const InsertOrderedMap& other) {
-    // TODO, watch out for iterators.
-    WASM_UNREACHABLE("unimp");
+    if (this != &other) {
+      this->~InsertOrderedMap();
+      new (this) InsertOrderedMap<Key, T>(other);
+    }
+    return *this;
   }
+
   bool operator==(const InsertOrderedMap& other) {
     return Map == other.Map && List == other.List;
   }
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index 8dd083391..0635dc61d 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -29,6 +29,7 @@ high chance for set at start of loop
 
 #include "ir/branch-utils.h"
 #include "ir/memory-utils.h"
+#include "support/insert_ordered.h"
 #include <ir/find_all.h>
 #include <ir/literal-utils.h>
 #include <ir/manipulation.h>
@@ -459,7 +460,7 @@ private:
     }
   }
 
-  std::map<Type, std::vector<Name>> globalsByType;
+  std::unordered_map<Type, std::vector<Name>> globalsByType;
 
   void setupGlobals() {
     // If there were initial wasm contents, there may be imported globals. That
@@ -650,7 +651,7 @@ private:
     std::vector<Expression*> hangStack;
 
     // type => list of locals with that type
-    std::map<Type, std::vector<Index>> typeLocals;
+    std::unordered_map<Type, std::vector<Index>> typeLocals;
 
     FunctionCreationContext(TranslateToFuzzReader& parent, Function* func)
       : parent(parent), func(func) {
@@ -782,7 +783,7 @@ private:
     struct Scanner
       : public PostWalker<Scanner, UnifiedExpressionVisitor<Scanner>> {
       // A map of all expressions, categorized by type.
-      std::map<Type, std::vector<Expression*>> exprsByType;
+      InsertOrderedMap<Type, std::vector<Expression*>> exprsByType;
 
       void visitExpression(Expression* curr) {
         exprsByType[curr->type].push_back(curr);
diff --git a/src/wasm-stack.h b/src/wasm-stack.h
index 38b64dff4..f114bf43e 100644
--- a/src/wasm-stack.h
+++ b/src/wasm-stack.h
@@ -20,6 +20,7 @@
 #include "ir/branch-utils.h"
 #include "ir/properties.h"
 #include "pass.h"
+#include "support/insert_ordered.h"
 #include "wasm-binary.h"
 #include "wasm-traversal.h"
 #include "wasm.h"
@@ -141,7 +142,7 @@ private:
 
   // Keeps track of the binary index of the scratch locals used to lower
   // tuple.extract.
-  std::map<Type, Index> scratchLocals;
+  InsertOrderedMap<Type, Index> scratchLocals;
   void countScratchLocals();
   void setScratchLocals();
 };
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 41a89d4fe..03e8c129f 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -173,9 +173,6 @@ public:
   bool operator!=(const Type& other) const { return id != other.id; }
   bool operator!=(const BasicType& other) const { return id != other; }
 
-  // Order types by some notion of simplicity.
-  bool operator<(const Type& other) const;
-
   // Returns the type size in bytes. Only single types are supported.
   unsigned getByteSize() const;
 
@@ -362,9 +359,6 @@ public:
   bool operator!=(const HeapType& other) const { return id != other.id; }
   bool operator!=(const BasicHeapType& other) const { return id != other; }
 
-  // Order heap types by some notion of simplicity.
-  bool operator<(const HeapType& other) const;
-
   // Returns true if left is a subtype of right. Subtype includes itself.
   static bool isSubType(HeapType left, HeapType right);
 
@@ -414,7 +408,6 @@ struct Signature {
     return params == other.params && results == other.results;
   }
   bool operator!=(const Signature& other) const { return !(*this == other); }
-  bool operator<(const Signature& other) const;
   std::string toString() const;
 };
 
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 9006eb9f8..d222d3a1a 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -128,24 +128,6 @@ struct HeapTypeInfo {
   bool operator!=(const HeapTypeInfo& other) const { return !(*this == other); }
 };
 
-// Helper for coinductively comparing Types and HeapTypes according to some
-// arbitrary notion of complexity.
-struct TypeComparator {
-  // Set of HeapTypes we are assuming are equivalent as long as we cannot prove
-  // otherwise.
-  std::unordered_set<std::pair<HeapType, HeapType>> seen;
-  bool lessThan(Type a, Type b);
-  bool lessThan(HeapType a, HeapType b);
-  bool lessThan(const TypeInfo& a, const TypeInfo& b);
-  bool lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b);
-  bool lessThan(const Tuple& a, const Tuple& b);
-  bool lessThan(const Field& a, const Field& b);
-  bool lessThan(const Signature& a, const Signature& b);
-  bool lessThan(const Struct& a, const Struct& b);
-  bool lessThan(const Array& a, const Array& b);
-  bool lessThan(const Rtt& a, const Rtt& b);
-};
-
 // Helper for coinductively checking whether a pair of Types or HeapTypes are in
 // a subtype relation.
 struct SubTyper {
@@ -833,10 +815,6 @@ Nullability Type::getNullability() const {
   return isNullable() ? Nullable : NonNullable;
 }
 
-bool Type::operator<(const Type& other) const {
-  return TypeComparator().lessThan(*this, other);
-}
-
 unsigned Type::getByteSize() const {
   // TODO: alignment?
   auto getSingleByteSize = [](Type t) {
@@ -1116,10 +1094,6 @@ bool HeapType::isArray() const {
   }
 }
 
-bool HeapType::operator<(const HeapType& other) const {
-  return TypeComparator().lessThan(*this, other);
-}
-
 Signature HeapType::getSignature() const {
   assert(isSignature());
   return getHeapTypeInfo(*this)->signature;
@@ -1145,10 +1119,6 @@ std::vector<HeapType> HeapType::getHeapTypeChildren() {
   return collector.children;
 }
 
-bool Signature::operator<(const Signature& other) const {
-  return TypeComparator().lessThan(*this, other);
-}
-
 template<typename T> static std::string genericToString(const T& t) {
   std::ostringstream ss;
   ss << t;
@@ -1203,127 +1173,6 @@ unsigned Field::getByteSize() const {
 
 namespace {
 
-bool TypeComparator::lessThan(Type a, Type b) {
-  if (a == b) {
-    return false;
-  }
-  if (a.isBasic() && b.isBasic()) {
-    return a.getBasic() < b.getBasic();
-  }
-  if (a.isBasic()) {
-    return true;
-  }
-  if (b.isBasic()) {
-    return false;
-  }
-  return lessThan(*getTypeInfo(a), *getTypeInfo(b));
-}
-
-bool TypeComparator::lessThan(HeapType a, HeapType b) {
-  if (a == b) {
-    return false;
-  }
-  if (seen.count({a, b})) {
-    // We weren't able to disprove that a == b since we last saw them, so it
-    // holds coinductively that a < b is false.
-    return false;
-  }
-  if (a.isBasic() && b.isBasic()) {
-    return a.getBasic() < b.getBasic();
-  }
-  if (a.isBasic()) {
-    return true;
-  }
-  if (b.isBasic()) {
-    return false;
-  }
-  // As we recurse, we will coinductively assume that a == b unless proven
-  // otherwise.
-  seen.insert({a, b});
-  return lessThan(*getHeapTypeInfo(a), *getHeapTypeInfo(b));
-}
-
-bool TypeComparator::lessThan(const TypeInfo& a, const TypeInfo& b) {
-  if (a.kind != b.kind) {
-    return a.kind < b.kind;
-  }
-  switch (a.kind) {
-    case TypeInfo::TupleKind:
-      return lessThan(a.tuple, b.tuple);
-    case TypeInfo::RefKind:
-      if (a.ref.nullable != b.ref.nullable) {
-        return a.ref.nullable < b.ref.nullable;
-      }
-      return lessThan(a.ref.heapType, b.ref.heapType);
-    case TypeInfo::RttKind:
-      return lessThan(a.rtt, b.rtt);
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
-bool TypeComparator::lessThan(const HeapTypeInfo& a, const HeapTypeInfo& b) {
-  if (a.kind != b.kind) {
-    return a.kind < b.kind;
-  }
-  switch (a.kind) {
-    case HeapTypeInfo::BasicKind:
-      return a.basic < b.basic;
-    case HeapTypeInfo::SignatureKind:
-      return lessThan(a.signature, b.signature);
-    case HeapTypeInfo::StructKind:
-      return lessThan(a.struct_, b.struct_);
-    case HeapTypeInfo::ArrayKind:
-      return lessThan(a.array, b.array);
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
-bool TypeComparator::lessThan(const Tuple& a, const Tuple& b) {
-  return std::lexicographical_compare(
-    a.types.begin(),
-    a.types.end(),
-    b.types.begin(),
-    b.types.end(),
-    [&](Type ta, Type tb) { return lessThan(ta, tb); });
-}
-
-bool TypeComparator::lessThan(const Field& a, const Field& b) {
-  if (a.mutable_ != b.mutable_) {
-    return a.mutable_ < b.mutable_;
-  }
-  if (a.type == Type::i32 && b.type == Type::i32) {
-    return a.packedType < b.packedType;
-  }
-  return lessThan(a.type, b.type);
-}
-
-bool TypeComparator::lessThan(const Signature& a, const Signature& b) {
-  if (a.results != b.results) {
-    return lessThan(a.results, b.results);
-  }
-  return lessThan(a.params, b.params);
-}
-
-bool TypeComparator::lessThan(const Struct& a, const Struct& b) {
-  return std::lexicographical_compare(
-    a.fields.begin(),
-    a.fields.end(),
-    b.fields.begin(),
-    b.fields.end(),
-    [&](const Field& fa, const Field& fb) { return lessThan(fa, fb); });
-}
-
-bool TypeComparator::lessThan(const Array& a, const Array& b) {
-  return lessThan(a.element, b.element);
-}
-
-bool TypeComparator::lessThan(const Rtt& a, const Rtt& b) {
-  if (a.depth != b.depth) {
-    return a.depth < b.depth;
-  }
-  return lessThan(a.heapType, b.heapType);
-}
-
 bool SubTyper::isSubType(Type a, Type b) {
   if (a == b) {
     return true;
@@ -1546,7 +1395,8 @@ HeapType TypeBounder::lub(HeapType a, HeapType b) {
   // Allocate a new slot to construct the LUB of this pair if we have not
   // already seen it before. Canonicalize the pair to have the element with the
   // smaller ID first since order does not matter.
-  auto pair = std::make_pair(std::min(a, b), std::max(a, b));
+  auto pair =
+    a.getID() < b.getID() ? std::make_pair(a, b) : std::make_pair(b, a);
   size_t index = builder.size();
   auto result = indices.insert({pair, index});
   if (!result.second) {
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 3079ad0bb..d82542668 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -224,7 +224,7 @@ struct FunctionValidator : public WalkerPass<PostWalker<FunctionValidator>> {
   std::unordered_set<Name> delegateTargetNames;
   std::unordered_set<Name> rethrowTargetNames;
 
-  std::set<Type> returnTypes; // types used in returns
+  std::unordered_set<Type> returnTypes; // types used in returns
 
   // Binaryen IR requires that label names must be unique - IR generators must
   // ensure that