why not consfold sin(const)

why not consfold sin(const)

[Luchezar Belev]

Hi all,

when compiling with -ffast-math, gcc replaces sin(0) with 0, but does not const fold sin of any
other const.
Is there some problem with that in principle (like that would not be correct code in some
circumstances)
or it's just not implemented?
This is also true for other builtin math funcs like log() (gcc only optimizes log(1) to 0),
but it is not the case with sqrt() - in that case the compiler always constfolds and eliminates
the
expensive and redundant sqrt operation.

Lucho



		
__________________________________
Do you Yahoo!?
Yahoo! Mail - 50x more storage than other providers!
http://promotions.yahoo.com/new_mail

Re: why not consfold sin(const)

[Robert Dewar]

Luchezar Belev wrote:
> Hi all,
> 
> when compiling with -ffast-math, gcc replaces sin(0) with 0, but does not const fold sin of any
> other const.

First, I can never remember what incorrect transformations people tolerate
with -ffast-math, but in normal circumstances, one would demand that the
result be indentical to what would have been obtained at run-time, something
that is for example impossible in general with cross-compilers (I mean
impossible, not difficult, since the algorithms for some of the built in
elementary functions have not been revealed).

Second, surely in any reasonably written program you would expect such
constants to only be defined once, so I wonder how useful this would
be in practice.

> Is there some problem with that in principle (like that would not be correct code in some
> circumstances)

If you tolerate any transformation of the kind

(mathematical expression) => (precise result of mathematical expression)
                              converted to nearest machine number.

which to me seems a reasonable rule in -ffast-math, then this is a
legitimate transformation.

> or it's just not implemented?

so in that case, yes, it's just not implemented. Note that to do this
properly you need super accurate elementary functions that are platform
independent available. That's definitely possible.

> This is also true for other builtin math funcs like log() (gcc only optimizes log(1) to 0),

Seems a rather silly optimization to me, hard to believe
that it ever arises. But harmless ...

> but it is not the case with sqrt() - in that case the compiler always constfolds and eliminates
> the
> expensive and redundant sqrt operation.

Seems reassonable, I can imagine people writing sqrt(2.0) in open
code (though there again, giving this a name and defining it as
a constant seems better style to me).

Re: why not consfold sin(const)

[Luchezar Belev]

Robert Dewar wrote:

> Luchezar Belev wrote:
> ... 
> Second, surely in any reasonably written program you would expect such
> constants to only be defined once, so I wonder how useful this would
> be in practice.
>...

Here is one example of how this could be useful:
Imagine you have some defined floating point const MY_CONST in your program and you use it in
various floating point expressions in different ways. Say somewhere you use the expression
x+MY_CONST, somewhere else you use the expression log(x)/log(MY_CONST), and somewhere else
exp(2-x*(MY_CONST + sqrt(MY_CONST))) and so on.

Of course you could define different consts for 1/log(MY_CONST) and MY_CONST+sqrt(MY_CONST), but
that's not very beautifuf, especially if you would like to change the value of MY_CONST from time
to time - then you would have to recalculate all of it's derivated consts too.

Lucho



		
__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - Send 10MB messages!
http://promotions.yahoo.com/new_mail 

Re: why not consfold sin(const)

[Robert Dewar]

Luchezar Belev wrote:

> Here is one example of how this could be useful:
> Imagine you have some defined floating point const MY_CONST in your program and you use it in
> various floating point expressions in different ways. Say somewhere you use the expression
> x+MY_CONST, somewhere else you use the expression log(x)/log(MY_CONST), and somewhere else
> exp(2-x*(MY_CONST + sqrt(MY_CONST))) and so on.

Yes, indeed, that's the most likely scenario
> 
> Of course you could define different consts for 1/log(MY_CONST) and MY_CONST+sqrt(MY_CONST), but
> that's not very beautifuf, especially if you would like to change the value of MY_CONST from time
> to time - then you would have to recalculate all of it's derivated consts too.

Well not really, you would simply define these as constants with the given
initial values. There obviously is no significant overhead in computing
these guys once.

But the stylistic issue here is not so clear.

