Re: match.pd: Three new patterns

[Richard Biener]

On Mon, 22 Jun 2015, Marek Polacek wrote:

 On Fri, Jun 19, 2015 at 05:51:53PM +0200, Marc Glisse wrote:
  On Fri, 19 Jun 2015, Marek Polacek wrote:
  
  +/* x + y - (x | y) - x  y */
  +(simplify
  + (minus (plus @0 @1) (bit_ior @0 @1))
  + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
  +  (bit_and @0 @1)))
  +
  +/* (x + y) - (x  y) - x | y */
  +(simplify
  + (minus (plus @0 @1) (bit_and @0 @1))
  + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
  +  (bit_ior @0 @1)))
  
  It could be macroized so they are handled by the same piece of code, but
  that's not important for a couple lines.
  
 Yeah, that could be done, but I didn't see much value in doing that.
 
  As far as I can tell, TYPE_SATURATING is for fixed point numbers only, are
  we allowed to use bit_ior/bit_and on those? I never know what kind of
  integers are supposed to be supported, so I would have checked
  TYPE_OVERFLOW_UNDEFINED (type) || TYPE_OVERFLOW_WRAPS (type) since those are
  the 2 cases where we know it is safe (for TYPE_OVERFLOW_TRAPS it is never
  clear if we are supposed to preserve traps or just avoid introducing new
  ones). Well, the reviewer will know, I'll shut up :-)
  
 I think you're right about TYPE_SATURATING so I've dropped that and instead
 replaced it with TYPE_OVERFLOW_TRAPS.  That should do the right thing
 together with TYPE_OVERFLOW_SANITIZED.

Are you sure?  The point is that if the minus or the plus in the original
expression saturate the result isn't correct, no?

  (I still believe that the necessity for TYPE_OVERFLOW_SANITIZED here points
  to a design issue in ubsan, but it is way too late to discuss that)
 
 I think delayed folding would help here a bit.  Also, we've been talking
 about doing the signed overflow sanitization earlier, but so far I didn't
 implement that.  And -ftrapv should be merged into the ubsan infrastructure
 some day.
 
  It is probably not worth the trouble adding the variant:
  x+(y-(xy)) - x|y
  since it decomposes as
  y-(xy) - y~x
  x+(y~x) - x|y
  x+(y-(x|y)) - x-(x~y) - xy is less likely to happen because the first
  transform y-(x|y) - -(x~y) increases the number of insns. Bah, we can't
  handle everything...
 
 That sounds about right ;).  Thanks!
 
 So, Richi, is this variant ok as well?  I also added one ubsan test.

As said, removing TYPE_SATURATING doesn't sound correct.  I'm not sure
about TYPE_OVERFLOW_TRAPS - we're certainly removing traps elsewhere
(look for the scarce use of this flag in fold-const.c and match.pd
where I only preserved those that were originally in fold-const.c).

So, TYPE_OVERFLOW_TRAPS is your choice but TYPE_SATURATING is
required IMHO.

Richard.

 Bootstrapped/regtested on x86_64-linux, ok for trunk?
 
 2015-06-22  Marek Polacek  pola...@redhat.com
 
   * match.pd ((x + y) - (x | y) - x  y,
   (x + y) - (x  y) - x | y): New patterns.
 
   * gcc.dg/fold-minus-4.c: New test.
   * gcc.dg/fold-minus-5.c: New test.
   * c-c++-common/ubsan/overflow-add-5.c: New test.
 
 diff --git gcc/match.pd gcc/match.pd
 index badb80a..6d520ef 100644
 --- gcc/match.pd
 +++ gcc/match.pd
 @@ -343,6 +343,18 @@ along with GCC; see the file COPYING3.  If not see
   (plus:c (bit_and @0 @1) (bit_ior @0 @1))
   (plus @0 @1))
  
 +/* (x + y) - (x | y) - x  y */
 +(simplify
 + (minus (plus @0 @1) (bit_ior @0 @1))
 + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_OVERFLOW_TRAPS (type))
 +  (bit_and @0 @1)))
 +
 +/* (x + y) - (x  y) - x | y */
 +(simplify
 + (minus (plus @0 @1) (bit_and @0 @1))
 + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_OVERFLOW_TRAPS (type))
 +  (bit_ior @0 @1)))
 +
  /* (x | y) - (x ^ y) - x  y */
  (simplify
   (minus (bit_ior @0 @1) (bit_xor @0 @1))
 diff --git gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c 
 gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
 index e69de29..905a60a 100644
 --- gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
 +++ gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
 @@ -0,0 +1,30 @@
 +/* { dg-do run } */
 +/* { dg-options -fsanitize=signed-integer-overflow } */
 +
 +int __attribute__ ((noinline))
 +foo (int i, int j)
 +{
 +  return (i + j) - (i | j);
 +}
 +
 +/* { dg-output signed integer overflow: 2147483647 \\+ 1 cannot be 
 represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
 +/* { dg-output \[^\n\r]*signed integer overflow: -2147483648 - 2147483647 
 cannot be represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
 +
 +int __attribute__ ((noinline))
 +bar (int i, int j)
 +{
 +  return (i + j) - (i  j);
 +}
 +
 +/* { dg-output \[^\n\r]*signed integer overflow: 2147483647 \\+ 1 cannot be 
 represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
 +/* { dg-output \[^\n\r]*signed integer overflow: -2147483648 - 1 cannot be 
 represented in type 'int' } */
 +
 +int
 +main ()
 +{
 +  int r = foo (__INT_MAX__, 1);
 +  asm volatile ( : +g (r));
 +  r = bar (__INT_MAX__, 1);
 +  asm volatile ( : +g (r));
 +  return 0;
 +}
 diff --git gcc/testsuite/gcc.dg/fold-minus-4.c 
 

Re: match.pd: Three new patterns

[Richard Biener]

On Tue, 23 Jun 2015, Marek Polacek wrote:

 On Tue, Jun 23, 2015 at 09:56:33AM +0200, Richard Biener wrote:
   I think you're right about TYPE_SATURATING so I've dropped that and 
   instead
   replaced it with TYPE_OVERFLOW_TRAPS.  That should do the right thing
   together with TYPE_OVERFLOW_SANITIZED.
  
  Are you sure?  The point is that if the minus or the plus in the original
  expression saturate the result isn't correct, no?
  
 Yes, but I thought that TYPE_SATURATING is only true for fixed-point, i.e.
 those _Accum/_Sat/_Fract (?), and you can't do bitwise  or | on them, which
 means that the TYPE_SATURATING check wouldn't be necessary.

Who says you can't do bitwise ops on them?  I can't see that being
enforced in the GIMPLE checking in tree-cfg.c.  Yes, there is no
such thing as a saturating bitwise and but bitwise and should
just work fine.

You can check with a arm cross what the C FE does when you use
bitwise ops but I believe the regular and/ior md patterns work
just fine (there are no special modes/registers but they seem
to be shared with regular registers, just special operations
are available).

Richard.

 
  As said, removing TYPE_SATURATING doesn't sound correct.  I'm not sure
  about TYPE_OVERFLOW_TRAPS - we're certainly removing traps elsewhere
  (look for the scarce use of this flag in fold-const.c and match.pd
  where I only preserved those that were originally in fold-const.c).
  
  So, TYPE_OVERFLOW_TRAPS is your choice but TYPE_SATURATING is
  required IMHO.
 
 Ok, I guess I'll add TYPE_SATURATING back, even though I'm not clear
 on that one, and commit.
 
 Thanks,
 
   Marek
 
 

-- 
Richard Biener rguent...@suse.de
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham 
Norton, HRB 21284 (AG Nuernberg)

Re: match.pd: Three new patterns

[Marek Polacek]

On Tue, Jun 23, 2015 at 09:56:33AM +0200, Richard Biener wrote:
  I think you're right about TYPE_SATURATING so I've dropped that and instead
  replaced it with TYPE_OVERFLOW_TRAPS.  That should do the right thing
  together with TYPE_OVERFLOW_SANITIZED.
 
 Are you sure?  The point is that if the minus or the plus in the original
 expression saturate the result isn't correct, no?
 
Yes, but I thought that TYPE_SATURATING is only true for fixed-point, i.e.
those _Accum/_Sat/_Fract (?), and you can't do bitwise  or | on them, which
means that the TYPE_SATURATING check wouldn't be necessary.

 As said, removing TYPE_SATURATING doesn't sound correct.  I'm not sure
 about TYPE_OVERFLOW_TRAPS - we're certainly removing traps elsewhere
 (look for the scarce use of this flag in fold-const.c and match.pd
 where I only preserved those that were originally in fold-const.c).
 
 So, TYPE_OVERFLOW_TRAPS is your choice but TYPE_SATURATING is
 required IMHO.

Ok, I guess I'll add TYPE_SATURATING back, even though I'm not clear
on that one, and commit.

Thanks,

Marek

Re: match.pd: Three new patterns

[Marek Polacek]

On Tue, Jun 23, 2015 at 10:22:35AM +0200, Richard Biener wrote:
 Who says you can't do bitwise ops on them?  I can't see that being
 enforced in the GIMPLE checking in tree-cfg.c.  Yes, there is no
 such thing as a saturating bitwise and but bitwise and should
 just work fine.
 
 You can check with a arm cross what the C FE does when you use
 bitwise ops but I believe the regular and/ior md patterns work
 just fine (there are no special modes/registers but they seem
 to be shared with regular registers, just special operations
 are available).

Ok ;).  Applied the following then.

2015-06-23  Marek Polacek  pola...@redhat.com

* match.pd ((x + y) - (x | y) - x  y,
(x + y) - (x  y) - x | y): New patterns.

* gcc.dg/fold-minus-4.c: New test.
* gcc.dg/fold-minus-5.c: New test.
* c-c++-common/ubsan/overflow-add-5.c: New test.

diff --git gcc/match.pd gcc/match.pd
index badb80a..9c88e3e 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -343,6 +343,20 @@ along with GCC; see the file COPYING3.  If not see
  (plus:c (bit_and @0 @1) (bit_ior @0 @1))
  (plus @0 @1))
 
