[V2] Optimize '(X - N * M) / N' to 'X / N - M' if valid
Checks
Commit Message
Hi,
This patch tries to optimize "(X - N * M) / N" to "X / N - M".
For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
wrap/overflow/underflow. So, it is valid that "X - N * M" does
not cross zero and does not wrap/overflow/underflow.
Compare with previous version:
https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
This patch 1. adds the patterns for variable N or M,
2. uses simpler form "(X - N * M) / N" for patterns,
3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
4. updates testcases
Bootstrap & regtest pass on ppc64{,le} and x86_64.
Is this patch ok for trunk?
BR,
Jeff (Jiufu Guo)
PR tree-optimization/108757
gcc/ChangeLog:
* gimple-fold.cc (maybe_mult_overflow): New function.
(maybe_plus_overflow): New function.
(maybe_minus_overflow): New function.
(plus_mult_no_ovf_and_keep_sign): New function.
(plus_no_ovf_and_keep_sign): New function.
* gimple-fold.h (maybe_mult_overflow): New declare.
(plus_mult_no_ovf_and_keep_sign): New declare.
(plus_no_ovf_and_keep_sign): New declare.
* match.pd ((X - N * M) / N): New pattern.
((X + N * M) / N): New pattern.
((X + C) / N): New pattern.
((X + C) >> N): New pattern.
gcc/testsuite/ChangeLog:
* gcc.dg/pr108757-1.c: New test.
* gcc.dg/pr108757-2.c: New test.
* gcc.dg/pr108757.h: New test.
---
gcc/gimple-fold.cc | 161 ++++++++++++++++++++
gcc/gimple-fold.h | 3 +
gcc/match.pd | 58 +++++++
gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
gcc/testsuite/gcc.dg/pr108757.h | 244 ++++++++++++++++++++++++++++++
6 files changed, 503 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
Comments
On Wed, 7 Jun 2023, Jiufu Guo wrote:
> Hi,
>
> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
> wrap/overflow/underflow. So, it is valid that "X - N * M" does
> not cross zero and does not wrap/overflow/underflow.
>
> Compare with previous version:
> https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
>
> This patch 1. adds the patterns for variable N or M,
> 2. uses simpler form "(X - N * M) / N" for patterns,
> 3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
> 4. updates testcases
>
> Bootstrap & regtest pass on ppc64{,le} and x86_64.
> Is this patch ok for trunk?
Comments below.
>
> BR,
> Jeff (Jiufu Guo)
>
> PR tree-optimization/108757
>
> gcc/ChangeLog:
>
> * gimple-fold.cc (maybe_mult_overflow): New function.
> (maybe_plus_overflow): New function.
> (maybe_minus_overflow): New function.
> (plus_mult_no_ovf_and_keep_sign): New function.
> (plus_no_ovf_and_keep_sign): New function.
> * gimple-fold.h (maybe_mult_overflow): New declare.
> (plus_mult_no_ovf_and_keep_sign): New declare.
> (plus_no_ovf_and_keep_sign): New declare.
> * match.pd ((X - N * M) / N): New pattern.
> ((X + N * M) / N): New pattern.
> ((X + C) / N): New pattern.
> ((X + C) >> N): New pattern.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/pr108757-1.c: New test.
> * gcc.dg/pr108757-2.c: New test.
> * gcc.dg/pr108757.h: New test.
>
> ---
> gcc/gimple-fold.cc | 161 ++++++++++++++++++++
> gcc/gimple-fold.h | 3 +
> gcc/match.pd | 58 +++++++
> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
> gcc/testsuite/gcc.dg/pr108757.h | 244 ++++++++++++++++++++++++++++++
> 6 files changed, 503 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
> create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
> create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
>
> diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
> index 581575b65ec..bb833ae17b3 100644
> --- a/gcc/gimple-fold.cc
> +++ b/gcc/gimple-fold.cc
> @@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
> return false;
> }
> }
> +
> +/* Return true if "X * Y" may be overflow. */
> +
> +bool
> +maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
These functions look like some "basic" functionality that should
be (or maybe already is? Andrew?) provided by the value-range
framework. That means it should not reside in gimple-fold.{cc,h}
but elsehwere and possibly with an API close to the existing
value-range stuff.
Andrew?
> +{
> + wide_int wmin0 = x.lower_bound ();
> + wide_int wmax0 = x.upper_bound ();
> + wide_int wmin1 = y.lower_bound ();
> + wide_int wmax1 = y.upper_bound ();
> +
> + wi::overflow_type min_ovf, max_ovf;
> + wi::mul (wmin0, wmin1, sgn, &min_ovf);
> + wi::mul (wmax0, wmax1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + {
> + wi::mul (wmin0, wmax1, sgn, &min_ovf);
> + wi::mul (wmax0, wmin1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + return false;
> + }
> + return true;
> +}
> +
> +/* Return true if "X + Y" may be overflow. */
> +
> +static bool
> +maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
> +{
> + wide_int wmin0 = x.lower_bound ();
> + wide_int wmax0 = x.upper_bound ();
> + wide_int wmin1 = y.lower_bound ();
> + wide_int wmax1 = y.upper_bound ();
> +
> + wi::overflow_type min_ovf, max_ovf;
> + wi::add (wmax0, wmax1, sgn, &min_ovf);
> + wi::add (wmin0, wmin1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if "X - Y" may be overflow. */
> +
> +static bool
> +maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
> +{
> + wide_int wmin0 = x.lower_bound ();
> + wide_int wmax0 = x.upper_bound ();
> + wide_int wmin1 = y.lower_bound ();
> + wide_int wmax1 = y.upper_bound ();
> +
> + wi::overflow_type min_ovf, max_ovf;
> + wi::sub (wmin0, wmax1, sgn, &min_ovf);
> + wi::sub (wmax0, wmin1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if there is no overflow in the expression.
> + And no sign change on the plus/minus for X.
What does the second sentence mean? sign(X) == sign (X + N*M)?
I suppose zero has positive sign?
> + CODE is PLUS_EXPR, if the expression is "X + N * M".
> + CODE is MINUS_EXPR, if the expression is "X - N * M".
> + TYPE is the integer type of the expressions. */
> +
> +bool
> +plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
> + tree type)
> +{
> + value_range vr0;
> + value_range vr1;
> + value_range vr2;
> +
> + if (get_range_query (cfun)->range_of_expr (vr0, x)
> + && get_range_query (cfun)->range_of_expr (vr1, n)
> + && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
> + && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
> + && !vr2.varying_p () && !vr2.undefined_p ())
> + {
> + signop sgn = TYPE_SIGN (type);
> + if (!TYPE_OVERFLOW_UNDEFINED (type))
> + {
> + if (maybe_mult_overflow (vr1, vr2, sgn))
> + {
> + m = fold_build1 (NEGATE_EXPR, type, m);
How's this valid? 'm' might wrap here? IMHO this special-case
needs a comment. Maybe you try to handle only constant 'm' here
since we tend to canonicalize X - N * 4u to X + N * -4u?
> + if (get_range_query (cfun)->range_of_expr (vr2, m)
> + && !vr2.varying_p () && !vr2.undefined_p ()
> + && !maybe_mult_overflow (vr1, vr2, sgn))
> + code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
> + else
> + return false;
> + }
> +
> + /* Get range of N*M */
> + tree mult = fold_build2 (MULT_EXPR, type, n, m);
Since you are working on GIMPLE 'mult' has an SSA name associated
which should also possibly get you more precise ranges (just capture
it, no need to re-generate a GENERIC expression here).
> + value_range vr3;
> + bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
> + gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
> +
> + bool overflow = code == MINUS_EXPR
> + ? maybe_minus_overflow (vr0, vr3, sgn)
> + : maybe_plus_overflow (vr0, vr3, sgn);
> + if (overflow)
> + return false;
> + }
> +
> + /* The value cross "0" is also a concern. */
> + if (sgn == UNSIGNED)
> + return true;
> + tree op
> + = fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
> + value_range vr4;
Again please use the captured representative here.
> + if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
> + && !vr4.undefined_p ())
> + {
> + /* X and (X +- N*M) are both positive (or both negtive). */
> + if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
> + && wi::ge_p (vr4.lower_bound (), 0, sgn))
> + || (wi::le_p (vr0.upper_bound (), 0, sgn)
> + && wi::le_p (vr4.upper_bound (), 0, sgn)))
As noted above I was hoping there's a value-range API for this. We
seem to have set_nonnegative, set_zero, etc. but no way to query
a known sign for integer ranges. FP ranges have signbit_p,
I guess that would work here, too, no?
Andrew?
Seeing the repeated check for !varying && !undefined I wonder if
we can somehow avoid the repetition with a higher level API?
> + return true;
> + }
> + }
> +
> +return false;
> +}
> +
> +/* Return true if there is no overflow and no sign change in "X + C".
> + C is a constant integer. */
> +
> +bool
> +plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
Pass 'c' as const wide_int& here.
> +{
> + value_range vr;
> + if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
> + && !vr.undefined_p ())
> + {
> + wi::overflow_type ovf = wi::OVF_NONE;
> + wide_int min = vr.lower_bound ();
> + wide_int max = vr.upper_bound ();
> + wide_int wc = wi::to_wide (c);
> + if (!TYPE_OVERFLOW_UNDEFINED (type))
> + {
> + if (tree_int_cst_sign_bit (c))
> + wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
> + else
> + wi::add (max, wc, TYPE_SIGN (type), &ovf);
> + }
> + if (ovf == wi::OVF_NONE)
> + /* unsigned, or 't' and 't + C' are both positive/negative. */
> + if (TYPE_UNSIGNED (type)
> + || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
the second compare should be the same as wi::ge_p (min, -wc, SIGNED) or
are you implicitely checking for overflow here?
> + || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
> + return true;
> + }
> +
> + return false;
> +}
> diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
> index 2fd58db9a2e..45df86a433e 100644
> --- a/gcc/gimple-fold.h
> +++ b/gcc/gimple-fold.h
> @@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
> extern void replace_call_with_value (gimple_stmt_iterator *, tree);
> extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
> extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
> +extern bool maybe_mult_overflow (tree, tree, tree);
> +extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
> +extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
>
> /* gimple_build, functionally matching fold_buildN, outputs stmts
> int the provided sequence, matching and simplifying them on-the-fly.
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 16482b741ea..6f7a6afdca8 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> #endif
> ))))
>
> +#if GIMPLE
> +(for div (trunc_div exact_div)
> + /* Simplify (t + M*N) / N -> t / N + M. */
> + (simplify
> + (div (plus:c @0 (mult:c @1 @2)) @2)
> + (if (INTEGRAL_TYPE_P (type)
> + && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
> + (plus (div @0 @2) @1)))
> +
> + /* Simplify (t - M*N) / N -> t / N - M. */
> + (simplify
> + (div (minus @0 (mult:c @1 @2)) @2)
> + (if (INTEGRAL_TYPE_P (type)
> + && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR, type))
> + (minus (div @0 @2) @1)))
> +
> + /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N */
> + (simplify
> + (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
> + (with
> + { tree repaired_c = @1;
> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> + repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
What if @1 is 0x80000000? Please consider re-doing this with
wide_int from the start.
> + }
> + (if (INTEGRAL_TYPE_P (type)
> + && multiple_of_p (type, repaired_c, @2)
> + && plus_no_ovf_and_keep_sign (@0, @1, type))
> + (with
> + { wide_int m;
> + wide_int c = wi::to_wide (@1);
> + wide_int n = wi::to_wide (@2);
> + wi::overflow_type ovf;
> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> + m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
> + else
> + m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
> + gcc_assert (ovf == wi::OVF_NONE);
> + }
> + (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
> +
> +/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */
> +(simplify
> + (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
> + (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
> + && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
> + && plus_no_ovf_and_keep_sign (@0, @1, type))
> + (with
> + { wide_int m;
> + wide_int c = wi::to_wide (@1);
> + wide_int n = wi::to_wide (@2);
> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> + m = -wi::rshift (-c, n, TYPE_SIGN (type));
> + else
> + m = wi::rshift (c, n, TYPE_SIGN (type));
> + }
> + (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
> +#endif
> +
> (for op (negate abs)
> /* Simplify cos(-x) and cos(|x|) -> cos(x). Similarly for cosh. */
> (for coss (COS COSH)
> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c b/gcc/testsuite/gcc.dg/pr108757-1.c
> new file mode 100644
> index 00000000000..7e7b60c756d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
> @@ -0,0 +1,18 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#include <limits.h>
> +#define N 5
> +#define M 3
> +#define GAP 0
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" } } *
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c b/gcc/testsuite/gcc.dg/pr108757-2.c
> new file mode 100644
> index 00000000000..2a9ad234e68
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
> @@ -0,0 +1,19 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
> +
> +#include <limits.h>
> +#define N 4
> +#define M 3
> +#define GAP 2
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
> +
> diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
> new file mode 100644
> index 00000000000..9dfa527f533
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757.h
> @@ -0,0 +1,244 @@
> +#define NOINLINE __attribute__ ((noinline))
> +UINT NOINLINE
> +opt_u1 (UINT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + UINT a = x - (M * N);
> + UINT b = a / N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u2 (UINT x)
> +{
> + if (x > (UMAX - (M * N) + GAP))
> + return 0;
> + UINT a = x + (M * N);
> + UINT b = a / N;
> + return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s1 (INT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s2 (INT x)
> +{
> + if (x < IMIN + (M * N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s3 (INT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / -N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s4 (INT x)
> +{
> + if (x < IMIN + (M * N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / -N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s5 (INT x)
> +{
> + if (x > (-M * N) + GAP)
> + return 0;
> + INT a = x - (-M * N);
> + INT b = a / N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s6 (INT x)
> +{
> + if (x > IMAX - (M * N) + GAP || x < 0)
> + return 0;
> + INT a = x - (-M * N);
> + INT b = a / N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s7 (INT x)
> +{
> + if (x > (M * -N) + GAP)
> + return 0;
> + INT a = x - (M * -N);
> + INT b = a / -N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s8 (INT x)
> +{
> + if (x > IMAX - (M * N) + GAP || x < 0)
> + return 0;
> + INT a = x - (M * -N);
> + INT b = a / -N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u3 (UINT x)
> +{
> + if (x < (M << N) - GAP)
> + return 0;
> + UINT a = x - (M << N);
> + UINT b = a >> N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u4 (UINT x)
> +{
> + if (x > (UMAX - (M << N)) + GAP)
> + return 0;
> + UINT a = x + (M << N);
> + UINT b = a >> N;
> + return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s9 (INT x)
> +{
> + if (x < (M << N) - GAP)
> + return 0;
> + INT a = x - (M << N);
> + INT b = a >> N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s10 (INT x)
> +{
> + if (x < IMIN + (M << N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M << N);
> + INT b = a >> N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s11 (INT x)
> +{
> + if (x > (-M << N) + GAP)
> + return 0;
> + INT a = x - (-M << N);
> + INT b = a >> N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s12 (INT x)
> +{
> + if (x > IMAX - (M << N) + GAP || x < 0)
> + return 0;
> + INT a = x - (-M << N);
> + INT b = a >> N;
> + return b + -M;
> +}
> +
> +UINT NOINLINE
> +opt_u5 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m > M)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + UINT a = x - (m * n);
> + UINT b = a / n;
> + return b + m;
> +}
> +
> +UINT NOINLINE
> +opt_u6 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m > M)
> + return 0;
> + if (x > (UMAX - M*N) + GAP)
> + return 0;
> + UINT a = x + (m * n);
> + UINT b = a / n;
> + return b - m;
> +}
> +
> +INT NOINLINE
> +opt_s13 (INT x, INT n, INT m)
> +{
> + if (n > N || m > M || n < 0 || m < 0)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + INT a = x - (m * n);
> + INT b = a / n;
> + return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s14 (INT x, INT n, INT m)
> +{
> + if (n > N || m > M || n < 0 || m < 0)
> + return 0;
> + if (x > -M*N + GAP)
> + return 0;
> + INT a = x + (m * n);
> + INT b = a / n;
> + return b - m;
> +}
> +
> +INT
> +opt_s15 (INT x, INT n, INT m)
> +{
> + if (n > 0 || m > 0 || n < -N || m < -M)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + INT a = x - (m * n);
> + INT b = a / n;
> + return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s16 (INT x, INT n, INT m)
> +{
> + if (n > 0 || m > 0 || n < -N || m < -M)
> + return 0;
> + if (x < 0 || x > (IMAX - M*N) + GAP)
> + return 0;
> + INT a = x + (m * n);
> + INT b = a / n;
> + return b - m;
> +}
> +
> +UINT NOINLINE
> +opt_u7 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m <= UMAX - M)
> + return 0;
> + if (x > UMAX - (M*N) + GAP)
> + return 0;
> + UINT a = x - (m * n);
> + UINT b = a / n;
> + return b + m;
> +}
>
Hi,
Richard Biener <rguenther@suse.de> writes:
> On Wed, 7 Jun 2023, Jiufu Guo wrote:
>
>> Hi,
>>
>> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
>> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
>> wrap/overflow/underflow. So, it is valid that "X - N * M" does
>> not cross zero and does not wrap/overflow/underflow.
>>
>> Compare with previous version:
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
>>
>> This patch 1. adds the patterns for variable N or M,
>> 2. uses simpler form "(X - N * M) / N" for patterns,
>> 3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
>> 4. updates testcases
>>
>> Bootstrap & regtest pass on ppc64{,le} and x86_64.
>> Is this patch ok for trunk?
>
> Comments below.
>
>>
>> BR,
>> Jeff (Jiufu Guo)
>>
>> PR tree-optimization/108757
>>
>> gcc/ChangeLog:
>>
>> * gimple-fold.cc (maybe_mult_overflow): New function.
>> (maybe_plus_overflow): New function.
>> (maybe_minus_overflow): New function.
>> (plus_mult_no_ovf_and_keep_sign): New function.
>> (plus_no_ovf_and_keep_sign): New function.
>> * gimple-fold.h (maybe_mult_overflow): New declare.
>> (plus_mult_no_ovf_and_keep_sign): New declare.
>> (plus_no_ovf_and_keep_sign): New declare.
>> * match.pd ((X - N * M) / N): New pattern.
>> ((X + N * M) / N): New pattern.
>> ((X + C) / N): New pattern.
>> ((X + C) >> N): New pattern.
>>
>> gcc/testsuite/ChangeLog:
>>
>> * gcc.dg/pr108757-1.c: New test.
>> * gcc.dg/pr108757-2.c: New test.
>> * gcc.dg/pr108757.h: New test.
>>
>> ---
>> gcc/gimple-fold.cc | 161 ++++++++++++++++++++
>> gcc/gimple-fold.h | 3 +
>> gcc/match.pd | 58 +++++++
>> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
>> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
>> gcc/testsuite/gcc.dg/pr108757.h | 244 ++++++++++++++++++++++++++++++
>> 6 files changed, 503 insertions(+)
>> create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
>> create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
>> create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
>>
>> diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
>> index 581575b65ec..bb833ae17b3 100644
>> --- a/gcc/gimple-fold.cc
>> +++ b/gcc/gimple-fold.cc
>> @@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
>> return false;
>> }
>> }
>> +
>> +/* Return true if "X * Y" may be overflow. */
>> +
>> +bool
>> +maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
>
> These functions look like some "basic" functionality that should
> be (or maybe already is? Andrew?) provided by the value-range
> framework. That means it should not reside in gimple-fold.{cc,h}
> but elsehwere and possibly with an API close to the existing
> value-range stuff.
>
> Andrew?
It would be great to get the overflow info directly from VR :)
Now, in range-op.cc, there is aleady value_range_with_overflow and
value_range_from_overflowed_bounds which checks OVFs.
While this information seems not recorded. Maybe, it is helpful
adding a field in VR and adding API to query it.
>
>> +{
>> + wide_int wmin0 = x.lower_bound ();
>> + wide_int wmax0 = x.upper_bound ();
>> + wide_int wmin1 = y.lower_bound ();
>> + wide_int wmax1 = y.upper_bound ();
>> +
>> + wi::overflow_type min_ovf, max_ovf;
>> + wi::mul (wmin0, wmin1, sgn, &min_ovf);
>> + wi::mul (wmax0, wmax1, sgn, &max_ovf);
>> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> + {
>> + wi::mul (wmin0, wmax1, sgn, &min_ovf);
>> + wi::mul (wmax0, wmin1, sgn, &max_ovf);
>> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> + return false;
>> + }
>> + return true;
>> +}
>> +
>> +/* Return true if "X + Y" may be overflow. */
>> +
>> +static bool
>> +maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
>> +{
>> + wide_int wmin0 = x.lower_bound ();
>> + wide_int wmax0 = x.upper_bound ();
>> + wide_int wmin1 = y.lower_bound ();
>> + wide_int wmax1 = y.upper_bound ();
>> +
>> + wi::overflow_type min_ovf, max_ovf;
>> + wi::add (wmax0, wmax1, sgn, &min_ovf);
>> + wi::add (wmin0, wmin1, sgn, &max_ovf);
>> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> + return false;
>> +
>> + return true;
>> +}
>> +
>> +/* Return true if "X - Y" may be overflow. */
>> +
>> +static bool
>> +maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
>> +{
>> + wide_int wmin0 = x.lower_bound ();
>> + wide_int wmax0 = x.upper_bound ();
>> + wide_int wmin1 = y.lower_bound ();
>> + wide_int wmax1 = y.upper_bound ();
>> +
>> + wi::overflow_type min_ovf, max_ovf;
>> + wi::sub (wmin0, wmax1, sgn, &min_ovf);
>> + wi::sub (wmax0, wmin1, sgn, &max_ovf);
>> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
>> + return false;
>> +
>> + return true;
>> +}
>> +
>> +/* Return true if there is no overflow in the expression.
>> + And no sign change on the plus/minus for X.
>
> What does the second sentence mean? sign(X) == sign (X + N*M)?
> I suppose zero has positive sign?
Right! This is useful for signed int. If "X" and "X + N*M" are
both negative, this transformation would be also valid.
Would use "sign(X) == sign (X + N*M)" clearly.
>
>> + CODE is PLUS_EXPR, if the expression is "X + N * M".
>> + CODE is MINUS_EXPR, if the expression is "X - N * M".
>> + TYPE is the integer type of the expressions. */
>> +
>> +bool
>> +plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
>> + tree type)
>> +{
>> + value_range vr0;
>> + value_range vr1;
>> + value_range vr2;
>> +
>> + if (get_range_query (cfun)->range_of_expr (vr0, x)
>> + && get_range_query (cfun)->range_of_expr (vr1, n)
>> + && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
>> + && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
>> + && !vr2.varying_p () && !vr2.undefined_p ())
>> + {
>> + signop sgn = TYPE_SIGN (type);
>> + if (!TYPE_OVERFLOW_UNDEFINED (type))
>> + {
>> + if (maybe_mult_overflow (vr1, vr2, sgn))
>> + {
>> + m = fold_build1 (NEGATE_EXPR, type, m);
>
> How's this valid? 'm' might wrap here? IMHO this special-case
> needs a comment. Maybe you try to handle only constant 'm' here
> since we tend to canonicalize X - N * 4u to X + N * -4u?
Thanks! A comment should be added. This would be useful for
"unsigned" (for signed, OVF info for 'n*m' would be same with
'n*-m').
Like a prepared test case for this:
opt_u7 (UINT x, UINT n, UINT m)
{
if (n > N || m <= UMAX - M)
return 0;
if (x > UMAX - (M*N) + GAP)
return 0;
UINT a = x - (m * n);
UINT b = a / n;
Here, m is "-M to -1u", then "n*m" overflows, but
"n*-m" does not overflow. And "x - (m * n)" can be treated
as "x + (-m) * n".
>
>> + if (get_range_query (cfun)->range_of_expr (vr2, m)
>> + && !vr2.varying_p () && !vr2.undefined_p ()
>> + && !maybe_mult_overflow (vr1, vr2, sgn))
>> + code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
>> + else
>> + return false;
>> + }
>> +
>> + /* Get range of N*M */
>> + tree mult = fold_build2 (MULT_EXPR, type, n, m);
>
> Since you are working on GIMPLE 'mult' has an SSA name associated
> which should also possibly get you more precise ranges (just capture
> it, no need to re-generate a GENERIC expression here).
Great idea!
>
>> + value_range vr3;
>> + bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
>> + gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
>> +
>> + bool overflow = code == MINUS_EXPR
>> + ? maybe_minus_overflow (vr0, vr3, sgn)
>> + : maybe_plus_overflow (vr0, vr3, sgn);
>> + if (overflow)
>> + return false;
>> + }
>> +
>> + /* The value cross "0" is also a concern. */
>> + if (sgn == UNSIGNED)
>> + return true;
>> + tree op
>> + = fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
>> + value_range vr4;
>
> Again please use the captured representative here.
Thanks!
>
>> + if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
>> + && !vr4.undefined_p ())
>> + {
>> + /* X and (X +- N*M) are both positive (or both negtive). */
>> + if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
>> + && wi::ge_p (vr4.lower_bound (), 0, sgn))
>> + || (wi::le_p (vr0.upper_bound (), 0, sgn)
>> + && wi::le_p (vr4.upper_bound (), 0, sgn)))
>
> As noted above I was hoping there's a value-range API for this. We
> seem to have set_nonnegative, set_zero, etc. but no way to query
> a known sign for integer ranges. FP ranges have signbit_p,
> I guess that would work here, too, no?
Thanks for pointing out this! I will check these APIs!
>
> Andrew?
>
> Seeing the repeated check for !varying && !undefined I wonder if
> we can somehow avoid the repetition with a higher level API?
The VR info for x,n,m are checked. If OVF info for "X", "N*M", are
checked too, ranges for combined expressions ("N*M", "X-N*M") may not
be needed, but verifying the final OVF infor may still be required.
Thanks for any comments!!
>
>> + return true;
>> + }
>> + }
>> +
>> +return false;
>> +}
>> +
>> +/* Return true if there is no overflow and no sign change in "X + C".
>> + C is a constant integer. */
>> +
>> +bool
>> +plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
>
> Pass 'c' as const wide_int& here.
Yeap, while "tree_int_cst_sign_bit (c)" can be used on "tree c" :)
Using wide_int should be also ok, tree_int_cst_sign_bit is also based on
wide_int.
>
>> +{
>> + value_range vr;
>> + if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
>> + && !vr.undefined_p ())
>> + {
>> + wi::overflow_type ovf = wi::OVF_NONE;
>> + wide_int min = vr.lower_bound ();
>> + wide_int max = vr.upper_bound ();
>> + wide_int wc = wi::to_wide (c);
>> + if (!TYPE_OVERFLOW_UNDEFINED (type))
>> + {
>> + if (tree_int_cst_sign_bit (c))
>> + wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
>> + else
>> + wi::add (max, wc, TYPE_SIGN (type), &ovf);
>> + }
>> + if (ovf == wi::OVF_NONE)
>> + /* unsigned, or 't' and 't + C' are both positive/negative. */
>> + if (TYPE_UNSIGNED (type)
>> + || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
>
> the second compare should be the same as wi::ge_p (min, -wc, SIGNED) or
> are you implicitely checking for overflow here?
"wi::ge_p (min + wc, 0, SIGNED)" is used just because it may more
readable as: "'min + wc' is positive".
>
>> + || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
>> + return true;
>> + }
>> +
>> + return false;
>> +}
>> diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
>> index 2fd58db9a2e..45df86a433e 100644
>> --- a/gcc/gimple-fold.h
>> +++ b/gcc/gimple-fold.h
>> @@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
>> extern void replace_call_with_value (gimple_stmt_iterator *, tree);
>> extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
>> extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
>> +extern bool maybe_mult_overflow (tree, tree, tree);
>> +extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
>> +extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
>>
>> /* gimple_build, functionally matching fold_buildN, outputs stmts
>> int the provided sequence, matching and simplifying them on-the-fly.
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 16482b741ea..6f7a6afdca8 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>> #endif
>> ))))
>>
>> +#if GIMPLE
>> +(for div (trunc_div exact_div)
>> + /* Simplify (t + M*N) / N -> t / N + M. */
>> + (simplify
>> + (div (plus:c @0 (mult:c @1 @2)) @2)
>> + (if (INTEGRAL_TYPE_P (type)
>> + && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
>> + (plus (div @0 @2) @1)))
>> +
>> + /* Simplify (t - M*N) / N -> t / N - M. */
>> + (simplify
>> + (div (minus @0 (mult:c @1 @2)) @2)
>> + (if (INTEGRAL_TYPE_P (type)
>> + && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR, type))
>> + (minus (div @0 @2) @1)))
>> +
>> + /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N */
>> + (simplify
>> + (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
>> + (with
>> + { tree repaired_c = @1;
>> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
>> + repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
>
> What if @1 is 0x80000000? Please consider re-doing this with
> wide_int from the start.
Thanks for the great catch here! This is a special value, while NEGATE
would not break it here.
OK, wide_int would be preferred.
Thanks again for your quick and helpful comments!
BR,
Jeff (Jiufu Guo)
>
>> + }
>> + (if (INTEGRAL_TYPE_P (type)
>> + && multiple_of_p (type, repaired_c, @2)
>> + && plus_no_ovf_and_keep_sign (@0, @1, type))
>> + (with
>> + { wide_int m;
>> + wide_int c = wi::to_wide (@1);
>> + wide_int n = wi::to_wide (@2);
>> + wi::overflow_type ovf;
>> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
>> + m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
>> + else
>> + m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
>> + gcc_assert (ovf == wi::OVF_NONE);
>> + }
>> + (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
>> +
>> +/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */
>> +(simplify
>> + (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
>> + (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
>> + && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
>> + && plus_no_ovf_and_keep_sign (@0, @1, type))
>> + (with
>> + { wide_int m;
>> + wide_int c = wi::to_wide (@1);
>> + wide_int n = wi::to_wide (@2);
>> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
>> + m = -wi::rshift (-c, n, TYPE_SIGN (type));
>> + else
>> + m = wi::rshift (c, n, TYPE_SIGN (type));
>> + }
>> + (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
>> +#endif
>> +
>> (for op (negate abs)
>> /* Simplify cos(-x) and cos(|x|) -> cos(x). Similarly for cosh. */
>> (for coss (COS COSH)
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c b/gcc/testsuite/gcc.dg/pr108757-1.c
>> new file mode 100644
>> index 00000000000..7e7b60c756d
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
>> @@ -0,0 +1,18 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +#include <limits.h>
>> +#define N 5
>> +#define M 3
>> +#define GAP 0
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" } } *
>> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" } } */
>> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
>> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c b/gcc/testsuite/gcc.dg/pr108757-2.c
>> new file mode 100644
>> index 00000000000..2a9ad234e68
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
>> @@ -0,0 +1,19 @@
>> +/* PR tree-optimization/108757 */
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
>> +
>> +#include <limits.h>
>> +#define N 4
>> +#define M 3
>> +#define GAP 2
>> +typedef unsigned int UINT;
>> +typedef int INT;
>> +#define UMAX UINT_MAX
>> +#define IMAX INT_MAX
>> +#define IMIN INT_MIN
>> +#include "pr108757.h"
>> +
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4 "optimized" } } */
>> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
>> +
>> diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
>> new file mode 100644
>> index 00000000000..9dfa527f533
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/pr108757.h
>> @@ -0,0 +1,244 @@
>> +#define NOINLINE __attribute__ ((noinline))
>> +UINT NOINLINE
>> +opt_u1 (UINT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + UINT a = x - (M * N);
>> + UINT b = a / N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u2 (UINT x)
>> +{
>> + if (x > (UMAX - (M * N) + GAP))
>> + return 0;
>> + UINT a = x + (M * N);
>> + UINT b = a / N;
>> + return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s1 (INT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s2 (INT x)
>> +{
>> + if (x < IMIN + (M * N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s3 (INT x)
>> +{
>> + if (x < (M * N) - GAP)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / -N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s4 (INT x)
>> +{
>> + if (x < IMIN + (M * N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M * N);
>> + INT b = a / -N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s5 (INT x)
>> +{
>> + if (x > (-M * N) + GAP)
>> + return 0;
>> + INT a = x - (-M * N);
>> + INT b = a / N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s6 (INT x)
>> +{
>> + if (x > IMAX - (M * N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (-M * N);
>> + INT b = a / N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s7 (INT x)
>> +{
>> + if (x > (M * -N) + GAP)
>> + return 0;
>> + INT a = x - (M * -N);
>> + INT b = a / -N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s8 (INT x)
>> +{
>> + if (x > IMAX - (M * N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (M * -N);
>> + INT b = a / -N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u3 (UINT x)
>> +{
>> + if (x < (M << N) - GAP)
>> + return 0;
>> + UINT a = x - (M << N);
>> + UINT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u4 (UINT x)
>> +{
>> + if (x > (UMAX - (M << N)) + GAP)
>> + return 0;
>> + UINT a = x + (M << N);
>> + UINT b = a >> N;
>> + return b - M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s9 (INT x)
>> +{
>> + if (x < (M << N) - GAP)
>> + return 0;
>> + INT a = x - (M << N);
>> + INT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s10 (INT x)
>> +{
>> + if (x < IMIN + (M << N) - GAP || x > 0)
>> + return 0;
>> + INT a = x - (M << N);
>> + INT b = a >> N;
>> + return b + M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s11 (INT x)
>> +{
>> + if (x > (-M << N) + GAP)
>> + return 0;
>> + INT a = x - (-M << N);
>> + INT b = a >> N;
>> + return b + -M;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s12 (INT x)
>> +{
>> + if (x > IMAX - (M << N) + GAP || x < 0)
>> + return 0;
>> + INT a = x - (-M << N);
>> + INT b = a >> N;
>> + return b + -M;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u5 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m > M)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + UINT a = x - (m * n);
>> + UINT b = a / n;
>> + return b + m;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u6 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m > M)
>> + return 0;
>> + if (x > (UMAX - M*N) + GAP)
>> + return 0;
>> + UINT a = x + (m * n);
>> + UINT b = a / n;
>> + return b - m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s13 (INT x, INT n, INT m)
>> +{
>> + if (n > N || m > M || n < 0 || m < 0)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + INT a = x - (m * n);
>> + INT b = a / n;
>> + return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s14 (INT x, INT n, INT m)
>> +{
>> + if (n > N || m > M || n < 0 || m < 0)
>> + return 0;
>> + if (x > -M*N + GAP)
>> + return 0;
>> + INT a = x + (m * n);
>> + INT b = a / n;
>> + return b - m;
>> +}
>> +
>> +INT
>> +opt_s15 (INT x, INT n, INT m)
>> +{
>> + if (n > 0 || m > 0 || n < -N || m < -M)
>> + return 0;
>> + if (x < (M*N) - GAP)
>> + return 0;
>> + INT a = x - (m * n);
>> + INT b = a / n;
>> + return b + m;
>> +}
>> +
>> +INT NOINLINE
>> +opt_s16 (INT x, INT n, INT m)
>> +{
>> + if (n > 0 || m > 0 || n < -N || m < -M)
>> + return 0;
>> + if (x < 0 || x > (IMAX - M*N) + GAP)
>> + return 0;
>> + INT a = x + (m * n);
>> + INT b = a / n;
>> + return b - m;
>> +}
>> +
>> +UINT NOINLINE
>> +opt_u7 (UINT x, UINT n, UINT m)
>> +{
>> + if (n > N || m <= UMAX - M)
>> + return 0;
>> + if (x > UMAX - (M*N) + GAP)
>> + return 0;
>> + UINT a = x - (m * n);
>> + UINT b = a / n;
>> + return b + m;
>> +}
>>
Hi!
On Wed, Jun 07, 2023 at 04:21:11PM +0800, Jiufu Guo wrote:
> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
> wrap/overflow/underflow. So, it is valid that "X - N * M" does
> not cross zero and does not wrap/overflow/underflow.
Is it ever valid semi-generally when N does not divide X?
Say X=5, N=2, M=3. Then the original expression evaluates to 0, but the
new one to -1. Whenever one of the divisions rounds up and the other
rounds down you have this problem.
Segher
Hi,
Thanks for your comments!
Segher Boessenkool <segher@kernel.crashing.org> writes:
> Hi!
>
> On Wed, Jun 07, 2023 at 04:21:11PM +0800, Jiufu Guo wrote:
>> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
>> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
>> wrap/overflow/underflow. So, it is valid that "X - N * M" does
>> not cross zero and does not wrap/overflow/underflow.
>
> Is it ever valid semi-generally when N does not divide X?
It is valid only if there is no wrap/overflow/underflow, and the sign
of "X" and "X-N*M" are the same. Under this condition, N,M and X can be
any value.
>
> Say X=5, N=2, M=3. Then the original expression evaluates to 0, but the
> new one to -1. Whenever one of the divisions rounds up and the other
> rounds down you have this problem.
You are right. Since '/' is always towards zero, so, 'X' and 'X-N*M'
should have the same sign bit. Otherwise, one rounds up, the other
rounds down, then the transform is invalid.
BR,
Jeff (Jiufu Guo)
>
>
> Segher
@@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int depth)
return false;
}
}
+
+/* Return true if "X * Y" may be overflow. */
+
+bool
+maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
+{
+ wide_int wmin0 = x.lower_bound ();
+ wide_int wmax0 = x.upper_bound ();
+ wide_int wmin1 = y.lower_bound ();
+ wide_int wmax1 = y.upper_bound ();
+
+ wi::overflow_type min_ovf, max_ovf;
+ wi::mul (wmin0, wmin1, sgn, &min_ovf);
+ wi::mul (wmax0, wmax1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ {
+ wi::mul (wmin0, wmax1, sgn, &min_ovf);
+ wi::mul (wmax0, wmin1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ return false;
+ }
+ return true;
+}
+
+/* Return true if "X + Y" may be overflow. */
+
+static bool
+maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
+{
+ wide_int wmin0 = x.lower_bound ();
+ wide_int wmax0 = x.upper_bound ();
+ wide_int wmin1 = y.lower_bound ();
+ wide_int wmax1 = y.upper_bound ();
+
+ wi::overflow_type min_ovf, max_ovf;
+ wi::add (wmax0, wmax1, sgn, &min_ovf);
+ wi::add (wmin0, wmin1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if "X - Y" may be overflow. */
+
+static bool
+maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
+{
+ wide_int wmin0 = x.lower_bound ();
+ wide_int wmax0 = x.upper_bound ();
+ wide_int wmin1 = y.lower_bound ();
+ wide_int wmax1 = y.upper_bound ();
+
+ wi::overflow_type min_ovf, max_ovf;
+ wi::sub (wmin0, wmax1, sgn, &min_ovf);
+ wi::sub (wmax0, wmin1, sgn, &max_ovf);
+ if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
+ return false;
+
+ return true;
+}
+
+/* Return true if there is no overflow in the expression.
+ And no sign change on the plus/minus for X.
+ CODE is PLUS_EXPR, if the expression is "X + N * M".
+ CODE is MINUS_EXPR, if the expression is "X - N * M".
+ TYPE is the integer type of the expressions. */
+
+bool
+plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
+ tree type)
+{
+ value_range vr0;
+ value_range vr1;
+ value_range vr2;
+
+ if (get_range_query (cfun)->range_of_expr (vr0, x)
+ && get_range_query (cfun)->range_of_expr (vr1, n)
+ && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
+ && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
+ && !vr2.varying_p () && !vr2.undefined_p ())
+ {
+ signop sgn = TYPE_SIGN (type);
+ if (!TYPE_OVERFLOW_UNDEFINED (type))
+ {
+ if (maybe_mult_overflow (vr1, vr2, sgn))
+ {
+ m = fold_build1 (NEGATE_EXPR, type, m);
+ if (get_range_query (cfun)->range_of_expr (vr2, m)
+ && !vr2.varying_p () && !vr2.undefined_p ()
+ && !maybe_mult_overflow (vr1, vr2, sgn))
+ code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
+ else
+ return false;
+ }
+
+ /* Get range of N*M */
+ tree mult = fold_build2 (MULT_EXPR, type, n, m);
+ value_range vr3;
+ bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
+ gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
+
+ bool overflow = code == MINUS_EXPR
+ ? maybe_minus_overflow (vr0, vr3, sgn)
+ : maybe_plus_overflow (vr0, vr3, sgn);
+ if (overflow)
+ return false;
+ }
+
+ /* The value cross "0" is also a concern. */
+ if (sgn == UNSIGNED)
+ return true;
+ tree op
+ = fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
+ value_range vr4;
+ if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p ()
+ && !vr4.undefined_p ())
+ {
+ /* X and (X +- N*M) are both positive (or both negtive). */
+ if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
+ && wi::ge_p (vr4.lower_bound (), 0, sgn))
+ || (wi::le_p (vr0.upper_bound (), 0, sgn)
+ && wi::le_p (vr4.upper_bound (), 0, sgn)))
+ return true;
+ }
+ }
+
+return false;
+}
+
+/* Return true if there is no overflow and no sign change in "X + C".
+ C is a constant integer. */
+
+bool
+plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
+{
+ value_range vr;
+ if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
+ && !vr.undefined_p ())
+ {
+ wi::overflow_type ovf = wi::OVF_NONE;
+ wide_int min = vr.lower_bound ();
+ wide_int max = vr.upper_bound ();
+ wide_int wc = wi::to_wide (c);
+ if (!TYPE_OVERFLOW_UNDEFINED (type))
+ {
+ if (tree_int_cst_sign_bit (c))
+ wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
+ else
+ wi::add (max, wc, TYPE_SIGN (type), &ovf);
+ }
+ if (ovf == wi::OVF_NONE)
+ /* unsigned, or 't' and 't + C' are both positive/negative. */
+ if (TYPE_UNSIGNED (type)
+ || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
+ || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
+ return true;
+ }
+
+ return false;
+}
@@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *, bool = false);
extern void replace_call_with_value (gimple_stmt_iterator *, tree);
extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree, tree);
extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
+extern bool maybe_mult_overflow (tree, tree, tree);
+extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code, tree);
+extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
/* gimple_build, functionally matching fold_buildN, outputs stmts
int the provided sequence, matching and simplifying them on-the-fly.
@@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
#endif
))))
+#if GIMPLE
+(for div (trunc_div exact_div)
+ /* Simplify (t + M*N) / N -> t / N + M. */
+ (simplify
+ (div (plus:c @0 (mult:c @1 @2)) @2)
+ (if (INTEGRAL_TYPE_P (type)
+ && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
+ (plus (div @0 @2) @1)))
+
+ /* Simplify (t - M*N) / N -> t / N - M. */
+ (simplify
+ (div (minus @0 (mult:c @1 @2)) @2)
+ (if (INTEGRAL_TYPE_P (type)
+ && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR, type))
+ (minus (div @0 @2) @1)))
+
+ /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N */
+ (simplify
+ (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
+ (with
+ { tree repaired_c = @1;
+ if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+ repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
+ }
+ (if (INTEGRAL_TYPE_P (type)
+ && multiple_of_p (type, repaired_c, @2)
+ && plus_no_ovf_and_keep_sign (@0, @1, type))
+ (with
+ { wide_int m;
+ wide_int c = wi::to_wide (@1);
+ wide_int n = wi::to_wide (@2);
+ wi::overflow_type ovf;
+ if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+ m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
+ else
+ m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
+ gcc_assert (ovf == wi::OVF_NONE);
+ }
+ (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
+
+/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */
+(simplify
+ (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
+ && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
+ && plus_no_ovf_and_keep_sign (@0, @1, type))
+ (with
+ { wide_int m;
+ wide_int c = wi::to_wide (@1);
+ wide_int n = wi::to_wide (@2);
+ if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
+ m = -wi::rshift (-c, n, TYPE_SIGN (type));
+ else
+ m = wi::rshift (c, n, TYPE_SIGN (type));
+ }
+ (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
+#endif
+
(for op (negate abs)
/* Simplify cos(-x) and cos(|x|) -> cos(x). Similarly for cosh. */
(for coss (COS COSH)
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -0,0 +1,19 @@
+/* PR tree-optimization/108757 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
+
+#include <limits.h>
+#define N 4
+#define M 3
+#define GAP 2
+typedef unsigned int UINT;
+typedef int INT;
+#define UMAX UINT_MAX
+#define IMAX INT_MAX
+#define IMIN INT_MIN
+#include "pr108757.h"
+
+/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized" } } */
+
new file mode 100644
@@ -0,0 +1,244 @@
+#define NOINLINE __attribute__ ((noinline))
+UINT NOINLINE
+opt_u1 (UINT x)
+{
+ if (x < (M * N) - GAP)
+ return 0;
+ UINT a = x - (M * N);
+ UINT b = a / N;
+ return b + M;
+}
+
+UINT NOINLINE
+opt_u2 (UINT x)
+{
+ if (x > (UMAX - (M * N) + GAP))
+ return 0;
+ UINT a = x + (M * N);
+ UINT b = a / N;
+ return b - M;
+}
+
+INT NOINLINE
+opt_s1 (INT x)
+{
+ if (x < (M * N) - GAP)
+ return 0;
+ INT a = x - (M * N);
+ INT b = a / N;
+ return b + M;
+}
+
+INT NOINLINE
+opt_s2 (INT x)
+{
+ if (x < IMIN + (M * N) - GAP || x > 0)
+ return 0;
+ INT a = x - (M * N);
+ INT b = a / N;
+ return b + M;
+}
+
+INT NOINLINE
+opt_s3 (INT x)
+{
+ if (x < (M * N) - GAP)
+ return 0;
+ INT a = x - (M * N);
+ INT b = a / -N;
+ return b + -M;
+}
+
+INT NOINLINE
+opt_s4 (INT x)
+{
+ if (x < IMIN + (M * N) - GAP || x > 0)
+ return 0;
+ INT a = x - (M * N);
+ INT b = a / -N;
+ return b + -M;
+}
+
+INT NOINLINE
+opt_s5 (INT x)
+{
+ if (x > (-M * N) + GAP)
+ return 0;
+ INT a = x - (-M * N);
+ INT b = a / N;
+ return b + -M;
+}
+
+INT NOINLINE
+opt_s6 (INT x)
+{
+ if (x > IMAX - (M * N) + GAP || x < 0)
+ return 0;
+ INT a = x - (-M * N);
+ INT b = a / N;
+ return b + -M;
+}
+
+INT NOINLINE
+opt_s7 (INT x)
+{
+ if (x > (M * -N) + GAP)
+ return 0;
+ INT a = x - (M * -N);
+ INT b = a / -N;
+ return b + M;
+}
+
+INT NOINLINE
+opt_s8 (INT x)
+{
+ if (x > IMAX - (M * N) + GAP || x < 0)
+ return 0;
+ INT a = x - (M * -N);
+ INT b = a / -N;
+ return b + M;
+}
+
+UINT NOINLINE
+opt_u3 (UINT x)
+{
+ if (x < (M << N) - GAP)
+ return 0;
+ UINT a = x - (M << N);
+ UINT b = a >> N;
+ return b + M;
+}
+
+UINT NOINLINE
+opt_u4 (UINT x)
+{
+ if (x > (UMAX - (M << N)) + GAP)
+ return 0;
+ UINT a = x + (M << N);
+ UINT b = a >> N;
+ return b - M;
+}
+
+INT NOINLINE
+opt_s9 (INT x)
+{
+ if (x < (M << N) - GAP)
+ return 0;
+ INT a = x - (M << N);
+ INT b = a >> N;
+ return b + M;
+}
+
+INT NOINLINE
+opt_s10 (INT x)
+{
+ if (x < IMIN + (M << N) - GAP || x > 0)
+ return 0;
+ INT a = x - (M << N);
+ INT b = a >> N;
+ return b + M;
+}
+
+INT NOINLINE
+opt_s11 (INT x)
+{
+ if (x > (-M << N) + GAP)
+ return 0;
+ INT a = x - (-M << N);
+ INT b = a >> N;
+ return b + -M;
+}
+
+INT NOINLINE
+opt_s12 (INT x)
+{
+ if (x > IMAX - (M << N) + GAP || x < 0)
+ return 0;
+ INT a = x - (-M << N);
+ INT b = a >> N;
+ return b + -M;
+}
+
+UINT NOINLINE
+opt_u5 (UINT x, UINT n, UINT m)
+{
+ if (n > N || m > M)
+ return 0;
+ if (x < (M*N) - GAP)
+ return 0;
+ UINT a = x - (m * n);
+ UINT b = a / n;
+ return b + m;
+}
+
+UINT NOINLINE
+opt_u6 (UINT x, UINT n, UINT m)
+{
+ if (n > N || m > M)
+ return 0;
+ if (x > (UMAX - M*N) + GAP)
+ return 0;
+ UINT a = x + (m * n);
+ UINT b = a / n;
+ return b - m;
+}
+
+INT NOINLINE
+opt_s13 (INT x, INT n, INT m)
+{
+ if (n > N || m > M || n < 0 || m < 0)
+ return 0;
+ if (x < (M*N) - GAP)
+ return 0;
+ INT a = x - (m * n);
+ INT b = a / n;
+ return b + m;
+}
+
+INT NOINLINE
+opt_s14 (INT x, INT n, INT m)
+{
+ if (n > N || m > M || n < 0 || m < 0)
+ return 0;
+ if (x > -M*N + GAP)
+ return 0;
+ INT a = x + (m * n);
+ INT b = a / n;
+ return b - m;
+}
+
+INT
+opt_s15 (INT x, INT n, INT m)
+{
+ if (n > 0 || m > 0 || n < -N || m < -M)
+ return 0;
+ if (x < (M*N) - GAP)
+ return 0;
+ INT a = x - (m * n);
+ INT b = a / n;
+ return b + m;
+}
+
+INT NOINLINE
+opt_s16 (INT x, INT n, INT m)
+{
+ if (n > 0 || m > 0 || n < -N || m < -M)
+ return 0;
+ if (x < 0 || x > (IMAX - M*N) + GAP)
+ return 0;
+ INT a = x + (m * n);
+ INT b = a / n;
+ return b - m;
+}
+
+UINT NOINLINE
+opt_u7 (UINT x, UINT n, UINT m)
+{
+ if (n > N || m <= UMAX - M)
+ return 0;
+ if (x > UMAX - (M*N) + GAP)
+ return 0;
+ UINT a = x - (m * n);
+ UINT b = a / n;
+ return b + m;
+}