summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorAlon Zakai <alonzakai@gmail.com>2017-02-16 22:11:13 -0800
committerGitHub <noreply@github.com>2017-02-16 22:11:13 -0800
commit0728a53fb6bf0540b9789c7bcd26e195800c5ecc (patch)
treec615e78f96e79b121e92b598335b9e361a8025d4 /src
parenta78dddbcf2bf9f23840c7074ce16c04a8d55c3df (diff)
downloadbinaryen-0728a53fb6bf0540b9789c7bcd26e195800c5ecc.tar.gz
binaryen-0728a53fb6bf0540b9789c7bcd26e195800c5ecc.tar.bz2
binaryen-0728a53fb6bf0540b9789c7bcd26e195800c5ecc.zip
optimize linear sums (#904)
Diffstat (limited to 'src')
-rw-r--r--src/passes/OptimizeInstructions.cpp110
-rw-r--r--src/support/bits.cpp2
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;
}
}