[V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid

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

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;
> +}
> +

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;
> > +}
> > +
>

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;
>> > +}
>> > +
>>