1 files changed, 134 insertions, 42 deletions
diff --git a/src/ir/stack-utils.cpp b/src/ir/stack-utils.cpp
index 1f70a6618..05b7f6de6 100644
--- a/src/ir/stack-utils.cpp
+++ b/src/ir/stack-utils.cpp
@@ -83,48 +83,6 @@ bool StackSignature::composes(const StackSignature& next) const {
                     });
 }
 
-bool StackSignature::satisfies(Signature sig) const {
-  if (sig.params.size() < params.size() ||
-      sig.results.size() < results.size()) {
-    // Not enough values provided or too many produced
-    return false;
-  }
-  bool paramSuffixMatches =
-    std::equal(params.begin(),
-               params.end(),
-               sig.params.end() - params.size(),
-               [](const Type& consumed, const Type& provided) {
-                 return Type::isSubType(provided, consumed);
-               });
-  if (!paramSuffixMatches) {
-    return false;
-  }
-  bool resultSuffixMatches =
-    std::equal(results.begin(),
-               results.end(),
-               sig.results.end() - results.size(),
-               [](const Type& produced, const Type& expected) {
-                 return Type::isSubType(produced, expected);
-               });
-  if (!resultSuffixMatches) {
-    return false;
-  }
-  if (unreachable) {
-    // The unreachable can consume any additional provided params and produce
-    // any additional expected results, so we are done.
-    return true;
-  }
-  // Any additional provided params will pass through untouched, so they must be
-  // equivalent to the additional produced results.
-  return std::equal(sig.params.begin(),
-                    sig.params.end() - params.size(),
-                    sig.results.begin(),
-                    sig.results.end() - results.size(),
-                    [](const Type& produced, const Type& expected) {
-                      return Type::isSubType(produced, expected);
-                    });
-}
-
 StackSignature& StackSignature::operator+=(const StackSignature& next) {
   assert(composes(next));
   std::vector<Type> stack(results.begin(), results.end());
@@ -160,6 +118,140 @@ StackSignature StackSignature::operator+(const StackSignature& next) const {
   return sig;
 }
 
+bool StackSignature::isSubType(StackSignature a, StackSignature b) {
+  if (a.params.size() > b.params.size() ||
+      a.results.size() > b.results.size()) {
+    // `a` consumes or produces more values than `b` can provides or expects.
+    return false;
+  }
+  if (b.unreachable && !a.unreachable) {
+    // Non-polymorphic sequences cannot be typed as being polymorphic.
+    return false;
+  }
+  bool paramSuffixMatches =
+    std::equal(a.params.begin(),
+               a.params.end(),
+               b.params.end() - a.params.size(),
+               [](const Type& consumed, const Type& provided) {
+                 return Type::isSubType(provided, consumed);
+               });
+  if (!paramSuffixMatches) {
+    return false;
+  }
+  bool resultSuffixMatches =
+    std::equal(a.results.begin(),
+               a.results.end(),
+               b.results.end() - a.results.size(),
+               [](const Type& produced, const Type& expected) {
+                 return Type::isSubType(produced, expected);
+               });
+  if (!resultSuffixMatches) {
+    return false;
+  }
+  if (a.unreachable) {
+    // The unreachable can consume any additional provided params and produce
+    // any additional expected results, so we are done.
+    return true;
+  }
+  // Any additional provided params will pass through untouched, so they must be
+  // compatible with the additional produced results.
+  return std::equal(b.params.begin(),
+                    b.params.end() - a.params.size(),
+                    b.results.begin(),
+                    b.results.end() - a.results.size(),
+                    [](const Type& provided, const Type& expected) {
+                      return Type::isSubType(provided, expected);
+                    });
+}
+
+bool StackSignature::haveLeastUpperBound(StackSignature a, StackSignature b) {
+  // If a signature is unreachable, 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.unreachable) {
+      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);
+  });
+
+  return StackSignature{
+    Type(params), Type(results), a.unreachable && b.unreachable};
+}
+
 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