diff options
author | Alon Zakai <alonzakai@gmail.com> | 2017-02-16 22:11:13 -0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-02-16 22:11:13 -0800 |
commit | 0728a53fb6bf0540b9789c7bcd26e195800c5ecc (patch) | |
tree | c615e78f96e79b121e92b598335b9e361a8025d4 /src | |
parent | a78dddbcf2bf9f23840c7074ce16c04a8d55c3df (diff) | |
download | binaryen-0728a53fb6bf0540b9789c7bcd26e195800c5ecc.tar.gz binaryen-0728a53fb6bf0540b9789c7bcd26e195800c5ecc.tar.bz2 binaryen-0728a53fb6bf0540b9789c7bcd26e195800c5ecc.zip |
optimize linear sums (#904)
Diffstat (limited to 'src')
-rw-r--r-- | src/passes/OptimizeInstructions.cpp | 110 | ||||
-rw-r--r-- | src/support/bits.cpp | 2 |
2 files changed, 111 insertions, 1 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index c374a15ac..de46f155a 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -357,6 +357,8 @@ struct OptimizeInstructions : public WalkerPass<PostWalker<OptimizeInstructions, } } // note that both left and right may be consts, but then we let precompute compute the constant result + } else if (binary->op == AddInt32 || binary->op == SubInt32) { + return optimizeAddedConstants(binary); } else if (binary->op == AndInt32) { if (auto* right = binary->right->dynCast<Const>()) { if (right->type == i32) { @@ -518,6 +520,114 @@ private: return boolean; } + // 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 + Expression* optimizeAddedConstants(Binary* binary) { + int32_t constant = 0; + std::vector<Const*> constants; + std::function<void (Expression*, int)> seek = [&](Expression* curr, int mul) { + if (auto* c = curr->dynCast<Const>()) { + auto value = c->value.geti32(); + if (value != 0) { + constant += value * mul; + constants.push_back(c); + } + } else if (auto* binary = curr->dynCast<Binary>()) { + if (binary->op == AddInt32) { + seek(binary->left, mul); + seek(binary->right, mul); + return; + } else if (binary->op == SubInt32) { + // if the left is a zero, ignore it, it's how we negate ints + auto* left = binary->left->dynCast<Const>(); + if (!left || left->value.geti32() != 0) { + seek(binary->left, mul); + } + seek(binary->right, -mul); + return; + } else if (binary->op == ShlInt32) { + if (auto* c = binary->right->dynCast<Const>()) { + seek(binary->left, mul * Pow2(c->value.geti32())); + return; + } + } else if (binary->op == MulInt32) { + if (auto* c = binary->left->dynCast<Const>()) { + seek(binary->right, mul * c->value.geti32()); + return; + } else if (auto* c = binary->right->dynCast<Const>()) { + seek(binary->left, mul * c->value.geti32()); + return; + } + } + } + }; + // find all factors + seek(binary, 1); + if (constants.size() <= 1) return nullptr; // nothing to do + // wipe out all constants, we'll replace with a single added one + for (auto* c : constants) { + c->value = Literal(int32_t(0)); + } + // remove added/subbed zeros + struct ZeroRemover : public PostWalker<ZeroRemover, Visitor<ZeroRemover>> { + // TODO: we could save the binarys and costs we drop, and reuse them later + + PassOptions& passOptions; + + ZeroRemover(PassOptions& passOptions) : passOptions(passOptions) {} + + void visitBinary(Binary* curr) { + auto* left = curr->left->dynCast<Const>(); + auto* right = curr->right->dynCast<Const>(); + if (curr->op == AddInt32) { + if (left && left->value.geti32() == 0) { + replaceCurrent(curr->right); + return; + } + if (right && right->value.geti32() == 0) { + replaceCurrent(curr->left); + return; + } + } else if (curr->op == SubInt32) { + // we must leave a left zero, as it is how we negate ints + if (right && right->value.geti32() == 0) { + replaceCurrent(curr->left); + return; + } + } else if (curr->op == ShlInt32) { + // shifting a 0 is a 0, unless the shift has side effects + if (left && left->value.geti32() == 0 && !EffectAnalyzer(passOptions, curr->right).hasSideEffects()) { + replaceCurrent(left); + return; + } + } else if (curr->op == MulInt32) { + // multiplying by zero is a zero, unless the other side has side effects + if (left && left->value.geti32() == 0 && !EffectAnalyzer(passOptions, curr->right).hasSideEffects()) { + replaceCurrent(left); + return; + } + if (right && right->value.geti32() == 0 && !EffectAnalyzer(passOptions, curr->left).hasSideEffects()) { + replaceCurrent(right); + return; + } + } + } + }; + Expression* walked = binary; + ZeroRemover(getPassOptions()).walk(walked); + if (constant == 0) return walked; // nothing more to do + if (auto* c = walked->dynCast<Const>()) { + assert(c->value.geti32() == 0); + c->value = Literal(constant); + return c; + } + Builder builder(*getModule()); + return builder.makeBinary(AddInt32, + walked, + builder.makeConst(Literal(constant)) + ); + } + // expensive1 | expensive2 can be turned into expensive1 ? 1 : expensive2, and // expensive | cheap can be turned into cheap ? 1 : expensive, // so that we can avoid one expensive computation, if it has no side effects. diff --git a/src/support/bits.cpp b/src/support/bits.cpp index aa72201f4..8f28a7fdb 100644 --- a/src/support/bits.cpp +++ b/src/support/bits.cpp @@ -114,13 +114,13 @@ uint32_t Log2(uint32_t v) { uint32_t Pow2(uint32_t v) { switch (v) { - default: WASM_UNREACHABLE(); case 0: return 1; case 1: return 2; case 2: return 4; case 3: return 8; case 4: return 16; case 5: return 32; + default: return 1 << v; } } |