+/* (x + y) - (x | y) - x  y */
+(simplify
+ (minus (plus @0 @1) (bit_ior @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_OVERFLOW_TRAPS (type)
+   !TYPE_SATURATING (type))
+  (bit_and @0 @1)))
+
+/* (x + y) - (x  y) - x | y */
+(simplify
+ (minus (plus @0 @1) (bit_and @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_OVERFLOW_TRAPS (type)
+   !TYPE_SATURATING (type))
+  (bit_ior @0 @1)))
+
 /* (x | y) - (x ^ y) - x  y */
 (simplify
  (minus (bit_ior @0 @1) (bit_xor @0 @1))
diff --git gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c 
gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
index e69de29..905a60a 100644
--- gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
+++ gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
@@ -0,0 +1,30 @@
+/* { dg-do run } */
+/* { dg-options -fsanitize=signed-integer-overflow } */
+
+int __attribute__ ((noinline))
+foo (int i, int j)
+{
+  return (i + j) - (i | j);
+}
+
+/* { dg-output signed integer overflow: 2147483647 \\+ 1 cannot be 
represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
+/* { dg-output \[^\n\r]*signed integer overflow: -2147483648 - 2147483647 
cannot be represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
+
+int __attribute__ ((noinline))
+bar (int i, int j)
+{
+  return (i + j) - (i  j);
+}
+
+/* { dg-output \[^\n\r]*signed integer overflow: 2147483647 \\+ 1 cannot be 
represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
+/* { dg-output \[^\n\r]*signed integer overflow: -2147483648 - 1 cannot be 
represented in type 'int' } */
+
+int
+main ()
+{
+  int r = foo (__INT_MAX__, 1);
+  asm volatile ( : +g (r));
+  r = bar (__INT_MAX__, 1);
+  asm volatile ( : +g (r));
+  return 0;
+}
diff --git gcc/testsuite/gcc.dg/fold-minus-4.c 
gcc/testsuite/gcc.dg/fold-minus-4.c
index e69de29..2d76b4f 100644
--- gcc/testsuite/gcc.dg/fold-minus-4.c
+++ gcc/testsuite/gcc.dg/fold-minus-4.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-notcddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
diff --git gcc/testsuite/gcc.dg/fold-minus-5.c 
gcc/testsuite/gcc.dg/fold-minus-5.c
index e69de29..a31e1cc 100644
--- gcc/testsuite/gcc.dg/fold-minus-5.c
+++ gcc/testsuite/gcc.dg/fold-minus-5.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = a | b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = a | b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = b | a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = b | a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */

Marek

Re: match.pd: Three new patterns

[Marek Polacek]

On Fri, Jun 19, 2015 at 05:51:53PM +0200, Marc Glisse wrote:
 On Fri, 19 Jun 2015, Marek Polacek wrote:
 
 +/* x + y - (x | y) - x  y */
 +(simplify
 + (minus (plus @0 @1) (bit_ior @0 @1))
 + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
 +  (bit_and @0 @1)))
 +
 +/* (x + y) - (x  y) - x | y */
 +(simplify
 + (minus (plus @0 @1) (bit_and @0 @1))
 + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
 +  (bit_ior @0 @1)))
 
 It could be macroized so they are handled by the same piece of code, but
 that's not important for a couple lines.
 
Yeah, that could be done, but I didn't see much value in doing that.

 As far as I can tell, TYPE_SATURATING is for fixed point numbers only, are
 we allowed to use bit_ior/bit_and on those? I never know what kind of
 integers are supposed to be supported, so I would have checked
 TYPE_OVERFLOW_UNDEFINED (type) || TYPE_OVERFLOW_WRAPS (type) since those are
 the 2 cases where we know it is safe (for TYPE_OVERFLOW_TRAPS it is never
 clear if we are supposed to preserve traps or just avoid introducing new
 ones). Well, the reviewer will know, I'll shut up :-)
 
I think you're right about TYPE_SATURATING so I've dropped that and instead
replaced it with TYPE_OVERFLOW_TRAPS.  That should do the right thing
together with TYPE_OVERFLOW_SANITIZED.

 (I still believe that the necessity for TYPE_OVERFLOW_SANITIZED here points
 to a design issue in ubsan, but it is way too late to discuss that)

I think delayed folding would help here a bit.  Also, we've been talking
about doing the signed overflow sanitization earlier, but so far I didn't
implement that.  And -ftrapv should be merged into the ubsan infrastructure
some day.

 It is probably not worth the trouble adding the variant:
 x+(y-(xy)) - x|y
 since it decomposes as
 y-(xy) - y~x
 x+(y~x) - x|y
 x+(y-(x|y)) - x-(x~y) - xy is less likely to happen because the first
 transform y-(x|y) - -(x~y) increases the number of insns. Bah, we can't
 handle everything...

That sounds about right ;).  Thanks!

So, Richi, is this variant ok as well?  I also added one ubsan test.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

2015-06-22  Marek Polacek  pola...@redhat.com

* match.pd ((x + y) - (x | y) - x  y,
(x + y) - (x  y) - x | y): New patterns.

* gcc.dg/fold-minus-4.c: New test.
* gcc.dg/fold-minus-5.c: New test.
* c-c++-common/ubsan/overflow-add-5.c: New test.

diff --git gcc/match.pd gcc/match.pd
index badb80a..6d520ef 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -343,6 +343,18 @@ along with GCC; see the file COPYING3.  If not see
  (plus:c (bit_and @0 @1) (bit_ior @0 @1))
  (plus @0 @1))
 
