Drop Z from X + Z < Y + Z

Drop Z from X + Z < Y + Z

[Marc Glisse]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 999 bytes --]

Hello,

surprisingly, this did not cause any Wstrict-overflow failure. Some of it 
sounds more like reassoc's job, but it is convenient to handle simple 
cases in match.pd. I think we could wait until there are reports of 
regressions related to register pressure before adding single_use tests.

For a std::vector<long> v, we now simplify v.size()==v.capacity() to a 
single comparison (long)finish==(long)end_storage (I guess I could still 
try to drop the casts to consider it really done). Handling 
v.size()<v.capacity() seems much harder, because of C++'s questionable 
choice to use unsigned types. I may still be able to remove the divisions, 
I'll see if I can sprinkle some 'convert' in recent transformations.

Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

2017-04-28  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* match.pd (X+Z CMP Y+Z, X-Z CMP Y-Z, Z-X CMP Z-Y): New
 	transformations.

gcc/testsuite/
 	* gcc.dg/tree-ssa/cmpexactdiv-2.c: Update for X-Z CMP Y-Z.

-- 
Marc Glisse

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-diff; name=cmpadd.patch, Size: 3514 bytes --]

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 247362)
+++ gcc/match.pd	(working copy)
@@ -1035,20 +1035,68 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	&& wi::neg_p (@1, TYPE_SIGN (TREE_TYPE (@1))))
     (cmp @2 @0))))))
 
 /* X / 4 < Y / 4 iff X < Y when the division is known to be exact.  */
 (for cmp (simple_comparison)
  (simplify
   (cmp (exact_div @0 INTEGER_CST@2) (exact_div @1 @2))
   (if (wi::gt_p(@2, 0, TYPE_SIGN (TREE_TYPE (@2))))
    (cmp @0 @1))))
 
+/* X + Z < Y + Z iff X < Y when there is no overflow.  */
+(for cmp (lt le ge gt)
+ (simplify
+  (cmp (plus:c @0 @2) (plus:c @1 @2))
+  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
+   (cmp @0 @1))))
+/* For ==, this is also true with wrapping overflow.  */
+(for cmp (eq ne minus)
+ (simplify
+  (cmp (plus:c @0 @2) (plus:c @1 @2))
+  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
+	   || TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))))
+   (cmp @0 @1))))
+
+/* X - Z < Y - Z iff X < Y when there is no overflow.  */
+(for cmp (lt le ge gt)
+ (simplify
+  (cmp (minus @0 @2) (minus @1 @2))
+  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
+   (cmp @0 @1))))
+/* For ==, this is also true with wrapping overflow.  */
+(for cmp (eq ne minus)
+ (simplify
+  (cmp (minus @0 @2) (minus @1 @2))
+  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
+	   || TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))))
+   (cmp @0 @1))))
+
+/* Z - X < Z - Y iff Y < X when there is no overflow.  */
+(for cmp (lt le ge gt)
+ (simplify
+  (cmp (minus @2 @0) (minus @2 @1))
+  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
+   (cmp @1 @0))))
+/* For ==, this is also true with wrapping overflow.  */
+(for cmp (eq ne minus)
+ (simplify
+  (cmp (minus @2 @0) (minus @2 @1))
+  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
+	   || TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))))
+   (cmp @1 @0))))
+
 /* ((X inner_op C0) outer_op C1)
    With X being a tree where value_range has reasoned certain bits to always be
    zero throughout its computed value range,
    inner_op = {|,^}, outer_op = {|,^} and inner_op != outer_op
    where zero_mask has 1's for all bits that are sure to be 0 in
    and 0's otherwise.
    if (inner_op == '^') C0 &= ~C1;
    if ((C0 & ~zero_mask) == 0) then emit (X outer_op (C0 outer_op C1)
    if ((C1 & ~zero_mask) == 0) then emit (X inner_op (C0 outer_op C1)
 */
Index: gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-2.c	(revision 247362)
+++ gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-2.c	(working copy)
@@ -1,11 +1,11 @@
 /* { dg-do compile } */
