[PATCH 1/2] Match: Add maybe_bit_not instead of plain matching

[PATCH 1/2] Match: Add maybe_bit_not instead of plain matching

[Andrew Pinski]

While working on adding matching of negative expressions of `a - b`,
I noticed that we started to have "duplicated" patterns due to not having
a way to match maybe negative expressions. So I went back to what I did for
bit_not and decided to improve the situtation there so for some patterns
where we had 2 operands of an expression where one could have been a bit_not,
add back maybe_bit_not.
This does not add maybe_bit_not in every place were bitwise_inverted_equal_p
is used, just the ones were 2 operands of an expression could be swapped.

Bootstrapped and tested on x86_64-linux-gnu with no regressions.

gcc/ChangeLog:

	* match.pd (bit_not_with_nop): Unconditionalize.
	(maybe_cmp): Likewise.
	(maybe_bit_not): New match pattern.
	(`~X & X`): Use maybe_bit_not and add `:c` back.
	(`~x ^ x`/`~x | x`): Likewise.

Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>
---
 gcc/match.pd | 14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/gcc/match.pd b/gcc/match.pd
index 024e3350465..090ad4e08b0 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -167,7 +167,6 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 		   TYPE_VECTOR_SUBPARTS (TREE_TYPE (@0)))
       && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
 
-#if GIMPLE
 /* These are used by gimple_bitwise_inverted_equal_p to simplify
    detection of BIT_NOT and comparisons. */
 (match (bit_not_with_nop @0)
@@ -188,7 +187,14 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (bit_xor@0 @1 @2)
  (if (INTEGRAL_TYPE_P (type)
       && TYPE_PRECISION (type) == 1)))
-#endif
+/* maybe_bit_not is used to match what
+   is acceptable for bitwise_inverted_equal_p. */
+(match (maybe_bit_not @0)
+ (bit_not_with_nop@0 @1))
+(match (maybe_bit_not @0)
+ (INTEGER_CST@0))
+(match (maybe_bit_not @0)
+ (maybe_cmp@0 @1))
 
 /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
    ABSU_EXPR returns unsigned absolute value of the operand and the operand
