At -O1, GCC lowers (~a & 1) == (~b & 1) into two different GIMPLE
forms depending on whether the boolean values come from a function
return boundary or an inline expression:
1. Via function return (e.g. inlined is_even), GCC preserves the
eq/ne form because the function boundary hides the internal
structure from the gimplifier:
((a&1)==0) == ((b&1)==0) outer node is eq/ne
2. Via inline expression (directly written), GCC sees the full
boolean expression tree at once and folds to bit_xor during
gimplification:
((a&1)!=0) ^ ((b&1)==0) outer node is bit_xor
Add a generalized match.pd rule handling:
1. ((x & c) == 0) OP ((y & c) == 0)
2. ((x & c) != 0) OP ((y & c) == 0)
3. ((x & c) == 0) OP (y & c)
for OP in { ==, !=, ^ } and pow2 masks. The third form is required
because GCC canonicalize: ((x & c) != 0) into (x & c) before this
rule runs.
Fold these directly into the canonical xor-mask form:
((x ^ y) & c) == 0
((x ^ y) & c) != 0
Bootstrapped and tested on aarch64-linux-gnu.
Changes since v1:
* v3: Collapse both previous simplify rules into one generalized
matcher covering all combinations of outer {eq, ne, bit_xor}
and inner {eq, ne} comparisons.
Add missing mixed-polarity test cases.
* v2: Generalize mask from integer_onep to integer_pow2p.
Combine both patterns into single one.
Split test into bool-eq-evenness.c, bool-eq-bitxor.c,
bool-eq-pow2.c.
PR tree-optimization/112533
gcc/ChangeLog:
* match.pd: Canonicalize boolean comparisons of masked pow2
bits into xor-mask tests.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/bool-eq-bitxor.c: New test.
* gcc.dg/tree-ssa/bool-eq-evenness.c: New test.
* gcc.dg/tree-ssa/bool-eq-pow2.c: New test.
Signed-off-by: Shivam Gupta <[email protected]>
---
gcc/match.pd | 38 ++++++++
.../gcc.dg/tree-ssa/bool-eq-bitxor.c | 39 ++++++++
.../gcc.dg/tree-ssa/bool-eq-evenness.c | 43 +++++++++
gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c | 89 +++++++++++++++++++
4 files changed, 209 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
diff --git a/gcc/match.pd b/gcc/match.pd
index ff13a07ea94..d41a2b2f329 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1464,6 +1464,44 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (TYPE_UNSIGNED (type))
(bit_and @0 (bit_not (lshift { build_all_ones_cst (type); } @1)))))
+/* PR112533: Canonicalize boolean comparisons of masked pow2 bits into
+ xor-mask tests.
+ ((x & c) == 0) == ((y & c) == 0) -> (((x ^ y) & c) == 0)
+ ((x & c) == 0) != ((y & c) == 0) -> (((x ^ y) & c) != 0)
+ and equivalent xor forms. */
+(for ocmp (eq ne bit_xor)
+ (for icmp0 (eq eq ne ne)
+ icmp1 (eq ne eq ne)
+ (simplify
+ (ocmp
+ (icmp0 (bit_and @0 integer_pow2p@1) integer_zerop@3)
+ (icmp1 (bit_and @2 @1) @3))
+ (if (types_match (@0, @2))
+ (with {
+ bool innersame
+ = (icmp0 == EQ_EXPR) == (icmp1 == EQ_EXPR);
+ }
+ (if (innersame == (ocmp == EQ_EXPR))
+ (eq (bit_and (bit_xor @0 @2) @1) @3)
+ (ne (bit_and (bit_xor @0 @2) @1) @3)))))
+
+ /* Canonicalized: ((x & c) == 0) OP (y & c)
+ because ((y & c) != 0) may fold into (y & c). */
+ (simplify
+ (ocmp
+ (convert?@4
+ (icmp0 (bit_and @0 integer_pow2p@1) integer_zerop@3))
+ (convert?@5
+ (bit_and @2 @1)))
+ (if (types_match (@0, @2))
+ (with {
+ bool innersame
+ = (icmp0 == EQ_EXPR) == false;
+ }
+ (if (innersame == (ocmp == EQ_EXPR))
+ (eq (bit_and (bit_xor @0 @2) @1) @3)
+ (ne (bit_and (bit_xor @0 @2) @1) @3)))))))
+
(for bitop (bit_and bit_ior)
cmp (eq ne)
/* PR35691: Transform
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
new file mode 100644
index 00000000000..05cee9696cf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
@@ -0,0 +1,39 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-optimized" } */
+
+typedef unsigned int u32;
+
+_Bool
+xor_ne_eq (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 != 0) ^ (t2 == 0);
+}
+
+_Bool
+xor_eq_eq (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) ^ (t2 == 0);
+}
+
+_Bool
+xor_eq_ne (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) ^ (t2 != 0);
+}
+
+_Bool
+xor_ne_ne (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 != 0) ^ (t2 != 0);
+}
+
+/* Verify all functions canonicalize to xor-mask tests. */
+/* { dg-final { scan-tree-dump-times "& 1" 4 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
new file mode 100644
index 00000000000..75df70dc6a4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-optimized" } */
+
+/* Verify the GIMPLE-level fix for PR112533. */
+
+typedef unsigned int u32;
+
+static _Bool
+is_even (u32 a)
+{
+ return a % 2 == 0;
+}
+
+_Bool
+same_evenness (u32 a, u32 b)
+{
+ return is_even (a) == is_even (b);
+}
+
+_Bool
+diff_evenness (u32 a, u32 b)
+{
+ return is_even (a) != is_even (b);
+}
+
+_Bool
+same_evenness_cmp_zero (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) == (t2 == 0);
+}
+
+_Bool
+diff_evenness_cmp_zero (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) != (t2 == 0);
+}
+
+/* Verify all functions canonicalize to xor forms. */
+/* { dg-final { scan-tree-dump-times "\\^" 4 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
new file mode 100644
index 00000000000..109c5f03610
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
@@ -0,0 +1,89 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-optimized" } */
+
+typedef unsigned int u32;
+
+_Bool
+eq_eq_outer_eq_mask2 (u32 a, u32 b)
+{
+ u32 t1 = a & 2;
+ u32 t2 = b & 2;
+ return (t1 == 0) == (t2 == 0);
+}
+
+_Bool
+eq_eq_outer_eq_mask4 (u32 a, u32 b)
+{
+ u32 t1 = a & 4;
+ u32 t2 = b & 4;
+ return (t1 == 0) == (t2 == 0);
+}
+
+_Bool
+eq_eq_outer_ne (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) != (t2 == 0);
+}
+
+_Bool
+ne_eq_outer_eq (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 != 0) == (t2 == 0);
+}
+
+_Bool
+ne_eq_outer_ne (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 != 0) != (t2 == 0);
+}
+
+_Bool
+eq_ne_outer_eq (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) == (t2 != 0);
+}
+
+_Bool
+eq_ne_outer_ne (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 == 0) != (t2 != 0);
+}
+
+_Bool
+ne_ne_outer_eq (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 != 0) == (t2 != 0);
+}
+
+_Bool
+ne_ne_outer_ne (u32 a, u32 b)
+{
+ u32 t1 = a & 1;
+ u32 t2 = b & 1;
+ return (t1 != 0) != (t2 != 0);
+}
+
+/* Non-power-of-2: should not be simplified. */
+_Bool
+eq_eq_outer_eq_nonpow2 (u32 a, u32 b)
+{
+ u32 t1 = a & 3;
+ u32 t2 = b & 3;
+ return (t1 == 0) == (t2 == 0);
+}
+
+/* Verify power-of-2 masks are simplified, non-power-of-2 masks are not. */
+/* { dg-final { scan-tree-dump-times "a_\[0-9\]+\\(D\\) \\^ b_\[0-9\]+\\(D\\)"
9 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "& 3" 2 "optimized" } } */
--
2.34.1
