1 files changed, 89 insertions, 0 deletions
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