10 files changed, 106 insertions, 279 deletions

diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index a0166381b..947f9d975 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -44,16 +44,18 @@ void ReFinalize::visitBlock(Block* curr) {
     curr->type = Type::none;
     return;
   }
-  // Get the least upper bound type of the last element and all branch return
-  // values
-  curr->type = curr->list.back()->type;
   if (curr->name.is()) {
-    auto iter = breakValues.find(curr->name);
-    if (iter != breakValues.end()) {
-      curr->type = Type::getLeastUpperBound(curr->type, iter->second);
+    auto iter = breakTypes.find(curr->name);
+    if (iter != breakTypes.end()) {
+      // Set the type to be a supertype of the branch types and the flowed-out
+      // type. TODO: calculate proper LUBs to compute a new correct type in this
+      // situation.
+      iter->second.insert(curr->list.back()->type);
+      Type::ensureSuperType(iter->second, curr->type);
       return;
     }
   }
+  curr->type = curr->list.back()->type;
   if (curr->type == Type::unreachable) {
     return;
   }
@@ -187,11 +189,7 @@ void ReFinalize::visitModule(Module* curr) { WASM_UNREACHABLE("unimp"); }
 
 void ReFinalize::updateBreakValueType(Name name, Type type) {
   if (type != Type::unreachable) {
-    if (breakValues.count(name) == 0) {
-      breakValues[name] = type;
-    } else {
-      breakValues[name] = Type::getLeastUpperBound(breakValues[name], type);
-    }
+    breakTypes[name].insert(type);
   }
 }
 
diff --git a/src/ir/branch-utils.h b/src/ir/branch-utils.h
index f6c55c563..414ee0e16 100644
--- a/src/ir/branch-utils.h
+++ b/src/ir/branch-utils.h
@@ -225,20 +225,14 @@ struct BranchSeeker
   Name target;
 
   Index found = 0;
-  // None indicates no value is sent.
-  Type valueType = Type::none;
+
+  std::unordered_set<Type> types;
 
   BranchSeeker(Name target) : target(target) {}
 
   void noteFound(Type newType) {
     found++;
-    if (newType != Type::none) {
-      if (found == 1) {
-        valueType = newType;
-      } else {
-        valueType = Type::getLeastUpperBound(valueType, newType);
-      }
-    }
+    types.insert(newType);
   }
 
   void visitExpression(Expression* curr) {
diff --git a/src/ir/stack-utils.cpp b/src/ir/stack-utils.cpp
index bc20dfe91..aa6da22d9 100644
--- a/src/ir/stack-utils.cpp
+++ b/src/ir/stack-utils.cpp
@@ -164,95 +164,6 @@ bool StackSignature::isSubType(StackSignature a, StackSignature b) {
                     });
 }
 
