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

From: Kyrylo Tkachov <[email protected]>

(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.

Both quotients are required to be singly used, as a hard condition rather
than a :s marker.  :s only forbids emitting new statements, so it lets the
rule fire whenever the two products happen to fold away, which is exactly
what X * X does for one reciprocal square root: there the rule added a
division and hid the pattern the recip pass looks for.  Requiring two singly
used quotients also excludes that case, since a value feeding both operands
of a product has two uses.

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                                  | 27 ++++++++++++++
 .../gcc.dg/tree-ssa/recip-mult-div-1.c        | 35 +++++++++++++++++++
 .../gcc.dg/tree-ssa/recip-mult-div-2.c        | 15 ++++++++
 3 files changed, 77 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..be792e30f22 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -819,6 +819,33 @@ 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 (!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..40d36bd3e57
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/recip-mult-div-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -freciprocal-math -ffinite-math-only -fdump-tree-optimized" } */
+
+/* (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)