[PATCH][v2] match.pd: turn a product of two quotients into one division

From: Kyrylo Tkachov <[email protected]>

v2: Add flag_associative_math on top of flag_reciprocal_math as
condition

(A / B) * (C / D) is (A * C) / (B * D), which replaces one of the two
divisions with a multiply.  The operation count is unchanged and a division
costs several multiplies on every target.

  double f (double a, double b, double c)
  { return (a / b) * (1.0 / c); }

aarch64 -Ofast before:

	fdiv	d0, d0, d1
	fdiv	d0, d0, d2

after:

	fmul	d1, d1, d2
	fdiv	d0, d0, d1

The reciprocal spelling is what appears in source that has been hand-tuned
for -freciprocal-math: the reciprocal is folded into a quotient by the
existing rules, but the resulting division of a division was never revisited
because the multiply had already consumed it.  The existing (A/B)/C rule
therefore only caught the case where the second division was written out.

The rule also needs infinities and NaNs excluded.  It forms two products,
and each is a new place for the exponent to leave the range: with both
divisors large B * D is an infinity and the quotient becomes inf / inf, with
both small it is a zero and the quotient becomes 0 / 0, and either turns a
finite result into a NaN.  The cancellation rules in the same block carry
the same test for the same reason.

Complex values also require signed zeros to be ignored,
because reassociation can change the sign of an imaginary zero.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

gcc/ChangeLog:

	* match.pd ((A / B) * (C / D)): New simplification.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/recip-mult-div-1.c: New test.
	* gcc.dg/tree-ssa/recip-mult-div-2.c: New test.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 28 +++++++++++++++
 .../gcc.dg/tree-ssa/recip-mult-div-1.c        | 36 +++++++++++++++++++
 .../gcc.dg/tree-ssa/recip-mult-div-2.c        | 15 ++++++++
 3 files changed, 79 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-2.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 7c93eff6e47..914c4e330b8 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -819,6 +819,34 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	   || !HONOR_SIGNED_ZEROS (type)))
    (rdiv @0 (mult @1 @2))))
 
+ /* Convert (A/B) * (C/D) to (A*C) / (B*D).  Two divisions become one
+    multiply and one division, and a division costs several multiplies on
+    every target.
+
+    The two products are new places for the exponent to leave the range, so
+    the rule needs more than the rounding licence: with B and D both large
+    B * D is an infinity and the quotient becomes inf / inf, and with both
+    small it is a zero and the quotient becomes 0 / 0.  Either way a finite
+    result turns into a NaN, so the rule is restricted to the case where
+    infinities and NaNs are excluded, as the cancellation rules above are.
+
+    Both quotients have to be dead outside the product, otherwise a division
+    would be added rather than removed, and a shared reciprocal is better
+    left alone for the multiplications to reuse.  That is a hard requirement
+    rather than a :s marker, because :s only forbids emitting new statements
+    and both products can fold away to nothing, as they do for X * X where X
+    is one reciprocal square root.  Requiring two singly used quotients also
+    excludes that case, since a value feeding both operands of the product
+    has two uses.  */
+ (simplify
+  (mult (rdiv@4 @0 @1) (rdiv@5 @2 @3))
+  (if (flag_associative_math
+       && !HONOR_NANS (type) && !HONOR_INFINITIES (type)
+       && (TREE_CODE (type) != COMPLEX_TYPE
+	   || !HONOR_SIGNED_ZEROS (type))
+       && single_use (@4) && single_use (@5))
+   (rdiv (mult @0 @2) (mult @1 @3))))
+
  /* Canonicalize x / (C1 * y) to (x * C2) / y.  */
  (simplify
   (rdiv @0 (mult:s @1 REAL_CST@2))
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-1.c b/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-1.c
new file mode 100644
index 00000000000..889354c7a26
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-1.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -freciprocal-math -ffinite-math-only -fdump-tree-optimized" } */
+/* { dg-additional-options "-fassociative-math -fno-signed-zeros -fno-trapping-math" } */
+
+/* (A / B) * (C / D) is (A * C) / (B * D): one of the two divisions becomes
+   a multiply.  The rule also needs infinities and NaNs excluded, because the
+   two products it forms can leave the range of the type.  */
+
+double f1 (double a, double b, double c)
+{
+  return (a / b) * (1.0 / c);
+}
+
+double f2 (double a, double b, double c, double d)
+{
+  return (a / b) * (c / d);
+}
+
+float f3 (float a, float b, float c, float d)
+{
+  return (a / b) * (c / d);
+}
+
+/* Must not fold: the reciprocal is shared, so the multiplications should
+   reuse it rather than pay for a second division.  */
+double keep (double a, double b, double c, double *r)
+{
+  double t = 1.0 / c;
+  r[0] = (a / b) * t;
+  r[1] = t;
+  return t;
+}
+
+/* Must not fold without -ffinite-math-only: see recip-mult-div-2.c.  */
+
+/* { dg-final { scan-tree-dump-times " / " 5 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-2.c b/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-2.c
new file mode 100644
index 00000000000..e866d217ee7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-2.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -freciprocal-math -fdump-tree-optimized" } */
+
+/* (A / B) * (C / D) -> (A * C) / (B * D) forms two products that can leave
+   the range of the type.  With B and D both large B * D is an infinity and
+   the quotient becomes inf / inf; with both small it is a zero and the
+   quotient becomes 0 / 0.  Either turns a finite result into a NaN, so
+   -freciprocal-math on its own must not enable the rule.  */
+
+double f (double a, double b, double c, double d)
+{
+  return (a / b) * (c / d);
+}
+
+/* { dg-final { scan-tree-dump-times " / " 2 "optimized" } } */
-- 
2.50.1 (Apple Git-155)