-bool StackSignature::haveLeastUpperBound(StackSignature a, StackSignature b) {
-  // If a signature is polymorphic, the LUB could extend its params and results
-  // arbitrarily. Otherwise, the LUB must extend its params and results
-  // uniformly so that each additional param is a subtype of the corresponding
-  // additional result.
-  auto extensionCompatible = [](auto self, auto other) -> bool {
-    if (self.kind == Polymorphic) {
-      return true;
-    }
-    // If no extension, then no problem.
-    if (self.params.size() >= other.params.size() &&
-        self.results.size() >= other.results.size()) {
-      return true;
-    }
-    auto extSize = other.params.size() - self.params.size();
-    if (extSize != other.results.size() - self.results.size()) {
-      return false;
-    }
-    return std::equal(other.params.begin(),
-                      other.params.begin() + extSize,
-                      other.results.begin(),
-                      other.results.begin() + extSize,
-                      [](const Type& param, const Type& result) {
-                        return Type::isSubType(param, result);
-                      });
-  };
-  if (!extensionCompatible(a, b) || !extensionCompatible(b, a)) {
-    return false;
-  }
-
-  auto valsCompatible = [](auto as, auto bs, auto compatible) -> bool {
-    // Canonicalize so the as are shorter and any unshared prefix is on bs.
-    if (bs.size() < as.size()) {
-      std::swap(as, bs);
-    }
-    // Check that shared values after the unshared prefix have are compatible.
-    size_t diff = bs.size() - as.size();
-    for (size_t i = 0, shared = as.size(); i < shared; ++i) {
-      if (!compatible(as[i], bs[i + diff])) {
-        return false;
-      }
-    }
-    return true;
-  };
-
-  bool paramsOk = valsCompatible(a.params, b.params, [](Type a, Type b) {
-    assert(a == b && "TODO: calculate greatest lower bound to handle "
-                     "contravariance correctly");
-    return true;
-  });
-  bool resultsOk = valsCompatible(a.results, b.results, [](Type a, Type b) {
-    return Type::getLeastUpperBound(a, b) != Type::none;
-  });
-  return paramsOk && resultsOk;
-}
-
-StackSignature StackSignature::getLeastUpperBound(StackSignature a,
-                                                  StackSignature b) {
-  assert(haveLeastUpperBound(a, b));
-
-  auto combineVals = [](auto as, auto bs, auto combine) -> std::vector<Type> {
-    // Canonicalize so the as are shorter and any unshared prefix is on bs.
-    if (bs.size() < as.size()) {
-      std::swap(as, bs);
-    }
-    // Combine shared values after the unshared prefix.
-    size_t diff = bs.size() - as.size();
-    std::vector<Type> vals(bs.begin(), bs.begin() + diff);
-    for (size_t i = 0, shared = as.size(); i < shared; ++i) {
-      vals.push_back(combine(as[i], bs[i + diff]));
-    }
-    return vals;
-  };
-
-  auto params = combineVals(a.params, b.params, [&](Type a, Type b) {
-    assert(a == b && "TODO: calculate greatest lower bound to handle "
-                     "contravariance correctly");
-    return a;
-  });
-
-  auto results = combineVals(a.results, b.results, [&](Type a, Type b) {
-    return Type::getLeastUpperBound(a, b);
-  });
-
-  Kind kind =
-    a.kind == Polymorphic && b.kind == Polymorphic ? Polymorphic : Fixed;
-  return StackSignature{Type(params), Type(results), kind};
-}
-
 StackFlow::StackFlow(Block* block) {
   // Encapsulates the logic for treating the block and its children
   // uniformly. The end of the block is treated as if it consumed values
diff --git a/src/ir/stack-utils.h b/src/ir/stack-utils.h
index aad13f7f0..0c05381db 100644
--- a/src/ir/stack-utils.h
+++ b/src/ir/stack-utils.h
@@ -166,13 +166,6 @@ struct StackSignature {
   // other stack signature. This corresponds to the `unreachable` instruction
   // being able to be given any stack signature.
   static bool isSubType(StackSignature a, StackSignature b);
-
-  // Returns true iff `a` and `b` have a LUB, i.e. a minimal StackSignature that
-  // could type block contents of either type `a` or type `b`.
-  static bool haveLeastUpperBound(StackSignature a, StackSignature b);
-
-  // Returns the LUB of `a` and `b`. Assumes that the LUB exists.
-  static StackSignature getLeastUpperBound(StackSignature a, StackSignature b);
 };
 
 // Calculates stack machine data flow, associating the sources and destinations
diff --git a/src/ir/utils.h b/src/ir/utils.h
index f06a68fff..fa3e34423 100644
--- a/src/ir/utils.h
+++ b/src/ir/utils.h
@@ -109,7 +109,9 @@ struct ReFinalize
   // block finalization is O(bad) if we do each block by itself, so do it in
   // bulk, tracking break value types so we just do a linear pass
 
-  std::map<Name, Type> breakValues;
+  // TODO: Switch to std::unordered_set once types are properly canonicalized so
+  // determinism isn't an issue.
+  std::unordered_map<Name, std::set<Type>> breakTypes;
 
 #define DELEGATE(CLASS_TO_VISIT)                                               \
   void visit##CLASS_TO_VISIT(CLASS_TO_VISIT* curr);
diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp
index ca777431a..c9b83da78 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -291,7 +291,9 @@ struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
             BranchUtils::BranchSeeker seeker(block->name);
             Expression* temp = block;
             seeker.walk(temp);
-            if (seeker.found && seeker.valueType != Type::none) {
+            Type supertype;
+            if (seeker.found && Type::getSuperType(seeker.types, supertype) &&
+                supertype != Type::none) {
               canPop = false;
             }
           }
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 8c1d72085..7f037d5e7 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -19,6 +19,7 @@
 
 #include "support/name.h"
 #include "wasm-features.h"
+#include <algorithm>
 #include <ostream>
 #include <vector>
 
@@ -202,18 +203,42 @@ public:
   // Returns true if left is a subtype of right. Subtype includes itself.
   static bool isSubType(Type left, Type right);
 
-  // Computes the least upper bound from the type lattice.
-  // If one of the type is unreachable, the other type becomes the result. If
-  // the common supertype does not exist, returns none, a poison value.
-  static Type getLeastUpperBound(Type a, Type b);
+  // Returns true and sets `super` to the type in range [begin,end) that is a
+  // supertype of all types in the range iff such a type exists. This is similar
+  // to but more limited than calculating a proper least upper bound on the
+  // types.
+  template<typename T> static bool getSuperType(const T& types, Type& super) {
+    // Sort the types so that the supertype will be at the back.
+    std::vector<Type> sorted(types.begin(), types.end());
+    std::stable_sort(
+      sorted.begin(), sorted.end(), [&](const Type& a, const Type& b) {
+        return Type::isSubType(a, b);
+      });
+    // Check that the "highest" type found by the sort is actually a supertype
+    // of all the other sorted.
+    for (auto t : sorted) {
+      if (!Type::isSubType(t, sorted.back())) {
+        return false;
+      }
+    }
+    super = sorted.back();
+    return true;
+  }
 
-  // Computes the least upper bound for all types in the given list.
-  template<typename T> static Type mergeTypes(const T& types) {
-    Type type = Type::unreachable;
-    for (auto other : types) {
-      type = Type::getLeastUpperBound(type, other);
+  // Ensure that `type` is a supertype of `types`. If it is not already a
+  // supertype, then use `getSuperType` on `types` to set `type` to a supertype.
+  // Assumes `getSuperType` will be able to find an appropriate type in that
+  // case.
+  template<typename T>
+  static void ensureSuperType(const T& types, Type& super) {
+    if (std::all_of(types.begin(), types.end(), [&](const Type& type) {
+          return isSubType(type, super);
+        })) {
+      return;
+    }
+    if (!getSuperType(types, super)) {
+      WASM_UNREACHABLE("Could not ensure supertype");
     }
-    return type;
   }
 
   std::string toString() const;
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 141ec6496..86f95ccd4 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -630,62 +630,6 @@ bool Type::isSubType(Type left, Type right) {
   return SubTyper().isSubType(left, right);
 }
 
-Type Type::getLeastUpperBound(Type a, Type b) {
-  if (a == b) {
-    return a;
-  }
-  if (a == Type::unreachable) {
-    return b;
-  }
-  if (b == Type::unreachable) {
-    return a;
-  }
-  if (a.size() != b.size()) {
-    return Type::none; // a poison value that must not be consumed
-  }
-  if (a.isRef() || b.isRef()) {
-    if (!a.isRef() || !b.isRef()) {
-      return Type::none;
-    }
-    auto handleNullability = [&](HeapType heapType) {
-      return Type(heapType,
-                  a.isNullable() || b.isNullable() ? Nullable : NonNullable);
-    };
-    auto aHeap = a.getHeapType();
-    auto bHeap = b.getHeapType();
-    if (aHeap.isFunction() && bHeap.isFunction()) {
-      return handleNullability(HeapType::func);
-    }
-    if (aHeap.isData() && bHeap.isData()) {
-      return handleNullability(HeapType::data);
-    }
-    if ((aHeap == HeapType::eq || aHeap == HeapType::i31 ||
-         aHeap == HeapType::data) &&
-        (bHeap == HeapType::eq || bHeap == HeapType::i31 ||
-         bHeap == HeapType::data)) {
-      return handleNullability(HeapType::eq);
-    }
-    // The LUB of two different reference types is anyref, which may or may
-    // not be a valid type depending on whether the GC feature is enabled. When
-    // GC is disabled, it is possible for the finalization of invalid code to
-    // introduce a use of anyref via this function, but that is not a problem
-    // because it will be caught and rejected by validation.
-    return Type::anyref;
-  }
-  if (a.isTuple()) {
-    TypeList types;
-    types.resize(a.size());
-    for (size_t i = 0; i < types.size(); ++i) {
-      types[i] = getLeastUpperBound(a[i], b[i]);
-      if (types[i] == Type::none) {
-        return Type::none;
-      }
-    }
-    return Type(types);
-  }
-  return Type::none;
-}
-
 Type::Iterator Type::end() const {
   if (isTuple()) {
     return Iterator(this, getTypeInfo(*this)->tuple.types.size());
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 057243fd3..80b7eb874 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -209,21 +209,7 @@ struct FunctionValidator : public WalkerPass<PostWalker<FunctionValidator>> {
 
   FunctionValidator(ValidationInfo* info) : info(*info) {}
 
-  struct BreakInfo {
-    enum { UnsetArity = Index(-1), PoisonArity = Index(-2) };
-
-    Type type;
-    Index arity;
-    BreakInfo() : arity(UnsetArity) {}
-    BreakInfo(Type type, Index arity) : type(type), arity(arity) {}
-
-    bool hasBeenSet() {
-      // Compare to the impossible value.
-      return arity != UnsetArity;
-    }
-  };
-
-  std::unordered_map<Name, BreakInfo> breakInfos;
+  std::unordered_map<Name, std::unordered_set<Type>> breakTypes;
   std::unordered_set<Name> delegateTargetNames;
   std::unordered_set<Name> rethrowTargetNames;
 
@@ -248,7 +234,7 @@ public:
   static void visitPreBlock(FunctionValidator* self, Expression** currp) {
     auto* curr = (*currp)->cast<Block>();
     if (curr->name.is()) {
-      self->breakInfos[curr->name];
+      self->breakTypes[curr->name];
     }
   }
 
@@ -259,7 +245,7 @@ public:
   static void visitPreLoop(FunctionValidator* self, Expression** currp) {
     auto* curr = (*currp)->cast<Loop>();
     if (curr->name.is()) {
-      self->breakInfos[curr->name];
+      self->breakTypes[curr->name];
     }
   }
 
@@ -533,49 +519,17 @@ void FunctionValidator::visitBlock(Block* curr) {
   // if we are break'ed to, then the value must be right for us
   if (curr->name.is()) {
     noteLabelName(curr->name);
-    auto iter = breakInfos.find(curr->name);
-    assert(iter != breakInfos.end()); // we set it ourselves
-    auto& info = iter->second;
-    if (info.hasBeenSet()) {
-      if (curr->type.isConcrete()) {
-        shouldBeTrue(info.arity != 0,
-                     curr,
-                     "break arities must be > 0 if block has a value");
-      } else {
-        shouldBeTrue(info.arity == 0,
-                     curr,
-                     "break arities must be 0 if block has no value");
-      }
+    auto iter = breakTypes.find(curr->name);
+    assert(iter != breakTypes.end()); // we set it ourselves
+    for (Type breakType : iter->second) {
       // none or unreachable means a poison value that we should ignore - if
       // consumed, it will error
-      if (info.type.isConcrete() && curr->type.isConcrete()) {
-        shouldBeSubType(
-          info.type,
-          curr->type,
-          curr,
-          "block+breaks must have right type if breaks return a value");
-      }
-      if (curr->type.isConcrete() && info.arity &&
-          info.type != Type::unreachable) {
-        shouldBeSubType(
-          info.type,
-          curr->type,
-          curr,
-          "block+breaks must have right type if breaks have arity");
-      }
-      shouldBeTrue(
-        info.arity != BreakInfo::PoisonArity, curr, "break arities must match");
-      if (curr->list.size() > 0) {
-        auto last = curr->list.back()->type;
-        if (last == Type::none) {
-          shouldBeTrue(info.arity == Index(0),
-                       curr,
-                       "if block ends with a none, breaks cannot send a value "
-                       "of any type");
-        }
-      }
+      shouldBeSubType(breakType,
+                      curr->type,
+                      curr,
+                      "break type must be a subtype of the target block type");
     }
-    breakInfos.erase(iter);
+    breakTypes.erase(iter);
   }
   switch (getFunction()->profile) {
     case IRProfile::Normal:
@@ -679,14 +633,15 @@ void FunctionValidator::validatePoppyBlockElements(Block* curr) {
 void FunctionValidator::visitLoop(Loop* curr) {
   if (curr->name.is()) {
     noteLabelName(curr->name);
-    auto iter = breakInfos.find(curr->name);
-    assert(iter != breakInfos.end()); // we set it ourselves
-    auto& info = iter->second;
-    if (info.hasBeenSet()) {
-      shouldBeEqual(
-        info.arity, Index(0), curr, "breaks to a loop cannot pass a value");
+    auto iter = breakTypes.find(curr->name);
+    assert(iter != breakTypes.end()); // we set it ourselves
+    for (Type breakType : iter->second) {
+      shouldBeEqual(breakType,
+                    Type(Type::none),
+                    curr,
+                    "breaks to a loop cannot pass a value");
     }
-    breakInfos.erase(iter);
+    breakTypes.erase(iter);
   }
   if (curr->type == Type::none) {
     shouldBeFalse(curr->body->type.isConcrete(),
@@ -775,24 +730,12 @@ void FunctionValidator::noteBreak(Name name,
 }
 
 void FunctionValidator::noteBreak(Name name, Type valueType, Expression* curr) {
-  Index arity = 0;
-  if (valueType != Type::none) {
-    arity = 1;
-  }
-  auto iter = breakInfos.find(name);
+  auto iter = breakTypes.find(name);
   if (!shouldBeTrue(
-        iter != breakInfos.end(), curr, "all break targets must be valid")) {
+        iter != breakTypes.end(), curr, "all break targets must be valid")) {
     return;
   }
-  auto& info = iter->second;
-  if (!info.hasBeenSet()) {
-    info = BreakInfo(valueType, arity);
-  } else {
-    info.type = Type::getLeastUpperBound(info.type, valueType);
-    if (arity != info.arity) {
-      info.arity = BreakInfo::PoisonArity;
-    }
-  }
+  iter->second.insert(valueType);
 }
 
 void FunctionValidator::visitBreak(Break* curr) {
@@ -2518,7 +2461,7 @@ void FunctionValidator::visitFunction(Function* curr) {
                     "function result must match, if function has returns");
   }
 
-  assert(breakInfos.empty());
+  assert(breakTypes.empty());
   assert(delegateTargetNames.empty());
   assert(rethrowTargetNames.empty());
   returnTypes.clear();
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index ef8cfb2f7..5eea3f315 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -180,9 +180,9 @@ void Block::finalize() {
     type = Type::none;
     return;
   }
+  type = list.back()->type;
   // The default type is what is at the end. Next we need to see if breaks and/
   // or unreachabitily change that.
-  type = list.back()->type;
   if (!name.is()) {
     // Nothing branches here, so this is easy.
     handleUnreachable(this, NoBreak);
@@ -194,13 +194,12 @@ void Block::finalize() {
   Expression* temp = this;
   seeker.walk(temp);
   if (seeker.found) {
-    // Take the branch values into account.
-    if (seeker.valueType != Type::none) {
-      type = Type::getLeastUpperBound(type, seeker.valueType);
-    } else {
-      // No value is sent, but as we have a branch we are not unreachable.
-      type = Type::none;
-    }
+    // Calculate the supertype of the branch types and the flowed-out type. If
+    // there is no supertype among the available types, assume the current type
+    // is already correct. TODO: calculate proper LUBs to compute a new correct
+    // type in this situation.
+    seeker.types.insert(type);
+    Type::ensureSuperType(seeker.types, type);
   } else {
     // There are no branches, so this block may be unreachable.
     handleUnreachable(this, NoBreak);
@@ -231,17 +230,24 @@ void If::finalize(Type type_) {
 }
 
 void If::finalize() {
-  type = ifFalse ? Type::getLeastUpperBound(ifTrue->type, ifFalse->type)
-                 : Type::none;
+  if (ifFalse) {
+    // TODO: Calculate a proper LUB.
+    Type::ensureSuperType(std::array<Type, 2>{{ifTrue->type, ifFalse->type}},
+                          type);
+  } else {
+    type = Type::none;
+  }
   // if the arms return a value, leave it even if the condition
   // is unreachable, we still mark ourselves as having that type, e.g.
   // (if (result i32)
   //  (unreachable)
   //  (i32.const 10)
-  //  (i32.const 20
+  //  (i32.const 20)
   // )
   // otherwise, if the condition is unreachable, so is the if
-  if (type == Type::none && condition->type == Type::unreachable) {
+  if ((type == Type::none && condition->type == Type::unreachable) ||
+      (ifTrue->type == Type::unreachable && ifFalse &&
+       ifFalse->type == Type::unreachable)) {
     type = Type::unreachable;
   }
 }
@@ -779,7 +785,9 @@ void Select::finalize() {
       condition->type == Type::unreachable) {
     type = Type::unreachable;
   } else {
-    type = Type::getLeastUpperBound(ifTrue->type, ifFalse->type);
+    // TODO: Calculate a proper LUB.
+    Type::ensureSuperType(std::array<Type, 2>{{ifTrue->type, ifFalse->type}},
+                          type);
   }
 }
 
@@ -833,9 +841,16 @@ void RefEq::finalize() {
 }
 
 void Try::finalize() {
-  type = body->type;
+  // If none of the component bodies' type is a supertype of the others, assume
+  // the current type is already correct. TODO: Calculate a proper LUB.
+  std::unordered_set<Type> types{body->type};
   for (auto catchBody : catchBodies) {
-    type = Type::getLeastUpperBound(type, catchBody->type);
+    types.insert(catchBody->type);
+  }
+  if (types.size() == 1 && *types.begin() == Type::unreachable) {
+    type = Type::unreachable;
+  } else {
+    Type::ensureSuperType(types, type);
   }
 }