Lower signed binops to unsigned binops when possible (#2988)

This can unlock further instruction optimizations that do not apply to signed operations.

5 files changed, 228 insertions, 31 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 1c2445d5d..d77db8093 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -501,30 +501,42 @@ struct OptimizeInstructions
         }
         // math operations on a constant power of 2 right side can be optimized
         if (right->type == Type::i32) {
-          uint32_t c = right->value.geti32();
-          if (IsPowerOf2(c)) {
+          BinaryOp op;
+          int32_t c = right->value.geti32();
+          if (c >= 0 &&
+              (op = makeUnsignedBinaryOp(binary->op)) != InvalidBinary &&
+              Bits::getMaxBits(binary->left, this) <= 31) {
+            binary->op = op;
+          }
+          if (IsPowerOf2((uint32_t)c)) {
             switch (binary->op) {
               case MulInt32:
-                return optimizePowerOf2Mul(binary, c);
+                return optimizePowerOf2Mul(binary, (uint32_t)c);
               case RemUInt32:
-                return optimizePowerOf2URem(binary, c);
+                return optimizePowerOf2URem(binary, (uint32_t)c);
               case DivUInt32:
-                return optimizePowerOf2UDiv(binary, c);
+                return optimizePowerOf2UDiv(binary, (uint32_t)c);
               default:
                 break;
             }
           }
         }
         if (right->type == Type::i64) {
-          uint64_t c = right->value.geti64();
-          if (IsPowerOf2(c)) {
+          BinaryOp op;
+          int64_t c = right->value.geti64();
+          if (c >= 0 &&
+              (op = makeUnsignedBinaryOp(binary->op)) != InvalidBinary &&
+              Bits::getMaxBits(binary->left, this) <= 63) {
+            binary->op = op;
+          }
+          if (IsPowerOf2((uint64_t)c)) {
             switch (binary->op) {
               case MulInt64:
-                return optimizePowerOf2Mul(binary, c);
+                return optimizePowerOf2Mul(binary, (uint64_t)c);
               case RemUInt64:
-                return optimizePowerOf2URem(binary, c);
+                return optimizePowerOf2URem(binary, (uint64_t)c);
               case DivUInt64:
-                return optimizePowerOf2UDiv(binary, c);
+                return optimizePowerOf2UDiv(binary, (uint64_t)c);
               default:
                 break;
             }
@@ -1773,6 +1785,43 @@ private:
     }
   }
 
+  BinaryOp makeUnsignedBinaryOp(BinaryOp op) {
+    switch (op) {
+      case DivSInt32:
+        return DivUInt32;
+      case RemSInt32:
+        return RemUInt32;
+      case ShrSInt32:
+        return ShrUInt32;
+      case LtSInt32:
+        return LtUInt32;
+      case LeSInt32:
+        return LeUInt32;
+      case GtSInt32:
+        return GtUInt32;
+      case GeSInt32:
+        return GeUInt32;
+
+      case DivSInt64:
+        return DivUInt64;
+      case RemSInt64:
+        return RemUInt64;
+      case ShrSInt64:
+        return ShrUInt64;
+      case LtSInt64:
+        return LtUInt64;
+      case LeSInt64:
+        return LeUInt64;
+      case GtSInt64:
+        return GtUInt64;
+      case GeSInt64:
+        return GeUInt64;
+
+      default:
+        return InvalidBinary;
+    }
+  }
+
   bool isSymmetric(Binary* binary) {
     if (Properties::isSymmetric(binary)) {
       return true;
diff --git a/src/wasm.h b/src/wasm.h
index d2965b405..d41ad863a 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -225,8 +225,8 @@ enum BinaryOp {
   OrInt32,
   XorInt32,
   ShlInt32,
-  ShrUInt32,
   ShrSInt32,
+  ShrUInt32,
   RotLInt32,
   RotRInt32,
 
@@ -258,8 +258,8 @@ enum BinaryOp {
   OrInt64,
   XorInt64,
   ShlInt64,
-  ShrUInt64,
   ShrSInt64,
+  ShrUInt64,
   RotLInt64,
   RotRInt64,
 
diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt
index 8c21b8494..82b0af68a 100644
--- a/test/passes/optimize-instructions_all-features.txt
+++ b/test/passes/optimize-instructions_all-features.txt
@@ -49,25 +49,25 @@
    )
   )
   (drop
-   (i32.le_s
+   (i32.le_u
     (i32.const 1)
     (i32.const 2)
    )
   )
   (drop
-   (i32.lt_s
+   (i32.lt_u
     (i32.const 1)
     (i32.const 2)
    )
   )
   (drop
-   (i32.ge_s
+   (i32.ge_u
     (i32.const 1)
     (i32.const 2)
    )
   )
   (drop
-   (i32.gt_s
+   (i32.gt_u
     (i32.const 1)
     (i32.const 2)
    )
@@ -375,7 +375,7 @@
    )
   )
   (drop
-   (i32.lt_s
+   (i32.lt_u
     (i32.const 2000)
     (i32.const 3000)
    )
@@ -544,7 +544,7 @@
   )
   (drop
    (i32.and
-    (i32.gt_s
+    (i32.gt_u
      (i32.const 16)
      (i32.const 17)
     )
@@ -556,14 +556,14 @@
   )
   (drop
    (i32.and
-    (i32.gt_s
-     (i32.const 22)
-     (i32.const 23)
-    )
     (i32.gt_u
      (i32.const 20)
      (i32.const 21)
     )
+    (i32.gt_u
+     (i32.const 22)
+     (i32.const 23)
+    )
    )
   )
   (drop
@@ -887,9 +887,9 @@
    )
   )
   (drop
-   (i32.div_s
+   (i32.shr_u
+    (i32.const 1)
     (i32.const 1)
-    (i32.const 2)
    )
   )
   (drop
@@ -997,7 +997,7 @@
   (drop
    (i32.shr_s
     (i32.shl
-     (i32.shr_s
+     (i32.shr_u
       (i32.const 256)
       (i32.const 1)
      )
@@ -1007,13 +1007,13 @@
    )
   )
   (drop
-   (i32.shr_s
+   (i32.shr_u
     (i32.const 256)
     (i32.const 2)
    )
   )
   (drop
-   (i32.shr_s
+   (i32.shr_u
     (i32.const 128)
     (i32.const 35)
    )
@@ -1031,7 +1031,7 @@
    )
   )
   (drop
-   (i32.shr_s
+   (i32.shr_u
     (i32.and
      (i32.const -1)
      (i32.const 2147483647)
@@ -2325,7 +2325,7 @@
   )
  )
  (func $mix-shifts (result i32)
-  (i32.shr_s
+  (i32.shr_u
    (i32.shl
     (i32.const 23)
     (i32.const -61)
@@ -3826,6 +3826,89 @@
    )
   )
  )
+ (func $unsigned-context (param $x i32) (param $y i64)
+  (drop
+   (i32.div_u
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const 3)
+   )
+  )
+  (drop
+   (i32.div_s
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const -3)
+   )
+  )
+  (drop
+   (i32.div_s
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const -2147483648)
+   )
+  )
+  (drop
+   (i64.shr_u
+    (i64.and
+     (local.get $y)
+     (i64.const 9223372036854775807)
+    )
+    (i64.const 1)
+   )
+  )
+  (drop
+   (i64.div_s
+    (i64.and
+     (local.get $y)
+     (i64.const 9223372036854775807)
+    )
+    (i64.const -1)
+   )
+  )
+  (drop
+   (i32.rem_u
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const 3)
+   )
+  )
+  (drop
+   (i32.shr_u
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const 7)
+   )
+  )
+  (drop
+   (i32.ge_u
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const 7)
+   )
+  )
+  (drop
+   (i32.ge_s
+    (i32.and
+     (local.get $x)
+     (i32.const 2147483647)
+    )
+    (i32.const -7)
+   )
+  )
+ )
  (func $duplicate-elimination (param $x i32) (param $y i32) (param $z i32) (param $w f64)
   (drop
    (f64.abs
diff --git a/test/passes/optimize-instructions_all-features.wast b/test/passes/optimize-instructions_all-features.wast
index 1b03782e9..a89a16c1b 100644
--- a/test/passes/optimize-instructions_all-features.wast
+++ b/test/passes/optimize-instructions_all-features.wast
@@ -4354,6 +4354,71 @@
       )
     ))
   )
+  (func $unsigned-context (param $x i32) (param $y i64)
+    (drop (i32.div_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const 3)
+    ))
+    (drop (i32.div_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const -3) ;; skip
+    ))
+    (drop (i32.div_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const 0x80000000) ;; skip
+    ))
+    (drop (i64.div_s
+      (i64.and
+        (local.get $y)
+        (i64.const 0x7fffffffffffffff)
+      )
+      (i64.const 2)
+    ))
+     (drop (i64.div_s
+      (i64.and
+        (local.get $y)
+        (i64.const 0x7fffffffffffffff)
+      )
+      (i64.const -1) ;; skip
+    ))
+    (drop (i32.rem_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const 3)
+    ))
+    (drop (i32.shr_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const 7)
+    ))
+    (drop (i32.ge_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const 7)
+    ))
+    (drop (i32.ge_s
+      (i32.and
+        (local.get $x)
+        (i32.const 0x7fffffff)
+      )
+      (i32.const -7) ;; skip
+    ))
+  )
   (func $duplicate-elimination (param $x i32) (param $y i32) (param $z i32) (param $w f64)
     ;; unary
     (drop (f64.abs (f64.abs (local.get $w))))
diff --git a/test/passes/optimize-instructions_optimize-level=2_all-features_ignore-implicit-traps.txt b/test/passes/optimize-instructions_optimize-level=2_all-features_ignore-implicit-traps.txt
index 8c45bb46a..adb69fd90 100644
--- a/test/passes/optimize-instructions_optimize-level=2_all-features_ignore-implicit-traps.txt
+++ b/test/passes/optimize-instructions_optimize-level=2_all-features_ignore-implicit-traps.txt
@@ -257,7 +257,7 @@
   (if
    (i32.eqz
     (i32.and
-     (i32.lt_s
+     (i32.lt_u
       (i32.and
        (i32.shr_s
         (i32.shl
@@ -296,7 +296,7 @@
      (local.tee $1
       (i32.const 0)
      )
-     (i32.lt_s
+     (i32.lt_u
       (i32.and
        (i32.shr_s
         (i32.shl