diff options
| -rw-r--r-- | src/ir/properties.h | 68 | ||||
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 306 | ||||
| -rw-r--r-- | src/wasm-type.h | 2 | ||||
| -rw-r--r-- | src/wasm/wasm-type.cpp | 25 | ||||
| -rw-r--r-- | test/lit/passes/optimize-instructions-call_ref.wast | 13 | ||||
| -rw-r--r-- | test/lit/passes/optimize-instructions-gc-iit.wast | 4 | ||||
| -rw-r--r-- | test/lit/passes/optimize-instructions-gc.wast | 572 |
7 files changed, 806 insertions, 184 deletions
diff --git a/src/ir/properties.h b/src/ir/properties.h index d47cf774b..7f247f72f 100644 --- a/src/ir/properties.h +++ b/src/ir/properties.h @@ -362,6 +362,74 @@ inline Expression* getFallthrough( } } +// Look at all the intermediate fallthrough expressions and return the most +// precise type we know this value will have. +inline Type getFallthroughType(Expression* curr, + const PassOptions& passOptions, + Module& module) { + Type type = curr->type; + if (!type.isRef()) { + // Only reference types can be improved (excepting improvements to + // unreachable, which we leave to refinalization). + // TODO: Handle tuples if that ever becomes important. + return type; + } + while (1) { + auto* next = getImmediateFallthrough(curr, passOptions, module); + if (next == curr) { + return type; + } + type = Type::getGreatestLowerBound(type, next->type); + if (type == Type::unreachable) { + return type; + } + curr = next; + } +} + +// Find the best fallthrough value ordered by refinement of heaptype, refinement +// of nullability, and closeness to the current expression. The type of the +// expression this function returns may be nullable even if `getFallthroughType` +// is non-nullable, but the heap type will definitely match. +inline Expression** getMostRefinedFallthrough(Expression** currp, + const PassOptions& passOptions, + Module& module) { + Expression* curr = *currp; + if (!curr->type.isRef()) { + return currp; + } + auto bestType = curr->type.getHeapType(); + auto bestNullability = curr->type.getNullability(); + auto** bestp = currp; + while (1) { + curr = *currp; + auto** nextp = + Properties::getImmediateFallthroughPtr(currp, passOptions, module); + auto* next = *nextp; + if (next == curr || next->type == Type::unreachable) { + return bestp; + } + assert(next->type.isRef()); + auto nextType = next->type.getHeapType(); + auto nextNullability = next->type.getNullability(); + if (nextType == bestType) { + // Heap types match: refine nullability if possible. + if (bestNullability == Nullable && nextNullability == NonNullable) { + bestp = nextp; + bestNullability = NonNullable; + } + } else { + // Refine heap type if possible, resetting nullability. + if (HeapType::isSubType(nextType, bestType)) { + bestp = nextp; + bestNullability = nextNullability; + bestType = nextType; + } + } + currp = nextp; + } +} + inline Index getNumChildren(Expression* curr) { Index ret = 0; diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 965f8b2d8..f15bac23d 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -1995,39 +1995,64 @@ struct OptimizeInstructions return; } - // Check whether the cast will definitely fail (or succeed). Look not just - // at the fallthrough but all intermediatary fallthrough values as well, as - // if any of them has a type that cannot be cast to us, then we will trap, - // e.g. - // - // (ref.cast $struct-A - // (ref.cast $struct-B - // (ref.cast $array - // (local.get $x) - // - // The fallthrough is the local.get, but the array cast in the middle - // proves a trap must happen. Builder builder(*getModule()); - auto nullType = curr->type.getHeapType().getBottom(); - { - auto** refp = &curr->ref; - while (1) { - auto* ref = *refp; - auto result = GCTypeUtils::evaluateCastCheck(ref->type, curr->type); + // Look at all the fallthrough values to get the most precise possible type + // of the value we are casting. local.tee, br_if, and blocks can all "lose" + // type information, so looking at all the fallthrough values can give us a + // more precise type than is stored in the IR. + Type refType = + Properties::getFallthroughType(curr->ref, getPassOptions(), *getModule()); + + // As a first step, we can tighten up the cast type to be the greatest lower + // bound of the original cast type and the type we know the cast value to + // have. We know any less specific type either cannot appear or will fail + // the cast anyways. + auto glb = Type::getGreatestLowerBound(curr->type, refType); + if (glb != Type::unreachable && glb != curr->type) { + curr->type = glb; + refinalize = true; + // Call replaceCurrent() to make us re-optimize this node, as we may have + // just unlocked further opportunities. (We could just continue down to + // the rest, but we'd need to do more work to make sure all the local + // state in this function is in sync which this change; it's easier to + // just do another clean pass on this node.) + replaceCurrent(curr); + return; + } - if (result == GCTypeUtils::Success) { - // The cast will succeed. This can only happen if the ref is a subtype - // of the cast instruction, which means we can replace the cast with - // the ref. - assert(Type::isSubType(ref->type, curr->type)); - if (curr->type != ref->type) { - refinalize = true; - } - // If there were no intermediate expressions, we can just skip the - // cast. + // Given what we know about the type of the value, determine what we know + // about the results of the cast and optimize accordingly. + switch (GCTypeUtils::evaluateCastCheck(refType, curr->type)) { + case GCTypeUtils::Unknown: + // The cast may or may not succeed, so we cannot optimize. + break; + case GCTypeUtils::Success: + case GCTypeUtils::SuccessOnlyIfNonNull: { + // We know the cast will succeed, or at most requires a null check, so + // we can try to optimize it out. Find the best-typed fallthrough value + // to propagate. + auto** refp = Properties::getMostRefinedFallthrough( + &curr->ref, getPassOptions(), *getModule()); + auto* ref = *refp; + assert(ref->type.isRef()); + if (HeapType::isSubType(ref->type.getHeapType(), + curr->type.getHeapType())) { + // We know ref's heap type matches, but the knowledge that the + // nullabillity matches might come from somewhere else or we might not + // know at all whether the nullability matches, so we might need to + // emit a null check. + bool needsNullCheck = ref->type.getNullability() == Nullable && + curr->type.getNullability() == NonNullable; + // If the best value to propagate is the argument to the cast, we can + // simply remove the cast (or downgrade it to a null check if + // necessary). if (ref == curr->ref) { - replaceCurrent(ref); + if (needsNullCheck) { + replaceCurrent(builder.makeRefAs(RefAsNonNull, curr->ref)); + } else { + replaceCurrent(ref); + } return; } // Otherwise we can't just remove the cast and replace it with `ref` @@ -2052,6 +2077,7 @@ struct OptimizeInstructions // even reach the cast. Such casts will be evaluated as // Unreachable, so we'll not hit this assertion. assert(curr->type.isNullable()); + auto nullType = curr->type.getHeapType().getBottom(); replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref), builder.makeRefNull(nullType))); return; @@ -2060,114 +2086,80 @@ struct OptimizeInstructions // it directly. auto scratch = builder.addVar(getFunction(), ref->type); *refp = builder.makeLocalTee(scratch, ref, ref->type); + Expression* get = builder.makeLocalGet(scratch, ref->type); + if (needsNullCheck) { + get = builder.makeRefAs(RefAsNonNull, get); + } replaceCurrent( - builder.makeSequence(builder.makeDrop(curr->ref), - builder.makeLocalGet(scratch, ref->type))); + builder.makeSequence(builder.makeDrop(curr->ref), get)); return; - } 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. + } + // If we get here, then we know that the heap type of the cast input is + // more refined than the heap type of the best available fallthrough + // expression. The only way this can happen is if we were able to infer + // that the input has bottom heap type because it was typed with + // multiple, incompatible heap types in different fallthrough + // expressions. For example: + // + // (ref.cast eqref + // (br_on_cast_fail $l anyref i31ref + // (br_on_cast_fail $l anyref structref + // ...))) + // + // In this case, the cast succeeds because the value must be null, so we + // can fall through to handle that case. + assert(Type::isSubType(refType, ref->type)); + assert(refType.getHeapType().isBottom()); + } + [[fallthrough]]; + case GCTypeUtils::SuccessOnlyIfNull: { + auto nullType = Type(curr->type.getHeapType().getBottom(), Nullable); + // The cast either returns null or traps. In trapsNeverHappen mode + // we know the result, since by assumption it will not trap. + if (getPassOptions().trapsNeverHappen) { replaceCurrent(builder.makeBlock( - {builder.makeDrop(curr->ref), builder.makeUnreachable()}, + {builder.makeDrop(curr->ref), builder.makeRefNull(nullType)}, curr->type)); return; - } else if (result == GCTypeUtils::SuccessOnlyIfNull) { - // If either cast or ref types were non-nullable then the cast could - // never succeed, and we'd have reached |Failure|, above. - assert(curr->type.isNullable() && curr->ref->type.isNullable()); - - // The cast either returns null, or traps. In trapsNeverHappen mode - // we know the result, since it by assumption will not trap. - if (getPassOptions().trapsNeverHappen) { - replaceCurrent(builder.makeBlock( - {builder.makeDrop(curr->ref), builder.makeRefNull(nullType)}, - curr->type)); - return; - } - - // Without trapsNeverHappen we can at least sharpen the type here, if - // it is not already a null type. - auto newType = Type(nullType, Nullable); - if (curr->type != newType) { - curr->type = newType; - // Call replaceCurrent() to make us re-optimize this node, as we - // may have just unlocked further opportunities. (We could just - // continue down to the rest, but we'd need to do more work to - // make sure all the local state in this function is in sync - // which this change; it's easier to just do another clean pass - // on this node.) - replaceCurrent(curr); - return; - } - } - - auto** last = refp; - refp = Properties::getImmediateFallthroughPtr( - refp, getPassOptions(), *getModule()); - if (refp == last) { - break; } + // Otherwise, we should have already refined the cast type to cast + // directly to null. + assert(curr->type == nullType); + break; } + case GCTypeUtils::Unreachable: + case GCTypeUtils::Failure: + // 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( + {builder.makeDrop(curr->ref), builder.makeUnreachable()}, + curr->type)); + return; } - // See what we know about the cast result. - // - // Note that we could look at the fallthrough for the ref, but that would - // require additional work to make sure we emit something that validates - // properly. TODO - auto result = GCTypeUtils::evaluateCastCheck(curr->ref->type, curr->type); - - if (result == GCTypeUtils::Success) { - replaceCurrent(curr->ref); - return; - } else if (result == GCTypeUtils::SuccessOnlyIfNonNull) { - // All we need to do is check for a null here. - // - // As above, we must refinalize as we may now be emitting a more refined - // type (specifically a more refined heap type). - replaceCurrent(builder.makeRefAs(RefAsNonNull, curr->ref)); - return; - } + // If we got past the optimizations above, it must be the case that we + // cannot tell from the static types whether the cast will succeed or not, + // which means we must have a proper down cast. + assert(Type::isSubType(curr->type, curr->ref->type)); if (auto* child = curr->ref->dynCast<RefCast>()) { - // Repeated casts can be removed, leaving just the most demanding of - // them. Note that earlier we already checked for the cast of the ref's - // type being more refined, so all we need to handle is the opposite, that - // is, something like this: - // - // (ref.cast $B - // (ref.cast $A - // - // where $B is a subtype of $A. We don't need to cast to $A here; we can - // just cast all the way to $B immediately. To check this, see if the - // parent's type would succeed if cast by the child's; if it must then the - // child's is redundant. - auto result = GCTypeUtils::evaluateCastCheck(curr->type, child->type); - if (result == GCTypeUtils::Success) { - curr->ref = child->ref; - return; - } else if (result == GCTypeUtils::SuccessOnlyIfNonNull) { - // Similar to above, but we must also trap on null. - curr->ref = child->ref; - curr->type = Type(curr->type.getHeapType(), NonNullable); - return; - } + // Repeated casts can be removed, leaving just the most demanding of them. + // Since we know the current cast is a downcast, it must be strictly + // stronger than its child cast and we can remove the child cast entirely. + curr->ref = child->ref; + return; } - // ref.cast can be combined with ref.as_non_null, + // Similarly, ref.cast can be combined with ref.as_non_null. // // (ref.cast null (ref.as_non_null ..)) // => // (ref.cast ..) // - if (auto* as = curr->ref->dynCast<RefAs>()) { - if (as->op == RefAsNonNull) { - curr->ref = as->value; - curr->type = Type(curr->type.getHeapType(), NonNullable); - } + if (auto* as = curr->ref->dynCast<RefAs>(); as && as->op == RefAsNonNull) { + curr->ref = as->value; + curr->type = Type(curr->type.getHeapType(), NonNullable); } } @@ -2180,47 +2172,45 @@ struct OptimizeInstructions // Parallel to the code in visitRefCast: we look not just at the final type // we are given, but at fallthrough values as well. - auto* ref = curr->ref; - while (1) { - switch (GCTypeUtils::evaluateCastCheck(ref->type, curr->castType)) { - case GCTypeUtils::Unknown: - break; - case GCTypeUtils::Success: - replaceCurrent(builder.makeBlock( - {builder.makeDrop(curr->ref), builder.makeConst(int32_t(1))})); - return; - case GCTypeUtils::Unreachable: - // Make sure to emit a block with the same type as us, to avoid other - // code in this pass needing to handle unexpected unreachable code - // (which is only properly propagated at the end of this pass when we - // refinalize). - replaceCurrent(builder.makeBlock( - {builder.makeDrop(curr->ref), builder.makeUnreachable()}, - Type::i32)); - return; - case GCTypeUtils::Failure: - replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref), - builder.makeConst(int32_t(0)))); - return; - case GCTypeUtils::SuccessOnlyIfNull: - replaceCurrent(builder.makeRefIsNull(curr->ref)); - return; - case GCTypeUtils::SuccessOnlyIfNonNull: - // This adds an EqZ, but code size does not regress since ref.test - // also encodes a type, and ref.is_null does not. The EqZ may also add - // some work, but a cast is likely more expensive than a null check + - // a fast int operation. - replaceCurrent( - builder.makeUnary(EqZInt32, builder.makeRefIsNull(curr->ref))); - return; - } + Type refType = + Properties::getFallthroughType(curr->ref, getPassOptions(), *getModule()); + + // Improve the cast type as much as we can without changing the results. + auto glb = Type::getGreatestLowerBound(curr->castType, refType); + if (glb != Type::unreachable && glb != curr->castType) { + curr->castType = glb; + } - auto* fallthrough = Properties::getImmediateFallthrough( - ref, getPassOptions(), *getModule()); - if (fallthrough == ref) { + switch (GCTypeUtils::evaluateCastCheck(refType, curr->castType)) { + case GCTypeUtils::Unknown: + break; + case GCTypeUtils::Success: + replaceCurrent(builder.makeBlock( + {builder.makeDrop(curr->ref), builder.makeConst(int32_t(1))})); + return; + case GCTypeUtils::Unreachable: + // Make sure to emit a block with the same type as us, to avoid other + // code in this pass needing to handle unexpected unreachable code + // (which is only properly propagated at the end of this pass when we + // refinalize). + replaceCurrent(builder.makeBlock( + {builder.makeDrop(curr->ref), builder.makeUnreachable()}, Type::i32)); + return; + case GCTypeUtils::Failure: + replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref), + builder.makeConst(int32_t(0)))); + return; + case GCTypeUtils::SuccessOnlyIfNull: + replaceCurrent(builder.makeRefIsNull(curr->ref)); + return; + case GCTypeUtils::SuccessOnlyIfNonNull: + // This adds an EqZ, but code size does not regress since ref.test + // also encodes a type, and ref.is_null does not. The EqZ may also add + // some work, but a cast is likely more expensive than a null check + + // a fast int operation. + replaceCurrent( + builder.makeUnary(EqZInt32, builder.makeRefIsNull(curr->ref))); return; - } - ref = fallthrough; } } diff --git a/src/wasm-type.h b/src/wasm-type.h index 580c198e3..0d41d0cc2 100644 --- a/src/wasm-type.h +++ b/src/wasm-type.h @@ -264,6 +264,8 @@ public: return lub; } + static Type getGreatestLowerBound(Type a, Type b); + // Helper allowing the value of `print(...)` to be sent to an ostream. Stores // a `TypeID` because `Type` is incomplete at this point and using a reference // makes it less convenient to use. diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp index 114a83bd6..fd9838b31 100644 --- a/src/wasm/wasm-type.cpp +++ b/src/wasm/wasm-type.cpp @@ -1035,6 +1035,31 @@ Type Type::getLeastUpperBound(Type a, Type b) { WASM_UNREACHABLE("unexpected type"); } +Type Type::getGreatestLowerBound(Type a, Type b) { + if (a == b) { + return a; + } + if (!a.isRef() || !b.isRef()) { + return Type::unreachable; + } + auto heapA = a.getHeapType(); + auto heapB = b.getHeapType(); + if (heapA.getBottom() != heapB.getBottom()) { + return Type::unreachable; + } + auto nullability = + (a.isNonNullable() || b.isNonNullable()) ? NonNullable : Nullable; + HeapType heapType; + if (HeapType::isSubType(heapA, heapB)) { + heapType = heapA; + } else if (HeapType::isSubType(heapB, heapA)) { + heapType = heapB; + } else { + heapType = heapA.getBottom(); + } + return Type(heapType, nullability); +} + size_t Type::size() const { if (isTuple()) { return getTypeInfo(*this)->tuple.size(); diff --git a/test/lit/passes/optimize-instructions-call_ref.wast b/test/lit/passes/optimize-instructions-call_ref.wast index ed849c7d8..a085e1ed4 100644 --- a/test/lit/passes/optimize-instructions-call_ref.wast +++ b/test/lit/passes/optimize-instructions-call_ref.wast @@ -158,13 +158,16 @@ ) ;; CHECK: (func $fallthrough-bad-type (type $none_=>_i32) (result i32) - ;; CHECK-NEXT: (call_ref $none_=>_i32 - ;; CHECK-NEXT: (block (result (ref $none_=>_i32)) - ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (ref.func $return-nothing) + ;; CHECK-NEXT: (block ;; (replaces something unreachable we can't emit) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.func $return-nothing) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) (func $fallthrough-bad-type (result i32) diff --git a/test/lit/passes/optimize-instructions-gc-iit.wast b/test/lit/passes/optimize-instructions-gc-iit.wast index 4271d3de7..b3d5a2559 100644 --- a/test/lit/passes/optimize-instructions-gc-iit.wast +++ b/test/lit/passes/optimize-instructions-gc-iit.wast @@ -39,7 +39,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $other)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.get $child) ;; CHECK-NEXT: ) @@ -60,7 +60,7 @@ ;; TNH-NEXT: ) ;; TNH-NEXT: ) ;; TNH-NEXT: (drop - ;; TNH-NEXT: (block (result (ref $other)) + ;; TNH-NEXT: (block ;; TNH-NEXT: (drop ;; TNH-NEXT: (local.get $child) ;; TNH-NEXT: ) diff --git a/test/lit/passes/optimize-instructions-gc.wast b/test/lit/passes/optimize-instructions-gc.wast index 9f33c55a3..4882bae9f 100644 --- a/test/lit/passes/optimize-instructions-gc.wast +++ b/test/lit/passes/optimize-instructions-gc.wast @@ -584,7 +584,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast i31 ;; CHECK-NEXT: (local.get $x) @@ -1088,7 +1088,7 @@ ;; CHECK: (func $incompatible-cast-of-non-null (type $ref|$struct|_=>_none) (param $struct (ref $struct)) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $array)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.get $struct) ;; CHECK-NEXT: ) @@ -1283,6 +1283,221 @@ ) ) ) + + ;; CHECK: (func $compatible-test-separate-fallthrough (type $eqref_=>_i32) (param $eqref eqref) (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.cast null i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + (func $compatible-test-separate-fallthrough (param $eqref eqref) (result i32) + (ref.test i31 + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is non-nullable + (ref.as_non_null + (block (result eqref) + ;; Prove that the value is an i31 + (ref.cast null i31 + (local.get $eqref) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $improvable-test-separate-fallthrough (type $eqref_=>_i32) (param $eqref eqref) (result i32) + ;; CHECK-NEXT: (ref.test i31 + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $improvable-test-separate-fallthrough (param $eqref eqref) (result i32) + ;; There is no need to admit null here, but we don't know whether we have an i31. + (ref.test null i31 + (block (result eqref) + ;; Prove that the value is non-nullable + (ref.as_non_null + (local.get $eqref) + ) + ) + ) + ) + + ;; CHECK: (func $incompatible-test-separate-fallthrough (type $eqref_=>_i32) (param $eqref eqref) (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.cast null i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + (func $incompatible-test-separate-fallthrough (param $eqref eqref) (result i32) + (ref.test null struct + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is non-nullable + (ref.as_non_null + (block (result eqref) + ;; Prove that the value is an i31 + (ref.cast null i31 + (local.get $eqref) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $incompatible-test-heap-types-nonnullable (type $anyref_=>_anyref) (param $anyref anyref) (result anyref) + ;; CHECK-NEXT: (block $outer (result anyref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result anyref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref i31ref + ;; CHECK-NEXT: (block (result anyref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref structref + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $incompatible-test-heap-types-nonnullable (param $anyref anyref) (result anyref) + (block $outer (result anyref) + (drop + ;; The value cannot be both i31 and struct, so it must be null and we + ;; can optimize to 0. + (ref.test any + (block (result anyref) + (br_on_cast_fail $outer anyref i31ref + (block (result anyref) + (br_on_cast_fail $outer anyref structref + (local.get $anyref) + ) + ) + ) + ) + ) + ) + (local.get $anyref) + ) + ) + + ;; CHECK: (func $incompatible-test-heap-types-nullable (type $anyref_=>_anyref) (param $anyref anyref) (result anyref) + ;; CHECK-NEXT: (block $outer (result anyref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result anyref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref i31ref + ;; CHECK-NEXT: (block (result anyref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref structref + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $incompatible-test-heap-types-nullable (param $anyref anyref) (result anyref) + (block $outer (result anyref) + (drop + ;; Same as above, but now we allow null, so we optimize to 1. + (ref.test null any + (block (result anyref) + (br_on_cast_fail $outer anyref i31ref + (block (result anyref) + (br_on_cast_fail $outer anyref structref + (local.get $anyref) + ) + ) + ) + ) + ) + ) + (local.get $anyref) + ) + ) + + ;; CHECK: (func $incompatible-test-heap-types-unreachable (type $anyref_=>_anyref) (param $anyref anyref) (result anyref) + ;; CHECK-NEXT: (block $outer (result anyref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result anyref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref (ref i31) + ;; CHECK-NEXT: (block (result anyref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref structref + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $incompatible-test-heap-types-unreachable (param $anyref anyref) (result anyref) + (block $outer (result anyref) + (drop + ;; Same as above, but now we know the value must be non-null and bottom, + ;; so it cannot exist at all. + (ref.test null any + (block (result anyref) + (br_on_cast_fail $outer anyref (ref i31) + (block (result anyref) + (br_on_cast_fail $outer anyref structref + (local.get $anyref) + ) + ) + ) + ) + ) + ) + (local.get $anyref) + ) + ) + ;; CHECK: (func $ref.test-unreachable (type $ref?|$A|_=>_none) (param $A (ref null $A)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.test $A @@ -1694,9 +1909,9 @@ ;; CHECK: (func $ref-cast-static-fallthrough-remaining-impossible (type $ref|eq|_=>_none) (param $x (ref eq)) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $array)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref eq)) + ;; CHECK-NEXT: (block (result (ref $struct)) ;; CHECK-NEXT: (call $ref-cast-static-fallthrough-remaining-impossible ;; CHECK-NEXT: (local.get $x) ;; CHECK-NEXT: ) @@ -1773,7 +1988,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast $array ;; CHECK-NEXT: (local.get $x) @@ -1783,7 +1998,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast $array ;; CHECK-NEXT: (local.get $x) @@ -1793,7 +2008,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast $array ;; CHECK-NEXT: (local.get $x) @@ -2105,7 +2320,7 @@ ;; CHECK: (func $ref-cast-heap-type-incompatible (type $ref?|$B|_ref|$B|_=>_none) (param $null-b (ref null $B)) (param $b (ref $B)) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.get $b) ;; CHECK-NEXT: ) @@ -2113,7 +2328,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.get $null-b) ;; CHECK-NEXT: ) @@ -2121,7 +2336,7 @@ ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (block ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.get $b) ;; CHECK-NEXT: ) @@ -2162,6 +2377,328 @@ ) ) + ;; CHECK: (func $compatible-cast-separate-fallthrough (type $eqref_=>_ref|i31|) (param $eqref eqref) (result (ref i31)) + ;; CHECK-NEXT: (local $1 i31ref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (local.tee $1 + ;; CHECK-NEXT: (ref.cast null i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $compatible-cast-separate-fallthrough (param $eqref eqref) (result (ref i31)) + ;; This cast will succeed even though no individual fallthrough value is sufficiently refined. + (ref.cast i31 + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is non-nullable + (ref.as_non_null + (block (result eqref) + ;; Prove that the value is an i31 + (ref.cast null i31 + (local.get $eqref) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $compatible-cast-fallthrough-null-check (type $eqref_=>_ref|i31|) (param $eqref eqref) (result (ref i31)) + ;; CHECK-NEXT: (local $1 i31ref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (local.tee $1 + ;; CHECK-NEXT: (ref.cast null i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $compatible-cast-fallthrough-null-check (param $eqref eqref) (result (ref i31)) + ;; Similar to above, but now we no longer know whether the value going into + ;; the cast is null or not. + (ref.cast i31 + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is an i31 + (ref.cast null i31 + (local.get $eqref) + ) + ) + ) + ) + ) + + ;; CHECK: (func $compatible-cast-separate-fallthrough-multiple-options-1 (type $eqref_=>_ref|eq|) (param $eqref eqref) (result (ref eq)) + ;; CHECK-NEXT: (local $1 i31ref) + ;; CHECK-NEXT: (block $outer (result (ref eq)) + ;; CHECK-NEXT: (block (result (ref i31)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (local.tee $1 + ;; CHECK-NEXT: (br_on_cast_fail $outer eqref i31ref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.cast null i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $compatible-cast-separate-fallthrough-multiple-options-1 + (param $eqref eqref) (result (ref eq)) + ;; There are multiple "best" values we could tee and propagate. Choose the + ;; shallowest. + (block $outer (result (ref eq)) + (ref.cast i31 + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is an i31 a second time. This one will be + ;; propagated. + (br_on_cast_fail $outer eqref i31ref + (block (result eqref) + ;; Prove that the value is non-nullable + (ref.as_non_null + (block (result eqref) + ;; Prove that the value is an i31 + (ref.cast null i31 + (local.get $eqref) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $compatible-cast-separate-fallthrough-multiple-options-2 (type $eqref_=>_ref|eq|) (param $eqref eqref) (result (ref eq)) + ;; CHECK-NEXT: (local $1 (ref i31)) + ;; CHECK-NEXT: (block $outer (result (ref eq)) + ;; CHECK-NEXT: (block (result (ref i31)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (br_on_cast_fail $outer eqref i31ref + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (block (result eqref) + ;; CHECK-NEXT: (local.tee $1 + ;; CHECK-NEXT: (ref.cast i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $compatible-cast-separate-fallthrough-multiple-options-2 + (param $eqref eqref) (result (ref eq)) + (block $outer (result (ref eq)) + (ref.cast i31 + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is an i31 a second time, but not that it is + ;; non-null at the same time. + (br_on_cast_fail $outer eqref i31ref + (block (result eqref) + ;; Prove that the value is non-nullable but not i31. + (ref.as_non_null + (block (result eqref) + ;; Now this is non-nullable and an exact match, so we + ;; propagate this one. + (ref.cast i31 + (local.get $eqref) + ) + ) + ) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $incompatible-cast-separate-fallthrough (type $eqref_=>_structref) (param $eqref eqref) (result structref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $eqref + ;; CHECK-NEXT: (block (result (ref i31)) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (block (result i31ref) + ;; CHECK-NEXT: (ref.cast null i31 + ;; CHECK-NEXT: (local.get $eqref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $incompatible-cast-separate-fallthrough (param $eqref eqref) (result structref) + (ref.cast null struct + (local.tee $eqref + (block (result eqref) + ;; Prove that the value is non-nullable + (ref.as_non_null + (block (result eqref) + ;; Prove that the value is an i31 + (ref.cast null i31 + (local.get $eqref) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $incompatible-cast-heap-types-nonnullable (type $anyref_=>_anyref) (param $anyref anyref) (result anyref) + ;; CHECK-NEXT: (block $outer (result (ref any)) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i31ref) + ;; CHECK-NEXT: (br_on_cast_fail $outer structref i31ref + ;; CHECK-NEXT: (block (result structref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref structref + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $incompatible-cast-heap-types-nonnullable (param $anyref anyref) (result anyref) + (block $outer (result anyref) + ;; The value cannot be both an i31 and a struct, so it must be null, so + ;; the cast will fail. + (ref.cast struct + (block (result anyref) + (br_on_cast_fail $outer anyref i31ref + (block (result anyref) + (br_on_cast_fail $outer anyref structref + (local.get $anyref) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $incompatible-cast-heap-types-nullable (type $anyref_=>_anyref) (param $anyref anyref) (result anyref) + ;; CHECK-NEXT: (block $outer (result anyref) + ;; CHECK-NEXT: (ref.cast null none + ;; CHECK-NEXT: (block (result i31ref) + ;; CHECK-NEXT: (br_on_cast_fail $outer structref i31ref + ;; CHECK-NEXT: (block (result structref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref structref + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $incompatible-cast-heap-types-nullable (param $anyref anyref) (result anyref) + (block $outer (result anyref) + ;; As above, but now the cast might succeed because we allow null. + (ref.cast null struct + (block (result anyref) + (br_on_cast_fail $outer anyref i31ref + (block (result anyref) + (br_on_cast_fail $outer anyref structref + (local.get $anyref) + ) + ) + ) + ) + ) + ) + ) + + ;; CHECK: (func $incompatible-cast-heap-types-unreachable (type $anyref_=>_anyref) (param $anyref anyref) (result anyref) + ;; CHECK-NEXT: (block $outer (result anyref) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result (ref i31)) + ;; CHECK-NEXT: (br_on_cast_fail $outer structref (ref i31) + ;; CHECK-NEXT: (block (result structref) + ;; CHECK-NEXT: (br_on_cast_fail $outer anyref structref + ;; CHECK-NEXT: (local.get $anyref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $incompatible-cast-heap-types-unreachable (param $anyref anyref) (result anyref) + (block $outer (result anyref) + ;; As above, but now we know the value is not null, so the cast is unreachable. + (ref.cast null struct + (block (result anyref) + (br_on_cast_fail $outer anyref (ref i31) + (block (result anyref) + (br_on_cast_fail $outer anyref structref + (local.get $anyref) + ) + ) + ) + ) + ) + ) + ) + ;; CHECK: (func $as_of_unreachable (type $none_=>_ref|$A|) (result (ref $A)) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) @@ -2368,21 +2905,18 @@ ;; 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: (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: ) (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. + ;; As above, but now it's a ref.test instead of cast. (ref.test func (local.tee $0 (loop (result (ref nofunc)) |