Message ID | trinity-29f353a1-cf4d-4730-8689-77a224fc5996-1533488391784@3c-app-mailcom-bs15 |
---|---|
State | New |
Headers | show |
Series | Optimize logarithm addition and subtraction | expand |
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?
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.
> 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))
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...
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); +}