From 0036218b1093a36a67d7c04834e5c0383eda6efa Mon Sep 17 00:00:00 2001
From: Marc Glisse <marc.glisse@inria.fr>
Date: Tue, 2 Oct 2018 17:02:13 +0200
Subject: [PATCH] ((X /[ex] A) +- B) * A --> X +- A * B

2018-10-02  Marc Glisse  <marc.glisse@inria.fr>

gcc/
	* match.pd (((X /[ex] A) +- B) * A): New transformation.

gcc/testsuite/
	* gcc.dg/tree-ssa/muldiv-1.c: New file.
	* gcc.dg/tree-ssa/muldiv-2.c: Likewise.

From-SVN: r264792
---
 gcc/ChangeLog                            |  4 ++++
 gcc/match.pd                             | 19 +++++++++++++++++++
 gcc/testsuite/ChangeLog                  |  5 +++++
 gcc/testsuite/gcc.dg/tree-ssa/muldiv-1.c | 13 +++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/muldiv-2.c | 12 ++++++++++++
 5 files changed, 53 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/muldiv-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/muldiv-2.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 236f70c52e0..0b67fa62bbf 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,7 @@
+2018-10-02  Marc Glisse  <marc.glisse@inria.fr>
+
+	* match.pd (((X /[ex] A) +- B) * A): New transformation.
+
 2018-10-02  Marc Glisse  <marc.glisse@inria.fr>
 
 	PR middle-end/87319
diff --git a/gcc/match.pd b/gcc/match.pd
index db0e4a8c4b9..7cc2374ffeb 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2669,6 +2669,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (mult (convert1? (exact_div @0 @@1)) (convert2? @1))
   (convert @0))
 
+/* ((X /[ex] A) +- B) * A  -->  X +- A * B.  */
+(for op (plus minus)
+ (simplify
+  (mult (convert1? (op (convert2? (exact_div @0 INTEGER_CST@@1)) INTEGER_CST@2)) @1)
+  (if (tree_nop_conversion_p (type, TREE_TYPE (@2))
+       && tree_nop_conversion_p (TREE_TYPE (@0), TREE_TYPE (@2)))
+   (with
+     {
+       wi::overflow_type overflow;
+       wide_int mul = wi::mul (wi::to_wide (@1), wi::to_wide (@2),
+			       TYPE_SIGN (type), &overflow);
+     }
+     (if (types_match (type, TREE_TYPE (@2))
+ 	 && types_match (TREE_TYPE (@0), TREE_TYPE (@2)) && !overflow)
+      (op @0 { wide_int_to_tree (type, mul); })
+      (with { tree utype = unsigned_type_for (type); }
+       (convert (op (convert:utype @0)
+		    (mult (convert:utype @1) (convert:utype @2))))))))))
+
 /* Canonicalization of binary operations.  */
 
 /* Convert X + -C into X - C.  */
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 6f7b577b86a..ce3b03b01a2 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2018-10-02  Marc Glisse  <marc.glisse@inria.fr>
+
+	* gcc.dg/tree-ssa/muldiv-1.c: New file.
+	* gcc.dg/tree-ssa/muldiv-2.c: Likewise.
+
 2018-10-02  Segher Boessenkool  <segher@kernel.crashing.org>
 
 	PR target/87081
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/muldiv-1.c b/gcc/testsuite/gcc.dg/tree-ssa/muldiv-1.c
new file mode 100644
index 00000000000..91612dc9de4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/muldiv-1.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized-raw" } */
+
+// ldist produces (((q-p-4)/4)&...+1)*4
+// Make sure we remove at least the division
+// Eventually this should just be n*4
+
+void foo(int*p, __SIZE_TYPE__ n){
+  for(int*q=p+n;p!=q;++p)*p=0;
+}
+
+/* { dg-final { scan-tree-dump "builtin_memset" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "div" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/muldiv-2.c b/gcc/testsuite/gcc.dg/tree-ssa/muldiv-2.c
new file mode 100644
index 00000000000..474741a248a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/muldiv-2.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-optimized-raw" } */
+
+// 'a' should disappear, but we are not there yet
+
+int* f(int* a, int* b, int* c){
+    __PTRDIFF_TYPE__ d = b - a;
+    d += 1;
+    return a + d;
+}
+
+/* { dg-final { scan-tree-dump-not "div" "optimized" } } */
-- 
2.30.2