diff options
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 75 | ||||
| -rw-r--r-- | test/lit/passes/optimize-instructions.wast | 102 |
2 files changed, 165 insertions, 12 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 54a791606..bde60e093 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -2510,12 +2510,37 @@ private: if (matches(curr->left, unary(EqZ, any(&x))) && matches(curr->right, unary(EqZ, any(&y))) && x->type == y->type) { auto* inner = curr->left->cast<Unary>(); - inner->value = Builder(*getModule()) - .makeBinary(Abstract::getBinary(x->type, Or), x, y); + inner->value = + Builder(*getModule()).makeBinary(getBinary(x->type, Or), x, y); return inner; } } { + // Binary operations that inverse a bitwise AND can be + // reordered. If F(x) = binary(x, c), and F(x) preserves AND, + // 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->left, binary(&bx, any(&x), ival(&cx))) && + matches(curr->right, binary(&by, any(&y), ival(&cy))) && + bx->op == by->op && x->type == y->type && cx->value == cy->value && + inversesAnd(bx)) { + by->op = getBinary(x->type, Or); + by->type = x->type; + by->left = x; + by->right = y; + bx->left = by; + return bx; + } + } + { // Binary operations that preserve a bitwise AND can be // reordered. If F(x) = binary(x, c), and F(x) preserves AND, // that is, @@ -2528,14 +2553,15 @@ private: Binary *bx, *by; Expression *x, *y; Const *cx, *cy; - if (matches(curr, - binary(AndInt32, - binary(&bx, any(&x), ival(&cx)), - binary(&by, any(&y), ival(&cy)))) && + if (matches(curr->left, binary(&bx, any(&x), ival(&cx))) && + matches(curr->right, binary(&by, any(&y), ival(&cy))) && bx->op == by->op && x->type == y->type && cx->value == cy->value && preserveAnd(bx)) { - bx->left = Builder(*getModule()) - .makeBinary(Abstract::getBinary(x->type, And), x, y); + by->op = getBinary(x->type, And); + by->type = x->type; + by->left = x; + by->right = y; + bx->left = by; return bx; } } @@ -2590,7 +2616,7 @@ private: matches(curr->right, binary(&by, any(&y), ival(&cy))) && bx->op == by->op && x->type == y->type && cx->value == cy->value && inversesOr(bx)) { - by->op = Abstract::getBinary(x->type, And); + by->op = getBinary(x->type, And); by->type = x->type; by->left = x; by->right = y; @@ -2615,7 +2641,7 @@ private: matches(curr->right, binary(&by, any(&y), ival(&cy))) && bx->op == by->op && x->type == y->type && cx->value == cy->value && preserveOr(bx)) { - by->op = Abstract::getBinary(x->type, Or); + by->op = getBinary(x->type, Or); by->type = x->type; by->left = x; by->right = y; @@ -2645,13 +2671,11 @@ private: 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; } @@ -2701,6 +2725,33 @@ private: return true; } + // (x == -1) & (y == -1) ==> (x & y) == -1 + if (matches(curr, binary(Eq, any(), ival(-1)))) { + return true; + } + + return false; + } + + // Check whether an operation inverses the And operation to Or, 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 inversesAnd(Binary* curr) { + using namespace Abstract; + using namespace Match; + + // (x >= 0) & (y >= 0) ==> (x | y) >= 0 + if (matches(curr, binary(GeS, any(), ival(0)))) { + return true; + } + return false; } diff --git a/test/lit/passes/optimize-instructions.wast b/test/lit/passes/optimize-instructions.wast index 5d8d0473f..70e28cfd6 100644 --- a/test/lit/passes/optimize-instructions.wast +++ b/test/lit/passes/optimize-instructions.wast @@ -11253,6 +11253,108 @@ (i64.lt_s (local.get $b) (i64.const 0)) )) ) + ;; CHECK: (func $optimize-combined-by-and-greatequal-zero (param $x i32) (param $y i32) (param $a i64) (param $b i64) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.ge_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.ge_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.and + ;; CHECK-NEXT: (i32.ge_s + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.ge_s + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $optimize-combined-by-and-greatequal-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.and + (i32.ge_s (local.get $x) (i32.const 0)) + (i32.ge_s (local.get $y) (i32.const 0)) + )) + ;; (i64(x) >= 0) & (i64(y) >= 0) ==> i64(x | y) >= 0 + (drop (i32.and + (i64.ge_s (local.get $a) (i64.const 0)) + (i64.ge_s (local.get $b) (i64.const 0)) + )) + + ;; skips + ;; (i32(x) >= 0) & (i64(y) >= 0) ==> skip + (drop (i32.and + (i32.ge_s (local.get $x) (i32.const 0)) + (i64.ge_s (local.get $a) (i64.const 0)) + )) + ) + ;; CHECK: (func $optimize-combined-by-and-equal-neg-one (param $x i32) (param $y i32) (param $a i64) (param $b i64) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.eq + ;; CHECK-NEXT: (i32.and + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const -1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i64.eq + ;; CHECK-NEXT: (i64.and + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (local.get $b) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.const -1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.and + ;; CHECK-NEXT: (i32.eq + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const -1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.eq + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (i64.const -1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $optimize-combined-by-and-equal-neg-one (param $x i32) (param $y i32) (param $a i64) (param $b i64) + ;; (i32(x) == -1) & (i32(y) == -1) ==> i32(x & y) == -1 + (drop (i32.and + (i32.eq (local.get $x) (i32.const -1)) + (i32.eq (local.get $y) (i32.const -1)) + )) + ;; (i64(x) == -1) & (i64(y) == -1) ==> i64(x & y) == -1 + (drop (i32.and + (i64.eq (local.get $a) (i64.const -1)) + (i64.eq (local.get $b) (i64.const -1)) + )) + + ;; skips + ;; (i32(x) == -1) & (i64(y) == -1) ==> skip + (drop (i32.and + (i32.eq (local.get $x) (i32.const -1)) + (i64.eq (local.get $a) (i64.const -1)) + )) + ) ;; CHECK: (func $optimize-relationals (param $x i32) (param $y i32) (param $X i64) (param $Y i64) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (i32.eq |