diff options
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 56 | ||||
| -rw-r--r-- | test/lit/passes/optimize-instructions.wast | 85 |
2 files changed, 132 insertions, 9 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index ecc5d4488..1a2807ab4 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -2543,23 +2543,61 @@ private: } } { - // (i32(x) != 0) | (i32(y) != 0) ==> i32(x | y) != 0 - // (i64(x) != 0) | (i64(y) != 0) ==> i64(x | y) != 0 + // Binary operations that preserve a bitwise OR can be + // reordered. If F(x) = binary(x, c), and F(x) preserves OR, + // that is, + // + // F(x) | F(y) == F(x | y) + // + // Then also + // + // binary(x, c) | binary(y, c) => binary(x | y, c) + Binary *bx, *by; Expression *x, *y; + Const *cx, *cy; if (matches(curr, binary(OrInt32, - binary(Ne, any(&x), ival(0)), - binary(Ne, any(&y), ival(0)))) && - x->type == y->type) { - auto* inner = curr->left->cast<Binary>(); - inner->left = Builder(*getModule()) - .makeBinary(Abstract::getBinary(x->type, Or), x, y); - return inner; + binary(&bx, any(&x), ival(&cx)), + binary(&by, any(&y), ival(&cy)))) && + bx->op == by->op && x->type == y->type && cx->value == cy->value && + preserveOr(bx)) { + bx->left = Builder(*getModule()) + .makeBinary(Abstract::getBinary(x->type, Or), x, y); + return bx; } } return nullptr; } + // Check whether an operation preserves the Or operation through it, that is, + // + // F(x | y) = F(x) | F(y) + // + // Mathematically that means F is homomorphic with respect to the | operation. + // + // F(x) is seen as taking a single parameter of its first child. That is, the + // first child is |x|, and the rest is constant. For example, if we are given + // a binary with operation != and the right child is a constant 0, then + // F(x) = (x != 0). + bool preserveOr(Binary* curr) { + using namespace Abstract; + using namespace Match; + + // (x != 0) | (y != 0) ==> (x | y) != 0 + // This effectively checks if any bits are set in x or y. + if (matches(curr, binary(Ne, any(), ival(0)))) { + return true; + } + + // (x < 0) | (y < 0) ==> (x | y) < 0 + // This effectively checks if x or y have the sign bit set. + if (matches(curr, binary(LtS, any(), ival(0)))) { + return true; + } + + return false; + } + // fold constant factors into the offset void optimizeMemoryAccess(Expression*& ptr, Address& offset) { // ptr may be a const, but it isn't worth folding that in (we still have a diff --git a/test/lit/passes/optimize-instructions.wast b/test/lit/passes/optimize-instructions.wast index 574671076..9a5d33f87 100644 --- a/test/lit/passes/optimize-instructions.wast +++ b/test/lit/passes/optimize-instructions.wast @@ -11034,6 +11034,91 @@ (i64.ne (local.get $b) (i64.const 0)) )) ) + ;; CHECK: (func $optimize-combined-by-or-lessthan-zero (param $x i32) (param $y i32) (param $a i64) (param $b i64) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.lt_s + ;; CHECK-NEXT: (i32.or + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i64.lt_s + ;; CHECK-NEXT: (i64.or + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (local.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.or + ;; CHECK-NEXT: (i32.lt_s + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.lt_s + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.or + ;; CHECK-NEXT: (i32.lt_s + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.le_s + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.or + ;; CHECK-NEXT: (i32.lt_s + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.le_s + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $optimize-combined-by-or-lessthan-zero (param $x i32) (param $y i32) (param $a i64) (param $b i64) + ;; (i32(x) < 0) | (i32(y) < 0) ==> i32(x | y) < 0 + (drop (i32.or + (i32.lt_s (local.get $x) (i32.const 0)) + (i32.lt_s (local.get $y) (i32.const 0)) + )) + ;; (i64(x) < 0) | (i64(y) < 0) ==> i64(x | y) < 0 + (drop (i32.or + (i64.lt_s (local.get $a) (i64.const 0)) + (i64.lt_s (local.get $b) (i64.const 0)) + )) + + ;; skips + ;; (i32(x) < 0) | (i64(a) < 0) ==> skip + (drop (i32.or + (i32.lt_s (local.get $x) (i32.const 0)) + (i64.lt_s (local.get $a) (i64.const 0)) + )) + ;; (i32(x) <= 0) | (i32(y) < 0) ==> skip + (drop (i32.or + (i32.le_s (local.get $x) (i32.const 0)) + (i32.lt_s (local.get $y) (i32.const 0)) + )) + ;; (i32(x) < 1) | (i32(y) < 0) ==> skip + (drop (i32.or + (i32.lt_s (local.get $x) (i32.const 1)) + (i32.lt_s (local.get $y) (i32.const 0)) + )) + ) ;; CHECK: (func $optimize-relationals (param $x i32) (param $y i32) (param $X i64) (param $Y i64) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (i32.eq |