summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/passes/OptimizeInstructions.cpp79
-rw-r--r--test/passes/optimize-instructions_all-features.txt79
-rw-r--r--test/passes/optimize-instructions_fuzz-exec.txt67
-rw-r--r--test/passes/optimize-instructions_fuzz-exec.wast78
4 files changed, 217 insertions, 86 deletions
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index dd088b03b..2ca670f89 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -498,47 +498,50 @@ struct OptimizeInstructions
} else if (binary->op == EqInt32 || binary->op == NeInt32) {
if (auto* c = binary->right->dynCast<Const>()) {
if (auto* ext = Properties::getSignExtValue(binary->left)) {
- // we are comparing a sign extend to a constant, which means we can
- // use a cheaper zext
+ // We are comparing a sign extend to a constant, which means we can
+ // use a cheaper zero-extend in some cases. That is,
+ // (x << S) >> S ==/!= C => x & T ==/!= C
+ // where S and T are the matching values for sign/zero extend of the
+ // same size. For example, for an effective 8-bit value:
+ // (x << 24) >> 24 ==/!= C => x & 255 ==/!= C
+ //
+ // The key thing to track here are the upper bits plus the sign bit;
+ // call those the "relevant bits". This is crucial because x is
+ // sign-extended, that is, its effective sign bit is spread to all
+ // the upper bits, which means that the relevant bits on the left
+ // side are either all 0, or all 1.
auto bits = Properties::getSignExtBits(binary->left);
- binary->left = makeZeroExt(ext, bits);
- // when we replace the sign-ext of the non-constant with a zero-ext,
- // we are forcing the high bits to be all zero, instead of all zero
- // or all one depending on the sign bit. so we may be changing the
- // high bits from all one to all zero:
- // * if the constant value's higher bits are mixed, then it can't
- // be equal anyhow
- // * if they are all zero, we may get a false true if the
- // non-constant's upper bits were one. this can only happen if
- // the non-constant's sign bit is set, so this false true is a
- // risk only if the constant's sign bit is set (otherwise,
- // false). But a constant with a sign bit but with upper bits
- // zero is impossible to be equal to a sign-extended value
- // anyhow, so the entire thing is false.
- // * if they were all one, we may get a false false, if the only
- // difference is in those upper bits. that means we are equal on
- // the other bits, including the sign bit. so we can just mask
- // off the upper bits in the constant value, in this case,
- // forcing them to zero like we do in the zero-extend.
- int32_t constValue = c->value.geti32();
- auto upperConstValue = constValue & ~Bits::lowBitMask(bits);
- uint32_t count = Bits::popCount(upperConstValue);
- auto constSignBit = constValue & (1 << (bits - 1));
- if ((count > 0 && count < 32 - bits) ||
- (constSignBit && count == 0)) {
- // mixed or [zero upper const bits with sign bit set]; the
- // compared values can never be identical, so force something
- // definitely impossible even after zext
- assert(bits < 32);
- c->value = Literal(int32_t(0x80000000));
- // TODO: if no side effects, we can just replace it all with 1 or
- // 0
- } else {
- // otherwise, they are all ones, so we can mask them off as
- // mentioned before
+ uint32_t right = c->value.geti32();
+ uint32_t numRelevantBits = 32 - bits + 1;
+ uint32_t setRelevantBits =
+ Bits::popCount(right >> uint32_t(bits - 1));
+ // If all the relevant bits on C are zero
+ // then we can mask off the high bits instead of sign-extending x.
+ // This is valid because if x is negative, then the comparison was
+ // false before (negative vs positive), and will still be false
+ // as the sign bit will remain to cause a difference. And if x is
+ // positive then the upper bits would be zero anyhow.
+ if (setRelevantBits == 0) {
+ binary->left = makeZeroExt(ext, bits);
+ return binary;
+ } else if (setRelevantBits == numRelevantBits) {
+ // If all those bits are one, then we can do something similar if
+ // we also zero-extend on the right as well. This is valid
+ // because, as in the previous case, the sign bit differentiates
+ // the two sides when they are different, and if the sign bit is
+ // identical, then the upper bits don't matter, so masking them
+ // off both sides is fine.
+ binary->left = makeZeroExt(ext, bits);
c->value = c->value.and_(Literal(Bits::lowBitMask(bits)));
+ return binary;
+ } else {
+ // Otherwise, C's relevant bits are mixed, and then the two sides
+ // can never be equal, as the left side's bits cannot be mixed.
+ Builder builder(*getModule());
+ // The result is either always true, or always false.
+ c->value = Literal::makeFromInt32(binary->op == NeInt32, c->type);
+ return builder.makeSequence(builder.makeDrop(ext), c);
}
- return binary;
}
} else if (auto* left = Properties::getSignExtValue(binary->left)) {
if (auto* right = Properties::getSignExtValue(binary->right)) {
diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt
index 3b557693d..d6c98bc0a 100644
--- a/test/passes/optimize-instructions_all-features.txt
+++ b/test/passes/optimize-instructions_all-features.txt
@@ -896,21 +896,19 @@
)
)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $0)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 0)
)
)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $0)
- (i32.const 255)
)
- (i32.const 107)
+ (i32.const 0)
)
)
(drop
@@ -1458,30 +1456,27 @@
)
(func $sign-ext-ne (param $0 i32) (param $1 i32)
(drop
- (i32.ne
- (i32.and
+ (block (result i32)
+ (drop
(local.get $0)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 1)
)
)
(drop
- (i32.ne
- (i32.and
+ (block (result i32)
+ (drop
(local.get $0)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 1)
)
)
(drop
- (i32.ne
- (i32.and
+ (block (result i32)
+ (drop
(local.get $0)
- (i32.const 255)
)
- (i32.const 107)
+ (i32.const 1)
)
)
(drop
@@ -2176,21 +2171,19 @@
)
(func $fuzz-comp-impossible (param $x i32)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $x)
- (i32.const 65535)
)
- (i32.const -2147483648)
+ (i32.const 0)
)
)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $x)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 0)
)
)
(drop
@@ -2203,30 +2196,27 @@
)
)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $x)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 0)
)
)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $x)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 0)
)
)
(drop
- (i32.eq
- (i32.and
+ (block (result i32)
+ (drop
(local.get $x)
- (i32.const 255)
)
- (i32.const -2147483648)
+ (i32.const 0)
)
)
(drop
@@ -2401,13 +2391,10 @@
)
)
(func $sign-ext-1-and-ne (result i32)
- (i32.ne
- (i32.and
- (call $sign-ext-1-and-ne)
- (i32.const 2147483647)
- )
- (i32.const -2147483648)
+ (drop
+ (call $sign-ext-1-and-ne)
)
+ (i32.const 1)
)
(func $neg-shifts-and-255 (result i32)
(i32.and
diff --git a/test/passes/optimize-instructions_fuzz-exec.txt b/test/passes/optimize-instructions_fuzz-exec.txt
index 5da803fb1..e8985222d 100644
--- a/test/passes/optimize-instructions_fuzz-exec.txt
+++ b/test/passes/optimize-instructions_fuzz-exec.txt
@@ -257,11 +257,46 @@
[LoggingExternalInterface logging 1]
[LoggingExternalInterface logging 1]
[LoggingExternalInterface logging 0]
+[fuzz-exec] calling call-compare-maybe-signed-eq
+[fuzz-exec] note result: call-compare-maybe-signed-eq => 0
+[fuzz-exec] calling call-compare-maybe-signed-ne
+[fuzz-exec] note result: call-compare-maybe-signed-ne => 1
(module
(type $i32_=>_none (func (param i32)))
+ (type $none_=>_i32 (func (result i32)))
+ (type $i32_=>_i32 (func (param i32) (result i32)))
+ (type $none_=>_none (func))
(import "fuzzing-support" "log-i32" (func $log (param i32)))
- (export "foo" (func $0))
- (func $0 (param $0 i32)
+ (export "foo" (func $1))
+ (export "call-compare-maybe-signed-eq" (func $3))
+ (export "call-compare-maybe-signed-ne" (func $5))
+ (func $signed-comparison-to-unsigned
+ (call $log
+ (block (result i32)
+ (drop
+ (i32.const -25749)
+ )
+ (i32.const 0)
+ )
+ )
+ (call $log
+ (block (result i32)
+ (drop
+ (i32.const -25749)
+ )
+ (i32.const 0)
+ )
+ )
+ (call $log
+ (block (result i32)
+ (drop
+ (i32.const -25749)
+ )
+ (i32.const 1)
+ )
+ )
+ )
+ (func $1 (param $0 i32)
(call $log
(i32.le_s
(i32.sub
@@ -286,8 +321,36 @@
)
)
)
+ (func $compare-maybe-signed-eq (param $0 i32) (result i32)
+ (drop
+ (local.get $0)
+ )
+ (i32.const 0)
+ )
+ (func $3 (result i32)
+ (call $compare-maybe-signed-eq
+ (i32.const 128)
+ )
+ )
+ (func $compare-maybe-signed-ne (param $0 i32) (result i32)
+ (drop
+ (local.get $0)
+ )
+ (i32.const 1)
+ )
+ (func $5 (result i32)
+ (call $compare-maybe-signed-ne
+ (i32.const 128)
+ )
+ )
)
[fuzz-exec] calling foo
[LoggingExternalInterface logging 1]
[LoggingExternalInterface logging 1]
[LoggingExternalInterface logging 0]
+[fuzz-exec] calling call-compare-maybe-signed-eq
+[fuzz-exec] note result: call-compare-maybe-signed-eq => 0
+[fuzz-exec] calling call-compare-maybe-signed-ne
+[fuzz-exec] note result: call-compare-maybe-signed-ne => 1
+[fuzz-exec] comparing call-compare-maybe-signed-eq
+[fuzz-exec] comparing call-compare-maybe-signed-ne
diff --git a/test/passes/optimize-instructions_fuzz-exec.wast b/test/passes/optimize-instructions_fuzz-exec.wast
index 8d2e1beee..8bd43b694 100644
--- a/test/passes/optimize-instructions_fuzz-exec.wast
+++ b/test/passes/optimize-instructions_fuzz-exec.wast
@@ -205,6 +205,47 @@
)
(module
(import "fuzzing-support" "log-i32" (func $log (param i32)))
+ (func $signed-comparison-to-unsigned
+ (call $log
+ (i32.eq ;; should be false
+ (i32.shr_s ;; 0x0000006b after the sign-extend
+ (i32.shl
+ (i32.const -25749) ;; 0xffff9b6b
+ (i32.const 24)
+ )
+ (i32.const 24)
+ )
+ (i32.const -149) ;; 0xffffff6b - high bits are set, but not sign bit
+ )
+ )
+ ;; the same, with mixed high bits. mixed bits mean the two sides can never be
+ ;; equal, so the eq is always false
+ (call $log
+ (i32.eq
+ (i32.shr_s
+ (i32.shl
+ (i32.const -25749)
+ (i32.const 24)
+ )
+ (i32.const 24)
+ )
+ (i32.const 0xffffeb)
+ )
+ )
+ ;; the same, with !=, so the result is always true
+ (call $log
+ (i32.ne
+ (i32.shr_s
+ (i32.shl
+ (i32.const -25749)
+ (i32.const 24)
+ )
+ (i32.const 24)
+ )
+ (i32.const 0xffffeb)
+ )
+ )
+ )
(func "foo" (param $0 i32)
;; 8 - 0x80000000 < 0
;;
@@ -246,4 +287,41 @@
)
)
)
+ ;; similar, but with the value compared to having the sign bit set but no
+ ;; upper bits
+ (func $compare-maybe-signed-eq (param $0 i32) (result i32)
+ (i32.eq
+ (i32.shr_s
+ (i32.shl
+ (local.get $0)
+ (i32.const 24)
+ )
+ (i32.const 24)
+ )
+ (i32.const 128)
+ )
+ )
+ (func "call-compare-maybe-signed-eq" (result i32)
+ (call $compare-maybe-signed-eq
+ (i32.const 128)
+ )
+ )
+ ;; the same with !=
+ (func $compare-maybe-signed-ne (param $0 i32) (result i32)
+ (i32.ne
+ (i32.shr_s
+ (i32.shl
+ (local.get $0)
+ (i32.const 24)
+ )
+ (i32.const 24)
+ )
+ (i32.const 128)
+ )
+ )
+ (func "call-compare-maybe-signed-ne" (result i32)
+ (call $compare-maybe-signed-ne
+ (i32.const 128)
+ )
+ )
)
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 18:06:22 +0000