[OptimizeInstructions] Combine some relational ops joined Or/And (Part 7-8) (#4399)

Final part of #4265

(i32(x) >= 0) & (i32(y) >= 0)   ==>   i32(x | y) >= 0
(i64(x) >= 0) & (i64(y) >= 0)   ==>   i64(x | y) >= 0

(i32(x) == -1) & (i32(y) == -1)   ==>   i32(x & y) == -1
(i64(x) == -1) & (i64(y) == -1)   ==>   i64(x & y) == -1

1 files changed, 63 insertions, 12 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 54a791606..bde60e093 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -2510,12 +2510,37 @@ private:
       if (matches(curr->left, unary(EqZ, any(&x))) &&
           matches(curr->right, unary(EqZ, any(&y))) && x->type == y->type) {
         auto* inner = curr->left->cast<Unary>();
-        inner->value = Builder(*getModule())
-                         .makeBinary(Abstract::getBinary(x->type, Or), x, y);
+        inner->value =
+          Builder(*getModule()).makeBinary(getBinary(x->type, Or), x, y);
         return inner;
       }
     }
     {
+      // Binary operations that inverse a bitwise AND can be
+      // reordered. If F(x) = binary(x, c), and F(x) preserves AND,
+      // 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->left, binary(&bx, any(&x), ival(&cx))) &&
+          matches(curr->right, binary(&by, any(&y), ival(&cy))) &&
+          bx->op == by->op && x->type == y->type && cx->value == cy->value &&
+          inversesAnd(bx)) {
+        by->op = getBinary(x->type, Or);
+        by->type = x->type;
+        by->left = x;
+        by->right = y;
+        bx->left = by;
+        return bx;
+      }
+    }
+    {
       // Binary operations that preserve a bitwise AND can be
       // reordered. If F(x) = binary(x, c), and F(x) preserves AND,
       // that is,
@@ -2528,14 +2553,15 @@ private:
       Binary *bx, *by;
       Expression *x, *y;
       Const *cx, *cy;
-      if (matches(curr,
-                  binary(AndInt32,
-                         binary(&bx, any(&x), ival(&cx)),
-                         binary(&by, any(&y), ival(&cy)))) &&
+      if (matches(curr->left, binary(&bx, any(&x), ival(&cx))) &&
+          matches(curr->right, binary(&by, any(&y), ival(&cy))) &&
           bx->op == by->op && x->type == y->type && cx->value == cy->value &&
           preserveAnd(bx)) {
-        bx->left = Builder(*getModule())
-                     .makeBinary(Abstract::getBinary(x->type, And), x, y);
+        by->op = getBinary(x->type, And);
+        by->type = x->type;
+        by->left = x;
+        by->right = y;
+        bx->left = by;
         return bx;
       }
     }
@@ -2590,7 +2616,7 @@ private:
           matches(curr->right, binary(&by, any(&y), ival(&cy))) &&
           bx->op == by->op && x->type == y->type && cx->value == cy->value &&
           inversesOr(bx)) {
-        by->op = Abstract::getBinary(x->type, And);
+        by->op = getBinary(x->type, And);
         by->type = x->type;
         by->left = x;
         by->right = y;
@@ -2615,7 +2641,7 @@ private:
           matches(curr->right, binary(&by, any(&y), ival(&cy))) &&
           bx->op == by->op && x->type == y->type && cx->value == cy->value &&
           preserveOr(bx)) {
-        by->op = Abstract::getBinary(x->type, Or);
+        by->op = getBinary(x->type, Or);
         by->type = x->type;
         by->left = x;
         by->right = y;
@@ -2645,13 +2671,11 @@ private:
     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;
   }
 
@@ -2701,6 +2725,33 @@ private:
       return true;
     }
 
+    // (x == -1) & (y == -1)   ==>   (x & y) == -1
+    if (matches(curr, binary(Eq, any(), ival(-1)))) {
+      return true;
+    }
+
+    return false;
+  }
+
+  // Check whether an operation inverses the And operation to Or, 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 inversesAnd(Binary* curr) {
+    using namespace Abstract;
+    using namespace Match;
+
+    // (x >= 0) & (y >= 0)   ==>   (x | y) >= 0
+    if (matches(curr, binary(GeS, any(), ival(0)))) {
+      return true;
+    }
+
     return false;
   }