I think everyone would agree that you do not want to see

    sin (0.362789)

appearing in other than a constant declaration, but

    sin (Take_Off_Angle)

where Take_Off_Angle is a constant, seems reasonable.

So that indeed is an argument in favor of this optimization.
Of course in practice a constant like this will often be pulled
out of loops, CSE'ed etc, so the impact may be smaller than
expected.

Generally speaking in compiler-development-land, far too much effort
goes into optimizations that have no measureable significant value.

So the best argument for a given optimization is to show a real program
where the optimization would make a real difference.

I remember from SPITBOL times that many people would write to us
suggesting an optimization. We then imposed a rule that we would
only publish such suggestions in the newsletter if they were
accompanied by a sample program where the optimization would
speed things up at least a few percent. The flow of suggestions
completely dried up :-)

Re: why not consfold sin(const)

[Luchezar Belev]

Robert Dewar wrote:
> ...
> Generally speaking in compiler-development-land, far too much effort
> goes into optimizations that have no measureable significant value.
> 
> So the best argument for a given optimization is to show a real program
> where the optimization would make a real difference.
> 
> I remember from SPITBOL times that many people would write to us
> suggesting an optimization. We then imposed a rule that we would
> only publish such suggestions in the newsletter if they were
> accompanied by a sample program where the optimization would
> speed things up at least a few percent. The flow of suggestions
> completely dried up :-)

OK, but in our concrete case we already have some optimizing logic in place
which looks if the argument of sin() is zero or if the argument of log() is one,
and in the case of sqrt always replaces with const. So if this already present
logic is worth enough to be there in the compiler, i fail to see why a full consfolder
is not worth enough. It's definitely not the case that it's something too complex
for implementing. In fact it's exactly as complex as the currently present logic.
Surely the precision is not much of an issue either, since -ffast-math
implies possible non-strict copliance with standards, precision requirements, etc.

Lucho



		
_______________________________
Do you Yahoo!?
Declare Yourself - Register online to vote today!
http://vote.yahoo.com

Re: why not consfold sin(const)

[Robert Dewar]

Luchezar Belev wrote:

> OK, but in our concrete case we already have some optimizing logic in place
> which looks if the argument of sin() is zero or if the argument of log() is one,
> and in the case of sqrt always replaces with const. So if this already present
> logic is worth enough to be there in the compiler, i fail to see why a full consfolder
> is not worth enough. It's definitely not the case that it's something too complex
> for implementing. In fact it's exactly as complex as the currently present logic.

Not at all, it is far more complex to implement, since you need a very
accurate set of target independent elementary function routines (you
can't just go calling these routines from the compiler and using the
host functions!)

> Surely the precision is not much of an issue either, since -ffast-math
> implies possible non-strict copliance with standards, precision requirements, etc.

Yes, but it does not stretch as far as giving complete junk results,
which is what would happen in some cases if you used host functions.

Re: why not consfold sin(const)

[Luchezar Belev]

Robert Dewar wrote:

> Luchezar Belev wrote:
> 
> > OK, but in our concrete case we already have some optimizing logic in place
> > which looks if the argument of sin() is zero or if the argument of log() is one,
> > and in the case of sqrt always replaces with const. So if this already present
> > logic is worth enough to be there in the compiler, i fail to see why a full consfolder
> > is not worth enough. It's definitely not the case that it's something too complex
> > for implementing. In fact it's exactly as complex as the currently present logic.
> 
> Not at all, it is far more complex to implement, since you need a very
> accurate set of target independent elementary function routines (you
> can't just go calling these routines from the compiler and using the
> host functions!)
> 
> > Surely the precision is not much of an issue either, since -ffast-math
> > implies possible non-strict copliance with standards, precision requirements, etc.
> 
> Yes, but it does not stretch as far as giving complete junk results,
> which is what would happen in some cases if you used host functions.
 
I see. I'm surprised that in the compiler there is no sin/cos/log/etc. funcs
already implemented for other reasons.

What are the requirements for possible implementation of such functions?
 - precision of somewhere about the long double (64-bit mantissa)
 - the speed doesn't matter too much
is this right?

