match.pd: turn a product of two quotients into one division
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap |
fail
|
Patch failed to apply
|
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
(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 <ktkachov@nvidia.com>
---
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
Comments
On Tue, Aug 04, 2026 at 11:40:28AM +0200, ktkachov@nvidia.com wrote:
> --- 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))))
Shouldn't this depend also on flag_unsafe_math_optimizations?
I mean, even if infinities, NaNs and signed zeros aren't involved,
the optimization changes the results due to different rounding, doesn't it?
Jakub
> On 4 Aug 2026, at 12:03, Jakub Jelinek <jakub@redhat.com> wrote:
>
> On Tue, Aug 04, 2026 at 11:40:28AM +0200, ktkachov@nvidia.com wrote:
>> --- 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))))
>
> Shouldn't this depend also on flag_unsafe_math_optimizations?
> I mean, even if infinities, NaNs and signed zeros aren't involved,
> the optimization changes the results due to different rounding, doesn't it?
The rule is already inside a flag_reciprocal_math. I guess this reassociates multiplication across division so maybe it should also have a flag_associative_math. I think that would be enough without going for the full flag_unsafe_math_optimizations?
Thanks,
Kyrill
>
> Jakub
>
On Tue, Aug 04, 2026 at 10:21:19AM +0000, Kyrylo Tkachov wrote:
> > Shouldn't this depend also on flag_unsafe_math_optimizations?
> > I mean, even if infinities, NaNs and signed zeros aren't involved,
> > the optimization changes the results due to different rounding, doesn't it?
>
> The rule is already inside a flag_reciprocal_math. I guess this
> reassociates multiplication across division so maybe it should also have a
> flag_associative_math. I think that would be enough without going for the
> full flag_unsafe_math_optimizations? Thanks, Kyrill
I'd say that flag_reciprocal_math && flag_associative_math sufficiently
describe what IEEE violations it is allowed to do.
Jakub
@@ -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))
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */