diff options
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 36 | ||||
| -rw-r--r-- | test/lit/passes/optimize-instructions-mvp.wast | 80 |
2 files changed, 90 insertions, 26 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 41f7a9e11..a4054e49b 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -3761,7 +3761,11 @@ private: // Returns true if the given binary operation can overflow. If we can't be // sure either way, we return true, assuming the worst. - bool canOverflow(Binary* binary) { + // + // We can check for an unsigned overflow (more than the max number of bits) or + // a signed one (where even reaching the sign bit is an overflow, as that + // would turn us from positive to negative). + bool canOverflow(Binary* binary, bool signed_) { using namespace Abstract; // If we know nothing about a limit on the amount of bits on either side, @@ -3774,17 +3778,23 @@ private: } if (binary->op == getBinary(binary->type, Add)) { - // Proof this cannot overflow: - // - // left + right < 2^leftMaxBits + 2^rightMaxBits (1) - // <= 2^(typeMaxBits-1) + 2^(typeMaxBits-1) (2) - // = 2^typeMaxBits (3) - // - // (1) By the definition of the max bits (e.g. an int32 has 32 max bits, - // and its max value is 2^32 - 1, which is < 2^32). - // (2) By the above checks and early returns. - // (3) 2^x + 2^x === 2*2^x === 2^(x+1) - return false; + if (!signed_) { + // Proof this cannot overflow: + // + // left + right < 2^leftMaxBits + 2^rightMaxBits (1) + // <= 2^(typeMaxBits-1) + 2^(typeMaxBits-1) (2) + // = 2^typeMaxBits (3) + // + // (1) By the definition of the max bits (e.g. an int32 has 32 max bits, + // and its max value is 2^32 - 1, which is < 2^32). + // (2) By the above checks and early returns. + // (3) 2^x + 2^x === 2*2^x === 2^(x+1) + return false; + } + + // For a signed comparison, check that the total cannot reach the sign + // bit. + return leftMaxBits + rightMaxBits >= typeMaxBits; } // TODO subtraction etc. @@ -4102,7 +4112,7 @@ private: Const* c2; if (matches(curr, binary(binary(&add, Add, any(), ival(&c1)), ival(&c2))) && - !canOverflow(add)) { + !canOverflow(add, isSignedOp(curr->op))) { // We want to subtract C2-C1 or C1-C2. When doing so, we must avoid an // overflow in that subtraction (so that we keep all the math here // properly linear in the mathematical sense). Overflows that concern diff --git a/test/lit/passes/optimize-instructions-mvp.wast b/test/lit/passes/optimize-instructions-mvp.wast index db864087d..d5388ffd1 100644 --- a/test/lit/passes/optimize-instructions-mvp.wast +++ b/test/lit/passes/optimize-instructions-mvp.wast @@ -16145,12 +16145,15 @@ ;; CHECK: (func $lt-added-constant (param $x i32) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (i32.lt_u - ;; CHECK-NEXT: (i32.shr_u - ;; CHECK-NEXT: (local.get $x) - ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.lt_s + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (i32.shr_u + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 5) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (i32.const 6) + ;; CHECK-NEXT: (i32.const 11) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) @@ -16813,21 +16816,21 @@ ;; CHECK-NEXT: (i32.load ;; CHECK-NEXT: (i32.const 0) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 16) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (i32.const 1) ;; CHECK-NEXT: ) (func $skip-added-constants-mix (result i32) ;; A case of one negative and one positive constant. Here we have - ;; [max 31 bits] + 10 >=_s -20 which is always true. + ;; [max 16 bits] + 10 >=_s -20 which is always true. (i32.ge_s (i32.add (i32.shr_u (i32.load (i32.const 0) ) - (i32.const 1) + (i32.const 16) ) (i32.const 10) ) @@ -16842,7 +16845,7 @@ ;; CHECK-NEXT: (i32.load ;; CHECK-NEXT: (i32.const 0) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 16) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (i32.const 20) ;; CHECK-NEXT: ) @@ -16858,7 +16861,7 @@ (i32.load (i32.const 0) ) - (i32.const 1) + (i32.const 16) ) (i32.const -20) ) @@ -16872,25 +16875,76 @@ ;; CHECK-NEXT: (i32.load ;; CHECK-NEXT: (i32.const 0) ;; CHECK-NEXT: ) - ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 16) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (i32.const 1) ;; CHECK-NEXT: ) (func $skip-added-constants-mix-flip-other (result i32) ;; As above, but with the sign the same while the absolute values are - ;; flipped. Here we have [max 31 bits] + 20 >=_s -10 which is always true. + ;; flipped. Here we have [max 16 bits] + 20 >=_s -10 which is always true. (i32.ge_s (i32.add (i32.shr_u (i32.load (i32.const 0) ) - (i32.const 1) + (i32.const 16) ) (i32.const 20) ) (i32.const -10) ) ) + + ;; CHECK: (func $skip-added-constants-signed-overflow (result i32) + ;; CHECK-NEXT: (i64.lt_s + ;; CHECK-NEXT: (i64.add + ;; CHECK-NEXT: (i64.or + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: (i64.const 9223372036854775807) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i64.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $skip-added-constants-signed-overflow (result i32) + ;; Adding 1 to 0x7fffffffffffffff turns it into 0x8000000000000000, which + ;; when signed is -1, that is, we overflow. So we can't subtract 1 from the + ;; gt_s arms. + ;; (The i64.or is needed to avoid other opts.) + (i64.gt_s + (i64.const 2) + (i64.add + (i64.const 1) + (i64.or + (i64.const 0) + (i64.const 0x7fffffffffffffff) + ) + ) + ) + ) + + ;; CHECK: (func $added-constants-unsigned (result i32) + ;; CHECK-NEXT: (i64.eqz + ;; CHECK-NEXT: (i64.or + ;; CHECK-NEXT: (i64.const 0) + ;; CHECK-NEXT: (i64.const 9223372036854775807) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $added-constants-unsigned (result i32) + ;; As above, but unsigned. This is ok, as it can't overflow as unsigned. + (i64.gt_u + (i64.const 2) + (i64.add + (i64.const 1) + (i64.or + (i64.const 0) + (i64.const 0x7fffffffffffffff) + ) + ) + ) + ) ) |