On Wed, 7 Jun 2023, Jiufu Guo wrote:
> Hi,
>
> This patch tries to optimize "(X - N * M) / N" to "X / N - M".
> For C code, "/" towards zero (trunc_div), and "X - N * M" maybe
> wrap/overflow/underflow. So, it is valid that "X - N * M" does
> not cross zero and does not wrap/overflow/underflow.
>
> Compare with previous version:
> https://gcc.gnu.org/pipermail/gcc-patches/2023-May/618796.html
>
> This patch 1. adds the patterns for variable N or M,
> 2. uses simpler form "(X - N * M) / N" for patterns,
> 3. adds functions to gimle-fold.h/cc (not gimple-match-head.cc)
> 4. updates testcases
>
> Bootstrap & regtest pass on ppc64{,le} and x86_64.
> Is this patch ok for trunk?
Comments below.
>
> BR,
> Jeff (Jiufu Guo)
>
> PR tree-optimization/108757
>
> gcc/ChangeLog:
>
> * gimple-fold.cc (maybe_mult_overflow): New function.
> (maybe_plus_overflow): New function.
> (maybe_minus_overflow): New function.
> (plus_mult_no_ovf_and_keep_sign): New function.
> (plus_no_ovf_and_keep_sign): New function.
> * gimple-fold.h (maybe_mult_overflow): New declare.
> (plus_mult_no_ovf_and_keep_sign): New declare.
> (plus_no_ovf_and_keep_sign): New declare.
> * match.pd ((X - N * M) / N): New pattern.
> ((X + N * M) / N): New pattern.
> ((X + C) / N): New pattern.
> ((X + C) >> N): New pattern.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/pr108757-1.c: New test.
> * gcc.dg/pr108757-2.c: New test.
> * gcc.dg/pr108757.h: New test.
>
> ---
> gcc/gimple-fold.cc | 161 ++++++++++++++++++++
> gcc/gimple-fold.h | 3 +
> gcc/match.pd | 58 +++++++
> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++
> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++
> gcc/testsuite/gcc.dg/pr108757.h | 244 ++++++++++++++++++++++++++++++
> 6 files changed, 503 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c
> create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c
> create mode 100644 gcc/testsuite/gcc.dg/pr108757.h
>
> diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
> index 581575b65ec..bb833ae17b3 100644
> --- a/gcc/gimple-fold.cc
> +++ b/gcc/gimple-fold.cc
> @@ -9349,3 +9349,164 @@ gimple_stmt_integer_valued_real_p (gimple *stmt, int
> depth)
> return false;
> }
> }
> +
> +/* Return true if "X * Y" may be overflow. */
> +
> +bool
> +maybe_mult_overflow (value_range &x, value_range &y, signop sgn)
These functions look like some "basic" functionality that should
be (or maybe already is? Andrew?) provided by the value-range
framework. That means it should not reside in gimple-fold.{cc,h}
but elsehwere and possibly with an API close to the existing
value-range stuff.
Andrew?
> +{
> + wide_int wmin0 = x.lower_bound ();
> + wide_int wmax0 = x.upper_bound ();
> + wide_int wmin1 = y.lower_bound ();
> + wide_int wmax1 = y.upper_bound ();
> +
> + wi::overflow_type min_ovf, max_ovf;
> + wi::mul (wmin0, wmin1, sgn, &min_ovf);
> + wi::mul (wmax0, wmax1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + {
> + wi::mul (wmin0, wmax1, sgn, &min_ovf);
> + wi::mul (wmax0, wmin1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + return false;
> + }
> + return true;
> +}
> +
> +/* Return true if "X + Y" may be overflow. */
> +
> +static bool
> +maybe_plus_overflow (value_range &x, value_range &y, signop sgn)
> +{
> + wide_int wmin0 = x.lower_bound ();
> + wide_int wmax0 = x.upper_bound ();
> + wide_int wmin1 = y.lower_bound ();
> + wide_int wmax1 = y.upper_bound ();
> +
> + wi::overflow_type min_ovf, max_ovf;
> + wi::add (wmax0, wmax1, sgn, &min_ovf);
> + wi::add (wmin0, wmin1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if "X - Y" may be overflow. */
> +
> +static bool
> +maybe_minus_overflow (value_range &x, value_range &y, signop sgn)
> +{
> + wide_int wmin0 = x.lower_bound ();
> + wide_int wmax0 = x.upper_bound ();
> + wide_int wmin1 = y.lower_bound ();
> + wide_int wmax1 = y.upper_bound ();
> +
> + wi::overflow_type min_ovf, max_ovf;
> + wi::sub (wmin0, wmax1, sgn, &min_ovf);
> + wi::sub (wmax0, wmin1, sgn, &max_ovf);
> + if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if there is no overflow in the expression.
> + And no sign change on the plus/minus for X.
What does the second sentence mean? sign(X) == sign (X + N*M)?
I suppose zero has positive sign?
> + CODE is PLUS_EXPR, if the expression is "X + N * M".
> + CODE is MINUS_EXPR, if the expression is "X - N * M".
> + TYPE is the integer type of the expressions. */
> +
> +bool
> +plus_mult_no_ovf_and_keep_sign (tree x, tree m, tree n, tree_code code,
> + tree type)
> +{
> + value_range vr0;
> + value_range vr1;
> + value_range vr2;
> +
> + if (get_range_query (cfun)->range_of_expr (vr0, x)
> + && get_range_query (cfun)->range_of_expr (vr1, n)
> + && get_range_query (cfun)->range_of_expr (vr2, m) && !vr0.varying_p ()
> + && !vr0.undefined_p () && !vr1.varying_p () && !vr1.undefined_p ()
> + && !vr2.varying_p () && !vr2.undefined_p ())
> + {
> + signop sgn = TYPE_SIGN (type);
> + if (!TYPE_OVERFLOW_UNDEFINED (type))
> + {
> + if (maybe_mult_overflow (vr1, vr2, sgn))
> + {
> + m = fold_build1 (NEGATE_EXPR, type, m);
How's this valid? 'm' might wrap here? IMHO this special-case
needs a comment. Maybe you try to handle only constant 'm' here
since we tend to canonicalize X - N * 4u to X + N * -4u?
> + if (get_range_query (cfun)->range_of_expr (vr2, m)
> + && !vr2.varying_p () && !vr2.undefined_p ()
> + && !maybe_mult_overflow (vr1, vr2, sgn))
> + code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
> + else
> + return false;
> + }
> +
> + /* Get range of N*M */
> + tree mult = fold_build2 (MULT_EXPR, type, n, m);
Since you are working on GIMPLE 'mult' has an SSA name associated
which should also possibly get you more precise ranges (just capture
it, no need to re-generate a GENERIC expression here).
> + value_range vr3;
> + bool r = get_range_query (cfun)->range_of_expr (vr3, mult);
> + gcc_assert (r && !vr3.varying_p () && !vr3.undefined_p ());
> +
> + bool overflow = code == MINUS_EXPR
> + ? maybe_minus_overflow (vr0, vr3, sgn)
> + : maybe_plus_overflow (vr0, vr3, sgn);
> + if (overflow)
> + return false;
> + }
> +
> + /* The value cross "0" is also a concern. */
> + if (sgn == UNSIGNED)
> + return true;
> + tree op
> + = fold_build2 (code, type, x, fold_build2 (MULT_EXPR, type, n, m));
> + value_range vr4;
Again please use the captured representative here.
> + if (get_range_query (cfun)->range_of_expr (vr4, op) && !vr4.varying_p
> ()
> + && !vr4.undefined_p ())
> + {
> + /* X and (X +- N*M) are both positive (or both negtive). */
> + if ((wi::ge_p (vr0.lower_bound (), 0, sgn)
> + && wi::ge_p (vr4.lower_bound (), 0, sgn))
> + || (wi::le_p (vr0.upper_bound (), 0, sgn)
> + && wi::le_p (vr4.upper_bound (), 0, sgn)))
As noted above I was hoping there's a value-range API for this. We
seem to have set_nonnegative, set_zero, etc. but no way to query
a known sign for integer ranges. FP ranges have signbit_p,
I guess that would work here, too, no?
Andrew?
Seeing the repeated check for !varying && !undefined I wonder if
we can somehow avoid the repetition with a higher level API?
> + return true;
> + }
> + }
> +
> +return false;
> +}
> +
> +/* Return true if there is no overflow and no sign change in "X + C".
> + C is a constant integer. */
> +
> +bool
> +plus_no_ovf_and_keep_sign (tree x, tree c, tree type)
Pass 'c' as const wide_int& here.
> +{
> + value_range vr;
> + if (get_range_query (cfun)->range_of_expr (vr, x) && !vr.varying_p ()
> + && !vr.undefined_p ())
> + {
> + wi::overflow_type ovf = wi::OVF_NONE;
> + wide_int min = vr.lower_bound ();
> + wide_int max = vr.upper_bound ();
> + wide_int wc = wi::to_wide (c);
> + if (!TYPE_OVERFLOW_UNDEFINED (type))
> + {
> + if (tree_int_cst_sign_bit (c))
> + wi::sub (min, -wc, TYPE_SIGN (type), &ovf);
> + else
> + wi::add (max, wc, TYPE_SIGN (type), &ovf);
> + }
> + if (ovf == wi::OVF_NONE)
> + /* unsigned, or 't' and 't + C' are both positive/negative. */
> + if (TYPE_UNSIGNED (type)
> + || (wi::ge_p (min, 0, SIGNED) && wi::ge_p (min + wc, 0, SIGNED))
the second compare should be the same as wi::ge_p (min, -wc, SIGNED) or
are you implicitely checking for overflow here?
> + || (wi::le_p (max, 0, SIGNED) && wi::le_p (max + wc, 0, SIGNED)))
> + return true;
> + }
> +
> + return false;
> +}
> diff --git a/gcc/gimple-fold.h b/gcc/gimple-fold.h
> index 2fd58db9a2e..45df86a433e 100644
> --- a/gcc/gimple-fold.h
> +++ b/gcc/gimple-fold.h
> @@ -64,6 +64,9 @@ extern gimple_seq rewrite_to_defined_overflow (gimple *,
> bool = false);
> extern void replace_call_with_value (gimple_stmt_iterator *, tree);
> extern tree tree_vec_extract (gimple_stmt_iterator *, tree, tree, tree,
> tree);
> extern void gsi_replace_with_seq_vops (gimple_stmt_iterator *, gimple_seq);
> +extern bool maybe_mult_overflow (tree, tree, tree);
> +extern bool plus_mult_no_ovf_and_keep_sign (tree, tree, tree, tree_code,
> tree);
> +extern bool plus_no_ovf_and_keep_sign (tree, tree, tree);
>
> /* gimple_build, functionally matching fold_buildN, outputs stmts
> int the provided sequence, matching and simplifying them on-the-fly.
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 16482b741ea..6f7a6afdca8 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -942,6 +942,64 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> #endif
> ))))
>
> +#if GIMPLE
> +(for div (trunc_div exact_div)
> + /* Simplify (t + M*N) / N -> t / N + M. */
> + (simplify
> + (div (plus:c @0 (mult:c @1 @2)) @2)
> + (if (INTEGRAL_TYPE_P (type)
> + && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, PLUS_EXPR, type))
> + (plus (div @0 @2) @1)))
> +
> + /* Simplify (t - M*N) / N -> t / N - M. */
> + (simplify
> + (div (minus @0 (mult:c @1 @2)) @2)
> + (if (INTEGRAL_TYPE_P (type)
> + && plus_mult_no_ovf_and_keep_sign (@0, @1, @2, MINUS_EXPR, type))
> + (minus (div @0 @2) @1)))
> +
> + /* Simplify (t + C) / N -> t / N + C / N where C is multiple of N */
> + (simplify
> + (div (plus @0 INTEGER_CST@1) INTEGER_CST@2)
> + (with
> + { tree repaired_c = @1;
> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> + repaired_c = fold_build1 (NEGATE_EXPR, type, @1);
What if @1 is 0x80000000? Please consider re-doing this with
wide_int from the start.
> + }
> + (if (INTEGRAL_TYPE_P (type)
> + && multiple_of_p (type, repaired_c, @2)
> + && plus_no_ovf_and_keep_sign (@0, @1, type))
> + (with
> + { wide_int m;
> + wide_int c = wi::to_wide (@1);
> + wide_int n = wi::to_wide (@2);
> + wi::overflow_type ovf;
> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> + m = -wi::div_trunc (-c, n, TYPE_SIGN (type), &ovf);
> + else
> + m = wi::div_trunc (c, n, TYPE_SIGN (type), &ovf);
> + gcc_assert (ovf == wi::OVF_NONE);
> + }
> + (plus (div @0 @2) { wide_int_to_tree(type, m); }))))))
> +
> +/* Simplify (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */
> +(simplify
> + (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2)
> + (if (INTEGRAL_TYPE_P (type) && !tree_int_cst_sign_bit (@2)
> + && wi::ctz (wi::to_wide (@1)) >= wi::to_wide (@2).to_shwi ()
> + && plus_no_ovf_and_keep_sign (@0, @1, type))
> + (with
> + { wide_int m;
> + wide_int c = wi::to_wide (@1);
> + wide_int n = wi::to_wide (@2);
> + if (TYPE_UNSIGNED (type) && tree_int_cst_sign_bit (@1))
> + m = -wi::rshift (-c, n, TYPE_SIGN (type));
> + else
> + m = wi::rshift (c, n, TYPE_SIGN (type));
> + }
> + (plus (rshift @0 @2) { wide_int_to_tree(type, m); }))))
> +#endif
> +
> (for op (negate abs)
> /* Simplify cos(-x) and cos(|x|) -> cos(x). Similarly for cosh. */
> (for coss (COS COSH)
> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c
> b/gcc/testsuite/gcc.dg/pr108757-1.c
> new file mode 100644
> index 00000000000..7e7b60c756d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c
> @@ -0,0 +1,18 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +#include <limits.h>
> +#define N 5
> +#define M 3
> +#define GAP 0
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " "optimized" }
> } *
> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " "optimized" }
> } */
> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c
> b/gcc/testsuite/gcc.dg/pr108757-2.c
> new file mode 100644
> index 00000000000..2a9ad234e68
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c
> @@ -0,0 +1,19 @@
> +/* PR tree-optimization/108757 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */
> +
> +#include <limits.h>
> +#define N 4
> +#define M 3
> +#define GAP 2
> +typedef unsigned int UINT;
> +typedef int INT;
> +#define UMAX UINT_MAX
> +#define IMAX INT_MAX
> +#define IMIN INT_MIN
> +#include "pr108757.h"
> +
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16
> "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 4
> "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 "optimized"
> } } */
> +
> diff --git a/gcc/testsuite/gcc.dg/pr108757.h b/gcc/testsuite/gcc.dg/pr108757.h
> new file mode 100644
> index 00000000000..9dfa527f533
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr108757.h
> @@ -0,0 +1,244 @@
> +#define NOINLINE __attribute__ ((noinline))
> +UINT NOINLINE
> +opt_u1 (UINT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + UINT a = x - (M * N);
> + UINT b = a / N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u2 (UINT x)
> +{
> + if (x > (UMAX - (M * N) + GAP))
> + return 0;
> + UINT a = x + (M * N);
> + UINT b = a / N;
> + return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s1 (INT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s2 (INT x)
> +{
> + if (x < IMIN + (M * N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s3 (INT x)
> +{
> + if (x < (M * N) - GAP)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / -N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s4 (INT x)
> +{
> + if (x < IMIN + (M * N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M * N);
> + INT b = a / -N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s5 (INT x)
> +{
> + if (x > (-M * N) + GAP)
> + return 0;
> + INT a = x - (-M * N);
> + INT b = a / N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s6 (INT x)
> +{
> + if (x > IMAX - (M * N) + GAP || x < 0)
> + return 0;
> + INT a = x - (-M * N);
> + INT b = a / N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s7 (INT x)
> +{
> + if (x > (M * -N) + GAP)
> + return 0;
> + INT a = x - (M * -N);
> + INT b = a / -N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s8 (INT x)
> +{
> + if (x > IMAX - (M * N) + GAP || x < 0)
> + return 0;
> + INT a = x - (M * -N);
> + INT b = a / -N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u3 (UINT x)
> +{
> + if (x < (M << N) - GAP)
> + return 0;
> + UINT a = x - (M << N);
> + UINT b = a >> N;
> + return b + M;
> +}
> +
> +UINT NOINLINE
> +opt_u4 (UINT x)
> +{
> + if (x > (UMAX - (M << N)) + GAP)
> + return 0;
> + UINT a = x + (M << N);
> + UINT b = a >> N;
> + return b - M;
> +}
> +
> +INT NOINLINE
> +opt_s9 (INT x)
> +{
> + if (x < (M << N) - GAP)
> + return 0;
> + INT a = x - (M << N);
> + INT b = a >> N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s10 (INT x)
> +{
> + if (x < IMIN + (M << N) - GAP || x > 0)
> + return 0;
> + INT a = x - (M << N);
> + INT b = a >> N;
> + return b + M;
> +}
> +
> +INT NOINLINE
> +opt_s11 (INT x)
> +{
> + if (x > (-M << N) + GAP)
> + return 0;
> + INT a = x - (-M << N);
> + INT b = a >> N;
> + return b + -M;
> +}
> +
> +INT NOINLINE
> +opt_s12 (INT x)
> +{
> + if (x > IMAX - (M << N) + GAP || x < 0)
> + return 0;
> + INT a = x - (-M << N);
> + INT b = a >> N;
> + return b + -M;
> +}
> +
> +UINT NOINLINE
> +opt_u5 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m > M)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + UINT a = x - (m * n);
> + UINT b = a / n;
> + return b + m;
> +}
> +
> +UINT NOINLINE
> +opt_u6 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m > M)
> + return 0;
> + if (x > (UMAX - M*N) + GAP)
> + return 0;
> + UINT a = x + (m * n);
> + UINT b = a / n;
> + return b - m;
> +}
> +
> +INT NOINLINE
> +opt_s13 (INT x, INT n, INT m)
> +{
> + if (n > N || m > M || n < 0 || m < 0)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + INT a = x - (m * n);
> + INT b = a / n;
> + return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s14 (INT x, INT n, INT m)
> +{
> + if (n > N || m > M || n < 0 || m < 0)
> + return 0;
> + if (x > -M*N + GAP)
> + return 0;
> + INT a = x + (m * n);
> + INT b = a / n;
> + return b - m;
> +}
> +
> +INT
> +opt_s15 (INT x, INT n, INT m)
> +{
> + if (n > 0 || m > 0 || n < -N || m < -M)
> + return 0;
> + if (x < (M*N) - GAP)
> + return 0;
> + INT a = x - (m * n);
> + INT b = a / n;
> + return b + m;
> +}
> +
> +INT NOINLINE
> +opt_s16 (INT x, INT n, INT m)
> +{
> + if (n > 0 || m > 0 || n < -N || m < -M)
> + return 0;
> + if (x < 0 || x > (IMAX - M*N) + GAP)
> + return 0;
> + INT a = x + (m * n);
> + INT b = a / n;
> + return b - m;
> +}
> +
> +UINT NOINLINE
> +opt_u7 (UINT x, UINT n, UINT m)
> +{
> + if (n > N || m <= UMAX - M)
> + return 0;
> + if (x > UMAX - (M*N) + GAP)
> + return 0;
> + UINT a = x - (m * n);
> + UINT b = a / n;
> + return b + m;
> +}
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)
