diff options
| -rw-r--r-- | src/ir/abstract.h | 17 | ||||
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 221 | ||||
| -rw-r--r-- | test/passes/optimize-instructions_all-features.txt | 168 | ||||
| -rw-r--r-- | test/passes/optimize-instructions_all-features.wast | 214 | ||||
| -rw-r--r-- | test/wasm2js/i64-lowering.2asm.js.opt | 72 | ||||
| -rw-r--r-- | test/wasm2js/nested-selects.2asm.js.opt | 2 |
6 files changed, 539 insertions, 155 deletions
diff --git a/src/ir/abstract.h b/src/ir/abstract.h index 3071e6dd6..687412455 100644 --- a/src/ir/abstract.h +++ b/src/ir/abstract.h @@ -44,6 +44,7 @@ enum Op { Or, Xor, // Relational + EqZ, Eq, Ne, LtS, @@ -62,10 +63,22 @@ enum Op { inline UnaryOp getUnary(Type type, Op op) { switch (type.getSingle()) { case Type::i32: { - return InvalidUnary; + switch (op) { + case EqZ: + return EqZInt32; + default: + return InvalidUnary; + } + break; } case Type::i64: { - return InvalidUnary; + switch (op) { + case EqZ: + return EqZInt64; + default: + return InvalidUnary; + } + break; } case Type::f32: { switch (op) { diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 2e59775c0..860ea3ac7 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -666,87 +666,13 @@ struct OptimizeInstructions } } } else if (auto* unary = curr->dynCast<Unary>()) { - // de-morgan's laws if (unary->op == EqZInt32) { if (auto* inner = unary->value->dynCast<Binary>()) { - switch (inner->op) { - case EqInt32: - inner->op = NeInt32; - return inner; - case NeInt32: - inner->op = EqInt32; - return inner; - case LtSInt32: - inner->op = GeSInt32; - return inner; - case LtUInt32: - inner->op = GeUInt32; - return inner; - case LeSInt32: - inner->op = GtSInt32; - return inner; - case LeUInt32: - inner->op = GtUInt32; - return inner; - case GtSInt32: - inner->op = LeSInt32; - return inner; - case GtUInt32: - inner->op = LeUInt32; - return inner; - case GeSInt32: - inner->op = LtSInt32; - return inner; - case GeUInt32: - inner->op = LtUInt32; - return inner; - - case EqInt64: - inner->op = NeInt64; - return inner; - case NeInt64: - inner->op = EqInt64; - return inner; - case LtSInt64: - inner->op = GeSInt64; - return inner; - case LtUInt64: - inner->op = GeUInt64; - return inner; - case LeSInt64: - inner->op = GtSInt64; - return inner; - case LeUInt64: - inner->op = GtUInt64; - return inner; - case GtSInt64: - inner->op = LeSInt64; - return inner; - case GtUInt64: - inner->op = LeUInt64; - return inner; - case GeSInt64: - inner->op = LtSInt64; - return inner; - case GeUInt64: - inner->op = LtUInt64; - return inner; - - case EqFloat32: - inner->op = NeFloat32; - return inner; - case NeFloat32: - inner->op = EqFloat32; - return inner; - - case EqFloat64: - inner->op = NeFloat64; - return inner; - case NeFloat64: - inner->op = EqFloat64; - return inner; - - default: {} + // Try to invert a relational operation using De Morgan's law + auto op = invertBinaryOp(inner->op); + if (op != InvalidBinary) { + inner->op = op; + return inner; } } // eqz of a sign extension can be of zero-extension @@ -809,16 +735,6 @@ struct OptimizeInstructions } } else if (auto* select = curr->dynCast<Select>()) { select->condition = optimizeBoolean(select->condition); - auto* condition = select->condition->dynCast<Unary>(); - if (condition && condition->op == EqZInt32) { - // flip select to remove eqz, if we can reorder - EffectAnalyzer ifTrue(getPassOptions(), features, select->ifTrue); - EffectAnalyzer ifFalse(getPassOptions(), features, select->ifFalse); - if (!ifTrue.invalidates(ifFalse)) { - select->condition = condition->value; - std::swap(select->ifTrue, select->ifFalse); - } - } if (auto* c = select->condition->dynCast<Const>()) { // constant condition, we can just pick the right side (barring side // effects) @@ -841,6 +757,42 @@ struct OptimizeInstructions } } } + if (auto* constTrue = select->ifTrue->dynCast<Const>()) { + if (auto* constFalse = select->ifFalse->dynCast<Const>()) { + if (select->type == Type::i32 || select->type == Type::i64) { + auto trueValue = constTrue->value.getInteger(); + auto falseValue = constFalse->value.getInteger(); + if ((trueValue == 1LL && falseValue == 0LL) || + (trueValue == 0LL && falseValue == 1LL)) { + Builder builder(*getModule()); + Expression* condition = select->condition; + if (trueValue == 0LL) { + condition = + optimizeBoolean(builder.makeUnary(EqZInt32, condition)); + } + if (!Properties::emitsBoolean(condition)) { + // expr ? 1 : 0 ==> !!expr + condition = builder.makeUnary( + EqZInt32, builder.makeUnary(EqZInt32, condition)); + } + return select->type == Type::i64 + ? builder.makeUnary(ExtendUInt32, condition) + : condition; + } + } + } + } + if (auto* condition = select->condition->dynCast<Unary>()) { + if (condition->op == EqZInt32) { + // flip select to remove eqz, if we can reorder + EffectAnalyzer ifTrue(getPassOptions(), features, select->ifTrue); + EffectAnalyzer ifFalse(getPassOptions(), features, select->ifFalse); + if (!ifTrue.invalidates(ifFalse)) { + select->condition = condition->value; + std::swap(select->ifTrue, select->ifFalse); + } + } + } if (ExpressionAnalyzer::equal(select->ifTrue, select->ifFalse)) { // sides are identical, fold EffectAnalyzer value(getPassOptions(), features, select->ifTrue); @@ -974,11 +926,21 @@ private: Expression* optimizeBoolean(Expression* boolean) { // TODO use a general getFallthroughs if (auto* unary = boolean->dynCast<Unary>()) { - if (unary && unary->op == EqZInt32) { - auto* unary2 = unary->value->dynCast<Unary>(); - if (unary2 && unary2->op == EqZInt32) { - // double eqz - return unary2->value; + if (unary) { + if (unary->op == EqZInt32) { + auto* unary2 = unary->value->dynCast<Unary>(); + if (unary2 && unary2->op == EqZInt32) { + // double eqz + return unary2->value; + } + if (auto* binary = unary->value->dynCast<Binary>()) { + // !(x <=> y) ==> x <!=> y + auto op = invertBinaryOp(binary->op); + if (op != InvalidBinary) { + binary->op = op; + return binary; + } + } } } } else if (auto* binary = boolean->dynCast<Binary>()) { @@ -989,18 +951,23 @@ private: return binary->right; } } - } - if (binary->op == OrInt32) { + } else if (binary->op == OrInt32) { // an or flowing into a boolean context can consider each input as // boolean binary->left = optimizeBoolean(binary->left); binary->right = optimizeBoolean(binary->right); } else if (binary->op == NeInt32) { - // x != 0 is just x if it's used as a bool if (auto* num = binary->right->dynCast<Const>()) { + // x != 0 is just x if it's used as a bool if (num->value.geti32() == 0) { return binary->left; } + // TODO: Perhaps use it for separate final pass??? + // x != -1 ==> x ^ -1 + // if (num->value.geti32() == -1) { + // binary->op = XorInt32; + // return binary; + // } } } if (auto* ext = Properties::getSignExtValue(binary)) { @@ -1611,6 +1578,66 @@ private: return nullptr; } } + + BinaryOp invertBinaryOp(BinaryOp op) { + // use de-morgan's laws + switch (op) { + case EqInt32: + return NeInt32; + case NeInt32: + return EqInt32; + case LtSInt32: + return GeSInt32; + case LtUInt32: + return GeUInt32; + case LeSInt32: + return GtSInt32; + case LeUInt32: + return GtUInt32; + case GtSInt32: + return LeSInt32; + case GtUInt32: + return LeUInt32; + case GeSInt32: + return LtSInt32; + case GeUInt32: + return LtUInt32; + + case EqInt64: + return NeInt64; + case NeInt64: + return EqInt64; + case LtSInt64: + return GeSInt64; + case LtUInt64: + return GeUInt64; + case LeSInt64: + return GtSInt64; + case LeUInt64: + return GtUInt64; + case GtSInt64: + return LeSInt64; + case GtUInt64: + return LeUInt64; + case GeSInt64: + return LtSInt64; + case GeUInt64: + return LtUInt64; + + case EqFloat32: + return NeFloat32; + case NeFloat32: + return EqFloat32; + + case EqFloat64: + return NeFloat64; + case NeFloat64: + return EqFloat64; + + default: + return InvalidBinary; + } + } }; Pass* createOptimizeInstructionsPass() { return new OptimizeInstructions(); } diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt index 76c6ffe0a..e08702b91 100644 --- a/test/passes/optimize-instructions_all-features.txt +++ b/test/passes/optimize-instructions_all-features.txt @@ -3,8 +3,8 @@ (type $i32_=>_i32 (func (param i32) (result i32))) (type $none_=>_i32 (func (result i32))) (type $none_=>_none (func)) - (type $i32_=>_none (func (param i32))) (type $i32_i64_=>_none (func (param i32 i64))) + (type $i32_=>_none (func (param i32))) (type $i32_i32_=>_i32 (func (param i32 i32) (result i32))) (type $none_=>_i64 (func (result i64))) (type $i64_=>_i64 (func (param i64) (result i64))) @@ -3228,7 +3228,7 @@ (local.get $x) ) ) - (func $select-on-const (param $x i32) (param $y i32) + (func $select-on-const (param $x i32) (param $y i64) (drop (local.get $x) ) @@ -3264,6 +3264,157 @@ (i32.const 6) ) ) + (drop + (i32.eqz + (i32.eqz + (local.get $x) + ) + ) + ) + (drop + (i32.eqz + (local.get $x) + ) + ) + (drop + (i32.ge_s + (local.get $x) + (i32.const 0) + ) + ) + (drop + (i32.lt_s + (local.get $x) + (i32.const 0) + ) + ) + (drop + (i32.lt_s + (local.get $x) + (i32.const 0) + ) + ) + (drop + (i32.gt_s + (local.get $x) + (i32.const 0) + ) + ) + (drop + (i32.le_s + (local.get $x) + (i32.const 0) + ) + ) + (drop + (i32.ge_s + (local.get $x) + (i32.const 0) + ) + ) + (drop + (i64.extend_i32_u + (i32.eqz + (i32.eqz + (local.get $x) + ) + ) + ) + ) + (drop + (i64.extend_i32_u + (i32.eqz + (local.get $x) + ) + ) + ) + (drop + (i64.extend_i32_u + (i64.eqz + (local.get $y) + ) + ) + ) + (drop + (i64.extend_i32_u + (i32.eqz + (i64.eqz + (local.get $y) + ) + ) + ) + ) + (drop + (i64.extend_i32_u + (i64.ge_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (i64.extend_i32_u + (i64.lt_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (i64.extend_i32_u + (i64.lt_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (i64.extend_i32_u + (i64.ge_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (select + (i32.const 0) + (local.get $x) + (i32.const 0) + ) + ) + (drop + (select + (i32.const 2) + (local.get $x) + (i32.const 2) + ) + ) + (drop + (select + (local.get $x) + (i32.const 2) + (local.get $x) + ) + ) + (drop + (select + (local.get $y) + (i64.const 0) + (i64.eqz + (i64.const 0) + ) + ) + ) + (drop + (select + (local.get $y) + (i64.const 2) + (i64.eqz + (i64.const 2) + ) + ) + ) ) (func $optimize-boolean (param $x i32) (drop @@ -3563,6 +3714,19 @@ (func $if-arms-subtype (result externref) (ref.null) ) + (func $optimize-boolean-context (param $x i32) (param $y i32) + (if + (local.get $x) + (unreachable) + ) + (drop + (select + (local.get $x) + (local.get $y) + (local.get $x) + ) + ) + ) ) (module (type $none_=>_none (func)) diff --git a/test/passes/optimize-instructions_all-features.wast b/test/passes/optimize-instructions_all-features.wast index c62f0bc42..2790cc9ea 100644 --- a/test/passes/optimize-instructions_all-features.wast +++ b/test/passes/optimize-instructions_all-features.wast @@ -3714,7 +3714,7 @@ ) ) ) - (func $select-on-const (param $x i32) (param $y i32) + (func $select-on-const (param $x i32) (param $y i64) (drop (select (i32.const 2) @@ -3765,6 +3765,200 @@ (i32.const 1) ) ) + (drop + (select + (i32.const 1) + (i32.const 0) + (local.get $x) + ) + ) + (drop + (select + (i32.const 0) + (i32.const 1) + (local.get $x) + ) + ) + (drop + (select + (i32.const 0) + (i32.const 1) + (i32.lt_s + (local.get $x) + (i32.const 0) + ) + ) + ) + (drop + (select + (i32.const 1) + (i32.const 0) + (i32.lt_s + (local.get $x) + (i32.const 0) + ) + ) + ) + (drop + (select + (i32.const 0) + (i32.const 1) + (i32.ge_s + (local.get $x) + (i32.const 0) + ) + ) + ) + (drop + (select + (i32.const 1) + (i32.const 0) + (i32.gt_s + (local.get $x) + (i32.const 0) + ) + ) + ) + (drop + (select + (i32.const 0) + (i32.const 1) + (i32.gt_s + (local.get $x) + (i32.const 0) + ) + ) + ) + (drop + (select + (i32.const 1) + (i32.const 0) + (i32.ge_s + (local.get $x) + (i32.const 0) + ) + ) + ) + (drop + (select + (i64.const 1) + (i64.const 0) + (local.get $x) + ) + ) + (drop + (select + (i64.const 0) + (i64.const 1) + (local.get $x) + ) + ) + (drop + (select + (i64.const 1) + (i64.const 0) + (i64.eqz + (local.get $y) + ) + ) + ) + (drop + (select + (i64.const 0) + (i64.const 1) + (i64.eqz + (local.get $y) + ) + ) + ) + (drop + (select + (i64.const 0) + (i64.const 1) + (i64.lt_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (select + (i64.const 1) + (i64.const 0) + (i64.lt_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (select + (i64.const 0) + (i64.const 1) + (i64.ge_s + (local.get $y) + (i64.const 0) + ) + ) + ) + (drop + (select + (i64.const 1) + (i64.const 0) + (i64.ge_s + (local.get $y) + (i64.const 0) + ) + ) + ) + ;; optimize boolean + (drop + (select + (local.get $x) + (i32.const 0) + (i32.eqz + (i32.const 0) + ) + ) + ) + (drop + (select + (local.get $x) + (i32.const 2) + (i32.eqz + (i32.const 2) + ) + ) + ) + (drop + (select + (local.get $x) + (i32.const 2) + (i32.eqz + (i32.eqz + (local.get $x) + ) + ) + ) + ) + (drop + (select + (local.get $y) + (i64.const 0) + (i64.eqz + (i64.const 0) + ) + ) + ) + (drop + (select + (local.get $y) + (i64.const 2) + (i64.eqz + (i64.const 2) + ) + ) + ) ) (func $optimize-boolean (param $x i32) (drop @@ -4021,6 +4215,24 @@ (ref.null) ) ) + (func $optimize-boolean-context (param $x i32) (param $y i32) + ;; 0 - x ==> x + (if + (i32.sub + (i32.const 0) + (local.get $x) + ) + (unreachable) + ) + (drop (select + (local.get $x) + (local.get $y) + (i32.sub + (i32.const 0) + (local.get $x) + ) + )) + ) ) (module (import "env" "memory" (memory $0 (shared 256 256))) diff --git a/test/wasm2js/i64-lowering.2asm.js.opt b/test/wasm2js/i64-lowering.2asm.js.opt index e5d955dfd..f4d940863 100644 --- a/test/wasm2js/i64-lowering.2asm.js.opt +++ b/test/wasm2js/i64-lowering.2asm.js.opt @@ -20,76 +20,44 @@ function asmFunc(global, env, buffer) { var abort = env.abort; var nan = global.NaN; var infinity = global.Infinity; - function $3($0, $1, $2, $3_1) { - $0 = $0 | 0; - $1 = $1 | 0; - $2 = $2 | 0; - $3_1 = $3_1 | 0; - return (($1 | 0) > ($3_1 | 0) ? 1 : ($1 | 0) >= ($3_1 | 0) ? ($0 >>> 0 < $2 >>> 0 ? 0 : 1) : 0) | 0; + function legalstub$1($0, $1, $2, $3) { + return ($0 | 0) == ($2 | 0) & ($1 | 0) == ($3 | 0); } - function $4($0, $1, $2, $3_1) { - $0 = $0 | 0; - $1 = $1 | 0; - $2 = $2 | 0; - $3_1 = $3_1 | 0; - return (($1 | 0) > ($3_1 | 0) ? 1 : ($1 | 0) >= ($3_1 | 0) ? ($0 >>> 0 <= $2 >>> 0 ? 0 : 1) : 0) | 0; + function legalstub$2($0, $1, $2, $3) { + return ($0 | 0) != ($2 | 0) | ($1 | 0) != ($3 | 0); } - function $5($0, $1, $2, $3_1) { - $0 = $0 | 0; - $1 = $1 | 0; - $2 = $2 | 0; - $3_1 = $3_1 | 0; - return (($1 | 0) < ($3_1 | 0) ? 1 : ($1 | 0) <= ($3_1 | 0) ? ($0 >>> 0 > $2 >>> 0 ? 0 : 1) : 0) | 0; + function legalstub$3($0, $1, $2, $3) { + return ($1 | 0) > ($3 | 0) ? 1 : ($1 | 0) >= ($3 | 0) ? $0 >>> 0 >= $2 >>> 0 : 0; } - function $6($0, $1, $2, $3_1) { - $0 = $0 | 0; - $1 = $1 | 0; - $2 = $2 | 0; - $3_1 = $3_1 | 0; - return (($1 | 0) < ($3_1 | 0) ? 1 : ($1 | 0) <= ($3_1 | 0) ? ($0 >>> 0 >= $2 >>> 0 ? 0 : 1) : 0) | 0; + function legalstub$4($0, $1, $2, $3) { + return ($1 | 0) > ($3 | 0) ? 1 : ($1 | 0) >= ($3 | 0) ? $0 >>> 0 > $2 >>> 0 : 0; } - function legalstub$1($0, $1, $2, $3_1) { - return ($0 | 0) == ($2 | 0) & ($1 | 0) == ($3_1 | 0); + function legalstub$5($0, $1, $2, $3) { + return ($1 | 0) < ($3 | 0) ? 1 : ($1 | 0) <= ($3 | 0) ? $0 >>> 0 <= $2 >>> 0 : 0; } - function legalstub$2($0, $1, $2, $3_1) { - return ($0 | 0) != ($2 | 0) | ($1 | 0) != ($3_1 | 0); + function legalstub$6($0, $1, $2, $3) { + return ($1 | 0) < ($3 | 0) ? 1 : ($1 | 0) <= ($3 | 0) ? $0 >>> 0 < $2 >>> 0 : 0; } - function legalstub$3($0, $1, $2, $3_1) { - return $3($0, $1, $2, $3_1); + function legalstub$7($0, $1, $2, $3) { + return ($1 | 0) == ($3 | 0) & $0 >>> 0 >= $2 >>> 0 | $1 >>> 0 > $3 >>> 0; } - function legalstub$4($0, $1, $2, $3_1) { - return $4($0, $1, $2, $3_1); + function legalstub$8($0, $1, $2, $3) { + return ($1 | 0) == ($3 | 0) & $0 >>> 0 > $2 >>> 0 | $1 >>> 0 > $3 >>> 0; } - function legalstub$5($0, $1, $2, $3_1) { - return $5($0, $1, $2, $3_1); + function legalstub$9($0, $1, $2, $3) { + return ($1 | 0) == ($3 | 0) & $0 >>> 0 <= $2 >>> 0 | $1 >>> 0 < $3 >>> 0; } - function legalstub$6($0, $1, $2, $3_1) { - return $6($0, $1, $2, $3_1); - } - - function legalstub$7($0, $1, $2, $3_1) { - return ($1 | 0) == ($3_1 | 0) & $0 >>> 0 >= $2 >>> 0 | $1 >>> 0 > $3_1 >>> 0; - } - - function legalstub$8($0, $1, $2, $3_1) { - return ($1 | 0) == ($3_1 | 0) & $0 >>> 0 > $2 >>> 0 | $1 >>> 0 > $3_1 >>> 0; - } - - function legalstub$9($0, $1, $2, $3_1) { - return ($1 | 0) == ($3_1 | 0) & $0 >>> 0 <= $2 >>> 0 | $1 >>> 0 < $3_1 >>> 0; - } - - function legalstub$10($0, $1, $2, $3_1) { - return ($1 | 0) == ($3_1 | 0) & $0 >>> 0 < $2 >>> 0 | $1 >>> 0 < $3_1 >>> 0; + function legalstub$10($0, $1, $2, $3) { + return ($1 | 0) == ($3 | 0) & $0 >>> 0 < $2 >>> 0 | $1 >>> 0 < $3 >>> 0; } var FUNCTION_TABLE = []; diff --git a/test/wasm2js/nested-selects.2asm.js.opt b/test/wasm2js/nested-selects.2asm.js.opt index 16d5529cd..9bb06d563 100644 --- a/test/wasm2js/nested-selects.2asm.js.opt +++ b/test/wasm2js/nested-selects.2asm.js.opt @@ -22,7 +22,7 @@ function asmFunc(global, env, buffer) { var infinity = global.Infinity; function $1($0) { $0 = $0 | 0; - return (($0 | 0) < 0 ? -1 : ($0 | 0) > 0 ? 1 : 0) | 0; + return (($0 | 0) < 0 ? -1 : ($0 | 0) > 0) | 0; } var FUNCTION_TABLE = []; |