> Am 26.10.2023 um 23:10 schrieb Andrew Pinski <pins...@gmail.com>:
>
> From: Andrew Pinski <apin...@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
>
