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.

1 files changed, 68 insertions, 54 deletions

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