Remove LUB calculation (#3669)

Since correct LUB calculation for recursive types is complicated, stop depending
on LUBs throughout the code base. This also fixes a validation bug in which the
validator required blocks to be typed with the LUB of all the branch types, when
in fact any upper bound should have been valid. In addition to fixing that bug,
this PR simplifies the code for break handling by not storing redundant
information about the arity of types.

12 files changed, 106 insertions, 393 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);
   }
 }
 
diff --git a/test/example/stack-utils.cpp b/test/example/stack-utils.cpp
index b5ac496ca..9ed3e1a8a 100644
--- a/test/example/stack-utils.cpp
+++ b/test/example/stack-utils.cpp
@@ -354,118 +354,6 @@ void test_signature_subtype() {
   }
 }
 
-void test_signature_lub() {
-  std::cout << ";; Test stack signature lub\n";
-  {
-    StackSignature a{Type::none, Type::none, StackSignature::Fixed};
-    StackSignature b{Type::none, Type::none, StackSignature::Fixed};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(StackSignature::getLeastUpperBound(a, b) ==
-           (StackSignature{Type::none, Type::none, StackSignature::Fixed}));
-  }
-  {
-    StackSignature a{Type::none, Type::none, StackSignature::Polymorphic};
-    StackSignature b{Type::none, Type::none, StackSignature::Fixed};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(StackSignature::getLeastUpperBound(a, b) ==
-           (StackSignature{Type::none, Type::none, StackSignature::Fixed}));
-  }
-  {
-    StackSignature a{Type::none, Type::none, StackSignature::Fixed};
-    StackSignature b{Type::none, Type::none, StackSignature::Polymorphic};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(StackSignature::getLeastUpperBound(a, b) ==
-           (StackSignature{Type::none, Type::none, StackSignature::Fixed}));
-  }
-  {
-    StackSignature a{Type::i32, Type::none, StackSignature::Polymorphic};
-    StackSignature b{Type::none, Type::i32, StackSignature::Polymorphic};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(StackSignature::getLeastUpperBound(a, b) ==
-           (StackSignature{Type::i32, Type::i32, StackSignature::Polymorphic}));
-  }
-  {
-    StackSignature a{Type::none, Type::i32, StackSignature::Polymorphic};
-    StackSignature b{Type::i32, Type::none, StackSignature::Polymorphic};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(StackSignature::getLeastUpperBound(a, b) ==
-           (StackSignature{Type::i32, Type::i32, StackSignature::Polymorphic}));
-  }
-  {
-    StackSignature a{Type::none, Type::externref, StackSignature::Polymorphic};
-    StackSignature b{Type::none, Type::funcref, StackSignature::Polymorphic};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(
-      StackSignature::getLeastUpperBound(a, b) ==
-      (StackSignature{Type::none, Type::anyref, StackSignature::Polymorphic}));
-  }
-  {
-    StackSignature a{Type::anyref, Type::none, StackSignature::Polymorphic};
-    StackSignature b{Type::funcref, Type::none, StackSignature::Polymorphic};
-    // assert(StackSignature::haveLeastUpperBound(a, b));
-    // assert(StackSignature::getLeastUpperBound(a, b) ==
-    //        (StackSignature{Type::funcref, Type::none,
-    //        StackSignature::Polymorphic}));
-  }
-  {
-    StackSignature a{
-      {Type::i32, Type::funcref}, Type::funcref, StackSignature::Polymorphic};
-    StackSignature b{
-      Type::funcref, {Type::f32, Type::externref}, StackSignature::Polymorphic};
-    assert(StackSignature::haveLeastUpperBound(a, b));
-    assert(StackSignature::getLeastUpperBound(a, b) ==
-           (StackSignature{{Type::i32, Type::funcref},
-                           {Type::f32, Type::anyref},
-                           StackSignature::Polymorphic}));
-  }
-  // No LUB
-  {
-    StackSignature a(Type::none, Type::i32, StackSignature::Fixed);
-    StackSignature b(Type::none, Type::f32, StackSignature::Fixed);
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a(Type::none, Type::i32, StackSignature::Polymorphic);
-    StackSignature b(Type::none, Type::f32, StackSignature::Polymorphic);
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a(Type::i32, Type::none, StackSignature::Fixed);
-    StackSignature b(Type::f32, Type::none, StackSignature::Fixed);
-    // assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a(Type::i32, Type::none, StackSignature::Polymorphic);
-    StackSignature b(Type::f32, Type::none, StackSignature::Polymorphic);
-    // assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a(Type::none, Type::none, StackSignature::Fixed);
-    StackSignature b(Type::none, Type::i32, StackSignature::Polymorphic);
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a(Type::none, Type::none, StackSignature::Fixed);
-    StackSignature b(Type::i32, Type::none, StackSignature::Polymorphic);
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a{Type::none, Type::i32, StackSignature::Fixed};
-    StackSignature b{Type::i32, Type::none, StackSignature::Fixed};
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a{Type::none, Type::i32, StackSignature::Polymorphic};
-    StackSignature b{Type::i32, Type::none, StackSignature::Fixed};
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-  {
-    StackSignature a{Type::none, Type::i32, StackSignature::Fixed};
-    StackSignature b{Type::i32, Type::none, StackSignature::Polymorphic};
-    assert(!StackSignature::haveLeastUpperBound(a, b));
-  }
-}
-
 void test_stack_flow() {
   std::cout << ";; Test stack flow\n";
   {
@@ -605,6 +493,5 @@ int main() {
   test_stack_signatures();
   test_signature_composition();
   test_signature_subtype();
-  test_signature_lub();
   test_stack_flow();
 }
diff --git a/test/example/stack-utils.txt b/test/example/stack-utils.txt
index d24119aab..a61ed9ac5 100644
--- a/test/example/stack-utils.txt
+++ b/test/example/stack-utils.txt
@@ -14,5 +14,4 @@
 ;; Test stack signatures
 ;; Test stack signature composition
 ;; Test stack signature subtyping
-;; Test stack signature lub
 ;; Test stack flow