diff options
-rw-r--r-- | src/passes/OptimizeInstructions.cpp | 159 | ||||
-rw-r--r-- | test/lit/passes/optimize-instructions-gc.wast | 310 |
2 files changed, 447 insertions, 22 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 7c14c4172..5613aca11 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -34,6 +34,7 @@ #include <ir/iteration.h> #include <ir/literal-utils.h> #include <ir/load-utils.h> +#include <ir/localize.h> #include <ir/manipulation.h> #include <ir/match.h> #include <ir/ordering.h> @@ -1782,6 +1783,40 @@ struct OptimizeInstructions } } + void visitStructNew(StructNew* curr) { + // If values are provided, but they are all the default, then we can remove + // them (in reachable code). + if (curr->type == Type::unreachable || curr->isWithDefault()) { + return; + } + + auto& passOptions = getPassOptions(); + const auto& fields = curr->type.getHeapType().getStruct().fields; + assert(fields.size() == curr->operands.size()); + + for (Index i = 0; i < fields.size(); i++) { + // The field must be defaultable. + auto type = fields[i].type; + if (!type.isDefaultable()) { + return; + } + + // The field must be written the default value. + auto* value = Properties::getFallthrough( + curr->operands[i], passOptions, *getModule()); + if (!Properties::isSingleConstantExpression(value) || + Properties::getLiteral(value) != Literal::makeZero(type)) { + return; + } + } + + // Success! Drop the children and return a struct.new_with_default. + auto* rep = getDroppedChildrenAndAppend(curr, curr); + curr->operands.clear(); + assert(curr->isWithDefault()); + replaceCurrent(rep); + } + void visitStructGet(StructGet* curr) { skipNonNullCast(curr->ref, curr); trapOnNull(curr, curr->ref); @@ -1943,6 +1978,130 @@ struct OptimizeInstructions return true; } + void visitArrayNew(ArrayNew* curr) { + // If a value is provided, we can optimize in some cases. + if (curr->type == Type::unreachable || curr->isWithDefault()) { + return; + } + + Builder builder(*getModule()); + + // ArrayNew of size 1 is less efficient than ArrayNewFixed with one value + // (the latter avoids a Const, which ends up saving one byte). + // TODO: also look at the case with a fallthrough or effects on the size + if (auto* c = curr->size->dynCast<Const>()) { + if (c->value.geti32() == 1) { + // Optimize to ArrayNewFixed. Note that if the value is the default + // then we may end up optimizing further in visitArrayNewFixed. + replaceCurrent( + builder.makeArrayNewFixed(curr->type.getHeapType(), {curr->init})); + return; + } + } + + // If the type is defaultable then perhaps the value here is the default. + auto type = curr->type.getHeapType().getArray().element.type; + if (!type.isDefaultable()) { + return; + } + + // The value must be the default/zero. + auto& passOptions = getPassOptions(); + auto zero = Literal::makeZero(type); + auto* value = + Properties::getFallthrough(curr->init, passOptions, *getModule()); + if (!Properties::isSingleConstantExpression(value) || + Properties::getLiteral(value) != zero) { + return; + } + + // Success! Drop the init and return an array.new_with_default. + auto* init = curr->init; + curr->init = nullptr; + assert(curr->isWithDefault()); + replaceCurrent(builder.makeSequence(builder.makeDrop(init), curr)); + } + + void visitArrayNewFixed(ArrayNewFixed* curr) { + if (curr->type == Type::unreachable) { + return; + } + + auto size = curr->values.size(); + if (size == 0) { + // TODO: Consider what to do in the trivial case of an empty array: we can + // can use ArrayNew or ArrayNewFixed there. Measure which is best. + return; + } + + auto& passOptions = getPassOptions(); + + // If all the values are equal then we can optimize, either to + // array.new_default (if they are all equal to the default) or array.new (if + // they are all equal to some other value). First, see if they are all + // equal, which we do by comparing in pairs: [0,1], then [1,2], etc. + for (Index i = 0; i < size - 1; i++) { + if (!areConsecutiveInputsEqual(curr->values[i], curr->values[i + 1])) { + return; + } + } + + // Great, they are all equal! + + Builder builder(*getModule()); + + // See if they are equal to a constant, and if that constant is the default. + auto type = curr->type.getHeapType().getArray().element.type; + if (type.isDefaultable()) { + auto* value = + Properties::getFallthrough(curr->values[0], passOptions, *getModule()); + + if (Properties::isSingleConstantExpression(value) && + Properties::getLiteral(value) == Literal::makeZero(type)) { + // They are all equal to the default. Drop the children and return an + // array.new_with_default. + auto* withDefault = builder.makeArrayNew( + curr->type.getHeapType(), builder.makeConst(int32_t(size))); + replaceCurrent(getDroppedChildrenAndAppend(curr, withDefault)); + return; + } + } + + // They are all equal to each other, but not to the default value. If there + // are 2 or more elements here then we can save by using array.new. For + // example, with 2 elements we are doing this: + // + // (array.new_fixed + // (A) + // (A) + // ) + // => + // (array.new + // (A) + // (i32.const 2) ;; get two copies of (A) + // ) + // + // However, with 1, ArrayNewFixed is actually more compact, and we optimize + // ArrayNew to it, above. + if (size == 1) { + return; + } + + // Move children to locals, if we need to keep them around. We are removing + // them all, except from the first, when we remove the array.new_fixed's + // list of children and replace it with a single child + a constant for the + // number of children. + ChildLocalizer localizer( + curr, getFunction(), *getModule(), getPassOptions()); + auto* block = localizer.getChildrenReplacement(); + auto* arrayNew = builder.makeArrayNew(curr->type.getHeapType(), + builder.makeConst(int32_t(size)), + curr->values[0]); + block->list.push_back(arrayNew); + block->finalize(); + replaceCurrent(block); + } + void visitArrayGet(ArrayGet* curr) { skipNonNullCast(curr->ref, curr); trapOnNull(curr, curr->ref); diff --git a/test/lit/passes/optimize-instructions-gc.wast b/test/lit/passes/optimize-instructions-gc.wast index 9a49c3435..d44c7da5d 100644 --- a/test/lit/passes/optimize-instructions-gc.wast +++ b/test/lit/passes/optimize-instructions-gc.wast @@ -12,14 +12,14 @@ (field $i64 (mut i64)) )) + ;; CHECK: (type $array (array (mut i8))) + ;; CHECK: (type $A (sub (struct (field i32)))) (type $A (sub (struct (field i32)))) - ;; CHECK: (type $B (sub $A (struct (field i32) (field i32) (field f32)))) - - ;; CHECK: (type $array (array (mut i8))) (type $array (array (mut i8))) + ;; CHECK: (type $B (sub $A (struct (field i32) (field i32) (field f32)))) (type $B (sub $A (struct (field i32) (field i32) (field f32)))) ;; CHECK: (type $B-child (sub $B (struct (field i32) (field i32) (field f32) (field i64)))) @@ -32,6 +32,10 @@ ;; CHECK: (type $void2 (sub $void (func))) ;; CHECK: (type $C (sub $A (struct (field i32) (field i32) (field f64)))) + + ;; CHECK: (type $struct.ref (struct (field funcref))) + (type $struct.ref (struct (field funcref))) + (type $C (sub $A (struct (field i32) (field i32) (field f64)))) (type $void (sub (func))) @@ -46,7 +50,7 @@ ;; These functions test if an `if` with subtyped arms is correctly folded ;; 1. if its `ifTrue` and `ifFalse` arms are identical (can fold) - ;; CHECK: (func $if-arms-subtype-fold (type $26) (result anyref) + ;; CHECK: (func $if-arms-subtype-fold (type $27) (result anyref) ;; CHECK-NEXT: (ref.null none) ;; CHECK-NEXT: ) (func $if-arms-subtype-fold (result anyref) @@ -61,7 +65,7 @@ ) ) ;; 2. if its `ifTrue` and `ifFalse` arms are not identical (cannot fold) - ;; CHECK: (func $if-arms-subtype-nofold (type $27) (param $i31ref i31ref) (result anyref) + ;; CHECK: (func $if-arms-subtype-nofold (type $28) (param $i31ref i31ref) (result anyref) ;; CHECK-NEXT: (if (result anyref) ;; CHECK-NEXT: (i32.const 0) ;; CHECK-NEXT: (then @@ -304,7 +308,7 @@ ) ) - ;; CHECK: (func $redundant-non-null-casts (type $28) (param $x (ref null $struct)) (param $y (ref null $array)) (param $f (ref null $void)) + ;; CHECK: (func $redundant-non-null-casts (type $29) (param $x (ref null $struct)) (param $y (ref null $array)) (param $f (ref null $void)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.as_non_null ;; CHECK-NEXT: (local.get $x) @@ -391,7 +395,7 @@ ) ) - ;; CHECK: (func $get-eqref (type $29) (result eqref) + ;; CHECK: (func $get-eqref (type $30) (result eqref) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) (func $get-eqref (result eqref) @@ -655,7 +659,7 @@ ) ) - ;; CHECK: (func $flip-tee-of-as-non-null-non-nullable (type $30) (param $x (ref any)) (param $y anyref) + ;; CHECK: (func $flip-tee-of-as-non-null-non-nullable (type $31) (param $x (ref any)) (param $y anyref) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.tee $x ;; CHECK-NEXT: (ref.as_non_null @@ -676,7 +680,7 @@ ) ) ) - ;; CHECK: (func $ternary-identical-arms (type $31) (param $x i32) (param $y (ref null $struct)) (param $z (ref null $struct)) + ;; CHECK: (func $ternary-identical-arms (type $32) (param $x i32) (param $y (ref null $struct)) (param $z (ref null $struct)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.is_null ;; CHECK-NEXT: (if (result (ref null $struct)) @@ -731,7 +735,7 @@ ) ) ) - ;; CHECK: (func $ternary-identical-arms-no-side-effect (type $32) (param $x (ref $struct)) (param $y (ref $struct)) (param $z i32) + ;; CHECK: (func $ternary-identical-arms-no-side-effect (type $33) (param $x (ref $struct)) (param $y (ref $struct)) (param $z i32) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (struct.get_u $struct $i8 ;; CHECK-NEXT: (select (result (ref $struct)) @@ -1083,7 +1087,7 @@ ) ) - ;; CHECK: (func $hoist-LUB-danger (type $33) (param $x i32) (param $b (ref $B)) (param $c (ref $C)) (result i32) + ;; CHECK: (func $hoist-LUB-danger (type $34) (param $x i32) (param $b (ref $B)) (param $c (ref $C)) (result i32) ;; CHECK-NEXT: (if (result i32) ;; CHECK-NEXT: (local.get $x) ;; CHECK-NEXT: (then @@ -1122,7 +1126,7 @@ ) ) - ;; CHECK: (func $incompatible-cast-of-non-null (type $34) (param $struct (ref $struct)) + ;; CHECK: (func $incompatible-cast-of-non-null (type $35) (param $struct (ref $struct)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (block (result (ref none)) ;; CHECK-NEXT: (drop @@ -1534,7 +1538,7 @@ ) ) - ;; CHECK: (func $ref.test-unreachable (type $35) (param $A (ref null $A)) + ;; CHECK: (func $ref.test-unreachable (type $36) (param $A (ref null $A)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.test (ref $A) ;; CHECK-NEXT: (unreachable) @@ -2178,7 +2182,7 @@ ) ) - ;; CHECK: (func $ref-test-static-impossible (type $36) (param $nullable (ref null $array)) (param $non-nullable (ref $array)) + ;; CHECK: (func $ref-test-static-impossible (type $37) (param $nullable (ref null $array)) (param $non-nullable (ref $array)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (block (result i32) ;; CHECK-NEXT: (drop @@ -2258,14 +2262,14 @@ ) ) - ;; CHECK: (func $impossible (type $37) (result (ref none)) + ;; CHECK: (func $impossible (type $38) (result (ref none)) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) (func $impossible (result (ref none)) (unreachable) ) - ;; CHECK: (func $bottom-type-accessors (type $38) (param $bot (ref none)) (param $null nullref) + ;; CHECK: (func $bottom-type-accessors (type $39) (param $bot (ref none)) (param $null nullref) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) @@ -2598,7 +2602,7 @@ ) ) - ;; CHECK: (func $incompatible-cast-separate-fallthrough (type $39) (param $eqref eqref) (result structref) + ;; CHECK: (func $incompatible-cast-separate-fallthrough (type $40) (param $eqref eqref) (result structref) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.tee $eqref ;; CHECK-NEXT: (block (result (ref i31)) @@ -2735,7 +2739,7 @@ ) ) - ;; CHECK: (func $as_of_unreachable (type $40) (result (ref $A)) + ;; CHECK: (func $as_of_unreachable (type $41) (result (ref $A)) ;; CHECK-NEXT: (unreachable) ;; CHECK-NEXT: ) (func $as_of_unreachable (result (ref $A)) @@ -2749,7 +2753,7 @@ ) ) - ;; CHECK: (func $cast-internalized-extern (type $41) (param $externref externref) + ;; CHECK: (func $cast-internalized-extern (type $42) (param $externref externref) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast (ref $A) ;; CHECK-NEXT: (extern.internalize @@ -2878,7 +2882,7 @@ ) ) - ;; CHECK: (func $refinalize.select.arm.unknown (type $42) (param $x i32) + ;; CHECK: (func $refinalize.select.arm.unknown (type $43) (param $x i32) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast (ref $void2) ;; CHECK-NEXT: (ref.func $refinalize.select.arm) @@ -2898,7 +2902,7 @@ ) ) - ;; CHECK: (func $non-null-bottom-ref (type $43) (result (ref func)) + ;; CHECK: (func $non-null-bottom-ref (type $44) (result (ref func)) ;; CHECK-NEXT: (local $0 funcref) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (local.tee $0 @@ -2926,7 +2930,7 @@ ) ) - ;; CHECK: (func $non-null-bottom-cast (type $44) (result (ref nofunc)) + ;; CHECK: (func $non-null-bottom-cast (type $45) (result (ref nofunc)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.func $non-null-bottom-cast) ;; CHECK-NEXT: ) @@ -3173,4 +3177,266 @@ ) ) ) + + ;; CHECK: (func $struct.new (type $5) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result (ref $struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (call $struct.new) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new_default $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $struct.ref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (call $get-i32) + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $struct.ref + ;; CHECK-NEXT: (ref.func $struct.new) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $struct.new + ;; Convert struct.new with default values into struct.new_default. + (drop + (struct.new $struct + (i32.const 0) + (block (result i32) + ;; A block in the middle, even with side effects, is no problem (it + ;; will be dropped). + (call $struct.new) + (i32.const 0) + ) + (i32.const 0) + (i64.const 0) + ) + ) + + ;; Refs work too. + (drop + (struct.new $struct.ref + (ref.null func) + ) + ) + + ;; But a single non-default value is enough to prevent this. Test various + ;; cases of that. + (drop + (struct.new $struct + (i32.const 0) + (i32.const 0) + (i32.const 1) ;; constant, but non-default + (i64.const 0) + ) + ) + (drop + (struct.new $struct + (i32.const 0) + (i32.const 0) + (call $get-i32) ;; non-constant + (i64.const 0) + ) + ) + (drop + (struct.new $struct.ref + (ref.func $struct.new) ;; func constant, but non-default + ) + ) + ) + + ;; CHECK: (func $array.new (type $5) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result (ref $array)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (call $array.new) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (array.new_default $array + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new $array + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_fixed $array 1 + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new $array + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array.new + ;; Convert array.new with the default value into array.new_default. + (drop + (array.new $array + (block (result i32) + (call $array.new) + (i32.const 0) + ) + (i32.const 42) + ) + ) + + ;; Ignore any non-default value. + (drop + (array.new $array + (i32.const 1) + (i32.const 42) + ) + ) + + ;; array.new_fixed is preferable when the size is exactly 1. + (drop + (array.new $array + (i32.const 42) + (i32.const 1) + ) + ) + + ;; Do nothing for size 0, for now (see TODO in code). + (drop + (array.new $array + (i32.const 42) + (i32.const 0) + ) + ) + ) + + ;; CHECK: (func $array.new_fixed (type $5) + ;; CHECK-NEXT: (local $0 i32) + ;; CHECK-NEXT: (local $1 i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result (ref $array)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (call $array.new_fixed) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (array.new_default $array + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_fixed $array 3 + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_fixed $array 3 + ;; CHECK-NEXT: (call $get-i32) + ;; CHECK-NEXT: (call $get-i32) + ;; CHECK-NEXT: (call $get-i32) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (block (result (ref $array)) + ;; CHECK-NEXT: (local.set $0 + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (call $array.new_fixed) + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $1 + ;; CHECK-NEXT: (block (result i32) + ;; CHECK-NEXT: (call $array.new_fixed) + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (array.new $array + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (array.new_fixed $array 1 + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $array.new_fixed + ;; Convert array.new_fixed with default values into array.new_default. + (drop + (array.new_fixed $array 3 + (i32.const 0) + (block (result i32) + (call $array.new_fixed) + (i32.const 0) + ) + (i32.const 0) + ) + ) + + ;; Ignore when the values are not equal. + (drop + (array.new_fixed $array 3 + (i32.const 0) + (i32.const 1) + (i32.const 0) + ) + ) + (drop + (array.new_fixed $array 3 + (call $get-i32) + (call $get-i32) + (call $get-i32) + ) + ) + + ;; If they are equal but not default, we can optimize to array.new, even + ;; with effects. + (drop + (array.new_fixed $array 2 + (block (result i32) + (call $array.new_fixed) + (i32.const 42) + ) + (block (result i32) + (call $array.new_fixed) + (i32.const 42) + ) + ) + ) + + ;; Do nothing for size 1 (this is better than array.new as-is). + (drop + (array.new_fixed $array 1 + (i32.const 42) + ) + ) + ) ) |