From: Richard Biener <richard.guenther@gmail.com>
To: Andrew Pinski <pinskia@gmail.com>
Cc: gcc-patches@gcc.gnu.org, Andrew Pinski <apinski@marvell.com>
Subject: Re: [PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]
Date: Fri, 27 Oct 2023 08:56:35 +0200 [thread overview]
Message-ID: <24B3B859-0A59-4699-8C3D-2C6D5D4450BF@gmail.com> (raw)
In-Reply-To: <20231026210949.2881006-1-pinskia@gmail.com>
> 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
>
next prev parent reply other threads:[~2023-10-27 6:56 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-10-26 21:09 Andrew Pinski
2023-10-27 6:56 ` Richard Biener [this message]
2023-10-27 7:15 ` Andrew Pinski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=24B3B859-0A59-4699-8C3D-2C6D5D4450BF@gmail.com \
--to=richard.guenther@gmail.com \
--cc=apinski@marvell.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=pinskia@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).