[Wasm GC] Casts of a non-nullable bottom type to non-null fail (#5645)

Casting (ref nofunc) to (ref func) seems like it can succeed based on the rule
of "if it's a subtype, it can cast ok." But the fuzzer found a corner case where that
leads to a validation error (see testcase).

Refactor the cast evaluation logic to handle uninhabitable refs directly, and
return Unreachable for them (since the cast cannot even be reached).

Also reorder the rule checks there to always check for a non-nullable cast
of a bottom type (which always fails).

6 files changed, 245 insertions, 53 deletions

diff --git a/src/ir/gc-type-utils.h b/src/ir/gc-type-utils.h
index 53cc6feb2..7c530e179 100644
--- a/src/ir/gc-type-utils.h
+++ b/src/ir/gc-type-utils.h
@@ -21,6 +21,10 @@
 
 namespace wasm::GCTypeUtils {
 
+inline bool isUninhabitable(Type type) {
+  return type.isNonNullable() && type.getHeapType().isBottom();
+}
+
 // Helper code to evaluate a reference at compile time and check if it is of a
 // certain kind. Various wasm instructions check if something is a function or
 // data etc., and that code is shared here.
@@ -37,6 +41,10 @@ enum EvaluationResult {
   // The cast will only succeed if the input is a null, or is not
   SuccessOnlyIfNull,
   SuccessOnlyIfNonNull,
+  // The cast will not even be reached. This can occur if the value being cast
+  // has unreachable type, or is uninhabitable (like a non-nullable bottom
+  // type).
+  Unreachable,
 };
 
 inline EvaluationResult flipEvaluationResult(EvaluationResult result) {
@@ -51,6 +59,8 @@ inline EvaluationResult flipEvaluationResult(EvaluationResult result) {
       return SuccessOnlyIfNonNull;
     case SuccessOnlyIfNonNull:
       return SuccessOnlyIfNull;
+    case Unreachable:
+      return Unreachable;
   }
   WASM_UNREACHABLE("unexpected result");
 }
@@ -59,19 +69,58 @@ inline EvaluationResult flipEvaluationResult(EvaluationResult result) {
 // what we know about the result.
 inline EvaluationResult evaluateCastCheck(Type refType, Type castType) {
   if (!refType.isRef() || !castType.isRef()) {
-    // Unreachable etc. are meaningless situations in which we can inform the
-    // caller about nothing useful.
+    if (refType == Type::unreachable) {
+      return Unreachable;
+    }
+    // If the cast type is unreachable, we can't tell - perhaps this is a br
+    // instruction of some kind, that has unreachable type normally.
     return Unknown;
   }
 
-  if (Type::isSubType(refType, castType)) {
-    return Success;
+  if (isUninhabitable(refType)) {
+    // No value can appear in the ref, so the cast cannot be reached.
+    return Unreachable;
   }
 
   auto refHeapType = refType.getHeapType();
-  auto castHeapType = castType.getHeapType();
 
+  if (castType.isNonNullable() && refHeapType.isBottom()) {
+    // Non-null references to bottom types do not exist, so there's no value
+    // that could make the cast succeed.
+    //
+    // Note that there is an interesting corner case that is relevant here: if
+    // the ref type is uninhabitable, say (ref nofunc), and the cast type is
+    // non-nullable, say (ref func), then we have two contradictory rules that
+    // seem to apply:
+    //
+    //  * A non-nullable cast of a bottom type must fail.
+    //  * A cast of a subtype must succeed.
+    //
+    // In practice the uninhabitable type means that the cast is not even
+    // reached, which is why there is no contradiction here. To avoid ambiguity,
+    // we already checked for uninhabitability earlier, and returned
+    // Unreachable.
+    return Failure;
+  }
+
+  auto castHeapType = castType.getHeapType();
   auto refIsHeapSubType = HeapType::isSubType(refHeapType, castHeapType);
+
+  if (refIsHeapSubType) {
+    // The heap type is a subtype. All we need is for nullability to work out as
+    // well, and then the cast must succeed.
+    if (castType.isNullable() || refType.isNonNullable()) {
+      return Success;
+    }
+
+    // If the heap type part of the cast is compatible but the cast as a whole
+    // is not, we must have a nullable input ref that we are casting to a
+    // non-nullable type.
+    assert(refType.isNullable());
+    assert(castType.isNonNullable());
+    return SuccessOnlyIfNonNull;
+  }
+
   auto castIsHeapSubType = HeapType::isSubType(castHeapType, refHeapType);
   bool heapTypesCompatible = refIsHeapSubType || castIsHeapSubType;
 
@@ -79,6 +128,8 @@ inline EvaluationResult evaluateCastCheck(Type refType, Type castType) {
     // If the heap types are incompatible or if it is impossible to have a
     // non-null reference to the target heap type, then the only way the cast
     // can succeed is if it allows nulls and the input is null.
+    //
+    // Note that this handles uninhabitability of the cast type.
     if (refType.isNonNullable() || castType.isNonNullable()) {
       return Failure;
     }
@@ -88,20 +139,6 @@ inline EvaluationResult evaluateCastCheck(Type refType, Type castType) {
     return SuccessOnlyIfNull;
   }
 
-  // If the heap type part of the cast is compatible but the cast as a whole is
-  // not, we must have a nullable input ref that we are casting to a
-  // non-nullable type.
-  if (refIsHeapSubType) {
-    assert(refType.isNullable());
-    assert(castType.isNonNullable());
-    if (refHeapType.isBottom()) {
-      // Non-null references to bottom types do not exist, so there's no value
-      // that could make the cast succeed.
-      return Failure;
-    }
-    return SuccessOnlyIfNonNull;
-  }
-
   return Unknown;
 }
 
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index a546930c6..70df652b8 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -2018,6 +2018,22 @@ struct OptimizeInstructions
           // the value, though.
           if (ref->type.isNull()) {
             // We can materialize the resulting null value directly.
+            //
+            // The type must be nullable for us to do that, which it normally
+            // would be, aside from the interesting corner case of
+            // uninhabitable types:
+            //
+            //  (ref.cast func
+            //    (block (result (ref nofunc))
+            //      (unreachable)
+            //    )
+            //  )
+            //
+            // (ref nofunc) is a subtype of (ref func), so the cast might seem
+            // to be successful, but since the input is uninhabitable we won't
+            // even reach the cast. Such casts will be evaluated as
+            // Unreachable, so we'll not hit this assertion.
+            assert(curr->type.isNullable());
             replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref),
                                                 builder.makeRefNull(nullType)));
             return;
@@ -2030,8 +2046,10 @@ struct OptimizeInstructions
             builder.makeSequence(builder.makeDrop(curr->ref),
                                  builder.makeLocalGet(scratch, ref->type)));
           return;
-        } else if (result == GCTypeUtils::Failure) {
-          // This cast cannot succeed, so it will trap.
+        } else if (result == GCTypeUtils::Failure ||
+                   result == GCTypeUtils::Unreachable) {
+          // This cast cannot succeed, or it cannot even be reached, so we can
+          // trap.
           // Make sure to emit a block with the same type as us; leave updating
           // types for other passes.
           replaceCurrent(builder.makeBlock(
@@ -2142,14 +2160,6 @@ struct OptimizeInstructions
 
     Builder builder(*getModule());
 
-    if (curr->ref->type.isNull()) {
-      // The input is null, so we know whether this will succeed or fail.
-      int32_t result = curr->castType.isNullable() ? 1 : 0;
-      replaceCurrent(builder.makeBlock(
-        {builder.makeDrop(curr->ref), builder.makeConst(int32_t(result))}));
-      return;
-    }
-
     // Parallel to the code in visitRefCast
     switch (GCTypeUtils::evaluateCastCheck(curr->ref->type, curr->castType)) {
       case GCTypeUtils::Unknown:
@@ -2158,6 +2168,10 @@ struct OptimizeInstructions
         replaceCurrent(builder.makeBlock(
           {builder.makeDrop(curr->ref), builder.makeConst(int32_t(1))}));
         break;
+      case GCTypeUtils::Unreachable:
+        replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref),
+                                            builder.makeUnreachable()));
+        break;
       case GCTypeUtils::Failure:
         replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref),
                                             builder.makeConst(int32_t(0))));
diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp
index a7011abe0..197126f5e 100644
--- a/src/passes/RemoveUnusedBrs.cpp
+++ b/src/passes/RemoveUnusedBrs.cpp
@@ -754,9 +754,11 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
           replaceCurrent(
             Builder(*getModule()).makeBreak(curr->name, curr->ref));
           worked = true;
-        } else if (result == GCTypeUtils::Failure) {
+        } else if (result == GCTypeUtils::Failure ||
+                   result == GCTypeUtils::Unreachable) {
           // The cast fails, so the branch is never taken, and the value just
-          // flows through.
+          // flows through. Or, the cast cannot even be reached, so it does not
+          // matter what we do, and we can handle it as a failure.
           replaceCurrent(curr->ref);
           worked = true;
         }
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 0e6d41ec9..6ce299822 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -15,6 +15,7 @@
  */
 
 #include "tools/fuzzing.h"
+#include "ir/gc-type-utils.h"
 #include "ir/module-utils.h"
 #include "ir/subtypes.h"
 #include "ir/type-updating.h"
@@ -3635,10 +3636,6 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
   return type;
 }
 
-static bool isUninhabitable(Type type) {
-  return type.isNonNullable() && type.getHeapType().isBottom();
-}
-
 Type TranslateToFuzzReader::getSubType(Type type) {
   if (type.isTuple()) {
     std::vector<Type> types;
@@ -3653,7 +3650,8 @@ Type TranslateToFuzzReader::getSubType(Type type) {
     // We don't want to emit lots of uninhabitable types like (ref none), so
     // avoid them with high probability. Specifically, if the original type was
     // inhabitable then return that; avoid adding more uninhabitability.
-    if (isUninhabitable(subType) && !isUninhabitable(type) && !oneIn(20)) {
+    if (GCTypeUtils::isUninhabitable(subType) &&
+        !GCTypeUtils::isUninhabitable(type) && !oneIn(20)) {
       return type;
     }
     return subType;
@@ -3691,7 +3689,7 @@ Type TranslateToFuzzReader::getSuperType(Type type) {
   auto superType = Type(heapType, nullability);
   // As with getSubType, we want to avoid returning an uninhabitable type where
   // possible. Here all we can do is flip the super's nullability to nullable.
-  if (isUninhabitable(superType)) {
+  if (GCTypeUtils::isUninhabitable(superType)) {
     superType = Type(heapType, Nullable);
   }
   return superType;
diff --git a/test/lit/passes/optimize-instructions-gc-tnh.wast b/test/lit/passes/optimize-instructions-gc-tnh.wast
index 846ae4283..3c7494bac 100644
--- a/test/lit/passes/optimize-instructions-gc-tnh.wast
+++ b/test/lit/passes/optimize-instructions-gc-tnh.wast
@@ -556,17 +556,15 @@
   )
 
   ;; TNH:      (func $cast-if-null (type $ref|none|_=>_ref|$struct|) (param $x (ref none)) (result (ref $struct))
-  ;; TNH-NEXT:  (block ;; (replaces something unreachable we can't emit)
-  ;; TNH-NEXT:   (drop
-  ;; TNH-NEXT:    (block
-  ;; TNH-NEXT:     (drop
-  ;; TNH-NEXT:      (i32.const 1)
-  ;; TNH-NEXT:     )
-  ;; TNH-NEXT:     (unreachable)
+  ;; TNH-NEXT:  (drop
+  ;; TNH-NEXT:   (block
+  ;; TNH-NEXT:    (drop
+  ;; TNH-NEXT:     (i32.const 1)
   ;; TNH-NEXT:    )
+  ;; TNH-NEXT:    (unreachable)
   ;; TNH-NEXT:   )
-  ;; TNH-NEXT:   (unreachable)
   ;; TNH-NEXT:  )
+  ;; TNH-NEXT:  (unreachable)
   ;; TNH-NEXT: )
   ;; NO_TNH:      (func $cast-if-null (type $ref|none|_=>_ref|$struct|) (param $x (ref none)) (result (ref $struct))
   ;; NO_TNH-NEXT:  (drop
@@ -592,17 +590,15 @@
   )
 
   ;; TNH:      (func $cast-if-null-flip (type $ref|none|_=>_ref|$struct|) (param $x (ref none)) (result (ref $struct))
-  ;; TNH-NEXT:  (block ;; (replaces something unreachable we can't emit)
-  ;; TNH-NEXT:   (drop
-  ;; TNH-NEXT:    (block
-  ;; TNH-NEXT:     (drop
-  ;; TNH-NEXT:      (i32.const 1)
-  ;; TNH-NEXT:     )
-  ;; TNH-NEXT:     (unreachable)
+  ;; TNH-NEXT:  (drop
+  ;; TNH-NEXT:   (block
+  ;; TNH-NEXT:    (drop
+  ;; TNH-NEXT:     (i32.const 1)
   ;; TNH-NEXT:    )
+  ;; TNH-NEXT:    (unreachable)
   ;; TNH-NEXT:   )
-  ;; TNH-NEXT:   (unreachable)
   ;; TNH-NEXT:  )
+  ;; TNH-NEXT:  (unreachable)
   ;; TNH-NEXT: )
   ;; NO_TNH:      (func $cast-if-null-flip (type $ref|none|_=>_ref|$struct|) (param $x (ref none)) (result (ref $struct))
   ;; NO_TNH-NEXT:  (drop
diff --git a/test/lit/passes/optimize-instructions-gc.wast b/test/lit/passes/optimize-instructions-gc.wast
index 593de7dec..0f35cc238 100644
--- a/test/lit/passes/optimize-instructions-gc.wast
+++ b/test/lit/passes/optimize-instructions-gc.wast
@@ -3342,4 +3342,149 @@
       )
     )
   )
+
+  ;; CHECK:      (func $non-null-bottom-ref (type $none_=>_ref|func|) (result (ref func))
+  ;; CHECK-NEXT:  (local $0 funcref)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.tee $0
+  ;; CHECK-NEXT:    (loop (result (ref nofunc))
+  ;; CHECK-NEXT:     (unreachable)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  ;; NOMNL:      (func $non-null-bottom-ref (type $none_=>_ref|func|) (result (ref func))
+  ;; NOMNL-NEXT:  (local $0 funcref)
+  ;; NOMNL-NEXT:  (drop
+  ;; NOMNL-NEXT:   (local.tee $0
+  ;; NOMNL-NEXT:    (loop (result (ref nofunc))
+  ;; NOMNL-NEXT:     (unreachable)
+  ;; NOMNL-NEXT:    )
+  ;; NOMNL-NEXT:   )
+  ;; NOMNL-NEXT:  )
+  ;; NOMNL-NEXT:  (unreachable)
+  ;; NOMNL-NEXT: )
+  (func $non-null-bottom-ref (result (ref func))
+    (local $0 (ref null func))
+    ;; The reference is uninhabitable, a non-null bottom type. The cast is not
+    ;; even reached, but we need to be careful: The tee makes this a corner case
+    ;; since it makes the type nullable again, so if we thought the cast would
+    ;; succeed, and replaced the cast with its child, we'd fail to validate.
+    ;; Instead, since the cast fails, we can replace it with an unreachable
+    ;; (after the dropped child).
+    (ref.cast func
+      (local.tee $0
+        (loop (result (ref nofunc))
+          (unreachable)
+        )
+      )
+    )
+  )
+
+  ;; CHECK:      (func $non-null-bottom-cast (type $none_=>_ref|nofunc|) (result (ref nofunc))
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (ref.func $non-null-bottom-cast)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  ;; NOMNL:      (func $non-null-bottom-cast (type $none_=>_ref|nofunc|) (result (ref nofunc))
+  ;; NOMNL-NEXT:  (drop
+  ;; NOMNL-NEXT:   (ref.func $non-null-bottom-cast)
+  ;; NOMNL-NEXT:  )
+  ;; NOMNL-NEXT:  (unreachable)
+  ;; NOMNL-NEXT: )
+  (func $non-null-bottom-cast (result (ref nofunc))
+    ;; As above, but now the cast is uninhabitable.
+    (ref.cast nofunc
+      (ref.func $non-null-bottom-cast)
+    )
+  )
+
+  ;; CHECK:      (func $non-null-bottom-ref-test (type $none_=>_i32) (result i32)
+  ;; CHECK-NEXT:  (local $0 funcref)
+  ;; CHECK-NEXT:  (i32.eqz
+  ;; CHECK-NEXT:   (ref.is_null
+  ;; CHECK-NEXT:    (local.tee $0
+  ;; CHECK-NEXT:     (loop (result (ref nofunc))
+  ;; CHECK-NEXT:      (unreachable)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  ;; NOMNL:      (func $non-null-bottom-ref-test (type $none_=>_i32) (result i32)
+  ;; NOMNL-NEXT:  (local $0 funcref)
+  ;; NOMNL-NEXT:  (i32.eqz
+  ;; NOMNL-NEXT:   (ref.is_null
+  ;; NOMNL-NEXT:    (local.tee $0
+  ;; NOMNL-NEXT:     (loop (result (ref nofunc))
+  ;; NOMNL-NEXT:      (unreachable)
+  ;; NOMNL-NEXT:     )
+  ;; NOMNL-NEXT:    )
+  ;; NOMNL-NEXT:   )
+  ;; NOMNL-NEXT:  )
+  ;; NOMNL-NEXT: )
+  (func $non-null-bottom-ref-test (result i32)
+    (local $0 (ref null func))
+    ;; As above, but ref.test instead of cast. This is ok - we can turn the test
+    ;; into a ref.is_null. TODO: if ref.test looked into intermediate casts
+    ;; before it, it could do better.
+    (ref.test func
+      (local.tee $0
+        (loop (result (ref nofunc))
+          (unreachable)
+        )
+      )
+    )
+  )
+
+  ;; CHECK:      (func $non-null-bottom-ref-test-notee (type $none_=>_i32) (result i32)
+  ;; CHECK-NEXT:  (local $0 funcref)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (loop
+  ;; CHECK-NEXT:    (unreachable)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  ;; NOMNL:      (func $non-null-bottom-ref-test-notee (type $none_=>_i32) (result i32)
+  ;; NOMNL-NEXT:  (local $0 funcref)
+  ;; NOMNL-NEXT:  (drop
+  ;; NOMNL-NEXT:   (loop
+  ;; NOMNL-NEXT:    (unreachable)
+  ;; NOMNL-NEXT:   )
+  ;; NOMNL-NEXT:  )
+  ;; NOMNL-NEXT:  (unreachable)
+  ;; NOMNL-NEXT: )
+  (func $non-null-bottom-ref-test-notee (result i32)
+    (local $0 (ref null func))
+    ;; As above, but without an intermediate local.tee. Now ref.test will see
+    ;; that it is unreachable, as the input is uninhabitable.
+    (ref.test func
+      (loop (result (ref nofunc))
+        (unreachable)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $non-null-bottom-test (type $none_=>_i32) (result i32)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (ref.func $non-null-bottom-cast)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT: )
+  ;; NOMNL:      (func $non-null-bottom-test (type $none_=>_i32) (result i32)
+  ;; NOMNL-NEXT:  (drop
+  ;; NOMNL-NEXT:   (ref.func $non-null-bottom-cast)
+  ;; NOMNL-NEXT:  )
+  ;; NOMNL-NEXT:  (i32.const 0)
+  ;; NOMNL-NEXT: )
+  (func $non-null-bottom-test (result i32)
+    ;; As above, but now the cast type is uninhabitable, and also use ref.test.
+    ;; This cast cannot succeed, so return 0.
+    (ref.test nofunc
+      (ref.func $non-null-bottom-cast)
+    )
+  )
 )