[Wasm GC] Add negated BrOn* operations (#3913)

They are basically the flip versions. The only interesting part in the impl is that their
returned typed and sent types are different.

Spec: https://docs.google.com/document/d/1DklC3qVuOdLHSXB5UXghM_syCh-4cMinQ50ICiXnK3Q/edit

14 files changed, 228 insertions, 49 deletions

diff --git a/src/gen-s-parser.inc b/src/gen-s-parser.inc
index 7aba3faf1..2eca900cc 100644
--- a/src/gen-s-parser.inc
+++ b/src/gen-s-parser.inc
@@ -76,9 +76,17 @@ switch (op[0]) {
                 goto parse_error;
               case 'o': {
                 switch (op[6]) {
-                  case 'c':
-                    if (strcmp(op, "br_on_cast") == 0) { return makeBrOn(s, BrOnCast); }
-                    goto parse_error;
+                  case 'c': {
+                    switch (op[10]) {
+                      case '\0':
+                        if (strcmp(op, "br_on_cast") == 0) { return makeBrOn(s, BrOnCast); }
+                        goto parse_error;
+                      case '_':
+                        if (strcmp(op, "br_on_cast_fail") == 0) { return makeBrOn(s, BrOnCastFail); }
+                        goto parse_error;
+                      default: goto parse_error;
+                    }
+                  }
                   case 'd':
                     if (strcmp(op, "br_on_data") == 0) { return makeBrOn(s, BrOnData); }
                     goto parse_error;
@@ -88,9 +96,31 @@ switch (op[0]) {
                   case 'i':
                     if (strcmp(op, "br_on_i31") == 0) { return makeBrOn(s, BrOnI31); }
                     goto parse_error;
-                  case 'n':
-                    if (strcmp(op, "br_on_null") == 0) { return makeBrOn(s, BrOnNull); }
-                    goto parse_error;
+                  case 'n': {
+                    switch (op[7]) {
+                      case 'o': {
+                        switch (op[10]) {
+                          case 'd':
+                            if (strcmp(op, "br_on_non_data") == 0) { return makeBrOn(s, BrOnNonData); }
+                            goto parse_error;
+                          case 'f':
+                            if (strcmp(op, "br_on_non_func") == 0) { return makeBrOn(s, BrOnNonFunc); }
+                            goto parse_error;
+                          case 'i':
+                            if (strcmp(op, "br_on_non_i31") == 0) { return makeBrOn(s, BrOnNonI31); }
+                            goto parse_error;
+                          case 'n':
+                            if (strcmp(op, "br_on_non_null") == 0) { return makeBrOn(s, BrOnNonNull); }
+                            goto parse_error;
+                          default: goto parse_error;
+                        }
+                      }
+                      case 'u':
+                        if (strcmp(op, "br_on_null") == 0) { return makeBrOn(s, BrOnNull); }
+                        goto parse_error;
+                      default: goto parse_error;
+                    }
+                  }
                   default: goto parse_error;
                 }
               }
diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index 1dcb55f61..b024c94be 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -153,7 +153,7 @@ void ReFinalize::visitBrOn(BrOn* curr) {
   if (curr->type == Type::unreachable) {
     replaceUntaken(curr->ref, nullptr);
   } else {
-    updateBreakValueType(curr->name, curr->getCastType());
+    updateBreakValueType(curr->name, curr->getSentType());
   }
 }
 void ReFinalize::visitRttCanon(RttCanon* curr) { curr->finalize(); }
diff --git a/src/ir/branch-utils.h b/src/ir/branch-utils.h
index 662f70725..87f7813e7 100644
--- a/src/ir/branch-utils.h
+++ b/src/ir/branch-utils.h
@@ -81,7 +81,7 @@ void operateOnScopeNameUsesAndSentTypes(Expression* expr, T func) {
     } else if (auto* sw = expr->dynCast<Switch>()) {
       func(name, sw->value ? sw->value->type : Type::none);
     } else if (auto* br = expr->dynCast<BrOn>()) {
-      func(name, br->getCastType());
+      func(name, br->getSentType());
     } else {
       assert(expr->is<Try>() || expr->is<Rethrow>()); // delegate or rethrow
     }
diff --git a/src/ir/gc-type-utils.h b/src/ir/gc-type-utils.h
index d59193193..70db7b178 100644
--- a/src/ir/gc-type-utils.h
+++ b/src/ir/gc-type-utils.h
@@ -46,19 +46,33 @@ inline EvaluationResult evaluateKindCheck(Expression* curr) {
   Kind expected;
   Expression* child;
 
+  // Some operations flip the condition.
+  bool flip = false;
+
   if (auto* br = curr->dynCast<BrOn>()) {
     switch (br->op) {
       // We don't check nullability here.
       case BrOnNull:
+      case BrOnNonNull:
       // Casts can only be known at runtime using RTTs.
       case BrOnCast:
+      case BrOnCastFail:
         return Unknown;
+      case BrOnNonFunc:
+        flip = true;
+        [[fallthrough]];
       case BrOnFunc:
         expected = Func;
         break;
+      case BrOnNonData:
+        flip = true;
+        [[fallthrough]];
       case BrOnData:
         expected = Data;
         break;
+      case BrOnNonI31:
+        flip = true;
+        [[fallthrough]];
       case BrOnI31:
         expected = I31;
         break;
@@ -120,7 +134,11 @@ inline EvaluationResult evaluateKindCheck(Expression* curr) {
     return Unknown;
   }
 
-  return actual == expected ? Success : Failure;
+  auto success = actual == expected;
+  if (flip) {
+    success = !success;
+  }
+  return success ? Success : Failure;
 }
 
 } // namespace GCTypeUtils
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index df408fdf3..47db029ab 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -1888,18 +1888,33 @@ struct PrintExpressionContents
       case BrOnNull:
         printMedium(o, "br_on_null ");
         break;
+      case BrOnNonNull:
+        printMedium(o, "br_on_non_null ");
+        break;
       case BrOnCast:
         printMedium(o, "br_on_cast ");
         break;
+      case BrOnCastFail:
+        printMedium(o, "br_on_cast_fail ");
+        break;
       case BrOnFunc:
         printMedium(o, "br_on_func ");
         break;
+      case BrOnNonFunc:
+        printMedium(o, "br_on_non_func ");
+        break;
       case BrOnData:
         printMedium(o, "br_on_data ");
         break;
+      case BrOnNonData:
+        printMedium(o, "br_on_non_data ");
+        break;
       case BrOnI31:
         printMedium(o, "br_on_i31 ");
         break;
+      case BrOnNonI31:
+        printMedium(o, "br_on_non_i31 ");
+        break;
       default:
         WASM_UNREACHABLE("invalid ref.is_*");
     }
diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp
index 88a87ba1f..5631c9d5f 100644
--- a/src/passes/RemoveUnusedBrs.cpp
+++ b/src/passes/RemoveUnusedBrs.cpp
@@ -389,10 +389,9 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
 
     // First, check for a possible null which would prevent all other
     // optimizations.
-    // (Note: if the spec had BrOnNonNull, instead of BrOnNull, then we could
-    // replace a br_on_func whose input is (ref null func) with br_on_non_null,
-    // as only the null check would be needed. But as things are, we cannot do
-    // such a thing.)
+    // TODO: Look into using BrOnNonNull here, to replace a br_on_func whose
+    // input is (ref null func) with br_on_non_null (as only the null check
+    // would be needed).
     auto refType = curr->ref->type;
     if (refType.isNullable()) {
       return;
@@ -405,6 +404,12 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
       anotherCycle = true;
       return;
     }
+    if (curr->op == BrOnNonNull) {
+      // This cannot be null, so the br is always taken.
+      replaceCurrent(Builder(*getModule()).makeBreak(curr->name, curr->ref));
+      anotherCycle = true;
+      return;
+    }
 
     // Check if the type is the kind we are checking for.
     auto result = GCTypeUtils::evaluateKindCheck(curr);
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 00c45ef60..408aafc63 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1019,6 +1019,7 @@ enum ASTNodes {
   RefFunc = 0xd2,
   RefAsNonNull = 0xd3,
   BrOnNull = 0xd4,
+  BrOnNonNull = 0xd6,
 
   // exception handling opcodes
 
@@ -1060,6 +1061,7 @@ enum ASTNodes {
   RefTest = 0x40,
   RefCast = 0x41,
   BrOnCast = 0x42,
+  BrOnCastFail = 0x43,
   RefIsFunc = 0x50,
   RefIsData = 0x51,
   RefIsI31 = 0x52,
@@ -1069,6 +1071,9 @@ enum ASTNodes {
   BrOnFunc = 0x60,
   BrOnData = 0x61,
   BrOnI31 = 0x62,
+  BrOnNonFunc = 0x63,
+  BrOnNonData = 0x64,
+  BrOnNonI31 = 0x65,
 };
 
 enum MemoryAccess {
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 86d868ac8..94230b747 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1500,17 +1500,25 @@ public:
   }
   Flow visitBrOn(BrOn* curr) {
     NOTE_ENTER("BrOn");
-    // BrOnCast uses the casting infrastructure, so handle it first.
-    if (curr->op == BrOnCast) {
+    // BrOnCast* uses the casting infrastructure, so handle it first.
+    if (curr->op == BrOnCast || curr->op == BrOnCastFail) {
       auto cast = doCast(curr);
       if (cast.outcome == cast.Break) {
         return cast.breaking;
       }
       if (cast.outcome == cast.Null || cast.outcome == cast.Failure) {
-        return cast.originalRef;
+        if (curr->op == BrOnCast) {
+          return cast.originalRef;
+        } else {
+          return Flow(curr->name, cast.originalRef);
+        }
       }
       assert(cast.outcome == cast.Success);
-      return Flow(curr->name, cast.castRef);
+      if (curr->op == BrOnCast) {
+        return Flow(curr->name, cast.castRef);
+      } else {
+        return cast.castRef;
+      }
     }
     // The others do a simpler check for the type.
     Flow flow = visit(curr->ref);
@@ -1528,30 +1536,54 @@ public:
       // If the branch is not taken, we return the non-null value.
       return {value};
     }
+    if (curr->op == BrOnNonNull) {
+      // Unlike the others, BrOnNonNull does not return a value if it does not
+      // take the branch.
+      if (value.isNull()) {
+        return Flow();
+      }
+      // If the branch is taken, we send the non-null value.
+      return Flow(curr->name, value);
+    }
+    // See if the input is the right kind (ignoring the flipping behavior of
+    // BrOn*).
+    bool isRightKind;
     if (value.isNull()) {
-      return {value};
+      // A null is never the right kind.
+      isRightKind = false;
+    } else {
+      switch (curr->op) {
+        case BrOnNonFunc:
+        case BrOnFunc:
+          isRightKind = value.type.isFunction();
+          break;
+        case BrOnNonData:
+        case BrOnData:
+          isRightKind = value.isData();
+          break;
+        case BrOnNonI31:
+        case BrOnI31:
+          isRightKind = value.type.getHeapType() == HeapType::i31;
+          break;
+        default:
+          WASM_UNREACHABLE("invalid br_on_*");
+      }
     }
+    // The Non* operations require us to flip the normal behavior.
     switch (curr->op) {
-      case BrOnFunc:
-        if (!value.type.isFunction()) {
-          return {value};
-        }
-        break;
-      case BrOnData:
-        if (!value.isData()) {
-          return {value};
-        }
+      case BrOnNonFunc:
+      case BrOnNonData:
+      case BrOnNonI31:
+        isRightKind = !isRightKind;
         break;
-      case BrOnI31:
-        if (value.type.getHeapType() != HeapType::i31) {
-          return {value};
-        }
-        break;
-      default:
-        WASM_UNREACHABLE("invalid br_on_*");
+      default: {
+      }
+    }
+    if (isRightKind) {
+      // Take the branch.
+      return Flow(curr->name, value);
     }
-    // No problems: take the branch.
-    return Flow(curr->name, value);
+    return {value};
   }
   Flow visitRttCanon(RttCanon* curr) { return Literal(curr->type); }
   Flow visitRttSub(RttSub* curr) {
diff --git a/src/wasm.h b/src/wasm.h
index baea1fabe..08f039451 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -545,10 +545,15 @@ enum RefAsOp {
 
 enum BrOnOp {
   BrOnNull,
+  BrOnNonNull,
   BrOnCast,
+  BrOnCastFail,
   BrOnFunc,
+  BrOnNonFunc,
   BrOnData,
+  BrOnNonData,
   BrOnI31,
+  BrOnNonI31,
 };
 
 //
@@ -1374,7 +1379,7 @@ public:
   Name name;
   Expression* ref;
 
-  // BrOnCast has an rtt that is used in the cast.
+  // BrOnCast* has an rtt that is used in the cast.
   Expression* rtt;
 
   // TODO: BrOnNull also has an optional extra value in the spec, which we do
@@ -1385,7 +1390,8 @@ public:
 
   void finalize();
 
-  Type getCastType();
+  // Returns the type sent on the branch, if it is taken.
+  Type getSentType();
 };
 
 class RttCanon : public SpecificExpression<Expression::RttCanonId> {
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 12aa5f214..35bc468b1 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -3377,6 +3377,9 @@ BinaryConsts::ASTNodes WasmBinaryBuilder::readExpression(Expression*& curr) {
     case BinaryConsts::BrOnNull:
       maybeVisitBrOn(curr, code);
       break;
+    case BinaryConsts::BrOnNonNull:
+      maybeVisitBrOn(curr, code);
+      break;
     case BinaryConsts::Try:
       visitTryOrTryInBlock(curr);
       break;
@@ -6333,24 +6336,39 @@ bool WasmBinaryBuilder::maybeVisitBrOn(Expression*& out, uint32_t code) {
     case BinaryConsts::BrOnNull:
       op = BrOnNull;
       break;
+    case BinaryConsts::BrOnNonNull:
+      op = BrOnNonNull;
+      break;
     case BinaryConsts::BrOnCast:
       op = BrOnCast;
       break;
+    case BinaryConsts::BrOnCastFail:
+      op = BrOnCastFail;
+      break;
     case BinaryConsts::BrOnFunc:
       op = BrOnFunc;
       break;
+    case BinaryConsts::BrOnNonFunc:
+      op = BrOnNonFunc;
+      break;
     case BinaryConsts::BrOnData:
       op = BrOnData;
       break;
+    case BinaryConsts::BrOnNonData:
+      op = BrOnNonData;
+      break;
     case BinaryConsts::BrOnI31:
       op = BrOnI31;
       break;
+    case BinaryConsts::BrOnNonI31:
+      op = BrOnNonI31;
+      break;
     default:
       return false;
   }
   auto name = getBreakTarget(getU32LEB()).name;
   Expression* rtt = nullptr;
-  if (op == BrOnCast) {
+  if (op == BrOnCast || op == BrOnCastFail) {
     rtt = popNonVoidExpression();
   }
   auto* ref = popNonVoidExpression();
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 25db9a993..9c2d028a4 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -2573,7 +2573,7 @@ Expression* SExpressionWasmBuilder::makeBrOn(Element& s, BrOnOp op) {
   auto name = getLabel(*s[1]);
   auto* ref = parseExpression(*s[2]);
   Expression* rtt = nullptr;
-  if (op == BrOnCast) {
+  if (op == BrOnCast || op == BrOnCastFail) {
     rtt = parseExpression(*s[3]);
   }
   return ValidatingBuilder(wasm, s.line, s.col)
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 12c999c0d..70a593bec 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -1954,18 +1954,33 @@ void BinaryInstWriter::visitBrOn(BrOn* curr) {
     case BrOnNull:
       o << int8_t(BinaryConsts::BrOnNull);
       break;
+    case BrOnNonNull:
+      o << int8_t(BinaryConsts::BrOnNonNull);
+      break;
     case BrOnCast:
       o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnCast);
       break;
+    case BrOnCastFail:
+      o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnCastFail);
+      break;
     case BrOnFunc:
       o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnFunc);
       break;
+    case BrOnNonFunc:
+      o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnNonFunc);
+      break;
     case BrOnData:
       o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnData);
       break;
+    case BrOnNonData:
+      o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnNonData);
+      break;
     case BrOnI31:
       o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnI31);
       break;
+    case BrOnNonI31:
+      o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::BrOnNonI31);
+      break;
     default:
       WASM_UNREACHABLE("invalid br_on_*");
   }
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 10b60e0a7..bbc92f09c 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -2245,14 +2245,14 @@ void FunctionValidator::visitBrOn(BrOn* curr) {
     shouldBeTrue(
       curr->ref->type.isRef(), curr, "br_on_cast ref must have ref type");
   }
-  if (curr->op == BrOnCast) {
+  if (curr->op == BrOnCast || curr->op == BrOnCastFail) {
     // Note that an unreachable rtt is not supported: the text and binary
     // formats do not provide the type, so if it's unreachable we should not
     // even create a br_on_cast in such a case, as we'd have no idea what it
     // casts to.
     shouldBeTrue(
       curr->rtt->type.isRtt(), curr, "br_on_cast rtt must have rtt type");
-    noteBreak(curr->name, curr->getCastType(), curr);
+    noteBreak(curr->name, curr->getSentType(), curr);
   } else {
     shouldBeTrue(curr->rtt == nullptr, curr, "non-cast BrOn must not have rtt");
   }
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index f0d130d6b..b41f34ddf 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -916,22 +916,52 @@ void BrOn::finalize() {
   if (ref->type == Type::unreachable ||
       (rtt && rtt->type == Type::unreachable)) {
     type = Type::unreachable;
-  } else {
-    if (op == BrOnNull) {
-      // If BrOnNull does not branch, it flows out the existing value as
-      // non-null.
+    return;
+  }
+  switch (op) {
+    case BrOnNull:
+      // If we do not branch, we flow out the existing value as non-null.
       type = Type(ref->type.getHeapType(), NonNullable);
-    } else {
+      break;
+    case BrOnNonNull:
+      // If we do not branch, we flow out nothing (the spec could also have had
+      // us flow out the null, but it does not).
+      type = Type::none;
+      break;
+    case BrOnCast:
+    case BrOnFunc:
+    case BrOnData:
+    case BrOnI31:
+      // If we do not branch, we return the input in this case.
       type = ref->type;
-    }
+      break;
+    case BrOnCastFail:
+      // If we do not branch, the cast worked, and we have something of the cast
+      // type.
+      type = Type(rtt->type.getHeapType(), NonNullable);
+      break;
+    case BrOnNonFunc:
+      type = Type(HeapType::func, NonNullable);
+      break;
+    case BrOnNonData:
+      type = Type(HeapType::data, NonNullable);
+      break;
+    case BrOnNonI31:
+      type = Type(HeapType::i31, NonNullable);
+      break;
+    default:
+      WASM_UNREACHABLE("invalid br_on_*");
   }
 }
 
-Type BrOn::getCastType() {
+Type BrOn::getSentType() {
   switch (op) {
     case BrOnNull:
       // BrOnNull does not send a value on the branch.
       return Type::none;
+    case BrOnNonNull:
+      // BrOnNonNull sends the non-nullable type on the branch.
+      return Type(ref->type.getHeapType(), NonNullable);
     case BrOnCast:
       return Type(rtt->type.getHeapType(), NonNullable);
     case BrOnFunc:
@@ -940,6 +970,11 @@ Type BrOn::getCastType() {
       return Type::dataref;
     case BrOnI31:
       return Type::i31ref;
+    case BrOnCastFail:
+    case BrOnNonFunc:
+    case BrOnNonData:
+    case BrOnNonI31:
+      return ref->type;
     default:
       WASM_UNREACHABLE("invalid br_on_*");
   }