StackSignature subtypes and LUBs (#3543)

Add a utility for calculating the least upper bounds of two StackSignatures,
taking into account polymorphic unreachable behavior. This will important in the
finalization and validation of Poppy IR blocks, where a block is allowed to
directly produce fewer values than the branches that target it carry if the
difference can be made up for by polymorphism due to an unreachable instruction
in the block.

5 files changed, 387 insertions, 147 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
diff --git a/src/ir/stack-utils.h b/src/ir/stack-utils.h
index fc23b6080..418840263 100644
--- a/src/ir/stack-utils.h
+++ b/src/ir/stack-utils.h
@@ -16,55 +16,7 @@
 
 //
 // stack-utils.h: Utilities for manipulating and analyzing stack machine code in
-// the form of Poppy IR.
-//
-// Poppy IR represents stack machine code using normal Binaryen IR types by
-// imposing the following constraints:
-//
-//  1. Function bodies and children of control flow (except If conditions) must
-//     be blocks.
-//
-//  2. Blocks may have any Expressions except for Pops as children. The sequence
-//     of instructions in a block follows the same validation rules as in
-//     WebAssembly. That means that any expression may have a concrete type, not
-//     just the final expression in the block.
-//
-//  3. All other children must be Pops, which are used to determine the input
-//     stack type of each instruction. Pops may not have `unreachable` type.
-//
-//  4. Only control flow structures and instructions that have polymorphic
-//     unreachable behavior in WebAssembly may have unreachable type. Blocks may
-//     be unreachable when they are not branch targets and when they have an
-//     unreachable child. Note that this means a block may be unreachable even
-//     if it would otherwise have a concrete type, unlike in Binaryen IR.
-//
-// For example, the following Binaryen IR Function:
-//
-//   (func $foo (result i32)
-//    (i32.add
-//     (i32.const 42)
-//     (i32.const 5)
-//    )
-//   )
-//
-// would look like this in Poppy IR:
-//
-//   (func $foo (result i32)
-//    (block
-//     (i32.const 42)
-//     (i32.const 5)
-//     (i32.add
-//      (i32.pop)
-//      (i32.pop)
-//     )
-//    )
-//   )
-//
-// Notice that the sequence of instructions in the block is now identical to the
-// sequence of instructions in raw WebAssembly. Also note that Poppy IR's
-// validation rules are largely additional on top of the normal Binaryen IR
-// validation rules, with the only exceptions being block body validation and
-// block unreahchability rules.
+// the form of Poppy IR. See src/passes/Poppify.cpp for Poppy IR documentation.
 //
 
 #ifndef wasm_ir_stack_h
@@ -121,7 +73,7 @@ struct StackSignature {
 
   StackSignature()
     : params(Type::none), results(Type::none), unreachable(false) {}
-  StackSignature(Type params, Type results, bool unreachable = false)
+  StackSignature(Type params, Type results, bool unreachable)
     : params(params), results(results), unreachable(unreachable) {}
 
   StackSignature(const StackSignature&) = default;
@@ -146,10 +98,6 @@ struct StackSignature {
   // Return `true` iff `next` composes after this stack signature.
   bool composes(const StackSignature& next) const;
 
-  // Whether a block whose contents have this stack signature could be typed
-  // with `sig`.
-  bool satisfies(Signature sig) const;
-
   // Compose stack signatures. Assumes they actually compose.
   StackSignature& operator+=(const StackSignature& next);
   StackSignature operator+(const StackSignature& next) const;
@@ -158,6 +106,72 @@ struct StackSignature {
     return params == other.params && results == other.results &&
            unreachable == other.unreachable;
   }
+
+  // Whether a block whose contents have stack signature `a` could be typed with
+  // stack signature `b`, i.e. whether it could be used in a context that
+  // expects signature `b`. Formally, where `a` is the LHS and `b` the RHS:
+  //
+  // [t1*] -> [t2*] <: [s1* t1'*] -> [s2* t2'*] iff
+  //
+  //  - t1' <: t1
+  //  - t2 <: t2'
+  //  - s1 <: s2
+  //
+  //  Note that neither signature is unreachable in this rule and that the
+  //  cardinalities of t1* and t1'*, t2* and t2'*, and s1* and s2* must match.
+  //
+  // [t1*] -> [t2*] {u} <: [s1* t1'*] -> [s2* t2'*] {u?} iff
+  //
+  //  - [t1*] -> [t2*] <: [t1'*] -> [t2'*]
+  //
+  //  Note that s1* and s2* can have different cardinalities and arbitrary types
+  //  in this rule.
+  //
+  // As an example of the first rule, consider this instruction sequence:
+  //
+  //   ref.as_func
+  //   drop
+  //   i32.add
+  //
+  // The most specific type you could give this sequence is [i32, i32, anyref]
+  // -> [i32]. But it could also be used in a context that expects [i32, i32,
+  // funcref] -> [i32] because ref.as_func can accept funcref or any other
+  // subtype of anyref. That's where the contravariance comes from. This
+  // instruction sequence could also be used anywhere that expects [f32, i32,
+  // i32, anyref] -> [f32, i32] because the f32 simply stays on the stack
+  // throughout the sequence. That's where the the prefix extension comes from.
+  //
+  // For the second rule, consider this sequence:
+  //
+  //   ref.as_func
+  //   drop
+  //   i32.add
+  //   unreachable
+  //   i32.const 0
+  //
+  // This instruction sequence has the specific type [i32, i32, anyref] -> [i32]
+  // {u}. It can be used in any situation the previous block can be used in, but
+  // can additionally be used in contexts that expect something like [f32, i32,
+  // i32, anyref] -> [v128, i32]. Because of the unreachable polymorphism, the
+  // additional prefixes on the params and results do not need to match.
+  //
+  // Note that a reachable stack signature (without a {u}) is never a subtype of
+  // any unreachable stack signature (with a {u}). This makes sense because a
+  // sequence of instructions that has no polymorphic unreachable behavior
+  // cannot be given a type that says it does have polymorphic unreachable
+  // behavior.
+  //
+  // Also, [] -> [] {u} is the bottom type here; it is a subtype of every other
+  // stack signature. This corresponds to (unreachable) 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/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 7e05bd375..276b9602f 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -633,9 +633,11 @@ void FunctionValidator::validatePoppyBlockElements(Block* curr) {
                  curr,
                  "unreachable block should have unreachable element");
   } else {
-    if (!shouldBeTrue(blockSig.satisfies(Signature(Type::none, curr->type)),
-                      curr,
-                      "block contents should satisfy block type") &&
+    if (!shouldBeTrue(
+          StackSignature::isSubType(
+            blockSig, StackSignature(Type::none, curr->type, false)),
+          curr,
+          "block contents should satisfy block type") &&
         !info.quiet) {
       getStream() << "contents: " << blockSig.results
                   << (blockSig.unreachable ? " [unreachable]" : "") << "\n"
diff --git a/test/example/stack-utils.cpp b/test/example/stack-utils.cpp
index 96bc6fb85..63f0d2c66 100644
--- a/test/example/stack-utils.cpp
+++ b/test/example/stack-utils.cpp
@@ -221,79 +221,209 @@ void test_signature_composition() {
   }
 }
 
-void test_signature_satisfaction() {
-  std::cout << ";; Test stack signature satisfaction\n";
-  // No unreachable
+void test_signature_subtype() {
+  std::cout << ";; Test stack signature subtyping\n";
+  // Differences in unreachability only
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b(Type::i32, Type::f32);
-    assert(a.satisfies(b));
+    StackSignature a(Type::none, Type::none, true);
+    StackSignature b(Type::none, Type::none, false);
+    assert(StackSignature::isSubType(a, b));
+    assert(!StackSignature::isSubType(b, a));
   }
+  // Covariance of results
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b({Type::i64, Type::i32}, {Type::i64, Type::f32});
-    assert(a.satisfies(b));
+    StackSignature a(Type::none, Type::funcref, false);
+    StackSignature b(Type::none, Type::anyref, false);
+    assert(StackSignature::isSubType(a, b));
+    assert(!StackSignature::isSubType(b, a));
   }
+  // Contravariance of params
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b({Type::i64, Type::i32}, {Type::i64, Type::i64, Type::f32});
-    assert(!a.satisfies(b));
+    StackSignature a(Type::anyref, Type::none, false);
+    StackSignature b(Type::funcref, Type::none, false);
+    assert(StackSignature::isSubType(a, b));
+    assert(!StackSignature::isSubType(b, a));
   }
+  // First not unreachable
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b({Type::i64, Type::i32}, {Type::f64, Type::f32});
-    assert(!a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b(Type::i32, Type::f32, false);
+    assert(StackSignature::isSubType(a, b));
   }
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b(Type::none, Type::f32);
-    assert(!a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b({Type::i64, Type::i32}, {Type::i64, Type::f32}, false);
+    assert(StackSignature::isSubType(a, b));
   }
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b(Type::i32, Type::none);
-    assert(!a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b(
+      {Type::i64, Type::i32}, {Type::i64, Type::i64, Type::f32}, false);
+    assert(!StackSignature::isSubType(a, b));
   }
   {
-    StackSignature a{Type::i32, Type::f32, false};
-    Signature b(Type::f32, Type::i32);
-    assert(!a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b({Type::i64, Type::i32}, {Type::f64, Type::f32}, false);
+    assert(!StackSignature::isSubType(a, b));
   }
-  // With unreachable
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b(Type::i32, Type::f32);
-    assert(a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b(Type::none, Type::f32, false);
+    assert(!StackSignature::isSubType(a, b));
   }
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b({Type::i64, Type::i32}, {Type::i64, Type::f32});
-    assert(a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b(Type::i32, Type::none, false);
+    assert(!StackSignature::isSubType(a, b));
   }
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b({Type::i64, Type::i32}, {Type::i64, Type::i64, Type::f32});
-    assert(a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, false);
+    StackSignature b(Type::f32, Type::i32, false);
+    assert(!StackSignature::isSubType(a, b));
+  }
+  // First unreachable
+  {
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b(Type::i32, Type::f32, false);
+    assert(StackSignature::isSubType(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b({Type::i64, Type::i32}, {Type::i64, Type::f32}, false);
+    assert(StackSignature::isSubType(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b(
+      {Type::i64, Type::i32}, {Type::i64, Type::i64, Type::f32}, false);
+    assert(StackSignature::isSubType(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b({Type::i64, Type::i32}, {Type::f64, Type::f32}, false);
+    assert(StackSignature::isSubType(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b(Type::none, Type::f32, false);
+    assert(!StackSignature::isSubType(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b(Type::i32, Type::none, false);
+    assert(!StackSignature::isSubType(a, b));
   }
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b({Type::i64, Type::i32}, {Type::f64, Type::f32});
-    assert(a.satisfies(b));
+    StackSignature a(Type::i32, Type::f32, true);
+    StackSignature b(Type::f32, Type::i32, false);
+    assert(!StackSignature::isSubType(a, b));
+  }
+}
+
+void test_signature_lub() {
+  std::cout << ";; Test stack signature lub\n";
+  {
+    StackSignature a{Type::none, Type::none, false};
+    StackSignature b{Type::none, Type::none, false};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{Type::none, Type::none, false}));
   }
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b(Type::none, Type::f32);
-    assert(!a.satisfies(b));
+    StackSignature a{Type::none, Type::none, true};
+    StackSignature b{Type::none, Type::none, false};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{Type::none, Type::none, false}));
   }
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b(Type::i32, Type::none);
-    assert(!a.satisfies(b));
+    StackSignature a{Type::none, Type::none, false};
+    StackSignature b{Type::none, Type::none, true};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{Type::none, Type::none, false}));
   }
   {
-    StackSignature a{Type::i32, Type::f32, true};
-    Signature b(Type::f32, Type::i32);
-    assert(!a.satisfies(b));
+    StackSignature a{Type::i32, Type::none, true};
+    StackSignature b{Type::none, Type::i32, true};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{Type::i32, Type::i32, true}));
+  }
+  {
+    StackSignature a{Type::none, Type::i32, true};
+    StackSignature b{Type::i32, Type::none, true};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{Type::i32, Type::i32, true}));
+  }
+  {
+    StackSignature a{Type::none, Type::externref, true};
+    StackSignature b{Type::none, Type::funcref, true};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{Type::none, Type::anyref, true}));
+  }
+  {
+    StackSignature a{Type::anyref, Type::none, true};
+    StackSignature b{Type::funcref, Type::none, true};
+    // assert(StackSignature::haveLeastUpperBound(a, b));
+    // assert(StackSignature::getLeastUpperBound(a, b) ==
+    //        (StackSignature{Type::funcref, Type::none, true}));
+  }
+  {
+    StackSignature a{{Type::i32, Type::funcref}, Type::funcref, true};
+    StackSignature b{Type::funcref, {Type::f32, Type::externref}, true};
+    assert(StackSignature::haveLeastUpperBound(a, b));
+    assert(StackSignature::getLeastUpperBound(a, b) ==
+           (StackSignature{
+             {Type::i32, Type::funcref}, {Type::f32, Type::anyref}, true}));
+  }
+  // No LUB
+  {
+    StackSignature a(Type::none, Type::i32, false);
+    StackSignature b(Type::none, Type::f32, false);
+    assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a(Type::none, Type::i32, true);
+    StackSignature b(Type::none, Type::f32, true);
+    assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::none, false);
+    StackSignature b(Type::f32, Type::none, false);
+    // assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a(Type::i32, Type::none, true);
+    StackSignature b(Type::f32, Type::none, true);
+    // assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a(Type::none, Type::none, false);
+    StackSignature b(Type::none, Type::i32, true);
+    assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a(Type::none, Type::none, false);
+    StackSignature b(Type::i32, Type::none, true);
+    assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a{Type::none, Type::i32, false};
+    StackSignature b{Type::i32, Type::none, false};
+    assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a{Type::none, Type::i32, true};
+    StackSignature b{Type::i32, Type::none, false};
+    assert(!StackSignature::haveLeastUpperBound(a, b));
+  }
+  {
+    StackSignature a{Type::none, Type::i32, false};
+    StackSignature b{Type::i32, Type::none, true};
+    assert(!StackSignature::haveLeastUpperBound(a, b));
   }
 }
 
@@ -435,6 +565,7 @@ int main() {
   test_remove_nops();
   test_stack_signatures();
   test_signature_composition();
-  test_signature_satisfaction();
+  test_signature_subtype();
+  test_signature_lub();
   test_stack_flow();
 }
diff --git a/test/example/stack-utils.txt b/test/example/stack-utils.txt
index c278ca099..d24119aab 100644
--- a/test/example/stack-utils.txt
+++ b/test/example/stack-utils.txt
@@ -13,5 +13,6 @@
 )
 ;; Test stack signatures
 ;; Test stack signature composition
-;; Test stack signature satisfaction
+;; Test stack signature subtyping
+;; Test stack signature lub
 ;; Test stack flow