Re: match.pd: Three new patterns

[Marek Polacek <polacek at redhat dot com>]

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-(x&y)) -> x|y
> since it decomposes as
> y-(x&y) -> y&~x
> x+(y&~x) -> x|y
> x+(y-(x|y)) -> x-(x&~y) -> x&y 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  <polacek@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 { scan-tree-dump-not " & " "cddce1" } } */
+/* { 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