Lucho


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: why not consfold sin(const)

[Zack Weinberg]

Luchezar Belev <l_belev@yahoo.com> writes:

>> Yes, but it does not stretch as far as giving complete junk results,
>> which is what would happen in some cases if you used host functions.
>  
> I see. I'm surprised that in the compiler there is no sin/cos/log/etc. funcs
> already implemented for other reasons.

I'm not sure about exp/log, but trigonometric functions are
substantially harder to implement with accuracy over their entire
domain (i.e. the range of the floating-point type) - to do argument
reduction, glibc has a table giving 2/pi to 5628 hexadecimal digits!

This is the sort of thing where we'd probably take a patch if someone
wrote one, but we don't consider it very important, certainly not
compared to how hard it would be to code.  And I think you are
seriously underestimating the difficulty.

> What are the requirements for possible implementation of such functions?
>  - precision of somewhere about the long double (64-bit mantissa)

gcc uses an internal floating point representation with *at least* 160
bits of mantissa.  You would need to be accurate to that many bits at
least for all values with exponent 0 (ignoring bias).

>  - the speed doesn't matter too much

Yeah.

zw

Re: why not consfold sin(const)

[Kai Henningsen]

zack@codesourcery.com (Zack Weinberg)  wrote on 19.09.04 in <87oek257mp.fsf@codesourcery.com>:

> Luchezar Belev <l_belev@yahoo.com> writes:
>
> >> Yes, but it does not stretch as far as giving complete junk results,
> >> which is what would happen in some cases if you used host functions.
> >
> > I see. I'm surprised that in the compiler there is no sin/cos/log/etc.
> > funcs already implemented for other reasons.
>
> I'm not sure about exp/log, but trigonometric functions are
> substantially harder to implement with accuracy over their entire
> domain (i.e. the range of the floating-point type) - to do argument
> reduction, glibc has a table giving 2/pi to 5628 hexadecimal digits!
>
> This is the sort of thing where we'd probably take a patch if someone
> wrote one, but we don't consider it very important, certainly not
> compared to how hard it would be to code.  And I think you are
> seriously underestimating the difficulty.

I'd expect that looking into stuff like that would get much more  
interesting if gcc had gmp+mpfr regularly available (as opposed to only  
gfortran using it as an external library).

MfG Kai

Re: why not consfold sin(const)

[Robert Dewar]

Luchezar Belev wrote:

> I see. I'm surprised that in the compiler there is no sin/cos/log/etc. funcs
> already implemented for other reasons.

Compilers barely use floating-point except to simulate target
arithmetic, they sure don't use sin and log!
> 
> What are the requirements for possible implementation of such functions?
>  - precision of somewhere about the long double (64-bit mantissa)
>  - the speed doesn't matter too much
> is this right?

Right, the speed does not matter, and the precision needs to match
the relevant precision on the target machine (i.e. the precision
that would be obtained for that particular operation on the target).

Re: why not consfold sin(const)

[Timothy J.Wood]

On Sep 19, 2004, at 12:17 PM, Robert Dewar wrote:
> Not at all, it is far more complex to implement, since you need a very
> accurate set of target independent elementary function routines (you
> can't just go calling these routines from the compiler and using the
> host functions!)

   How about defining a ctor for that .o file that calls the target's 
elementary function at run time and puts it a global created by the 
compiler?

   This has some arguably less than ideal side effects (the global would 
need to be in writable memory), but it seems to me that this is not 
"impossible" as a previous message claimed.

-tim

Re: why not consfold sin(const)

[Robert Dewar]

Timothy J.Wood wrote:

>   How about defining a ctor for that .o file that calls the target's 
> elementary function at run time and puts it a global created by the 
> compiler?

Unnecessarily messy, it's not that hard to get hold of high precision
elementary functions (the code is certainly immediately available in
Ada, so it must be available in C).
> 
>   This has some arguably less than ideal side effects (the global would 
> need to be in writable memory), but it seems to me that this is not 
> "impossible" as a previous message claimed.

Nothing here is impossible! It's just a matter of whether it is
worthwhile.

Re: why not consfold sin(const)

[Timothy J.Wood]

