Use enum instead of bool for StackSignature kind (#3625)

As a readability improvement, use an enum with `Polymorphic` and `Fixed` variants to represent the polymorphic behavior of StackSignatures rather than a `bool uneachable`.
author: Thomas Lively <7121787+tlively@users.noreply.github.com> 2021-02-26 21:27:31 -0800
committer: GitHub <noreply@github.com> 2021-02-26 21:27:31 -0800
commit: 32bfd1c5b32a1ce38da310deb67819c471becb45 (patch)
tree: 37d73a6bcd461104dea2f5e389677ab4fccf0a26 /src
parent: a276c7e9687a98bb4cb222c71278a8658633d80f (diff)
download: binaryen-32bfd1c5b32a1ce38da310deb67819c471becb45.tar.gz
binaryen-32bfd1c5b32a1ce38da310deb67819c471becb45.tar.bz2
binaryen-32bfd1c5b32a1ce38da310deb67819c471becb45.zip
3 files changed, 64 insertions, 55 deletions
diff --git a/src/ir/stack-utils.cpp b/src/ir/stack-utils.cpp
index 05b7f6de6..bc20dfe91 100644
--- a/src/ir/stack-utils.cpp
+++ b/src/ir/stack-utils.cpp
@@ -65,10 +65,10 @@ StackSignature::StackSignature(Expression* expr) {
   }
   params = Type(inputs);
   if (expr->type == Type::unreachable) {
-    unreachable = true;
+    kind = Polymorphic;
     results = Type::none;
   } else {
-    unreachable = false;
+    kind = Fixed;
     results = expr->type;
   }
 }
