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.

2 files changed, 180 insertions, 48 deletions

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