De-morgan's "and" law (#1297)

(eqz X) and (eqz Y) === eqz (X or Y)

Normally de-morgan's laws apply only to boolean vars, but for the and (but not or or xor) version, it works in all cases (both sides are true iff X and Y have all zero bits).

1 files changed, 26 insertions, 0 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 37fb37ace..06f3d5b02 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -562,6 +562,32 @@ struct OptimizeInstructions : public WalkerPass<PostWalker<OptimizeInstructions,
           }
         }
       }
+      // bitwise operations
+      if (binary->op == AndInt32) {
+        // try de-morgan's AND law,
+        //  (eqz X) and (eqz Y) === eqz (X or Y)
+        // Note that the OR and XOR laws do not work here, as these
+        // are not booleans (we could check if they are, but a boolean
+        // would already optimize with the eqz anyhow, unless propagating).
+        // But for AND, the left is true iff X and Y are each all zero bits,
+        // and the right is true if the union of their bits is zero; same.
+        if (auto* left = binary->left->dynCast<Unary>()) {
+          if (left->op == EqZInt32) {
+            if (auto* right = binary->right->dynCast<Unary>()) {
+              if (right->op == EqZInt32) {
+                // reuse one unary, drop the other
+                auto* leftValue = left->value;
+                left->value = binary;
+                binary->left = leftValue;
+                binary->right = right->value;
+                binary->op = OrInt32;
+                return left;
+              }
+            }
+          }
+        }
+      }
+      // for and and or, we can potentially conditionalize
       if (binary->op == AndInt32 || binary->op == OrInt32) {
         return conditionalizeExpensiveOnBitwise(binary);
       }