[OptimizeInstructions] Combine some relational ops joined Or/And (Part 3) (#4338)

(i32(x) < 0) | (i32(y) < 0)   ==>   i32(x | y) < 0
(i32(x) != 0) | (i32(y) != 0)   ==>   i32(x | y) != 0

Likewise for i64.

2 files changed, 132 insertions, 9 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index ecc5d4488..1a2807ab4 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -2543,23 +2543,61 @@ private:
       }
     }
     {
-      // (i32(x) != 0) | (i32(y) != 0)   ==>   i32(x | y) != 0
-      // (i64(x) != 0) | (i64(y) != 0)   ==>   i64(x | y) != 0
+      // Binary operations that preserve a bitwise OR can be
+      // reordered. If F(x) = binary(x, c), and F(x) preserves OR,
+      // that is,
+      //
+      //   F(x) | F(y) == F(x | y)
+      //
+      // Then also
+      //
+      //   binary(x, c) | binary(y, c)  =>  binary(x | y, c)
+      Binary *bx, *by;
       Expression *x, *y;
+      Const *cx, *cy;
       if (matches(curr,
                   binary(OrInt32,
-                         binary(Ne, any(&x), ival(0)),
-                         binary(Ne, any(&y), ival(0)))) &&
-          x->type == y->type) {
-        auto* inner = curr->left->cast<Binary>();
-        inner->left = Builder(*getModule())
-                        .makeBinary(Abstract::getBinary(x->type, Or), x, y);
-        return inner;
+                         binary(&bx, any(&x), ival(&cx)),
+                         binary(&by, any(&y), ival(&cy)))) &&
+          bx->op == by->op && x->type == y->type && cx->value == cy->value &&
+          preserveOr(bx)) {
+        bx->left = Builder(*getModule())
+                     .makeBinary(Abstract::getBinary(x->type, Or), x, y);
+        return bx;
       }
     }
     return nullptr;
   }
 
+  // Check whether an operation preserves the Or operation through it, that is,
+  //
+  //   F(x | y) = F(x) | F(y)
+  //
+  // Mathematically that means F is homomorphic with respect to the | operation.
+  //
+  // F(x) is seen as taking a single parameter of its first child. That is, the
+  // first child is |x|, and the rest is constant. For example, if we are given
+  // a binary with operation != and the right child is a constant 0, then
+  // F(x) = (x != 0).
+  bool preserveOr(Binary* curr) {
+    using namespace Abstract;
+    using namespace Match;
+
+    // (x != 0) | (y != 0)    ==>    (x | y) != 0
+    // This effectively checks if any bits are set in x or y.
+    if (matches(curr, binary(Ne, any(), ival(0)))) {
+      return true;
+    }
+
+    // (x < 0) | (y < 0)    ==>    (x | y) < 0
+    // This effectively checks if x or y have the sign bit set.
+    if (matches(curr, binary(LtS, any(), ival(0)))) {
+      return true;
+    }
+
+    return false;
+  }
+
   // fold constant factors into the offset
   void optimizeMemoryAccess(Expression*& ptr, Address& offset) {
     // ptr may be a const, but it isn't worth folding that in (we still have a
diff --git a/test/lit/passes/optimize-instructions.wast b/test/lit/passes/optimize-instructions.wast
index 574671076..9a5d33f87 100644
--- a/test/lit/passes/optimize-instructions.wast
+++ b/test/lit/passes/optimize-instructions.wast
@@ -11034,6 +11034,91 @@
       (i64.ne (local.get $b) (i64.const 0))
     ))
   )
+  ;; CHECK:      (func $optimize-combined-by-or-lessthan-zero (param $x i32) (param $y i32) (param $a i64) (param $b i64)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.lt_s
+  ;; CHECK-NEXT:    (i32.or
+  ;; CHECK-NEXT:     (local.get $x)
+  ;; CHECK-NEXT:     (local.get $y)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i64.lt_s
+  ;; CHECK-NEXT:    (i64.or
+  ;; CHECK-NEXT:     (local.get $a)
+  ;; CHECK-NEXT:     (local.get $b)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i64.const 0)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.or
+  ;; CHECK-NEXT:    (i32.lt_s
+  ;; CHECK-NEXT:     (local.get $x)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i64.lt_s
+  ;; CHECK-NEXT:     (local.get $a)
+  ;; CHECK-NEXT:     (i64.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.or
+  ;; CHECK-NEXT:    (i32.lt_s
+  ;; CHECK-NEXT:     (local.get $y)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.le_s
+  ;; CHECK-NEXT:     (local.get $x)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.or
+  ;; CHECK-NEXT:    (i32.lt_s
+  ;; CHECK-NEXT:     (local.get $y)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.le_s
+  ;; CHECK-NEXT:     (local.get $x)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $optimize-combined-by-or-lessthan-zero (param $x i32) (param $y i32) (param $a i64) (param $b i64)
+    ;; (i32(x) < 0) | (i32(y) < 0)   ==>   i32(x | y) < 0
+    (drop (i32.or
+      (i32.lt_s (local.get $x) (i32.const 0))
+      (i32.lt_s (local.get $y) (i32.const 0))
+    ))
+    ;; (i64(x) < 0) | (i64(y) < 0)   ==>   i64(x | y) < 0
+    (drop (i32.or
+      (i64.lt_s (local.get $a) (i64.const 0))
+      (i64.lt_s (local.get $b) (i64.const 0))
+    ))
+
+    ;; skips
+    ;; (i32(x) < 0) | (i64(a) < 0)   ==>   skip
+    (drop (i32.or
+      (i32.lt_s (local.get $x) (i32.const 0))
+      (i64.lt_s (local.get $a) (i64.const 0))
+    ))
+    ;; (i32(x) <= 0) | (i32(y) < 0)   ==>   skip
+    (drop (i32.or
+      (i32.le_s (local.get $x) (i32.const 0))
+      (i32.lt_s (local.get $y) (i32.const 0))
+    ))
+    ;; (i32(x) < 1) | (i32(y) < 0)   ==>   skip
+    (drop (i32.or
+      (i32.lt_s (local.get $x) (i32.const 1))
+      (i32.lt_s (local.get $y) (i32.const 0))
+    ))
+  )
   ;; CHECK:      (func $optimize-relationals (param $x i32) (param $y i32) (param $X i64) (param $Y i64)
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (i32.eq