* [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]
@ 2023-10-26 21:09 Andrew Pinski
2023-10-27 6:56 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Andrew Pinski @ 2023-10-26 21:09 UTC (permalink / raw)
To: gcc-patches; +Cc: Andrew Pinski
From: Andrew Pinski <apinski@marvell.com>
I noticed we were missing these simplifications so let's add them.
This adds the following simplifications:
U & N <= U -> true
U & N > U -> false
When U is known to be as non-negative.
When N is also known to be non-negative, this is also true:
U | N < U -> false
U | N >= U -> true
When N is a negative integer, the result flips and we get:
U | N < U -> true
U | N >= U -> false
We could extend this later on to be the case where we know N
is nonconstant but is known to be negative.
Bootstrapped and tested on x86_64-linux-gnu with no regressions.
PR tree-optimization/101590
PR tree-optimization/94884
gcc/ChangeLog:
* match.pd (`(X BIT_OP Y) CMP X`): New pattern.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/bitcmp-1.c: New test.
* gcc.dg/tree-ssa/bitcmp-2.c: New test.
* gcc.dg/tree-ssa/bitcmp-3.c: New test.
* gcc.dg/tree-ssa/bitcmp-4.c: New test.
* gcc.dg/tree-ssa/bitcmp-5.c: New test.
* gcc.dg/tree-ssa/bitcmp-6.c: New test.
---
gcc/match.pd | 24 +++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c | 20 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c | 20 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c | 21 ++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c | 36 ++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c | 43 ++++++++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c | 41 ++++++++++++++++++++++
7 files changed, 205 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 5f6aeb07ac0..7d651a6582d 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2707,6 +2707,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(if (TREE_INT_CST_LOW (@1) & 1)
{ constant_boolean_node (cmp == NE_EXPR, type); })))
+/*
+ U & N <= U -> true
+ U & N > U -> false
+ U needs to be non-negative.
+
+ U | N < U -> false
+ U | N >= U -> true
+ U and N needs to be non-negative
+
+ U | N < U -> true
+ U | N >= U -> false
+ U needs to be non-negative and N needs to be a negative constant.
+ */
+(for cmp (lt ge le gt )
+ bitop (bit_ior bit_ior bit_and bit_and)
+ (simplify
+ (cmp:c (bitop:c tree_expr_nonnegative_p@0 @1) @0)
+ (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
+ (if (bitop == BIT_AND_EXPR || tree_expr_nonnegative_p (@1))
+ { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); }
+ /* The sign is opposite now so the comparison is swapped around. */
+ (if (TREE_CODE (@1) == INTEGER_CST && wi::neg_p (wi::to_wide (@1)))
+ { constant_boolean_node (cmp == LT_EXPR, type); })))))
+
/* Arguments on which one can call get_nonzero_bits to get the bits
possibly set. */
(match with_possible_nonzero_bits
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
new file mode 100644
index 00000000000..f3d515bb2d6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/101590 */
+
+int f_and_le(unsigned len) {
+ const unsigned N = 4;
+ unsigned newlen = len & -N;
+ return newlen <= len; // return 1
+}
+int f_or_ge(unsigned len) {
+ const unsigned N = 4;
+ unsigned newlen = len | -N;
+ return newlen >= len; // return 1
+}
+
+/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
new file mode 100644
index 00000000000..d0031d9ecb8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/101590 */
+
+int f_and_gt(unsigned len) {
+ const unsigned N = 4;
+ unsigned newlen = len & -N;
+ return newlen > len; // return 0
+}
+int f_or_lt(unsigned len) {
+ const unsigned N = 4;
+ unsigned newlen = len | -N;
+ return newlen < len; // return 0
+}
+
+/* { dg-final { scan-tree-dump-not " > " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " < " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" } } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
new file mode 100644
index 00000000000..5cfab7dc742
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/94884 */
+
+#define bool _Bool
+bool decide() __attribute((const));
+
+inline unsigned getXOrY(unsigned x, unsigned y)
+{
+ return decide() ? y : x;
+}
+
+bool f(unsigned x, unsigned y)
+{
+ return (x | y) >= getXOrY(x, y);
+}
+
+
+/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 1 "optimized" } } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
new file mode 100644
index 00000000000..701014b2d0e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/101590 */
+
+int f_and_le(int len) {
+ const int N = 4;
+ int newlen = len & -N;
+ return newlen <= len;
+}
+int f_or_ge(int len) {
+ const int N = 4;
+ int newlen = len | -N;
+ return newlen >= len;
+}
+
+int f_and_gt(int len) {
+ const int N = 4;
+ int newlen = len & -N;
+ return newlen > len;
+}
+int f_or_lt(int len) {
+ const int N = 4;
+ int newlen = len | -N;
+ return newlen < len;
+}
+
+/* These cannot be optimized since we don't know if the sign
+ can change or not. */
+/* { dg-final { scan-tree-dump-times " > " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " < " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " <= " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " >= " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\\| " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "return 1;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "return 0;" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
new file mode 100644
index 00000000000..a6be14294b4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/101590 */
+
+/* These are the signed integer versions
+ of `(a & b) CMP a` and `(a | b) CMP a`
+ which can be optimized to 1. */
+
+
+/* For `&`, the non-negativeness of b is not taken into account. */
+int f_and_le(int len) {
+ len &= 0xfffff;
+ const int N = 4;
+ int newlen = len & -N;
+ return newlen <= len; // return 1
+}
+int f_and_le_(int len, int N) {
+ len &= 0xfffff;
+ int newlen = len & -N;
+ return newlen <= len; // return 1
+}
+
+
+/* For `|`, to get a known value, b either needs to be non-negative
+ or a constant. For the negative constant case, we swap around the comparison. */
+int f_or_ge_(int len, int N) {
+ len &= 0xfffff;
+ N &= 0xffff;
+ int newlen = len | N;
+ return newlen >= len; // return 1
+}
+int f_or_lt(int len) {
+ len &= 0xfffff;
+ const int N = 4;
+ int newlen = len | -N;
+ return newlen < len; // return 1
+}
+
+/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 4 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
new file mode 100644
index 00000000000..a86a19fbef2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/101590 */
+
+/* These are the signed integer versions
+ of `(a & b) CMP a` and `(a | b) CMP a`
+ which can be optimized to 0. */
+
+/* For `&`, the non-negativeness of b is not taken into account. */
+int f_and_gt(int len) {
+ len &= 0xfffff;
+ const int N = 4;
+ int newlen = len & -N;
+ return newlen > len; // return 0
+}
+int f_and_gt_(int len, int N) {
+ len &= 0xfffff;
+ int newlen = len & -N;
+ return newlen > len; // return 0
+}
+
+/* For `|`, to get a known value, b either needs to be non-negative
+ or a constant. For the negative constant case, we swap around the comparison. */
+int f_or_lt_(int len, int N) {
+ len &= 0xfffff;
+ N &= 0xffff;
+ int newlen = len | N;
+ return newlen < len; // return 0
+}
+int f_or_ge(int len) {
+ len &= 0xfffff;
+ const int N = 4;
+ int newlen = len | -N;
+ return newlen >= len; // return 0
+}
+
+/* { dg-final { scan-tree-dump-not " > " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " < " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" } } */
--
2.39.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]
2023-10-26 21:09 [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590] Andrew Pinski
@ 2023-10-27 6:56 ` Richard Biener
2023-10-27 7:15 ` Andrew Pinski
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2023-10-27 6:56 UTC (permalink / raw)
To: Andrew Pinski; +Cc: gcc-patches, Andrew Pinski
> Am 26.10.2023 um 23:10 schrieb Andrew Pinski <pinskia@gmail.com>:
>
> From: Andrew Pinski <apinski@marvell.com>
>
> I noticed we were missing these simplifications so let's add them.
>
> This adds the following simplifications:
> U & N <= U -> true
> U & N > U -> false
> When U is known to be as non-negative.
>
> When N is also known to be non-negative, this is also true:
> U | N < U -> false
> U | N >= U -> true
>
> When N is a negative integer, the result flips and we get:
> U | N < U -> true
> U | N >= U -> false
I think bit-CCP should get this, does ranger also figure this out (iirc it tracks nonzero bits?)
Your testcases suggest this doesn’t happen, can you figure out why CCP doesn’t optimize this and maybe file a bug?
> We could extend this later on to be the case where we know N
> is nonconstant but is known to be negative.
>
> Bootstrapped and tested on x86_64-linux-gnu with no regressions.
Ok
Richard
> PR tree-optimization/101590
> PR tree-optimization/94884
>
> gcc/ChangeLog:
>
> * match.pd (`(X BIT_OP Y) CMP X`): New pattern.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/bitcmp-1.c: New test.
> * gcc.dg/tree-ssa/bitcmp-2.c: New test.
> * gcc.dg/tree-ssa/bitcmp-3.c: New test.
> * gcc.dg/tree-ssa/bitcmp-4.c: New test.
> * gcc.dg/tree-ssa/bitcmp-5.c: New test.
> * gcc.dg/tree-ssa/bitcmp-6.c: New test.
> ---
> gcc/match.pd | 24 +++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c | 20 +++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c | 20 +++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c | 21 ++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c | 36 ++++++++++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c | 43 ++++++++++++++++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c | 41 ++++++++++++++++++++++
> 7 files changed, 205 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 5f6aeb07ac0..7d651a6582d 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2707,6 +2707,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> (if (TREE_INT_CST_LOW (@1) & 1)
> { constant_boolean_node (cmp == NE_EXPR, type); })))
>
> +/*
> + U & N <= U -> true
> + U & N > U -> false
> + U needs to be non-negative.
> +
> + U | N < U -> false
> + U | N >= U -> true
> + U and N needs to be non-negative
> +
> + U | N < U -> true
> + U | N >= U -> false
> + U needs to be non-negative and N needs to be a negative constant.
> + */
> +(for cmp (lt ge le gt )
> + bitop (bit_ior bit_ior bit_and bit_and)
> + (simplify
> + (cmp:c (bitop:c tree_expr_nonnegative_p@0 @1) @0)
> + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
> + (if (bitop == BIT_AND_EXPR || tree_expr_nonnegative_p (@1))
> + { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); }
> + /* The sign is opposite now so the comparison is swapped around. */
> + (if (TREE_CODE (@1) == INTEGER_CST && wi::neg_p (wi::to_wide (@1)))
> + { constant_boolean_node (cmp == LT_EXPR, type); })))))
> +
> /* Arguments on which one can call get_nonzero_bits to get the bits
> possibly set. */
> (match with_possible_nonzero_bits
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
> new file mode 100644
> index 00000000000..f3d515bb2d6
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* PR tree-optimization/101590 */
> +
> +int f_and_le(unsigned len) {
> + const unsigned N = 4;
> + unsigned newlen = len & -N;
> + return newlen <= len; // return 1
> +}
> +int f_or_ge(unsigned len) {
> + const unsigned N = 4;
> + unsigned newlen = len | -N;
> + return newlen >= len; // return 1
> +}
> +
> +/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
> new file mode 100644
> index 00000000000..d0031d9ecb8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* PR tree-optimization/101590 */
> +
> +int f_and_gt(unsigned len) {
> + const unsigned N = 4;
> + unsigned newlen = len & -N;
> + return newlen > len; // return 0
> +}
> +int f_or_lt(unsigned len) {
> + const unsigned N = 4;
> + unsigned newlen = len | -N;
> + return newlen < len; // return 0
> +}
> +
> +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" } } */
> \ No newline at end of file
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
> new file mode 100644
> index 00000000000..5cfab7dc742
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
> @@ -0,0 +1,21 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* PR tree-optimization/94884 */
> +
> +#define bool _Bool
> +bool decide() __attribute((const));
> +
> +inline unsigned getXOrY(unsigned x, unsigned y)
> +{
> + return decide() ? y : x;
> +}
> +
> +bool f(unsigned x, unsigned y)
> +{
> + return (x | y) >= getXOrY(x, y);
> +}
> +
> +
> +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "return 1;" 1 "optimized" } } */
> \ No newline at end of file
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
> new file mode 100644
> index 00000000000..701014b2d0e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
> @@ -0,0 +1,36 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* PR tree-optimization/101590 */
> +
> +int f_and_le(int len) {
> + const int N = 4;
> + int newlen = len & -N;
> + return newlen <= len;
> +}
> +int f_or_ge(int len) {
> + const int N = 4;
> + int newlen = len | -N;
> + return newlen >= len;
> +}
> +
> +int f_and_gt(int len) {
> + const int N = 4;
> + int newlen = len & -N;
> + return newlen > len;
> +}
> +int f_or_lt(int len) {
> + const int N = 4;
> + int newlen = len | -N;
> + return newlen < len;
> +}
> +
> +/* These cannot be optimized since we don't know if the sign
> + can change or not. */
> +/* { dg-final { scan-tree-dump-times " > " 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " < " 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " <= " 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " >= " 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\\| " 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "return 1;" "optimized" } } */
> +/* { dg-final { scan-tree-dump-not "return 0;" "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
> new file mode 100644
> index 00000000000..a6be14294b4
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
> @@ -0,0 +1,43 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* PR tree-optimization/101590 */
> +
> +/* These are the signed integer versions
> + of `(a & b) CMP a` and `(a | b) CMP a`
> + which can be optimized to 1. */
> +
> +
> +/* For `&`, the non-negativeness of b is not taken into account. */
> +int f_and_le(int len) {
> + len &= 0xfffff;
> + const int N = 4;
> + int newlen = len & -N;
> + return newlen <= len; // return 1
> +}
> +int f_and_le_(int len, int N) {
> + len &= 0xfffff;
> + int newlen = len & -N;
> + return newlen <= len; // return 1
> +}
> +
> +
> +/* For `|`, to get a known value, b either needs to be non-negative
> + or a constant. For the negative constant case, we swap around the comparison. */
> +int f_or_ge_(int len, int N) {
> + len &= 0xfffff;
> + N &= 0xffff;
> + int newlen = len | N;
> + return newlen >= len; // return 1
> +}
> +int f_or_lt(int len) {
> + len &= 0xfffff;
> + const int N = 4;
> + int newlen = len | -N;
> + return newlen < len; // return 1
> +}
> +
> +/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "return 1;" 4 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
> new file mode 100644
> index 00000000000..a86a19fbef2
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
> @@ -0,0 +1,41 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* PR tree-optimization/101590 */
> +
> +/* These are the signed integer versions
> + of `(a & b) CMP a` and `(a | b) CMP a`
> + which can be optimized to 0. */
> +
> +/* For `&`, the non-negativeness of b is not taken into account. */
> +int f_and_gt(int len) {
> + len &= 0xfffff;
> + const int N = 4;
> + int newlen = len & -N;
> + return newlen > len; // return 0
> +}
> +int f_and_gt_(int len, int N) {
> + len &= 0xfffff;
> + int newlen = len & -N;
> + return newlen > len; // return 0
> +}
> +
> +/* For `|`, to get a known value, b either needs to be non-negative
> + or a constant. For the negative constant case, we swap around the comparison. */
> +int f_or_lt_(int len, int N) {
> + len &= 0xfffff;
> + N &= 0xffff;
> + int newlen = len | N;
> + return newlen < len; // return 0
> +}
> +int f_or_ge(int len) {
> + len &= 0xfffff;
> + const int N = 4;
> + int newlen = len | -N;
> + return newlen >= len; // return 0
> +}
> +
> +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" } } */
> --
> 2.39.3
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]
2023-10-27 6:56 ` Richard Biener
@ 2023-10-27 7:15 ` Andrew Pinski
0 siblings, 0 replies; 3+ messages in thread
From: Andrew Pinski @ 2023-10-27 7:15 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, Andrew Pinski
On Thu, Oct 26, 2023 at 11:56 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
>
>
> > Am 26.10.2023 um 23:10 schrieb Andrew Pinski <pinskia@gmail.com>:
> >
> > From: Andrew Pinski <apinski@marvell.com>
> >
> > I noticed we were missing these simplifications so let's add them.
> >
> > This adds the following simplifications:
> > U & N <= U -> true
> > U & N > U -> false
> > When U is known to be as non-negative.
> >
> > When N is also known to be non-negative, this is also true:
> > U | N < U -> false
> > U | N >= U -> true
> >
> > When N is a negative integer, the result flips and we get:
> > U | N < U -> true
> > U | N >= U -> false
>
> I think bit-CCP should get this, does ranger also figure this out (iirc it tracks nonzero bits?)
>
> Your testcases suggest this doesn’t happen, can you figure out why CCP doesn’t optimize this and maybe file a bug?
CCP and ranger is able to figure when N is a negative constant.
Otherwise no. I only added this to the testcase/match because I
originally messed up that case while working on the patch and noticed
different answers.
Thanks,
Andrew
>
> > We could extend this later on to be the case where we know N
> > is nonconstant but is known to be negative.
> >
> > Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>
> Ok
>
> Richard
>
> > PR tree-optimization/101590
> > PR tree-optimization/94884
> >
> > gcc/ChangeLog:
> >
> > * match.pd (`(X BIT_OP Y) CMP X`): New pattern.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/bitcmp-1.c: New test.
> > * gcc.dg/tree-ssa/bitcmp-2.c: New test.
> > * gcc.dg/tree-ssa/bitcmp-3.c: New test.
> > * gcc.dg/tree-ssa/bitcmp-4.c: New test.
> > * gcc.dg/tree-ssa/bitcmp-5.c: New test.
> > * gcc.dg/tree-ssa/bitcmp-6.c: New test.
> > ---
> > gcc/match.pd | 24 +++++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c | 20 +++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c | 20 +++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c | 21 ++++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c | 36 ++++++++++++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c | 43 ++++++++++++++++++++++++
> > gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c | 41 ++++++++++++++++++++++
> > 7 files changed, 205 insertions(+)
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
> > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
> >
> > diff --git a/gcc/match.pd b/gcc/match.pd
> > index 5f6aeb07ac0..7d651a6582d 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -2707,6 +2707,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> > (if (TREE_INT_CST_LOW (@1) & 1)
> > { constant_boolean_node (cmp == NE_EXPR, type); })))
> >
> > +/*
> > + U & N <= U -> true
> > + U & N > U -> false
> > + U needs to be non-negative.
> > +
> > + U | N < U -> false
> > + U | N >= U -> true
> > + U and N needs to be non-negative
> > +
> > + U | N < U -> true
> > + U | N >= U -> false
> > + U needs to be non-negative and N needs to be a negative constant.
> > + */
> > +(for cmp (lt ge le gt )
> > + bitop (bit_ior bit_ior bit_and bit_and)
> > + (simplify
> > + (cmp:c (bitop:c tree_expr_nonnegative_p@0 @1) @0)
> > + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
> > + (if (bitop == BIT_AND_EXPR || tree_expr_nonnegative_p (@1))
> > + { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); }
> > + /* The sign is opposite now so the comparison is swapped around. */
> > + (if (TREE_CODE (@1) == INTEGER_CST && wi::neg_p (wi::to_wide (@1)))
> > + { constant_boolean_node (cmp == LT_EXPR, type); })))))
> > +
> > /* Arguments on which one can call get_nonzero_bits to get the bits
> > possibly set. */
> > (match with_possible_nonzero_bits
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
> > new file mode 100644
> > index 00000000000..f3d515bb2d6
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c
> > @@ -0,0 +1,20 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +/* PR tree-optimization/101590 */
> > +
> > +int f_and_le(unsigned len) {
> > + const unsigned N = 4;
> > + unsigned newlen = len & -N;
> > + return newlen <= len; // return 1
> > +}
> > +int f_or_ge(unsigned len) {
> > + const unsigned N = 4;
> > + unsigned newlen = len | -N;
> > + return newlen >= len; // return 1
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
> > new file mode 100644
> > index 00000000000..d0031d9ecb8
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c
> > @@ -0,0 +1,20 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +/* PR tree-optimization/101590 */
> > +
> > +int f_and_gt(unsigned len) {
> > + const unsigned N = 4;
> > + unsigned newlen = len & -N;
> > + return newlen > len; // return 0
> > +}
> > +int f_or_lt(unsigned len) {
> > + const unsigned N = 4;
> > + unsigned newlen = len | -N;
> > + return newlen < len; // return 0
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" } } */
> > \ No newline at end of file
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
> > new file mode 100644
> > index 00000000000..5cfab7dc742
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c
> > @@ -0,0 +1,21 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +/* PR tree-optimization/94884 */
> > +
> > +#define bool _Bool
> > +bool decide() __attribute((const));
> > +
> > +inline unsigned getXOrY(unsigned x, unsigned y)
> > +{
> > + return decide() ? y : x;
> > +}
> > +
> > +bool f(unsigned x, unsigned y)
> > +{
> > + return (x | y) >= getXOrY(x, y);
> > +}
> > +
> > +
> > +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "return 1;" 1 "optimized" } } */
> > \ No newline at end of file
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
> > new file mode 100644
> > index 00000000000..701014b2d0e
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c
> > @@ -0,0 +1,36 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +/* PR tree-optimization/101590 */
> > +
> > +int f_and_le(int len) {
> > + const int N = 4;
> > + int newlen = len & -N;
> > + return newlen <= len;
> > +}
> > +int f_or_ge(int len) {
> > + const int N = 4;
> > + int newlen = len | -N;
> > + return newlen >= len;
> > +}
> > +
> > +int f_and_gt(int len) {
> > + const int N = 4;
> > + int newlen = len & -N;
> > + return newlen > len;
> > +}
> > +int f_or_lt(int len) {
> > + const int N = 4;
> > + int newlen = len | -N;
> > + return newlen < len;
> > +}
> > +
> > +/* These cannot be optimized since we don't know if the sign
> > + can change or not. */
> > +/* { dg-final { scan-tree-dump-times " > " 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " < " 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " <= " 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " >= " 1 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times " \\\| " 2 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not "return 1;" "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not "return 0;" "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
> > new file mode 100644
> > index 00000000000..a6be14294b4
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c
> > @@ -0,0 +1,43 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +/* PR tree-optimization/101590 */
> > +
> > +/* These are the signed integer versions
> > + of `(a & b) CMP a` and `(a | b) CMP a`
> > + which can be optimized to 1. */
> > +
> > +
> > +/* For `&`, the non-negativeness of b is not taken into account. */
> > +int f_and_le(int len) {
> > + len &= 0xfffff;
> > + const int N = 4;
> > + int newlen = len & -N;
> > + return newlen <= len; // return 1
> > +}
> > +int f_and_le_(int len, int N) {
> > + len &= 0xfffff;
> > + int newlen = len & -N;
> > + return newlen <= len; // return 1
> > +}
> > +
> > +
> > +/* For `|`, to get a known value, b either needs to be non-negative
> > + or a constant. For the negative constant case, we swap around the comparison. */
> > +int f_or_ge_(int len, int N) {
> > + len &= 0xfffff;
> > + N &= 0xffff;
> > + int newlen = len | N;
> > + return newlen >= len; // return 1
> > +}
> > +int f_or_lt(int len) {
> > + len &= 0xfffff;
> > + const int N = 4;
> > + int newlen = len | -N;
> > + return newlen < len; // return 1
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "return 1;" 4 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
> > new file mode 100644
> > index 00000000000..a86a19fbef2
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c
> > @@ -0,0 +1,41 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-optimized" } */
> > +/* PR tree-optimization/101590 */
> > +
> > +/* These are the signed integer versions
> > + of `(a & b) CMP a` and `(a | b) CMP a`
> > + which can be optimized to 0. */
> > +
> > +/* For `&`, the non-negativeness of b is not taken into account. */
> > +int f_and_gt(int len) {
> > + len &= 0xfffff;
> > + const int N = 4;
> > + int newlen = len & -N;
> > + return newlen > len; // return 0
> > +}
> > +int f_and_gt_(int len, int N) {
> > + len &= 0xfffff;
> > + int newlen = len & -N;
> > + return newlen > len; // return 0
> > +}
> > +
> > +/* For `|`, to get a known value, b either needs to be non-negative
> > + or a constant. For the negative constant case, we swap around the comparison. */
> > +int f_or_lt_(int len, int N) {
> > + len &= 0xfffff;
> > + N &= 0xffff;
> > + int newlen = len | N;
> > + return newlen < len; // return 0
> > +}
> > +int f_or_ge(int len) {
> > + len &= 0xfffff;
> > + const int N = 4;
> > + int newlen = len | -N;
> > + return newlen >= len; // return 0
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" } } */
> > --
> > 2.39.3
> >
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-10-27 7:16 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-10-26 21:09 [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590] Andrew Pinski
2023-10-27 6:56 ` Richard Biener
2023-10-27 7:15 ` Andrew Pinski
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).