-/* { dg-options "-O -fdump-tree-optimized-raw" } */
+/* { dg-options "-O -fstrict-overflow -fdump-tree-optimized-raw" } */
 
 int f (long *a, long *b, long *c) {
     __PTRDIFF_TYPE__ l1 = b - a;
     __PTRDIFF_TYPE__ l2 = c - a;
     return l1 < l2;
 }
 
-/* Eventually we also want to remove all minus_expr.  */
+/* { dg-final { scan-tree-dump-not "minus_expr" "optimized" } } */
 /* { dg-final { scan-tree-dump-not "exact_div_expr" "optimized" } } */

Re: Drop Z from X + Z < Y + Z

[Richard Biener]

On Fri, Apr 28, 2017 at 1:35 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> surprisingly, this did not cause any Wstrict-overflow failure. Some of it
> sounds more like reassoc's job, but it is convenient to handle simple cases
> in match.pd. I think we could wait until there are reports of regressions
> related to register pressure before adding single_use tests.
>
> For a std::vector<long> v, we now simplify v.size()==v.capacity() to a
> single comparison (long)finish==(long)end_storage (I guess I could still try
> to drop the casts to consider it really done). Handling
> v.size()<v.capacity() seems much harder, because of C++'s questionable
> choice to use unsigned types. I may still be able to remove the divisions,
> I'll see if I can sprinkle some 'convert' in recent transformations.
>
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

