diff options
Diffstat (limited to 'src/passes/OptimizeInstructions.cpp')
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 720 |
1 files changed, 368 insertions, 352 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 9cc16004d..1c2445d5d 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -28,6 +28,7 @@ #include <ir/literal-utils.h> #include <ir/load-utils.h> #include <ir/manipulation.h> +#include <ir/match.h> #include <ir/properties.h> #include <ir/utils.h> #include <pass.h> @@ -132,6 +133,19 @@ struct LocalScanner : PostWalker<LocalScanner> { } }; +// Create a custom matcher for checking side effects +template<class Opt> struct PureMatcherKind {}; +template<class Opt> +struct Match::Internal::KindTypeRegistry<PureMatcherKind<Opt>> { + using matched_t = Expression*; + using data_t = Opt*; +}; +template<class Opt> struct Match::Internal::MatchSelf<PureMatcherKind<Opt>> { + bool operator()(Expression* curr, Opt* opt) { + return !opt->effects(curr).hasSideEffects(); + } +}; + // Main pass class struct OptimizeInstructions : public WalkerPass< @@ -189,6 +203,20 @@ struct OptimizeInstructions } } + EffectAnalyzer effects(Expression* expr) { + return EffectAnalyzer(getPassOptions(), getModule()->features, expr); + } + + decltype(auto) pure(Expression** binder) { + using namespace Match::Internal; + return Matcher<PureMatcherKind<OptimizeInstructions>>(binder, this); + } + + bool canReorder(Expression* a, Expression* b) { + return EffectAnalyzer::canReorder( + getPassOptions(), getModule()->features, a, b); + } + // Optimizations that don't yet fit in the pattern DSL, but could be // eventually maybe Expression* handOptimize(Expression* curr) { @@ -205,6 +233,104 @@ struct OptimizeInstructions if (isSymmetric(binary)) { canonicalize(binary); } + } + + { + // TODO: It is an ongoing project to port more transformations to the + // match API. Once most of the transformations have been ported, the + // `using namespace Match` can be hoisted to function scope and this extra + // block scope can be removed. + using namespace Match; + Builder builder(*getModule()); + { + // X == 0 => eqz X + Expression* x; + if (matches(curr, binary(EqInt32, any(&x), i32(0)))) { + return Builder(*getModule()).makeUnary(EqZInt32, x); + } + } + { + // try to get rid of (0 - ..), that is, a zero only used to negate an + // int. an add of a subtract can be flipped in order to remove it: + // (i32.add + // (i32.sub + // (i32.const 0) + // X + // ) + // Y + // ) + // => + // (i32.sub + // Y + // X + // ) + // Note that this reorders X and Y, so we need to be careful about that. + Expression *x, *y; + Binary* sub; + if (matches(curr, + binary(AddInt32, + binary(&sub, SubInt32, i32(0), any(&x)), + any(&y))) && + canReorder(x, y)) { + sub->left = y; + sub->right = x; + return sub; + } + } + { + // The flip case is even easier, as no reordering occurs: + // (i32.add + // Y + // (i32.sub + // (i32.const 0) + // X + // ) + // ) + // => + // (i32.sub + // Y + // X + // ) + Expression* y; + Binary* sub; + if (matches(curr, + binary(AddInt32, + any(&y), + binary(&sub, SubInt32, i32(0), any())))) { + sub->left = y; + return sub; + } + } + { + // try de-morgan's AND law, + // (eqz X) and (eqz Y) === eqz (X or Y) + // Note that the OR and XOR laws do not work here, as these + // are not booleans (we could check if they are, but a boolean + // would already optimize with the eqz anyhow, unless propagating). + // But for AND, the left is true iff X and Y are each all zero bits, + // and the right is true if the union of their bits is zero; same. + Unary* un; + Binary* bin; + Expression *x, *y; + if (matches(curr, + binary(&bin, + AndInt32, + unary(&un, EqZInt32, any(&x)), + unary(EqZInt32, any(&y))))) { + bin->op = OrInt32; + bin->left = x; + bin->right = y; + un->value = bin; + return un; + } + } + } + + if (auto* select = curr->dynCast<Select>()) { + return optimizeSelect(select); + } + + if (auto* binary = curr->dynCast<Binary>()) { if (auto* ext = Properties::getAlmostSignExt(binary)) { Index extraShifts; auto bits = Properties::getAlmostSignExtBits(binary, extraShifts); @@ -313,57 +439,6 @@ struct OptimizeInstructions // note that both left and right may be consts, but then we let // precompute compute the constant result } else if (binary->op == AddInt32) { - // try to get rid of (0 - ..), that is, a zero only used to negate an - // int. an add of a subtract can be flipped in order to remove it: - // (i32.add - // (i32.sub - // (i32.const 0) - // X - // ) - // Y - // ) - // => - // (i32.sub - // Y - // X - // ) - // Note that this reorders X and Y, so we need to be careful about that. - if (auto* sub = binary->left->dynCast<Binary>()) { - if (sub->op == SubInt32) { - if (auto* subZero = sub->left->dynCast<Const>()) { - if (subZero->value.geti32() == 0) { - if (EffectAnalyzer::canReorder( - getPassOptions(), features, sub->right, binary->right)) { - sub->left = binary->right; - return sub; - } - } - } - } - } - // The flip case is even easier, as no reordering occurs: - // (i32.add - // Y - // (i32.sub - // (i32.const 0) - // X - // ) - // ) - // => - // (i32.sub - // Y - // X - // ) - if (auto* sub = binary->right->dynCast<Binary>()) { - if (sub->op == SubInt32) { - if (auto* subZero = sub->left->dynCast<Const>()) { - if (subZero->value.geti32() == 0) { - sub->left = binary->left; - return sub; - } - } - } - } if (auto* ret = optimizeAddedConstants(binary)) { return ret; } @@ -463,30 +538,6 @@ struct OptimizeInstructions } } // bitwise operations - if (binary->op == AndInt32) { - // try de-morgan's AND law, - // (eqz X) and (eqz Y) === eqz (X or Y) - // Note that the OR and XOR laws do not work here, as these - // are not booleans (we could check if they are, but a boolean - // would already optimize with the eqz anyhow, unless propagating). - // But for AND, the left is true iff X and Y are each all zero bits, - // and the right is true if the union of their bits is zero; same. - if (auto* left = binary->left->dynCast<Unary>()) { - if (left->op == EqZInt32) { - if (auto* right = binary->right->dynCast<Unary>()) { - if (right->op == EqZInt32) { - // reuse one unary, drop the other - auto* leftValue = left->value; - left->value = binary; - binary->left = leftValue; - binary->right = right->value; - binary->op = OrInt32; - return left; - } - } - } - } - } // for and and or, we can potentially conditionalize if (binary->op == AndInt32 || binary->op == OrInt32) { if (auto* ret = conditionalizeExpensiveOnBitwise(binary)) { @@ -507,8 +558,7 @@ struct OptimizeInstructions } // finally, try more expensive operations on the binary in // the case that they have no side effects - if (!EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { + if (!effects(binary->left).hasSideEffects()) { if (ExpressionAnalyzer::equal(binary->left, binary->right)) { if (auto* ret = optimizeBinaryWithEqualEffectlessChildren(binary)) { return ret; @@ -563,9 +613,7 @@ struct OptimizeInstructions // sides are identical, fold // if we can replace the if with one arm, and no side effects in the // condition, do that - auto needCondition = - EffectAnalyzer(getPassOptions(), features, iff->condition) - .hasSideEffects(); + auto needCondition = effects(iff->condition).hasSideEffects(); auto isSubType = Type::isSubType(iff->ifTrue->type, iff->type); if (isSubType && !needCondition) { return iff->ifTrue; @@ -591,92 +639,6 @@ struct OptimizeInstructions } } } - } else if (auto* select = curr->dynCast<Select>()) { - select->condition = optimizeBoolean(select->condition); - if (auto* c = select->condition->dynCast<Const>()) { - // constant condition, we can just pick the right side (barring side - // effects) - if (c->value.getInteger()) { - if (!EffectAnalyzer(getPassOptions(), features, select->ifFalse) - .hasSideEffects()) { - return select->ifTrue; - } else { - // don't bother - we would need to reverse the order using a temp - // local, which is bad - } - } else { - if (!EffectAnalyzer(getPassOptions(), features, select->ifTrue) - .hasSideEffects()) { - return select->ifFalse; - } else { - Builder builder(*getModule()); - return builder.makeSequence(builder.makeDrop(select->ifTrue), - select->ifFalse); - } - } - } - 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); - if (value.hasSideEffects()) { - // at best we don't need the condition, but need to execute the value - // twice. a block is larger than a select by 2 bytes, and - // we must drop one value, so 3, while we save the condition, - // so it's not clear this is worth it, TODO - } else { - // value has no side effects - EffectAnalyzer condition( - getPassOptions(), features, select->condition); - if (!condition.hasSideEffects()) { - return select->ifTrue; - } else { - // the condition is last, so we need a new local, and it may be - // a bad idea to use a block like we do for an if. Do it only if we - // can reorder - if (!condition.invalidates(value)) { - Builder builder(*getModule()); - return builder.makeSequence(builder.makeDrop(select->condition), - select->ifTrue); - } - } - } - } } else if (auto* br = curr->dynCast<Break>()) { if (br->condition) { br->condition = optimizeBoolean(br->condition); @@ -734,15 +696,12 @@ private: // write more concise pattern matching code elsewhere. void canonicalize(Binary* binary) { assert(isSymmetric(binary)); - FeatureSet features = getModule()->features; auto swap = [&]() { - assert(EffectAnalyzer::canReorder( - getPassOptions(), features, binary->left, binary->right)); + assert(canReorder(binary->left, binary->right)); std::swap(binary->left, binary->right); }; auto maybeSwap = [&]() { - if (EffectAnalyzer::canReorder( - getPassOptions(), features, binary->left, binary->right)) { + if (canReorder(binary->left, binary->right)) { swap(); } }; @@ -860,6 +819,89 @@ private: return boolean; } + Expression* optimizeSelect(Select* curr) { + using namespace Match; + Builder builder(*getModule()); + curr->condition = optimizeBoolean(curr->condition); + { + // Constant condition, we can just pick the correct side (barring side + // effects) + Expression *ifTrue, *ifFalse; + if (matches(curr, select(pure(&ifTrue), any(&ifFalse), i32(0)))) { + return ifFalse; + } + if (matches(curr, select(any(&ifTrue), any(&ifFalse), i32(0)))) { + return builder.makeSequence(builder.makeDrop(ifTrue), ifFalse); + } + int32_t cond; + if (matches(curr, select(any(&ifTrue), pure(&ifFalse), i32(&cond)))) { + // The condition must be non-zero because a zero would have matched one + // of the previous patterns. + assert(cond != 0); + return ifTrue; + } + // Don't bother when `ifFalse` isn't pure - we would need to reverse the + // order using a temp local, which would be bad + } + { + // Flip select to remove eqz if we can reorder + Select* s; + Expression *ifTrue, *ifFalse, *c; + if (matches( + curr, + select( + &s, any(&ifTrue), any(&ifFalse), unary(EqZInt32, any(&c)))) && + canReorder(ifTrue, ifFalse)) { + s->ifTrue = ifFalse; + s->ifFalse = ifTrue; + s->condition = c; + } + } + { + // Simplify selects between 0 and 1 + Expression* c; + bool reversed = matches(curr, select(ival(0), ival(1), any(&c))); + if (reversed || matches(curr, select(ival(1), ival(0), any(&c)))) { + if (reversed) { + c = optimizeBoolean(builder.makeUnary(EqZInt32, c)); + } + if (!Properties::emitsBoolean(c)) { + // cond ? 1 : 0 ==> !!cond + c = builder.makeUnary(EqZInt32, builder.makeUnary(EqZInt32, c)); + } + return curr->type == Type::i64 ? builder.makeUnary(ExtendUInt32, c) : c; + } + } + { + // Sides are identical, fold + Expression *ifTrue, *ifFalse, *c; + if (matches(curr, select(any(&ifTrue), any(&ifFalse), any(&c))) && + ExpressionAnalyzer::equal(ifTrue, ifFalse)) { + auto value = effects(ifTrue); + if (value.hasSideEffects()) { + // At best we don't need the condition, but need to execute the + // value twice. a block is larger than a select by 2 bytes, and we + // must drop one value, so 3, while we save the condition, so it's + // not clear this is worth it, TODO + } else { + // value has no side effects + auto condition = effects(c); + if (!condition.hasSideEffects()) { + return ifTrue; + } else { + // The condition is last, so we need a new local, and it may be a + // bad idea to use a block like we do for an if. Do it only if we + // can reorder + if (!condition.invalidates(value)) { + return builder.makeSequence(builder.makeDrop(c), ifTrue); + } + } + } + } + } + return nullptr; + } + // find added constants in an expression tree, including multiplied/shifted, // and combine them note that we ignore division/shift-right, as rounding // makes this nonlinear, so not a valid opt @@ -1024,9 +1066,8 @@ private: if (!Properties::emitsBoolean(left) || !Properties::emitsBoolean(right)) { return nullptr; } - FeatureSet features = getModule()->features; - auto leftEffects = EffectAnalyzer(getPassOptions(), features, left); - auto rightEffects = EffectAnalyzer(getPassOptions(), features, right); + auto leftEffects = effects(left); + auto rightEffects = effects(right); auto leftHasSideEffects = leftEffects.hasSideEffects(); auto rightHasSideEffects = rightEffects.hasSideEffects(); if (leftHasSideEffects && rightHasSideEffects) { @@ -1072,16 +1113,13 @@ private: // (x > y) | (x == y) ==> x >= y Expression* combineOr(Binary* binary) { assert(binary->op == OrInt32); - FeatureSet features = getModule()->features; if (auto* left = binary->left->dynCast<Binary>()) { if (auto* right = binary->right->dynCast<Binary>()) { if (left->op != right->op && ExpressionAnalyzer::equal(left->left, right->left) && ExpressionAnalyzer::equal(left->right, right->right) && - !EffectAnalyzer(getPassOptions(), features, left->left) - .hasSideEffects() && - !EffectAnalyzer(getPassOptions(), features, left->right) - .hasSideEffects()) { + !effects(left->left).hasSideEffects() && + !effects(left->right).hasSideEffects()) { switch (left->op) { // (x > y) | (x == y) ==> x >= y case EqInt32: { @@ -1202,185 +1240,165 @@ private: // optimize trivial math operations, given that the right side of a binary // is a constant - // TODO: templatize on type? - Expression* optimizeWithConstantOnRight(Binary* binary) { - FeatureSet features = getModule()->features; - auto type = binary->right->type; - auto* right = binary->right->cast<Const>(); - if (type.isInteger()) { - auto constRight = right->value.getInteger(); - // operations on zero - if (constRight == 0LL) { - if (binary->op == Abstract::getBinary(type, Abstract::Shl) || - binary->op == Abstract::getBinary(type, Abstract::ShrU) || - binary->op == Abstract::getBinary(type, Abstract::ShrS) || - binary->op == Abstract::getBinary(type, Abstract::Or) || - binary->op == Abstract::getBinary(type, Abstract::Xor)) { - return binary->left; - } else if ((binary->op == Abstract::getBinary(type, Abstract::Mul) || - binary->op == Abstract::getBinary(type, Abstract::And)) && - !EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - return binary->right; - } else if (binary->op == Abstract::getBinary(type, Abstract::Eq)) { - return Builder(*getModule()) - .makeUnary(Abstract::getUnary(type, Abstract::EqZ), binary->left); - } - } - // operations on one - if (constRight == 1LL) { - // (signed)x % 1 ==> 0 - if (binary->op == Abstract::getBinary(type, Abstract::RemS) && - !EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - right->value = Literal::makeSingleZero(type); - return right; - } - // bool(x) | 1 ==> 1 - // bool(x) & 1 ==> bool(x) - // bool(x) == 1 ==> bool(x) - // bool(x) != 1 ==> !bool(x) - if (Bits::getMaxBits(binary->left, this) == 1) { - switch (binary->op) { - case OrInt32: - case OrInt64: { - if (!EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - // bool(x) | 1 ==> 1 - return binary->right; - } - break; - } - case AndInt32: - case AndInt64: - case EqInt32: { - // bool(x) & 1 ==> bool(x) - // bool(x) == 1 ==> bool(x) - return binary->left; - } - case EqInt64: { - // i64(bool(x)) == 1 ==> i32(bool(x)) - return Builder(*getModule()).makeUnary(WrapInt64, binary->left); - } - case NeInt32: - case NeInt64: { - // bool(x) != 1 ==> !bool(x) - return Builder(*getModule()) - .makeUnary( - Abstract::getUnary(binary->left->type, Abstract::EqZ), - binary->left); - } - default: { - } - } - } - } - // operations on all 1s - if (constRight == -1LL) { - if (binary->op == Abstract::getBinary(type, Abstract::And)) { - // x & -1 ==> x - return binary->left; - } else if (binary->op == Abstract::getBinary(type, Abstract::Or) && - !EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - // x | -1 ==> -1 - return binary->right; - } else if (binary->op == Abstract::getBinary(type, Abstract::RemS) && - !EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - // (signed)x % -1 ==> 0 - right->value = Literal::makeSingleZero(type); - return right; - } else if (binary->op == Abstract::getBinary(type, Abstract::GtU) && - !EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - // (unsigned)x > -1 ==> 0 - right->value = Literal::makeSingleZero(Type::i32); - right->type = Type::i32; - return right; - } else if (binary->op == Abstract::getBinary(type, Abstract::LtU)) { - // (unsigned)x < -1 ==> x != -1 - // friendlier to JS emitting as we don't need to write an unsigned - // -1 value which is large. - binary->op = Abstract::getBinary(type, Abstract::Ne); - return binary; - } else if (binary->op == DivUInt32) { - // (unsigned)x / -1 ==> x == -1 - binary->op = Abstract::getBinary(type, Abstract::Eq); - return binary; - } else if (binary->op == Abstract::getBinary(type, Abstract::Mul)) { - // x * -1 ==> 0 - x - binary->op = Abstract::getBinary(type, Abstract::Sub); - right->value = Literal::makeSingleZero(type); - std::swap(binary->left, binary->right); - return binary; - } else if (binary->op == Abstract::getBinary(type, Abstract::LeU) && - !EffectAnalyzer(getPassOptions(), features, binary->left) - .hasSideEffects()) { - // (unsigned)x <= -1 ==> 1 - right->value = Literal::makeFromInt32(1, Type::i32); - right->type = Type::i32; - return right; - } - } - // wasm binary encoding uses signed LEBs, which slightly favor negative + Expression* optimizeWithConstantOnRight(Binary* curr) { + using namespace Match; + Builder builder(*getModule()); + Expression* left; + auto* right = curr->right->cast<Const>(); + auto type = curr->right->type; + + // Operations on zero + if (matches(curr, binary(Abstract::Shl, any(&left), ival(0))) || + matches(curr, binary(Abstract::ShrU, any(&left), ival(0))) || + matches(curr, binary(Abstract::ShrS, any(&left), ival(0))) || + matches(curr, binary(Abstract::Or, any(&left), ival(0))) || + matches(curr, binary(Abstract::Xor, any(&left), ival(0)))) { + return left; + } + if (matches(curr, binary(Abstract::Mul, pure(&left), ival(0))) || + matches(curr, binary(Abstract::And, pure(&left), ival(0)))) { + return right; + } + // x == 0 ==> eqz x + if ((matches(curr, binary(Abstract::Eq, any(&left), ival(0))))) { + return builder.makeUnary(EqZInt64, left); + } + + // Operations on one + // (signed)x % 1 ==> 0 + if (matches(curr, binary(Abstract::RemS, pure(&left), ival(1)))) { + right->value = Literal::makeSingleZero(type); + return right; + } + // bool(x) | 1 ==> 1 + if (matches(curr, binary(Abstract::Or, pure(&left), ival(1))) && + Bits::getMaxBits(left, this) == 1) { + return right; + } + // bool(x) & 1 ==> bool(x) + if (matches(curr, binary(Abstract::And, any(&left), ival(1))) && + Bits::getMaxBits(left, this) == 1) { + return left; + } + // bool(x) == 1 ==> bool(x) + if (matches(curr, binary(EqInt32, any(&left), i32(1))) && + Bits::getMaxBits(left, this) == 1) { + return left; + } + // i64(bool(x)) == 1 ==> i32(bool(x)) + if (matches(curr, binary(EqInt64, any(&left), i64(1))) && + Bits::getMaxBits(left, this) == 1) { + return builder.makeUnary(WrapInt64, left); + } + // bool(x) != 1 ==> !bool(x) + if (matches(curr, binary(Abstract::Ne, any(&left), ival(1))) && + Bits::getMaxBits(curr->left, this) == 1) { + return builder.makeUnary(Abstract::getUnary(type, Abstract::EqZ), left); + } + + // Operations on all 1s + // x & -1 ==> x + if (matches(curr, binary(Abstract::And, any(&left), ival(-1)))) { + return left; + } + // x | -1 ==> -1 + if (matches(curr, binary(Abstract::Or, pure(&left), ival(-1)))) { + return right; + } + // (signed)x % -1 ==> 0 + if (matches(curr, binary(Abstract::RemS, pure(&left), ival(-1)))) { + right->value = Literal::makeSingleZero(type); + return right; + } + // (unsigned)x > -1 ==> 0 + if (matches(curr, binary(Abstract::GtU, pure(&left), ival(-1)))) { + right->value = Literal::makeSingleZero(Type::i32); + right->type = Type::i32; + return right; + } + // (unsigned)x < -1 ==> x != -1 + // Friendlier to JS emitting as we don't need to write an unsigned -1 value + // which is large. + if (matches(curr, binary(Abstract::LtU, any(), ival(-1)))) { + curr->op = Abstract::getBinary(type, Abstract::Ne); + return curr; + } + // (unsigned)x / -1 ==> x == -1 + // TODO: i64 as well if sign-extension is enabled + if (matches(curr, binary(DivUInt32, any(), ival(-1)))) { + curr->op = Abstract::getBinary(type, Abstract::Eq); + return curr; + } + // x * -1 ==> 0 - x + if (matches(curr, binary(Abstract::Mul, any(&left), ival(-1)))) { + right->value = Literal::makeSingleZero(type); + curr->op = Abstract::getBinary(type, Abstract::Sub); + curr->left = right; + curr->right = left; + return curr; + } + // (unsigned)x <= -1 ==> 1 + if (matches(curr, binary(Abstract::LeU, pure(&left), ival(-1)))) { + right->value = Literal::makeFromInt32(1, Type::i32); + right->type = Type::i32; + return right; + } + { + // Wasm binary encoding uses signed LEBs, which slightly favor negative // numbers: -64 is more efficient than +64 etc., as well as other powers - // of two 7 bits etc. higher. we therefore prefer x - -64 over x + 64. - // in theory we could just prefer negative numbers over positive, but - // that can have bad effects on gzip compression (as it would mean more - // subtractions than the more common additions). - if (binary->op == Abstract::getBinary(type, Abstract::Add) || - binary->op == Abstract::getBinary(type, Abstract::Sub)) { - auto value = constRight; - if (value == 0x40 || value == 0x2000 || value == 0x100000 || - value == 0x8000000 || value == 0x400000000LL || - value == 0x20000000000LL || value == 0x1000000000000LL || - value == 0x80000000000000LL || value == 0x4000000000000000LL) { - right->value = right->value.neg(); - if (binary->op == Abstract::getBinary(type, Abstract::Add)) { - binary->op = Abstract::getBinary(type, Abstract::Sub); - } else { - binary->op = Abstract::getBinary(type, Abstract::Add); - } - return binary; + // of two 7 bits etc. higher. we therefore prefer x - -64 over x + 64. in + // theory we could just prefer negative numbers over positive, but that + // can have bad effects on gzip compression (as it would mean more + // subtractions than the more common additions). TODO: Simplify this by + // adding an ival matcher than can bind int64_t vars. + int64_t value; + if ((matches(curr, binary(Abstract::Add, any(), ival(&value))) || + matches(curr, binary(Abstract::Sub, any(), ival(&value)))) && + (value == 0x40 || value == 0x2000 || value == 0x100000 || + value == 0x8000000 || value == 0x400000000LL || + value == 0x20000000000LL || value == 0x1000000000000LL || + value == 0x80000000000000LL || value == 0x4000000000000000LL)) { + right->value = right->value.neg(); + if (matches(curr, binary(Abstract::Add, any(), constant()))) { + curr->op = Abstract::getBinary(type, Abstract::Sub); + } else { + curr->op = Abstract::getBinary(type, Abstract::Add); } + return curr; } } - if (type.isFloat()) { - auto value = right->value.getFloat(); - if (value == 0.0) { - if (binary->op == Abstract::getBinary(type, Abstract::Sub)) { - if (std::signbit(value)) { - // x - (-0.0) ==> x + 0.0 - binary->op = Abstract::getBinary(type, Abstract::Add); - right->value = right->value.neg(); - return binary; - } else { - // x - 0.0 ==> x - return binary->left; - } - } else if (binary->op == Abstract::getBinary(type, Abstract::Add)) { - if (std::signbit(value)) { - // x + (-0.0) ==> x - return binary->left; - } + { + double value; + if (matches(curr, binary(Abstract::Sub, any(), fval(&value))) && + value == 0.0) { + // x - (-0.0) ==> x + 0.0 + if (std::signbit(value)) { + curr->op = Abstract::getBinary(type, Abstract::Add); + right->value = right->value.neg(); + return curr; + } else { + // x - 0.0 ==> x + return curr->left; } } } - if (type.isInteger() || type.isFloat()) { - // note that this is correct even on floats with a NaN on the left, - // as a NaN would skip the computation and just return the NaN, - // and that is precisely what we do here. but, the same with -1 - // (change to a negation) would be incorrect for that reason. - if (right->value == Literal::makeFromInt32(1, type)) { - if (binary->op == Abstract::getBinary(type, Abstract::Mul) || - binary->op == Abstract::getBinary(type, Abstract::DivS) || - binary->op == Abstract::getBinary(type, Abstract::DivU)) { - return binary->left; - } + { + // x + (-0.0) ==> x + double value; + if (matches(curr, binary(Abstract::Add, any(), fval(&value))) && + value == 0.0 && std::signbit(value)) { + return curr->left; } } - // TODO: v128 not implemented yet + // Note that this is correct even on floats with a NaN on the left, + // as a NaN would skip the computation and just return the NaN, + // and that is precisely what we do here. but, the same with -1 + // (change to a negation) would be incorrect for that reason. + if (matches(curr, binary(Abstract::Mul, any(&left), constant(1))) || + matches(curr, binary(Abstract::DivS, any(&left), constant(1))) || + matches(curr, binary(Abstract::DivU, any(&left), constant(1)))) { + return left; + } return nullptr; } @@ -1397,9 +1415,7 @@ private: if ((binary->op == Abstract::getBinary(type, Abstract::Shl) || binary->op == Abstract::getBinary(type, Abstract::ShrU) || binary->op == Abstract::getBinary(type, Abstract::ShrS)) && - !EffectAnalyzer( - getPassOptions(), getModule()->features, binary->right) - .hasSideEffects()) { + !effects(binary->right).hasSideEffects()) { return binary->left; } } |