* [PATCH V5 1/2] Add overflow API for plus minus mult on range
@ 2023-07-18 14:05 Jiufu Guo
2023-07-18 14:05 ` [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
2023-08-03 2:18 ` [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
0 siblings, 2 replies; 9+ messages in thread
From: Jiufu Guo @ 2023-07-18 14:05 UTC (permalink / raw)
To: gcc-patches
Cc: amacleod, aldyh, rguenther, jeffreyalaw, richard.sandiford,
segher, dje.gcc, linkw, bergner, guojiufu
Hi,
As discussed in previous reviews, adding overflow APIs to range-op
would be useful. Those APIs could help to check if overflow happens
when operating between two 'range's, like: plus, minus, and mult.
Previous discussions are here:
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624701.html
Bootstrap & regtest pass on ppc64{,le} and x86_64.
Is this patch ok for trunk?
BR,
Jeff (Jiufu Guo)
gcc/ChangeLog:
* range-op-mixed.h (operator_plus::overflow_free_p): New declare.
(operator_minus::overflow_free_p): New declare.
(operator_mult::overflow_free_p): New declare.
* range-op.cc (range_op_handler::overflow_free_p): New function.
(range_operator::overflow_free_p): New default function.
(operator_plus::overflow_free_p): New function.
(operator_minus::overflow_free_p): New function.
(operator_mult::overflow_free_p): New function.
* range-op.h (range_op_handler::overflow_free_p): New declare.
(range_operator::overflow_free_p): New declare.
* 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/range-op-mixed.h | 11 ++++
gcc/range-op.cc | 124 +++++++++++++++++++++++++++++++++++++++++++
gcc/range-op.h | 5 ++
gcc/value-range.cc | 12 +++++
gcc/value-range.h | 2 +
5 files changed, 154 insertions(+)
diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h
index 6944742ecbc..42157ed9061 100644
--- a/gcc/range-op-mixed.h
+++ b/gcc/range-op-mixed.h
@@ -383,6 +383,10 @@ public:
relation_kind rel) const final override;
void update_bitmask (irange &r, const irange &lh,
const irange &rh) const final override;
+
+ virtual bool overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio = TRIO_VARYING) const;
+
private:
void wi_fold (irange &r, tree type, const wide_int &lh_lb,
const wide_int &lh_ub, const wide_int &rh_lb,
@@ -446,6 +450,10 @@ public:
relation_kind rel) const final override;
void update_bitmask (irange &r, const irange &lh,
const irange &rh) const final override;
+
+ virtual bool overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio = TRIO_VARYING) const;
+
private:
void wi_fold (irange &r, tree type, const wide_int &lh_lb,
const wide_int &lh_ub, const wide_int &rh_lb,
@@ -525,6 +533,9 @@ public:
const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub,
const REAL_VALUE_TYPE &rh_lb, const REAL_VALUE_TYPE &rh_ub,
relation_kind kind) const final override;
+ virtual bool overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio = TRIO_VARYING) const;
+
};
class operator_addr_expr : public range_operator
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index cb584314f4c..632b044331b 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -366,6 +366,22 @@ range_op_handler::op1_op2_relation (const vrange &lhs) const
}
}
+bool
+range_op_handler::overflow_free_p (const vrange &lh,
+ const vrange &rh,
+ relation_trio rel) const
+{
+ gcc_checking_assert (m_operator);
+ switch (dispatch_kind (lh, lh, rh))
+ {
+ case RO_III:
+ return m_operator->overflow_free_p(as_a <irange> (lh),
+ as_a <irange> (rh),
+ rel);
+ default:
+ return false;
+ }
+}
// Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP.
@@ -688,6 +704,13 @@ range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
return false;
}
+bool
+range_operator::overflow_free_p (const irange &, const irange &,
+ relation_trio) const
+{
+ return false;
+}
+
// Apply any known bitmask updates based on this operator.
void
@@ -4311,6 +4334,107 @@ range_op_table::initialize_integral_ops ()
}
+bool
+operator_plus::overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio) const
+{
+ if (lh.undefined_p () || rh.undefined_p ())
+ return false;
+
+ tree type = lh.type ();
+ if (TYPE_OVERFLOW_UNDEFINED (type))
+ return true;
+
+ wi::overflow_type ovf;
+ signop sgn = TYPE_SIGN (type);
+ wide_int wmax0 = lh.upper_bound ();
+ wide_int wmax1 = rh.upper_bound ();
+ wi::add (wmax0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ wide_int wmin0 = lh.lower_bound ();
+ wide_int wmin1 = rh.lower_bound ();
+ wi::add (wmin0, wmin1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+bool
+operator_minus::overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio) const
+{
+ if (lh.undefined_p () || rh.undefined_p ())
+ return false;
+
+ tree type = lh.type ();
+ if (TYPE_OVERFLOW_UNDEFINED (type))
+ return true;
+
+ wi::overflow_type ovf;
+ signop sgn = TYPE_SIGN (type);
+ wide_int wmin0 = lh.lower_bound ();
+ wide_int wmax1 = rh.upper_bound ();
+ wi::sub (wmin0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ wide_int wmax0 = lh.upper_bound ();
+ wide_int wmin1 = rh.lower_bound ();
+ wi::sub (wmax0, wmin1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+bool
+operator_mult::overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio) const
+{
+ if (lh.undefined_p () || rh.undefined_p ())
+ return false;
+
+ tree type = lh.type ();
+ if (TYPE_OVERFLOW_UNDEFINED (type))
+ return true;
+
+ wi::overflow_type ovf;
+ signop sgn = TYPE_SIGN (type);
+ wide_int wmax0 = lh.upper_bound ();
+ wide_int wmax1 = rh.upper_bound ();
+ wi::mul (wmax0, wmax1, sgn, &ovf);
+ if (ovf != wi::OVF_NONE)
+ return false;
+
+ if (TYPE_UNSIGNED (type))
+ return true;
+
+ wide_int wmin0 = lh.lower_bound ();
+ wide_int wmin1 = rh.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;
+}
+
#if CHECKING_P
#include "selftest.h"
diff --git a/gcc/range-op.h b/gcc/range-op.h
index af94c2756a7..db3b03f28a5 100644
--- a/gcc/range-op.h
+++ b/gcc/range-op.h
@@ -147,6 +147,9 @@ public:
virtual relation_kind op1_op2_relation (const irange &lhs) const;
virtual relation_kind op1_op2_relation (const frange &lhs) const;
+
+ virtual bool overflow_free_p (const irange &lh, const irange &rh,
+ relation_trio = TRIO_VARYING) const;
protected:
// Perform an integral operation between 2 sub-ranges and return it.
virtual void wi_fold (irange &r, tree type,
@@ -214,6 +217,8 @@ public:
const vrange &op2,
relation_kind = VREL_VARYING) const;
relation_kind op1_op2_relation (const vrange &lhs) const;
+ bool overflow_free_p (const vrange &lh, const vrange &rh,
+ relation_trio = TRIO_VARYING) const;
protected:
unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
const vrange& op2) const;
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 011bdbdeae6..5ae4e044194 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -313,6 +313,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 0170188201b..a12dea514e4 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -280,6 +280,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;
--
2.39.3
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-07-18 14:05 [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
@ 2023-07-18 14:05 ` Jiufu Guo
2023-08-07 2:45 ` guojiufu
2023-08-03 2:18 ` [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
1 sibling, 1 reply; 9+ messages in thread
From: Jiufu Guo @ 2023-07-18 14:05 UTC (permalink / raw)
To: gcc-patches
Cc: amacleod, aldyh, 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 the previous version:
https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
- APIs: overflow, nonnegative_p and nonpositive_p are moved close
to value range.
- Use above APIs in match.pd.
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:
* match.pd ((X - N * M) / N): New pattern.
((X + N * M) / N): New pattern.
((X + C) div_rshift 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/match.pd | 85 +++++++++++
gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
gcc/testsuite/gcc.dg/pr108757.h | 233 ++++++++++++++++++++++++++++++
4 files changed, 355 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/match.pd b/gcc/match.pd
index 8543f777a28..39dbb0567dc 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -942,6 +942,91 @@ 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)
+ (with {value_range vr0, vr1, vr2, vr3, vr4;}
+ (if (INTEGRAL_TYPE_P (type)
+ && get_range_query (cfun)->range_of_expr (vr1, @1)
+ && get_range_query (cfun)->range_of_expr (vr2, @2)
+ && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
+ && get_range_query (cfun)->range_of_expr (vr0, @0)
+ && get_range_query (cfun)->range_of_expr (vr3, @3)
+ && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
+ && get_range_query (cfun)->range_of_expr (vr4, @4)
+ && (TYPE_UNSIGNED (type)
+ || (vr0.nonnegative_p () && vr4.nonnegative_p ())
+ || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
+ (plus (div @0 @2) @1))))
+
+ /* Simplify (t - M*N) / N -> t / N - M. */
+ (simplify
+ (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
+ (with {value_range vr0, vr1, vr2, vr3, vr4;}
+ (if (INTEGRAL_TYPE_P (type)
+ && get_range_query (cfun)->range_of_expr (vr1, @1)
+ && get_range_query (cfun)->range_of_expr (vr2, @2)
+ && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
+ && get_range_query (cfun)->range_of_expr (vr0, @0)
+ && get_range_query (cfun)->range_of_expr (vr3, @3)
+ && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
+ && get_range_query (cfun)->range_of_expr (vr4, @4)
+ && (TYPE_UNSIGNED (type)
+ || (vr0.nonnegative_p () && vr4.nonnegative_p ())
+ || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
+ (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 is_rshift = op == RSHIFT_EXPR;
+ bool neg_c = false;
+ bool ok = false;
+ value_range vr0;
+ if (INTEGRAL_TYPE_P (type)
+ && get_range_query (cfun)->range_of_expr (vr0, @0))
+ {
+ ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
+ : wi::multiple_of_p (c, n, TYPE_SIGN (type));
+ value_range vr1, vr3;
+ ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1)
+ && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
+ && get_range_query (cfun)->range_of_expr (vr3, @3)
+ && (TYPE_UNSIGNED (type)
+ || (vr0.nonnegative_p () && vr3.nonnegative_p ())
+ || (vr0.nonpositive_p () && vr3.nonpositive_p ()));
+
+ /* Try check 'X + C' as 'X - -C' for unsigned. */
+ if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0)
+ {
+ neg_c = true;
+ c = -c;
+ ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
+ : wi::multiple_of_p (c, n, UNSIGNED);
+ ok = ok && wi::geu_p (vr0.lower_bound (), c);
+ }
+ }
+ }
+ (if (ok)
+ (with
+ {
+ wide_int m;
+ m = is_rshift ? 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/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] 9+ messages in thread
* Re: [PATCH V5 1/2] Add overflow API for plus minus mult on range
2023-07-18 14:05 [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
2023-07-18 14:05 ` [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
@ 2023-08-03 2:18 ` Jiufu Guo
2023-08-03 13:18 ` Andrew MacLeod
1 sibling, 1 reply; 9+ messages in thread
From: Jiufu Guo @ 2023-08-03 2:18 UTC (permalink / raw)
To: gcc-patches
Cc: amacleod, aldyh, rguenther, jeffreyalaw, richard.sandiford,
segher, dje.gcc, linkw, bergner
Hi,
I would like to have a ping on this patch.
BR,
Jeff (Jiufu Guo)
Jiufu Guo <guojiufu@linux.ibm.com> writes:
> Hi,
>
> As discussed in previous reviews, adding overflow APIs to range-op
> would be useful. Those APIs could help to check if overflow happens
> when operating between two 'range's, like: plus, minus, and mult.
>
> Previous discussions are here:
> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624701.html
>
> Bootstrap & regtest pass on ppc64{,le} and x86_64.
> Is this patch ok for trunk?
>
> BR,
> Jeff (Jiufu Guo)
>
> gcc/ChangeLog:
>
> * range-op-mixed.h (operator_plus::overflow_free_p): New declare.
> (operator_minus::overflow_free_p): New declare.
> (operator_mult::overflow_free_p): New declare.
> * range-op.cc (range_op_handler::overflow_free_p): New function.
> (range_operator::overflow_free_p): New default function.
> (operator_plus::overflow_free_p): New function.
> (operator_minus::overflow_free_p): New function.
> (operator_mult::overflow_free_p): New function.
> * range-op.h (range_op_handler::overflow_free_p): New declare.
> (range_operator::overflow_free_p): New declare.
> * 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/range-op-mixed.h | 11 ++++
> gcc/range-op.cc | 124 +++++++++++++++++++++++++++++++++++++++++++
> gcc/range-op.h | 5 ++
> gcc/value-range.cc | 12 +++++
> gcc/value-range.h | 2 +
> 5 files changed, 154 insertions(+)
>
> diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h
> index 6944742ecbc..42157ed9061 100644
> --- a/gcc/range-op-mixed.h
> +++ b/gcc/range-op-mixed.h
> @@ -383,6 +383,10 @@ public:
> relation_kind rel) const final override;
> void update_bitmask (irange &r, const irange &lh,
> const irange &rh) const final override;
> +
> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio = TRIO_VARYING) const;
> +
> private:
> void wi_fold (irange &r, tree type, const wide_int &lh_lb,
> const wide_int &lh_ub, const wide_int &rh_lb,
> @@ -446,6 +450,10 @@ public:
> relation_kind rel) const final override;
> void update_bitmask (irange &r, const irange &lh,
> const irange &rh) const final override;
> +
> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio = TRIO_VARYING) const;
> +
> private:
> void wi_fold (irange &r, tree type, const wide_int &lh_lb,
> const wide_int &lh_ub, const wide_int &rh_lb,
> @@ -525,6 +533,9 @@ public:
> const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub,
> const REAL_VALUE_TYPE &rh_lb, const REAL_VALUE_TYPE &rh_ub,
> relation_kind kind) const final override;
> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio = TRIO_VARYING) const;
> +
> };
>
> class operator_addr_expr : public range_operator
> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
> index cb584314f4c..632b044331b 100644
> --- a/gcc/range-op.cc
> +++ b/gcc/range-op.cc
> @@ -366,6 +366,22 @@ range_op_handler::op1_op2_relation (const vrange &lhs) const
> }
> }
>
> +bool
> +range_op_handler::overflow_free_p (const vrange &lh,
> + const vrange &rh,
> + relation_trio rel) const
> +{
> + gcc_checking_assert (m_operator);
> + switch (dispatch_kind (lh, lh, rh))
> + {
> + case RO_III:
> + return m_operator->overflow_free_p(as_a <irange> (lh),
> + as_a <irange> (rh),
> + rel);
> + default:
> + return false;
> + }
> +}
>
> // Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP.
>
> @@ -688,6 +704,13 @@ range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
> return false;
> }
>
> +bool
> +range_operator::overflow_free_p (const irange &, const irange &,
> + relation_trio) const
> +{
> + return false;
> +}
> +
> // Apply any known bitmask updates based on this operator.
>
> void
> @@ -4311,6 +4334,107 @@ range_op_table::initialize_integral_ops ()
>
> }
>
> +bool
> +operator_plus::overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio) const
> +{
> + if (lh.undefined_p () || rh.undefined_p ())
> + return false;
> +
> + tree type = lh.type ();
> + if (TYPE_OVERFLOW_UNDEFINED (type))
> + return true;
> +
> + wi::overflow_type ovf;
> + signop sgn = TYPE_SIGN (type);
> + wide_int wmax0 = lh.upper_bound ();
> + wide_int wmax1 = rh.upper_bound ();
> + wi::add (wmax0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + wide_int wmin0 = lh.lower_bound ();
> + wide_int wmin1 = rh.lower_bound ();
> + wi::add (wmin0, wmin1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +bool
> +operator_minus::overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio) const
> +{
> + if (lh.undefined_p () || rh.undefined_p ())
> + return false;
> +
> + tree type = lh.type ();
> + if (TYPE_OVERFLOW_UNDEFINED (type))
> + return true;
> +
> + wi::overflow_type ovf;
> + signop sgn = TYPE_SIGN (type);
> + wide_int wmin0 = lh.lower_bound ();
> + wide_int wmax1 = rh.upper_bound ();
> + wi::sub (wmin0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + wide_int wmax0 = lh.upper_bound ();
> + wide_int wmin1 = rh.lower_bound ();
> + wi::sub (wmax0, wmin1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +bool
> +operator_mult::overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio) const
> +{
> + if (lh.undefined_p () || rh.undefined_p ())
> + return false;
> +
> + tree type = lh.type ();
> + if (TYPE_OVERFLOW_UNDEFINED (type))
> + return true;
> +
> + wi::overflow_type ovf;
> + signop sgn = TYPE_SIGN (type);
> + wide_int wmax0 = lh.upper_bound ();
> + wide_int wmax1 = rh.upper_bound ();
> + wi::mul (wmax0, wmax1, sgn, &ovf);
> + if (ovf != wi::OVF_NONE)
> + return false;
> +
> + if (TYPE_UNSIGNED (type))
> + return true;
> +
> + wide_int wmin0 = lh.lower_bound ();
> + wide_int wmin1 = rh.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;
> +}
> +
> #if CHECKING_P
> #include "selftest.h"
>
> diff --git a/gcc/range-op.h b/gcc/range-op.h
> index af94c2756a7..db3b03f28a5 100644
> --- a/gcc/range-op.h
> +++ b/gcc/range-op.h
> @@ -147,6 +147,9 @@ public:
>
> virtual relation_kind op1_op2_relation (const irange &lhs) const;
> virtual relation_kind op1_op2_relation (const frange &lhs) const;
> +
> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
> + relation_trio = TRIO_VARYING) const;
> protected:
> // Perform an integral operation between 2 sub-ranges and return it.
> virtual void wi_fold (irange &r, tree type,
> @@ -214,6 +217,8 @@ public:
> const vrange &op2,
> relation_kind = VREL_VARYING) const;
> relation_kind op1_op2_relation (const vrange &lhs) const;
> + bool overflow_free_p (const vrange &lh, const vrange &rh,
> + relation_trio = TRIO_VARYING) const;
> protected:
> unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
> const vrange& op2) const;
> diff --git a/gcc/value-range.cc b/gcc/value-range.cc
> index 011bdbdeae6..5ae4e044194 100644
> --- a/gcc/value-range.cc
> +++ b/gcc/value-range.cc
> @@ -313,6 +313,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 0170188201b..a12dea514e4 100644
> --- a/gcc/value-range.h
> +++ b/gcc/value-range.h
> @@ -280,6 +280,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;
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH V5 1/2] Add overflow API for plus minus mult on range
2023-08-03 2:18 ` [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
@ 2023-08-03 13:18 ` Andrew MacLeod
2023-08-31 5:07 ` guojiufu
0 siblings, 1 reply; 9+ messages in thread
From: Andrew MacLeod @ 2023-08-03 13:18 UTC (permalink / raw)
To: Jiufu Guo, gcc-patches
Cc: aldyh, rguenther, jeffreyalaw, richard.sandiford, segher,
dje.gcc, linkw, bergner
This is OK.
On 8/2/23 22:18, Jiufu Guo wrote:
> Hi,
>
> I would like to have a ping on this patch.
>
> BR,
> Jeff (Jiufu Guo)
>
>
> Jiufu Guo <guojiufu@linux.ibm.com> writes:
>
>> Hi,
>>
>> As discussed in previous reviews, adding overflow APIs to range-op
>> would be useful. Those APIs could help to check if overflow happens
>> when operating between two 'range's, like: plus, minus, and mult.
>>
>> Previous discussions are here:
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624701.html
>>
>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>> Is this patch ok for trunk?
>>
>> BR,
>> Jeff (Jiufu Guo)
>>
>> gcc/ChangeLog:
>>
>> * range-op-mixed.h (operator_plus::overflow_free_p): New declare.
>> (operator_minus::overflow_free_p): New declare.
>> (operator_mult::overflow_free_p): New declare.
>> * range-op.cc (range_op_handler::overflow_free_p): New function.
>> (range_operator::overflow_free_p): New default function.
>> (operator_plus::overflow_free_p): New function.
>> (operator_minus::overflow_free_p): New function.
>> (operator_mult::overflow_free_p): New function.
>> * range-op.h (range_op_handler::overflow_free_p): New declare.
>> (range_operator::overflow_free_p): New declare.
>> * 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/range-op-mixed.h | 11 ++++
>> gcc/range-op.cc | 124 +++++++++++++++++++++++++++++++++++++++++++
>> gcc/range-op.h | 5 ++
>> gcc/value-range.cc | 12 +++++
>> gcc/value-range.h | 2 +
>> 5 files changed, 154 insertions(+)
>>
>> diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h
>> index 6944742ecbc..42157ed9061 100644
>> --- a/gcc/range-op-mixed.h
>> +++ b/gcc/range-op-mixed.h
>> @@ -383,6 +383,10 @@ public:
>> relation_kind rel) const final override;
>> void update_bitmask (irange &r, const irange &lh,
>> const irange &rh) const final override;
>> +
>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio = TRIO_VARYING) const;
>> +
>> private:
>> void wi_fold (irange &r, tree type, const wide_int &lh_lb,
>> const wide_int &lh_ub, const wide_int &rh_lb,
>> @@ -446,6 +450,10 @@ public:
>> relation_kind rel) const final override;
>> void update_bitmask (irange &r, const irange &lh,
>> const irange &rh) const final override;
>> +
>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio = TRIO_VARYING) const;
>> +
>> private:
>> void wi_fold (irange &r, tree type, const wide_int &lh_lb,
>> const wide_int &lh_ub, const wide_int &rh_lb,
>> @@ -525,6 +533,9 @@ public:
>> const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub,
>> const REAL_VALUE_TYPE &rh_lb, const REAL_VALUE_TYPE &rh_ub,
>> relation_kind kind) const final override;
>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio = TRIO_VARYING) const;
>> +
>> };
>>
>> class operator_addr_expr : public range_operator
>> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
>> index cb584314f4c..632b044331b 100644
>> --- a/gcc/range-op.cc
>> +++ b/gcc/range-op.cc
>> @@ -366,6 +366,22 @@ range_op_handler::op1_op2_relation (const vrange &lhs) const
>> }
>> }
>>
>> +bool
>> +range_op_handler::overflow_free_p (const vrange &lh,
>> + const vrange &rh,
>> + relation_trio rel) const
>> +{
>> + gcc_checking_assert (m_operator);
>> + switch (dispatch_kind (lh, lh, rh))
>> + {
>> + case RO_III:
>> + return m_operator->overflow_free_p(as_a <irange> (lh),
>> + as_a <irange> (rh),
>> + rel);
>> + default:
>> + return false;
>> + }
>> +}
>>
>> // Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP.
>>
>> @@ -688,6 +704,13 @@ range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
>> return false;
>> }
>>
>> +bool
>> +range_operator::overflow_free_p (const irange &, const irange &,
>> + relation_trio) const
>> +{
>> + return false;
>> +}
>> +
>> // Apply any known bitmask updates based on this operator.
>>
>> void
>> @@ -4311,6 +4334,107 @@ range_op_table::initialize_integral_ops ()
>>
>> }
>>
>> +bool
>> +operator_plus::overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio) const
>> +{
>> + if (lh.undefined_p () || rh.undefined_p ())
>> + return false;
>> +
>> + tree type = lh.type ();
>> + if (TYPE_OVERFLOW_UNDEFINED (type))
>> + return true;
>> +
>> + wi::overflow_type ovf;
>> + signop sgn = TYPE_SIGN (type);
>> + wide_int wmax0 = lh.upper_bound ();
>> + wide_int wmax1 = rh.upper_bound ();
>> + wi::add (wmax0, wmax1, sgn, &ovf);
>> + if (ovf != wi::OVF_NONE)
>> + return false;
>> +
>> + if (TYPE_UNSIGNED (type))
>> + return true;
>> +
>> + wide_int wmin0 = lh.lower_bound ();
>> + wide_int wmin1 = rh.lower_bound ();
>> + wi::add (wmin0, wmin1, sgn, &ovf);
>> + if (ovf != wi::OVF_NONE)
>> + return false;
>> +
>> + return true;
>> +}
>> +
>> +bool
>> +operator_minus::overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio) const
>> +{
>> + if (lh.undefined_p () || rh.undefined_p ())
>> + return false;
>> +
>> + tree type = lh.type ();
>> + if (TYPE_OVERFLOW_UNDEFINED (type))
>> + return true;
>> +
>> + wi::overflow_type ovf;
>> + signop sgn = TYPE_SIGN (type);
>> + wide_int wmin0 = lh.lower_bound ();
>> + wide_int wmax1 = rh.upper_bound ();
>> + wi::sub (wmin0, wmax1, sgn, &ovf);
>> + if (ovf != wi::OVF_NONE)
>> + return false;
>> +
>> + if (TYPE_UNSIGNED (type))
>> + return true;
>> +
>> + wide_int wmax0 = lh.upper_bound ();
>> + wide_int wmin1 = rh.lower_bound ();
>> + wi::sub (wmax0, wmin1, sgn, &ovf);
>> + if (ovf != wi::OVF_NONE)
>> + return false;
>> +
>> + return true;
>> +}
>> +
>> +bool
>> +operator_mult::overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio) const
>> +{
>> + if (lh.undefined_p () || rh.undefined_p ())
>> + return false;
>> +
>> + tree type = lh.type ();
>> + if (TYPE_OVERFLOW_UNDEFINED (type))
>> + return true;
>> +
>> + wi::overflow_type ovf;
>> + signop sgn = TYPE_SIGN (type);
>> + wide_int wmax0 = lh.upper_bound ();
>> + wide_int wmax1 = rh.upper_bound ();
>> + wi::mul (wmax0, wmax1, sgn, &ovf);
>> + if (ovf != wi::OVF_NONE)
>> + return false;
>> +
>> + if (TYPE_UNSIGNED (type))
>> + return true;
>> +
>> + wide_int wmin0 = lh.lower_bound ();
>> + wide_int wmin1 = rh.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;
>> +}
>> +
>> #if CHECKING_P
>> #include "selftest.h"
>>
>> diff --git a/gcc/range-op.h b/gcc/range-op.h
>> index af94c2756a7..db3b03f28a5 100644
>> --- a/gcc/range-op.h
>> +++ b/gcc/range-op.h
>> @@ -147,6 +147,9 @@ public:
>>
>> virtual relation_kind op1_op2_relation (const irange &lhs) const;
>> virtual relation_kind op1_op2_relation (const frange &lhs) const;
>> +
>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>> + relation_trio = TRIO_VARYING) const;
>> protected:
>> // Perform an integral operation between 2 sub-ranges and return it.
>> virtual void wi_fold (irange &r, tree type,
>> @@ -214,6 +217,8 @@ public:
>> const vrange &op2,
>> relation_kind = VREL_VARYING) const;
>> relation_kind op1_op2_relation (const vrange &lhs) const;
>> + bool overflow_free_p (const vrange &lh, const vrange &rh,
>> + relation_trio = TRIO_VARYING) const;
>> protected:
>> unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
>> const vrange& op2) const;
>> diff --git a/gcc/value-range.cc b/gcc/value-range.cc
>> index 011bdbdeae6..5ae4e044194 100644
>> --- a/gcc/value-range.cc
>> +++ b/gcc/value-range.cc
>> @@ -313,6 +313,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 0170188201b..a12dea514e4 100644
>> --- a/gcc/value-range.h
>> +++ b/gcc/value-range.h
>> @@ -280,6 +280,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;
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-07-18 14:05 ` [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
@ 2023-08-07 2:45 ` guojiufu
2023-08-23 2:04 ` Ping^^ " guojiufu
0 siblings, 1 reply; 9+ messages in thread
From: guojiufu @ 2023-08-07 2:45 UTC (permalink / raw)
To: gcc-patches, rguenther, jeffreyalaw, richard.sandiford
Cc: amacleod, aldyh, segher, dje.gcc, linkw, bergner
Hi,
Gentle ping...
On 2023-07-18 22:05, Jiufu Guo wrote:
> 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 the previous version:
> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
> - APIs: overflow, nonnegative_p and nonpositive_p are moved close
> to value range.
> - Use above APIs in match.pd.
>
> 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:
>
> * match.pd ((X - N * M) / N): New pattern.
> ((X + N * M) / N): New pattern.
> ((X + C) div_rshift 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/match.pd | 85 +++++++++++
> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
> gcc/testsuite/gcc.dg/pr108757.h | 233 ++++++++++++++++++++++++++++++
> 4 files changed, 355 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/match.pd b/gcc/match.pd
> index 8543f777a28..39dbb0567dc 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -942,6 +942,91 @@ 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)
> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
> + (if (INTEGRAL_TYPE_P (type)
> + && get_range_query (cfun)->range_of_expr (vr1, @1)
> + && get_range_query (cfun)->range_of_expr (vr2, @2)
> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
> + && get_range_query (cfun)->range_of_expr (vr0, @0)
> + && get_range_query (cfun)->range_of_expr (vr3, @3)
> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
> + && get_range_query (cfun)->range_of_expr (vr4, @4)
> + && (TYPE_UNSIGNED (type)
> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
> + (plus (div @0 @2) @1))))
> +
> + /* Simplify (t - M*N) / N -> t / N - M. */
> + (simplify
> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
> + (if (INTEGRAL_TYPE_P (type)
> + && get_range_query (cfun)->range_of_expr (vr1, @1)
> + && get_range_query (cfun)->range_of_expr (vr2, @2)
> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
> + && get_range_query (cfun)->range_of_expr (vr0, @0)
> + && get_range_query (cfun)->range_of_expr (vr3, @3)
> + && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
> + && get_range_query (cfun)->range_of_expr (vr4, @4)
> + && (TYPE_UNSIGNED (type)
> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
> + (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 is_rshift = op == RSHIFT_EXPR;
> + bool neg_c = false;
> + bool ok = false;
> + value_range vr0;
> + if (INTEGRAL_TYPE_P (type)
> + && get_range_query (cfun)->range_of_expr (vr0, @0))
> + {
> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
> + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
> + value_range vr1, vr3;
> + ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1)
> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
> + && get_range_query (cfun)->range_of_expr (vr3, @3)
> + && (TYPE_UNSIGNED (type)
> + || (vr0.nonnegative_p () && vr3.nonnegative_p ())
> + || (vr0.nonpositive_p () && vr3.nonpositive_p ()));
> +
> + /* Try check 'X + C' as 'X - -C' for unsigned. */
> + if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0)
> + {
> + neg_c = true;
> + c = -c;
> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
> + : wi::multiple_of_p (c, n, UNSIGNED);
> + ok = ok && wi::geu_p (vr0.lower_bound (), c);
> + }
> + }
> + }
> + (if (ok)
> + (with
> + {
> + wide_int m;
> + m = is_rshift ? 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/testsuite/gcc.dg/pr108757-1.c
> b/gcc/testsuite/gcc.dg/pr108757-1.c
> new file mode 100644
> index 00000000000..7908f4bdcb8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
> @@ -0,0 +1,18 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#include <limits.h>
> +#define N 5
> +#define M 3
> +#define GAP 0
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ "
> "optimized" } } *
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- "
> "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" }
> } */
> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c
> b/gcc/testsuite/gcc.dg/pr108757-2.c
> new file mode 100644
> index 00000000000..82bebd09944
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
> @@ -0,0 +1,19 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
> +
> +#include <limits.h>
> +#define N 4
> +#define M 3
> +#define GAP 2
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16
> "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3
> "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3
> "optimized" } } */
> +
> diff --git a/gcc/testsuite/gcc.dg/pr108757.h
> b/gcc/testsuite/gcc.dg/pr108757.h
> new file mode 100644
> index 00000000000..5550199c1ef
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757.h
> @@ -0,0 +1,233 @@
> +#define NOINLINE __attribute__ ((noinline))
> +UINT NOINLINE
> +opt_u1 (UINT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + UINT a = x - (M * N);
> + UINT b = a / N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u2 (UINT x)
> +{
> + if (x > (UMAX - (M * N) + GAP))
> + return 0;
> + UINT a = x + (M * N);
> + UINT b = a / N;
> + return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s1 (INT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s2 (INT x)
> +{
> + if (x < IMIN + (M * N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s3 (INT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / -N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s4 (INT x)
> +{
> + if (x < IMIN + (M * N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / -N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s5 (INT x)
> +{
> + if (x > (-M * N) + GAP)
> + return 0;
> + INT a = x - (-M * N);
> + INT b = a / N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s6 (INT x)
> +{
> + if (x > IMAX - (M * N) + GAP || x < 0)
> + return 0;
> + INT a = x - (-M * N);
> + INT b = a / N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s7 (INT x)
> +{
> + if (x > (M * -N) + GAP)
> + return 0;
> + INT a = x - (M * -N);
> + INT b = a / -N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s8 (INT x)
> +{
> + if (x > IMAX - (M * N) + GAP || x < 0)
> + return 0;
> + INT a = x - (M * -N);
> + INT b = a / -N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u3 (UINT x)
> +{
> + if (x < (M << N) - GAP)
> + return 0;
> + UINT a = x - (M << N);
> + UINT b = a >> N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u4 (UINT x)
> +{
> + if (x > (UMAX - (M << N)) + GAP)
> + return 0;
> + UINT a = x + (M << N);
> + UINT b = a >> N;
> + return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s9 (INT x)
> +{
> + if (x < (M << N) - GAP)
> + return 0;
> + INT a = x - (M << N);
> + INT b = a >> N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s10 (INT x)
> +{
> + if (x < IMIN + (M << N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M << N);
> + INT b = a >> N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s11 (INT x)
> +{
> + if (x > (-M << N) + GAP)
> + return 0;
> + INT a = x - (-M << N);
> + INT b = a >> N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s12 (INT x)
> +{
> + if (x > IMAX - (M << N) + GAP || x < 0)
> + return 0;
> + INT a = x - (-M << N);
> + INT b = a >> N;
> + return b + -M;
> +}
> +
> +UINT NOINLINE
> +opt_u5 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m > M)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + UINT a = x - (m * n);
> + UINT b = a / n;
> + return b + m;
> +}
> +
> +UINT NOINLINE
> +opt_u6 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m > M)
> + return 0;
> + if (x > (UMAX - M*N) + GAP)
> + return 0;
> + UINT a = x + (m * n);
> + UINT b = a / n;
> + return b - m;
> +}
> +
> +INT NOINLINE
> +opt_s13 (INT x, INT n, INT m)
> +{
> + if (n > N || m > M || n < 0 || m < 0)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + INT a = x - (m * n);
> + INT b = a / n;
> + return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s14 (INT x, INT n, INT m)
> +{
> + if (n > N || m > M || n < 0 || m < 0)
> + return 0;
> + if (x > -M*N + GAP)
> + return 0;
> + INT a = x + (m * n);
> + INT b = a / n;
> + return b - m;
> +}
> +
> +INT
> +opt_s15 (INT x, INT n, INT m)
> +{
> + if (n > 0 || m > 0 || n < -N || m < -M)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + INT a = x - (m * n);
> + INT b = a / n;
> + return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s16 (INT x, INT n, INT m)
> +{
> + if (n > 0 || m > 0 || n < -N || m < -M)
> + return 0;
> + if (x < 0 || x > (IMAX - M*N) + GAP)
> + return 0;
> + INT a = x + (m * n);
> + INT b = a / n;
> + return b - m;
> +}
> +
^ permalink raw reply [flat|nested] 9+ messages in thread
* Ping^^ [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-08-07 2:45 ` guojiufu
@ 2023-08-23 2:04 ` guojiufu
2023-08-28 13:14 ` Richard Biener
0 siblings, 1 reply; 9+ messages in thread
From: guojiufu @ 2023-08-23 2:04 UTC (permalink / raw)
To: rguenther, jeffreyalaw, richard.sandiford, guojiufu
Cc: gcc-patches, amacleod, aldyh, segher, dje.gcc, linkw, bergner
Hi,
I would like to have a gentle ping...
BR,
Jeff (Jiufu Guo)
On 2023-08-07 10:45, guojiufu via Gcc-patches wrote:
> Hi,
>
> Gentle ping...
>
> On 2023-07-18 22:05, Jiufu Guo wrote:
>> 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 the previous version:
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
>> - APIs: overflow, nonnegative_p and nonpositive_p are moved close
>> to value range.
>> - Use above APIs in match.pd.
>>
>> 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:
>>
>> * match.pd ((X - N * M) / N): New pattern.
>> ((X + N * M) / N): New pattern.
>> ((X + C) div_rshift 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/match.pd | 85 +++++++++++
>> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
>> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
>> gcc/testsuite/gcc.dg/pr108757.h | 233
>> ++++++++++++++++++++++++++++++
>> 4 files changed, 355 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/match.pd b/gcc/match.pd
>> index 8543f777a28..39dbb0567dc 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -942,6 +942,91 @@ 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)
>> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
>> + (if (INTEGRAL_TYPE_P (type)
>> + && get_range_query (cfun)->range_of_expr (vr1, @1)
>> + && get_range_query (cfun)->range_of_expr (vr2, @2)
>> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
>> + && get_range_query (cfun)->range_of_expr (vr0, @0)
>> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
>> + && get_range_query (cfun)->range_of_expr (vr4, @4)
>> + && (TYPE_UNSIGNED (type)
>> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
>> + (plus (div @0 @2) @1))))
>> +
>> + /* Simplify (t - M*N) / N -> t / N - M. */
>> + (simplify
>> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
>> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
>> + (if (INTEGRAL_TYPE_P (type)
>> + && get_range_query (cfun)->range_of_expr (vr1, @1)
>> + && get_range_query (cfun)->range_of_expr (vr2, @2)
>> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
>> + && get_range_query (cfun)->range_of_expr (vr0, @0)
>> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> + && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
>> + && get_range_query (cfun)->range_of_expr (vr4, @4)
>> + && (TYPE_UNSIGNED (type)
>> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
>> + (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 is_rshift = op == RSHIFT_EXPR;
>> + bool neg_c = false;
>> + bool ok = false;
>> + value_range vr0;
>> + if (INTEGRAL_TYPE_P (type)
>> + && get_range_query (cfun)->range_of_expr (vr0, @0))
>> + {
>> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
>> + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
>> + value_range vr1, vr3;
>> + ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1)
>> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
>> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> + && (TYPE_UNSIGNED (type)
>> + || (vr0.nonnegative_p () && vr3.nonnegative_p ())
>> + || (vr0.nonpositive_p () && vr3.nonpositive_p ()));
>> +
>> + /* Try check 'X + C' as 'X - -C' for unsigned. */
>> + if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0)
>> + {
>> + neg_c = true;
>> + c = -c;
>> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
>> + : wi::multiple_of_p (c, n, UNSIGNED);
>> + ok = ok && wi::geu_p (vr0.lower_bound (), c);
>> + }
>> + }
>> + }
>> + (if (ok)
>> + (with
>> + {
>> + wide_int m;
>> + m = is_rshift ? 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/testsuite/gcc.dg/pr108757-1.c
>> b/gcc/testsuite/gcc.dg/pr108757-1.c
>> new file mode 100644
>> index 00000000000..7908f4bdcb8
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
>> @@ -0,0 +1,18 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +#include <limits.h>
>> +#define N 5
>> +#define M 3
>> +#define GAP 0
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ "
>> "optimized" } } *
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- "
>> "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" }
>> } */
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c
>> b/gcc/testsuite/gcc.dg/pr108757-2.c
>> new file mode 100644
>> index 00000000000..82bebd09944
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
>> @@ -0,0 +1,19 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
>> +
>> +#include <limits.h>
>> +#define N 4
>> +#define M 3
>> +#define GAP 2
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16
>> "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3
>> "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3
>> "optimized" } } */
>> +
>> diff --git a/gcc/testsuite/gcc.dg/pr108757.h
>> b/gcc/testsuite/gcc.dg/pr108757.h
>> new file mode 100644
>> index 00000000000..5550199c1ef
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757.h
>> @@ -0,0 +1,233 @@
>> +#define NOINLINE __attribute__ ((noinline))
>> +UINT NOINLINE
>> +opt_u1 (UINT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + UINT a = x - (M * N);
>> + UINT b = a / N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u2 (UINT x)
>> +{
>> + if (x > (UMAX - (M * N) + GAP))
>> + return 0;
>> + UINT a = x + (M * N);
>> + UINT b = a / N;
>> + return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s1 (INT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s2 (INT x)
>> +{
>> + if (x < IMIN + (M * N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s3 (INT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / -N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s4 (INT x)
>> +{
>> + if (x < IMIN + (M * N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / -N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s5 (INT x)
>> +{
>> + if (x > (-M * N) + GAP)
>> + return 0;
>> + INT a = x - (-M * N);
>> + INT b = a / N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s6 (INT x)
>> +{
>> + if (x > IMAX - (M * N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (-M * N);
>> + INT b = a / N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s7 (INT x)
>> +{
>> + if (x > (M * -N) + GAP)
>> + return 0;
>> + INT a = x - (M * -N);
>> + INT b = a / -N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s8 (INT x)
>> +{
>> + if (x > IMAX - (M * N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (M * -N);
>> + INT b = a / -N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u3 (UINT x)
>> +{
>> + if (x < (M << N) - GAP)
>> + return 0;
>> + UINT a = x - (M << N);
>> + UINT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u4 (UINT x)
>> +{
>> + if (x > (UMAX - (M << N)) + GAP)
>> + return 0;
>> + UINT a = x + (M << N);
>> + UINT b = a >> N;
>> + return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s9 (INT x)
>> +{
>> + if (x < (M << N) - GAP)
>> + return 0;
>> + INT a = x - (M << N);
>> + INT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s10 (INT x)
>> +{
>> + if (x < IMIN + (M << N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M << N);
>> + INT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s11 (INT x)
>> +{
>> + if (x > (-M << N) + GAP)
>> + return 0;
>> + INT a = x - (-M << N);
>> + INT b = a >> N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s12 (INT x)
>> +{
>> + if (x > IMAX - (M << N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (-M << N);
>> + INT b = a >> N;
>> + return b + -M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u5 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m > M)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + UINT a = x - (m * n);
>> + UINT b = a / n;
>> + return b + m;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u6 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m > M)
>> + return 0;
>> + if (x > (UMAX - M*N) + GAP)
>> + return 0;
>> + UINT a = x + (m * n);
>> + UINT b = a / n;
>> + return b - m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s13 (INT x, INT n, INT m)
>> +{
>> + if (n > N || m > M || n < 0 || m < 0)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + INT a = x - (m * n);
>> + INT b = a / n;
>> + return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s14 (INT x, INT n, INT m)
>> +{
>> + if (n > N || m > M || n < 0 || m < 0)
>> + return 0;
>> + if (x > -M*N + GAP)
>> + return 0;
>> + INT a = x + (m * n);
>> + INT b = a / n;
>> + return b - m;
>> +}
>> +
>> +INT
>> +opt_s15 (INT x, INT n, INT m)
>> +{
>> + if (n > 0 || m > 0 || n < -N || m < -M)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + INT a = x - (m * n);
>> + INT b = a / n;
>> + return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s16 (INT x, INT n, INT m)
>> +{
>> + if (n > 0 || m > 0 || n < -N || m < -M)
>> + return 0;
>> + if (x < 0 || x > (IMAX - M*N) + GAP)
>> + return 0;
>> + INT a = x + (m * n);
>> + INT b = a / n;
>> + return b - m;
>> +}
>> +
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ping^^ [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-08-23 2:04 ` Ping^^ " guojiufu
@ 2023-08-28 13:14 ` Richard Biener
2023-08-29 7:25 ` Jiufu Guo
0 siblings, 1 reply; 9+ messages in thread
From: Richard Biener @ 2023-08-28 13:14 UTC (permalink / raw)
To: guojiufu
Cc: jeffreyalaw, richard.sandiford, gcc-patches, amacleod, aldyh,
segher, dje.gcc, linkw, bergner
On Wed, 23 Aug 2023, guojiufu wrote:
> Hi,
>
> I would like to have a gentle ping...
>
> BR,
> Jeff (Jiufu Guo)
>
> On 2023-08-07 10:45, guojiufu via Gcc-patches wrote:
> > Hi,
> >
> > Gentle ping...
> >
> > On 2023-07-18 22:05, Jiufu Guo wrote:
> >> 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 the previous version:
> >> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
> >> - APIs: overflow, nonnegative_p and nonpositive_p are moved close
> >> to value range.
> >> - Use above APIs in match.pd.
> >>
> >> 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:
> >>
> >> * match.pd ((X - N * M) / N): New pattern.
> >> ((X + N * M) / N): New pattern.
> >> ((X + C) div_rshift 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/match.pd | 85 +++++++++++
> >> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
> >> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
> >> gcc/testsuite/gcc.dg/pr108757.h | 233
> >> ++++++++++++++++++++++++++++++
> >> 4 files changed, 355 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/match.pd b/gcc/match.pd
> >> index 8543f777a28..39dbb0567dc 100644
> >> --- a/gcc/match.pd
> >> +++ b/gcc/match.pd
> >> @@ -942,6 +942,91 @@ 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)
The :c on the plus isn't necessary?
> >> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
> >> + (if (INTEGRAL_TYPE_P (type)
> >> + && get_range_query (cfun)->range_of_expr (vr1, @1)
> >> + && get_range_query (cfun)->range_of_expr (vr2, @2)
> >> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
the multiplication doesn't overflow
> >> + && get_range_query (cfun)->range_of_expr (vr0, @0)
> >> + && get_range_query (cfun)->range_of_expr (vr3, @3)
> >> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
the add doesn't overflow
> >> + && get_range_query (cfun)->range_of_expr (vr4, @4)
> >> + && (TYPE_UNSIGNED (type)
> >> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
> >> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
I don't know what this checks - the add result and the add first
argument are not of opposite sign. Huh. At least this part
needs an explaining comment.
Sorry if we hashed this out before, but you can see I forgot
and it's not obvious.
> >> + (plus (div @0 @2) @1))))
> >> +
> >> + /* Simplify (t - M*N) / N -> t / N - M. */
> >> + (simplify
> >> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
> >> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
> >> + (if (INTEGRAL_TYPE_P (type)
> >> + && get_range_query (cfun)->range_of_expr (vr1, @1)
> >> + && get_range_query (cfun)->range_of_expr (vr2, @2)
> >> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
> >> + && get_range_query (cfun)->range_of_expr (vr0, @0)
> >> + && get_range_query (cfun)->range_of_expr (vr3, @3)
> >> + && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
> >> + && get_range_query (cfun)->range_of_expr (vr4, @4)
> >> + && (TYPE_UNSIGNED (type)
> >> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
> >> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
> >> + (minus (div @0 @2) @1)))))
looks like exactly the same - if you use a
(for addsub (plus minus)
you should be able to do range_op_handler (addsub).
> >> +
> >> +/* 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 is_rshift = op == RSHIFT_EXPR;
> >> + bool neg_c = false;
> >> + bool ok = false;
> >> + value_range vr0;
> >> + if (INTEGRAL_TYPE_P (type)
> >> + && get_range_query (cfun)->range_of_expr (vr0, @0))
> >> + {
> >> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
> >> + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
> >> + value_range vr1, vr3;
> >> + ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1)
> >> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
> >> + && get_range_query (cfun)->range_of_expr (vr3, @3)
> >> + && (TYPE_UNSIGNED (type)
> >> + || (vr0.nonnegative_p () && vr3.nonnegative_p ())
> >> + || (vr0.nonpositive_p () && vr3.nonpositive_p ()));
> >> +
> >> + /* Try check 'X + C' as 'X - -C' for unsigned. */
> >> + if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0)
> >> + {
> >> + neg_c = true;
> >> + c = -c;
> >> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
> >> + : wi::multiple_of_p (c, n, UNSIGNED);
> >> + ok = ok && wi::geu_p (vr0.lower_bound (), c);
> >> + }
> >> + }
> >> + }
> >> + (if (ok)
> >> + (with
> >> + {
> >> + wide_int m;
> >> + m = is_rshift ? wi::rshift (c, n, TYPE_SIGN (type))
> >> + : wi::div_trunc (c, n, TYPE_SIGN (type));
> >> + m = neg_c ? -m : m;
> >> + }
why doesn't this look as nice as the other pattern? I'd put
(if (wi::multiple_of_p ( ....))
for @1 and @2 outside, then the rest should follow the pattern
of the above patterns?
Thanks,
Richard.
> >> + (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/testsuite/gcc.dg/pr108757-1.c
> >> b/gcc/testsuite/gcc.dg/pr108757-1.c
> >> new file mode 100644
> >> index 00000000000..7908f4bdcb8
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
> >> @@ -0,0 +1,18 @@
> >> +/* PR tree-optimization/108757 */
> >> +/* { dg-do compile } */
> >> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> >> +
> >> +#include <limits.h>
> >> +#define N 5
> >> +#define M 3
> >> +#define GAP 0
> >> +typedef unsigned int UINT;
> >> +typedef int INT;
> >> +#define UMAX UINT_MAX
> >> +#define IMAX INT_MAX
> >> +#define IMIN INT_MIN
> >> +#include "pr108757.h"
> >> +
> >> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ "
> >> "optimized" } } *
> >> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- "
> >> "optimized" } } */
> >> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
> >> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c
> >> b/gcc/testsuite/gcc.dg/pr108757-2.c
> >> new file mode 100644
> >> index 00000000000..82bebd09944
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
> >> @@ -0,0 +1,19 @@
> >> +/* PR tree-optimization/108757 */
> >> +/* { dg-do compile } */
> >> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
> >> +
> >> +#include <limits.h>
> >> +#define N 4
> >> +#define M 3
> >> +#define GAP 2
> >> +typedef unsigned int UINT;
> >> +typedef int INT;
> >> +#define UMAX UINT_MAX
> >> +#define IMAX INT_MAX
> >> +#define IMIN INT_MIN
> >> +#include "pr108757.h"
> >> +
> >> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16
> >> "optimized" } } */
> >> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3
> >> "optimized" } } */
> >> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3
> >> "optimized" } } */
> >> +
> >> diff --git a/gcc/testsuite/gcc.dg/pr108757.h
> >> b/gcc/testsuite/gcc.dg/pr108757.h
> >> new file mode 100644
> >> index 00000000000..5550199c1ef
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/pr108757.h
> >> @@ -0,0 +1,233 @@
> >> +#define NOINLINE __attribute__ ((noinline))
> >> +UINT NOINLINE
> >> +opt_u1 (UINT x)
> >> +{
> >> + if (x < (M * N) - GAP)
> >> + return 0;
> >> + UINT a = x - (M * N);
> >> + UINT b = a / N;
> >> + return b + M;
> >> +}
> >> +
> >> +UINT NOINLINE
> >> +opt_u2 (UINT x)
> >> +{
> >> + if (x > (UMAX - (M * N) + GAP))
> >> + return 0;
> >> + UINT a = x + (M * N);
> >> + UINT b = a / N;
> >> + return b - M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s1 (INT x)
> >> +{
> >> + if (x < (M * N) - GAP)
> >> + return 0;
> >> + INT a = x - (M * N);
> >> + INT b = a / N;
> >> + return b + M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s2 (INT x)
> >> +{
> >> + if (x < IMIN + (M * N) - GAP || x > 0)
> >> + return 0;
> >> + INT a = x - (M * N);
> >> + INT b = a / N;
> >> + return b + M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s3 (INT x)
> >> +{
> >> + if (x < (M * N) - GAP)
> >> + return 0;
> >> + INT a = x - (M * N);
> >> + INT b = a / -N;
> >> + return b + -M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s4 (INT x)
> >> +{
> >> + if (x < IMIN + (M * N) - GAP || x > 0)
> >> + return 0;
> >> + INT a = x - (M * N);
> >> + INT b = a / -N;
> >> + return b + -M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s5 (INT x)
> >> +{
> >> + if (x > (-M * N) + GAP)
> >> + return 0;
> >> + INT a = x - (-M * N);
> >> + INT b = a / N;
> >> + return b + -M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s6 (INT x)
> >> +{
> >> + if (x > IMAX - (M * N) + GAP || x < 0)
> >> + return 0;
> >> + INT a = x - (-M * N);
> >> + INT b = a / N;
> >> + return b + -M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s7 (INT x)
> >> +{
> >> + if (x > (M * -N) + GAP)
> >> + return 0;
> >> + INT a = x - (M * -N);
> >> + INT b = a / -N;
> >> + return b + M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s8 (INT x)
> >> +{
> >> + if (x > IMAX - (M * N) + GAP || x < 0)
> >> + return 0;
> >> + INT a = x - (M * -N);
> >> + INT b = a / -N;
> >> + return b + M;
> >> +}
> >> +
> >> +UINT NOINLINE
> >> +opt_u3 (UINT x)
> >> +{
> >> + if (x < (M << N) - GAP)
> >> + return 0;
> >> + UINT a = x - (M << N);
> >> + UINT b = a >> N;
> >> + return b + M;
> >> +}
> >> +
> >> +UINT NOINLINE
> >> +opt_u4 (UINT x)
> >> +{
> >> + if (x > (UMAX - (M << N)) + GAP)
> >> + return 0;
> >> + UINT a = x + (M << N);
> >> + UINT b = a >> N;
> >> + return b - M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s9 (INT x)
> >> +{
> >> + if (x < (M << N) - GAP)
> >> + return 0;
> >> + INT a = x - (M << N);
> >> + INT b = a >> N;
> >> + return b + M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s10 (INT x)
> >> +{
> >> + if (x < IMIN + (M << N) - GAP || x > 0)
> >> + return 0;
> >> + INT a = x - (M << N);
> >> + INT b = a >> N;
> >> + return b + M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s11 (INT x)
> >> +{
> >> + if (x > (-M << N) + GAP)
> >> + return 0;
> >> + INT a = x - (-M << N);
> >> + INT b = a >> N;
> >> + return b + -M;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s12 (INT x)
> >> +{
> >> + if (x > IMAX - (M << N) + GAP || x < 0)
> >> + return 0;
> >> + INT a = x - (-M << N);
> >> + INT b = a >> N;
> >> + return b + -M;
> >> +}
> >> +
> >> +UINT NOINLINE
> >> +opt_u5 (UINT x, UINT n, UINT m)
> >> +{
> >> + if (n > N || m > M)
> >> + return 0;
> >> + if (x < (M*N) - GAP)
> >> + return 0;
> >> + UINT a = x - (m * n);
> >> + UINT b = a / n;
> >> + return b + m;
> >> +}
> >> +
> >> +UINT NOINLINE
> >> +opt_u6 (UINT x, UINT n, UINT m)
> >> +{
> >> + if (n > N || m > M)
> >> + return 0;
> >> + if (x > (UMAX - M*N) + GAP)
> >> + return 0;
> >> + UINT a = x + (m * n);
> >> + UINT b = a / n;
> >> + return b - m;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s13 (INT x, INT n, INT m)
> >> +{
> >> + if (n > N || m > M || n < 0 || m < 0)
> >> + return 0;
> >> + if (x < (M*N) - GAP)
> >> + return 0;
> >> + INT a = x - (m * n);
> >> + INT b = a / n;
> >> + return b + m;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s14 (INT x, INT n, INT m)
> >> +{
> >> + if (n > N || m > M || n < 0 || m < 0)
> >> + return 0;
> >> + if (x > -M*N + GAP)
> >> + return 0;
> >> + INT a = x + (m * n);
> >> + INT b = a / n;
> >> + return b - m;
> >> +}
> >> +
> >> +INT
> >> +opt_s15 (INT x, INT n, INT m)
> >> +{
> >> + if (n > 0 || m > 0 || n < -N || m < -M)
> >> + return 0;
> >> + if (x < (M*N) - GAP)
> >> + return 0;
> >> + INT a = x - (m * n);
> >> + INT b = a / n;
> >> + return b + m;
> >> +}
> >> +
> >> +INT NOINLINE
> >> +opt_s16 (INT x, INT n, INT m)
> >> +{
> >> + if (n > 0 || m > 0 || n < -N || m < -M)
> >> + return 0;
> >> + if (x < 0 || x > (IMAX - M*N) + GAP)
> >> + return 0;
> >> + INT a = x + (m * n);
> >> + INT b = a / n;
> >> + return b - m;
> >> +}
> >> +
>
--
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ping^^ [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
2023-08-28 13:14 ` Richard Biener
@ 2023-08-29 7:25 ` Jiufu Guo
0 siblings, 0 replies; 9+ messages in thread
From: Jiufu Guo @ 2023-08-29 7:25 UTC (permalink / raw)
To: Richard Biener
Cc: jeffreyalaw, richard.sandiford, gcc-patches, amacleod, aldyh,
segher, dje.gcc, linkw, bergner
Hi Richard,
Thanks a lot for your review!
Richard Biener <rguenther@suse.de> writes:
> On Wed, 23 Aug 2023, guojiufu wrote:
>
>> Hi,
>>
>> I would like to have a gentle ping...
>>
>> BR,
>> Jeff (Jiufu Guo)
>>
>> On 2023-08-07 10:45, guojiufu via Gcc-patches wrote:
>> > Hi,
>> >
>> > Gentle ping...
>> >
>> > On 2023-07-18 22:05, Jiufu Guo wrote:
>> >> 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 the previous version:
>> >> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
>> >> - APIs: overflow, nonnegative_p and nonpositive_p are moved close
>> >> to value range.
>> >> - Use above APIs in match.pd.
>> >>
>> >> 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:
>> >>
>> >> * match.pd ((X - N * M) / N): New pattern.
>> >> ((X + N * M) / N): New pattern.
>> >> ((X + C) div_rshift 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/match.pd | 85 +++++++++++
>> >> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
>> >> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
>> >> gcc/testsuite/gcc.dg/pr108757.h | 233
>> >> ++++++++++++++++++++++++++++++
>> >> 4 files changed, 355 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/match.pd b/gcc/match.pd
>> >> index 8543f777a28..39dbb0567dc 100644
>> >> --- a/gcc/match.pd
>> >> +++ b/gcc/match.pd
>> >> @@ -942,6 +942,91 @@ 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)
>
> The :c on the plus isn't necessary?
":c" would be needed. Because when the pattern is matched
in gimple passes(e.g. vrp), the insn sequences would looks
like:
"%_6 = N * M; %_7 = %_6 + t": "%_6" is leading "t".
Without ":c", the pattern may need write as:
(plus@4 (mult:c@3 @1 @2) $0).
>
>> >> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
>> >> + (if (INTEGRAL_TYPE_P (type)
>> >> + && get_range_query (cfun)->range_of_expr (vr1, @1)
>> >> + && get_range_query (cfun)->range_of_expr (vr2, @2)
>> >> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
>
> the multiplication doesn't overflow
Yes, this is checking no overflow on mult.
>
>> >> + && get_range_query (cfun)->range_of_expr (vr0, @0)
>> >> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> >> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
>
> the add doesn't overflow
Yes, this is checking no overflow on add.
>
>> >> + && get_range_query (cfun)->range_of_expr (vr4, @4)
>> >> + && (TYPE_UNSIGNED (type)
>> >> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> >> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
>
> I don't know what this checks - the add result and the add first
> argument are not of opposite sign. Huh. At least this part
> needs an explaining comment.
Right, "X-N*M" is not with opposite sign of "X".
Because it is trunc_div in this pattern. Which cutting towards
zero, if "X-N*M" changes the sign of "X", then "(X-N*M)/N" and
"X/N" cut mod to different direction.
A comment is needed, I will add.
>
> Sorry if we hashed this out before, but you can see I forgot
> and it's not obvious.
>
>> >> + (plus (div @0 @2) @1))))
>> >> +
>> >> + /* Simplify (t - M*N) / N -> t / N - M. */
>> >> + (simplify
>> >> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2)
>> >> + (with {value_range vr0, vr1, vr2, vr3, vr4;}
>> >> + (if (INTEGRAL_TYPE_P (type)
>> >> + && get_range_query (cfun)->range_of_expr (vr1, @1)
>> >> + && get_range_query (cfun)->range_of_expr (vr2, @2)
>> >> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2)
>> >> + && get_range_query (cfun)->range_of_expr (vr0, @0)
>> >> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> >> + && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
>> >> + && get_range_query (cfun)->range_of_expr (vr4, @4)
>> >> + && (TYPE_UNSIGNED (type)
>> >> + || (vr0.nonnegative_p () && vr4.nonnegative_p ())
>> >> + || (vr0.nonpositive_p () && vr4.nonpositive_p ())))
>> >> + (minus (div @0 @2) @1)))))
>
> looks like exactly the same - if you use a
>
> (for addsub (plus minus)
I also tried to use this. But fail, the reason is similar
with adding ":c" for "plus".
For "plus", the insn sequences would like:
"%_6 = N * M; %_7 = %_6 + t": "%_6" is leading "t".
(plus@4 (mult:c@3 @1 @2) $0).
But for "sub", the insn sequence would be:
"%_6 = N * M; %_7 = t - %_6": "t" is leading "%6".
(sub@4 $0 (mult:c@3 @1 @2)).
So, I fail to combine these two patterns into one.
>
> you should be able to do range_op_handler (addsub).
>
>> >> +
>> >> +/* 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 is_rshift = op == RSHIFT_EXPR;
>> >> + bool neg_c = false;
>> >> + bool ok = false;
>> >> + value_range vr0;
>> >> + if (INTEGRAL_TYPE_P (type)
>> >> + && get_range_query (cfun)->range_of_expr (vr0, @0))
>> >> + {
>> >> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
>> >> + : wi::multiple_of_p (c, n, TYPE_SIGN (type));
>> >> + value_range vr1, vr3;
>> >> + ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1)
>> >> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1)
>> >> + && get_range_query (cfun)->range_of_expr (vr3, @3)
>> >> + && (TYPE_UNSIGNED (type)
>> >> + || (vr0.nonnegative_p () && vr3.nonnegative_p ())
>> >> + || (vr0.nonpositive_p () && vr3.nonpositive_p ()));
>> >> +
>> >> + /* Try check 'X + C' as 'X - -C' for unsigned. */
>> >> + if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0)
>> >> + {
>> >> + neg_c = true;
>> >> + c = -c;
>> >> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi ()
>> >> + : wi::multiple_of_p (c, n, UNSIGNED);
>> >> + ok = ok && wi::geu_p (vr0.lower_bound (), c);
>> >> + }
>> >> + }
>> >> + }
>> >> + (if (ok)
>> >> + (with
>> >> + {
>> >> + wide_int m;
>> >> + m = is_rshift ? wi::rshift (c, n, TYPE_SIGN (type))
>> >> + : wi::div_trunc (c, n, TYPE_SIGN (type));
>> >> + m = neg_c ? -m : m;
>> >> + }
>
> why doesn't this look as nice as the other pattern? I'd put
>
> (if (wi::multiple_of_p ( ....))
>
> for @1 and @2 outside, then the rest should follow the pattern
> of the above patterns?
Thanks, I would try to refactor the pattern.
BR,
Jeff (Jiufu Guo)
>
> Thanks,
> Richard.
>
>> >> + (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/testsuite/gcc.dg/pr108757-1.c
>> >> b/gcc/testsuite/gcc.dg/pr108757-1.c
>> >> new file mode 100644
>> >> index 00000000000..7908f4bdcb8
>> >> --- /dev/null
>> >> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
>> >> @@ -0,0 +1,18 @@
>> >> +/* PR tree-optimization/108757 */
>> >> +/* { dg-do compile } */
>> >> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> >> +
>> >> +#include <limits.h>
>> >> +#define N 5
>> >> +#define M 3
>> >> +#define GAP 0
>> >> +typedef unsigned int UINT;
>> >> +typedef int INT;
>> >> +#define UMAX UINT_MAX
>> >> +#define IMAX INT_MAX
>> >> +#define IMIN INT_MIN
>> >> +#include "pr108757.h"
>> >> +
>> >> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ "
>> >> "optimized" } } *
>> >> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- "
>> >> "optimized" } } */
>> >> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
>> >> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c
>> >> b/gcc/testsuite/gcc.dg/pr108757-2.c
>> >> new file mode 100644
>> >> index 00000000000..82bebd09944
>> >> --- /dev/null
>> >> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
>> >> @@ -0,0 +1,19 @@
>> >> +/* PR tree-optimization/108757 */
>> >> +/* { dg-do compile } */
>> >> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
>> >> +
>> >> +#include <limits.h>
>> >> +#define N 4
>> >> +#define M 3
>> >> +#define GAP 2
>> >> +typedef unsigned int UINT;
>> >> +typedef int INT;
>> >> +#define UMAX UINT_MAX
>> >> +#define IMAX INT_MAX
>> >> +#define IMIN INT_MIN
>> >> +#include "pr108757.h"
>> >> +
>> >> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16
>> >> "optimized" } } */
>> >> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3
>> >> "optimized" } } */
>> >> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3
>> >> "optimized" } } */
>> >> +
>> >> diff --git a/gcc/testsuite/gcc.dg/pr108757.h
>> >> b/gcc/testsuite/gcc.dg/pr108757.h
>> >> new file mode 100644
>> >> index 00000000000..5550199c1ef
>> >> --- /dev/null
>> >> +++ b/gcc/testsuite/gcc.dg/pr108757.h
>> >> @@ -0,0 +1,233 @@
>> >> +#define NOINLINE __attribute__ ((noinline))
>> >> +UINT NOINLINE
>> >> +opt_u1 (UINT x)
>> >> +{
>> >> + if (x < (M * N) - GAP)
>> >> + return 0;
>> >> + UINT a = x - (M * N);
>> >> + UINT b = a / N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +UINT NOINLINE
>> >> +opt_u2 (UINT x)
>> >> +{
>> >> + if (x > (UMAX - (M * N) + GAP))
>> >> + return 0;
>> >> + UINT a = x + (M * N);
>> >> + UINT b = a / N;
>> >> + return b - M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s1 (INT x)
>> >> +{
>> >> + if (x < (M * N) - GAP)
>> >> + return 0;
>> >> + INT a = x - (M * N);
>> >> + INT b = a / N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s2 (INT x)
>> >> +{
>> >> + if (x < IMIN + (M * N) - GAP || x > 0)
>> >> + return 0;
>> >> + INT a = x - (M * N);
>> >> + INT b = a / N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s3 (INT x)
>> >> +{
>> >> + if (x < (M * N) - GAP)
>> >> + return 0;
>> >> + INT a = x - (M * N);
>> >> + INT b = a / -N;
>> >> + return b + -M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s4 (INT x)
>> >> +{
>> >> + if (x < IMIN + (M * N) - GAP || x > 0)
>> >> + return 0;
>> >> + INT a = x - (M * N);
>> >> + INT b = a / -N;
>> >> + return b + -M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s5 (INT x)
>> >> +{
>> >> + if (x > (-M * N) + GAP)
>> >> + return 0;
>> >> + INT a = x - (-M * N);
>> >> + INT b = a / N;
>> >> + return b + -M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s6 (INT x)
>> >> +{
>> >> + if (x > IMAX - (M * N) + GAP || x < 0)
>> >> + return 0;
>> >> + INT a = x - (-M * N);
>> >> + INT b = a / N;
>> >> + return b + -M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s7 (INT x)
>> >> +{
>> >> + if (x > (M * -N) + GAP)
>> >> + return 0;
>> >> + INT a = x - (M * -N);
>> >> + INT b = a / -N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s8 (INT x)
>> >> +{
>> >> + if (x > IMAX - (M * N) + GAP || x < 0)
>> >> + return 0;
>> >> + INT a = x - (M * -N);
>> >> + INT b = a / -N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +UINT NOINLINE
>> >> +opt_u3 (UINT x)
>> >> +{
>> >> + if (x < (M << N) - GAP)
>> >> + return 0;
>> >> + UINT a = x - (M << N);
>> >> + UINT b = a >> N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +UINT NOINLINE
>> >> +opt_u4 (UINT x)
>> >> +{
>> >> + if (x > (UMAX - (M << N)) + GAP)
>> >> + return 0;
>> >> + UINT a = x + (M << N);
>> >> + UINT b = a >> N;
>> >> + return b - M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s9 (INT x)
>> >> +{
>> >> + if (x < (M << N) - GAP)
>> >> + return 0;
>> >> + INT a = x - (M << N);
>> >> + INT b = a >> N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s10 (INT x)
>> >> +{
>> >> + if (x < IMIN + (M << N) - GAP || x > 0)
>> >> + return 0;
>> >> + INT a = x - (M << N);
>> >> + INT b = a >> N;
>> >> + return b + M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s11 (INT x)
>> >> +{
>> >> + if (x > (-M << N) + GAP)
>> >> + return 0;
>> >> + INT a = x - (-M << N);
>> >> + INT b = a >> N;
>> >> + return b + -M;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s12 (INT x)
>> >> +{
>> >> + if (x > IMAX - (M << N) + GAP || x < 0)
>> >> + return 0;
>> >> + INT a = x - (-M << N);
>> >> + INT b = a >> N;
>> >> + return b + -M;
>> >> +}
>> >> +
>> >> +UINT NOINLINE
>> >> +opt_u5 (UINT x, UINT n, UINT m)
>> >> +{
>> >> + if (n > N || m > M)
>> >> + return 0;
>> >> + if (x < (M*N) - GAP)
>> >> + return 0;
>> >> + UINT a = x - (m * n);
>> >> + UINT b = a / n;
>> >> + return b + m;
>> >> +}
>> >> +
>> >> +UINT NOINLINE
>> >> +opt_u6 (UINT x, UINT n, UINT m)
>> >> +{
>> >> + if (n > N || m > M)
>> >> + return 0;
>> >> + if (x > (UMAX - M*N) + GAP)
>> >> + return 0;
>> >> + UINT a = x + (m * n);
>> >> + UINT b = a / n;
>> >> + return b - m;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s13 (INT x, INT n, INT m)
>> >> +{
>> >> + if (n > N || m > M || n < 0 || m < 0)
>> >> + return 0;
>> >> + if (x < (M*N) - GAP)
>> >> + return 0;
>> >> + INT a = x - (m * n);
>> >> + INT b = a / n;
>> >> + return b + m;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s14 (INT x, INT n, INT m)
>> >> +{
>> >> + if (n > N || m > M || n < 0 || m < 0)
>> >> + return 0;
>> >> + if (x > -M*N + GAP)
>> >> + return 0;
>> >> + INT a = x + (m * n);
>> >> + INT b = a / n;
>> >> + return b - m;
>> >> +}
>> >> +
>> >> +INT
>> >> +opt_s15 (INT x, INT n, INT m)
>> >> +{
>> >> + if (n > 0 || m > 0 || n < -N || m < -M)
>> >> + return 0;
>> >> + if (x < (M*N) - GAP)
>> >> + return 0;
>> >> + INT a = x - (m * n);
>> >> + INT b = a / n;
>> >> + return b + m;
>> >> +}
>> >> +
>> >> +INT NOINLINE
>> >> +opt_s16 (INT x, INT n, INT m)
>> >> +{
>> >> + if (n > 0 || m > 0 || n < -N || m < -M)
>> >> + return 0;
>> >> + if (x < 0 || x > (IMAX - M*N) + GAP)
>> >> + return 0;
>> >> + INT a = x + (m * n);
>> >> + INT b = a / n;
>> >> + return b - m;
>> >> +}
>> >> +
>>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH V5 1/2] Add overflow API for plus minus mult on range
2023-08-03 13:18 ` Andrew MacLeod
@ 2023-08-31 5:07 ` guojiufu
0 siblings, 0 replies; 9+ messages in thread
From: guojiufu @ 2023-08-31 5:07 UTC (permalink / raw)
To: Andrew MacLeod
Cc: gcc-patches, aldyh, rguenther, jeffreyalaw, richard.sandiford,
segher, dje.gcc, linkw, bergner
On 2023-08-03 21:18, Andrew MacLeod wrote:
> This is OK.
>
Thanks a lot! Committed via r14-3582.
BR,
Jeff (Jiufu Guo)
>
> On 8/2/23 22:18, Jiufu Guo wrote:
>> Hi,
>>
>> I would like to have a ping on this patch.
>>
>> BR,
>> Jeff (Jiufu Guo)
>>
>>
>> Jiufu Guo <guojiufu@linux.ibm.com> writes:
>>
>>> Hi,
>>>
>>> As discussed in previous reviews, adding overflow APIs to range-op
>>> would be useful. Those APIs could help to check if overflow happens
>>> when operating between two 'range's, like: plus, minus, and mult.
>>>
>>> Previous discussions are here:
>>> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html
>>> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624701.html
>>>
>>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>>> Is this patch ok for trunk?
>>>
>>> BR,
>>> Jeff (Jiufu Guo)
>>>
>>> gcc/ChangeLog:
>>>
>>> * range-op-mixed.h (operator_plus::overflow_free_p): New declare.
>>> (operator_minus::overflow_free_p): New declare.
>>> (operator_mult::overflow_free_p): New declare.
>>> * range-op.cc (range_op_handler::overflow_free_p): New function.
>>> (range_operator::overflow_free_p): New default function.
>>> (operator_plus::overflow_free_p): New function.
>>> (operator_minus::overflow_free_p): New function.
>>> (operator_mult::overflow_free_p): New function.
>>> * range-op.h (range_op_handler::overflow_free_p): New declare.
>>> (range_operator::overflow_free_p): New declare.
>>> * 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/range-op-mixed.h | 11 ++++
>>> gcc/range-op.cc | 124
>>> +++++++++++++++++++++++++++++++++++++++++++
>>> gcc/range-op.h | 5 ++
>>> gcc/value-range.cc | 12 +++++
>>> gcc/value-range.h | 2 +
>>> 5 files changed, 154 insertions(+)
>>>
>>> diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h
>>> index 6944742ecbc..42157ed9061 100644
>>> --- a/gcc/range-op-mixed.h
>>> +++ b/gcc/range-op-mixed.h
>>> @@ -383,6 +383,10 @@ public:
>>> relation_kind rel) const final override;
>>> void update_bitmask (irange &r, const irange &lh,
>>> const irange &rh) const final override;
>>> +
>>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio = TRIO_VARYING) const;
>>> +
>>> private:
>>> void wi_fold (irange &r, tree type, const wide_int &lh_lb,
>>> const wide_int &lh_ub, const wide_int &rh_lb,
>>> @@ -446,6 +450,10 @@ public:
>>> relation_kind rel) const final override;
>>> void update_bitmask (irange &r, const irange &lh,
>>> const irange &rh) const final override;
>>> +
>>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio = TRIO_VARYING) const;
>>> +
>>> private:
>>> void wi_fold (irange &r, tree type, const wide_int &lh_lb,
>>> const wide_int &lh_ub, const wide_int &rh_lb,
>>> @@ -525,6 +533,9 @@ public:
>>> const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub,
>>> const REAL_VALUE_TYPE &rh_lb, const REAL_VALUE_TYPE &rh_ub,
>>> relation_kind kind) const final override;
>>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio = TRIO_VARYING) const;
>>> +
>>> };
>>> class operator_addr_expr : public range_operator
>>> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
>>> index cb584314f4c..632b044331b 100644
>>> --- a/gcc/range-op.cc
>>> +++ b/gcc/range-op.cc
>>> @@ -366,6 +366,22 @@ range_op_handler::op1_op2_relation (const vrange
>>> &lhs) const
>>> }
>>> }
>>> +bool
>>> +range_op_handler::overflow_free_p (const vrange &lh,
>>> + const vrange &rh,
>>> + relation_trio rel) const
>>> +{
>>> + gcc_checking_assert (m_operator);
>>> + switch (dispatch_kind (lh, lh, rh))
>>> + {
>>> + case RO_III:
>>> + return m_operator->overflow_free_p(as_a <irange> (lh),
>>> + as_a <irange> (rh),
>>> + rel);
>>> + default:
>>> + return false;
>>> + }
>>> +}
>>> // Convert irange bitmasks into a VALUE MASK pair suitable for
>>> calling CCP.
>>> @@ -688,6 +704,13 @@ range_operator::op1_op2_relation_effect
>>> (irange &lhs_range ATTRIBUTE_UNUSED,
>>> return false;
>>> }
>>> +bool
>>> +range_operator::overflow_free_p (const irange &, const irange &,
>>> + relation_trio) const
>>> +{
>>> + return false;
>>> +}
>>> +
>>> // Apply any known bitmask updates based on this operator.
>>> void
>>> @@ -4311,6 +4334,107 @@ range_op_table::initialize_integral_ops ()
>>> }
>>> +bool
>>> +operator_plus::overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio) const
>>> +{
>>> + if (lh.undefined_p () || rh.undefined_p ())
>>> + return false;
>>> +
>>> + tree type = lh.type ();
>>> + if (TYPE_OVERFLOW_UNDEFINED (type))
>>> + return true;
>>> +
>>> + wi::overflow_type ovf;
>>> + signop sgn = TYPE_SIGN (type);
>>> + wide_int wmax0 = lh.upper_bound ();
>>> + wide_int wmax1 = rh.upper_bound ();
>>> + wi::add (wmax0, wmax1, sgn, &ovf);
>>> + if (ovf != wi::OVF_NONE)
>>> + return false;
>>> +
>>> + if (TYPE_UNSIGNED (type))
>>> + return true;
>>> +
>>> + wide_int wmin0 = lh.lower_bound ();
>>> + wide_int wmin1 = rh.lower_bound ();
>>> + wi::add (wmin0, wmin1, sgn, &ovf);
>>> + if (ovf != wi::OVF_NONE)
>>> + return false;
>>> +
>>> + return true;
>>> +}
>>> +
>>> +bool
>>> +operator_minus::overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio) const
>>> +{
>>> + if (lh.undefined_p () || rh.undefined_p ())
>>> + return false;
>>> +
>>> + tree type = lh.type ();
>>> + if (TYPE_OVERFLOW_UNDEFINED (type))
>>> + return true;
>>> +
>>> + wi::overflow_type ovf;
>>> + signop sgn = TYPE_SIGN (type);
>>> + wide_int wmin0 = lh.lower_bound ();
>>> + wide_int wmax1 = rh.upper_bound ();
>>> + wi::sub (wmin0, wmax1, sgn, &ovf);
>>> + if (ovf != wi::OVF_NONE)
>>> + return false;
>>> +
>>> + if (TYPE_UNSIGNED (type))
>>> + return true;
>>> +
>>> + wide_int wmax0 = lh.upper_bound ();
>>> + wide_int wmin1 = rh.lower_bound ();
>>> + wi::sub (wmax0, wmin1, sgn, &ovf);
>>> + if (ovf != wi::OVF_NONE)
>>> + return false;
>>> +
>>> + return true;
>>> +}
>>> +
>>> +bool
>>> +operator_mult::overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio) const
>>> +{
>>> + if (lh.undefined_p () || rh.undefined_p ())
>>> + return false;
>>> +
>>> + tree type = lh.type ();
>>> + if (TYPE_OVERFLOW_UNDEFINED (type))
>>> + return true;
>>> +
>>> + wi::overflow_type ovf;
>>> + signop sgn = TYPE_SIGN (type);
>>> + wide_int wmax0 = lh.upper_bound ();
>>> + wide_int wmax1 = rh.upper_bound ();
>>> + wi::mul (wmax0, wmax1, sgn, &ovf);
>>> + if (ovf != wi::OVF_NONE)
>>> + return false;
>>> +
>>> + if (TYPE_UNSIGNED (type))
>>> + return true;
>>> +
>>> + wide_int wmin0 = lh.lower_bound ();
>>> + wide_int wmin1 = rh.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;
>>> +}
>>> +
>>> #if CHECKING_P
>>> #include "selftest.h"
>>> diff --git a/gcc/range-op.h b/gcc/range-op.h
>>> index af94c2756a7..db3b03f28a5 100644
>>> --- a/gcc/range-op.h
>>> +++ b/gcc/range-op.h
>>> @@ -147,6 +147,9 @@ public:
>>> virtual relation_kind op1_op2_relation (const irange &lhs)
>>> const;
>>> virtual relation_kind op1_op2_relation (const frange &lhs) const;
>>> +
>>> + virtual bool overflow_free_p (const irange &lh, const irange &rh,
>>> + relation_trio = TRIO_VARYING) const;
>>> protected:
>>> // Perform an integral operation between 2 sub-ranges and return
>>> it.
>>> virtual void wi_fold (irange &r, tree type,
>>> @@ -214,6 +217,8 @@ public:
>>> const vrange &op2,
>>> relation_kind = VREL_VARYING) const;
>>> relation_kind op1_op2_relation (const vrange &lhs) const;
>>> + bool overflow_free_p (const vrange &lh, const vrange &rh,
>>> + relation_trio = TRIO_VARYING) const;
>>> protected:
>>> unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
>>> const vrange& op2) const;
>>> diff --git a/gcc/value-range.cc b/gcc/value-range.cc
>>> index 011bdbdeae6..5ae4e044194 100644
>>> --- a/gcc/value-range.cc
>>> +++ b/gcc/value-range.cc
>>> @@ -313,6 +313,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 0170188201b..a12dea514e4 100644
>>> --- a/gcc/value-range.h
>>> +++ b/gcc/value-range.h
>>> @@ -280,6 +280,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;
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2023-08-31 5:07 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-18 14:05 [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
2023-07-18 14:05 ` [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid Jiufu Guo
2023-08-07 2:45 ` guojiufu
2023-08-23 2:04 ` Ping^^ " guojiufu
2023-08-28 13:14 ` Richard Biener
2023-08-29 7:25 ` Jiufu Guo
2023-08-03 2:18 ` [PATCH V5 1/2] Add overflow API for plus minus mult on range Jiufu Guo
2023-08-03 13:18 ` Andrew MacLeod
2023-08-31 5:07 ` guojiufu
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).