[PATCH] tree-optimization: Optimize division followed by multiply [PR95176]

[Victor Tong <vitong@microsoft.com>]

[-- Attachment #1: Type: text/plain, Size: 1568 bytes --]

Hello,

This patch fixes PR tree-optimization/95176. A new pattern in match.pd was added to transform "a * (b / a)" --> "b - (b % a)". A new test case was also added to cover this scenario.

The new pattern interfered with the existing pattern of "X - (X / Y) * Y". In some cases (such as in fn4() in gcc/testsuite/gcc.dg/fold-minus-6.c), the new pattern is applied causing the existing pattern to no longer apply. This results in worse code generation because the expression is left as "X - (X - Y)". An additional subtraction pattern of "X - (X - Y) --> Y" was added to this patch to avoid this regression.

I also didn't remove the existing pattern because it triggered in more cases than the new pattern because of a tree_invariant_p check that's inserted by genmatch for the new pattern.

I verified that all "make -k check" tests pass when targeting x86_64-pc-linux-gnu.

2021-03-31  Victor Tong  <vitong@microsoft.com> 

gcc/ChangeLog:

	* match.pd: Two new patterns: One to optimize division followed by multiply and the other to avoid a regression as explained above

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/20030807-10.c: Update existing test to look for a subtraction because a shift is no longer emitted
	* gcc.dg/pr95176.c: New test to cover optimizing division followed by multiply

I don't have write access to the GCC repo but I've completed the FSF paperwork as I plan to make more contributions in the future. I'm looking for a sponsorship from an existing GCC maintainer before applying for write access.

Thanks,
Victor

[-- Attachment #2: pr95176.patch --]
[-- Type: application/octet-stream, Size: 3025 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index 036f92fa959..ef9c6719a0a 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -599,6 +599,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
   (convert (trunc_mod @0 @1))))
 
+/* X * (Y / X) is the same as Y - (Y % X).  */
+(simplify
+ (mult:c (convert1? @0) (convert2? (trunc_div @1 @@0)))
+ (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+  (minus (convert @1) (convert (trunc_mod @1 @0)))))
+
+/* X - (X - Y) --> Y */
+(simplify
+ (minus (convert1? @0) (convert2? (minus @@0 @1)))
+ (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)) && TYPE_OVERFLOW_UNDEFINED(type))
+  (convert @1)))
+
 /* Optimize TRUNC_MOD_EXPR by a power of two into a BIT_AND_EXPR,
    i.e. "X % C" into "X & (C - 1)", if X and C are positive.
    Also optimize A % (C << N)  where C is a power of 2,
diff --git a/gcc/testsuite/gcc.dg/pr95176.c b/gcc/testsuite/gcc.dg/pr95176.c
new file mode 100644
index 00000000000..ef087317187
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr95176.c
@@ -0,0 +1,45 @@
+/* { dg-do run } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+extern int printf (__const char *__restrict __format, ...);
+
+int __attribute__ ((noinline))
+f(int a, int b)
+{
+    return a * (b / a);
+}
+
+int __attribute__((optimize("O0"))) __attribute__ ((noinline))
+fNoOpt(int a, int b)
+{
+    return a * (b / a);
+}
+
+int __attribute__ ((noinline))
+f2(int a, int b)
+{
+    return (b / a) * a;
+}
+
+int __attribute__((optimize("O0"))) __attribute__ ((noinline))
+f2NoOpt(int a, int b)
+{
+    return (b / a) * a;
+}
+
+int main()
+{
+    if (f(2, 15) != fNoOpt(2, 15))
+        __builtin_abort();
+    if (f2(2, 15) != f2NoOpt(2, 15))
+        __builtin_abort();
+    printf("pass");
+}
+
+// There should be two instances of trunc_div_expr and 
+// mult_expr in the output. One in fNoOpt and one in f2NoOpt.
+/* { dg-final { scan-tree-dump-times "trunc_div_expr" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "mult_expr" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "trunc_mod_expr" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "minus_expr" 2 "optimized" } } */
+/* { dg-output "pass" } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030807-10.c b/gcc/testsuite/gcc.dg/tree-ssa/20030807-10.c
index 0e01e511b78..4cd35738057 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/20030807-10.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/20030807-10.c
@@ -20,6 +20,9 @@ subreg_highpart_offset (outermode, innermode)
 /* There should be one mask with the value 3.  */
 /* { dg-final { scan-tree-dump-times " \& 3" 1 "vrp1"} } */
   
-/* There should be one right shift by 2 places.  */
-/* { dg-final { scan-tree-dump-times " >> 2" 1 "vrp1"} } */
+/* There should be no right shift by 2 places.  */
+/* { dg-final { scan-tree-dump-times " >> 2" 0 "vrp1"} } */
+
+/* The "difference / 4 * 4" should become a subtraction */
+/* { dg-final { scan-tree-dump-times " - " 2 "vrp1"} } */