Optimize logarithm addition and subtraction

Message ID trinity-29f353a1-cf4d-4730-8689-77a224fc5996-1533488391784@3c-app-mailcom-bs15
State New
Headers show
Series
  • Optimize logarithm addition and subtraction
Related show

Commit Message

MCC CS Aug. 5, 2018, 4:59 p.m.
Hi everyone,

this patch reduces calls to logarithm functions by
merging log a + log b => log a*b and
log a - log b => log a/b
This is my first contribution, so have I forgot something?
I think a contributor agreement is not needed since it's
a 20-line patch, and I may not have time to contribute in the
future.

Thank you for your comments.

2018-08-05  Deswurstes  <DesWurstes@users.noreply.github.com>

gcc/
	PR tree-optimization/86710
	* match.pd: Add logarithm addition optimization

gcc/testsuite/
	PR tree-optimization/86710
	* gcc.dg/pr86710.c: Add logarithm tests

Comments

Marc Glisse Aug. 5, 2018, 6:17 p.m. | #1
On Sun, 5 Aug 2018, MCC CS wrote:

> this patch reduces calls to logarithm functions by
> merging log a + log b => log a*b and

this makes sense.

> + /* x * logN(a) + y * logN(b) -> x * y * logN(a * b). */

this on the other hand... Can you explain the math?
Andreas Schwab Aug. 5, 2018, 6:32 p.m. | #2
On Aug 05 2018, Marc Glisse <marc.glisse@inria.fr> wrote:

> On Sun, 5 Aug 2018, MCC CS wrote:
>
>> this patch reduces calls to logarithm functions by
>> merging log a + log b => log a*b and
>
> this makes sense.

Even when a*b may overflow?

Andreas.
MCC CS Aug. 5, 2018, 7:22 p.m. | #3
> Sent: Sunday, August 05, 2018 at 8:17 PM
> From: "Marc Glisse" <marc.glisse@inria.fr>
> To: "MCC CS" <mcccs@gmx.com>
> Cc: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] Optimize logarithm addition and subtraction
>
> On Sun, 5 Aug 2018, MCC CS wrote:
> 
> > this patch reduces calls to logarithm functions by
> > merging log a + log b => log a*b and
> 
> this makes sense.
> 
> > + /* x * logN(a) + y * logN(b) -> x * y * logN(a * b). */
> 
> this on the other hand... Can you explain the math?
> 
> -- 
> Marc Glisse
> 


Oops, please ignore the patch at the top and 
review the second patch. I must have done 
A mistake somewhere. It's actually x * y * log(a^(1/y)b^(1/x))
Marc Glisse Aug. 5, 2018, 7:54 p.m. | #4
On Sun, 5 Aug 2018, MCC CS wrote:

> Besides, if you think optimizing
> /* logN(a) + logN(b) -> logN(a * b) */
> would be enough, without the coefficients,
> here's a simpler patch:
>
> Index: gcc/match.pd
> ===================================================================
> --- gcc/match.pd    (revision 263305)
> +++ gcc/match.pd    (working copy)
> @@ -4015,6 +4015,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>    (exps (logs @0))
>    @0))
>
> +(for logs (LOG LOG2 LOG10)

You seem to be missing some indentation, see neighboring
transformations.

> + /* logN(a) + logN(b) -> logN(a * b). */
> + (simplify
> +  (plus:c (logs:s (@0)) (logs:s (@1)))
> +  (logs (mult (@0) (@1))))

No parentheses around @0 and @1. No :c here, the pattern is symmetric
and a permutation would be redundant.

> +
> +(for logs (LOG LOG2 LOG10)
> + /* logN(a) - logN(b) -> logN(a / b). */
> + (simplify
> +  (sub (logs:s (@0)) (logs:s (@1)))
> +  (logs (rdiv (@0) (@1))))

It would be possible to merge the 2 with a second 'for', but that's not a 
requirement.

> +
>  /* Optimize logN(func()) for various exponential functions.  We
>     want to determine the value "x" and the power "exponent" in
>     order to transform logN(x**exponent) into exponent*logN(x).  */
> Index: gcc/testsuite/gcc.dg/pr86710.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/pr86710.c    (nonexistent)
> +++ gcc/testsuite/gcc.dg/pr86710.c    (working copy)
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */

The transformation should not happen at -O2, it should require
-funsafe-math-optimizations or similar.

> +/* { dg-final { scan-assembler-not "log(.*)log(.*)log" } } */

I think I'd rather scan-tree-dump-times the "optimized" dump.

> +
> +double c;
> +
> +void f1 (double x, double s)
> +{
> +  c = __builtin_log(x) + __builtin_log(s);
> +}
> +
> +void f2 (double x, double s)
> +{
> +  c = __builtin_log(x) - __builtin_log(s);
> +}

You need to specify how you tested the patch (bootstrap on what platform, 
run make check, whatever). And then we need to see if other people think 
-funsafe-math-optimization is enough protection or the transformation is 
too dangerous...

Patch

Index: gcc/match.pd
===================================================================
--- gcc/match.pd	(revision 263305)
+++ gcc/match.pd	(working copy)
@@ -4015,6 +4015,18 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (exps (logs @0))
    @0))

