Canonicalize relationals as well (#3303)

13 files changed, 243 insertions, 87 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 20cdeee19..003f204a9 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -210,7 +210,7 @@ struct OptimizeInstructions
       return nullptr;
     }
     if (auto* binary = curr->dynCast<Binary>()) {
-      if (isSymmetric(binary)) {
+      if (isSymmetricOrRelational(binary)) {
         canonicalize(binary);
       }
     }
@@ -895,9 +895,12 @@ private:
   // Canonicalizing the order of a symmetric binary helps us
   // write more concise pattern matching code elsewhere.
   void canonicalize(Binary* binary) {
-    assert(isSymmetric(binary));
+    assert(isSymmetricOrRelational(binary));
     auto swap = [&]() {
       assert(canReorder(binary->left, binary->right));
+      if (binary->isRelational()) {
+        binary->op = reverseRelationalOp(binary->op);
+      }
       std::swap(binary->left, binary->right);
     };
     auto maybeSwap = [&]() {
@@ -2183,6 +2186,81 @@ private:
     }
   }
 
+  BinaryOp reverseRelationalOp(BinaryOp op) {
+    switch (op) {
+      case EqInt32:
+        return EqInt32;
+      case NeInt32:
+        return NeInt32;
+      case LtSInt32:
+        return GtSInt32;
+      case LtUInt32:
+        return GtUInt32;
+      case LeSInt32:
+        return GeSInt32;
+      case LeUInt32:
+        return GeUInt32;
+      case GtSInt32:
+        return LtSInt32;
+      case GtUInt32:
+        return LtUInt32;
+      case GeSInt32:
+        return LeSInt32;
+      case GeUInt32:
+        return LeUInt32;
+
+      case EqInt64:
+        return EqInt64;
+      case NeInt64:
+        return NeInt64;
+      case LtSInt64:
+        return GtSInt64;
+      case LtUInt64:
+        return GtUInt64;
+      case LeSInt64:
+        return GeSInt64;
+      case LeUInt64:
+        return GeUInt64;
+      case GtSInt64:
+        return LtSInt64;
+      case GtUInt64:
+        return LtUInt64;
+      case GeSInt64:
+        return LeSInt64;
+      case GeUInt64:
+        return LeUInt64;
+
+      case EqFloat32:
+        return EqFloat32;
+      case NeFloat32:
+        return NeFloat32;
+      case LtFloat32:
+        return GtFloat32;
+      case LeFloat32:
+        return GeFloat32;
+      case GtFloat32:
+        return LtFloat32;
+      case GeFloat32:
+        return LeFloat32;
+
+      case EqFloat64:
+        return EqFloat64;
+      case NeFloat64:
+        return NeFloat64;
+      case LtFloat64:
+        return GtFloat64;
+      case LeFloat64:
+        return GeFloat64;
+      case GtFloat64:
+        return LtFloat64;
+      case GeFloat64:
+        return LeFloat64;
+
+      default:
+        return InvalidBinary;
+    }
+  }
+
   BinaryOp makeUnsignedBinaryOp(BinaryOp op) {
     switch (op) {
       case DivSInt32:
@@ -2220,8 +2298,8 @@ private:
     }
   }
 
-  bool isSymmetric(Binary* binary) {
-    if (Properties::isSymmetric(binary)) {
+  bool isSymmetricOrRelational(Binary* binary) {
+    if (Properties::isSymmetric(binary) || binary->isRelational()) {
       return true;
     }
     switch (binary->op) {
diff --git a/test/passes/O3_low-memory-unused_metrics.txt b/test/passes/O3_low-memory-unused_metrics.txt
index 4989dec5f..f148cacd8 100644
--- a/test/passes/O3_low-memory-unused_metrics.txt
+++ b/test/passes/O3_low-memory-unused_metrics.txt
@@ -1142,9 +1142,9 @@ total
                             )
                            )
                           )
-                          (i32.gt_u
-                           (local.get $5)
+                          (i32.lt_u
                            (local.get $3)
+                           (local.get $5)
                           )
                          )
                         )
@@ -1287,8 +1287,7 @@ total
                     )
                    )
                    (if
-                    (i32.ge_u
-                     (local.get $6)
+                    (i32.le_u
                      (i32.load16_u offset=20
                       (local.tee $5
                        (i32.load offset=28
@@ -1296,6 +1295,7 @@ total
                        )
                       )
                      )
+                     (local.get $6)
                     )
                     (block
                      (local.set $3
@@ -1482,9 +1482,9 @@ total
                           )
                          )
                         )
-                        (i32.gt_u
-                         (local.get $5)
+                        (i32.lt_u
                          (local.get $3)
+                         (local.get $5)
                         )
                        )
                       )
@@ -1795,9 +1795,9 @@ total
                       )
                      )
                     )
-                    (i32.gt_u
-                     (local.get $5)
+                    (i32.lt_u
                      (local.get $3)
+                     (local.get $5)
                     )
                    )
                   )
@@ -2030,16 +2030,16 @@ total
        (block
         (block $label$52
          (br_if $label$52
-          (i32.le_u
+          (i32.ge_u
+           (i32.load offset=12
+            (local.get $2)
+           )
            (i32.add
             (i32.load offset=20
              (local.get $2)
             )
             (i32.const 2)
            )
-           (i32.load offset=12
-            (local.get $2)
-           )
           )
          )
          (br_if $label$52
@@ -2060,9 +2060,9 @@ total
                )
               )
              )
-             (i32.gt_u
-              (local.get $5)
+             (i32.lt_u
               (local.get $3)
+              (local.get $5)
              )
             )
            )
@@ -2141,7 +2141,10 @@ total
          )
         )
         (br_if $label$6
-         (i32.gt_u
+         (i32.lt_u
+          (i32.load offset=12
+           (local.get $2)
+          )
           (i32.add
            (local.tee $3
             (i32.load offset=20
@@ -2150,9 +2153,6 @@ total
            )
            (i32.const 2)
           )
-          (i32.load offset=12
-           (local.get $2)
-          )
          )
         )
         (local.set $4
@@ -2344,9 +2344,9 @@ total
        )
       )
       (br_if $label$53
-       (i32.lt_s
-        (local.get $7)
+       (i32.gt_s
         (local.get $1)
+        (local.get $7)
        )
       )
       (br_if $label$53
@@ -3024,9 +3024,9 @@ total
             )
            )
           )
-          (i32.gt_u
-           (local.get $4)
+          (i32.lt_u
            (local.get $1)
+           (local.get $4)
           )
          )
         )
