Simplify 3*x == 3*y for wrapping types

Simplify 3*x == 3*y for wrapping types

[Marc Glisse]

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

Hello,

I remember wanting to add this when the undefined-overflow case was 
introduced a while ago.

It turns out the tree where I wrote this wasn't clean. Since the rest is 
details, I am including it in this patch, hope it is ok.

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

2017-06-26  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* match.pd ((X & ~Y) | (~X & Y)): Generalize to + and ^.
 	(x * C EQ/NE y * C): New transformation.

gcc/testsuite/
 	* gcc.dg/tree-ssa/addadd.c: Remove test duplicated in addadd-2.c.
 	* gcc.dg/tree-ssa/mulcmp-1.c: New file.

-- 
Marc Glisse

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

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 249623)
+++ gcc/match.pd	(working copy)
@@ -583,28 +583,29 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 (simplify
  (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
  (if (wi::bit_not (@2) == @1)
   (minus (bit_xor @0 @1) @1)))
 
 /* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
 (simplify
  (minus (bit_and:cs @0 @1) (bit_and:cs @0 (bit_not @1)))
   (minus @1 (bit_xor @0 @1)))
 
-/* Simplify (X & ~Y) | (~X & Y) -> X ^ Y.  */
-(simplify
- (bit_ior (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
-  (bit_xor @0 @1))
-(simplify
- (bit_ior:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1))
- (if (wi::bit_not (@2) == @1)
-  (bit_xor @0 @1)))
+/* Simplify (X & ~Y) |^+ (~X & Y) -> X ^ Y.  */
+(for op (bit_ior bit_xor plus)
+ (simplify
+  (op (bit_and:c @0 (bit_not @1)) (bit_and:c (bit_not @0) @1))
+   (bit_xor @0 @1))
+ (simplify
+  (op:c (bit_and @0 INTEGER_CST@2) (bit_and (bit_not @0) INTEGER_CST@1))
+  (if (wi::bit_not (@2) == @1)
+   (bit_xor @0 @1))))
 
 /* PR53979: Transform ((a ^ b) | a) -> (a | b) */
 (simplify
   (bit_ior:c (bit_xor:c @0 @1) @0)
   (bit_ior @0 @1))
 
 /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0.  */
 #if GIMPLE
 (simplify
  (bit_and (bit_not SSA_NAME@0) INTEGER_CST@1)
@@ -1038,20 +1039,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 /* For integral types with undefined overflow and C != 0 fold
    x * C EQ/NE y * C into x EQ/NE y.  */
 (for cmp (eq ne)
  (simplify
   (cmp (mult:c @0 @1) (mult:c @2 @1))
   (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
        && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
        && tree_expr_nonzero_p (@1))
    (cmp @0 @2))))
 
+/* For integral types with wrapping overflow and C odd fold
+   x * C EQ/NE y * C into x EQ/NE y.  */
+(for cmp (eq ne)
+ (simplify
+  (cmp (mult:c @0 INTEGER_CST@1) (mult:c @2 @1))
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
+       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
+       && (TREE_INT_CST_LOW (@1) & 1) != 0)
+   (cmp @0 @2))))
+
 /* For integral types with undefined overflow and C != 0 fold
    x * C RELOP y * C into:
 
    x RELOP y for nonnegative C
    y RELOP x for negative C  */
 (for cmp (lt gt le ge)
  (simplify
   (cmp (mult:c @0 @1) (mult:c @2 @1))
   (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
        && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0)))
Index: gcc/testsuite/gcc.dg/tree-ssa/addadd.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/addadd.c	(revision 249623)
+++ gcc/testsuite/gcc.dg/tree-ssa/addadd.c	(working copy)
@@ -16,19 +16,14 @@ unsigned g(int x){
 int h(int x){
   x += __INT_MAX__;
   x += 1;
   return x;
 }
 int i(int x){
   x += __INT_MAX__;
   x += __INT_MAX__;
   return x;
 }
-typedef int S __attribute__((vector_size(16)));
-void j(S*x){
-  *x += __INT_MAX__;
-  *x += __INT_MAX__;
-}
 
 /* { dg-final { scan-tree-dump-times " \\+ 24;" 2 "optimized" } } */
 /* { dg-final { scan-tree-dump-times "\\(unsigned int\\)" 2 "optimized" } } */
 /* { dg-final { scan-tree-dump-not "2147483647" "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/mulcmp-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/mulcmp-1.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/mulcmp-1.c	(working copy)
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+int f(unsigned a,unsigned b){
+    a *= 3;
+    b *= 3;
+    return a == b;
+}
+
+/* { dg-final { scan-tree-dump-not "mult_expr" "optimized" } } */

Re: Simplify 3*x == 3*y for wrapping types

[Andrew Pinski]

On Sat, Jun 24, 2017 at 5:34 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> I remember wanting to add this when the undefined-overflow case was
> introduced a while ago.
>
> It turns out the tree where I wrote this wasn't clean. Since the rest is
> details, I am including it in this patch, hope it is ok.

You can do the x * C1 == y * C1 optimization for floating point (if
-ffast-math).  That is recorded as PR 31098.

Thanks,
Andrew

>
> Bootstrap + testsuite on powerpc64le-unknown-linux-gnu.
>
> 2017-06-26  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * match.pd ((X & ~Y) | (~X & Y)): Generalize to + and ^.
>         (x * C EQ/NE y * C): New transformation.
>
> gcc/testsuite/
>         * gcc.dg/tree-ssa/addadd.c: Remove test duplicated in addadd-2.c.
>         * gcc.dg/tree-ssa/mulcmp-1.c: New file.
>
> --
> Marc Glisse

Re: Simplify 3*x == 3*y for wrapping types

[Richard Biener]

On Sat, Jun 24, 2017 at 2:34 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> I remember wanting to add this when the undefined-overflow case was
> introduced a while ago.
>
> It turns out the tree where I wrote this wasn't clean. Since the rest is
> details, I am including it in this patch, hope it is ok.

Yeah, that's ok.

Besides eventually handling FP (not required in this patch initially)
I think the mults don't need :c as we should canonicalize the constant
to 2nd operand.

Ok with removing :c

Thanks,
Richard.

> Bootstrap + testsuite on powerpc64le-unknown-linux-gnu.
>
> 2017-06-26  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * match.pd ((X & ~Y) | (~X & Y)): Generalize to + and ^.
>         (x * C EQ/NE y * C): New transformation.
>
> gcc/testsuite/
>         * gcc.dg/tree-ssa/addadd.c: Remove test duplicated in addadd-2.c.
>         * gcc.dg/tree-ssa/mulcmp-1.c: New file.
>
> --
> Marc Glisse

Re: Simplify 3*x == 3*y for wrapping types

[Marc Glisse]

On Mon, 26 Jun 2017, Richard Biener wrote:

> I think the mults don't need :c as we should canonicalize the constant
> to 2nd operand.

Oups, I copied the transformation above (which does need :c) and didn't 
notice it was there. Good catch, thanks.

-- 
Marc Glisse