Fix comparisons of sign-extends to weird constants (#956)

* fix eq/ne of sign-ext with a constant, when the constant can never be equal to it as it has the effective sign bit but not the upper bits above it set, which the sign-ext would emit

3 files changed, 248 insertions, 9 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index ad828dafc..c1787b57d 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -423,18 +423,43 @@ struct OptimizeInstructions : public WalkerPass<PostWalker<OptimizeInstructions,
         }
       } else if (binary->op == EqInt32 || binary->op == NeInt32) {
         if (auto* c = binary->right->dynCast<Const>()) {
+          if (binary->op == EqInt32 && c->value.geti32() == 0) {
+            // equal 0 => eqz
+            return Builder(*getModule()).makeUnary(EqZInt32, binary->left);
+          }
           if (auto* ext = Properties::getSignExtValue(binary->left)) {
             // we are comparing a sign extend to a constant, which means we can use a cheaper zext
             auto bits = Properties::getSignExtBits(binary->left);
             binary->left = makeZeroExt(ext, bits);
-            // the const we compare to only needs the relevant bits
-            c->value = c->value.and_(Literal(Bits::lowBitMask(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 = 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 < 31);
+              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
+              c->value = c->value.and_(Literal(Bits::lowBitMask(bits)));
+            }
             return binary;
           }
-          if (binary->op == EqInt32 && c->value.geti32() == 0) {
-            // equal 0 => eqz
-            return Builder(*getModule()).makeUnary(EqZInt32, binary->left);
-          }
         } else if (auto* left = Properties::getSignExtValue(binary->left)) {
           if (auto* right = Properties::getSignExtValue(binary->right)) {
             auto bits = Properties::getSignExtBits(binary->left);
diff --git a/test/passes/optimize-instructions.txt b/test/passes/optimize-instructions.txt
index 41d45d57f..03edc6e4c 100644
--- a/test/passes/optimize-instructions.txt
+++ b/test/passes/optimize-instructions.txt
@@ -541,7 +541,16 @@
      (get_local $0)
      (i32.const 255)
     )
-    (i32.const 255)
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $0)
+     (i32.const 255)
+    )
+    (i32.const 107)
    )
   )
   (drop
@@ -1103,7 +1112,25 @@
      (get_local $0)
      (i32.const 255)
     )
-    (i32.const 232)
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.ne
+    (i32.and
+     (get_local $0)
+     (i32.const 255)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.ne
+    (i32.and
+     (get_local $0)
+     (i32.const 255)
+    )
+    (i32.const 107)
    )
   )
   (drop
@@ -1790,4 +1817,69 @@
    )
   )
  )
+ (func $fuzz-comp-impossible (type $5) (param $x i32)
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 65535)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 255)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 255)
+    )
+    (i32.const 127)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 255)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 255)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 255)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i32.eq
+    (i32.and
+     (get_local $x)
+     (i32.const 255)
+    )
+    (i32.const 252)
+   )
+  )
+ )
 )
diff --git a/test/passes/optimize-instructions.wast b/test/passes/optimize-instructions.wast
index 8ef6f67a5..eccbf1268 100644
--- a/test/passes/optimize-instructions.wast
+++ b/test/passes/optimize-instructions.wast
@@ -491,7 +491,19 @@
           )
           (i32.const 24)
         )
-        (i32.const 32767) ;; non-zero and bigger than the mask
+        (i32.const 32767) ;; non-zero and bigger than the mask, with sign bit
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $0)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const -149) ;; non-zero and bigger than the mask, without sign bit
       )
     )
     ;; eq of two sign-ext, can both be a zext
@@ -1370,6 +1382,30 @@
           )
           (i32.const 24)
         )
+        (i32.const 64872) ;; no sign bit
+      )
+    )
+    (drop
+      (i32.ne
+        (i32.shr_s
+          (i32.shl
+            (get_local $0)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const -149) ;; no sign bit, not all ones
+      )
+    )
+    (drop
+      (i32.ne
+        (i32.shr_s
+          (i32.shl
+            (get_local $0)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
         (i32.const 111)
       )
     )
@@ -2181,4 +2217,90 @@
       )
     )
   )
+  (func $fuzz-comp-impossible (param $x i32)
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 16)
+          )
+          (i32.const 16)
+        )
+        (i32.const 65535) ;; impossible to be equal, the effective sign bit is set, but not the higher bits, which the sign-ext will set on the non-const value
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const 255)
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const 127) ;; safe
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const 128) ;; unsafe again
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const 4223) ;; more big bits, so sign bit though
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const 4224) ;; more big bits
+      )
+    )
+    (drop
+      (i32.eq
+        (i32.shr_s
+          (i32.shl
+            (get_local $x)
+            (i32.const 24)
+          )
+          (i32.const 24)
+        )
+        (i32.const -4) ;; safe even with more big bits, as they are all 1s
+      )
+    )
+  )
 )