1 files changed, 53 insertions, 4 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 1a2807ab4..80ca7162c 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -2494,21 +2494,47 @@ private:
   // We can combine `and` operations, e.g.
   //   (x == 0) & (y == 0)   ==>    (x | y) == 0
   Expression* combineAnd(Binary* curr) {
+    assert(curr->op == AndInt32);
+
     using namespace Abstract;
     using namespace Match;
+
     {
       // (i32(x) == 0) & (i32(y) == 0)   ==>   i32(x | y) == 0
       // (i64(x) == 0) & (i64(y) == 0)   ==>   i64(x | y) == 0
       Expression *x, *y;
-      if (matches(curr,
-                  binary(AndInt32, unary(EqZ, any(&x)), unary(EqZ, any(&y)))) &&
-          x->type == y->type) {
+      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);
         return inner;
       }
     }
+    {
+      // Binary operations that preserve 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,
+                  binary(AndInt32,
+                         binary(&bx, any(&x), ival(&cx)),
+                         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);
+        return bx;
+      }
+    }
     return nullptr;
   }
 
@@ -2516,10 +2542,11 @@ private:
   //   (x > y)  | (x == y)    ==>    x >= y
   //   (x != 0) | (y != 0)    ==>    (x | y) != 0
   Expression* combineOr(Binary* curr) {
+    assert(curr->op == OrInt32);
+
     using namespace Abstract;
     using namespace Match;
 
-    assert(curr->op == OrInt32);
     if (auto* left = curr->left->dynCast<Binary>()) {
       if (auto* right = curr->right->dynCast<Binary>()) {
         if (left->op != right->op &&
@@ -2598,6 +2625,28 @@ private:
     return false;
   }
 
+  // Check whether an operation preserves the And 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 preserveAnd(Binary* curr) {
+    using namespace Abstract;
+    using namespace Match;
+
+    // (x < 0) & (y < 0)   ==>   (x & y) < 0
+    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