Simple reassoc transforms in match.pd

Simple reassoc transforms in match.pd

[Marc Glisse]

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

Hello,

here are a few simple transformations, mostly useful for types with 
undefined overflow where we do not have reassoc.

I did not name the testcase reassoc-* to leave that namespace to the 
realloc pass, and -fno-tree-reassoc is just in case someone ever enhances 
that pass...

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

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

gcc/
 	* match.pd ((A+-B)+(C-A), (A+B)-(A-C)): New transformations.

gcc/testsuite/
 	* gcc.dg/tree-ssa/assoc-1.c: New file.

-- 
Marc Glisse

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

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 249585)
+++ gcc/match.pd	(working copy)
@@ -1314,20 +1314,32 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (negate @1))
   (simplify
     (plus:c (minus @0 @1) @1)
     @0)
   (simplify
    (minus @0 (plus:c @0 @1))
    (negate @1))
   (simplify
    (minus @0 (minus @0 @1))
    @1)
+  /* (A +- B) + (C - A)   -> C +- B */
+  /* (A +  B) - (A - C)   -> B + C */
+  /* More cases are handled with comparisons.  */
+  (simplify
+   (plus:c (plus:c @0 @1) (minus @2 @0))
+   (plus @2 @1))
+  (simplify
+   (plus:c (minus @0 @1) (minus @2 @0))
+   (minus @2 @1))
+  (simplify
+   (minus (plus:c @0 @1) (minus @0 @2))
+   (plus @1 @2))
 
   /* (A +- CST1) +- CST2 -> A + CST3
      Use view_convert because it is safe for vectors and equivalent for
      scalars.  */
   (for outer_op (plus minus)
    (for inner_op (plus minus)
 	neg_inner_op (minus plus)
     (simplify
      (outer_op (nop_convert (inner_op @0 CONSTANT_CLASS_P@1))
 	       CONSTANT_CLASS_P@2)
Index: gcc/testsuite/gcc.dg/tree-ssa/assoc-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/assoc-1.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/assoc-1.c	(working copy)
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw -fno-tree-reassoc" } */
+
+int f0(int a,int b,int c){
+  int d = a + b;
+  int e = c + b;
+  return d - e;
+}
+int f1(int a,int b,int c){
+  int d = a + b;
+  int e = b - c;
+  return d - e;
+}
+int f2(int a,int b,int c){
+  int d = a + b;
+  int e = c - b;
+  return e + d;
+}
+int f3(int a,int b,int c){
+  int d = a - b;
+  int e = c - b;
+  return d - e;
+}
+int f4(int a,int b,int c){
+  int d = b - a;
+  int e = c - b;
+  return e + d;
+}
+
+/* { dg-final { scan-tree-dump-times "plus_expr" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "minus_expr" 3 "optimized" } } */

Re: Simple reassoc transforms in match.pd

[Richard Biener]

On Fri, Jun 23, 2017 at 3:12 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> here are a few simple transformations, mostly useful for types with
> undefined overflow where we do not have reassoc.
>
> I did not name the testcase reassoc-* to leave that namespace to the realloc
> pass, and -fno-tree-reassoc is just in case someone ever enhances that
> pass...

You probably saw

  /* (T)(P + A) - (T)(P + B) -> (T)A - (T)B */
  (for add (plus pointer_plus)
   (simplify
    (minus (convert (add @@0 @1))
     (convert (add @0 @2)))

as you didn't duplicate its functionality.  It misses a :c in one of
the adds for the
PLUS_EXPR case though so it might be worth splitting that out near to your
added cases?  Which then raises the question of handling conversions around
the inner ops in your patterns?

I think the patch is ok as-is but we could improve this as a followup maybe?

Thanks,
Richard.

> Bootstrap + testsuite on powerpc64le-unknown-linux-gnu.
>
> 2017-06-23  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * match.pd ((A+-B)+(C-A), (A+B)-(A-C)): New transformations.
>
> gcc/testsuite/
>         * gcc.dg/tree-ssa/assoc-1.c: New file.
>
> --
> Marc Glisse

Re: Simple reassoc transforms in match.pd

[Marc Glisse]

On Mon, 26 Jun 2017, Richard Biener wrote:

> On Fri, Jun 23, 2017 at 3:12 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> here are a few simple transformations, mostly useful for types with
>> undefined overflow where we do not have reassoc.
>>
>> I did not name the testcase reassoc-* to leave that namespace to the realloc
>> pass, and -fno-tree-reassoc is just in case someone ever enhances that
>> pass...
>
> You probably saw
>
>  /* (T)(P + A) - (T)(P + B) -> (T)A - (T)B */
>  (for add (plus pointer_plus)
>   (simplify
>    (minus (convert (add @@0 @1))
>     (convert (add @0 @2)))

And

/* X + Z < Y + Z is the same as X < Y when there is no overflow.  */
[...]
/* For equality and subtraction, this is also true with wrapping overflow.  */
(for op (eq ne minus)
  (simplify
   (op (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))))
    (op @0 @1))))

> as you didn't duplicate its functionality.  It misses a :c in one of
> the adds for the

For some other transform, I was tempted to write
(for op (plus:c minus) ...
i.e. use a different commutativity for different operations, but that's
not supported.

> PLUS_EXPR case though so it might be worth splitting that out near to your
> added cases?  Which then raises the question of handling conversions around
> the inner ops in your patterns?

It is probably possible to merge / generalize some of those transforms 
(although we sometimes do strange assumptions about overflow with pointers 
that may not match with the usual integer case). In this case, I was 
interested in the undefined-overflow case (more precisely the sum of 2 
pointer_diff), and as soon as one operation is done in a wrapping type, 
the result has to be as well (which could still be handled in the same 
transformation).

-- 
Marc Glisse