On Sep 19, 2004, at 1:56 PM, Robert Dewar wrote:

> Timothy J.Wood wrote:
>
>>   How about defining a ctor for that .o file that calls the target's 
>> elementary function at run time and puts it a global created by the 
>> compiler?
>
> Unnecessarily messy, it's not that hard to get hold of high precision
> elementary functions (the code is certainly immediately available in
> Ada, so it must be available in C).

   Yes; but someone (I forget who) early in this thread said it was 
"impossible" since you couldn't simulate target-specific elementary 
functions (presumably they were assuming that the target would have 
ill-defined or buggy routines).  I'm not saying you *should* do the 
ctor thing, it's more a proof of concept that its possible to exactly 
use the target functions.  You'd obviously get better code if you 
didn't call the target functions since you could then process 
"2*sin(CONST)" into a constant.

-tim

Re: why not consfold sin(const)

[Robert Dewar]

> Yes; but someone (I forget who) early in this thread said it was 
> "impossible" since you couldn't simulate target-specific elementary 
> functions (presumably they were assuming that the target would have 
> ill-defined or buggy routines).

Ah, now I see the discussion. This thread is actually specifically
about the possibility of doing this in -ffast-math mode. My
"impossible" comment was a note about doing it without this
mode being turned on, and yes it is impossible to simulate
target routines and precompute at compile-time the exact
values you will get at run-time (because the algorithms are
not documented -- which is not quite the same as ill-defined :-)

> I'm not saying you *should* do the ctor 
> thing, it's more a proof of concept that its possible to exactly use the 
> target functions.  You'd obviously get better code if you didn't call 
> the target functions since you could then process "2*sin(CONST)" into a 
> constant.

Well the "ctor thing" is really just a special case of CSE and
constant propagation, where you promote a constant to the top
level (a quite typical optimization actually), but it is really
not what this thread was about, which was (as you see from the
above quoted subject) about constant folding such calls.


> 
> -tim

Re: why not consfold sin(const)

[Dale Johannesen]

On Sep 19, 2004, at 5:31 PM, Robert Dewar wrote:

>> Yes; but someone (I forget who) early in this thread said it was 
>> "impossible" since you couldn't simulate target-specific elementary 
>> functions (presumably they were assuming that the target would have 
>> ill-defined or buggy routines).
>
> Ah, now I see the discussion. This thread is actually specifically
> about the possibility of doing this in -ffast-math mode. My
> "impossible" comment was a note about doing it without this
> mode being turned on, and yes it is impossible to simulate
> target routines and precompute at compile-time the exact
> values you will get at run-time (because the algorithms are
> not documented -- which is not quite the same as ill-defined :-)

Well, they *could* be reverse engineered, as there are a finite
number of possible inputs.  You'd have to want this an awful lot
to attempt it, though.

Re: why not consfold sin(const)

[Toon Moene]

Robert Dewar wrote:

> Of course in practice a constant like this will often be pulled
> out of loops, CSE'ed etc, so the impact may be smaller than
> expected.

In sensible languages for floating point computations, yes.  One has to 
conclude, though, that floating point arithmetic was added as an 
afterthought to C - not surprising, given its initial niche.

All functions in <math.h> can set errno for domain and range errors; in 
other words, those functions are not pure, and cannot be moved out of 
loops or CSE'd away.

Obviously, with some effort it might be possible to get gcc to the point 
where it can prove for a set of useful constants that, e.g., sqrt cannot 
possibly have to set errno and that the call therefore might be assumed 
pure.

-- 
Toon Moene - e-mail: toon@moene.indiv.nluug.nl - phone: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
A maintainer of GNU Fortran 95: http://gcc.gnu.org/fortran/

Re: why not consfold sin(const)

[Kaveh R. Ghazi]

 > From: Toon Moene 
 > 
 >  > Robert Dewar wrote:
 >  > 
 >  > Of course in practice a constant like this will often be pulled
 >  > out of loops, CSE'ed etc, so the impact may be smaller than
 >  > expected.
 > 
 > In sensible languages for floating point computations, yes. One has to
 > conclude, though, that floating point arithmetic was added as an
 > afterthought to C - not surprising, given its initial niche.
 > 
 > All functions in <math.h> can set errno for domain and range errors;
 > in other words, those functions are not pure, and cannot be moved out
 > of loops or CSE'd away.

