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

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

[Jiufu Guo]

Hi,

This patch tries to optimize "(X - N * M) / N" to "X / N - M".
For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
wrap/overflow/underflow. So, it is valid that "X - N * M" does
not cross zero and does not wrap/overflow/underflow.

Compare with previous version:
https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html

This patch 1. adds the patterns for variable N or M,
2. uses simpler form "(X - N * M) / N" for patterns,
3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
4. updates testcases

Bootstrap & regtest pass on ppc64{,le} and x86_64.
Is this patch ok for trunk?


BR,
Jeff (Jiufu Guo)

	PR tree-optimization/108757

gcc/ChangeLog:

	* gimple-fold.cc (maybe_mult_overflow): New function.
	(maybe_plus_overflow): New function.
	(maybe_minus_overflow): New function.
	(plus_mult_no_ovf_and_keep_sign): New function.
	(plus_no_ovf_and_keep_sign): New function.
	* gimple-fold.h (maybe_mult_overflow): New declare.
	(plus_mult_no_ovf_and_keep_sign): New declare.
	(plus_no_ovf_and_keep_sign): New declare.
	* match.pd ((X - N * M) / N): New pattern.
	((X + N * M) / N): New pattern.
	((X + C) / N): New pattern.
	((X + C) >> N): New pattern.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr108757-1.c: New test.
	* gcc.dg/pr108757-2.c: New test.
	* gcc.dg/pr108757.h: New test.

---
 gcc/gimple-fold.cc                | 161 ++++++++++++++++++++
 gcc/gimple-fold.h                 |   3 +
 gcc/match.pd                      |  58 +++++++
 gcc/testsuite/gcc.dg/pr108757-1.c |  18 +++
 gcc/testsuite/gcc.dg/pr108757-2.c |  19 +++
 gcc/testsuite/gcc.dg/pr108757.h   | 244 ++++++++++++++++++++++++++++++
 6 files changed, 503 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
 create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
 create mode 100644 gcc/testsuite/gcc.dg/pr108757.h

diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
index 581575b65ec..bb833ae17b3 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
       return false;
     }
 }
+
+/* Return true if "X * Y" may be overflow.  */
+
+bool
+maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
+{
+  wide_int wmin0 = x.lower_bound ();
+  wide_int wmax0 = x.upper_bound ();
+  wide_int wmin1 = y.lower_bound ();
+  wide_int wmax1 = y.upper_bound ();
+
+  wi::overflow_type min_ovf, max_ovf;
+  wi::mul (wmin0, wmin1, sgn, &min_ovf);
+  wi::mul (wmax0, wmax1, sgn, &max_ovf);
+  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+    {
+      wi::mul (wmin0, wmax1, sgn, &min_ovf);
+      wi::mul (wmax0, wmin1, sgn, &max_ovf);
+      if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+	return false;
+    }
+  return true;
+}
+
+/* Return true if "X + Y" may be overflow.  */
+
+static bool
+maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
+{
+  wide_int wmin0 = x.lower_bound ();
+  wide_int wmax0 = x.upper_bound ();
+  wide_int wmin1 = y.lower_bound ();
+  wide_int wmax1 = y.upper_bound ();
+
+  wi::overflow_type min_ovf, max_ovf;
+  wi::add (wmax0, wmax1, sgn, &min_ovf);
+  wi::add (wmin0, wmin1, sgn, &max_ovf);
+  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+    return false;
+
+  return true;
+}
+
+/* Return true if "X - Y" may be overflow.  */
+
+static bool
+maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
+{
+  wide_int wmin0 = x.lower_bound ();
+  wide_int wmax0 = x.upper_bound ();
+  wide_int wmin1 = y.lower_bound ();
+  wide_int wmax1 = y.upper_bound ();
+
+  wi::overflow_type min_ovf, max_ovf;
+  wi::sub (wmin0, wmax1, sgn, &min_ovf);
+  wi::sub (wmax0, wmin1, sgn, &max_ovf);
+  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+    return false;
+
+  return true;
+}
+
+/* Return true if there is no overflow in the expression.
+   And no sign change on the plus/minus for X.
+   CODE is PLUS_EXPR, if the expression is "X + N * M".
+   CODE is MINUS_EXPR, if the expression is "X - N * M".
+   TYPE is the integer type of the expressions.  */
+
+bool
+plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
+				tree type)
+{
+  value_range vr0;
+  value_range vr1;
+  value_range vr2;
+
+  if (get_range_query (cfun)->range_of_expr (vr0, x)
+      && get_range_query (cfun)->range_of_expr (vr1, n)
+      && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
+      && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
+      && !vr2.varying_p () && !vr2.undefined_p ())
+    {
+      signop sgn = TYPE_SIGN (type);
+      if (!TYPE_OVERFLOW_UNDEFINED (type))
+	{
+	  if (maybe_mult_overflow (vr1, vr2, sgn))
+	    {
+	      m = fold_build1 (NEGATE_EXPR, type, m);
+	      if (get_range_query (cfun)->range_of_expr (vr2, m)
+		  && !vr2.varying_p () && !vr2.undefined_p ()
+		  && !maybe_mult_overflow (vr1, vr2, sgn))
+		code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
+	      else
+		return false;
+	    }
+
+	  /* Get range of N*M  */
+	  tree mult = fold_build2 (MULT_EXPR, type, n, m);
+	  value_range vr3;
+	  bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
+	  gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
+
+	  bool overflow = code == MINUS_EXPR
+			    ? maybe_minus_overflow (vr0, vr3, sgn)
+			    : maybe_plus_overflow (vr0, vr3, sgn);
+	  if (overflow)
+	    return false;
+	}
+
+      /* The value cross "0" is also a concern.  */
+      if (sgn == UNSIGNED)
+	return true;
+      tree op
+	= fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
+      value_range vr4;
+      if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
+	  && !vr4.undefined_p ())
+	{
+	  /* X and (X +- N*M) are both positive (or both negtive).  */
+	  if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
+	       && wi::ge_p (vr4.lower_bound (), 0, sgn))
+	      || (wi::le_p (vr0.upper_bound (), 0, sgn)
+		  && wi::le_p (vr4.upper_bound (), 0, sgn)))
+	    return true;
+	}
+    }
+
+return false;
+}
+
+/* Return true if there is no overflow and no sign change in "X + C".
+   C is a constant integer.  */
+
+bool
+plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
+{
+  value_range vr;
+  if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
+      && !vr.undefined_p ())
+    {
+      wi::overflow_type ovf = wi::OVF_NONE;
+      wide_int min = vr.lower_bound ();
+      wide_int max = vr.upper_bound ();
+      wide_int wc = wi::to_wide (c);
+      if (!TYPE_OVERFLOW_UNDEFINED (type))
+	{
+	  if (tree_int_cst_sign_bit (c))
+	    wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
+	  else
+	    wi::add (max, wc, TYPE_SIGN (type), &ovf);
+	}
+      if (ovf == wi::OVF_NONE)
+	/* unsigned, or 't' and 't + C' are both positive/negative.  */
+	if (TYPE_UNSIGNED (type)
+	    || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
+	    || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
+	  return true;
+    }
+
+  return false;
+}
diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
index 2fd58db9a2e..45df86a433e 100644
--- a/gcc/gimple-fold.h
+++ b/gcc/gimple-fold.h
@@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
 extern void replace_call_with_value (gimple_stmt_iterator *, tree);
 extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
 extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
+extern bool maybe_mult_overflow (tree, tree, tree);
+extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
+extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
 
 /* gimple_build, functionally matching fold_buildN, outputs stmts
    int the provided sequence, matching and simplifying them on-the-fly.
diff --git a/gcc/match.pd b/gcc/match.pd
index 16482b741ea..6f7a6afdca8 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 #endif
    ))))
 
+#if GIMPLE
+(for div (trunc_div exact_div)
+ /* Simplify (t + M*N) / N -> t / N + M.  */
+ (simplify
+  (div (plus:c @0 (mult:c @1 @2)) @2)
+  (if (INTEGRAL_TYPE_P (type)
+       && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
+  (plus (div @0 @2) @1)))
+
+ /* Simplify (t - M*N) / N -> t / N - M.  */
+ (simplify
+  (div (minus @0 (mult:c @1 @2)) @2)
+  (if (INTEGRAL_TYPE_P (type)
+       && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR,  type))
+  (minus (div @0 @2) @1)))
+
+ /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N  */
+ (simplify
+  (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
+  (with
+   { tree repaired_c = @1;
+     if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+       repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
+   }
+   (if (INTEGRAL_TYPE_P (type)
+	&& multiple_of_p (type, repaired_c, @2)
+	&& plus_no_ovf_and_keep_sign (@0, @1, type))
+     (with
+      { wide_int m;
+	wide_int c = wi::to_wide (@1);
+	wide_int n = wi::to_wide (@2);
+	wi::overflow_type ovf;
+	if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+	  m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
+	else
+	  m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
+	gcc_assert (ovf == wi::OVF_NONE);
+      }
+   (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
+
+/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0.  */
+(simplify
+ (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
+      && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
+      && plus_no_ovf_and_keep_sign (@0, @1, type))
+  (with
+   { wide_int m;
+     wide_int c = wi::to_wide (@1);
+     wide_int n = wi::to_wide (@2);
+     if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+       m = -wi::rshift (-c, n, TYPE_SIGN (type));
+     else
+       m = wi::rshift (c, n, TYPE_SIGN (type));
+   }
+ (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
+#endif
+
 (for op (negate abs)
  /* Simplify cos(-x) and cos(|x|) -> cos(x).  Similarly for cosh.  */
  (for coss (COS COSH)
diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c b/gcc/testsuite/gcc.dg/pr108757-1.c
new file mode 100644
index 00000000000..7e7b60c756d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757-1.c
@@ -0,0 +1,18 @@
+/* PR tree-optimization/108757 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#include <limits.h>
+#define N 5
+#define M 3
+#define GAP 0
+typedef unsigned int UINT;
+typedef int INT;
+#define UMAX UINT_MAX
+#define IMAX INT_MAX
+#define IMIN INT_MIN
+#include "pr108757.h"
+
+/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" } } *
+/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c b/gcc/testsuite/gcc.dg/pr108757-2.c
new file mode 100644
index 00000000000..2a9ad234e68
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757-2.c
@@ -0,0 +1,19 @@
+/* PR tree-optimization/108757 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
+
+#include <limits.h>
+#define N 4
+#define M 3
+#define GAP 2
+typedef unsigned int UINT;
+typedef int INT;
+#define UMAX UINT_MAX
+#define IMAX INT_MAX
+#define IMIN INT_MIN
+#include "pr108757.h"
+
+/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
+
diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
new file mode 100644
index 00000000000..9dfa527f533
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757.h
@@ -0,0 +1,244 @@
+#define NOINLINE __attribute__ ((noinline))
+UINT NOINLINE
+opt_u1 (UINT x)
+{
+  if (x < (M * N) - GAP)
+    return 0;
+  UINT a = x - (M * N);
+  UINT b = a / N;
+  return b + M;
+}
+
+UINT NOINLINE
+opt_u2 (UINT x)
+{
+  if (x > (UMAX - (M * N) + GAP))
+    return 0;
+  UINT a = x + (M * N);
+  UINT b = a / N;
+  return b - M;
+}
+
+INT NOINLINE
+opt_s1 (INT x)
+{
+  if (x < (M * N) - GAP)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s2 (INT x)
+{
+  if (x < IMIN + (M * N) - GAP || x > 0)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s3 (INT x)
+{
+  if (x < (M * N) - GAP)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / -N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s4 (INT x)
+{
+  if (x < IMIN + (M * N) - GAP || x > 0)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / -N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s5 (INT x)
+{
+  if (x > (-M * N) + GAP)
+    return 0;
+  INT a = x - (-M * N);
+  INT b = a / N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s6 (INT x)
+{
+  if (x > IMAX - (M * N) + GAP || x < 0)
+    return 0;
+  INT a = x - (-M * N);
+  INT b = a / N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s7 (INT x)
+{
+  if (x > (M * -N) + GAP)
+    return 0;
+  INT a = x - (M * -N);
+  INT b = a / -N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s8 (INT x)
+{
+  if (x > IMAX - (M * N) + GAP || x < 0)
+    return 0;
+  INT a = x - (M * -N);
+  INT b = a / -N;
+  return b + M;
+}
+
+UINT NOINLINE
+opt_u3 (UINT x)
+{
+  if (x < (M << N) - GAP)
+    return 0;
+  UINT a = x - (M << N);
+  UINT b = a >> N;
+  return b + M;
+}
+
+UINT NOINLINE
+opt_u4 (UINT x)
+{
+  if (x > (UMAX - (M << N)) + GAP)
+    return 0;
+  UINT a = x + (M << N);
+  UINT b = a >> N;
+  return b - M;
+}
+
+INT NOINLINE
+opt_s9 (INT x)
+{
+  if (x < (M << N) - GAP)
+    return 0;
+  INT a = x - (M << N);
+  INT b = a >> N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s10 (INT x)
+{
+  if (x < IMIN + (M << N) - GAP || x > 0)
+    return 0;
+  INT a = x - (M << N);
+  INT b = a >> N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s11 (INT x)
+{
+  if (x > (-M << N) + GAP)
+    return 0;
+  INT a = x - (-M << N);
+  INT b = a >> N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s12 (INT x)
+{
+  if (x > IMAX - (M << N) + GAP || x < 0)
+    return 0;
+  INT a = x - (-M << N);
+  INT b = a >> N;
+  return b + -M;
+}
+
+UINT NOINLINE
+opt_u5 (UINT x, UINT n, UINT m)
+{
+  if (n > N || m > M)
+    return 0;
+  if (x < (M*N) - GAP)
+    return 0;
+  UINT a = x - (m * n);
+  UINT b = a / n;
+  return b + m;
+}
+
+UINT NOINLINE
+opt_u6 (UINT x, UINT n, UINT m)
+{
+  if (n > N || m > M)
+    return 0;
+  if (x > (UMAX - M*N) + GAP)
+    return 0;
+  UINT a = x + (m * n);
+  UINT b = a / n;
+  return b - m;
+}
+
+INT NOINLINE
+opt_s13 (INT x, INT n, INT m)
+{
+  if (n > N || m > M || n < 0 || m < 0)
+    return 0;
+  if (x < (M*N) - GAP)
+    return 0;
+  INT a = x - (m * n);
+  INT b = a / n;
+  return b + m;
+}
+
+INT NOINLINE
+opt_s14 (INT x, INT n, INT m)
+{
+  if (n > N || m > M || n < 0 || m < 0)
+    return 0;
+  if (x > -M*N + GAP)
+    return 0;
+  INT a = x + (m * n);
+  INT b = a / n;
+  return b - m;
+}
+
+INT
+opt_s15 (INT x, INT n, INT m)
+{
+  if (n > 0 || m > 0 || n < -N || m < -M)
+    return 0;
+  if (x < (M*N) - GAP)
+    return 0;
+  INT a = x - (m * n);
+  INT b = a / n;
+  return b + m;
+}
+
+INT NOINLINE
+opt_s16 (INT x, INT n, INT m)
+{
+  if (n > 0 || m > 0 || n < -N || m < -M)
+    return 0;
+  if (x < 0 || x > (IMAX - M*N) + GAP)
+    return 0;
+  INT a = x + (m * n);
+  INT b = a / n;
+  return b - m;
+}
+
+UINT NOINLINE
+opt_u7 (UINT x, UINT n, UINT m)
+{
+  if (n > N || m <= UMAX - M)
+    return 0;
+  if (x > UMAX - (M*N) + GAP)
+    return 0;
+  UINT a = x - (m * n);
+  UINT b = a / n;
+  return b + m;
+}
-- 
2.39.1

Re: [PATCH V2] Optimize '(X - N * M) / N' to 'X / N - M' if valid

[Richard Biener]

On Wed, 7 Jun 2023, Jiufu Guo wrote:

> Hi,
> 
> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
> wrap/overflow/underflow. So, it is valid that "X - N * M" does
> not cross zero and does not wrap/overflow/underflow.
> 
> Compare with previous version:
> https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
> 
> This patch 1. adds the patterns for variable N or M,
> 2. uses simpler form "(X - N * M) / N" for patterns,
> 3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
> 4. updates testcases
> 
> Bootstrap & regtest pass on ppc64{,le} and x86_64.
> Is this patch ok for trunk?

Comments below.

> 
> BR,
> Jeff (Jiufu Guo)
> 
> 	PR tree-optimization/108757
> 
> gcc/ChangeLog:
> 
> 	* gimple-fold.cc (maybe_mult_overflow): New function.
> 	(maybe_plus_overflow): New function.
> 	(maybe_minus_overflow): New function.
> 	(plus_mult_no_ovf_and_keep_sign): New function.
> 	(plus_no_ovf_and_keep_sign): New function.
> 	* gimple-fold.h (maybe_mult_overflow): New declare.
> 	(plus_mult_no_ovf_and_keep_sign): New declare.
> 	(plus_no_ovf_and_keep_sign): New declare.
> 	* match.pd ((X - N * M) / N): New pattern.
> 	((X + N * M) / N): New pattern.
> 	((X + C) / N): New pattern.
> 	((X + C) >> N): New pattern.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/pr108757-1.c: New test.
> 	* gcc.dg/pr108757-2.c: New test.
> 	* gcc.dg/pr108757.h: New test.
> 
> ---
>  gcc/gimple-fold.cc                | 161 ++++++++++++++++++++
>  gcc/gimple-fold.h                 |   3 +
>  gcc/match.pd                      |  58 +++++++
>  gcc/testsuite/gcc.dg/pr108757-1.c |  18 +++
>  gcc/testsuite/gcc.dg/pr108757-2.c |  19 +++
>  gcc/testsuite/gcc.dg/pr108757.h   | 244 ++++++++++++++++++++++++++++++
>  6 files changed, 503 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
>  create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
> 
> diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
> index 581575b65ec..bb833ae17b3 100644
> --- a/gcc/gimple-fold.cc
> +++ b/gcc/gimple-fold.cc
> @@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
>        return false;
>      }
>  }
> +
> +/* Return true if "X * Y" may be overflow.  */
> +
> +bool
> +maybe_mult_overflow (value_range &x, value_range &y, signop sgn)

These functions look like some "basic" functionality that should
be (or maybe already is?  Andrew?) provided by the value-range
framework.  That means it should not reside in gimple-fold.{cc,h}
but elsehwere and possibly with an API close to the existing
value-range stuff.

Andrew?

> +{
> +  wide_int wmin0 = x.lower_bound ();
> +  wide_int wmax0 = x.upper_bound ();
> +  wide_int wmin1 = y.lower_bound ();
> +  wide_int wmax1 = y.upper_bound ();
> +
> +  wi::overflow_type min_ovf, max_ovf;
> +  wi::mul (wmin0, wmin1, sgn, &min_ovf);
> +  wi::mul (wmax0, wmax1, sgn, &max_ovf);
> +  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> +    {
> +      wi::mul (wmin0, wmax1, sgn, &min_ovf);
> +      wi::mul (wmax0, wmin1, sgn, &max_ovf);
> +      if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> +	return false;
> +    }
> +  return true;
> +}
> +
> +/* Return true if "X + Y" may be overflow.  */
> +
> +static bool
> +maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
> +{
> +  wide_int wmin0 = x.lower_bound ();
> +  wide_int wmax0 = x.upper_bound ();
> +  wide_int wmin1 = y.lower_bound ();
> +  wide_int wmax1 = y.upper_bound ();
> +
> +  wi::overflow_type min_ovf, max_ovf;
> +  wi::add (wmax0, wmax1, sgn, &min_ovf);
> +  wi::add (wmin0, wmin1, sgn, &max_ovf);
> +  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> +    return false;
> +
> +  return true;
> +}
> +
> +/* Return true if "X - Y" may be overflow.  */
> +
> +static bool
> +maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
> +{
> +  wide_int wmin0 = x.lower_bound ();
> +  wide_int wmax0 = x.upper_bound ();
> +  wide_int wmin1 = y.lower_bound ();
> +  wide_int wmax1 = y.upper_bound ();
> +
> +  wi::overflow_type min_ovf, max_ovf;
> +  wi::sub (wmin0, wmax1, sgn, &min_ovf);
> +  wi::sub (wmax0, wmin1, sgn, &max_ovf);
> +  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> +    return false;
> +
> +  return true;
> +}
> +
> +/* Return true if there is no overflow in the expression.
> +   And no sign change on the plus/minus for X.

What does the second sentence mean?  sign(X) == sign (X + N*M)?
I suppose zero has positive sign?

> +   CODE is PLUS_EXPR, if the expression is "X + N * M".
> +   CODE is MINUS_EXPR, if the expression is "X - N * M".
> +   TYPE is the integer type of the expressions.  */
> +
> +bool
> +plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
> +				tree type)
> +{
> +  value_range vr0;
> +  value_range vr1;
> +  value_range vr2;
> +
> +  if (get_range_query (cfun)->range_of_expr (vr0, x)
> +      && get_range_query (cfun)->range_of_expr (vr1, n)
> +      && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
> +      && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
> +      && !vr2.varying_p () && !vr2.undefined_p ())
> +    {
> +      signop sgn = TYPE_SIGN (type);
> +      if (!TYPE_OVERFLOW_UNDEFINED (type))
> +	{
> +	  if (maybe_mult_overflow (vr1, vr2, sgn))
> +	    {
> +	      m = fold_build1 (NEGATE_EXPR, type, m);

How's this valid?  'm' might wrap here?  IMHO this special-case
needs a comment.  Maybe you try to handle only constant 'm' here
since we tend to canonicalize X - N * 4u to X + N * -4u?

> +	      if (get_range_query (cfun)->range_of_expr (vr2, m)
> +		  && !vr2.varying_p () && !vr2.undefined_p ()
> +		  && !maybe_mult_overflow (vr1, vr2, sgn))
> +		code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
> +	      else
> +		return false;
> +	    }
> +
> +	  /* Get range of N*M  */
> +	  tree mult = fold_build2 (MULT_EXPR, type, n, m);

Since you are working on GIMPLE 'mult' has an SSA name associated
which should also possibly get you more precise ranges (just capture
it, no need to re-generate a GENERIC expression here).

> +	  value_range vr3;
> +	  bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
> +	  gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
> +
> +	  bool overflow = code == MINUS_EXPR
> +			    ? maybe_minus_overflow (vr0, vr3, sgn)
> +			    : maybe_plus_overflow (vr0, vr3, sgn);
> +	  if (overflow)
> +	    return false;
> +	}
> +
> +      /* The value cross "0" is also a concern.  */
> +      if (sgn == UNSIGNED)
> +	return true;
> +      tree op
> +	= fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
> +      value_range vr4;

Again please use the captured representative here.

> +      if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
> +	  && !vr4.undefined_p ())
> +	{
> +	  /* X and (X +- N*M) are both positive (or both negtive).  */
> +	  if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
> +	       && wi::ge_p (vr4.lower_bound (), 0, sgn))
> +	      || (wi::le_p (vr0.upper_bound (), 0, sgn)
> +		  && wi::le_p (vr4.upper_bound (), 0, sgn)))

As noted above I was hoping there's a value-range API for this.  We
seem to have set_nonnegative, set_zero, etc. but no way to query
a known sign for integer ranges.  FP ranges have signbit_p,
I guess that would work here, too, no?

Andrew?

Seeing the repeated check for !varying && !undefined I wonder if
we can somehow avoid the repetition with a higher level API?

> +	    return true;
> +	}
> +    }
> +
> +return false;
> +}
> +
> +/* Return true if there is no overflow and no sign change in "X + C".
> +   C is a constant integer.  */
> +
> +bool
> +plus_no_ovf_and_keep_sign (tree x, tree c, tree type)

Pass 'c' as const wide_int& here.

> +{
> +  value_range vr;
> +  if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
> +      && !vr.undefined_p ())
> +    {
> +      wi::overflow_type ovf = wi::OVF_NONE;
> +      wide_int min = vr.lower_bound ();
> +      wide_int max = vr.upper_bound ();
> +      wide_int wc = wi::to_wide (c);
> +      if (!TYPE_OVERFLOW_UNDEFINED (type))
> +	{
> +	  if (tree_int_cst_sign_bit (c))
> +	    wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
> +	  else
> +	    wi::add (max, wc, TYPE_SIGN (type), &ovf);
> +	}
> +      if (ovf == wi::OVF_NONE)
> +	/* unsigned, or 't' and 't + C' are both positive/negative.  */
> +	if (TYPE_UNSIGNED (type)
> +	    || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))

the second compare should be the same as wi::ge_p (min, -wc, SIGNED) or
are you implicitely checking for overflow here?

> +	    || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
> +	  return true;
> +    }
> +
> +  return false;
> +}
> diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
> index 2fd58db9a2e..45df86a433e 100644
> --- a/gcc/gimple-fold.h
> +++ b/gcc/gimple-fold.h
> @@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
>  extern void replace_call_with_value (gimple_stmt_iterator *, tree);
>  extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
>  extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
> +extern bool maybe_mult_overflow (tree, tree, tree);
> +extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
> +extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
>  
>  /* gimple_build, functionally matching fold_buildN, outputs stmts
>     int the provided sequence, matching and simplifying them on-the-fly.
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 16482b741ea..6f7a6afdca8 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  #endif
>     ))))
>  
> +#if GIMPLE
> +(for div (trunc_div exact_div)
> + /* Simplify (t + M*N) / N -> t / N + M.  */
> + (simplify
> +  (div (plus:c @0 (mult:c @1 @2)) @2)
> +  (if (INTEGRAL_TYPE_P (type)
> +       && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
> +  (plus (div @0 @2) @1)))
> +
> + /* Simplify (t - M*N) / N -> t / N - M.  */
> + (simplify
> +  (div (minus @0 (mult:c @1 @2)) @2)
> +  (if (INTEGRAL_TYPE_P (type)
> +       && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR,  type))
> +  (minus (div @0 @2) @1)))
> +
> + /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N  */
> + (simplify
> +  (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
> +  (with
> +   { tree repaired_c = @1;
> +     if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> +       repaired_c = fold_build1 (NEGATE_EXPR, type, @1);

What if @1 is 0x80000000?  Please consider re-doing this with
wide_int from the start.

> +   }
> +   (if (INTEGRAL_TYPE_P (type)
> +	&& multiple_of_p (type, repaired_c, @2)
> +	&& plus_no_ovf_and_keep_sign (@0, @1, type))
> +     (with
> +      { wide_int m;
> +	wide_int c = wi::to_wide (@1);
> +	wide_int n = wi::to_wide (@2);
> +	wi::overflow_type ovf;
> +	if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> +	  m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
> +	else
> +	  m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
> +	gcc_assert (ovf == wi::OVF_NONE);
> +      }
> +   (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
> +
> +/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0.  */
> +(simplify
> + (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
> + (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
> +      && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
> +      && plus_no_ovf_and_keep_sign (@0, @1, type))
> +  (with
> +   { wide_int m;
> +     wide_int c = wi::to_wide (@1);
> +     wide_int n = wi::to_wide (@2);
> +     if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> +       m = -wi::rshift (-c, n, TYPE_SIGN (type));
> +     else
> +       m = wi::rshift (c, n, TYPE_SIGN (type));
> +   }
> + (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
> +#endif
> +
>  (for op (negate abs)
>   /* Simplify cos(-x) and cos(|x|) -> cos(x).  Similarly for cosh.  */
>   (for coss (COS COSH)
> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c b/gcc/testsuite/gcc.dg/pr108757-1.c
> new file mode 100644
> index 00000000000..7e7b60c756d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
> @@ -0,0 +1,18 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#include <limits.h>
> +#define N 5
> +#define M 3
> +#define GAP 0
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" } } *
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c b/gcc/testsuite/gcc.dg/pr108757-2.c
> new file mode 100644
> index 00000000000..2a9ad234e68
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
> @@ -0,0 +1,19 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
> +
> +#include <limits.h>
> +#define N 4
> +#define M 3
> +#define GAP 2
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
> +
> diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
> new file mode 100644
> index 00000000000..9dfa527f533
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757.h
> @@ -0,0 +1,244 @@
> +#define NOINLINE __attribute__ ((noinline))
> +UINT NOINLINE
> +opt_u1 (UINT x)
> +{
> +  if (x < (M * N) - GAP)
> +    return 0;
> +  UINT a = x - (M * N);
> +  UINT b = a / N;
> +  return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u2 (UINT x)
> +{
> +  if (x > (UMAX - (M * N) + GAP))
> +    return 0;
> +  UINT a = x + (M * N);
> +  UINT b = a / N;
> +  return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s1 (INT x)
> +{
> +  if (x < (M * N) - GAP)
> +    return 0;
> +  INT a = x - (M * N);
> +  INT b = a / N;
> +  return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s2 (INT x)
> +{
> +  if (x < IMIN + (M * N) - GAP || x > 0)
> +    return 0;
> +  INT a = x - (M * N);
> +  INT b = a / N;
> +  return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s3 (INT x)
> +{
> +  if (x < (M * N) - GAP)
> +    return 0;
> +  INT a = x - (M * N);
> +  INT b = a / -N;
> +  return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s4 (INT x)
> +{
> +  if (x < IMIN + (M * N) - GAP || x > 0)
> +    return 0;
> +  INT a = x - (M * N);
> +  INT b = a / -N;
> +  return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s5 (INT x)
> +{
> +  if (x > (-M * N) + GAP)
> +    return 0;
> +  INT a = x - (-M * N);
> +  INT b = a / N;
> +  return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s6 (INT x)
> +{
> +  if (x > IMAX - (M * N) + GAP || x < 0)
> +    return 0;
> +  INT a = x - (-M * N);
> +  INT b = a / N;
> +  return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s7 (INT x)
> +{
> +  if (x > (M * -N) + GAP)
> +    return 0;
> +  INT a = x - (M * -N);
> +  INT b = a / -N;
> +  return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s8 (INT x)
> +{
> +  if (x > IMAX - (M * N) + GAP || x < 0)
> +    return 0;
> +  INT a = x - (M * -N);
> +  INT b = a / -N;
> +  return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u3 (UINT x)
> +{
> +  if (x < (M << N) - GAP)
> +    return 0;
> +  UINT a = x - (M << N);
> +  UINT b = a >> N;
> +  return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u4 (UINT x)
> +{
> +  if (x > (UMAX - (M << N)) + GAP)
> +    return 0;
> +  UINT a = x + (M << N);
> +  UINT b = a >> N;
> +  return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s9 (INT x)
> +{
> +  if (x < (M << N) - GAP)
> +    return 0;
> +  INT a = x - (M << N);
> +  INT b = a >> N;
> +  return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s10 (INT x)
> +{
> +  if (x < IMIN + (M << N) - GAP || x > 0)
> +    return 0;
> +  INT a = x - (M << N);
> +  INT b = a >> N;
> +  return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s11 (INT x)
> +{
> +  if (x > (-M << N) + GAP)
> +    return 0;
> +  INT a = x - (-M << N);
> +  INT b = a >> N;
> +  return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s12 (INT x)
> +{
> +  if (x > IMAX - (M << N) + GAP || x < 0)
> +    return 0;
> +  INT a = x - (-M << N);
> +  INT b = a >> N;
> +  return b + -M;
> +}
> +
> +UINT NOINLINE
> +opt_u5 (UINT x, UINT n, UINT m)
> +{
> +  if (n > N || m > M)
> +    return 0;
> +  if (x < (M*N) - GAP)
> +    return 0;
> +  UINT a = x - (m * n);
> +  UINT b = a / n;
> +  return b + m;
> +}
> +
> +UINT NOINLINE
> +opt_u6 (UINT x, UINT n, UINT m)
> +{
> +  if (n > N || m > M)
> +    return 0;
> +  if (x > (UMAX - M*N) + GAP)
> +    return 0;
> +  UINT a = x + (m * n);
> +  UINT b = a / n;
> +  return b - m;
> +}
> +
> +INT NOINLINE
> +opt_s13 (INT x, INT n, INT m)
> +{
> +  if (n > N || m > M || n < 0 || m < 0)
> +    return 0;
> +  if (x < (M*N) - GAP)
> +    return 0;
> +  INT a = x - (m * n);
> +  INT b = a / n;
> +  return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s14 (INT x, INT n, INT m)
> +{
> +  if (n > N || m > M || n < 0 || m < 0)
> +    return 0;
> +  if (x > -M*N + GAP)
> +    return 0;
> +  INT a = x + (m * n);
> +  INT b = a / n;
> +  return b - m;
> +}
> +
> +INT
> +opt_s15 (INT x, INT n, INT m)
> +{
> +  if (n > 0 || m > 0 || n < -N || m < -M)
> +    return 0;
> +  if (x < (M*N) - GAP)
> +    return 0;
> +  INT a = x - (m * n);
> +  INT b = a / n;
> +  return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s16 (INT x, INT n, INT m)
> +{
> +  if (n > 0 || m > 0 || n < -N || m < -M)
> +    return 0;
> +  if (x < 0 || x > (IMAX - M*N) + GAP)
> +    return 0;
> +  INT a = x + (m * n);
> +  INT b = a / n;
> +  return b - m;
> +}
> +
> +UINT NOINLINE
> +opt_u7 (UINT x, UINT n, UINT m)
> +{
> +  if (n > N || m <= UMAX - M)
> +    return 0;
> +  if (x > UMAX - (M*N) + GAP)
> +    return 0;
> +  UINT a = x - (m * n);
> +  UINT b = a / n;
> +  return b + m;
> +}
> 

-- 
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)

Re: [PATCH V2] Optimize '(X - N * M) / N' to 'X / N - M' if valid

[Jiufu Guo]

Hi,

Richard Biener <rguenther@suse.de> writes:

> On Wed, 7 Jun 2023, Jiufu Guo wrote:
>
>> Hi,
>> 
>> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
>> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
>> wrap/overflow/underflow. So, it is valid that "X - N * M" does
>> not cross zero and does not wrap/overflow/underflow.
>> 
>> Compare with previous version:
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
>> 
>> This patch 1. adds the patterns for variable N or M,
>> 2. uses simpler form "(X - N * M) / N" for patterns,
>> 3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
>> 4. updates testcases
>> 
>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>> Is this patch ok for trunk?
>
> Comments below.
>
>> 
>> BR,
>> Jeff (Jiufu Guo)
>> 
>> 	PR tree-optimization/108757
>> 
>> gcc/ChangeLog:
>> 
>> 	* gimple-fold.cc (maybe_mult_overflow): New function.
>> 	(maybe_plus_overflow): New function.
>> 	(maybe_minus_overflow): New function.
>> 	(plus_mult_no_ovf_and_keep_sign): New function.
>> 	(plus_no_ovf_and_keep_sign): New function.
>> 	* gimple-fold.h (maybe_mult_overflow): New declare.
>> 	(plus_mult_no_ovf_and_keep_sign): New declare.
>> 	(plus_no_ovf_and_keep_sign): New declare.
>> 	* match.pd ((X - N * M) / N): New pattern.
>> 	((X + N * M) / N): New pattern.
>> 	((X + C) / N): New pattern.
>> 	((X + C) >> N): New pattern.
>> 
>> gcc/testsuite/ChangeLog:
>> 
>> 	* gcc.dg/pr108757-1.c: New test.
>> 	* gcc.dg/pr108757-2.c: New test.
>> 	* gcc.dg/pr108757.h: New test.
>> 
>> ---
>>  gcc/gimple-fold.cc                | 161 ++++++++++++++++++++
>>  gcc/gimple-fold.h                 |   3 +
>>  gcc/match.pd                      |  58 +++++++
>>  gcc/testsuite/gcc.dg/pr108757-1.c |  18 +++
>>  gcc/testsuite/gcc.dg/pr108757-2.c |  19 +++
>>  gcc/testsuite/gcc.dg/pr108757.h   | 244 ++++++++++++++++++++++++++++++
>>  6 files changed, 503 insertions(+)
>>  create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
>>  create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
>>  create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
>> 
>> diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
>> index 581575b65ec..bb833ae17b3 100644
>> --- a/gcc/gimple-fold.cc
>> +++ b/gcc/gimple-fold.cc
>> @@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
>>        return false;
>>      }
>>  }
>> +
>> +/* Return true if "X * Y" may be overflow.  */
>> +
>> +bool
>> +maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
>
> These functions look like some "basic" functionality that should
> be (or maybe already is?  Andrew?) provided by the value-range
> framework.  That means it should not reside in gimple-fold.{cc,h}
> but elsehwere and possibly with an API close to the existing
> value-range stuff.
>
> Andrew?

It would be great to get the overflow info directly from VR :)
Now, in range-op.cc, there is aleady value_range_with_overflow and
value_range_from_overflowed_bounds which checks OVFs.
While this information seems not recorded.  Maybe, it is helpful
adding a field in VR and adding API to query it.

>
>> +{
>> +  wide_int wmin0 = x.lower_bound ();
>> +  wide_int wmax0 = x.upper_bound ();
>> +  wide_int wmin1 = y.lower_bound ();
>> +  wide_int wmax1 = y.upper_bound ();
>> +
>> +  wi::overflow_type min_ovf, max_ovf;
>> +  wi::mul (wmin0, wmin1, sgn, &min_ovf);
>> +  wi::mul (wmax0, wmax1, sgn, &max_ovf);
>> +  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> +    {
>> +      wi::mul (wmin0, wmax1, sgn, &min_ovf);
>> +      wi::mul (wmax0, wmin1, sgn, &max_ovf);
>> +      if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> +	return false;
>> +    }
>> +  return true;
>> +}
>> +
>> +/* Return true if "X + Y" may be overflow.  */
>> +
>> +static bool
>> +maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
>> +{
>> +  wide_int wmin0 = x.lower_bound ();
>> +  wide_int wmax0 = x.upper_bound ();
>> +  wide_int wmin1 = y.lower_bound ();
>> +  wide_int wmax1 = y.upper_bound ();
>> +
>> +  wi::overflow_type min_ovf, max_ovf;
>> +  wi::add (wmax0, wmax1, sgn, &min_ovf);
>> +  wi::add (wmin0, wmin1, sgn, &max_ovf);
>> +  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> +    return false;
>> +
>> +  return true;
>> +}
>> +
>> +/* Return true if "X - Y" may be overflow.  */
>> +
>> +static bool
>> +maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
>> +{
>> +  wide_int wmin0 = x.lower_bound ();
>> +  wide_int wmax0 = x.upper_bound ();
>> +  wide_int wmin1 = y.lower_bound ();
>> +  wide_int wmax1 = y.upper_bound ();
>> +
>> +  wi::overflow_type min_ovf, max_ovf;
>> +  wi::sub (wmin0, wmax1, sgn, &min_ovf);
>> +  wi::sub (wmax0, wmin1, sgn, &max_ovf);
>> +  if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> +    return false;
>> +
>> +  return true;
>> +}
>> +
>> +/* Return true if there is no overflow in the expression.
>> +   And no sign change on the plus/minus for X.
>
> What does the second sentence mean?  sign(X) == sign (X + N*M)?
> I suppose zero has positive sign?

Right! This is useful for signed int.  If "X" and "X + N*M" are
both negative, this transformation would be also valid.
Would use "sign(X) == sign (X + N*M)" clearly.

>
>> +   CODE is PLUS_EXPR, if the expression is "X + N * M".
>> +   CODE is MINUS_EXPR, if the expression is "X - N * M".
>> +   TYPE is the integer type of the expressions.  */
>> +
>> +bool
>> +plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
>> +				tree type)
>> +{
>> +  value_range vr0;
>> +  value_range vr1;
>> +  value_range vr2;
>> +
>> +  if (get_range_query (cfun)->range_of_expr (vr0, x)
>> +      && get_range_query (cfun)->range_of_expr (vr1, n)
>> +      && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
>> +      && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
>> +      && !vr2.varying_p () && !vr2.undefined_p ())
>> +    {
>> +      signop sgn = TYPE_SIGN (type);
>> +      if (!TYPE_OVERFLOW_UNDEFINED (type))
>> +	{
>> +	  if (maybe_mult_overflow (vr1, vr2, sgn))
>> +	    {
>> +	      m = fold_build1 (NEGATE_EXPR, type, m);
>
> How's this valid?  'm' might wrap here?  IMHO this special-case
> needs a comment.  Maybe you try to handle only constant 'm' here
> since we tend to canonicalize X - N * 4u to X + N * -4u?

Thanks! A comment should be added.  This would be useful for
"unsigned" (for signed, OVF info for 'n*m' would be same with
'n*-m').

Like a prepared test case for this:

opt_u7 (UINT x, UINT n, UINT m)
{
  if (n > N || m <= UMAX - M)
    return 0;
  if (x > UMAX - (M*N) + GAP)
    return 0;
  UINT a = x - (m * n);
  UINT b = a / n;

Here, m is "-M to -1u", then "n*m" overflows, but
"n*-m" does not overflow. And "x - (m * n)" can be treated
as "x + (-m) * n".

>
>> +	      if (get_range_query (cfun)->range_of_expr (vr2, m)
>> +		  && !vr2.varying_p () && !vr2.undefined_p ()
>> +		  && !maybe_mult_overflow (vr1, vr2, sgn))
>> +		code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
>> +	      else
>> +		return false;
>> +	    }
>> +
>> +	  /* Get range of N*M  */
>> +	  tree mult = fold_build2 (MULT_EXPR, type, n, m);
>
> Since you are working on GIMPLE 'mult' has an SSA name associated
> which should also possibly get you more precise ranges (just capture
> it, no need to re-generate a GENERIC expression here).

Great idea! 
>
>> +	  value_range vr3;
>> +	  bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
>> +	  gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
>> +
>> +	  bool overflow = code == MINUS_EXPR
>> +			    ? maybe_minus_overflow (vr0, vr3, sgn)
>> +			    : maybe_plus_overflow (vr0, vr3, sgn);
>> +	  if (overflow)
>> +	    return false;
>> +	}
>> +
>> +      /* The value cross "0" is also a concern.  */
>> +      if (sgn == UNSIGNED)
>> +	return true;
>> +      tree op
>> +	= fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
>> +      value_range vr4;
>
> Again please use the captured representative here.
Thanks!
>
>> +      if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
>> +	  && !vr4.undefined_p ())
>> +	{
>> +	  /* X and (X +- N*M) are both positive (or both negtive).  */
>> +	  if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
>> +	       && wi::ge_p (vr4.lower_bound (), 0, sgn))
>> +	      || (wi::le_p (vr0.upper_bound (), 0, sgn)
>> +		  && wi::le_p (vr4.upper_bound (), 0, sgn)))
>
> As noted above I was hoping there's a value-range API for this.  We
> seem to have set_nonnegative, set_zero, etc. but no way to query
> a known sign for integer ranges.  FP ranges have signbit_p,
> I guess that would work here, too, no?

Thanks for pointing out this! I will check these APIs!

>
> Andrew?
>
> Seeing the repeated check for !varying && !undefined I wonder if
> we can somehow avoid the repetition with a higher level API?

The VR info for x,n,m are checked. If OVF info for "X", "N*M", are
checked too, ranges for combined expressions ("N*M", "X-N*M") may not
be needed, but verifying the final OVF infor may still be required.

Thanks for any comments!!

>
>> +	    return true;
>> +	}
>> +    }
>> +
>> +return false;
>> +}
>> +
>> +/* Return true if there is no overflow and no sign change in "X + C".
>> +   C is a constant integer.  */
>> +
>> +bool
>> +plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
>
> Pass 'c' as const wide_int& here.
Yeap, while "tree_int_cst_sign_bit (c)" can be used on "tree c" :)
Using wide_int should be also ok, tree_int_cst_sign_bit is also based on
wide_int.

>
>> +{
>> +  value_range vr;
>> +  if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
>> +      && !vr.undefined_p ())
>> +    {
>> +      wi::overflow_type ovf = wi::OVF_NONE;
>> +      wide_int min = vr.lower_bound ();
>> +      wide_int max = vr.upper_bound ();
>> +      wide_int wc = wi::to_wide (c);
>> +      if (!TYPE_OVERFLOW_UNDEFINED (type))
>> +	{
>> +	  if (tree_int_cst_sign_bit (c))
>> +	    wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
>> +	  else
>> +	    wi::add (max, wc, TYPE_SIGN (type), &ovf);
>> +	}
>> +      if (ovf == wi::OVF_NONE)
>> +	/* unsigned, or 't' and 't + C' are both positive/negative.  */
>> +	if (TYPE_UNSIGNED (type)
>> +	    || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
>
> the second compare should be the same as wi::ge_p (min, -wc, SIGNED) or
> are you implicitely checking for overflow here?
"wi::ge_p (min + wc, 0, SIGNED)" is used just because it may more
readable as: "'min + wc' is positive". 

>
>> +	    || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
>> +	  return true;
>> +    }
>> +
>> +  return false;
>> +}
>> diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
>> index 2fd58db9a2e..45df86a433e 100644
>> --- a/gcc/gimple-fold.h
>> +++ b/gcc/gimple-fold.h
>> @@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
>>  extern void replace_call_with_value (gimple_stmt_iterator *, tree);
>>  extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
>>  extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
>> +extern bool maybe_mult_overflow (tree, tree, tree);
>> +extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
>> +extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
>>  
>>  /* gimple_build, functionally matching fold_buildN, outputs stmts
>>     int the provided sequence, matching and simplifying them on-the-fly.
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 16482b741ea..6f7a6afdca8 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>  #endif
>>     ))))
>>  
>> +#if GIMPLE
>> +(for div (trunc_div exact_div)
>> + /* Simplify (t + M*N) / N -> t / N + M.  */
>> + (simplify
>> +  (div (plus:c @0 (mult:c @1 @2)) @2)
>> +  (if (INTEGRAL_TYPE_P (type)
>> +       && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
>> +  (plus (div @0 @2) @1)))
>> +
>> + /* Simplify (t - M*N) / N -> t / N - M.  */
>> + (simplify
>> +  (div (minus @0 (mult:c @1 @2)) @2)
>> +  (if (INTEGRAL_TYPE_P (type)
>> +       && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR,  type))
>> +  (minus (div @0 @2) @1)))
>> +
>> + /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N  */
>> + (simplify
>> +  (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
>> +  (with
>> +   { tree repaired_c = @1;
>> +     if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
>> +       repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
>
> What if @1 is 0x80000000?  Please consider re-doing this with
> wide_int from the start.
Thanks for the great catch here! This is a special value, while NEGATE
would not break it here.

OK, wide_int would be preferred.

Thanks again for your quick and helpful comments!

BR,
Jeff (Jiufu Guo)

>
>> +   }
>> +   (if (INTEGRAL_TYPE_P (type)
>> +	&& multiple_of_p (type, repaired_c, @2)
>> +	&& plus_no_ovf_and_keep_sign (@0, @1, type))
>> +     (with
>> +      { wide_int m;
>> +	wide_int c = wi::to_wide (@1);
>> +	wide_int n = wi::to_wide (@2);
>> +	wi::overflow_type ovf;
>> +	if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
>> +	  m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
>> +	else
>> +	  m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
>> +	gcc_assert (ovf == wi::OVF_NONE);
>> +      }
>> +   (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
>> +
>> +/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0.  */
>> +(simplify
>> + (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
>> + (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
>> +      && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
>> +      && plus_no_ovf_and_keep_sign (@0, @1, type))
>> +  (with
>> +   { wide_int m;
>> +     wide_int c = wi::to_wide (@1);
>> +     wide_int n = wi::to_wide (@2);
>> +     if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
>> +       m = -wi::rshift (-c, n, TYPE_SIGN (type));
>> +     else
>> +       m = wi::rshift (c, n, TYPE_SIGN (type));
>> +   }
>> + (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
>> +#endif
>> +
>>  (for op (negate abs)
>>   /* Simplify cos(-x) and cos(|x|) -> cos(x).  Similarly for cosh.  */
>>   (for coss (COS COSH)
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c b/gcc/testsuite/gcc.dg/pr108757-1.c
>> new file mode 100644
>> index 00000000000..7e7b60c756d
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
>> @@ -0,0 +1,18 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +#include <limits.h>
>> +#define N 5
>> +#define M 3
>> +#define GAP 0
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" } } *
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c b/gcc/testsuite/gcc.dg/pr108757-2.c
>> new file mode 100644
>> index 00000000000..2a9ad234e68
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
>> @@ -0,0 +1,19 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
>> +
>> +#include <limits.h>
>> +#define N 4
>> +#define M 3
>> +#define GAP 2
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
>> +
>> diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
>> new file mode 100644
>> index 00000000000..9dfa527f533
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757.h
>> @@ -0,0 +1,244 @@
>> +#define NOINLINE __attribute__ ((noinline))
>> +UINT NOINLINE
>> +opt_u1 (UINT x)
>> +{
>> +  if (x < (M * N) - GAP)
>> +    return 0;
>> +  UINT a = x - (M * N);
>> +  UINT b = a / N;
>> +  return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u2 (UINT x)
>> +{
>> +  if (x > (UMAX - (M * N) + GAP))
>> +    return 0;
>> +  UINT a = x + (M * N);
>> +  UINT b = a / N;
>> +  return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s1 (INT x)
>> +{
>> +  if (x < (M * N) - GAP)
>> +    return 0;
>> +  INT a = x - (M * N);
>> +  INT b = a / N;
>> +  return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s2 (INT x)
>> +{
>> +  if (x < IMIN + (M * N) - GAP || x > 0)
>> +    return 0;
>> +  INT a = x - (M * N);
>> +  INT b = a / N;
>> +  return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s3 (INT x)
>> +{
>> +  if (x < (M * N) - GAP)
>> +    return 0;
>> +  INT a = x - (M * N);
>> +  INT b = a / -N;
>> +  return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s4 (INT x)
>> +{
>> +  if (x < IMIN + (M * N) - GAP || x > 0)
>> +    return 0;
>> +  INT a = x - (M * N);
>> +  INT b = a / -N;
>> +  return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s5 (INT x)
>> +{
>> +  if (x > (-M * N) + GAP)
>> +    return 0;
>> +  INT a = x - (-M * N);
>> +  INT b = a / N;
>> +  return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s6 (INT x)
>> +{
>> +  if (x > IMAX - (M * N) + GAP || x < 0)
>> +    return 0;
>> +  INT a = x - (-M * N);
>> +  INT b = a / N;
>> +  return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s7 (INT x)
>> +{
>> +  if (x > (M * -N) + GAP)
>> +    return 0;
>> +  INT a = x - (M * -N);
>> +  INT b = a / -N;
>> +  return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s8 (INT x)
>> +{
>> +  if (x > IMAX - (M * N) + GAP || x < 0)
>> +    return 0;
>> +  INT a = x - (M * -N);
>> +  INT b = a / -N;
>> +  return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u3 (UINT x)
>> +{
>> +  if (x < (M << N) - GAP)
>> +    return 0;
>> +  UINT a = x - (M << N);
>> +  UINT b = a >> N;
>> +  return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u4 (UINT x)
>> +{
>> +  if (x > (UMAX - (M << N)) + GAP)
>> +    return 0;
>> +  UINT a = x + (M << N);
>> +  UINT b = a >> N;
>> +  return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s9 (INT x)
>> +{
>> +  if (x < (M << N) - GAP)
>> +    return 0;
>> +  INT a = x - (M << N);
>> +  INT b = a >> N;
>> +  return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s10 (INT x)
>> +{
>> +  if (x < IMIN + (M << N) - GAP || x > 0)
>> +    return 0;
>> +  INT a = x - (M << N);
>> +  INT b = a >> N;
>> +  return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s11 (INT x)
>> +{
>> +  if (x > (-M << N) + GAP)
>> +    return 0;
>> +  INT a = x - (-M << N);
>> +  INT b = a >> N;
>> +  return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s12 (INT x)
>> +{
>> +  if (x > IMAX - (M << N) + GAP || x < 0)
>> +    return 0;
>> +  INT a = x - (-M << N);
>> +  INT b = a >> N;
>> +  return b + -M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u5 (UINT x, UINT n, UINT m)
>> +{
>> +  if (n > N || m > M)
>> +    return 0;
>> +  if (x < (M*N) - GAP)
>> +    return 0;
>> +  UINT a = x - (m * n);
>> +  UINT b = a / n;
>> +  return b + m;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u6 (UINT x, UINT n, UINT m)
>> +{
>> +  if (n > N || m > M)
>> +    return 0;
>> +  if (x > (UMAX - M*N) + GAP)
>> +    return 0;
>> +  UINT a = x + (m * n);
>> +  UINT b = a / n;
>> +  return b - m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s13 (INT x, INT n, INT m)
>> +{
>> +  if (n > N || m > M || n < 0 || m < 0)
>> +    return 0;
>> +  if (x < (M*N) - GAP)
>> +    return 0;
>> +  INT a = x - (m * n);
>> +  INT b = a / n;
>> +  return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s14 (INT x, INT n, INT m)
>> +{
>> +  if (n > N || m > M || n < 0 || m < 0)
>> +    return 0;
>> +  if (x > -M*N + GAP)
>> +    return 0;
>> +  INT a = x + (m * n);
>> +  INT b = a / n;
>> +  return b - m;
>> +}
>> +
>> +INT
>> +opt_s15 (INT x, INT n, INT m)
>> +{
>> +  if (n > 0 || m > 0 || n < -N || m < -M)
>> +    return 0;
>> +  if (x < (M*N) - GAP)
>> +    return 0;
>> +  INT a = x - (m * n);
>> +  INT b = a / n;
>> +  return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s16 (INT x, INT n, INT m)
>> +{
>> +  if (n > 0 || m > 0 || n < -N || m < -M)
>> +    return 0;
>> +  if (x < 0 || x > (IMAX - M*N) + GAP)
>> +    return 0;
>> +  INT a = x + (m * n);
>> +  INT b = a / n;
>> +  return b - m;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u7 (UINT x, UINT n, UINT m)
>> +{
>> +  if (n > N || m <= UMAX - M)
>> +    return 0;
>> +  if (x > UMAX - (M*N) + GAP)
>> +    return 0;
>> +  UINT a = x - (m * n);
>> +  UINT b = a / n;
>> +  return b + m;
>> +}
>> 

Re: [PATCH V2] Optimize '(X - N * M) / N' to 'X / N - M' if valid

[Segher Boessenkool]

Hi!

On Wed, Jun 07, 2023 at 04:21:11PM +0800, Jiufu Guo wrote:
> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
> wrap/overflow/underflow. So, it is valid that "X - N * M" does
> not cross zero and does not wrap/overflow/underflow.

Is it ever valid semi-generally when N does not divide X?

Say X=5, N=2, M=3.  Then the original expression evaluates to 0, but the
new one to -1.  Whenever one of the divisions rounds up and the other
rounds down you have this problem.


Segher

Re: [PATCH V2] Optimize '(X - N * M) / N' to 'X / N - M' if valid

[Jiufu Guo]

Hi,

Thanks for your comments!

Segher Boessenkool <segher@kernel.crashing.org> writes:

> Hi!
>
> On Wed, Jun 07, 2023 at 04:21:11PM +0800, Jiufu Guo wrote:
>> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
>> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
>> wrap/overflow/underflow. So, it is valid that "X - N * M" does
>> not cross zero and does not wrap/overflow/underflow.
>
> Is it ever valid semi-generally when N does not divide X?

It is valid only if there is no wrap/overflow/underflow, and the sign
of "X" and "X-N*M" are the same.  Under this condition, N,M and X can be
any value. 

>
> Say X=5, N=2, M=3.  Then the original expression evaluates to 0, but the
> new one to -1.  Whenever one of the divisions rounds up and the other
> rounds down you have this problem.
You are right.  Since '/' is always towards zero, so, 'X' and 'X-N*M'
should have the same sign bit.  Otherwise, one rounds up, the other
rounds down, then the transform is invalid.

BR,
Jeff (Jiufu Guo)
>
>
> Segher