From c0151e99996a7b51d3d135fd5018c69e146b5c02 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 14 Jul 2022 09:32:16 -0700 Subject: [Wasm GC] Check if ref.eq inputs can possibly be the same (#4780) For them to be the same we must have a value that can appear on both sides. If the heap types disallow that, then only null is possible, and if that is impossible as well then the result must be 0. --- src/passes/OptimizeInstructions.cpp | 30 ++- test/lit/passes/optimize-instructions-gc.wast | 294 +++++++++++++++++++++++++- 2 files changed, 317 insertions(+), 7 deletions(-) diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 5f18beb73..9d50275b9 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -1494,11 +1494,35 @@ struct OptimizeInstructions } void visitRefEq(RefEq* curr) { + // The types may prove that the same reference cannot appear on both sides. + auto leftType = curr->left->type; + auto rightType = curr->right->type; + if (leftType == Type::unreachable || rightType == Type::unreachable) { + // Leave this for DCE. + return; + } + auto leftHeapType = leftType.getHeapType(); + auto rightHeapType = rightType.getHeapType(); + auto leftIsHeapSubtype = HeapType::isSubType(leftHeapType, rightHeapType); + auto rightIsHeapSubtype = HeapType::isSubType(rightHeapType, leftHeapType); + if (!leftIsHeapSubtype && !rightIsHeapSubtype && + (leftType.isNonNullable() || rightType.isNonNullable())) { + // The heap types have no intersection, so the only thing that can + // possibly appear on both sides is null, but one of the two is non- + // nullable, which rules that out. So there is no way that the same + // reference can appear on both sides. + auto* result = + Builder(*getModule()).makeConst(Literal::makeZero(Type::i32)); + replaceCurrent(getDroppedChildrenAndAppend( + curr, *getModule(), getPassOptions(), result)); + return; + } + // Equality does not depend on the type, so casts may be removable. // - // This is safe to do first because nothing else here cares about the type, - // and we consume the two input references, so removing a cast could not - // help our parents (see "notes on removing casts"). + // This is safe to do first because nothing farther down cares about the + // type, and we consume the two input references, so removing a cast could + // not help our parents (see "notes on removing casts"). skipCast(curr->left, Type::eqref); skipCast(curr->right, Type::eqref); diff --git a/test/lit/passes/optimize-instructions-gc.wast b/test/lit/passes/optimize-instructions-gc.wast index 643aad5ed..f53237f02 100644 --- a/test/lit/passes/optimize-instructions-gc.wast +++ b/test/lit/passes/optimize-instructions-gc.wast @@ -18,14 +18,12 @@ ;; NOMNL: (type $A (struct_subtype (field i32) data)) (type $A (struct (field i32))) - ;; CHECK: (type $B (struct (field i32) (field i32) (field f32))) - ;; CHECK: (type $array (array (mut i8))) - ;; NOMNL: (type $B (struct_subtype (field i32) (field i32) (field f32) $A)) - ;; NOMNL: (type $array (array_subtype (mut i8) data)) (type $array (array (mut i8))) + ;; CHECK: (type $B (struct (field i32) (field i32) (field f32))) + ;; NOMNL: (type $B (struct_subtype (field i32) (field i32) (field f32) $A)) (type $B (struct_subtype (field i32) (field i32) (field f32) $A)) ;; CHECK: (type $B-child (struct (field i32) (field i32) (field f32) (field i64))) @@ -1690,6 +1688,294 @@ ) ) + ;; CHECK: (func $ref-eq-possible (param $x eqref) (param $y eqref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (ref.cast_static $struct + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.cast_static $array + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; NOMNL: (func $ref-eq-possible (type $eqref_eqref_=>_none) (param $x eqref) (param $y eqref) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.eq + ;; NOMNL-NEXT: (ref.cast_static $struct + ;; NOMNL-NEXT: (local.get $x) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (ref.cast_static $array + ;; NOMNL-NEXT: (local.get $y) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + (func $ref-eq-possible (param $x eqref) (param $y eqref) + ;; These casts are to types that are incompatible. However, it is possible + ;; they are both null, so we cannot optimize here. + (drop + (ref.eq + (ref.cast_static $struct + (local.get $x) + ) + (ref.cast_static $array + (local.get $y) + ) + ) + ) + ) + + ;; CHECK: (func $ref-eq-impossible (param $x eqref) (param $y eqref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $struct + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast_static $array + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.cast_static $struct + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $array + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $struct + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $array + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; NOMNL: (func $ref-eq-impossible (type $eqref_eqref_=>_none) (param $x eqref) (param $y eqref) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (block (result i32) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $struct + ;; NOMNL-NEXT: (local.get $x) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.cast_static $array + ;; NOMNL-NEXT: (local.get $y) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (i32.const 0) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (block (result i32) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.cast_static $struct + ;; NOMNL-NEXT: (local.get $x) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $array + ;; NOMNL-NEXT: (local.get $y) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (i32.const 0) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (block (result i32) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $struct + ;; NOMNL-NEXT: (local.get $x) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $array + ;; NOMNL-NEXT: (local.get $y) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (i32.const 0) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + (func $ref-eq-impossible (param $x eqref) (param $y eqref) + ;; As above but cast one of them to non-null, which proves they cannot be + ;; equal, and the result must be 0. + (drop + (ref.eq + (ref.cast_static $struct + (ref.as_non_null + (local.get $x) + ) + ) + (ref.cast_static $array + (local.get $y) + ) + ) + ) + ;; As above but the cast is on the other one. + (drop + (ref.eq + (ref.cast_static $struct + (local.get $x) + ) + (ref.cast_static $array + (ref.as_non_null + (local.get $y) + ) + ) + ) + ) + ;; As above but the cast is both. + (drop + (ref.eq + (ref.cast_static $struct + (ref.as_non_null + (local.get $x) + ) + ) + (ref.cast_static $array + (ref.as_non_null + (local.get $y) + ) + ) + ) + ) + ) + + ;; CHECK: (func $ref-eq-possible-b (param $x eqref) (param $y eqref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $A + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $B + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $B + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.as_non_null + ;; CHECK-NEXT: (ref.cast_static $A + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; NOMNL: (func $ref-eq-possible-b (type $eqref_eqref_=>_none) (param $x eqref) (param $y eqref) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.eq + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $A + ;; NOMNL-NEXT: (local.get $x) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $B + ;; NOMNL-NEXT: (local.get $y) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (drop + ;; NOMNL-NEXT: (ref.eq + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $B + ;; NOMNL-NEXT: (local.get $x) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: (ref.as_non_null + ;; NOMNL-NEXT: (ref.cast_static $A + ;; NOMNL-NEXT: (local.get $y) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + ;; NOMNL-NEXT: ) + (func $ref-eq-possible-b (param $x eqref) (param $y eqref) + ;; As above but the casts are to things that are compatible, since B is a + ;; subtype of A, so we cannot optimize. + (drop + (ref.eq + (ref.cast_static $A + (ref.as_non_null + (local.get $x) + ) + ) + (ref.cast_static $B + (ref.as_non_null + (local.get $y) + ) + ) + ) + ) + ;; As above but flipped. + (drop + (ref.eq + (ref.cast_static $B + (ref.as_non_null + (local.get $x) + ) + ) + (ref.cast_static $A + (ref.as_non_null + (local.get $y) + ) + ) + ) + ) + ) + ;; CHECK: (func $hoist-LUB-danger (param $x i32) (result i32) ;; CHECK-NEXT: (if (result i32) ;; CHECK-NEXT: (local.get $x) -- cgit v1.2.3