+/* (x + y) - (x | y) - x  y */
+(simplify
+ (minus (plus @0 @1) (bit_ior @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_OVERFLOW_TRAPS (type))
+  (bit_and @0 @1)))
+
+/* (x + y) - (x  y) - x | y */
+(simplify
+ (minus (plus @0 @1) (bit_and @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_OVERFLOW_TRAPS (type))
+  (bit_ior @0 @1)))
+
 /* (x | y) - (x ^ y) - x  y */
 (simplify
  (minus (bit_ior @0 @1) (bit_xor @0 @1))
diff --git gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c 
gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
index e69de29..905a60a 100644
--- gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
+++ gcc/testsuite/c-c++-common/ubsan/overflow-add-5.c
@@ -0,0 +1,30 @@
+/* { dg-do run } */
+/* { dg-options -fsanitize=signed-integer-overflow } */
+
+int __attribute__ ((noinline))
+foo (int i, int j)
+{
+  return (i + j) - (i | j);
+}
+
+/* { dg-output signed integer overflow: 2147483647 \\+ 1 cannot be 
represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
+/* { dg-output \[^\n\r]*signed integer overflow: -2147483648 - 2147483647 
cannot be represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
+
+int __attribute__ ((noinline))
+bar (int i, int j)
+{
+  return (i + j) - (i  j);
+}
+
+/* { dg-output \[^\n\r]*signed integer overflow: 2147483647 \\+ 1 cannot be 
represented in type 'int'\[^\n\r]*(\n|\r\n|\r) } */
+/* { dg-output \[^\n\r]*signed integer overflow: -2147483648 - 1 cannot be 
represented in type 'int' } */
+
+int
+main ()
+{
+  int r = foo (__INT_MAX__, 1);
+  asm volatile ( : +g (r));
+  r = bar (__INT_MAX__, 1);
+  asm volatile ( : +g (r));
+  return 0;
+}
diff --git gcc/testsuite/gcc.dg/fold-minus-4.c 
gcc/testsuite/gcc.dg/fold-minus-4.c
index e69de29..2d76b4f 100644
--- gcc/testsuite/gcc.dg/fold-minus-4.c
+++ gcc/testsuite/gcc.dg/fold-minus-4.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { 

Re: match.pd: Three new patterns

[Richard Biener]

On Fri, 19 Jun 2015, Marek Polacek wrote:

 On Thu, Jun 18, 2015 at 05:41:18PM +0200, Marek Polacek wrote:
   Again for symmetry, it seems like this comes with
   x + y - (x | y) - x  y
   x + y - (x  y) - x | y
   which seem fine when overflow is undefined or wraps, but not if for 
   instance
   it saturates.
  
  I'll leave this as a follow-up.
 
 ...here.
 
 Bootstrapped/regtested on x86_64-linux, ok for trunk?
 
 2015-06-19  Marek Polacek  pola...@redhat.com
 
   * match.pd (x + y - (x | y) - x  y,

) missing

   (x + y) - (x  y) - x | y): New patterns.
 
   * gcc.dg/fold-minus-4.c: New test.
   * gcc.dg/fold-minus-5.c: New test.
 
 diff --git gcc/match.pd gcc/match.pd
 index badb80a..61ff710 100644
 --- gcc/match.pd
 +++ gcc/match.pd
 @@ -343,6 +343,18 @@ along with GCC; see the file COPYING3.  If not see
   (plus:c (bit_and @0 @1) (bit_ior @0 @1))
   (plus @0 @1))
  
 +/* x + y - (x | y) - x  y */

Please wrap x + y in () here as well.

Ok with that changes.