If one uses -fno-math-errno, then sqrt is marked "pure".  If you use
-funsafe-math-optimizations then it is marked "const".  (See comments
in builtins.def for ATTR_MATHFN_FPROUNDING and
ATTR_MATHFN_FPROUNDING_ERRNO.)

The g77 frontend sets -fno-math-errno automatically, so I guess it's a
"sensible" language.  However I cannot find where (if) the new fortran
frontend does it.  So it remains to be seen whether that one is
sensible or not. :-)

You may want to check into that.

		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu

Re: why not consfold sin(const)

[Robert Dewar]

Toon Moene wrote:
> Robert Dewar wrote:

> In sensible languages for floating point computations, yes.  One has to 
> conclude, though, that floating point arithmetic was added as an 
> afterthought to C - not surprising, given its initial niche.

UGH!

> All functions in <math.h> can set errno for domain and range errors; in 
> other words, those functions are not pure, and cannot be moved out of 
> loops or CSE'd away.

Seems like you might want to overlook this point in -ffast-math??

Re: why not consfold sin(const)

[Scott Robert Ladd]

Toon Moene wrote:
> All functions in <math.h> can set errno for domain and range errors; in 
> other words, those functions are not pure, and cannot be moved out of 
> loops or CSE'd away.

Another reason to write numerical code in a sensible language like Fortran 95. ;)

That's not really a flippant remark. How far do we go to force numerical performance in C?

-- 
Scott Robert Ladd
site: http://www.coyotegulch.com
blog: http://chaoticcoyote.blogspot.com

Re: why not consfold sin(const)

[Steven Bosscher]

On Tuesday 21 September 2004 01:12, Scott Robert Ladd wrote:
> Toon Moene wrote:
> > All functions in <math.h> can set errno for domain and range errors; in
> > other words, those functions are not pure, and cannot be moved out of
> > loops or CSE'd away.
>
> Another reason to write numerical code in a sensible language like Fortran
> 95. ;)
>
> That's not really a flippant remark. How far do we go to force numerical
> performance in C?

Since all languages try to be general purpose nowadays (class
inheritance in Fortran, whee!), probably pretty far!

Gr.
Steven

Re: why not consfold sin(const)

[Scott Robert Ladd]

Steven Bosscher wrote:

>> That's not really a flippant remark. How far do we go to force numerical performance in C?
> 
> Since all languages try to be general purpose nowadays (class inheritance in Fortran, whee!), probably pretty far!

Call me an old stick-in-the-mud, but I always preferred programming languages (and programs) that have specific applicability; 
combine different tools to accomplish heterogeneous tasks.

Then again, I'm a bearded, balding Unix geek who doesn't seem compatible with a world driven by marketing... ;)

-- 
Scott Robert Ladd
site: http://www.coyotegulch.com
blog: http://chaoticcoyote.blogspot.com

Re: why not consfold sin(const)

[Bradley Lucier]

Re:

> All functions in <math.h> can set errno for domain and range errors; 
> in other words, those functions are not pure, and cannot be moved out 
> of loops or CSE'd away.

Which is one reason to have -fno-math-errno (which is part of 
-ffast-math).

Brad

Re: why not consfold sin(const)

[Toon Moene]

Bradley Lucier wrote:

>> All functions in <math.h> can set errno for domain and range errors; 
>> in other words, those functions are not pure, and cannot be moved out 
>> of loops or CSE'd away.
> 
> Which is one reason to have -fno-math-errno (which is part of -ffast-math).

Sure, but the original implementation of -fno-math-errno I coded because 
Fortran programmers wouldn't have access to errno anyway, didn't concern 
itself with the pureness (or even constness) of the resulting <math.h> 
function.

This is a later addition.

-- 
Toon Moene - e-mail: toon@moene.indiv.nluug.nl - phone: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
A maintainer of GNU Fortran 95: http://gcc.gnu.org/fortran/