@@ -1332,7 +1338,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 
 /* Simplify ~X & X as zero.  */
 (simplify
- (bit_and (convert? @0) (convert? @1))
+ (bit_and:c (convert? @0) (convert? (maybe_bit_not @1)))
  (with { bool wascmp; }
   (if (types_match (TREE_TYPE (@0), TREE_TYPE (@1))
        && bitwise_inverted_equal_p (@0, @1, wascmp))
@@ -1597,7 +1603,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 /* ~x ^ x -> -1 */
 (for op (bit_ior bit_xor)
  (simplify
-  (op (convert? @0) (convert? @1))
+  (op:c (convert? @0) (convert? (maybe_bit_not @1)))
   (with { bool wascmp; }
    (if (types_match (TREE_TYPE (@0), TREE_TYPE (@1))
         && bitwise_inverted_equal_p (@0, @1, wascmp))
-- 
2.43.0

[PATCH 2/2] match: Add support for `a ^ CST` to bitwise_inverted_equal_p [PR115224]

[Andrew Pinski]

While looking into something else, I noticed that `a ^ CST` needed to be
special casing to bitwise_inverted_equal_p as it would simplify to `a ^ ~CST`
for the bitwise not.

Bootstrapped and tested on x86_64-linux-gnu with no regressions.

	PR tree-optimization/115224

gcc/ChangeLog:

	* generic-match-head.cc (bitwise_inverted_equal_p): Add `a ^ CST`
	case.
	* gimple-match-head.cc (gimple_bit_xor_cst): New declaration.
	(gimple_bitwise_inverted_equal_p): Add `a ^ CST` case.
	* match.pd (bit_xor_cst): New match.
	(maybe_bit_not): Add bit_xor_cst case.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/bitops-8.c: New test.

Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>
---
 gcc/generic-match-head.cc                | 10 ++++++++++
 gcc/gimple-match-head.cc                 | 13 +++++++++++++
 gcc/match.pd                             |  4 ++++
 gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c | 15 +++++++++++++++
 4 files changed, 42 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c

diff --git a/gcc/generic-match-head.cc b/gcc/generic-match-head.cc
index e2e1e4b2d64..3709fe5456d 100644
--- a/gcc/generic-match-head.cc
+++ b/gcc/generic-match-head.cc
@@ -156,6 +156,16 @@ bitwise_inverted_equal_p (tree expr1, tree expr2, bool &wascmp)
   if (TREE_CODE (expr2) == BIT_NOT_EXPR
       && bitwise_equal_p (expr1, TREE_OPERAND (expr2, 0)))
     return true;
+
+  /* `X ^ CST` and `X ^ ~CST` match for ~. */
+  if (TREE_CODE (expr1) == BIT_XOR_EXPR && TREE_CODE (expr2) == BIT_XOR_EXPR
+      && bitwise_equal_p (TREE_OPERAND (expr1, 0), TREE_OPERAND (expr2, 0)))
+    {
+      tree cst1 = uniform_integer_cst_p (TREE_OPERAND (expr1, 1));
+      tree cst2 = uniform_integer_cst_p (TREE_OPERAND (expr2, 1));
+      if (cst1 && cst2 && wi::to_wide (cst1) == ~wi::to_wide (cst2))
+	return true;
+    }
   if (COMPARISON_CLASS_P (expr1)
       && COMPARISON_CLASS_P (expr2))
     {
diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
index 49b1dde6ae4..d5908f4e9a6 100644
--- a/gcc/gimple-match-head.cc
+++ b/gcc/gimple-match-head.cc
@@ -283,6 +283,7 @@ gimple_bitwise_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
 
 bool gimple_bit_not_with_nop (tree, tree *, tree (*) (tree));
 bool gimple_maybe_cmp (tree, tree *, tree (*) (tree));
+bool gimple_bit_xor_cst (tree, tree *, tree (*) (tree));
 
 /* Helper function for bitwise_inverted_equal_p macro.  */
 
@@ -299,6 +300,18 @@ gimple_bitwise_inverted_equal_p (tree expr1, tree expr2, bool &wascmp, tree (*va
   if (operand_equal_p (expr1, expr2, 0))
     return false;
 
+  tree xor1[2];
+  tree xor2[2];
+  /* `X ^ CST` and `X ^ ~CST` match for ~. */
+  if (gimple_bit_xor_cst (expr1, xor1, valueize)
+      && gimple_bit_xor_cst (expr2, xor2, valueize))
+    {
+      if (operand_equal_p (xor1[0], xor2[0], 0)
+	  && (wi::to_wide (uniform_integer_cst_p (xor1[1]))
+	      == ~wi::to_wide (uniform_integer_cst_p (xor2[1]))))
+	return true;
+    }
+
   tree other;
   /* Try if EXPR1 was defined as ~EXPR2. */
   if (gimple_bit_not_with_nop (expr1, &other, valueize))
diff --git a/gcc/match.pd b/gcc/match.pd
index 090ad4e08b0..480e36bbbaf 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -174,6 +174,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 (match (bit_not_with_nop @0)
  (convert (bit_not @0))
  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))))
+(match (bit_xor_cst @0 @1)
+ (bit_xor @0 uniform_integer_cst_p@1))
 (for cmp (tcc_comparison)
  (match (maybe_cmp @0)
   (cmp@0 @1 @2))
@@ -195,6 +197,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (INTEGER_CST@0))
 (match (maybe_bit_not @0)
  (maybe_cmp@0 @1))
+(match (maybe_bit_not @0)
+ (bit_xor_cst@0 @1 @2))
 
 /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
    ABSU_EXPR returns unsigned absolute value of the operand and the operand
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c b/gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c
new file mode 100644
index 00000000000..40f756e4455
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
+/* PR tree-optimization/115224 */
+
+int f1(int a, int b)
+{
+        a = a ^ 1;
+        int c = ~a;
+        return c | (a ^ b);
+        // ~((a ^ 1) & b) or (a ^ -2) | ~b
+}
+/* { dg-final { scan-tree-dump-times   "bit_xor_expr, "  1  "optimized" } } */
+/* { dg-final { scan-tree-dump-times   "bit_ior_expr, "  1  "optimized" } } */
+/* { dg-final { scan-tree-dump-times   "bit_not_expr, "  1  "optimized" } } */
+
-- 
2.43.0

Re: [PATCH 1/2] Match: Add maybe_bit_not instead of plain matching

[Richard Biener]

On Mon, May 27, 2024 at 2:47 AM Andrew Pinski <quic_apinski@quicinc.com> wrote:
>
> While working on adding matching of negative expressions of `a - b`,
> I noticed that we started to have "duplicated" patterns due to not having
> a way to match maybe negative expressions. So I went back to what I did for
> bit_not and decided to improve the situtation there so for some patterns
> where we had 2 operands of an expression where one could have been a bit_not,
> add back maybe_bit_not.
> This does not add maybe_bit_not in every place were bitwise_inverted_equal_p
> is used, just the ones were 2 operands of an expression could be swapped.
>
> Bootstrapped and tested on x86_64-linux-gnu with no regressions.

OK.

Richard.

> gcc/ChangeLog:
>
>         * match.pd (bit_not_with_nop): Unconditionalize.
>         (maybe_cmp): Likewise.
>         (maybe_bit_not): New match pattern.
>         (`~X & X`): Use maybe_bit_not and add `:c` back.
>         (`~x ^ x`/`~x | x`): Likewise.
>
> Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>
> ---
>  gcc/match.pd | 14 ++++++++++----
>  1 file changed, 10 insertions(+), 4 deletions(-)
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 024e3350465..090ad4e08b0 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -167,7 +167,6 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>                    TYPE_VECTOR_SUBPARTS (TREE_TYPE (@0)))
>        && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
>
> -#if GIMPLE
>  /* These are used by gimple_bitwise_inverted_equal_p to simplify
>     detection of BIT_NOT and comparisons. */
>  (match (bit_not_with_nop @0)
> @@ -188,7 +187,14 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>   (bit_xor@0 @1 @2)
>   (if (INTEGRAL_TYPE_P (type)
>        && TYPE_PRECISION (type) == 1)))
> -#endif
> +/* maybe_bit_not is used to match what
> +   is acceptable for bitwise_inverted_equal_p. */
> +(match (maybe_bit_not @0)
> + (bit_not_with_nop@0 @1))
> +(match (maybe_bit_not @0)
> + (INTEGER_CST@0))
> +(match (maybe_bit_not @0)
> + (maybe_cmp@0 @1))
>
>  /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
>     ABSU_EXPR returns unsigned absolute value of the operand and the operand
> @@ -1332,7 +1338,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>
>  /* Simplify ~X & X as zero.  */
>  (simplify
> - (bit_and (convert? @0) (convert? @1))
> + (bit_and:c (convert? @0) (convert? (maybe_bit_not @1)))
>   (with { bool wascmp; }
>    (if (types_match (TREE_TYPE (@0), TREE_TYPE (@1))
>         && bitwise_inverted_equal_p (@0, @1, wascmp))
> @@ -1597,7 +1603,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  /* ~x ^ x -> -1 */
>  (for op (bit_ior bit_xor)
>   (simplify
> -  (op (convert? @0) (convert? @1))
> +  (op:c (convert? @0) (convert? (maybe_bit_not @1)))
>    (with { bool wascmp; }
>     (if (types_match (TREE_TYPE (@0), TREE_TYPE (@1))
>          && bitwise_inverted_equal_p (@0, @1, wascmp))
> --
> 2.43.0
>

Re: [PATCH 2/2] match: Add support for `a ^ CST` to bitwise_inverted_equal_p [PR115224]

[Richard Biener]

On Mon, May 27, 2024 at 2:48 AM Andrew Pinski <quic_apinski@quicinc.com> wrote:
>
> While looking into something else, I noticed that `a ^ CST` needed to be
> special casing to bitwise_inverted_equal_p as it would simplify to `a ^ ~CST`
> for the bitwise not.
>
> Bootstrapped and tested on x86_64-linux-gnu with no regressions.

OK.

>         PR tree-optimization/115224
>
> gcc/ChangeLog:
>
>         * generic-match-head.cc (bitwise_inverted_equal_p): Add `a ^ CST`
>         case.
>         * gimple-match-head.cc (gimple_bit_xor_cst): New declaration.
>         (gimple_bitwise_inverted_equal_p): Add `a ^ CST` case.
>         * match.pd (bit_xor_cst): New match.
>         (maybe_bit_not): Add bit_xor_cst case.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/bitops-8.c: New test.
>
> Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>
> ---
>  gcc/generic-match-head.cc                | 10 ++++++++++
>  gcc/gimple-match-head.cc                 | 13 +++++++++++++
>  gcc/match.pd                             |  4 ++++
>  gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c | 15 +++++++++++++++
>  4 files changed, 42 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c
>
> diff --git a/gcc/generic-match-head.cc b/gcc/generic-match-head.cc
> index e2e1e4b2d64..3709fe5456d 100644
> --- a/gcc/generic-match-head.cc
> +++ b/gcc/generic-match-head.cc
> @@ -156,6 +156,16 @@ bitwise_inverted_equal_p (tree expr1, tree expr2, bool &wascmp)
>    if (TREE_CODE (expr2) == BIT_NOT_EXPR
>        && bitwise_equal_p (expr1, TREE_OPERAND (expr2, 0)))
>      return true;
> +
> +  /* `X ^ CST` and `X ^ ~CST` match for ~. */
> +  if (TREE_CODE (expr1) == BIT_XOR_EXPR && TREE_CODE (expr2) == BIT_XOR_EXPR
> +      && bitwise_equal_p (TREE_OPERAND (expr1, 0), TREE_OPERAND (expr2, 0)))
> +    {
> +      tree cst1 = uniform_integer_cst_p (TREE_OPERAND (expr1, 1));
> +      tree cst2 = uniform_integer_cst_p (TREE_OPERAND (expr2, 1));
> +      if (cst1 && cst2 && wi::to_wide (cst1) == ~wi::to_wide (cst2))
> +       return true;
> +    }
>    if (COMPARISON_CLASS_P (expr1)
>        && COMPARISON_CLASS_P (expr2))
>      {
> diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
> index 49b1dde6ae4..d5908f4e9a6 100644
> --- a/gcc/gimple-match-head.cc
> +++ b/gcc/gimple-match-head.cc
> @@ -283,6 +283,7 @@ gimple_bitwise_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
>
>  bool gimple_bit_not_with_nop (tree, tree *, tree (*) (tree));
>  bool gimple_maybe_cmp (tree, tree *, tree (*) (tree));
> +bool gimple_bit_xor_cst (tree, tree *, tree (*) (tree));
>
>  /* Helper function for bitwise_inverted_equal_p macro.  */
>
> @@ -299,6 +300,18 @@ gimple_bitwise_inverted_equal_p (tree expr1, tree expr2, bool &wascmp, tree (*va
>    if (operand_equal_p (expr1, expr2, 0))
>      return false;
>
> +  tree xor1[2];
> +  tree xor2[2];
> +  /* `X ^ CST` and `X ^ ~CST` match for ~. */
> +  if (gimple_bit_xor_cst (expr1, xor1, valueize)
> +      && gimple_bit_xor_cst (expr2, xor2, valueize))
> +    {
> +      if (operand_equal_p (xor1[0], xor2[0], 0)
> +         && (wi::to_wide (uniform_integer_cst_p (xor1[1]))
> +             == ~wi::to_wide (uniform_integer_cst_p (xor2[1]))))
> +       return true;
> +    }
> +
>    tree other;
>    /* Try if EXPR1 was defined as ~EXPR2. */
>    if (gimple_bit_not_with_nop (expr1, &other, valueize))
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 090ad4e08b0..480e36bbbaf 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -174,6 +174,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  (match (bit_not_with_nop @0)
>   (convert (bit_not @0))
>   (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))))
> +(match (bit_xor_cst @0 @1)
> + (bit_xor @0 uniform_integer_cst_p@1))
>  (for cmp (tcc_comparison)
>   (match (maybe_cmp @0)
>    (cmp@0 @1 @2))
> @@ -195,6 +197,8 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>   (INTEGER_CST@0))
>  (match (maybe_bit_not @0)
>   (maybe_cmp@0 @1))
> +(match (maybe_bit_not @0)
> + (bit_xor_cst@0 @1 @2))
>
>  /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
>     ABSU_EXPR returns unsigned absolute value of the operand and the operand
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c b/gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c
> new file mode 100644
> index 00000000000..40f756e4455
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitops-8.c
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
> +/* PR tree-optimization/115224 */
> +
> +int f1(int a, int b)
> +{
> +        a = a ^ 1;
> +        int c = ~a;
> +        return c | (a ^ b);
> +        // ~((a ^ 1) & b) or (a ^ -2) | ~b
> +}
> +/* { dg-final { scan-tree-dump-times   "bit_xor_expr, "  1  "optimized" } } */
> +/* { dg-final { scan-tree-dump-times   "bit_ior_expr, "  1  "optimized" } } */
> +/* { dg-final { scan-tree-dump-times   "bit_not_expr, "  1  "optimized" } } */
> +
> --
> 2.43.0
>