* [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid
@ 2023-06-28 7:16 Jiufu Guo
2023-06-29 3:06 ` Jiufu Guo
0 siblings, 1 reply; 4+ messages in thread
From: Jiufu Guo @ 2023-06-28 7:16 UTC (permalink / raw)
To: gcc-patches
Cc: rguenther, jeffreyalaw, richard.sandiford, segher, dje.gcc,
linkw, bergner, guojiufu
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 with the previous version:
https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620896.html
This version changes:
1. Remove the behavior to convert 'm' to '-m' for unsigned variable.
This kind of case is rare, and it makes the code ambiguous.
2. Use the 'capture' expression and avoid building new expressions.
3. Add APIs like get_range and nonpositive/nonnegative.
4. Refactor patterns in match.pd and function names and signatures.
While some APIs are still in gimple-fold.cc/h. Tried to add them
to other files, but did not find a better place.
Thanks for comments/suggestions!
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 (mult_without_overflow_p): New function.
(plus_without_overflow_p): New function.
(minus_without_overflow_p): New function.
(same_sign_p): New function.
* gimple-fold.h (mult_without_overflow_p): New declare.
(plus_without_overflow_p): New declare.
(minus_without_overflow_p): New declare.
(same_sign_p): New declare.
* match.pd ((X - N * M) / N): New pattern.
((X + N * M) / N): New pattern.
((X + C) div_rshift N): New pattern.
* value-query.h (get_range): New function.
* value-range.cc (irange::nonnegative_p): New function.
(irange::nonpositive_p): New function.
* value-range.h (irange::nonnegative_p): New declare.
(irange::nonpositive_p): New declare.
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 | 132 +++++++++++++++++
gcc/gimple-fold.h | 4 +
gcc/match.pd | 54 +++++++
gcc/value-query.h | 10 ++
gcc/value-range.cc | 12 ++
gcc/value-range.h | 2 +
gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
gcc/testsuite/gcc.dg/pr108757.h | 233 ++++++++++++++++++++++++++++++
9 files changed, 484 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..c0703b45c4b 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -9349,3 +9349,135 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
return false;
}
}
+
+/* Return true if "X * Y" may be overflow on integer TYPE. */
+
+bool
+mult_without_overflow_p (tree x, tree y, tree type)
+{
+ gcc_assert (INTEGRAL_TYPE_P (type));
+
+ if (TYPE_OVERFLOW_UNDEFINED (type))
+ return true;
+
+ value_range vr0;
+ value_range vr1;
+ if (!(get_range (vr0, x) && get_range (vr1, y)))
+ return false;
+
+ wi::overflow_type ovf;
+ signop sgn = TYPE_SIGN (type);
+ wide_int wmax0 = vr0.upper_bound ();
+ wide_int wmax1 = vr1.upper_bound ();
+ wi::mul (wmax0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ wide_int wmin0 = vr0.lower_bound ();
+ wide_int wmin1 = vr1.lower_bound ();
+ wi::mul (wmin0, wmin1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ wi::mul (wmin0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ wi::mul (wmax0, wmin1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if "X + Y" may be overflow on integer TYPE. */
+
+bool
+plus_without_overflow_p (tree x, tree y, tree type)
+{
+ gcc_assert (INTEGRAL_TYPE_P (type));
+
+ if (TYPE_OVERFLOW_UNDEFINED (type))
+ return true;
+
+ value_range vr0;
+ value_range vr1;
+ if (!(get_range (vr0, x) && get_range (vr1, y)))
+ return false;
+
+ wi::overflow_type ovf;
+ signop sgn = TYPE_SIGN (type);
+ wide_int wmax0 = vr0.upper_bound ();
+ wide_int wmax1 = vr1.upper_bound ();
+ wi::add (wmax0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ wide_int wmin0 = vr0.lower_bound ();
+ wide_int wmin1 = vr1.lower_bound ();
+ wi::add (wmin0, wmin1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if "X - Y" may be overflow on integer TYPE. */
+
+bool
+minus_without_overflow_p (tree x, tree y, tree type)
+{
+ gcc_assert (INTEGRAL_TYPE_P (type));
+
+ if (TYPE_OVERFLOW_UNDEFINED (type))
+ return true;
+
+ value_range vr0;
+ value_range vr1;
+ if (!(get_range (vr0, x) && get_range (vr1, y)))
+ return false;
+
+ wi::overflow_type ovf;
+ signop sgn = TYPE_SIGN (type);
+ wide_int wmin0 = vr0.lower_bound ();
+ wide_int wmax1 = vr1.upper_bound ();
+ wi::sub (wmin0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ wide_int wmax0 = vr0.upper_bound ();
+ wide_int wmin1 = vr1.lower_bound ();
+ wi::sub (wmax0, wmin1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if "X" and "Y" have the same sign or zero. */
+
+bool
+same_sign_p (tree x, tree y, tree type)
+{
+ gcc_assert (INTEGRAL_TYPE_P (type));
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ value_range vr0;
+ value_range vr1;
+ if (!(get_range (vr0, x) && get_range (vr1, y)))
+ return false;
+
+ return (vr0.nonnegative_p () && vr1.nonnegative_p ())
+ || (vr0.nonpositive_p () && vr1.nonpositive_p ());
+}
diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
index 2fd58db9a2e..76c3fe15559 100644
--- a/gcc/gimple-fold.h
+++ b/gcc/gimple-fold.h
@@ -64,6 +64,10 @@ 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 mult_without_overflow_p (tree, tree, tree);
+extern bool plus_without_overflow_p (tree, tree, tree);
+extern bool minus_without_overflow_p (tree, tree, tree);
+extern bool same_sign_p (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..ca1defd6692 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -942,6 +942,60 @@ 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)
+ (if (INTEGRAL_TYPE_P (type)
+ && mult_without_overflow_p (@1, @2, type)
+ && plus_without_overflow_p (@0, @3, type)
+ && same_sign_p (@0, @4, type))
+ (plus (div @0 @2) @1)))
+
+ /* Simplify (t - M*N) / N -> t / N - M. */
+ (simplify
+ (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
+ (if (INTEGRAL_TYPE_P (type)
+ && mult_without_overflow_p (@1, @2, type)
+ && minus_without_overflow_p (@0, @3, type)
+ && same_sign_p (@0, @4, type))
+ (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 neg_c = TYPE_UNSIGNED (type) && c.sign_mask () < 0;
+ c = neg_c ? -c : c;
+ bool ok = INTEGRAL_TYPE_P (type);
+ if (ok)
+ ok = code == RSHIFT_EXPR ? wi::ctz (c) >= n.to_shwi ()
+ : wi::multiple_of_p (c, n, TYPE_SIGN (type));
+ if (ok)
+ ok = neg_c
+ ? minus_without_overflow_p (@0, wide_int_to_tree (type, c), type)
+ : plus_without_overflow_p (@0, @1, type);
+ if (ok)
+ ok = same_sign_p (@0, @3, type);
+ }
+ (if (ok)
+ (with
+ {
+ wide_int m;
+ m = op == RSHIFT_EXPR ? 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/value-query.h b/gcc/value-query.h
index d10c3eac1e2..2c4b9819d5a 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -137,6 +137,16 @@ get_range_query (const struct function *fun)
return (fun && fun->x_range_query) ? fun->x_range_query : &global_ranges;
}
+/* Return true if there is range for "X" expression at "S" statement,
+ and the range is not varying and not undefined. */
+
+inline bool
+get_range (vrange &r, tree x, gimple *s = NULL)
+{
+ return get_range_query (cfun)->range_of_expr (r, x, s) && !r.varying_p ()
+ && !r.undefined_p ();
+}
+
// Query the global range of NAME in function F. Default to cfun.
extern void gimple_range_global (vrange &v, tree name,
struct function *f = cfun);
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 707b1f15fd4..7ab9f56aec3 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -287,6 +287,18 @@ add_vrange (const vrange &v, inchash::hash &hstate,
} //namespace inchash
+bool
+irange::nonnegative_p () const
+{
+ return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
+}
+
+bool
+irange::nonpositive_p () const
+{
+ return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
+}
+
bool
irange::supports_type_p (const_tree type) const
{
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 2b4ebabe7c8..4dad4666a32 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -145,6 +145,8 @@ public:
virtual bool singleton_p (tree *result = NULL) const override;
bool singleton_p (wide_int &) const;
bool contains_p (const wide_int &) const;
+ bool nonnegative_p () const;
+ bool nonpositive_p () const;
// In-place operators.
virtual bool union_ (const vrange &) override;
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;
+}
+
--
2.39.3
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-06-28 7:16 [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
@ 2023-06-29 3:06 ` Jiufu Guo
2023-07-04 11:25 ` Richard Biener
0 siblings, 1 reply; 4+ messages in thread
From: Jiufu Guo @ 2023-06-29 3:06 UTC (permalink / raw)
To: gcc-patches
Cc: rguenther, jeffreyalaw, richard.sandiford, segher, dje.gcc,
linkw, bergner
Hi,
Jiufu Guo <guojiufu@linux.ibm.com> writes:
> 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 with the previous version:
> https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620896.html
> This version changes:
> 1. Remove the behavior to convert 'm' to '-m' for unsigned variable.
> This kind of case is rare, and it makes the code ambiguous.
> 2. Use the 'capture' expression and avoid building new expressions.
> 3. Add APIs like get_range and nonpositive/nonnegative.
> 4. Refactor patterns in match.pd and function names and signatures.
>
> While some APIs are still in gimple-fold.cc/h. Tried to add them
> to other files, but did not find a better place.
> Thanks for comments/suggestions!
Saving and propagating overflow information in range-op and value-range
maybe one idea. While I'm wondering if this is a better method from
the aspect of compiling time and memory usage.
As below attached patch, a m_ovf field is added to irange, and maintain
it in range-op/value-range-storage.
BR,
Jeff (Jiufu Guo)
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 3ab2c665901..7c287aed8b8 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -261,6 +261,7 @@ range_operator::fold_range (irange &r, tree type,
relation_trio trio) const
{
gcc_checking_assert (r.supports_type_p (type));
+ r.set_overflow (lh.with_overflow () || rh.with_overflow ());
if (empty_range_varying (r, type, lh, rh))
return true;
@@ -433,6 +434,10 @@ value_range_with_overflow (irange &r, tree type,
const unsigned int prec = TYPE_PRECISION (type);
const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
+ if (!TYPE_OVERFLOW_UNDEFINED (type)
+ && (min_ovf != wi::OVF_NONE || max_ovf != wi::OVF_NONE))
+ r.set_overflow (true);
+
// For one bit precision if max != min, then the range covers all
// values.
if (prec == 1 && wi::ne_p (wmax, wmin))
@@ -2050,10 +2055,15 @@ operator_mult::wi_fold (irange &r, tree type,
// Sort the 4 products so that min is in prod0 and max is in
// prod3.
- widest2_int prod0 = min0 * min1;
- widest2_int prod1 = min0 * max1;
- widest2_int prod2 = max0 * min1;
- widest2_int prod3 = max0 * max1;
+ wi::overflow_type ovf1, ovf2, ovf3, ovf4;
+ widest2_int prod0 = wi::mul (min0, min1, sign, &ovf1);
+ widest2_int prod1 = wi::mul (min0, max1, sign, &ovf2);
+ widest2_int prod2 = wi::mul (max0, min1, sign, &ovf3);
+ widest2_int prod3 = wi::mul (max0, max1, sign, &ovf4);
+ if (!TYPE_OVERFLOW_UNDEFINED (type)
+ && (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE || ovf3 != wi::OVF_NONE
+ || ovf3 != wi::OVF_NONE))
+ r.set_overflow (true);
// min0min1 > max0max1
if (prod0 > prod3)
diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
index 2f82739680c..a541c31bde2 100644
--- a/gcc/value-range-storage.cc
+++ b/gcc/value-range-storage.cc
@@ -277,6 +277,7 @@ void
irange_storage::set_irange (const irange &r)
{
gcc_checking_assert (fits_p (r));
+ m_ovf = r.with_overflow ();
if (r.undefined_p ())
{
@@ -325,6 +326,7 @@ read_wide_int (wide_int &w,
void
irange_storage::get_irange (irange &r, tree type) const
{
+ r.set_overflow (m_ovf);
if (m_kind == VR_UNDEFINED)
{
r.set_undefined ();
diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
index 99fb815cdc2..fc19009e566 100644
--- a/gcc/value-range-storage.h
+++ b/gcc/value-range-storage.h
@@ -90,6 +90,7 @@ private:
unsigned char m_num_ranges;
enum value_range_kind m_kind : 3;
+ bool m_ovf;
// The length of this is m_num_ranges * 2 + 1 to accomodate the nonzero bits.
HOST_WIDE_INT m_val[1];
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 4dad4666a32..468d48547e1 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -147,6 +147,8 @@ public:
bool contains_p (const wide_int &) const;
bool nonnegative_p () const;
bool nonpositive_p () const;
+ bool with_overflow () const { return m_ovf; }
+ void set_overflow (bool ovf) { m_ovf = ovf;}
// In-place operators.
virtual bool union_ (const vrange &) override;
@@ -199,6 +201,7 @@ private:
unsigned char m_max_ranges;
tree m_type;
wide_int m_nonzero_mask;
+ bool m_ovf;
protected:
wide_int *m_base;
};
@@ -842,6 +845,7 @@ irange::irange (wide_int *base, unsigned nranges, bool resizable)
{
m_base = base;
set_undefined ();
+ m_ovf = false;
}
// Constructors for int_range<>.
>
> 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 (mult_without_overflow_p): New function.
> (plus_without_overflow_p): New function.
> (minus_without_overflow_p): New function.
> (same_sign_p): New function.
> * gimple-fold.h (mult_without_overflow_p): New declare.
> (plus_without_overflow_p): New declare.
> (minus_without_overflow_p): New declare.
> (same_sign_p): New declare.
> * match.pd ((X - N * M) / N): New pattern.
> ((X + N * M) / N): New pattern.
> ((X + C) div_rshift N): New pattern.
> * value-query.h (get_range): New function.
> * value-range.cc (irange::nonnegative_p): New function.
> (irange::nonpositive_p): New function.
> * value-range.h (irange::nonnegative_p): New declare.
> (irange::nonpositive_p): New declare.
>
> 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 | 132 +++++++++++++++++
> gcc/gimple-fold.h | 4 +
> gcc/match.pd | 54 +++++++
> gcc/value-query.h | 10 ++
> gcc/value-range.cc | 12 ++
> gcc/value-range.h | 2 +
> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
> gcc/testsuite/gcc.dg/pr108757.h | 233 ++++++++++++++++++++++++++++++
> 9 files changed, 484 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..c0703b45c4b 100644
> --- a/gcc/gimple-fold.cc
> +++ b/gcc/gimple-fold.cc
> @@ -9349,3 +9349,135 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
> return false;
> }
> }
> +
> +/* Return true if "X * Y" may be overflow on integer TYPE. */
> +
> +bool
> +mult_without_overflow_p (tree x, tree y, tree type)
> +{
> + gcc_assert (INTEGRAL_TYPE_P (type));
> +
> + if (TYPE_OVERFLOW_UNDEFINED (type))
> + return true;
> +
> + value_range vr0;
> + value_range vr1;
> + if (!(get_range (vr0, x) && get_range (vr1, y)))
> + return false;
> +
> + wi::overflow_type ovf;
> + signop sgn = TYPE_SIGN (type);
> + wide_int wmax0 = vr0.upper_bound ();
> + wide_int wmax1 = vr1.upper_bound ();
> + wi::mul (wmax0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + wide_int wmin0 = vr0.lower_bound ();
> + wide_int wmin1 = vr1.lower_bound ();
> + wi::mul (wmin0, wmin1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + wi::mul (wmin0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + wi::mul (wmax0, wmin1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if "X + Y" may be overflow on integer TYPE. */
> +
> +bool
> +plus_without_overflow_p (tree x, tree y, tree type)
> +{
> + gcc_assert (INTEGRAL_TYPE_P (type));
> +
> + if (TYPE_OVERFLOW_UNDEFINED (type))
> + return true;
> +
> + value_range vr0;
> + value_range vr1;
> + if (!(get_range (vr0, x) && get_range (vr1, y)))
> + return false;
> +
> + wi::overflow_type ovf;
> + signop sgn = TYPE_SIGN (type);
> + wide_int wmax0 = vr0.upper_bound ();
> + wide_int wmax1 = vr1.upper_bound ();
> + wi::add (wmax0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + wide_int wmin0 = vr0.lower_bound ();
> + wide_int wmin1 = vr1.lower_bound ();
> + wi::add (wmin0, wmin1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if "X - Y" may be overflow on integer TYPE. */
> +
> +bool
> +minus_without_overflow_p (tree x, tree y, tree type)
> +{
> + gcc_assert (INTEGRAL_TYPE_P (type));
> +
> + if (TYPE_OVERFLOW_UNDEFINED (type))
> + return true;
> +
> + value_range vr0;
> + value_range vr1;
> + if (!(get_range (vr0, x) && get_range (vr1, y)))
> + return false;
> +
> + wi::overflow_type ovf;
> + signop sgn = TYPE_SIGN (type);
> + wide_int wmin0 = vr0.lower_bound ();
> + wide_int wmax1 = vr1.upper_bound ();
> + wi::sub (wmin0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + wide_int wmax0 = vr0.upper_bound ();
> + wide_int wmin1 = vr1.lower_bound ();
> + wi::sub (wmax0, wmin1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if "X" and "Y" have the same sign or zero. */
> +
> +bool
> +same_sign_p (tree x, tree y, tree type)
> +{
> + gcc_assert (INTEGRAL_TYPE_P (type));
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + value_range vr0;
> + value_range vr1;
> + if (!(get_range (vr0, x) && get_range (vr1, y)))
> + return false;
> +
> + return (vr0.nonnegative_p () && vr1.nonnegative_p ())
> + || (vr0.nonpositive_p () && vr1.nonpositive_p ());
> +}
> diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
> index 2fd58db9a2e..76c3fe15559 100644
> --- a/gcc/gimple-fold.h
> +++ b/gcc/gimple-fold.h
> @@ -64,6 +64,10 @@ 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 mult_without_overflow_p (tree, tree, tree);
> +extern bool plus_without_overflow_p (tree, tree, tree);
> +extern bool minus_without_overflow_p (tree, tree, tree);
> +extern bool same_sign_p (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..ca1defd6692 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -942,6 +942,60 @@ 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)
> + (if (INTEGRAL_TYPE_P (type)
> + && mult_without_overflow_p (@1, @2, type)
> + && plus_without_overflow_p (@0, @3, type)
> + && same_sign_p (@0, @4, type))
> + (plus (div @0 @2) @1)))
> +
> + /* Simplify (t - M*N) / N -> t / N - M. */
> + (simplify
> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
> + (if (INTEGRAL_TYPE_P (type)
> + && mult_without_overflow_p (@1, @2, type)
> + && minus_without_overflow_p (@0, @3, type)
> + && same_sign_p (@0, @4, type))
> + (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 neg_c = TYPE_UNSIGNED (type) && c.sign_mask () < 0;
> + c = neg_c ? -c : c;
> + bool ok = INTEGRAL_TYPE_P (type);
> + if (ok)
> + ok = code == RSHIFT_EXPR ? wi::ctz (c) >= n.to_shwi ()
> + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
> + if (ok)
> + ok = neg_c
> + ? minus_without_overflow_p (@0, wide_int_to_tree (type, c), type)
> + : plus_without_overflow_p (@0, @1, type);
> + if (ok)
> + ok = same_sign_p (@0, @3, type);
> + }
> + (if (ok)
> + (with
> + {
> + wide_int m;
> + m = op == RSHIFT_EXPR ? 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/value-query.h b/gcc/value-query.h
> index d10c3eac1e2..2c4b9819d5a 100644
> --- a/gcc/value-query.h
> +++ b/gcc/value-query.h
> @@ -137,6 +137,16 @@ get_range_query (const struct function *fun)
> return (fun && fun->x_range_query) ? fun->x_range_query : &global_ranges;
> }
>
> +/* Return true if there is range for "X" expression at "S" statement,
> + and the range is not varying and not undefined. */
> +
> +inline bool
> +get_range (vrange &r, tree x, gimple *s = NULL)
> +{
> + return get_range_query (cfun)->range_of_expr (r, x, s) && !r.varying_p ()
> + && !r.undefined_p ();
> +}
> +
> // Query the global range of NAME in function F. Default to cfun.
> extern void gimple_range_global (vrange &v, tree name,
> struct function *f = cfun);
> diff --git a/gcc/value-range.cc b/gcc/value-range.cc
> index 707b1f15fd4..7ab9f56aec3 100644
> --- a/gcc/value-range.cc
> +++ b/gcc/value-range.cc
> @@ -287,6 +287,18 @@ add_vrange (const vrange &v, inchash::hash &hstate,
>
> } //namespace inchash
>
> +bool
> +irange::nonnegative_p () const
> +{
> + return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
> +}
> +
> +bool
> +irange::nonpositive_p () const
> +{
> + return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
> +}
> +
> bool
> irange::supports_type_p (const_tree type) const
> {
> diff --git a/gcc/value-range.h b/gcc/value-range.h
> index 2b4ebabe7c8..4dad4666a32 100644
> --- a/gcc/value-range.h
> +++ b/gcc/value-range.h
> @@ -145,6 +145,8 @@ public:
> virtual bool singleton_p (tree *result = NULL) const override;
> bool singleton_p (wide_int &) const;
> bool contains_p (const wide_int &) const;
> + bool nonnegative_p () const;
> + bool nonpositive_p () const;
>
> // In-place operators.
> virtual bool union_ (const vrange &) override;
> 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;
> +}
> +
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-06-29 3:06 ` Jiufu Guo
@ 2023-07-04 11:25 ` Richard Biener
2023-07-05 5:51 ` Jiufu Guo
0 siblings, 1 reply; 4+ messages in thread
From: Richard Biener @ 2023-07-04 11:25 UTC (permalink / raw)
To: Jiufu Guo
Cc: gcc-patches, jeffreyalaw, richard.sandiford, segher, dje.gcc,
linkw, bergner, amacleod
On Thu, 29 Jun 2023, Jiufu Guo wrote:
>
> Hi,
>
> Jiufu Guo <guojiufu@linux.ibm.com> writes:
>
> > 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 with the previous version:
> > https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620896.html
> > This version changes:
> > 1. Remove the behavior to convert 'm' to '-m' for unsigned variable.
> > This kind of case is rare, and it makes the code ambiguous.
> > 2. Use the 'capture' expression and avoid building new expressions.
> > 3. Add APIs like get_range and nonpositive/nonnegative.
> > 4. Refactor patterns in match.pd and function names and signatures.
> >
> > While some APIs are still in gimple-fold.cc/h. Tried to add them
> > to other files, but did not find a better place.
> > Thanks for comments/suggestions!
>
> Saving and propagating overflow information in range-op and value-range
> maybe one idea. While I'm wondering if this is a better method from
> the aspect of compiling time and memory usage.
> As below attached patch, a m_ovf field is added to irange, and maintain
> it in range-op/value-range-storage.
I don't think we want to store that. But still we should have a
way to compute whether the operation in a stmt could overflow, but
this should be (or already does) exist within the ranger API.
So do not add mult_without_overflow_p and friends to gimple-fold.{cc,h}
but instead leverage what's available in ranger (or add to it there).
IIRC simplify_using_ranges for example used to perform narrowing
based on knowledge if the resulting op would overflow or not.
CCing Andrew again here.
Richard.
> BR,
> Jeff (Jiufu Guo)
>
> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
> index 3ab2c665901..7c287aed8b8 100644
> --- a/gcc/range-op.cc
> +++ b/gcc/range-op.cc
> @@ -261,6 +261,7 @@ range_operator::fold_range (irange &r, tree type,
> relation_trio trio) const
> {
> gcc_checking_assert (r.supports_type_p (type));
> + r.set_overflow (lh.with_overflow () || rh.with_overflow ());
> if (empty_range_varying (r, type, lh, rh))
> return true;
>
> @@ -433,6 +434,10 @@ value_range_with_overflow (irange &r, tree type,
> const unsigned int prec = TYPE_PRECISION (type);
> const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
>
> + if (!TYPE_OVERFLOW_UNDEFINED (type)
> + && (min_ovf != wi::OVF_NONE || max_ovf != wi::OVF_NONE))
> + r.set_overflow (true);
> +
> // For one bit precision if max != min, then the range covers all
> // values.
> if (prec == 1 && wi::ne_p (wmax, wmin))
> @@ -2050,10 +2055,15 @@ operator_mult::wi_fold (irange &r, tree type,
>
> // Sort the 4 products so that min is in prod0 and max is in
> // prod3.
> - widest2_int prod0 = min0 * min1;
> - widest2_int prod1 = min0 * max1;
> - widest2_int prod2 = max0 * min1;
> - widest2_int prod3 = max0 * max1;
> + wi::overflow_type ovf1, ovf2, ovf3, ovf4;
> + widest2_int prod0 = wi::mul (min0, min1, sign, &ovf1);
> + widest2_int prod1 = wi::mul (min0, max1, sign, &ovf2);
> + widest2_int prod2 = wi::mul (max0, min1, sign, &ovf3);
> + widest2_int prod3 = wi::mul (max0, max1, sign, &ovf4);
> + if (!TYPE_OVERFLOW_UNDEFINED (type)
> + && (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE || ovf3 != wi::OVF_NONE
> + || ovf3 != wi::OVF_NONE))
> + r.set_overflow (true);
>
> // min0min1 > max0max1
> if (prod0 > prod3)
> diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
> index 2f82739680c..a541c31bde2 100644
> --- a/gcc/value-range-storage.cc
> +++ b/gcc/value-range-storage.cc
> @@ -277,6 +277,7 @@ void
> irange_storage::set_irange (const irange &r)
> {
> gcc_checking_assert (fits_p (r));
> + m_ovf = r.with_overflow ();
>
> if (r.undefined_p ())
> {
> @@ -325,6 +326,7 @@ read_wide_int (wide_int &w,
> void
> irange_storage::get_irange (irange &r, tree type) const
> {
> + r.set_overflow (m_ovf);
> if (m_kind == VR_UNDEFINED)
> {
> r.set_undefined ();
> diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
> index 99fb815cdc2..fc19009e566 100644
> --- a/gcc/value-range-storage.h
> +++ b/gcc/value-range-storage.h
> @@ -90,6 +90,7 @@ private:
> unsigned char m_num_ranges;
>
> enum value_range_kind m_kind : 3;
> + bool m_ovf;
>
> // The length of this is m_num_ranges * 2 + 1 to accomodate the nonzero bits.
> HOST_WIDE_INT m_val[1];
> diff --git a/gcc/value-range.h b/gcc/value-range.h
> index 4dad4666a32..468d48547e1 100644
> --- a/gcc/value-range.h
> +++ b/gcc/value-range.h
> @@ -147,6 +147,8 @@ public:
> bool contains_p (const wide_int &) const;
> bool nonnegative_p () const;
> bool nonpositive_p () const;
> + bool with_overflow () const { return m_ovf; }
> + void set_overflow (bool ovf) { m_ovf = ovf;}
>
> // In-place operators.
> virtual bool union_ (const vrange &) override;
> @@ -199,6 +201,7 @@ private:
> unsigned char m_max_ranges;
> tree m_type;
> wide_int m_nonzero_mask;
> + bool m_ovf;
> protected:
> wide_int *m_base;
> };
> @@ -842,6 +845,7 @@ irange::irange (wide_int *base, unsigned nranges, bool resizable)
> {
> m_base = base;
> set_undefined ();
> + m_ovf = false;
> }
>
> // Constructors for int_range<>.
> >
> > 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 (mult_without_overflow_p): New function.
> > (plus_without_overflow_p): New function.
> > (minus_without_overflow_p): New function.
> > (same_sign_p): New function.
> > * gimple-fold.h (mult_without_overflow_p): New declare.
> > (plus_without_overflow_p): New declare.
> > (minus_without_overflow_p): New declare.
> > (same_sign_p): New declare.
> > * match.pd ((X - N * M) / N): New pattern.
> > ((X + N * M) / N): New pattern.
> > ((X + C) div_rshift N): New pattern.
> > * value-query.h (get_range): New function.
> > * value-range.cc (irange::nonnegative_p): New function.
> > (irange::nonpositive_p): New function.
> > * value-range.h (irange::nonnegative_p): New declare.
> > (irange::nonpositive_p): New declare.
> >
> > 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 | 132 +++++++++++++++++
> > gcc/gimple-fold.h | 4 +
> > gcc/match.pd | 54 +++++++
> > gcc/value-query.h | 10 ++
> > gcc/value-range.cc | 12 ++
> > gcc/value-range.h | 2 +
> > gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
> > gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
> > gcc/testsuite/gcc.dg/pr108757.h | 233 ++++++++++++++++++++++++++++++
> > 9 files changed, 484 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..c0703b45c4b 100644
> > --- a/gcc/gimple-fold.cc
> > +++ b/gcc/gimple-fold.cc
> > @@ -9349,3 +9349,135 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
> > return false;
> > }
> > }
> > +
> > +/* Return true if "X * Y" may be overflow on integer TYPE. */
> > +
> > +bool
> > +mult_without_overflow_p (tree x, tree y, tree type)
> > +{
> > + gcc_assert (INTEGRAL_TYPE_P (type));
> > +
> > + if (TYPE_OVERFLOW_UNDEFINED (type))
> > + return true;
> > +
> > + value_range vr0;
> > + value_range vr1;
> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
> > + return false;
> > +
> > + wi::overflow_type ovf;
> > + signop sgn = TYPE_SIGN (type);
> > + wide_int wmax0 = vr0.upper_bound ();
> > + wide_int wmax1 = vr1.upper_bound ();
> > + wi::mul (wmax0, wmax1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + if (TYPE_UNSIGNED (type))
> > + return true;
> > +
> > + wide_int wmin0 = vr0.lower_bound ();
> > + wide_int wmin1 = vr1.lower_bound ();
> > + wi::mul (wmin0, wmin1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + wi::mul (wmin0, wmax1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + wi::mul (wmax0, wmin1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + return true;
> > +}
> > +
> > +/* Return true if "X + Y" may be overflow on integer TYPE. */
> > +
> > +bool
> > +plus_without_overflow_p (tree x, tree y, tree type)
> > +{
> > + gcc_assert (INTEGRAL_TYPE_P (type));
> > +
> > + if (TYPE_OVERFLOW_UNDEFINED (type))
> > + return true;
> > +
> > + value_range vr0;
> > + value_range vr1;
> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
> > + return false;
> > +
> > + wi::overflow_type ovf;
> > + signop sgn = TYPE_SIGN (type);
> > + wide_int wmax0 = vr0.upper_bound ();
> > + wide_int wmax1 = vr1.upper_bound ();
> > + wi::add (wmax0, wmax1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + if (TYPE_UNSIGNED (type))
> > + return true;
> > +
> > + wide_int wmin0 = vr0.lower_bound ();
> > + wide_int wmin1 = vr1.lower_bound ();
> > + wi::add (wmin0, wmin1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + return true;
> > +}
> > +
> > +/* Return true if "X - Y" may be overflow on integer TYPE. */
> > +
> > +bool
> > +minus_without_overflow_p (tree x, tree y, tree type)
> > +{
> > + gcc_assert (INTEGRAL_TYPE_P (type));
> > +
> > + if (TYPE_OVERFLOW_UNDEFINED (type))
> > + return true;
> > +
> > + value_range vr0;
> > + value_range vr1;
> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
> > + return false;
> > +
> > + wi::overflow_type ovf;
> > + signop sgn = TYPE_SIGN (type);
> > + wide_int wmin0 = vr0.lower_bound ();
> > + wide_int wmax1 = vr1.upper_bound ();
> > + wi::sub (wmin0, wmax1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + if (TYPE_UNSIGNED (type))
> > + return true;
> > +
> > + wide_int wmax0 = vr0.upper_bound ();
> > + wide_int wmin1 = vr1.lower_bound ();
> > + wi::sub (wmax0, wmin1, sgn, &ovf);
> > + if (ovf != wi::OVF_NONE)
> > + return false;
> > +
> > + return true;
> > +}
> > +
> > +/* Return true if "X" and "Y" have the same sign or zero. */
> > +
> > +bool
> > +same_sign_p (tree x, tree y, tree type)
> > +{
> > + gcc_assert (INTEGRAL_TYPE_P (type));
> > +
> > + if (TYPE_UNSIGNED (type))
> > + return true;
> > +
> > + value_range vr0;
> > + value_range vr1;
> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
> > + return false;
> > +
> > + return (vr0.nonnegative_p () && vr1.nonnegative_p ())
> > + || (vr0.nonpositive_p () && vr1.nonpositive_p ());
> > +}
> > diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
> > index 2fd58db9a2e..76c3fe15559 100644
> > --- a/gcc/gimple-fold.h
> > +++ b/gcc/gimple-fold.h
> > @@ -64,6 +64,10 @@ 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 mult_without_overflow_p (tree, tree, tree);
> > +extern bool plus_without_overflow_p (tree, tree, tree);
> > +extern bool minus_without_overflow_p (tree, tree, tree);
> > +extern bool same_sign_p (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..ca1defd6692 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -942,6 +942,60 @@ 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)
> > + (if (INTEGRAL_TYPE_P (type)
> > + && mult_without_overflow_p (@1, @2, type)
> > + && plus_without_overflow_p (@0, @3, type)
> > + && same_sign_p (@0, @4, type))
> > + (plus (div @0 @2) @1)))
> > +
> > + /* Simplify (t - M*N) / N -> t / N - M. */
> > + (simplify
> > + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
> > + (if (INTEGRAL_TYPE_P (type)
> > + && mult_without_overflow_p (@1, @2, type)
> > + && minus_without_overflow_p (@0, @3, type)
> > + && same_sign_p (@0, @4, type))
> > + (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 neg_c = TYPE_UNSIGNED (type) && c.sign_mask () < 0;
> > + c = neg_c ? -c : c;
> > + bool ok = INTEGRAL_TYPE_P (type);
> > + if (ok)
> > + ok = code == RSHIFT_EXPR ? wi::ctz (c) >= n.to_shwi ()
> > + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
> > + if (ok)
> > + ok = neg_c
> > + ? minus_without_overflow_p (@0, wide_int_to_tree (type, c), type)
> > + : plus_without_overflow_p (@0, @1, type);
> > + if (ok)
> > + ok = same_sign_p (@0, @3, type);
> > + }
> > + (if (ok)
> > + (with
> > + {
> > + wide_int m;
> > + m = op == RSHIFT_EXPR ? 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/value-query.h b/gcc/value-query.h
> > index d10c3eac1e2..2c4b9819d5a 100644
> > --- a/gcc/value-query.h
> > +++ b/gcc/value-query.h
> > @@ -137,6 +137,16 @@ get_range_query (const struct function *fun)
> > return (fun && fun->x_range_query) ? fun->x_range_query : &global_ranges;
> > }
> >
> > +/* Return true if there is range for "X" expression at "S" statement,
> > + and the range is not varying and not undefined. */
> > +
> > +inline bool
> > +get_range (vrange &r, tree x, gimple *s = NULL)
> > +{
> > + return get_range_query (cfun)->range_of_expr (r, x, s) && !r.varying_p ()
> > + && !r.undefined_p ();
> > +}
> > +
> > // Query the global range of NAME in function F. Default to cfun.
> > extern void gimple_range_global (vrange &v, tree name,
> > struct function *f = cfun);
> > diff --git a/gcc/value-range.cc b/gcc/value-range.cc
> > index 707b1f15fd4..7ab9f56aec3 100644
> > --- a/gcc/value-range.cc
> > +++ b/gcc/value-range.cc
> > @@ -287,6 +287,18 @@ add_vrange (const vrange &v, inchash::hash &hstate,
> >
> > } //namespace inchash
> >
> > +bool
> > +irange::nonnegative_p () const
> > +{
> > + return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
> > +}
> > +
> > +bool
> > +irange::nonpositive_p () const
> > +{
> > + return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
> > +}
> > +
> > bool
> > irange::supports_type_p (const_tree type) const
> > {
> > diff --git a/gcc/value-range.h b/gcc/value-range.h
> > index 2b4ebabe7c8..4dad4666a32 100644
> > --- a/gcc/value-range.h
> > +++ b/gcc/value-range.h
> > @@ -145,6 +145,8 @@ public:
> > virtual bool singleton_p (tree *result = NULL) const override;
> > bool singleton_p (wide_int &) const;
> > bool contains_p (const wide_int &) const;
> > + bool nonnegative_p () const;
> > + bool nonpositive_p () const;
> >
> > // In-place operators.
> > virtual bool union_ (const vrange &) override;
> > 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;
> > +}
> > +
>
--
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-07-04 11:25 ` Richard Biener
@ 2023-07-05 5:51 ` Jiufu Guo
0 siblings, 0 replies; 4+ messages in thread
From: Jiufu Guo @ 2023-07-05 5:51 UTC (permalink / raw)
To: Richard Biener
Cc: gcc-patches, jeffreyalaw, richard.sandiford, segher, dje.gcc,
linkw, bergner, amacleod
Hi Richard/Andrew!
Richard Biener <rguenther@suse.de> writes:
> On Thu, 29 Jun 2023, Jiufu Guo wrote:
>
>>
>> Hi,
>>
>> Jiufu Guo <guojiufu@linux.ibm.com> writes:
>>
>> > 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 with the previous version:
>> > https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620896.html
>> > This version changes:
>> > 1. Remove the behavior to convert 'm' to '-m' for unsigned variable.
>> > This kind of case is rare, and it makes the code ambiguous.
>> > 2. Use the 'capture' expression and avoid building new expressions.
>> > 3. Add APIs like get_range and nonpositive/nonnegative.
>> > 4. Refactor patterns in match.pd and function names and signatures.
>> >
>> > While some APIs are still in gimple-fold.cc/h. Tried to add them
>> > to other files, but did not find a better place.
>> > Thanks for comments/suggestions!
>>
>> Saving and propagating overflow information in range-op and value-range
>> maybe one idea. While I'm wondering if this is a better method from
>> the aspect of compiling time and memory usage.
>> As below attached patch, a m_ovf field is added to irange, and maintain
>> it in range-op/value-range-storage.
>
> I don't think we want to store that. But still we should have a
> way to compute whether the operation in a stmt could overflow, but
> this should be (or already does) exist within the ranger API.
>
> So do not add mult_without_overflow_p and friends to gimple-fold.{cc,h}
> but instead leverage what's available in ranger (or add to it there).
>
> IIRC simplify_using_ranges for example used to perform narrowing
> based on knowledge if the resulting op would overflow or not.
>
> CCing Andrew again here.
I'm also trying to find a good place to define these APIs, but did not
find a perfect place.
If any suggestions, please point them out!!!
Thanks in advance.
*. For the trunk code, there are a few codes that care about overflow info:
- simplify_using_ranges is using arith_overflowed_p to check overflow info
on CST value.
- arith_overflowed_p is defined in fold-const/gimple-fold. It checks overflow
info via wi::add/sub/mult
-- fold_builtin_arith_overflow/fold_binary_loc also care about CST.
-- TREE_OVERFLOW(cst)/TREE_OVERFLOW_P, it is also about CONSTANT_CLASS
CST_CHECK (NODE)->base.public_flag.
- rewrite_to_defined_overflow and match_arith_overflow is transforming
signed integer operation to unsigned arithmetic.
- rang-op is also using wi::add/sub/mult/neg to check overflow info
This is why I was trying to use the overflow info directly.
If maintain the overflow info in value-range, we may need to pay the cost
on rang-op/ssa_cache/range-value-store. I'm also wondering if we want to
do this.
- match.pd, a few patterns in this file are checking overflow info via
value-range and wi::add/sub/mult. This is mostly what we need.
The most current match.pd is inlining value-range and overflow info
checking inside patterns.
I'm wondering if we may want to extract common code from patterns into
gimple-fold.cc/h (or xx-match-head.cc).
BR,
Jeff (Jiufu Guo)
>
> Richard.
>
>
>> BR,
>> Jeff (Jiufu Guo)
>>
>> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
>> index 3ab2c665901..7c287aed8b8 100644
>> --- a/gcc/range-op.cc
>> +++ b/gcc/range-op.cc
>> @@ -261,6 +261,7 @@ range_operator::fold_range (irange &r, tree type,
>> relation_trio trio) const
>> {
>> gcc_checking_assert (r.supports_type_p (type));
>> + r.set_overflow (lh.with_overflow () || rh.with_overflow ());
>> if (empty_range_varying (r, type, lh, rh))
>> return true;
>>
>> @@ -433,6 +434,10 @@ value_range_with_overflow (irange &r, tree type,
>> const unsigned int prec = TYPE_PRECISION (type);
>> const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
>>
>> + if (!TYPE_OVERFLOW_UNDEFINED (type)
>> + && (min_ovf != wi::OVF_NONE || max_ovf != wi::OVF_NONE))
>> + r.set_overflow (true);
>> +
>> // For one bit precision if max != min, then the range covers all
>> // values.
>> if (prec == 1 && wi::ne_p (wmax, wmin))
>> @@ -2050,10 +2055,15 @@ operator_mult::wi_fold (irange &r, tree type,
>>
>> // Sort the 4 products so that min is in prod0 and max is in
>> // prod3.
>> - widest2_int prod0 = min0 * min1;
>> - widest2_int prod1 = min0 * max1;
>> - widest2_int prod2 = max0 * min1;
>> - widest2_int prod3 = max0 * max1;
>> + wi::overflow_type ovf1, ovf2, ovf3, ovf4;
>> + widest2_int prod0 = wi::mul (min0, min1, sign, &ovf1);
>> + widest2_int prod1 = wi::mul (min0, max1, sign, &ovf2);
>> + widest2_int prod2 = wi::mul (max0, min1, sign, &ovf3);
>> + widest2_int prod3 = wi::mul (max0, max1, sign, &ovf4);
>> + if (!TYPE_OVERFLOW_UNDEFINED (type)
>> + && (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE || ovf3 != wi::OVF_NONE
>> + || ovf3 != wi::OVF_NONE))
>> + r.set_overflow (true);
>>
>> // min0min1 > max0max1
>> if (prod0 > prod3)
>> diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
>> index 2f82739680c..a541c31bde2 100644
>> --- a/gcc/value-range-storage.cc
>> +++ b/gcc/value-range-storage.cc
>> @@ -277,6 +277,7 @@ void
>> irange_storage::set_irange (const irange &r)
>> {
>> gcc_checking_assert (fits_p (r));
>> + m_ovf = r.with_overflow ();
>>
>> if (r.undefined_p ())
>> {
>> @@ -325,6 +326,7 @@ read_wide_int (wide_int &w,
>> void
>> irange_storage::get_irange (irange &r, tree type) const
>> {
>> + r.set_overflow (m_ovf);
>> if (m_kind == VR_UNDEFINED)
>> {
>> r.set_undefined ();
>> diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
>> index 99fb815cdc2..fc19009e566 100644
>> --- a/gcc/value-range-storage.h
>> +++ b/gcc/value-range-storage.h
>> @@ -90,6 +90,7 @@ private:
>> unsigned char m_num_ranges;
>>
>> enum value_range_kind m_kind : 3;
>> + bool m_ovf;
>>
>> // The length of this is m_num_ranges * 2 + 1 to accomodate the nonzero bits.
>> HOST_WIDE_INT m_val[1];
>> diff --git a/gcc/value-range.h b/gcc/value-range.h
>> index 4dad4666a32..468d48547e1 100644
>> --- a/gcc/value-range.h
>> +++ b/gcc/value-range.h
>> @@ -147,6 +147,8 @@ public:
>> bool contains_p (const wide_int &) const;
>> bool nonnegative_p () const;
>> bool nonpositive_p () const;
>> + bool with_overflow () const { return m_ovf; }
>> + void set_overflow (bool ovf) { m_ovf = ovf;}
>>
>> // In-place operators.
>> virtual bool union_ (const vrange &) override;
>> @@ -199,6 +201,7 @@ private:
>> unsigned char m_max_ranges;
>> tree m_type;
>> wide_int m_nonzero_mask;
>> + bool m_ovf;
>> protected:
>> wide_int *m_base;
>> };
>> @@ -842,6 +845,7 @@ irange::irange (wide_int *base, unsigned nranges, bool resizable)
>> {
>> m_base = base;
>> set_undefined ();
>> + m_ovf = false;
>> }
>>
>> // Constructors for int_range<>.
>> >
>> > 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 (mult_without_overflow_p): New function.
>> > (plus_without_overflow_p): New function.
>> > (minus_without_overflow_p): New function.
>> > (same_sign_p): New function.
>> > * gimple-fold.h (mult_without_overflow_p): New declare.
>> > (plus_without_overflow_p): New declare.
>> > (minus_without_overflow_p): New declare.
>> > (same_sign_p): New declare.
>> > * match.pd ((X - N * M) / N): New pattern.
>> > ((X + N * M) / N): New pattern.
>> > ((X + C) div_rshift N): New pattern.
>> > * value-query.h (get_range): New function.
>> > * value-range.cc (irange::nonnegative_p): New function.
>> > (irange::nonpositive_p): New function.
>> > * value-range.h (irange::nonnegative_p): New declare.
>> > (irange::nonpositive_p): New declare.
>> >
>> > 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 | 132 +++++++++++++++++
>> > gcc/gimple-fold.h | 4 +
>> > gcc/match.pd | 54 +++++++
>> > gcc/value-query.h | 10 ++
>> > gcc/value-range.cc | 12 ++
>> > gcc/value-range.h | 2 +
>> > gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
>> > gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
>> > gcc/testsuite/gcc.dg/pr108757.h | 233 ++++++++++++++++++++++++++++++
>> > 9 files changed, 484 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..c0703b45c4b 100644
>> > --- a/gcc/gimple-fold.cc
>> > +++ b/gcc/gimple-fold.cc
>> > @@ -9349,3 +9349,135 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
>> > return false;
>> > }
>> > }
>> > +
>> > +/* Return true if "X * Y" may be overflow on integer TYPE. */
>> > +
>> > +bool
>> > +mult_without_overflow_p (tree x, tree y, tree type)
>> > +{
>> > + gcc_assert (INTEGRAL_TYPE_P (type));
>> > +
>> > + if (TYPE_OVERFLOW_UNDEFINED (type))
>> > + return true;
>> > +
>> > + value_range vr0;
>> > + value_range vr1;
>> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
>> > + return false;
>> > +
>> > + wi::overflow_type ovf;
>> > + signop sgn = TYPE_SIGN (type);
>> > + wide_int wmax0 = vr0.upper_bound ();
>> > + wide_int wmax1 = vr1.upper_bound ();
>> > + wi::mul (wmax0, wmax1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + if (TYPE_UNSIGNED (type))
>> > + return true;
>> > +
>> > + wide_int wmin0 = vr0.lower_bound ();
>> > + wide_int wmin1 = vr1.lower_bound ();
>> > + wi::mul (wmin0, wmin1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + wi::mul (wmin0, wmax1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + wi::mul (wmax0, wmin1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + return true;
>> > +}
>> > +
>> > +/* Return true if "X + Y" may be overflow on integer TYPE. */
>> > +
>> > +bool
>> > +plus_without_overflow_p (tree x, tree y, tree type)
>> > +{
>> > + gcc_assert (INTEGRAL_TYPE_P (type));
>> > +
>> > + if (TYPE_OVERFLOW_UNDEFINED (type))
>> > + return true;
>> > +
>> > + value_range vr0;
>> > + value_range vr1;
>> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
>> > + return false;
>> > +
>> > + wi::overflow_type ovf;
>> > + signop sgn = TYPE_SIGN (type);
>> > + wide_int wmax0 = vr0.upper_bound ();
>> > + wide_int wmax1 = vr1.upper_bound ();
>> > + wi::add (wmax0, wmax1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + if (TYPE_UNSIGNED (type))
>> > + return true;
>> > +
>> > + wide_int wmin0 = vr0.lower_bound ();
>> > + wide_int wmin1 = vr1.lower_bound ();
>> > + wi::add (wmin0, wmin1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + return true;
>> > +}
>> > +
>> > +/* Return true if "X - Y" may be overflow on integer TYPE. */
>> > +
>> > +bool
>> > +minus_without_overflow_p (tree x, tree y, tree type)
>> > +{
>> > + gcc_assert (INTEGRAL_TYPE_P (type));
>> > +
>> > + if (TYPE_OVERFLOW_UNDEFINED (type))
>> > + return true;
>> > +
>> > + value_range vr0;
>> > + value_range vr1;
>> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
>> > + return false;
>> > +
>> > + wi::overflow_type ovf;
>> > + signop sgn = TYPE_SIGN (type);
>> > + wide_int wmin0 = vr0.lower_bound ();
>> > + wide_int wmax1 = vr1.upper_bound ();
>> > + wi::sub (wmin0, wmax1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + if (TYPE_UNSIGNED (type))
>> > + return true;
>> > +
>> > + wide_int wmax0 = vr0.upper_bound ();
>> > + wide_int wmin1 = vr1.lower_bound ();
>> > + wi::sub (wmax0, wmin1, sgn, &ovf);
>> > + if (ovf != wi::OVF_NONE)
>> > + return false;
>> > +
>> > + return true;
>> > +}
>> > +
>> > +/* Return true if "X" and "Y" have the same sign or zero. */
>> > +
>> > +bool
>> > +same_sign_p (tree x, tree y, tree type)
>> > +{
>> > + gcc_assert (INTEGRAL_TYPE_P (type));
>> > +
>> > + if (TYPE_UNSIGNED (type))
>> > + return true;
>> > +
>> > + value_range vr0;
>> > + value_range vr1;
>> > + if (!(get_range (vr0, x) && get_range (vr1, y)))
>> > + return false;
>> > +
>> > + return (vr0.nonnegative_p () && vr1.nonnegative_p ())
>> > + || (vr0.nonpositive_p () && vr1.nonpositive_p ());
>> > +}
>> > diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
>> > index 2fd58db9a2e..76c3fe15559 100644
>> > --- a/gcc/gimple-fold.h
>> > +++ b/gcc/gimple-fold.h
>> > @@ -64,6 +64,10 @@ 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 mult_without_overflow_p (tree, tree, tree);
>> > +extern bool plus_without_overflow_p (tree, tree, tree);
>> > +extern bool minus_without_overflow_p (tree, tree, tree);
>> > +extern bool same_sign_p (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..ca1defd6692 100644
>> > --- a/gcc/match.pd
>> > +++ b/gcc/match.pd
>> > @@ -942,6 +942,60 @@ 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)
>> > + (if (INTEGRAL_TYPE_P (type)
>> > + && mult_without_overflow_p (@1, @2, type)
>> > + && plus_without_overflow_p (@0, @3, type)
>> > + && same_sign_p (@0, @4, type))
>> > + (plus (div @0 @2) @1)))
>> > +
>> > + /* Simplify (t - M*N) / N -> t / N - M. */
>> > + (simplify
>> > + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
>> > + (if (INTEGRAL_TYPE_P (type)
>> > + && mult_without_overflow_p (@1, @2, type)
>> > + && minus_without_overflow_p (@0, @3, type)
>> > + && same_sign_p (@0, @4, type))
>> > + (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 neg_c = TYPE_UNSIGNED (type) && c.sign_mask () < 0;
>> > + c = neg_c ? -c : c;
>> > + bool ok = INTEGRAL_TYPE_P (type);
>> > + if (ok)
>> > + ok = code == RSHIFT_EXPR ? wi::ctz (c) >= n.to_shwi ()
>> > + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
>> > + if (ok)
>> > + ok = neg_c
>> > + ? minus_without_overflow_p (@0, wide_int_to_tree (type, c), type)
>> > + : plus_without_overflow_p (@0, @1, type);
>> > + if (ok)
>> > + ok = same_sign_p (@0, @3, type);
>> > + }
>> > + (if (ok)
>> > + (with
>> > + {
>> > + wide_int m;
>> > + m = op == RSHIFT_EXPR ? 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/value-query.h b/gcc/value-query.h
>> > index d10c3eac1e2..2c4b9819d5a 100644
>> > --- a/gcc/value-query.h
>> > +++ b/gcc/value-query.h
>> > @@ -137,6 +137,16 @@ get_range_query (const struct function *fun)
>> > return (fun && fun->x_range_query) ? fun->x_range_query : &global_ranges;
>> > }
>> >
>> > +/* Return true if there is range for "X" expression at "S" statement,
>> > + and the range is not varying and not undefined. */
>> > +
>> > +inline bool
>> > +get_range (vrange &r, tree x, gimple *s = NULL)
>> > +{
>> > + return get_range_query (cfun)->range_of_expr (r, x, s) && !r.varying_p ()
>> > + && !r.undefined_p ();
>> > +}
>> > +
>> > // Query the global range of NAME in function F. Default to cfun.
>> > extern void gimple_range_global (vrange &v, tree name,
>> > struct function *f = cfun);
>> > diff --git a/gcc/value-range.cc b/gcc/value-range.cc
>> > index 707b1f15fd4..7ab9f56aec3 100644
>> > --- a/gcc/value-range.cc
>> > +++ b/gcc/value-range.cc
>> > @@ -287,6 +287,18 @@ add_vrange (const vrange &v, inchash::hash &hstate,
>> >
>> > } //namespace inchash
>> >
>> > +bool
>> > +irange::nonnegative_p () const
>> > +{
>> > + return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
>> > +}
>> > +
>> > +bool
>> > +irange::nonpositive_p () const
>> > +{
>> > + return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
>> > +}
>> > +
>> > bool
>> > irange::supports_type_p (const_tree type) const
>> > {
>> > diff --git a/gcc/value-range.h b/gcc/value-range.h
>> > index 2b4ebabe7c8..4dad4666a32 100644
>> > --- a/gcc/value-range.h
>> > +++ b/gcc/value-range.h
>> > @@ -145,6 +145,8 @@ public:
>> > virtual bool singleton_p (tree *result = NULL) const override;
>> > bool singleton_p (wide_int &) const;
>> > bool contains_p (const wide_int &) const;
>> > + bool nonnegative_p () const;
>> > + bool nonpositive_p () const;
>> >
>> > // In-place operators.
>> > virtual bool union_ (const vrange &) override;
>> > 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;
>> > +}
>> > +
>>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2023-07-05 5:52 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-06-28 7:16 [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
2023-06-29 3:06 ` Jiufu Guo
2023-07-04 11:25 ` Richard Biener
2023-07-05 5:51 ` Jiufu Guo
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).