+(for cmp (eq ne minus)

Fat fingered 'minus' (in all places) or did you want to get fancy?
(the transforms
look valid even for cmp == minus)  Maybe adjust comments to reflect this.

There are a few related cases in fold-const.c, namely X +- Y CMP X -> Y CMP 0,
some of them also handling POINTER_PLUS_EXPR.  So I wonder if you can
handle pointer_plus like plus and maybe move those fold-const.c patterns.
Can be done as followup of course.

Ok with minus removed or comments adjusted.

Thanks,
Richard.

> 2017-04-28  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * match.pd (X+Z CMP Y+Z, X-Z CMP Y-Z, Z-X CMP Z-Y): New
>         transformations.
>
> gcc/testsuite/
>         * gcc.dg/tree-ssa/cmpexactdiv-2.c: Update for X-Z CMP Y-Z.
>
> --
> Marc Glisse

Re: Drop Z from X + Z < Y + Z

[Jakub Jelinek]

On Fri, Apr 28, 2017 at 02:25:55PM +0200, Richard Biener wrote:
> On Fri, Apr 28, 2017 at 1:35 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> > Hello,
> >
> > surprisingly, this did not cause any Wstrict-overflow failure. Some of it
> > sounds more like reassoc's job, but it is convenient to handle simple cases
> > in match.pd. I think we could wait until there are reports of regressions
> > related to register pressure before adding single_use tests.
> >
> > For a std::vector<long> v, we now simplify v.size()==v.capacity() to a
> > single comparison (long)finish==(long)end_storage (I guess I could still try
> > to drop the casts to consider it really done). Handling
> > v.size()<v.capacity() seems much harder, because of C++'s questionable
> > choice to use unsigned types. I may still be able to remove the divisions,
> > I'll see if I can sprinkle some 'convert' in recent transformations.
> >
> > Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
> 
> +(for cmp (eq ne minus)
> 
> Fat fingered 'minus' (in all places) or did you want to get fancy?
> (the transforms
> look valid even for cmp == minus)  Maybe adjust comments to reflect this.

If minus is intended, it might be better to use op instead of cmp for the
iterator.

	Jakub

Re: Drop Z from X + Z < Y + Z

[Marc Glisse]

On Fri, 28 Apr 2017, Richard Biener wrote:

> On Fri, Apr 28, 2017 at 1:35 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> surprisingly, this did not cause any Wstrict-overflow failure. Some of it
>> sounds more like reassoc's job, but it is convenient to handle simple cases
>> in match.pd. I think we could wait until there are reports of regressions
>> related to register pressure before adding single_use tests.
>>
>> For a std::vector<long> v, we now simplify v.size()==v.capacity() to a
>> single comparison (long)finish==(long)end_storage (I guess I could still try
>> to drop the casts to consider it really done). Handling
>> v.size()<v.capacity() seems much harder, because of C++'s questionable
>> choice to use unsigned types. I may still be able to remove the divisions,
>> I'll see if I can sprinkle some 'convert' in recent transformations.
>>
>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>
> +(for cmp (eq ne minus)
>
> Fat fingered 'minus' (in all places) or did you want to get fancy?
> (the transforms
> look valid even for cmp == minus)  Maybe adjust comments to reflect this.

I started with just comparisons and then noticed that minus worked as 
well. I'll adjust the comment and rename cmp to op as suggested by Jakub. 
I may have to separate the minus case when I add converts in a future 
patch.

> There are a few related cases in fold-const.c, namely X +- Y CMP X -> Y CMP 0,
> some of them also handling POINTER_PLUS_EXPR.  So I wonder if you can
> handle pointer_plus like plus and maybe move those fold-const.c patterns.

You already added (T)(P + A) - (T)(P + B) -> (T)A - (T)B, so I'll have to 
take care to avoid redundancy. Since it was meant for pointer_plus more 
than plus, you used convert, not convert?, and it is currently not 
redundant with my patch. If I integrate pointer_plus in the same 
transformation, I will probably have to use :C instead of :c, and we will 
get 2 dead paths (operand_equal_p on the first argument of one 
pointer_plus and the second argument of another pointer_plus), it might be 
easier as a separate pattern.

-- 
Marc Glisse

Re: Drop Z from X + Z < Y + Z

[Richard Biener]

On Fri, Apr 28, 2017 at 10:23 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Fri, 28 Apr 2017, Richard Biener wrote:
>
>> On Fri, Apr 28, 2017 at 1:35 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>
>>> Hello,
>>>
>>> surprisingly, this did not cause any Wstrict-overflow failure. Some of it
>>> sounds more like reassoc's job, but it is convenient to handle simple
>>> cases
>>> in match.pd. I think we could wait until there are reports of regressions
>>> related to register pressure before adding single_use tests.
>>>
>>> For a std::vector<long> v, we now simplify v.size()==v.capacity() to a
>>> single comparison (long)finish==(long)end_storage (I guess I could still
>>> try
>>> to drop the casts to consider it really done). Handling
>>> v.size()<v.capacity() seems much harder, because of C++'s questionable
>>> choice to use unsigned types. I may still be able to remove the
>>> divisions,
>>> I'll see if I can sprinkle some 'convert' in recent transformations.
>>>
>>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>>
>>
>> +(for cmp (eq ne minus)
>>
>> Fat fingered 'minus' (in all places) or did you want to get fancy?
>> (the transforms
>> look valid even for cmp == minus)  Maybe adjust comments to reflect this.
>
>
> I started with just comparisons and then noticed that minus worked as well.
> I'll adjust the comment and rename cmp to op as suggested by Jakub. I may
> have to separate the minus case when I add converts in a future patch.
>
>> There are a few related cases in fold-const.c, namely X +- Y CMP X -> Y
>> CMP 0,
>> some of them also handling POINTER_PLUS_EXPR.  So I wonder if you can
>> handle pointer_plus like plus and maybe move those fold-const.c patterns.
>
>
> You already added (T)(P + A) - (T)(P + B) -> (T)A - (T)B, so I'll have to
> take care to avoid redundancy. Since it was meant for pointer_plus more than
> plus, you used convert, not convert?, and it is currently not redundant with
> my patch. If I integrate pointer_plus in the same transformation, I will
> probably have to use :C instead of :c, and we will get 2 dead paths
> (operand_equal_p on the first argument of one pointer_plus and the second
> argument of another pointer_plus), it might be easier as a separate pattern.

Yes.   Just spotted the few patterns in fold-const.c when searching for things
doing the transform you add.

Richard.

> --
> Marc Glisse