Thanks,
Richard.

 +(simplify
 + (minus (plus @0 @1) (bit_ior @0 @1))
 + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
 +  (bit_and @0 @1)))
 +
 +/* (x + y) - (x  y) - x | y */
 +(simplify
 + (minus (plus @0 @1) (bit_and @0 @1))
 + (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
 +  (bit_ior @0 @1)))
 +
  /* (x | y) - (x ^ y) - x  y */
  (simplify
   (minus (bit_ior @0 @1) (bit_xor @0 @1))
 diff --git gcc/testsuite/gcc.dg/fold-minus-4.c 
 gcc/testsuite/gcc.dg/fold-minus-4.c
 index e69de29..2d76b4f 100644
 --- gcc/testsuite/gcc.dg/fold-minus-4.c
 +++ gcc/testsuite/gcc.dg/fold-minus-4.c
 @@ -0,0 +1,37 @@
 +/* { dg-do compile } */
 +/* { dg-options -O -fdump-tree-cddce1 } */
 +
 +int
 +fn1 (int a, int b)
 +{
 +  int tem1 = a + b;
 +  int tem2 = a  b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn2 (int a, int b)
 +{
 +  int tem1 = b + a;
 +  int tem2 = a  b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn3 (int a, int b)
 +{
 +  int tem1 = a + b;
 +  int tem2 = b  a;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn4 (int a, int b)
 +{
 +  int tem1 = b + a;
 +  int tem2 = b  a;
 +  return tem1 - tem2;
 +}
 +
 +/* { dg-final { scan-tree-dump-notcddce1 } } */
 +/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
 diff --git gcc/testsuite/gcc.dg/fold-minus-5.c 
 gcc/testsuite/gcc.dg/fold-minus-5.c
 index e69de29..a31e1cc 100644
 --- gcc/testsuite/gcc.dg/fold-minus-5.c
 +++ gcc/testsuite/gcc.dg/fold-minus-5.c
 @@ -0,0 +1,37 @@
 +/* { dg-do compile } */
 +/* { dg-options -O -fdump-tree-cddce1 } */
 +
 +int
 +fn1 (int a, int b)
 +{
 +  int tem1 = a + b;
 +  int tem2 = a | b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn2 (int a, int b)
 +{
 +  int tem1 = b + a;
 +  int tem2 = a | b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn3 (int a, int b)
 +{
 +  int tem1 = a + b;
 +  int tem2 = b | a;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn4 (int a, int b)
 +{
 +  int tem1 = b + a;
 +  int tem2 = b | a;
 +  return tem1 - tem2;
 +}
 +
 +/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
 +/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */
 
   Marek
 
 

-- 
Richard Biener rguent...@suse.de
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham 
Norton, HRB 21284 (AG Nuernberg)

Re: match.pd: Three new patterns (and some more)

[Richard Biener]

On Thu, 18 Jun 2015, Marek Polacek wrote:

 On Tue, Jun 16, 2015 at 03:35:15PM +0200, Richard Biener wrote:
  We already have
  
  /* (x  y) ^ (x | y) - x ^ y */
  (simplify
   (bit_xor:c (bit_and @0 @1) (bit_ior @0 @1))
   (bit_xor @0 @1))
  
  but of course with minus it doesn't commutate so it's hard to
  merge.
 
 Yeah :(.
  
+/* (x  y) + (x | y) - x + y */
   
   Again for symmetry, it seems like this comes with
   x + y - (x | y) - x  y
   x + y - (x  y) - x | y
   which seem fine when overflow is undefined or wraps, but not if for 
   instance
   it saturates.
  
  Can you adjust according to Marcs comment and re-submit?  If you like
  you can do it as followup as well and thus the original patch is ok
  as well.
 
 Sure.  This is a new version with some more patters.  Thanks.
 
 Bootstrapped/regtested on x86_64-linux, ok for trunk?

Ok.

Thanks,
Richard.

 2015-06-18  Marek Polacek  pola...@redhat.com
 
   * match.pd ((x ^ y) ^ (x | y) - x  y,
   (x  y) + (x ^ y) - x | y, (x  y) | (x ^ y) - x | y,
   (x  y) ^ (x ^ y) - x | y, (x  y) + (x | y) - x + y,
   (x | y) - (x ^ y) - x  y, (x | y) - (x  y) - x ^ y): New patterns.
 
   * gcc.dg/fold-ior-1.c: New test.
   * gcc.dg/fold-minus-2.c: New test.
   * gcc.dg/fold-minus-3.c: New test.
   * gcc.dg/fold-plus-1.c: New test.
   * gcc.dg/fold-plus-2.c: New test.
   * gcc.dg/fold-xor-4.c: New test.
   * gcc.dg/fold-xor-5.c: New test.
 
 diff --git gcc/match.pd gcc/match.pd
 index 1ab2b1c..badb80a 100644
 --- gcc/match.pd
 +++ gcc/match.pd
 @@ -325,6 +325,34 @@ along with GCC; see the file COPYING3.  If not see
   (bit_xor:c (bit_and @0 @1) (bit_ior @0 @1))
   (bit_xor @0 @1))
  
 +/* (x ^ y) ^ (x | y) - x  y */
 +(simplify
 + (bit_xor:c (bit_xor @0 @1) (bit_ior @0 @1))
 + (bit_and @0 @1))
 +
 +/* (x  y) + (x ^ y) - x | y */
 +/* (x  y) | (x ^ y) - x | y */
 +/* (x  y) ^ (x ^ y) - x | y */
 +(for op (plus bit_ior bit_xor)
 + (simplify
 +  (op:c (bit_and @0 @1) (bit_xor @0 @1))
 +  (bit_ior @0 @1)))
 +
 +/* (x  y) + (x | y) - x + y */
 +(simplify
 + (plus:c (bit_and @0 @1) (bit_ior @0 @1))
 + (plus @0 @1))
 +
 +/* (x | y) - (x ^ y) - x  y */
 +(simplify
 + (minus (bit_ior @0 @1) (bit_xor @0 @1))
 + (bit_and @0 @1))
 +
 +/* (x | y) - (x  y) - x ^ y */
 +(simplify
 + (minus (bit_ior @0 @1) (bit_and @0 @1))
 + (bit_xor @0 @1))
 +
  (simplify
   (abs (negate @0))
   (abs @0))
 diff --git gcc/testsuite/gcc.dg/fold-ior-1.c gcc/testsuite/gcc.dg/fold-ior-1.c
 index e69de29..0358eb5 100644
 --- gcc/testsuite/gcc.dg/fold-ior-1.c
 +++ gcc/testsuite/gcc.dg/fold-ior-1.c
 @@ -0,0 +1,69 @@
 +/* { dg-do compile } */
 +/* { dg-options -O -fdump-tree-cddce1 } */
 +
 +int
 +fn1 (int a, int b)
 +{
 +  int tem1 = a  b;
 +  int tem2 = a ^ b;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn2 (int a, int b)
 +{
 +  int tem1 = b  a;
 +  int tem2 = a ^ b;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn3 (int a, int b)
 +{
 +  int tem1 = a  b;
 +  int tem2 = b ^ a;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn4 (int a, int b)
 +{
 +  int tem1 = b  a;
 +  int tem2 = b ^ a;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn5 (int a, int b)
 +{
 +  int tem1 = a ^ b;
 +  int tem2 = a  b;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn6 (int a, int b)
 +{
 +  int tem1 = b ^ a;
 +  int tem2 = a  b;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn7 (int a, int b)
 +{
 +  int tem1 = a ^ b;
 +  int tem2 = b  a;
 +  return tem1 | tem2;
 +}
 +
 +int
 +fn8 (int a, int b)
 +{
 +  int tem1 = b ^ a;
 +  int tem2 = b  a;
 +  return tem1 | tem2;
 +}
 +
 +/* { dg-final { scan-tree-dump-notcddce1 } } */
 +/* { dg-final { scan-tree-dump-not  \\^  cddce1 } } */
 diff --git gcc/testsuite/gcc.dg/fold-minus-2.c 
 gcc/testsuite/gcc.dg/fold-minus-2.c
 index e69de29..6501f2f 100644
 --- gcc/testsuite/gcc.dg/fold-minus-2.c
 +++ gcc/testsuite/gcc.dg/fold-minus-2.c
 @@ -0,0 +1,37 @@
 +/* { dg-do compile } */
 +/* { dg-options -O -fdump-tree-cddce1 } */
 +
 +int
 +fn1 (int a, int b)
 +{
 +  int tem1 = a | b;
 +  int tem2 = a ^ b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn2 (int a, int b)
 +{
 +  int tem1 = b | a;
 +  int tem2 = a ^ b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn3 (int a, int b)
 +{
 +  int tem1 = a | b;
 +  int tem2 = b ^ a;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn4 (int a, int b)
 +{
 +  int tem1 = b | a;
 +  int tem2 = b ^ a;
 +  return tem1 - tem2;
 +}
 +
 +/* { dg-final { scan-tree-dump-not  \\^  cddce1 } } */
 +/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */
 diff --git gcc/testsuite/gcc.dg/fold-minus-3.c 
 gcc/testsuite/gcc.dg/fold-minus-3.c
 index e69de29..e7adce6 100644
 --- gcc/testsuite/gcc.dg/fold-minus-3.c
 +++ gcc/testsuite/gcc.dg/fold-minus-3.c
 @@ -0,0 +1,37 @@
 +/* { dg-do compile } */
 +/* { dg-options -O -fdump-tree-cddce1 } */
 +
 +int
 +fn1 (int a, int b)
 +{
 +  int tem1 = a | b;
 +  int tem2 = a  b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn2 (int a, int b)
 +{
 +  int tem1 = b | a;
 +  int tem2 = a  b;
 +  return tem1 - tem2;
 +}
 +
 +int
 +fn3 (int a, int b)
 

Re: match.pd: Three new patterns

[Marek Polacek]

On Thu, Jun 18, 2015 at 05:41:18PM +0200, Marek Polacek wrote:
  Again for symmetry, it seems like this comes with
  x + y - (x | y) - x  y
  x + y - (x  y) - x | y
  which seem fine when overflow is undefined or wraps, but not if for instance
  it saturates.
 
 I'll leave this as a follow-up.

...here.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

2015-06-19  Marek Polacek  pola...@redhat.com

* match.pd (x + y - (x | y) - x  y,
(x + y) - (x  y) - x | y): New patterns.

* gcc.dg/fold-minus-4.c: New test.
* gcc.dg/fold-minus-5.c: New test.

diff --git gcc/match.pd gcc/match.pd
index badb80a..61ff710 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -343,6 +343,18 @@ along with GCC; see the file COPYING3.  If not see
  (plus:c (bit_and @0 @1) (bit_ior @0 @1))
  (plus @0 @1))
 
+/* x + y - (x | y) - x  y */
+(simplify
+ (minus (plus @0 @1) (bit_ior @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
+  (bit_and @0 @1)))
+
+/* (x + y) - (x  y) - x | y */
+(simplify
+ (minus (plus @0 @1) (bit_and @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
+  (bit_ior @0 @1)))
+
 /* (x | y) - (x ^ y) - x  y */
 (simplify
  (minus (bit_ior @0 @1) (bit_xor @0 @1))
diff --git gcc/testsuite/gcc.dg/fold-minus-4.c 
gcc/testsuite/gcc.dg/fold-minus-4.c
index e69de29..2d76b4f 100644
--- gcc/testsuite/gcc.dg/fold-minus-4.c
+++ gcc/testsuite/gcc.dg/fold-minus-4.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-notcddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
diff --git gcc/testsuite/gcc.dg/fold-minus-5.c 
gcc/testsuite/gcc.dg/fold-minus-5.c
index e69de29..a31e1cc 100644
--- gcc/testsuite/gcc.dg/fold-minus-5.c
+++ gcc/testsuite/gcc.dg/fold-minus-5.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = a | b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = a | b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a + b;
+  int tem2 = b | a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b + a;
+  int tem2 = b | a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */

Marek

Re: match.pd: Three new patterns

[Marc Glisse]

On Fri, 19 Jun 2015, Marek Polacek wrote:


+/* x + y - (x | y) - x  y */
+(simplify
+ (minus (plus @0 @1) (bit_ior @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
+  (bit_and @0 @1)))
+
+/* (x + y) - (x  y) - x | y */
+(simplify
+ (minus (plus @0 @1) (bit_and @0 @1))
+ (if (!TYPE_OVERFLOW_SANITIZED (type)  !TYPE_SATURATING (type))
+  (bit_ior @0 @1)))


It could be macroized so they are handled by the same piece of code, but 
that's not important for a couple lines.


As far as I can tell, TYPE_SATURATING is for fixed point numbers only, are 
we allowed to use bit_ior/bit_and on those? I never know what kind of 
integers are supposed to be supported, so I would have checked 
TYPE_OVERFLOW_UNDEFINED (type) || TYPE_OVERFLOW_WRAPS (type) since those 
are the 2 cases where we know it is safe (for TYPE_OVERFLOW_TRAPS it is 
never clear if we are supposed to preserve traps or just avoid introducing 
new ones). Well, the reviewer will know, I'll shut up :-)


(I still believe that the necessity for TYPE_OVERFLOW_SANITIZED here 
points to a design issue in ubsan, but it is way too late to discuss that)


It is probably not worth the trouble adding the variant:
x+(y-(xy)) - x|y
since it decomposes as
y-(xy) - y~x
x+(y~x) - x|y
x+(y-(x|y)) - x-(x~y) - xy is less likely to happen because the first 
transform y-(x|y) - -(x~y) increases the number of insns. Bah, we can't 
handle everything...


--
Marc Glisse

Re: match.pd: Three new patterns

[Marek Polacek]

On Sat, Jun 13, 2015 at 12:05:42PM +0200, Marc Glisse wrote:
 They look fine to me.

Thanks!
 
 +/* (x  y) + (x ^ y) - x | y */
 
 This also works if you replace + with | or ^.

Done.
 
 +/* (x | y) - (x ^ y) - x  y */
 
 For symmetry, you probably also want:
 (x | y) - (x  y) - x ^ y
 
Done.

 (they both also work with ^ instead of -)

Done (except (x  y) ^ (x | y) - x ^ y which we already have).

 +/* (x  y) + (x | y) - x + y */
 
 Again for symmetry, it seems like this comes with
 x + y - (x | y) - x  y
 x + y - (x  y) - x | y
 which seem fine when overflow is undefined or wraps, but not if for instance
 it saturates.

I'll leave this as a follow-up.

Testing a new patch.  Thanks again.

Marek

Re: match.pd: Three new patterns (and some more)

[Marek Polacek]

On Tue, Jun 16, 2015 at 03:35:15PM +0200, Richard Biener wrote:
 We already have
 
 /* (x  y) ^ (x | y) - x ^ y */
 (simplify
  (bit_xor:c (bit_and @0 @1) (bit_ior @0 @1))
  (bit_xor @0 @1))
 
 but of course with minus it doesn't commutate so it's hard to
 merge.

Yeah :(.
 
   +/* (x  y) + (x | y) - x + y */
  
  Again for symmetry, it seems like this comes with
  x + y - (x | y) - x  y
  x + y - (x  y) - x | y
  which seem fine when overflow is undefined or wraps, but not if for instance
  it saturates.
 
 Can you adjust according to Marcs comment and re-submit?  If you like
 you can do it as followup as well and thus the original patch is ok
 as well.

Sure.  This is a new version with some more patters.  Thanks.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

2015-06-18  Marek Polacek  pola...@redhat.com

* match.pd ((x ^ y) ^ (x | y) - x  y,
(x  y) + (x ^ y) - x | y, (x  y) | (x ^ y) - x | y,
(x  y) ^ (x ^ y) - x | y, (x  y) + (x | y) - x + y,
(x | y) - (x ^ y) - x  y, (x | y) - (x  y) - x ^ y): New patterns.

* gcc.dg/fold-ior-1.c: New test.
* gcc.dg/fold-minus-2.c: New test.
* gcc.dg/fold-minus-3.c: New test.
* gcc.dg/fold-plus-1.c: New test.
* gcc.dg/fold-plus-2.c: New test.
* gcc.dg/fold-xor-4.c: New test.
* gcc.dg/fold-xor-5.c: New test.

diff --git gcc/match.pd gcc/match.pd
index 1ab2b1c..badb80a 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -325,6 +325,34 @@ along with GCC; see the file COPYING3.  If not see
  (bit_xor:c (bit_and @0 @1) (bit_ior @0 @1))
  (bit_xor @0 @1))
 
+/* (x ^ y) ^ (x | y) - x  y */
+(simplify
+ (bit_xor:c (bit_xor @0 @1) (bit_ior @0 @1))
+ (bit_and @0 @1))
+
+/* (x  y) + (x ^ y) - x | y */
+/* (x  y) | (x ^ y) - x | y */
+/* (x  y) ^ (x ^ y) - x | y */
+(for op (plus bit_ior bit_xor)
+ (simplify
+  (op:c (bit_and @0 @1) (bit_xor @0 @1))
+  (bit_ior @0 @1)))
+
+/* (x  y) + (x | y) - x + y */
+(simplify
+ (plus:c (bit_and @0 @1) (bit_ior @0 @1))
+ (plus @0 @1))
+
+/* (x | y) - (x ^ y) - x  y */
+(simplify
+ (minus (bit_ior @0 @1) (bit_xor @0 @1))
+ (bit_and @0 @1))
+
+/* (x | y) - (x  y) - x ^ y */
+(simplify
+ (minus (bit_ior @0 @1) (bit_and @0 @1))
+ (bit_xor @0 @1))
+
 (simplify
  (abs (negate @0))
  (abs @0))
diff --git gcc/testsuite/gcc.dg/fold-ior-1.c gcc/testsuite/gcc.dg/fold-ior-1.c
index e69de29..0358eb5 100644
--- gcc/testsuite/gcc.dg/fold-ior-1.c
+++ gcc/testsuite/gcc.dg/fold-ior-1.c
@@ -0,0 +1,69 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a  b;
+  int tem2 = a ^ b;
+  return tem1 | tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b  a;
+  int tem2 = a ^ b;
+  return tem1 | tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a  b;
+  int tem2 = b ^ a;
+  return tem1 | tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b  a;
+  int tem2 = b ^ a;
+  return tem1 | tem2;
+}
+
+int
+fn5 (int a, int b)
+{
+  int tem1 = a ^ b;
+  int tem2 = a  b;
+  return tem1 | tem2;
+}
+
+int
+fn6 (int a, int b)
+{
+  int tem1 = b ^ a;
+  int tem2 = a  b;
+  return tem1 | tem2;
+}
+
+int
+fn7 (int a, int b)
+{
+  int tem1 = a ^ b;
+  int tem2 = b  a;
+  return tem1 | tem2;
+}
+
+int
+fn8 (int a, int b)
+{
+  int tem1 = b ^ a;
+  int tem2 = b  a;
+  return tem1 | tem2;
+}
+
+/* { dg-final { scan-tree-dump-notcddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\^  cddce1 } } */
diff --git gcc/testsuite/gcc.dg/fold-minus-2.c 
gcc/testsuite/gcc.dg/fold-minus-2.c
index e69de29..6501f2f 100644
--- gcc/testsuite/gcc.dg/fold-minus-2.c
+++ gcc/testsuite/gcc.dg/fold-minus-2.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = a ^ b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = a ^ b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = b ^ a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = b ^ a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-not  \\^  cddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */
diff --git gcc/testsuite/gcc.dg/fold-minus-3.c 
gcc/testsuite/gcc.dg/fold-minus-3.c
index e69de29..e7adce6 100644
--- gcc/testsuite/gcc.dg/fold-minus-3.c
+++ gcc/testsuite/gcc.dg/fold-minus-3.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = a  b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = b  a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */
+/* { dg-final { scan-tree-dump-notcddce1 } } 

Re: match.pd: Three new patterns

[Richard Biener]

On Sat, 13 Jun 2015, Marc Glisse wrote:

 They look fine to me.
 
  +/* (x  y) + (x ^ y) - x | y */
 
 This also works if you replace + with | or ^.

  +/* (x | y) - (x ^ y) - x  y */
 
 For symmetry, you probably also want:
 (x | y) - (x  y) - x ^ y
 
 (they both also work with ^ instead of -)

We already have

/* (x  y) ^ (x | y) - x ^ y */
(simplify
 (bit_xor:c (bit_and @0 @1) (bit_ior @0 @1))
 (bit_xor @0 @1))

but of course with minus it doesn't commutate so it's hard to
merge.

  +/* (x  y) + (x | y) - x + y */
 
 Again for symmetry, it seems like this comes with
 x + y - (x | y) - x  y
 x + y - (x  y) - x | y
 which seem fine when overflow is undefined or wraps, but not if for instance
 it saturates.

Can you adjust according to Marcs comment and re-submit?  If you like
you can do it as followup as well and thus the original patch is ok
as well.

Thanks,
Richard.

Re: match.pd: Three new patterns

[Marc Glisse]

They look fine to me.


+/* (x  y) + (x ^ y) - x | y */


This also works if you replace + with | or ^.


+/* (x | y) - (x ^ y) - x  y */


For symmetry, you probably also want:
(x | y) - (x  y) - x ^ y

(they both also work with ^ instead of -)


+/* (x  y) + (x | y) - x + y */


Again for symmetry, it seems like this comes with
x + y - (x | y) - x  y
x + y - (x  y) - x | y
which seem fine when overflow is undefined or wraps, but not if for 
instance it saturates.


--
Marc Glisse

match.pd: Three new patterns

[Marek Polacek]

This patch brings three new patterns for match.pd.  I think these are
rare, but it shouldn't hurt to have them.
(I suppose you'd be happier if I was moving patterns from fold-const to
match.pd.  I'll work on that as well.)

Given previous discussion, I don't think there's much to say otherwise,
but I'd appreciate if someone could glance over this.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

2015-06-12  Marek Polacek  pola...@redhat.com

* match.pd ((x  y) + (x ^ y) - x | y,
(x  y) + (x | y) - x + y,
(x | y) - (x ^ y) - x  y): New patterns.

* gcc.dg/fold-plus-1.c: New test.
* gcc.dg/fold-plus-2.c: New test.
* gcc.dg/fold-minus-2.c: New test.

--- gcc/match.pd
+++ gcc/match.pd
@@ -325,6 +325,21 @@ along with GCC; see the file COPYING3.  If not see
  (bit_xor:c (bit_and @0 @1) (bit_ior @0 @1))
  (bit_xor @0 @1))
 
+/* (x  y) + (x ^ y) - x | y */
+(simplify
+ (plus:c (bit_and @0 @1) (bit_xor @0 @1))
+ (bit_ior @0 @1))
+
+/* (x  y) + (x | y) - x + y */
+(simplify
+ (plus:c (bit_and @0 @1) (bit_ior @0 @1))
+ (plus @0 @1))
+
+/* (x | y) - (x ^ y) - x  y */
+(simplify
+ (minus (bit_ior @0 @1) (bit_xor @0 @1))
+ (bit_and @0 @1))
+
 (simplify
  (abs (negate @0))
  (abs @0))
--- gcc/testsuite/gcc.dg/fold-plus-1.c
+++ gcc/testsuite/gcc.dg/fold-plus-1.c
@@ -0,0 +1,70 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a  b;
+  int tem2 = a ^ b;
+  return tem1 + tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b  a;
+  int tem2 = a ^ b;
+  return tem1 + tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a  b;
+  int tem2 = b ^ a;
+  return tem1 + tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b  a;
+  int tem2 = b ^ a;
+  return tem1 + tem2;
+}
+
+int
+fn5 (int a, int b)
+{
+  int tem1 = a ^ b;
+  int tem2 = a  b;
+  return tem1 + tem2;
+}
+
+int
+fn6 (int a, int b)
+{
+  int tem1 = b ^ a;
+  int tem2 = a  b;
+  return tem1 + tem2;
+}
+
+int
+fn7 (int a, int b)
+{
+  int tem1 = a ^ b;
+  int tem2 = b  a;
+  return tem1 + tem2;
+}
+
+int
+fn8 (int a, int b)
+{
+  int tem1 = b ^ a;
+  int tem2 = b  a;
+  return tem1 + tem2;
+}
+
+/* { dg-final { scan-tree-dump-notcddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\^  cddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\+  cddce1 } } */
--- gcc/testsuite/gcc.dg/fold-plus-2.c
+++ gcc/testsuite/gcc.dg/fold-plus-2.c
@@ -0,0 +1,69 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a  b;
+  int tem2 = a | b;
+  return tem1 + tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b  a;
+  int tem2 = a | b;
+  return tem1 + tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a  b;
+  int tem2 = b | a;
+  return tem1 + tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b  a;
+  int tem2 = b | a;
+  return tem1 + tem2;
+}
+
+int
+fn5 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = a  b;
+  return tem1 + tem2;
+}
+
+int
+fn6 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = a  b;
+  return tem1 + tem2;
+}
+
+int
+fn7 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = b  a;
+  return tem1 + tem2;
+}
+
+int
+fn8 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = b  a;
+  return tem1 + tem2;
+}
+
+/* { dg-final { scan-tree-dump-notcddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */
--- gcc/testsuite/gcc.dg/fold-minus-2.c
+++ gcc/testsuite/gcc.dg/fold-minus-2.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-cddce1 } */
+
+int
+fn1 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = a ^ b;
+  return tem1 - tem2;
+}
+
+int
+fn2 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = a ^ b;
+  return tem1 - tem2;
+}
+
+int
+fn3 (int a, int b)
+{
+  int tem1 = a | b;
+  int tem2 = b ^ a;
+  return tem1 - tem2;
+}
+
+int
+fn4 (int a, int b)
+{
+  int tem1 = b | a;
+  int tem2 = b ^ a;
+  return tem1 - tem2;
+}
+
+/* { dg-final { scan-tree-dump-not  \\^  cddce1 } } */
+/* { dg-final { scan-tree-dump-not  \\|  cddce1 } } */

Marek