LUBs (#3731)

This is a partial revert of #3669, which removed the old implementation of
Type::getLeastUpperBound that did not correctly handle recursive types. The new
implementation in this PR uses a TypeBuilder to construct LUBs and for recursive
types, it returns a temporary HeapType that has not yet been fully constructed
to break what would otherwise be infinite recursions.

8 files changed, 389 insertions, 67 deletions

diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index 947f9d975..0f7bab653 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -50,8 +50,9 @@ void ReFinalize::visitBlock(Block* curr) {
       // 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);
+      auto& types = iter->second;
+      types.insert(curr->list.back()->type);
+      curr->type = Type::getLeastUpperBound(types);
       return;
     }
   }
diff --git a/src/ir/stack-utils.cpp b/src/ir/stack-utils.cpp
index aa6da22d9..bc20dfe91 100644
--- a/src/ir/stack-utils.cpp
+++ b/src/ir/stack-utils.cpp
@@ -164,6 +164,95 @@ 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 0c05381db..aad13f7f0 100644
--- a/src/ir/stack-utils.h
+++ b/src/ir/stack-utils.h
@@ -166,6 +166,13 @@ 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 fa3e34423..805844a71 100644
--- a/src/ir/utils.h
+++ b/src/ir/utils.h
@@ -107,11 +107,8 @@ struct ReFinalize
   ReFinalize() { name = "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
-
-  // 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;
+  // bulk, tracking break value types so we just do a linear pass.
+  std::unordered_map<Name, std::unordered_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 c89a57976..506eee5e6 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -297,9 +297,7 @@ struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
             BranchUtils::BranchSeeker seeker(block->name);
             Expression* temp = block;
             seeker.walk(temp);
-            Type supertype;
-            if (seeker.found && Type::getSuperType(seeker.types, supertype) &&
-                supertype != Type::none) {
+            if (seeker.found && Type::hasLeastUpperBound(seeker.types)) {
               canPop = false;
             }
           }
diff --git a/src/wasm-type.h b/src/wasm-type.h
index befac3c1a..def5c7e2b 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -19,7 +19,6 @@
 
 #include "support/name.h"
 #include "wasm-features.h"
-#include <algorithm>
 #include <ostream>
 #include <vector>
 
@@ -205,42 +204,36 @@ public:
   // Returns true if left is a subtype of right. Subtype includes itself.
   static bool isSubType(Type left, Type right);
 
-  // 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())) {
+  // 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 bool hasLeastUpperBound(Type a, Type b);
+  static Type getLeastUpperBound(Type a, Type b);
+  template<typename T> static bool hasLeastUpperBound(const T& types) {
+    auto first = types.begin(), end = types.end();
+    if (first == end) {
+      return false;
+    }
+    for (auto second = std::next(first); second != end;) {
+      if (!hasLeastUpperBound(*first++, *second++)) {
         return false;
       }
     }
-    super = sorted.back();
     return true;
   }
-
-  // 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;
+  template<typename T> static Type getLeastUpperBound(const T& types) {
+    auto it = types.begin(), end = types.end();
+    if (it == end) {
+      return Type::none;
     }
-    if (!getSuperType(types, super)) {
-      WASM_UNREACHABLE("Could not ensure supertype");
+    Type lub = *it++;
+    for (; it != end; ++it) {
+      lub = getLeastUpperBound(lub, *it);
+      if (lub == Type::none) {
+        return Type::none;
+      }
     }
+    return lub;
   }
 
   std::string toString() const;
@@ -423,6 +416,8 @@ struct Field {
   } packedType; // applicable iff type=i32
   Mutability mutable_;
 
+  // Arbitrary defaults for convenience.
+  Field() : type(Type::i32), packedType(not_packed), mutable_(Mutable) {}
   Field(Type type, Mutability mutable_)
     : type(type), packedType(not_packed), mutable_(mutable_) {}
   Field(PackedType packedType, Mutability mutable_)
@@ -452,6 +447,7 @@ typedef std::vector<Field> FieldList;
 // amount of data.
 struct Struct {
   FieldList fields;
+  Struct() = default;
   Struct(const Struct& other) : fields(other.fields) {}
   Struct(const FieldList& fields) : fields(fields) {}
   Struct(FieldList&& fields) : fields(std::move(fields)) {}
@@ -465,6 +461,7 @@ struct Struct {
 
 struct Array {
   Field element;
+  Array() = default;
   Array(const Array& other) : element(other.element) {}
   Array(Field element) : element(element) {}
   bool operator==(const Array& other) const { return element == other.element; }
@@ -525,7 +522,7 @@ struct TypeBuilder {
 
   // Gets a temporary type or heap type for use in initializing the
   // TypeBuilder's HeapTypes. For Ref and Rtt types, the HeapType may be a
-  // temporary HeapType owned by this builder or a canonical HeapType. HeapType
+  // temporary HeapType owned by this builder or a canonical HeapType.
   Type getTempTupleType(const Tuple&);
   Type getTempRefType(HeapType heapType, Nullability nullable);
   Type getTempRttType(Rtt rtt);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 2c516ed98..f60f1c3a7 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -139,13 +139,38 @@ struct SubTyper {
   bool isSubType(HeapType a, HeapType b);
   bool isSubType(const Tuple& a, const Tuple& b);
   bool isSubType(const Field& a, const Field& b);
-  bool isSubType(const HeapTypeInfo& a, const HeapTypeInfo& b);
   bool isSubType(const Signature& a, const Signature& b);
   bool isSubType(const Struct& a, const Struct& b);
   bool isSubType(const Array& a, const Array& b);
   bool isSubType(const Rtt& a, const Rtt& b);
 };
 
+// Helper for finding the equirecursive least upper bound of two types.
+struct TypeBounder {
+  TypeBuilder builder;
+  // The indices in `builder` at which the LUB of each pair of HeapTypes are
+  // being constructed.
+  std::unordered_map<std::pair<HeapType, HeapType>, size_t> indices;
+
+  bool hasLeastUpperBound(Type a, Type b);
+  Type getLeastUpperBound(Type a, Type b);
+
+private:
+  // Return true and set `out` to be the LUB iff a LUB was found. The HeapType
+  // and Struct overloads are exceptional because they are infallible;
+  // HeapType::any is an upper bound of all HeapTypes and the empty struct is an
+  // upper bound of all struct types. Note that these methods can return
+  // temporary types, so they should never be used directly.
+  bool lub(Type a, Type b, Type& out);
+  HeapType lub(HeapType a, HeapType b);
+  bool lub(const Tuple& a, const Tuple& b, Tuple& out);
+  bool lub(const Field& a, const Field& b, Field& out);
+  bool lub(const Signature& a, const Signature& b, Signature& out);
+  Struct lub(const Struct& a, const Struct& b);
+  bool lub(const Array& a, const Array& b, Array& out);
+  bool lub(const Rtt& a, const Rtt& b, Rtt& out);
+};
+
 // Helper for printing types without infinitely recursing on recursive types.
 struct TypePrinter {
   size_t currDepth = 0;
@@ -773,6 +798,14 @@ bool Type::isSubType(Type left, Type right) {
   return SubTyper().isSubType(left, right);
 }
 
+bool Type::hasLeastUpperBound(Type a, Type b) {
+  return TypeBounder().hasLeastUpperBound(a, b);
+}
+
+Type Type::getLeastUpperBound(Type a, Type b) {
+  return TypeBounder().getLeastUpperBound(a, b);
+}
+
 Type::Iterator Type::end() const {
   if (isTuple()) {
     return Iterator(this, getTypeInfo(*this)->tuple.types.size());
@@ -1101,8 +1134,8 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
     return true;
   }
   if (seen.count({a, b})) {
-    // We weren't able to disprove that a is a subtype of b since we last saw
-    // them, so the relation holds coinductively.
+    // We weren't able to disprove that a == b since we last saw them, so the
+    // relation holds coinductively.
     return true;
   }
   // Everything is a subtype of any.
@@ -1111,7 +1144,7 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
   }
   // Various things are subtypes of eq.
   if (b == HeapType::eq) {
-    return a == HeapType::i31 || a.isArray() || a.isStruct();
+    return a == HeapType::i31 || a.isData();
   }
   // Some are also subtypes of data.
   if (b == HeapType::data) {
@@ -1121,8 +1154,8 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
   if (b == HeapType::func) {
     return a.isSignature();
   }
-  // As we recurse, we will coinductively assume that a is a subtype of b unless
-  // proven otherwise.
+  // As we recurse, we will coinductively assume that a == b unless proven
+  // otherwise.
   seen.insert({a, b});
   if (a.isSignature() && b.isSignature()) {
     return isSubType(a.getSignature(), b.getSignature());
@@ -1188,6 +1221,219 @@ bool SubTyper::isSubType(const Rtt& a, const Rtt& b) {
   return a.heapType == b.heapType && a.hasDepth() && !b.hasDepth();
 }
 
+bool TypeBounder::hasLeastUpperBound(Type a, Type b) {
+  Type tempLUB;
+  return lub(a, b, tempLUB);
+}
+
+Type TypeBounder::getLeastUpperBound(Type a, Type b) {
+  Type tempLUB;
+  if (!lub(a, b, tempLUB)) {
+    return Type::none;
+  }
+  // `tempLUB` is a temporary type owned by `builder`. Since TypeBuilder::build
+  // returns HeapTypes rather than Types, create a new HeapType definition meant
+  // only to get `tempLUB` canonicalized in a known location. The use of an
+  // Array is arbitrary; it might as well have been a Struct.
+  builder.grow(1);
+  builder[builder.size() - 1] = Array(Field(tempLUB, Mutable));
+  return builder.build().back().getArray().element.type;
+}
+
+bool TypeBounder::lub(Type a, Type b, Type& out) {
+  if (a == b) {
+    out = a;
+    return true;
+  }
+  if (a == Type::unreachable) {
+    out = b;
+    return true;
+  }
+  if (b == Type::unreachable) {
+    out = a;
+    return true;
+  }
+  if (a.isTuple() && b.isTuple()) {
+    Tuple tuple;
+    if (!lub(a.getTuple(), b.getTuple(), tuple)) {
+      return false;
+    }
+    out = builder.getTempTupleType(tuple);
+    return true;
+  } else if (a.isRef() && b.isRef()) {
+    auto nullability =
+      (a.isNullable() || b.isNullable()) ? Nullable : NonNullable;
+    HeapType heapType = lub(a.getHeapType(), b.getHeapType());
+    out = builder.getTempRefType(heapType, nullability);
+    return true;
+  } else if (a.isRtt() && b.isRtt()) {
+    Rtt rtt(HeapType::any);
+    if (!lub(a.getRtt(), b.getRtt(), rtt)) {
+      return false;
+    }
+    out = builder.getTempRttType(rtt);
+    return true;
+  }
+  return false;
+}
+
+HeapType TypeBounder::lub(HeapType a, HeapType b) {
+  if (a == b) {
+    return a;
+  }
+  // Canonicalize to have the basic HeapType on the left.
+  if (b.isBasic()) {
+    std::swap(a, b);
+  }
+  if (a.isBasic()) {
+    switch (a.getBasic()) {
+      case HeapType::func:
+        if (b.isFunction()) {
+          return HeapType::func;
+        } else {
+          return HeapType::any;
+        }
+      case HeapType::ext:
+        return HeapType::any;
+      case HeapType::any:
+        return HeapType::any;
+      case HeapType::eq:
+        if (b == HeapType::i31 || b.isData()) {
+          return HeapType::eq;
+        } else {
+          return HeapType::any;
+        }
+      case HeapType::i31:
+        if (b.isData()) {
+          return HeapType::eq;
+        } else {
+          return HeapType::any;
+        }
+      case HeapType::data:
+        if (b.isData()) {
+          return HeapType::data;
+        } else if (b == HeapType::i31) {
+          return HeapType::eq;
+        } else {
+          return HeapType::any;
+        }
+    }
+  }
+  // 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));
+  size_t index = builder.size();
+  auto result = indices.insert({pair, index});
+  if (!result.second) {
+    // We've seen this pair before; stop recursing and do not allocate.
+    return builder[result.first->second];
+  }
+
+  builder.grow(1);
+  if (a.isSignature() && b.isSignature()) {
+    Signature sig;
+    if (lub(a.getSignature(), b.getSignature(), sig)) {
+      return builder[index] = sig;
+    } else {
+      return builder[index] = HeapType::func;
+    }
+  } else if (a.isStruct() && b.isStruct()) {
+    return builder[index] = lub(a.getStruct(), b.getStruct());
+  } else if (a.isArray() && b.isArray()) {
+    Array array;
+    if (lub(a.getArray(), b.getArray(), array)) {
+      return builder[index] = array;
+    } else {
+      return builder[index] = HeapType::data;
+    }
+  } else {
+    // The types are not of the same kind, so the LUB is either `data` or `any`.
+    if (a.isSignature() || b.isSignature()) {
+      return builder[index] = HeapType::any;
+    } else {
+      return builder[index] = HeapType::data;
+    }
+  }
+}
+
+bool TypeBounder::lub(const Tuple& a, const Tuple& b, Tuple& out) {
+  if (a.types.size() != b.types.size()) {
+    return false;
+  }
+  out.types.resize(a.types.size());
+  for (size_t i = 0; i < a.types.size(); ++i) {
+    if (!lub(a.types[i], b.types[i], out.types[i])) {
+      return false;
+    }
+  }
+  return true;
+}
+
+bool TypeBounder::lub(const Field& a, const Field& b, Field& out) {
+  if (a == b) {
+    out = a;
+    return true;
+  }
+  // Mutable fields are invariant, so they would have had to be the same.
+  if (a.mutable_ == Mutable || b.mutable_ == Mutable) {
+    return false;
+  }
+  // Packed types must match.
+  if (a.isPacked() != b.isPacked() ||
+      (a.isPacked() && a.packedType != b.packedType)) {
+    return false;
+  }
+  // Either the packed types match or the types aren't packed.
+  Type type;
+  if (lub(a.type, b.type, type)) {
+    out = a;
+    out.type = type;
+    return true;
+  } else {
+    return false;
+  }
+}
+
+bool TypeBounder::lub(const Signature& a, const Signature& b, Signature& out) {
+  // TODO: Implement proper signature subtyping, covariant in results and
+  // contravariant in params, once V8 implements it.
+  if (a != b) {
+    return false;
+  } else {
+    out = a;
+    return true;
+  }
+}
+
+Struct TypeBounder::lub(const Struct& a, const Struct& b) {
+  Struct out;
+  size_t numFields = std::min(a.fields.size(), b.fields.size());
+  for (size_t i = 0; i < numFields; ++i) {
+    Field field;
+    if (lub(a.fields[i], b.fields[i], field)) {
+      out.fields.push_back(field);
+    } else {
+      // Stop at the common prefix and ignore the rest.
+      break;
+    }
+  }
+  return out;
+}
+
+bool TypeBounder::lub(const Array& a, const Array& b, Array& out) {
+  return lub(a.element, b.element, out.element);
+}
+
+bool TypeBounder::lub(const Rtt& a, const Rtt& b, Rtt& out) {
+  if (a.heapType != b.heapType) {
+    return false;
+  }
+  uint32_t depth = (a.depth == b.depth) ? a.depth : Rtt::NoDepth;
+  out = Rtt(depth, a.heapType);
+  return true;
+}
+
 template<typename T, typename F>
 std::ostream& TypePrinter::printChild(T curr, F printer) {
   auto it = depths.find(curr.getID());
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index 2dba93a4a..18f8594b1 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);
@@ -199,7 +199,7 @@ void Block::finalize() {
     // 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);
+    type = Type::getLeastUpperBound(seeker.types);
   } else {
     // There are no branches, so this block may be unreachable.
     handleUnreachable(this, NoBreak);
@@ -230,13 +230,8 @@ void If::finalize(Type type_) {
 }
 
 void If::finalize() {
-  if (ifFalse) {
-    // TODO: Calculate a proper LUB.
-    Type::ensureSuperType(std::array<Type, 2>{{ifTrue->type, ifFalse->type}},
-                          type);
-  } else {
-    type = Type::none;
-  }
+  type = ifFalse ? Type::getLeastUpperBound(ifTrue->type, ifFalse->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)
@@ -245,9 +240,7 @@ void If::finalize() {
   //  (i32.const 20)
   // )
   // otherwise, if the condition is unreachable, so is the if
-  if ((type == Type::none && condition->type == Type::unreachable) ||
-      (ifTrue->type == Type::unreachable && ifFalse &&
-       ifFalse->type == Type::unreachable)) {
+  if (type == Type::none && condition->type == Type::unreachable) {
     type = Type::unreachable;
   }
 }
@@ -785,9 +778,7 @@ void Select::finalize() {
       condition->type == Type::unreachable) {
     type = Type::unreachable;
   } else {
-    // TODO: Calculate a proper LUB.
-    Type::ensureSuperType(std::array<Type, 2>{{ifTrue->type, ifFalse->type}},
-                          type);
+    type = Type::getLeastUpperBound(ifTrue->type, ifFalse->type);
   }
 }
 
@@ -847,11 +838,7 @@ void Try::finalize() {
   for (auto catchBody : catchBodies) {
     types.insert(catchBody->type);
   }
-  if (types.size() == 1 && *types.begin() == Type::unreachable) {
-    type = Type::unreachable;
-  } else {
-    Type::ensureSuperType(types, type);
-  }
+  type = Type::getLeastUpperBound(types);
 }
 
 void Try::finalize(Type type_) {