On Thu, Oct 26, 2023 at 11:56 PM Richard Biener
<richard.guent...@gmail.com> wrote:
>
>
>
> > 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?
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
> >
