Repository: bytecodealliance/wasmtime
Pull request #5684 (2023-02-01 19:47:26)

Cranelift: Rewrite `or(and(x, y), not(y)) => or(x, not(y))` again
This rewrite was introduced in #5676 and then reverted in #5682 due to a footgun where we accidentally weren't actually checking the `y == !z` precondition. This commit fixes the precondition check. It also fixes the arithmetic to be correctly masked to the value type's width.

This reverts commit 268f6bfc1d383efe6793907c9d26209df2e96c94.

cc @avanhatt  

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

- [ ] This has been discussed in issue #..., or if not, please tell us why
  here.
- [ ] A short description of what this does, why it is needed; if the
  description becomes long, the matter should probably be discussed in an issue
  first.
- [ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
  If you don't know who could review this, please indicate so. The list of
  suggested reviewers on the right can help you.

Please ensure all communication adheres to the [code of
conduct](https://github.com/bytecodealliance/wasmtime/blob/master/CODE_OF_CONDUCT.md).
-->



Patch:
diff --git a/cranelift/codegen/src/isle_prelude.rs b/cranelift/codegen/src/isle_prelude.rs
index a32cee62c..81f10d9fd 100644
--- a/cranelift/codegen/src/isle_prelude.rs
+++ b/cranelift/codegen/src/isle_prelude.rs
@@ -109,6 +109,11 @@ macro_rules! isle_common_prelude_methods {
             !x
         }
 
+        #[inline]
+        fn u64_eq(&mut self, x: u64, y: u64) -> bool {
+            x == y
+        }
+
         #[inline]
         fn u64_is_zero(&mut self, value: u64) -> bool {
             0 == value
diff --git a/cranelift/codegen/src/opts/algebraic.isle b/cranelift/codegen/src/opts/algebraic.isle
index 64a64a3a1..88c46465c 100644
--- a/cranelift/codegen/src/opts/algebraic.isle
+++ b/cranelift/codegen/src/opts/algebraic.isle
@@ -138,6 +138,34 @@
 (rule (simplify (bnot ty (band t x y)))
       (bor ty (bnot ty x) (bnot ty y)))
 
+;; `or(and(x, y), not(y)) == or(x, not(y))`
+(rule (simplify (bor ty
+                     (band ty x y)
+                     z @ (bnot ty y)))
+      (bor ty x z))
+;; Duplicate the rule but swap the `bor` operands because `bor` is
+;; commutative. We could, of course, add a `simplify` rule to do the commutative
+;; swap for all `bor`s but this will bloat the e-graph with many e-nodes. It is
+;; cheaper to have additional rules, rather than additional e-nodes, because we
+;; amortize their cost via ISLE's smart codegen.
+(rule (simplify (bor ty
+                     z @ (bnot ty y)
+                     (band ty x y)))
+      (bor ty x z))
+
+;; `or(and(x, y), not(y)) == or(x, not(y))` specialized for constants, since
+;; otherwise we may not know that `z == not(y)` since we don't generally expand
+;; constants in the e-graph.
+;;
+;; (No need to duplicate for commutative `bor` for this constant version because
+;; we move constants to the right.)
+(rule (simplify (bor ty
+                     (band ty x (iconst ty (u64_from_imm64 y)))
+                     z @ (iconst ty (u64_from_imm64 zk))))
+      (if-let $true (u64_eq (u64_and (ty_mask ty) zk)
+                            (u64_and (ty_mask ty) (u64_not y))))
+      (bor ty x z))
+
 ;; x*2 == 2*x == x+x.
 (rule (simplify (imul ty x (iconst _ (simm32 2))))
       (iadd ty x x))
diff --git a/cranelift/codegen/src/prelude.isle b/cranelift/codegen/src/prelude.isle
index c1e7c8d2b..0aec07a86 100644
--- a/cranelift/codegen/src/prelude.isle
+++ b/cranelift/codegen/src/prelude.isle
@@ -141,6 +141,9 @@
 (decl pure u64_not (u64) u64)
 (extern constructor u64_not u64_not)
 
+(decl pure u64_eq (u64 u64) bool)
+(extern constructor u64_eq u64_eq)
+
 (decl pure u64_sextend_u32 (u64) u64)
 (extern constructor u64_sextend_u32 u64_sextend_u32)
 


Test patch:
diff --git a/cranelift/filetests/filetests/egraph/algebraic.clif b/cranelift/filetests/filetests/egraph/algebraic.clif
index 33e83936c..fd0f49597 100644
--- a/cranelift/filetests/filetests/egraph/algebraic.clif
+++ b/cranelift/filetests/filetests/egraph/algebraic.clif
@@ -40,7 +40,7 @@ block0(v0: i32):
     return v3
     ; check: v4 = iconst.i32 0xffff_ffe0
     ; check: v5 = band v0, v4
-    ; return v5
+    ; check: return v5
 }
 
 function %unsigned_shift_right_shift_left_i64(i64) -> i64 {
@@ -86,3 +86,109 @@ block0(v0: i64):
     ; check: v5 = band v0, v4
     ; return v5
 }
+
+function %or_and_y_with_not_y_i8(i8, i8) -> i8 {
+block0(v0: i8, v1: i8):
+    v2 = band v0, v1
+    v3 = bnot v1
+    v4 = bor v2, v3
+    return v4
+    ; check: v5 = bor v0, v3
+    ; check: return v5
+}
+
+function %or_and_constant_with_not_constant_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 -4
+    v2 = band v0, v1
+    v3 = iconst.i8 3
+    v4 = bor v2, v3
+    return v4
+    ; check: v5 = bor v0, v3
+    ; check: return v5
+}
+
+function %or_and_y_with_not_y_i8(i8, i8) -> i8 {
+block0(v0: i8, v1: i8):
+    v2 = band v0, v1
+    v3 = bnot v1
+    v4 = bor v3, v2
+    return v4
+    ; check: v5 = bor v0, v3
+    ; check: return v5
+}
+
+function %or_and_constant_with_not_constant_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 -4
+    v2 = band v0, v1
+    v3 = iconst.i8 3
+    v4 = bor v3, v2
+    return v4
+    ; check: v6 = bor v0, v3
+    ; check: return v6
+}
+
+function %or_and_constant_with_any_constant_should_not_apply_rule_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 -4
+    v2 = band v0, v1
+    ;; `v3` is not `bnot(v1)` so the rewrite should not apply.
+    v3 = iconst.i8 -5
+    v4 = bor v2, v3
+    return v4
+    ; check: return v4
+}
+
+function %or_and_y_with_not_y_i64(i64, i64) -> i64 {
+block0(v0: i64, v1: i64):
+    v2 = band v0, v1
+    v3 = bnot v1
+    v4 = bor v2, v3
+    return v4
+    ; check: v5 = bor v0, v3
+    ; check: return v5
+}
+
+function %or_and_constant_with_not_constant_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 -4
+    v2 = band v0, v1
+    v3 = iconst.i64 3
+    v4 = bor v2, v3
+    return v4
+    ; check: v5 = bor v0, v3
+    ; check: return v5
+}
+
+function %or_and_y_with_not_y_i64(i64, i64) -> i64 {
+block0(v0: i64, v1: i64):
+    v2 = band v0, v1
+    v3 = bnot v1
+    v4 = bor v3, v2
+    return v4
+    ; check: v5 = bor v0, v3
+    ; check: return v5
+}
+
+function %or_and_constant_with_not_constant_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 -4
+    v2 = band v0, v1
+    v3 = iconst.i64 3
+    v4 = bor v3, v2
+    return v4
+    ; check: v6 = bor v0, v3
+    ; check: return v6
+}
+
+function %or_and_constant_with_any_constant_should_not_apply_rule_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 -4
+    v2 = band v0, v1
+    ;; `v3` is not `bnot(v1)` so the rewrite should not apply.
+    v3 = iconst.i64 -5
+    v4 = bor v2, v3
+    return v4
+    ; check: return v4
+}
diff --git a/cranelift/filetests/filetests/runtests/or-and-y-with-not-y.clif b/cranelift/filetests/filetests/runtests/or-and-y-with-not-y.clif
new file mode 100644
index 000000000..55532d23b
--- /dev/null
+++ b/cranelift/filetests/filetests/runtests/or-and-y-with-not-y.clif
@@ -0,0 +1,34 @@
+;; Test the rewrite: `or(and(x, y), not(y)) => or(x, not(y))`
+
+test interpret
+test run
+target aarch64
+target x86_64
+target riscv64
+target s390x
+
+function %or_and_y_with_not_y(i8, i8) -> i8 {
+block0(v0: i8, v1: i8):
+    v2 = band v0, v1
+    v3 = bnot v1
+    v4 = bor v2, v3
+    return v4
+}
+; run: %or_and_y_with_not_y(0xff, 0x0a) == 0xff
+; run: %or_and_y_with_not_y(0xff, 0xb0) == 0xff
+; run: %or_and_y_with_not_y(0xaa, 0x0a) == 0xff
+; run: %or_and_y_with_not_y(0xaa, 0xb0) == 0xef
+; run: %or_and_y_with_not_y(0x00, 0x0a) == 0xf5
+; run: %or_and_y_with_not_y(0x00, 0xb0) == 0x4f
+
+function %or_and_constant_with_not_constant(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 -4
+    v2 = band v0, v1
+    v3 = iconst.i8 3
+    v4 = bor v2, v3
+    return v4
+}
+; run: %or_and_constant_with_not_constant(0xff) == 0xff
+; run: %or_and_constant_with_not_constant(0xaa) == 0xab
+; run: %or_and_constant_with_not_constant(0x00) == 0x03