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

[Marc Glisse <marc dot glisse at inria dot fr>]

On Tue, 26 Apr 2016, Richard Biener wrote:

> 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?

(I did that for the other patch as well)
I just realized that the *_OVERFLOW internal functions do not work the way 
I expected, the arguments and result can be any combination of unrelated 
types, which makes it unlikely that the transforms are safe as they are 
(could be, but that would be a lot of luck).

The patterns have a comparison between @0 and realpart, so at least those 
2 types are (essentially) the same. To be safe, I would add a condition 
that @0 and @1 have (essentially) the same type. Elsewhere we have a 
different condition for generic/gimple, but for such transforms it doesn't 
seem important to do them on generic.

Here is the new patch, with useless_type_conversion_p added. Is that ok?
(I could also drop that part of the patch and commit only the part that 
does not involve builtins)

I'll do another regtest to be sure.

> > 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 235448)
+++ trunk-ovf2/gcc/match.pd	(working copy)
@@ -2501,20 +2501,75 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
      out (gt gt le le)
  (simplify
   (cmp @0 (plus@2 @0 INTEGER_CST@1))
   (if (TYPE_UNSIGNED (TREE_TYPE (@0))
        && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
        && wi::ne_p (@1, 0)
        && single_use (@2))
    (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value
 	       (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); }))))
 
+/* 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.  */
+(if (GIMPLE)
+ /* 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))
+	&& useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (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))
+	&& useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (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))
+	&& useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (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))
+	&& useless_type_conversion_p (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (out (imagpart @2) { build_zero_cst (TREE_TYPE (@0)); })))))
+
 
 /* Simplification of math builtins.  These rules must all be optimizations
    as well as IL simplifications.  If there is a possibility that the new
    form could be a pessimization, the rule should go in the canonicalization
    section that follows this one.
 
    Rules can generally go in this section if they satisfy one of
    the following:
 
    - the rule describes an identity
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" } } */