match.pd: unsigned A - B > A --> A < B

Hello,

the first part is something that was discussed last stage3, and Jakub 
argued in favor of single_use. The second part is probably less useful, it 
notices that if we manually check for overflow using the result of 
IFN_*_OVERFLOW, then we might as well read that information from the 
result of that function.

Bootstrap+regtest on powerpc64le-unknown-linux-gnu. (hmm, I probably 
should have done it on x86_64 instead, I don't know if the ppc backend has 
implemented the overflow functions recently)

2016-04-25  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* match.pd (A - B > A, A + B < A): New transformations.

gcc/testsuite/
 	* gcc.dg/tree-ssa/overflow-2.c: New testcase.
 	* gcc.dg/tree-ssa/minus-ovf.c: Likewise.

On Sun, Apr 24, 2016 at 7:42 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> the first part is something that was discussed last stage3, and Jakub argued
> in favor of single_use. The second part is probably less useful, it notices
> that if we manually check for overflow using the result of IFN_*_OVERFLOW,
> then we might as well read that information from the result of that
> function.
>
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu. (hmm, I probably should
> have done it on x86_64 instead, I don't know if the ppc backend has
> implemented the overflow functions recently)

Ok.  Can you please place the match.pd rules adjacent to the other comparison
simplifications rather than at the end?

Thanks,
Richard.

> 2016-04-25  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * match.pd (A - B > A, A + B < A): New transformations.
>
> gcc/testsuite/
>         * gcc.dg/tree-ssa/overflow-2.c: New testcase.
>         * gcc.dg/tree-ssa/minus-ovf.c: Likewise.
>
> --
> Marc Glisse
> Index: trunk-ovf2/gcc/match.pd
> ===================================================================
> --- trunk-ovf2/gcc/match.pd     (revision 235371)
> +++ trunk-ovf2/gcc/match.pd     (working copy)
> @@ -3071,10 +3071,60 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  (simplify
>   /* signbit(x) -> 0 if x is nonnegative.  */
>   (SIGNBIT tree_expr_nonnegative_p@0)
>   { integer_zero_node; })
>
>  (simplify
>   /* signbit(x) -> x<0 if x doesn't have signed zeros.  */
>   (SIGNBIT @0)
>   (if (!HONOR_SIGNED_ZEROS (@0))
>    (convert (lt @0 { build_real (TREE_TYPE (@0), dconst0); }))))
> +
> +/* To detect overflow in unsigned A - B, A < B is simpler than A - B > A.
> +   However, the detection logic for SUB_OVERFLOW in tree-ssa-math-opts.c
> +   expects the long form, so we restrict the transformation for now.  */
> +(for cmp (gt le)
> + (simplify
> +  (cmp (minus@2 @0 @1) @0)
> +  (if (single_use (@2)
> +       && ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +       && TYPE_UNSIGNED (TREE_TYPE (@0))
> +       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)))
> +   (cmp @1 @0))))
> +(for cmp (lt ge)
> + (simplify
> +  (cmp @0 (minus@2 @0 @1))
> +  (if (single_use (@2)
> +       && ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +       && TYPE_UNSIGNED (TREE_TYPE (@0))
> +       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0)))
> +   (cmp @0 @1))))
> +
> +/* Testing for overflow is unnecessary if we already know the result.  */
> +/* A < A - B  */
> +(for cmp (lt ge)
> +     out (ne eq)
> + (simplify
> +  (cmp @0 (realpart (IFN_SUB_OVERFLOW@2 @0 @1)))
> +  (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
> +   (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
> +/* A - B > A  */
> +(for cmp (gt le)
> +     out (ne eq)
> + (simplify
> +  (cmp (realpart (IFN_SUB_OVERFLOW@2 @0 @1)) @0)
> +  (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
> +   (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
> +/* A + B < A  */
> +(for cmp (lt ge)
> +     out (ne eq)
> + (simplify
> +  (cmp (realpart (IFN_ADD_OVERFLOW:c@2 @0 @1)) @0)
> +  (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
> +   (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
> +/* A > A + B  */
> +(for cmp (gt le)
> +     out (ne eq)
> + (simplify
> +  (cmp @0 (realpart (IFN_ADD_OVERFLOW:c@2 @0 @1)))
> +  (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
> +   (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); }))))
> Index: trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/minus-ovf.c
> ===================================================================
> --- trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/minus-ovf.c        (revision 0)
> +++ trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/minus-ovf.c        (working
> copy)
> @@ -0,0 +1,24 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-optimized" } */
> +
> +int f(unsigned a, unsigned b) {
> +  unsigned remove = a - b;
> +  return remove > a;
> +}
> +
> +int g(unsigned a, unsigned b) {
> +  unsigned remove = a - b;
> +  return remove <= a;
> +}
> +
> +int h(unsigned a, unsigned b) {
> +  unsigned remove = a - b;
> +  return a < remove;
> +}
> +
> +int i(unsigned a, unsigned b) {
> +  unsigned remove = a - b;
> +  return a >= remove;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "remove" "optimized" } } */
> Index: trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/overflow-2.c
> ===================================================================
> --- trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/overflow-2.c       (revision 0)
> +++ trunk-ovf2/gcc/testsuite/gcc.dg/tree-ssa/overflow-2.c       (working
> copy)
> @@ -0,0 +1,68 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized-raw" } */
> +
> +int carry;
> +int f(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_sub_overflow(a, b, &r);
> +  return r > a;
> +}
> +int g(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_sub_overflow(a, b, &r);
> +  return a < r;
> +}
> +int h(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_sub_overflow(a, b, &r);
> +  return r <= a;
> +}
> +int i(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_sub_overflow(a, b, &r);
> +  return a >= r;
> +}
> +int j(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return r < a;
> +}
> +int j2(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return r < b;
> +}
> +int k(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return a > r;
> +}
> +int k2(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return b > r;
> +}
> +int l(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return r >= a;
> +}
> +int l2(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return r >= b;
> +}
> +int m(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return a <= r;
> +}
> +int m2(unsigned a, unsigned b) {
> +  unsigned r;
> +  carry = __builtin_add_overflow(a, b, &r);
> +  return b <= r;
> +}
> +
> +/* { dg-final { scan-tree-dump-not "(le|lt|ge|gt)_expr" "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "ADD_OVERFLOW" 8 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "SUB_OVERFLOW" 4 "optimized" } } */
>