From: guojiufu <guojiufu@linux.ibm.com>
To: rguenther@suse.de, jeffreyalaw@gmail.com,
richard.sandiford@arm.com, guojiufu <guojiufu@linux.ibm.com>
Cc: gcc-patches@gcc.gnu.org, amacleod@redhat.com, aldyh@redhat.com,
segher@kernel.crashing.org, dje.gcc@gmail.com, linkw@gcc.gnu.org,
bergner@linux.ibm.com
Subject: Ping^^ [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
Date: Wed, 23 Aug 2023 10:04:47 +0800 [thread overview]
Message-ID: <11eab982cf225b32e34e8d9c5f7f1947@linux.ibm.com> (raw)
In-Reply-To: <c4a0e6093ec5fb5771215caf7a749067@linux.ibm.com>
Hi,
I would like to have a gentle ping...
BR,
Jeff (Jiufu Guo)
On 2023-08-07 10:45, guojiufu via Gcc-patches wrote:
> Hi,
>
> Gentle ping...
>
> On 2023-07-18 22:05, Jiufu Guo wrote:
>> Hi,
>>
>> Integer expression "(X - N * M) / N" can be optimized to "X / N - M"
>> if there is no wrap/overflow/underflow and "X - N * M" has the same
>> sign with "X".
>>
>> Compare the previous version:
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
>> - APIs: overflow, nonnegative_p and nonpositive_p are moved close
>> to value range.
>> - Use above APIs in match.pd.
>>
>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>> Is this patch ok for trunk?
>>
>> BR,
>> Jeff (Jiufu Guo)
>>
>> PR tree-optimization/108757
>>
>> gcc/ChangeLog:
>>
>> * match.pd ((X - N * M) / N): New pattern.
>> ((X + N * M) / N): New pattern.
>> ((X + C) div_rshift N): New pattern.
>>
>> gcc/testsuite/ChangeLog:
>>
>> * gcc.dg/pr108757-1.c: New test.
>> * gcc.dg/pr108757-2.c: New test.
>> * gcc.dg/pr108757.h: New test.
>>
>> ---
>> gcc/match.pd | 85 +++++++++++
>> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
>> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
>> gcc/testsuite/gcc.dg/pr108757.h | 233
>> ++++++++++++++++++++++++++++++
>> 4 files changed, 355 insertions(+)
>> create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
>> create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
>> create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
>>
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 8543f777a28..39dbb0567dc 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -942,6 +942,91 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>> #endif
>> ))))
>>
>> +#if GIMPLE
>> +(for div (trunc_div exact_div)
>> + /* Simplify (t + M*N) / N -> t / N + M. */
>> + (simplify
>> + (div (plus:c@4 @0 (mult:c@3 @1 @2)) @2)
>> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
>> + (if (INTEGRAL_TYPE_P (type)
>> + && get_range_query (cfun)->range_of_expr (vr1, @1)
>> + && get_range_query (cfun)->range_of_expr (vr2, @2)
>> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
>> + && get_range_query (cfun)->range_of_expr (vr0, @0)
>> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
>> + && get_range_query (cfun)->range_of_expr (vr4, @4)
>> + && (TYPE_UNSIGNED (type)
>> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
>> + (plus (div @0 @2) @1))))
>> +
>> + /* Simplify (t - M*N) / N -> t / N - M. */
>> + (simplify
>> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
>> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
>> + (if (INTEGRAL_TYPE_P (type)
>> + && get_range_query (cfun)->range_of_expr (vr1, @1)
>> + && get_range_query (cfun)->range_of_expr (vr2, @2)
>> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
>> + && get_range_query (cfun)->range_of_expr (vr0, @0)
>> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> + && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
>> + && get_range_query (cfun)->range_of_expr (vr4, @4)
>> + && (TYPE_UNSIGNED (type)
>> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
>> + (minus (div @0 @2) @1)))))
>> +
>> +/* Simplify
>> + (t + C) / N -> t / N + C / N where C is multiple of N.
>> + (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */
>> +(for op (trunc_div exact_div rshift)
>> + (simplify
>> + (op (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)
>> + (with
>> + {
>> + wide_int c = wi::to_wide (@1);
>> + wide_int n = wi::to_wide (@2);
>> + bool is_rshift = op == RSHIFT_EXPR;
>> + bool neg_c = false;
>> + bool ok = false;
>> + value_range vr0;
>> + if (INTEGRAL_TYPE_P (type)
>> + && get_range_query (cfun)->range_of_expr (vr0, @0))
>> + {
>> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
>> + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
>> + value_range vr1, vr3;
>> + ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1)
>> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
>> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> + && (TYPE_UNSIGNED (type)
>> + || (vr0.nonnegative_p () && vr3.nonnegative_p ())
>> + || (vr0.nonpositive_p () && vr3.nonpositive_p ()));
>> +
>> + /* Try check 'X + C' as 'X - -C' for unsigned. */
>> + if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0)
>> + {
>> + neg_c = true;
>> + c = -c;
>> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
>> + : wi::multiple_of_p (c, n, UNSIGNED);
>> + ok = ok && wi::geu_p (vr0.lower_bound (), c);
>> + }
>> + }
>> + }
>> + (if (ok)
>> + (with
>> + {
>> + wide_int m;
>> + m = is_rshift ? wi::rshift (c, n, TYPE_SIGN (type))
>> + : wi::div_trunc (c, n, TYPE_SIGN (type));
>> + m = neg_c ? -m : m;
>> + }
>> + (plus (op @0 @2) { wide_int_to_tree(type, m); }))))))
>> +#endif
>> +
>> (for op (negate abs)
>> /* Simplify cos(-x) and cos(|x|) -> cos(x). Similarly for cosh. */
>> (for coss (COS COSH)
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c
>> b/gcc/testsuite/gcc.dg/pr108757-1.c
>> new file mode 100644
>> index 00000000000..7908f4bdcb8
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
>> @@ -0,0 +1,18 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +#include <limits.h>
>> +#define N 5
>> +#define M 3
>> +#define GAP 0
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ "
>> "optimized" } } *
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- "
>> "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" }
>> } */
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c
>> b/gcc/testsuite/gcc.dg/pr108757-2.c
>> new file mode 100644
>> index 00000000000..82bebd09944
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
>> @@ -0,0 +1,19 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
>> +
>> +#include <limits.h>
>> +#define N 4
>> +#define M 3
>> +#define GAP 2
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16
>> "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3
>> "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3
>> "optimized" } } */
>> +
>> diff --git a/gcc/testsuite/gcc.dg/pr108757.h
>> b/gcc/testsuite/gcc.dg/pr108757.h
>> new file mode 100644
>> index 00000000000..5550199c1ef
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757.h
>> @@ -0,0 +1,233 @@
>> +#define NOINLINE __attribute__ ((noinline))
>> +UINT NOINLINE
>> +opt_u1 (UINT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + UINT a = x - (M * N);
>> + UINT b = a / N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u2 (UINT x)
>> +{
>> + if (x > (UMAX - (M * N) + GAP))
>> + return 0;
>> + UINT a = x + (M * N);
>> + UINT b = a / N;
>> + return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s1 (INT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s2 (INT x)
>> +{
>> + if (x < IMIN + (M * N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s3 (INT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / -N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s4 (INT x)
>> +{
>> + if (x < IMIN + (M * N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / -N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s5 (INT x)
>> +{
>> + if (x > (-M * N) + GAP)
>> + return 0;
>> + INT a = x - (-M * N);
>> + INT b = a / N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s6 (INT x)
>> +{
>> + if (x > IMAX - (M * N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (-M * N);
>> + INT b = a / N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s7 (INT x)
>> +{
>> + if (x > (M * -N) + GAP)
>> + return 0;
>> + INT a = x - (M * -N);
>> + INT b = a / -N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s8 (INT x)
>> +{
>> + if (x > IMAX - (M * N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (M * -N);
>> + INT b = a / -N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u3 (UINT x)
>> +{
>> + if (x < (M << N) - GAP)
>> + return 0;
>> + UINT a = x - (M << N);
>> + UINT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u4 (UINT x)
>> +{
>> + if (x > (UMAX - (M << N)) + GAP)
>> + return 0;
>> + UINT a = x + (M << N);
>> + UINT b = a >> N;
>> + return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s9 (INT x)
>> +{
>> + if (x < (M << N) - GAP)
>> + return 0;
>> + INT a = x - (M << N);
>> + INT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s10 (INT x)
>> +{
>> + if (x < IMIN + (M << N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M << N);
>> + INT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s11 (INT x)
>> +{
>> + if (x > (-M << N) + GAP)
>> + return 0;
>> + INT a = x - (-M << N);
>> + INT b = a >> N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s12 (INT x)
>> +{
>> + if (x > IMAX - (M << N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (-M << N);
>> + INT b = a >> N;
>> + return b + -M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u5 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m > M)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + UINT a = x - (m * n);
>> + UINT b = a / n;
>> + return b + m;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u6 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m > M)
>> + return 0;
>> + if (x > (UMAX - M*N) + GAP)
>> + return 0;
>> + UINT a = x + (m * n);
>> + UINT b = a / n;
>> + return b - m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s13 (INT x, INT n, INT m)
>> +{
>> + if (n > N || m > M || n < 0 || m < 0)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + INT a = x - (m * n);
>> + INT b = a / n;
>> + return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s14 (INT x, INT n, INT m)
>> +{
>> + if (n > N || m > M || n < 0 || m < 0)
>> + return 0;
>> + if (x > -M*N + GAP)
>> + return 0;
>> + INT a = x + (m * n);
>> + INT b = a / n;
>> + return b - m;
>> +}
>> +
>> +INT
>> +opt_s15 (INT x, INT n, INT m)
>> +{
>> + if (n > 0 || m > 0 || n < -N || m < -M)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + INT a = x - (m * n);
>> + INT b = a / n;
>> + return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s16 (INT x, INT n, INT m)
>> +{
>> + if (n > 0 || m > 0 || n < -N || m < -M)
>> + return 0;
>> + if (x < 0 || x > (IMAX - M*N) + GAP)
>> + return 0;
>> + INT a = x + (m * n);
>> + INT b = a / n;
>> + return b - m;
>> +}
>> +
next prev parent reply other threads:[~2023-08-23 2:04 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-07-18 14:05 [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
2023-07-18 14:05 ` [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
2023-08-07 2:45 ` guojiufu
2023-08-23 2:04 ` guojiufu [this message]
2023-08-28 13:14 ` Ping^^ " Richard Biener
2023-08-29 7:25 ` Jiufu Guo
2023-08-03 2:18 ` [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
2023-08-03 13:18 ` Andrew MacLeod
2023-08-31 5:07 ` guojiufu
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=11eab982cf225b32e34e8d9c5f7f1947@linux.ibm.com \
--to=guojiufu@linux.ibm.com \
--cc=aldyh@redhat.com \
--cc=amacleod@redhat.com \
--cc=bergner@linux.ibm.com \
--cc=dje.gcc@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jeffreyalaw@gmail.com \
--cc=linkw@gcc.gnu.org \
--cc=rguenther@suse.de \
--cc=richard.sandiford@arm.com \
--cc=segher@kernel.crashing.org \
/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).