From: Jiufu Guo <guojiufu@linux.ibm.com>
To: gcc-patches@gcc.gnu.org
Cc: rguenther@suse.de, jeffreyalaw@gmail.com,
richard.sandiford@arm.com, segher@kernel.crashing.org,
bergner@linux.ibm.com, linkw@gcc.gnu.org, guojiufu@linux.ibm.com
Subject: [PATCH V2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
Date: Wed, 7 Jun 2023 16:21:11 +0800 [thread overview]
Message-ID: <20230607082111.2773414-1-guojiufu@linux.ibm.com> (raw)
Hi,
This patch tries to optimize "(X - N * M) / N" to "X / N - M".
For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
wrap/overflow/underflow. So, it is valid that "X - N * M" does
not cross zero and does not wrap/overflow/underflow.
Compare with previous version:
https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
This patch 1. adds the patterns for variable N or M,
2. uses simpler form "(X - N * M) / N" for patterns,
3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
4. updates testcases
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:
* gimple-fold.cc (maybe_mult_overflow): New function.
(maybe_plus_overflow): New function.
(maybe_minus_overflow): New function.
(plus_mult_no_ovf_and_keep_sign): New function.
(plus_no_ovf_and_keep_sign): New function.
* gimple-fold.h (maybe_mult_overflow): New declare.
(plus_mult_no_ovf_and_keep_sign): New declare.
(plus_no_ovf_and_keep_sign): New declare.
* match.pd ((X - N * M) / N): New pattern.
((X + N * M) / N): New pattern.
((X + C) / N): New pattern.
((X + C) >> 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/gimple-fold.cc | 161 ++++++++++++++++++++
gcc/gimple-fold.h | 3 +
gcc/match.pd | 58 +++++++
gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
gcc/testsuite/gcc.dg/pr108757.h | 244 ++++++++++++++++++++++++++++++
6 files changed, 503 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/gimple-fold.cc b/gcc/gimple-fold.cc
index 581575b65ec..bb833ae17b3 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
return false;
}
}
+
+/* Return true if "X * Y" may be overflow. */
+
+bool
+maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
+{
+ wide_int wmin0 = x.lower_bound ();
+ wide_int wmax0 = x.upper_bound ();
+ wide_int wmin1 = y.lower_bound ();
+ wide_int wmax1 = y.upper_bound ();
+
+ wi::overflow_type min_ovf, max_ovf;
+ wi::mul (wmin0, wmin1, sgn, &min_ovf);
+ wi::mul (wmax0, wmax1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ {
+ wi::mul (wmin0, wmax1, sgn, &min_ovf);
+ wi::mul (wmax0, wmin1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ return false;
+ }
+ return true;
+}
+
+/* Return true if "X + Y" may be overflow. */
+
+static bool
+maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
+{
+ wide_int wmin0 = x.lower_bound ();
+ wide_int wmax0 = x.upper_bound ();
+ wide_int wmin1 = y.lower_bound ();
+ wide_int wmax1 = y.upper_bound ();
+
+ wi::overflow_type min_ovf, max_ovf;
+ wi::add (wmax0, wmax1, sgn, &min_ovf);
+ wi::add (wmin0, wmin1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if "X - Y" may be overflow. */
+
+static bool
+maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
+{
+ wide_int wmin0 = x.lower_bound ();
+ wide_int wmax0 = x.upper_bound ();
+ wide_int wmin1 = y.lower_bound ();
+ wide_int wmax1 = y.upper_bound ();
+
+ wi::overflow_type min_ovf, max_ovf;
+ wi::sub (wmin0, wmax1, sgn, &min_ovf);
+ wi::sub (wmax0, wmin1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if there is no overflow in the expression.
+ And no sign change on the plus/minus for X.
+ CODE is PLUS_EXPR, if the expression is "X + N * M".
+ CODE is MINUS_EXPR, if the expression is "X - N * M".
+ TYPE is the integer type of the expressions. */
+
+bool
+plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
+ tree type)
+{
+ value_range vr0;
+ value_range vr1;
+ value_range vr2;
+
+ if (get_range_query (cfun)->range_of_expr (vr0, x)
+ && get_range_query (cfun)->range_of_expr (vr1, n)
+ && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
+ && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
+ && !vr2.varying_p () && !vr2.undefined_p ())
+ {
+ signop sgn = TYPE_SIGN (type);
+ if (!TYPE_OVERFLOW_UNDEFINED (type))
+ {
+ if (maybe_mult_overflow (vr1, vr2, sgn))
+ {
+ m = fold_build1 (NEGATE_EXPR, type, m);
+ if (get_range_query (cfun)->range_of_expr (vr2, m)
+ && !vr2.varying_p () && !vr2.undefined_p ()
+ && !maybe_mult_overflow (vr1, vr2, sgn))
+ code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
+ else
+ return false;
+ }
+
+ /* Get range of N*M */
+ tree mult = fold_build2 (MULT_EXPR, type, n, m);
+ value_range vr3;
+ bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
+ gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
+
+ bool overflow = code == MINUS_EXPR
+ ? maybe_minus_overflow (vr0, vr3, sgn)
+ : maybe_plus_overflow (vr0, vr3, sgn);
+ if (overflow)
+ return false;
+ }
+
+ /* The value cross "0" is also a concern. */
+ if (sgn == UNSIGNED)
+ return true;
+ tree op
+ = fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
+ value_range vr4;
+ if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
+ && !vr4.undefined_p ())
+ {
+ /* X and (X +- N*M) are both positive (or both negtive). */
+ if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
+ && wi::ge_p (vr4.lower_bound (), 0, sgn))
+ || (wi::le_p (vr0.upper_bound (), 0, sgn)
+ && wi::le_p (vr4.upper_bound (), 0, sgn)))
+ return true;
+ }
+ }
+
+return false;
+}
+
+/* Return true if there is no overflow and no sign change in "X + C".
+ C is a constant integer. */
+
+bool
+plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
+{
+ value_range vr;
+ if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
+ && !vr.undefined_p ())
+ {
+ wi::overflow_type ovf = wi::OVF_NONE;
+ wide_int min = vr.lower_bound ();
+ wide_int max = vr.upper_bound ();
+ wide_int wc = wi::to_wide (c);
+ if (!TYPE_OVERFLOW_UNDEFINED (type))
+ {
+ if (tree_int_cst_sign_bit (c))
+ wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
+ else
+ wi::add (max, wc, TYPE_SIGN (type), &ovf);
+ }
+ if (ovf == wi::OVF_NONE)
+ /* unsigned, or 't' and 't + C' are both positive/negative. */
+ if (TYPE_UNSIGNED (type)
+ || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
+ || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
+ return true;
+ }
+
+ return false;
+}
diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
index 2fd58db9a2e..45df86a433e 100644
--- a/gcc/gimple-fold.h
+++ b/gcc/gimple-fold.h
@@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
extern void replace_call_with_value (gimple_stmt_iterator *, tree);
extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
+extern bool maybe_mult_overflow (tree, tree, tree);
+extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
+extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
/* gimple_build, functionally matching fold_buildN, outputs stmts
int the provided sequence, matching and simplifying them on-the-fly.
diff --git a/gcc/match.pd b/gcc/match.pd
index 16482b741ea..6f7a6afdca8 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -942,6 +942,64 @@ 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 @0 (mult:c @1 @2)) @2)
+ (if (INTEGRAL_TYPE_P (type)
+ && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
+ (plus (div @0 @2) @1)))
+
+ /* Simplify (t - M*N) / N -> t / N - M. */
+ (simplify
+ (div (minus @0 (mult:c @1 @2)) @2)
+ (if (INTEGRAL_TYPE_P (type)
+ && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR, type))
+ (minus (div @0 @2) @1)))
+
+ /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N */
+ (simplify
+ (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
+ (with
+ { tree repaired_c = @1;
+ if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+ repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
+ }
+ (if (INTEGRAL_TYPE_P (type)
+ && multiple_of_p (type, repaired_c, @2)
+ && plus_no_ovf_and_keep_sign (@0, @1, type))
+ (with
+ { wide_int m;
+ wide_int c = wi::to_wide (@1);
+ wide_int n = wi::to_wide (@2);
+ wi::overflow_type ovf;
+ if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+ m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
+ else
+ m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
+ gcc_assert (ovf == wi::OVF_NONE);
+ }
+ (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
+
+/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */
+(simplify
+ (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
+ && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
+ && plus_no_ovf_and_keep_sign (@0, @1, type))
+ (with
+ { wide_int m;
+ wide_int c = wi::to_wide (@1);
+ wide_int n = wi::to_wide (@2);
+ if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+ m = -wi::rshift (-c, n, TYPE_SIGN (type));
+ else
+ m = wi::rshift (c, n, TYPE_SIGN (type));
+ }
+ (plus (rshift @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..7e7b60c756d
--- /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..2a9ad234e68
--- /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\\) \\- " 4 "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..9dfa527f533
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757.h
@@ -0,0 +1,244 @@
+#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;
+}
+
+UINT NOINLINE
+opt_u7 (UINT x, UINT n, UINT m)
+{
+ if (n > N || m <= UMAX - M)
+ return 0;
+ if (x > UMAX - (M*N) + GAP)
+ return 0;
+ UINT a = x - (m * n);
+ UINT b = a / n;
+ return b + m;
+}
--
2.39.1
next reply other threads:[~2023-06-07 8:21 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-06-07 8:21 Jiufu Guo [this message]
2023-06-09 8:44 ` Richard Biener
2023-06-09 13:38 ` Jiufu Guo
2023-06-09 20:26 ` Segher Boessenkool
2023-06-12 2:40 ` Jiufu Guo
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=20230607082111.2773414-1-guojiufu@linux.ibm.com \
--to=guojiufu@linux.ibm.com \
--cc=bergner@linux.ibm.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).