+(for logs (LOG LOG2 LOG10)
+ /* x * logN(a) + y * logN(b) -> x * y * logN(a * b). */
+ (simplify
+  (plus:c (mult:c @0 (logs:s @1)) (mult:c @2 (logs:s @3)))
+  (mult (mult @0 @2) (logs (mult @1 @3))))
+
+(for logs (LOG LOG2 LOG10)
+ /* x * logN(a) - y * logN(b) -> x * logN(a / b) / y. */
+ (simplify
+  (sub (mult:c @0 (logs:s @1)) (mult:c @2 (logs:s @3)))
+  (rdiv (mult @0 (logs (rdiv @1 @3))) @3))
+
  /* Optimize logN(func()) for various exponential functions.  We
     want to determine the value "x" and the power "exponent" in
     order to transform logN(x**exponent) into exponent*logN(x).  */
Index: gcc/testsuite/gcc.dg/pr86710.c
===================================================================
--- gcc/testsuite/gcc.dg/pr86710.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/pr86710.c	(working copy)
@@ -0,0 +1,15 @@ 
+/* { dg-do compile } */
+/* { dg-options "-Ofast" } */
+/* { dg-final { scan-assembler-not "log(.*)log(.*)log" } } */
+
+double c;
+
+void f1 (double x, double s)
+{
+  c = 5 * __builtin_log(x) + __builtin_log(s) / 2;
+}
+
+void f2 (double x, double s)
+{
+  c = __builtin_log(x) * 3 - 7 * __builtin_log(s);
+}

Besides, if you think optimizing
/* logN(a) + logN(b) -> logN(a * b) */
would be enough, without the coefficients,
here's a simpler patch:

Index: gcc/match.pd
===================================================================
--- gcc/match.pd    (revision 263305)
+++ gcc/match.pd    (working copy)
@@ -4015,6 +4015,18 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (exps (logs @0))
    @0))

+(for logs (LOG LOG2 LOG10)
+ /* logN(a) + logN(b) -> logN(a * b). */
+ (simplify
+  (plus:c (logs:s (@0)) (logs:s (@1)))
+  (logs (mult (@0) (@1))))
+
+(for logs (LOG LOG2 LOG10)
+ /* logN(a) - logN(b) -> logN(a / b). */
+ (simplify
+  (sub (logs:s (@0)) (logs:s (@1)))
+  (logs (rdiv (@0) (@1))))
+
  /* Optimize logN(func()) for various exponential functions.  We
     want to determine the value "x" and the power "exponent" in
     order to transform logN(x**exponent) into exponent*logN(x).  */
Index: gcc/testsuite/gcc.dg/pr86710.c
===================================================================
--- gcc/testsuite/gcc.dg/pr86710.c    (nonexistent)
+++ gcc/testsuite/gcc.dg/pr86710.c    (working copy)
@@ -0,0 +1,15 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler-not "log(.*)log(.*)log" } } */
+
+double c;
+
+void f1 (double x, double s)
+{
+  c = __builtin_log(x) + __builtin_log(s);
+}
+
+void f2 (double x, double s)
+{
+  c = __builtin_log(x) - __builtin_log(s);
+}