public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid
@ 2023-06-28  7:16 Jiufu Guo
  2023-06-29  3:06 ` Jiufu Guo
  0 siblings, 1 reply; 4+ messages in thread
From: Jiufu Guo @ 2023-06-28  7:16 UTC (permalink / raw)
  To: gcc-patches
  Cc: rguenther, jeffreyalaw, richard.sandiford, segher, dje.gcc,
	linkw, bergner, guojiufu

Hi,

Integer expression "(X - N * M) / N" can be optimized to "X / N - M" if
there is no wrap/overflow/underflow and "X - N * M" has the same sign
with "X".

Compare with the previous version:
https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620896.html
This version changes:
1. Remove the behavior to convert 'm' to '-m' for unsigned variable.
   This kind of case is rare, and it makes the code ambiguous.
2. Use the 'capture' expression and avoid building new expressions.
3. Add APIs like get_range and nonpositive/nonnegative.
4. Refactor patterns in match.pd and function names and signatures.

While some APIs are still in gimple-fold.cc/h.  Tried to add them
to other files, but did not find a better place.
Thanks for comments/suggestions!

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

BR,
Jeff (Jiufu Guo)


	PR tree-optimization/108757

gcc/ChangeLog:

	* gimple-fold.cc (mult_without_overflow_p): New function.
	(plus_without_overflow_p): New function.
	(minus_without_overflow_p): New function.
	(same_sign_p): New function.
	* gimple-fold.h (mult_without_overflow_p): New declare.
	(plus_without_overflow_p): New declare.
	(minus_without_overflow_p): New declare.
	(same_sign_p): New declare.
	* match.pd ((X - N * M) / N): New pattern.
	((X + N * M) / N): New pattern.
	((X + C) div_rshift N): New pattern.
	* value-query.h (get_range): New function.
	* value-range.cc (irange::nonnegative_p): New function.
	(irange::nonpositive_p): New function.
	* value-range.h (irange::nonnegative_p): New declare.
	(irange::nonpositive_p): New declare.

gcc/testsuite/ChangeLog:

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

---
 gcc/gimple-fold.cc                | 132 +++++++++++++++++
 gcc/gimple-fold.h                 |   4 +
 gcc/match.pd                      |  54 +++++++
 gcc/value-query.h                 |  10 ++
 gcc/value-range.cc                |  12 ++
 gcc/value-range.h                 |   2 +
 gcc/testsuite/gcc.dg/pr108757-1.c |  18 +++
 gcc/testsuite/gcc.dg/pr108757-2.c |  19 +++
 gcc/testsuite/gcc.dg/pr108757.h   | 233 ++++++++++++++++++++++++++++++
 9 files changed, 484 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
 create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
 create mode 100644 gcc/testsuite/gcc.dg/pr108757.h

diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
index 581575b65ec..c0703b45c4b 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -9349,3 +9349,135 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
       return false;
     }
 }
+
+/* Return true if "X * Y" may be overflow on integer TYPE.  */
+
+bool
+mult_without_overflow_p (tree x, tree y, tree type)
+{
+  gcc_assert (INTEGRAL_TYPE_P (type));
+
+  if (TYPE_OVERFLOW_UNDEFINED (type))
+    return true;
+
+  value_range vr0;
+  value_range vr1;
+  if (!(get_range (vr0, x) && get_range (vr1, y)))
+    return false;
+
+  wi::overflow_type ovf;
+  signop sgn = TYPE_SIGN (type);
+  wide_int wmax0 = vr0.upper_bound ();
+  wide_int wmax1 = vr1.upper_bound ();
+  wi::mul (wmax0, wmax1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  if (TYPE_UNSIGNED (type))
+    return true;
+
+  wide_int wmin0 = vr0.lower_bound ();
+  wide_int wmin1 = vr1.lower_bound ();
+  wi::mul (wmin0, wmin1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  wi::mul (wmin0, wmax1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  wi::mul (wmax0, wmin1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  return true;
+}
+
+/* Return true if "X + Y" may be overflow on integer TYPE.  */
+
+bool
+plus_without_overflow_p (tree x, tree y, tree type)
+{
+  gcc_assert (INTEGRAL_TYPE_P (type));
+
+  if (TYPE_OVERFLOW_UNDEFINED (type))
+    return true;
+
+  value_range vr0;
+  value_range vr1;
+  if (!(get_range (vr0, x) && get_range (vr1, y)))
+    return false;
+
+  wi::overflow_type ovf;
+  signop sgn = TYPE_SIGN (type);
+  wide_int wmax0 = vr0.upper_bound ();
+  wide_int wmax1 = vr1.upper_bound ();
+  wi::add (wmax0, wmax1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  if (TYPE_UNSIGNED (type))
+    return true;
+
+  wide_int wmin0 = vr0.lower_bound ();
+  wide_int wmin1 = vr1.lower_bound ();
+  wi::add (wmin0, wmin1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  return true;
+}
+
+/* Return true if "X - Y" may be overflow on integer TYPE.  */
+
+bool
+minus_without_overflow_p (tree x, tree y, tree type)
+{
+  gcc_assert (INTEGRAL_TYPE_P (type));
+
+  if (TYPE_OVERFLOW_UNDEFINED (type))
+    return true;
+
+  value_range vr0;
+  value_range vr1;
+  if (!(get_range (vr0, x) && get_range (vr1, y)))
+    return false;
+
+  wi::overflow_type ovf;
+  signop sgn = TYPE_SIGN (type);
+  wide_int wmin0 = vr0.lower_bound ();
+  wide_int wmax1 = vr1.upper_bound ();
+  wi::sub (wmin0, wmax1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  if (TYPE_UNSIGNED (type))
+    return true;
+
+  wide_int wmax0 = vr0.upper_bound ();
+  wide_int wmin1 = vr1.lower_bound ();
+  wi::sub (wmax0, wmin1, sgn, &ovf);
+  if (ovf != wi::OVF_NONE)
+    return false;
+
+  return true;
+}
+
+/* Return true if "X" and "Y" have the same sign or zero.  */
+
+bool
+same_sign_p (tree x, tree y, tree type)
+{
+  gcc_assert (INTEGRAL_TYPE_P (type));
+
+  if (TYPE_UNSIGNED (type))
+    return true;
+
+  value_range vr0;
+  value_range vr1;
+  if (!(get_range (vr0, x) && get_range (vr1, y)))
+    return false;
+
+  return (vr0.nonnegative_p () && vr1.nonnegative_p ())
+	 || (vr0.nonpositive_p () && vr1.nonpositive_p ());
+}
diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
index 2fd58db9a2e..76c3fe15559 100644
--- a/gcc/gimple-fold.h
+++ b/gcc/gimple-fold.h
@@ -64,6 +64,10 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
 extern void replace_call_with_value (gimple_stmt_iterator *, tree);
 extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
 extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
+extern bool mult_without_overflow_p (tree, tree, tree);
+extern bool plus_without_overflow_p (tree, tree, tree);
+extern bool minus_without_overflow_p (tree, tree, tree);
+extern bool same_sign_p (tree, tree, tree);
 
 /* gimple_build, functionally matching fold_buildN, outputs stmts
    int the provided sequence, matching and simplifying them on-the-fly.
diff --git a/gcc/match.pd b/gcc/match.pd
index 16482b741ea..ca1defd6692 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -942,6 +942,60 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 #endif
    ))))
 
+#if GIMPLE
+(for div (trunc_div exact_div)
+ /* Simplify (t + M*N) / N -> t / N + M.  */
+ (simplify
+  (div (plus:c@4 @0 (mult:c@3 @1 @2)) @2)
+  (if (INTEGRAL_TYPE_P (type)
+       && mult_without_overflow_p (@1, @2, type)
+       && plus_without_overflow_p (@0, @3, type)
+       && same_sign_p (@0, @4, type))
+  (plus (div @0 @2) @1)))
+
+ /* Simplify (t - M*N) / N -> t / N - M.  */
+ (simplify
+  (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
+  (if (INTEGRAL_TYPE_P (type)
+       && mult_without_overflow_p (@1, @2, type)
+       && minus_without_overflow_p (@0, @3, type)
+       && same_sign_p (@0, @4, type))
+  (minus (div @0 @2) @1))))
+
+/* Simplify
+   (t + C) / N -> t / N + C / N where C is multiple of N.
+   (t + C) >> N -> t >> N + C>>N if low N bits of C is 0.  */
+(for op (trunc_div exact_div rshift)
+ (simplify
+  (op (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2)
+   (with
+    {
+      wide_int c = wi::to_wide (@1);
+      wide_int n = wi::to_wide (@2);
+      bool neg_c = TYPE_UNSIGNED (type) && c.sign_mask () < 0;
+      c = neg_c ? -c : c;
+      bool ok = INTEGRAL_TYPE_P (type);
+      if (ok)
+	ok = code == RSHIFT_EXPR ? wi::ctz (c) >= n.to_shwi ()
+				 : wi::multiple_of_p (c, n, TYPE_SIGN (type));
+      if (ok)
+	ok = neg_c
+	       ? minus_without_overflow_p (@0, wide_int_to_tree (type, c), type)
+	       : plus_without_overflow_p (@0, @1, type);
+      if (ok)
+	ok = same_sign_p (@0, @3, type);
+    }
+   (if (ok)
+   (with
+    {
+      wide_int m;
+      m = op == RSHIFT_EXPR ? wi::rshift (c, n, TYPE_SIGN (type))
+			    : wi::div_trunc (c, n, TYPE_SIGN (type));
+      m = neg_c ? -m : m;
+    }
+   (plus (op @0 @2) { wide_int_to_tree(type, m); }))))))
+#endif
+
 (for op (negate abs)
  /* Simplify cos(-x) and cos(|x|) -> cos(x).  Similarly for cosh.  */
  (for coss (COS COSH)
diff --git a/gcc/value-query.h b/gcc/value-query.h
index d10c3eac1e2..2c4b9819d5a 100644
--- a/gcc/value-query.h
+++ b/gcc/value-query.h
@@ -137,6 +137,16 @@ get_range_query (const struct function *fun)
   return (fun && fun->x_range_query) ? fun->x_range_query : &global_ranges;
 }
 
+/* Return true if there is range for "X" expression at "S" statement,
+   and the range is not varying and not undefined.   */
+
+inline bool
+get_range (vrange &r, tree x, gimple *s = NULL)
+{
+  return get_range_query (cfun)->range_of_expr (r, x, s) && !r.varying_p ()
+	 && !r.undefined_p ();
+}
+
 // Query the global range of NAME in function F.  Default to cfun.
 extern void gimple_range_global (vrange &v, tree name,
 				 struct function *f = cfun);
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 707b1f15fd4..7ab9f56aec3 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -287,6 +287,18 @@ add_vrange (const vrange &v, inchash::hash &hstate,
 
 } //namespace inchash
 
+bool
+irange::nonnegative_p () const
+{
+  return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
+}
+
+bool
+irange::nonpositive_p () const
+{
+  return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
+}
+
 bool
 irange::supports_type_p (const_tree type) const
 {
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 2b4ebabe7c8..4dad4666a32 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -145,6 +145,8 @@ public:
   virtual bool singleton_p (tree *result = NULL) const override;
   bool singleton_p (wide_int &) const;
   bool contains_p (const wide_int &) const;
+  bool nonnegative_p () const;
+  bool nonpositive_p () const;
 
   // In-place operators.
   virtual bool union_ (const vrange &) override;
diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c b/gcc/testsuite/gcc.dg/pr108757-1.c
new file mode 100644
index 00000000000..7908f4bdcb8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757-1.c
@@ -0,0 +1,18 @@
+/* PR tree-optimization/108757 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#include <limits.h>
+#define N 5
+#define M 3
+#define GAP 0
+typedef unsigned int UINT;
+typedef int INT;
+#define UMAX UINT_MAX
+#define IMAX INT_MAX
+#define IMIN INT_MIN
+#include "pr108757.h"
+
+/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" } } *
+/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c b/gcc/testsuite/gcc.dg/pr108757-2.c
new file mode 100644
index 00000000000..82bebd09944
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757-2.c
@@ -0,0 +1,19 @@
+/* PR tree-optimization/108757 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
+
+#include <limits.h>
+#define N 4
+#define M 3
+#define GAP 2
+typedef unsigned int UINT;
+typedef int INT;
+#define UMAX UINT_MAX
+#define IMAX INT_MAX
+#define IMIN INT_MIN
+#include "pr108757.h"
+
+/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
+
diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
new file mode 100644
index 00000000000..5550199c1ef
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr108757.h
@@ -0,0 +1,233 @@
+#define NOINLINE __attribute__ ((noinline))
+UINT NOINLINE
+opt_u1 (UINT x)
+{
+  if (x < (M * N) - GAP)
+    return 0;
+  UINT a = x - (M * N);
+  UINT b = a / N;
+  return b + M;
+}
+
+UINT NOINLINE
+opt_u2 (UINT x)
+{
+  if (x > (UMAX - (M * N) + GAP))
+    return 0;
+  UINT a = x + (M * N);
+  UINT b = a / N;
+  return b - M;
+}
+
+INT NOINLINE
+opt_s1 (INT x)
+{
+  if (x < (M * N) - GAP)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s2 (INT x)
+{
+  if (x < IMIN + (M * N) - GAP || x > 0)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s3 (INT x)
+{
+  if (x < (M * N) - GAP)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / -N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s4 (INT x)
+{
+  if (x < IMIN + (M * N) - GAP || x > 0)
+    return 0;
+  INT a = x - (M * N);
+  INT b = a / -N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s5 (INT x)
+{
+  if (x > (-M * N) + GAP)
+    return 0;
+  INT a = x - (-M * N);
+  INT b = a / N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s6 (INT x)
+{
+  if (x > IMAX - (M * N) + GAP || x < 0)
+    return 0;
+  INT a = x - (-M * N);
+  INT b = a / N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s7 (INT x)
+{
+  if (x > (M * -N) + GAP)
+    return 0;
+  INT a = x - (M * -N);
+  INT b = a / -N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s8 (INT x)
+{
+  if (x > IMAX - (M * N) + GAP || x < 0)
+    return 0;
+  INT a = x - (M * -N);
+  INT b = a / -N;
+  return b + M;
+}
+
+UINT NOINLINE
+opt_u3 (UINT x)
+{
+  if (x < (M << N) - GAP)
+    return 0;
+  UINT a = x - (M << N);
+  UINT b = a >> N;
+  return b + M;
+}
+
+UINT NOINLINE
+opt_u4 (UINT x)
+{
+  if (x > (UMAX - (M << N)) + GAP)
+    return 0;
+  UINT a = x + (M << N);
+  UINT b = a >> N;
+  return b - M;
+}
+
+INT NOINLINE
+opt_s9 (INT x)
+{
+  if (x < (M << N) - GAP)
+    return 0;
+  INT a = x - (M << N);
+  INT b = a >> N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s10 (INT x)
+{
+  if (x < IMIN + (M << N) - GAP || x > 0)
+    return 0;
+  INT a = x - (M << N);
+  INT b = a >> N;
+  return b + M;
+}
+
+INT NOINLINE
+opt_s11 (INT x)
+{
+  if (x > (-M << N) + GAP)
+    return 0;
+  INT a = x - (-M << N);
+  INT b = a >> N;
+  return b + -M;
+}
+
+INT NOINLINE
+opt_s12 (INT x)
+{
+  if (x > IMAX - (M << N) + GAP || x < 0)
+    return 0;
+  INT a = x - (-M << N);
+  INT b = a >> N;
+  return b + -M;
+}
+
+UINT NOINLINE
+opt_u5 (UINT x, UINT n, UINT m)
+{
+  if (n > N || m > M)
+    return 0;
+  if (x < (M*N) - GAP)
+    return 0;
+  UINT a = x - (m * n);
+  UINT b = a / n;
+  return b + m;
+}
+
+UINT NOINLINE
+opt_u6 (UINT x, UINT n, UINT m)
+{
+  if (n > N || m > M)
+    return 0;
+  if (x > (UMAX - M*N) + GAP)
+    return 0;
+  UINT a = x + (m * n);
+  UINT b = a / n;
+  return b - m;
+}
+
+INT NOINLINE
+opt_s13 (INT x, INT n, INT m)
+{
+  if (n > N || m > M || n < 0 || m < 0)
+    return 0;
+  if (x < (M*N) - GAP)
+    return 0;
+  INT a = x - (m * n);
+  INT b = a / n;
+  return b + m;
+}
+
+INT NOINLINE
+opt_s14 (INT x, INT n, INT m)
+{
+  if (n > N || m > M || n < 0 || m < 0)
+    return 0;
+  if (x > -M*N + GAP)
+    return 0;
+  INT a = x + (m * n);
+  INT b = a / n;
+  return b - m;
+}
+
+INT
+opt_s15 (INT x, INT n, INT m)
+{
+  if (n > 0 || m > 0 || n < -N || m < -M)
+    return 0;
+  if (x < (M*N) - GAP)
+    return 0;
+  INT a = x - (m * n);
+  INT b = a / n;
+  return b + m;
+}
+
+INT NOINLINE
+opt_s16 (INT x, INT n, INT m)
+{
+  if (n > 0 || m > 0 || n < -N || m < -M)
+    return 0;
+  if (x < 0 || x > (IMAX - M*N) + GAP)
+    return 0;
+  INT a = x + (m * n);
+  INT b = a / n;
+  return b - m;
+}
+
-- 
2.39.3


^ permalink raw reply	[flat|nested] 4+ messages in thread
end of thread, other threads:[~2023-07-05  5:52 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-06-28  7:16 [PATCH V3] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
2023-06-29  3:06 ` Jiufu Guo
2023-07-04 11:25   ` Richard Biener
2023-07-05  5:51     ` Jiufu Guo

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).