diff --git a/test/passes/O4_disable-bulk-memory.txt b/test/passes/O4_disable-bulk-memory.txt
index 19d07a81e..dfb04c088 100644
--- a/test/passes/O4_disable-bulk-memory.txt
+++ b/test/passes/O4_disable-bulk-memory.txt
@@ -196,8 +196,7 @@
   (f64.store offset=24
    (local.tee $1
     (if (result i32)
-     (i32.lt_u
-      (i32.const 0)
+     (i32.gt_u
       (i32.shr_u
        (i32.load
         (local.tee $1
@@ -208,6 +207,7 @@
        )
        (i32.const 2)
       )
+      (i32.const 0)
      )
      (i32.load offset=8
       (local.get $1)
@@ -1212,9 +1212,9 @@
   (block $label$1
    (loop $label$2
     (br_if $label$1
-     (i32.ge_u
-      (local.get $1)
+     (i32.le_u
       (local.get $0)
+      (local.get $1)
      )
     )
     (call $assembly/index/NBodySystem#advance
@@ -1233,8 +1233,7 @@
  (func $assembly/index/getBody (; has Stack IR ;) (param $0 i32) (result i32)
   (local $1 i32)
   (if (result i32)
-   (i32.lt_u
-    (local.get $0)
+   (i32.gt_u
     (i32.load offset=4
      (local.tee $1
       (i32.load
@@ -1242,10 +1241,10 @@
       )
      )
     )
+    (local.get $0)
    )
    (if (result i32)
-    (i32.lt_u
-     (local.get $0)
+    (i32.gt_u
      (i32.shr_u
       (i32.load
        (local.tee $1
@@ -1256,6 +1255,7 @@
       )
       (i32.const 2)
      )
+     (local.get $0)
     )
     (i32.load offset=8
      (i32.add
diff --git a/test/passes/inlining-optimizing_optimize-level=3.txt b/test/passes/inlining-optimizing_optimize-level=3.txt
index 1b8a1b9f5..a127ec001 100644
--- a/test/passes/inlining-optimizing_optimize-level=3.txt
+++ b/test/passes/inlining-optimizing_optimize-level=3.txt
@@ -3602,9 +3602,9 @@
                                       )
                                      )
                                      (local.get $6)
-                                     (i32.lt_s
-                                      (local.get $6)
+                                     (i32.gt_s
                                       (local.get $5)
+                                      (local.get $6)
                                      )
                                     )
                                    )
@@ -4508,22 +4508,22 @@
                                     (block (result i32)
                                      (global.set $tempRet0
                                       (i32.add
-                                       (i32.lt_u
+                                       (i32.gt_u
+                                        (local.tee $20
+                                         (call $_bitshift64Shl
+                                          (i32.load
+                                           (local.get $9)
+                                          )
+                                          (i32.const 0)
+                                          (local.get $15)
+                                         )
+                                        )
                                         (local.tee $11
                                          (i32.add
                                           (local.get $11)
-                                          (local.tee $20
-                                           (call $_bitshift64Shl
-                                            (i32.load
-                                             (local.get $9)
-                                            )
-                                            (i32.const 0)
-                                            (local.get $15)
-                                           )
-                                          )
+                                          (local.get $20)
                                          )
                                         )
-                                        (local.get $20)
                                        )
                                        (global.get $tempRet0)
                                       )
@@ -4575,9 +4575,9 @@
                                )
                                (loop $while-in68
                                 (if
-                                 (i32.gt_u
-                                  (local.get $7)
+                                 (i32.lt_u
                                   (local.get $5)
+                                  (local.get $7)
                                  )
                                  (if
                                   (i32.eqz
@@ -4680,9 +4680,9 @@
                                  )
                                 )
                                 (if
-                                 (i32.lt_u
-                                  (local.get $6)
+                                 (i32.gt_u
                                   (local.get $5)
+                                  (local.get $6)
                                  )
                                  (block $do-once71
                                   (local.set $11
@@ -5263,9 +5263,9 @@
                                  )
                                 )
                                 (local.get $9)
-                                (i32.gt_u
-                                 (local.get $9)
+                                (i32.lt_u
                                  (local.get $5)
+                                 (local.get $9)
                                 )
                                )
                               )
@@ -5517,9 +5517,9 @@
                                          )
                                         )
                                        )
-                                       (i32.lt_s
-                                        (local.get $19)
+                                       (i32.gt_s
                                         (local.get $5)
+                                        (local.get $19)
                                        )
                                       )
                                      )
@@ -5547,9 +5547,9 @@
                                          )
                                         )
                                        )
-                                       (i32.lt_s
-                                        (local.get $19)
+                                       (i32.gt_s
                                         (local.get $5)
+                                        (local.get $19)
                                        )
                                       )
                                      )
@@ -6651,9 +6651,9 @@
                         )
                        )
                        (br_if $while-in127
-                        (i32.lt_u
-                         (local.get $6)
+                        (i32.gt_u
                          (local.get $5)
+                         (local.get $6)
                         )
                        )
                        (local.get $5)
@@ -6675,9 +6675,9 @@
                   (select
                    (local.get $17)
                    (local.get $7)
-                   (i32.gt_s
-                    (local.get $17)
+                   (i32.lt_s
                     (local.get $7)
+                    (local.get $17)
                    )
                   )
                  )
@@ -6733,9 +6733,9 @@
                      )
                     )
                    )
-                   (i32.gt_s
-                    (local.get $6)
+                   (i32.lt_s
                     (local.get $5)
+                    (local.get $6)
                    )
                   )
                   (block (result i32)
@@ -6762,9 +6762,9 @@
           )
          )
          (local.get $17)
-         (i32.lt_s
-          (local.get $17)
+         (i32.gt_s
           (local.get $5)
+          (local.get $17)
          )
         )
        )
diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt
index 522bd6fe8..1873b8d3a 100644
--- a/test/passes/optimize-instructions_all-features.txt
+++ b/test/passes/optimize-instructions_all-features.txt
@@ -658,6 +658,51 @@
    )
   )
   (drop
+   (i32.lt_s
+    (local.get $x)
+    (i32.const 1)
+   )
+  )
+  (drop
+   (i32.const 0)
+  )
+  (drop
+   (i32.ne
+    (local.get $x)
+    (i32.const -1)
+   )
+  )
+  (drop
+   (f64.ne
+    (local.get $fx)
+    (f64.const -1)
+   )
+  )
+  (drop
+   (f64.gt
+    (local.get $fx)
+    (f64.const -2)
+   )
+  )
+  (drop
+   (f64.le
+    (local.get $fx)
+    (f64.const inf)
+   )
+  )
+  (drop
+   (f64.ge
+    (local.get $fx)
+    (f64.const nan:0x8000000000000)
+   )
+  )
+  (drop
+   (f64.ge
+    (f64.const 1)
+    (f64.const 2)
+   )
+  )
+  (drop
    (i32.add
     (i32.ctz
      (local.get $x)
@@ -4486,9 +4531,9 @@
   )
   (drop
    (i32.or
-    (i32.gt_s
-     (local.get $y)
+    (i32.lt_s
      (call $ne0)
+     (local.get $y)
     )
     (i32.eq
      (call $ne0)
diff --git a/test/passes/optimize-instructions_all-features.wast b/test/passes/optimize-instructions_all-features.wast
index 9b172e4bd..cf35668d5 100644
--- a/test/passes/optimize-instructions_all-features.wast
+++ b/test/passes/optimize-instructions_all-features.wast
@@ -495,6 +495,39 @@
         (i32.const 23)
       )
     ))
+    (drop (i32.gt_s
+      (i32.const 1)
+      (local.get $x)
+    ))
+    (drop (i32.gt_u
+      (i32.const 0)
+      (local.get $x)
+    ))
+    (drop (i32.ne
+      (i32.const -1)
+      (local.get $x)
+    ))
+    (drop (f64.ne
+      (f64.const -1)
+      (local.get $fx)
+    ))
+    (drop (f64.lt
+      (f64.const -2)
+      (local.get $fx)
+    ))
+    (drop (f64.ge
+      (f64.const inf)
+      (local.get $fx)
+    ))
+    (drop (f64.le
+      (f64.const nan)
+      (local.get $fx)
+    ))
+    ;; skip
+    (drop (f64.ge
+      (f64.const 1)
+      (f64.const 2)
+    ))
     (drop (i32.add (i32.ctz (local.get $x)) (i32.ctz (local.get $y))))
     (drop (i32.add (i32.ctz (local.get $y)) (i32.ctz (local.get $x))))
     (drop (i32.add (i32.ctz (local.get $x)) (i32.eqz (local.get $y))))
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 adb69fd90..235944062 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
@@ -61,14 +61,14 @@
      )
     )
     (br_if $while-in6
-     (i32.lt_s
+     (i32.gt_s
+      (local.get $4)
       (local.tee $3
        (i32.add
         (local.get $3)
         (i32.const 1)
        )
       )
-      (local.get $4)
      )
     )
    )
@@ -144,14 +144,14 @@
      )
     )
     (br_if $while-in6
-     (i32.lt_s
+     (i32.gt_s
+      (local.get $4)
       (local.tee $3
        (i32.add
         (local.get $3)
         (i32.const 1)
        )
       )
-      (local.get $4)
      )
     )
    )
@@ -226,14 +226,14 @@
      )
     )
     (br_if $while-in6
-     (i32.lt_s
+     (i32.gt_s
+      (local.get $4)
       (local.tee $3
        (i32.add
         (local.get $3)
         (i32.const 1)
        )
       )
-      (local.get $4)
      )
     )
    )
diff --git a/test/wasm2js/bulk-memory.2asm.js.opt b/test/wasm2js/bulk-memory.2asm.js.opt
index 6616ef8f1..2003ea126 100644
--- a/test/wasm2js/bulk-memory.2asm.js.opt
+++ b/test/wasm2js/bulk-memory.2asm.js.opt
@@ -375,7 +375,7 @@ function asmFunc(global, env, buffer) {
  }
  
  function $1() {
-  if (0 > __wasm_memory_size() << 16 >>> 0) {
+  if (__wasm_memory_size() << 16 >>> 0 < 0) {
    abort()
   }
  }
diff --git a/test/wasm2js/i64-add-sub.2asm.js.opt b/test/wasm2js/i64-add-sub.2asm.js.opt
index 4913c4587..6d00c9321 100644
--- a/test/wasm2js/i64-add-sub.2asm.js.opt
+++ b/test/wasm2js/i64-add-sub.2asm.js.opt
@@ -21,7 +21,7 @@ function asmFunc(global, env) {
   $5 = $5 | 0;
   $1_1 = $1_1 + $3 | 0;
   $0 = $0 + $2 | 0;
-  if ($0 >>> 0 < $2 >>> 0) {
+  if ($2 >>> 0 > $0 >>> 0) {
    $1_1 = $1_1 + 1 | 0
   }
   return ($0 | 0) == ($4 | 0) & ($1_1 | 0) == ($5 | 0);
diff --git a/test/wasm2js/i64-ctz.2asm.js.opt b/test/wasm2js/i64-ctz.2asm.js.opt
index caadb1516..4cb4f79ff 100644
--- a/test/wasm2js/i64-ctz.2asm.js.opt
+++ b/test/wasm2js/i64-ctz.2asm.js.opt
@@ -39,7 +39,7 @@ function asmFunc(global, env) {
    $0 = Math_clz32($1 ^ $3);
    $0 = ($0 | 0) == 32 ? $2 : $0;
    $1 = 63 - $0 | 0;
-   i64toi32_i32$HIGH_BITS = 0 - (63 < $0 >>> 0) | 0;
+   i64toi32_i32$HIGH_BITS = 0 - ($0 >>> 0 > 63) | 0;
    return $1;
   }
   i64toi32_i32$HIGH_BITS = 0;
diff --git a/test/wasm2js/i64-rotate.2asm.js.opt b/test/wasm2js/i64-rotate.2asm.js.opt
index a024ec830..4eb245df5 100644
--- a/test/wasm2js/i64-rotate.2asm.js.opt
+++ b/test/wasm2js/i64-rotate.2asm.js.opt
@@ -26,7 +26,7 @@ function asmFunc(global, env) {
   $6 = $2 & 63;
   $5 = $6;
   $3 = $5 & 31;
-  if (32 <= $5 >>> 0) {
+  if ($5 >>> 0 >= 32) {
    $3 = -1 >>> $3 | 0
   } else {
    $4 = -1 >>> $3 | 0;
@@ -35,7 +35,7 @@ function asmFunc(global, env) {
   $5 = $3 & $0;
   $3 = $1 & $4;
   $4 = $6 & 31;
-  if (32 <= $6 >>> 0) {
+  if ($6 >>> 0 >= 32) {
    $3 = $5 << $4;
    $6 = 0;
   } else {
@@ -46,7 +46,7 @@ function asmFunc(global, env) {
   $4 = 0 - $2 & 63;
   $3 = $4;
   $2 = $3 & 31;
-  if (32 <= $3 >>> 0) {
+  if ($3 >>> 0 >= 32) {
    $3 = -1 << $2;
    $2 = 0;
   } else {
@@ -56,7 +56,7 @@ function asmFunc(global, env) {
   $0 = $2 & $0;
   $3 = $1 & $3;
   $1 = $4 & 31;
-  if (32 <= $4 >>> 0) {
+  if ($4 >>> 0 >= 32) {
    $2 = 0;
    $0 = $3 >>> $1 | 0;
   } else {
@@ -72,7 +72,7 @@ function asmFunc(global, env) {
   var $3 = 0, $4 = 0, $5 = 0, $6 = 0, $7 = 0;
   $6 = $2 & 63;
   $3 = $6 & 31;
-  if (32 <= $6 >>> 0) {
+  if ($6 >>> 0 >= 32) {
    $4 = -1 << $3;
    $7 = 0;
   } else {
@@ -82,7 +82,7 @@ function asmFunc(global, env) {
   $7 = $7 & $0;
   $3 = $1 & $4;
   $5 = $6 & 31;
-  if (32 <= $6 >>> 0) {
+  if ($6 >>> 0 >= 32) {
    $4 = 0;
    $6 = $3 >>> $5 | 0;
   } else {
@@ -92,7 +92,7 @@ function asmFunc(global, env) {
   $7 = $4;
   $3 = 0 - $2 & 63;
   $5 = $3 & 31;
-  if (32 <= $3 >>> 0) {
+  if ($3 >>> 0 >= 32) {
    $4 = 0;
    $2 = -1 >>> $5 | 0;
   } else {
@@ -102,7 +102,7 @@ function asmFunc(global, env) {
   $0 = $2 & $0;
   $1 = $1 & $4;
   $4 = $3 & 31;
-  if (32 <= $3 >>> 0) {
+  if ($3 >>> 0 >= 32) {
    $2 = $0 << $4;
    $0 = 0;
   } else {
diff --git a/test/wasm2js/i64-shifts.2asm.js.opt b/test/wasm2js/i64-shifts.2asm.js.opt
index b04fc3b8f..54cc05097 100644
--- a/test/wasm2js/i64-shifts.2asm.js.opt
+++ b/test/wasm2js/i64-shifts.2asm.js.opt
@@ -20,7 +20,7 @@ function asmFunc(global, env) {
   $4 = $4 | 0;
   var $5 = 0;
   $5 = $2_1 & 31;
-  if (32 <= ($2_1 & 63) >>> 0) {
+  if (($2_1 & 63) >>> 0 >= 32) {
    $1_1 = $0 << $5;
    $0 = 0;
   } else {
@@ -38,7 +38,7 @@ function asmFunc(global, env) {
   $4 = $4 | 0;
   var $5 = 0;
   $5 = $2_1 & 31;
-  if (32 <= ($2_1 & 63) >>> 0) {
+  if (($2_1 & 63) >>> 0 >= 32) {
    $2_1 = $1_1 >> 31;
    $0 = $1_1 >> $5;
   } else {
diff --git a/test/wasm2js/unary-ops.2asm.js.opt b/test/wasm2js/unary-ops.2asm.js.opt
index 8922b6fb7..9bda50800 100644
--- a/test/wasm2js/unary-ops.2asm.js.opt
+++ b/test/wasm2js/unary-ops.2asm.js.opt
@@ -80,7 +80,7 @@ function asmFunc(global, env) {
    $0 = Math_clz32($1_1 ^ $3);
    $0 = ($0 | 0) == 32 ? $2 : $0;
    $1_1 = 63 - $0 | 0;
-   i64toi32_i32$HIGH_BITS = 0 - (63 < $0 >>> 0) | 0;
+   i64toi32_i32$HIGH_BITS = 0 - ($0 >>> 0 > 63) | 0;
    return $1_1;
   }
   i64toi32_i32$HIGH_BITS = 0;