@@ -91,7 +91,7 @@ StackSignature& StackSignature::operator+=(const StackSignature& next) {
   if (stack.size() >= required) {
     stack.resize(stack.size() - required);
   } else {
-    if (!unreachable) {
+    if (kind == Fixed) {
       // Prepend the unsatisfied params of `next` to the current params
       size_t unsatisfied = required - stack.size();
       std::vector<Type> newParams(next.params.begin(),
@@ -102,9 +102,9 @@ StackSignature& StackSignature::operator+=(const StackSignature& next) {
     stack.clear();
   }
   // Add stack values according to next's results
-  if (next.unreachable) {
+  if (next.kind == Polymorphic) {
     results = next.results;
-    unreachable = true;
+    kind = Polymorphic;
   } else {
     stack.insert(stack.end(), next.results.begin(), next.results.end());
     results = Type(stack);
@@ -124,7 +124,7 @@ bool StackSignature::isSubType(StackSignature a, StackSignature b) {
     // `a` consumes or produces more values than `b` can provides or expects.
     return false;
   }
-  if (b.unreachable && !a.unreachable) {
+  if (a.kind == Fixed && b.kind == Polymorphic) {
     // Non-polymorphic sequences cannot be typed as being polymorphic.
     return false;
   }
@@ -148,8 +148,8 @@ bool StackSignature::isSubType(StackSignature a, StackSignature b) {
   if (!resultSuffixMatches) {
     return false;
   }
-  if (a.unreachable) {
-    // The unreachable can consume any additional provided params and produce
+  if (a.kind == Polymorphic) {
+    // The polymorphism can consume any additional provided params and produce
     // any additional expected results, so we are done.
     return true;
   }
@@ -165,12 +165,12 @@ bool StackSignature::isSubType(StackSignature a, StackSignature b) {
 }
 
 bool StackSignature::haveLeastUpperBound(StackSignature a, StackSignature b) {
-  // If a signature is unreachable, the LUB could extend its params and results
+  // 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.unreachable) {
+    if (self.kind == Polymorphic) {
       return true;
     }
     // If no extension, then no problem.
@@ -248,8 +248,9 @@ StackSignature StackSignature::getLeastUpperBound(StackSignature a,
     return Type::getLeastUpperBound(a, b);
   });
 
-  return StackSignature{
-    Type(params), Type(results), a.unreachable && b.unreachable};
+  Kind kind =
+    a.kind == Polymorphic && b.kind == Polymorphic ? Polymorphic : Fixed;
+  return StackSignature{Type(params), Type(results), kind};
 }
 
 StackFlow::StackFlow(Block* block) {
@@ -264,9 +265,10 @@ StackFlow::StackFlow(Block* block) {
     for (auto* expr : block->list) {
       process(expr, StackSignature(expr));
     }
-    bool unreachable = block->type == Type::unreachable;
-    Type params = unreachable ? Type::none : block->type;
-    process(block, StackSignature(params, Type::none, unreachable));
+    auto kind = block->type == Type::unreachable ? StackSignature::Polymorphic
+                                                 : StackSignature::Fixed;
+    Type params = block->type == Type::unreachable ? Type::none : block->type;
+    process(block, StackSignature(params, Type::none, kind));
   };
 
   // We need to make an initial pass through the block to figure out how many
@@ -289,7 +291,7 @@ StackFlow::StackFlow(Block* block) {
       }
 
       // Handle unreachable or produce results
-      if (sig.unreachable) {
+      if (sig.kind == StackSignature::Polymorphic) {
         if (lastUnreachable) {
           producedByUnreachable[lastUnreachable] = produced;
           produced = 0;
@@ -316,13 +318,14 @@ StackFlow::StackFlow(Block* block) {
            "Block inputs not yet supported");
 
     // Unreachable instructions consume all available values
-    size_t consumed = sig.unreachable
+    size_t consumed = sig.kind == StackSignature::Polymorphic
                         ? std::max(values.size(), sig.params.size())
                         : sig.params.size();
 
     // We previously calculated how many values unreachable instructions produce
-    size_t produced =
-      sig.unreachable ? producedByUnreachable[expr] : sig.results.size();
+    size_t produced = sig.kind == StackSignature::Polymorphic
+                        ? producedByUnreachable[expr]
+                        : sig.results.size();
 
     srcs[expr] = std::vector<Location>(consumed);
     dests[expr] = std::vector<Location>(produced);
@@ -376,7 +379,7 @@ StackFlow::StackFlow(Block* block) {
     }
 
     // Update the last unreachable instruction
-    if (sig.unreachable) {
+    if (sig.kind == StackSignature::Polymorphic) {
       assert(producedByUnreachable[lastUnreachable] == 0);
       lastUnreachable = expr;
     }
@@ -394,8 +397,9 @@ StackSignature StackFlow::getSignature(Expression* expr) {
   for (auto& dest : exprDests->second) {
     results.push_back(dest.type);
   }
-  bool unreachable = expr->type == Type::unreachable;
-  return StackSignature(Type(params), Type(results), unreachable);
+  auto kind = expr->type == Type::unreachable ? StackSignature::Polymorphic
+                                              : StackSignature::Fixed;
+  return StackSignature(Type(params), Type(results), kind);
 }
 
 } // namespace wasm
diff --git a/src/ir/stack-utils.h b/src/ir/stack-utils.h
index 418840263..aad13f7f0 100644
--- a/src/ir/stack-utils.h
+++ b/src/ir/stack-utils.h
@@ -40,12 +40,12 @@ bool mayBeUnreachable(Expression* expr);
 } // namespace StackUtils
 
 // Stack signatures are like regular function signatures, but they are used to
-// represent the stack parameters and results of arbitrary sequences of stacky
-// instructions. They have to record whether they cover an unreachable
-// instruction because their composition takes into account the polymorphic
-// results of unreachable instructions. For example, the following instruction
-// sequences both have params {i32, i32} and results {f32}, but only sequence B
-// is unreachable:
+// represent the stack parameters and results of arbitrary sequences of stack
+// machine instructions. Stack signatures that represent instruction sequences
+// including unreachable instructions are `Polymorphic` and otherwise they are
+// `Fixed`. For example, the following instruction sequences both have params
+// {i32, i32} and results {f32}, but sequence A is `Fixed` while sequence B is
+// `Polymorphic.`
 //
 //  A:
 //    i32.add
@@ -59,8 +59,8 @@ bool mayBeUnreachable(Expression* expr);
 //
 // Notice that this distinction is important because sequence B can be the body
 // of the blocks below but sequence A cannot. In other words, the stack
-// signature of sequence B satisfies the signatures of these blocks, but the
-// stack signature of sequence A does not.
+// signature of sequence B is a subtype of the signatures of these blocks, but
+// the stack signature of sequence A is not.
 //
 //  (block (param f64 i32 i32) (result f32) ... )
 //  (block (param i32 i32) (result f64 f32) ... )
@@ -69,12 +69,14 @@ bool mayBeUnreachable(Expression* expr);
 struct StackSignature {
   Type params;
   Type results;
-  bool unreachable;
+  enum Kind {
+    Fixed,
+    Polymorphic,
+  } kind;
 
-  StackSignature()
-    : params(Type::none), results(Type::none), unreachable(false) {}
-  StackSignature(Type params, Type results, bool unreachable)
-    : params(params), results(results), unreachable(unreachable) {}
+  StackSignature() : params(Type::none), results(Type::none), kind(Fixed) {}
+  StackSignature(Type params, Type results, Kind kind)
+    : params(params), results(results), kind(kind) {}
 
   StackSignature(const StackSignature&) = default;
   StackSignature& operator=(const StackSignature&) = default;
@@ -87,7 +89,7 @@ struct StackSignature {
   // compose.
   template<class InputIt>
   explicit StackSignature(InputIt first, InputIt last)
-    : params(Type::none), results(Type::none), unreachable(false) {
+    : params(Type::none), results(Type::none), kind(Fixed) {
     // TODO: It would be more efficient to build the signature directly and
     // construct the params in reverse to avoid quadratic behavior.
     while (first != last) {
@@ -104,7 +106,7 @@ struct StackSignature {
 
   bool operator==(const StackSignature& other) const {
     return params == other.params && results == other.results &&
-           unreachable == other.unreachable;
+           kind == other.kind;
   }
 
   // Whether a block whose contents have stack signature `a` could be typed with
@@ -117,10 +119,10 @@ struct StackSignature {
   //  - t2 <: t2'
   //  - s1 <: s2
   //
-  //  Note that neither signature is unreachable in this rule and that the
+  //  Note that neither signature is polymorphic 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*] {poly} <: [s1* t1'*] -> [s2* t2'*] {poly?} iff
   //
   //  - [t1*] -> [t2*] <: [t1'*] -> [t2'*]
   //
@@ -150,20 +152,19 @@ struct StackSignature {
   //   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
+  // {poly}. 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 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.
+  // Note that a fixed stack signature (without a {poly}) is never a subtype of
+  // any polymorphic stack signature (with a {poly}). This makes sense because a
+  // sequence of instructions that has no polymorphic behavior cannot be given a
+  // type that says it does have polymorphic 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.
+  // Also, [] -> [] {poly} is the bottom type here; it is a subtype of every
+  // other stack signature. This corresponds to the `unreachable` instruction
+  // 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
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 1a5894343..97146a7c4 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -666,8 +666,8 @@ void FunctionValidator::validatePoppyBlockElements(Block* curr) {
         !info.quiet) {
       getStream() << "(on index " << i << ":\n"
                   << expr << "\n), required: " << sig.params << ", available: ";
-      if (blockSig.unreachable) {
-        getStream() << "unreachable, ";
+      if (blockSig.kind == StackSignature::Polymorphic) {
+        getStream() << "polymorphic, ";
       }
       getStream() << blockSig.results << "\n";
       return;
@@ -675,18 +675,22 @@ void FunctionValidator::validatePoppyBlockElements(Block* curr) {
     blockSig += sig;
   }
   if (curr->type == Type::unreachable) {
-    shouldBeTrue(blockSig.unreachable,
+    shouldBeTrue(blockSig.kind == StackSignature::Polymorphic,
                  curr,
                  "unreachable block should have unreachable element");
   } else {
     if (!shouldBeTrue(
           StackSignature::isSubType(
-            blockSig, StackSignature(Type::none, curr->type, false)),
+            blockSig,
+            StackSignature(Type::none, curr->type, StackSignature::Fixed)),
           curr,
           "block contents should satisfy block type") &&
         !info.quiet) {
       getStream() << "contents: " << blockSig.results
-                  << (blockSig.unreachable ? " [unreachable]" : "") << "\n"
+                  << (blockSig.kind == StackSignature::Polymorphic
+                        ? " [polymorphic]"
+                        : "")
+                  << "\n"
                   << "expected: " << curr->type << "\n";
     }
   }
author	Thomas Lively <7121787+tlively@users.noreply.github.com>	2021-02-26 21:27:31 -0800
committer	GitHub <noreply@github.com>	2021-02-26 21:27:31 -0800
commit	32bfd1c5b32a1ce38da310deb67819c471becb45 (patch)
tree	37d73a6bcd461104dea2f5e389677ab4fccf0a26 /src
parent	a276c7e9687a98bb4cb222c71278a8658633d80f (diff)
download	binaryen-32bfd1c5b32a1ce38da310deb67819c471becb45.tar.gz binaryen-32bfd1c5b32a1ce38da310deb67819c471becb45.tar.bz2 binaryen-32bfd1c5b32a1ce38da310deb67819c471becb45.zip