Constant expression optimization

J

jacob navia

Hi

I am adding an optimization to lcc-win:

sqrt(2.0) will provoke now that the constant 1.4142... etc will be
generated instead of generating an actual call.

Details:
-------

The compiler does all calculation in the highest precision
available (long double), and then transforms the result into
the (maybe) lower precision as required.

For instance:
float f = sqrtf(2.0f);

The compiler transforms the input constant in a long double
precision constant, then transforms the result into a float
constant.

This code:
long double ld = sqrt(2.0f);

will provoke a call to sqrt(2.0f) with the 2.0 transformed
into a long double from a float constant, then the
result cast again down into a float from a double, then
cast up again to do the assignment of a float into a long
double. The actual value passed will be
1.414213538169861
and not
1.41421356237309504
as it should be in long double precision.


I hope I did not forget some obscure rule in this. Please
if you think about some problems with this optimization
just answer.

The functions supported are most of the functions in math.h
(sqrt acos sin/cos) etc.

Later I will add strlen of constant strings. (strlen("hello"))

What other functions would you add?

Thanks in advance for your attention.
 
V

vippstar

Hi

I am adding an optimization to lcc-win:

sqrt(2.0) will provoke now that the constant 1.4142... etc will be
generated instead of generating an actual call.

What other functions would you add?

I'd add memset(&obj, 0, sizeof obj); as T obj = {0}; if memset is the
first operation on obj.
 
W

Walter Banks

jacob said:
I hope I did not forget some obscure rule in this. Please
if you think about some problems with this optimization
just answer.

There are two potential problems with this.


1) How do you make sure the internal calculation will be the
same as what would have happened from an actual library
call.

2) What happens if someone uses their own library and it
produces a different result from your internal calculation
or redefines the function completely


w..
 
N

Nate Eldredge

jacob navia said:
Hi

I am adding an optimization to lcc-win:

sqrt(2.0) will provoke now that the constant 1.4142... etc will be
generated instead of generating an actual call.

What will sqrt(-1.0) do?
 
V

vippstar

There are two potential problems with this.

2) What happens if someone uses their own library and it
produces a different result from your internal calculation
or redefines the function completely

If the library is conforming, it should be the same result as I
understand it.
Also, if he redefines the function, he's invoking undefined behavior
and anything can happend. ;-)
 
I

Ian Collins

Walter said:
There are two potential problems with this.


1) How do you make sure the internal calculation will be the
same as what would have happened from an actual library
call.

2) What happens if someone uses their own library and it
produces a different result from your internal calculation
or redefines the function completely
These optimisations are already common.
 
N

Nate Eldredge

Default User said:
What would you imagine?

Well, by my reading of 7.12 (9) and 7.12.7.5 (2), it should either set
errno to EDOM or raise a floating-point exception, or both, depending on
the value of math_errhandling.

Incidentally, where in the standard is "floating-point exception"
defined, and is it stated exactly what happens when a floating-point
exception is raised? A natural assumption would be that it raises the
signal SIGFPE but I can't find that explicitly stated.
 
J

jacob navia

Eric said:
Are you doing anything with pow(any, integer)? Changing
pow(x, 2.0) into x*x, that sort of thing?

When the second argument is an integer I call ipow.
I did not think about that specific optimization. Thanks.
If you can get hold of a "representative" collection of programs
and profile them, you may be able to get better guidance on what's
worth optimizing than just by asking around. For example, do you
have reason to believe that some programs evaluate sqrt(2.0) often
enough that replacing it with 1.414... would be a big help?


Well it can be more complicated than that...

When I extend constant folding into doubles (I do now
only integers constant folding) I will be able
to use this too, enhancing constant folding across
function calls.
 
J

jameskuyper

christian.bau said:
If the right standard header file <math.h> is included, then I think
the compiler can assume that sqrt () is the actual standard library
function, and if the programmer replaces it with something else, it's
their own fault. If the programmer just adds a declaration himself
like

#include <stdio.h>
int main (void)
{
extern double sqrt (double x);
printf ("7.3f\n", sqrt (2.0));
}

without including <math.h>, then the compiler cannot do this
optimisation.

I don't follow that - what difference does it make how the identifier
'sqrt' is declared? sqrt is an identifier with external linkage
declared in a standard header. According to 7.3.1p1, "All identifiers
with external linkage in any of the following subclauses (including
the future library directions) are always reserved for use as
identifiers with external linkage), so no such declaration can refer
to a user-defined alternative function, whether it's declared in
<math.h> or in the user code.
 
J

jacob navia

Walter said:
There are two potential problems with this.


1) How do you make sure the internal calculation will be the
same as what would have happened from an actual library
call.

I call the library routine within the compiler, albeit
with more precision than necessary.

2) What happens if someone uses their own library and it
produces a different result from your internal calculation
or redefines the function completely

In that case I screw it... I just did not think about that
possibility.

I will test if math.h is included. Thanks.
 
F

Flash Gordon

Walter Banks wrote, On 20/10/08 19:00:
There are two potential problems with this.

1) How do you make sure the internal calculation will be the
same as what would have happened from an actual library
call.

I don't think there is any requirement for the functions to be stable.
2) What happens if someone uses their own library and it
produces a different result from your internal calculation
or redefines the function completely

This is only relevant if they do not include math.h either directly or
indirectly *and* their function is declared static. Otherwise they have
invoked undefined behaviour and it is not Jacob's problem and his
compiler can do whatever is most convenient for Jacob.

Jacob, can I suggest that one possibly simple way to deal with this
issue would be to implement a pragma to enable this optimisation and
then set the pragma in your math.h? Maybe with a switch that causes the
pragma to be ignored. Just ensure that the following program works (I
have no reason to suppose it won't) and you have probably avoided the
traps...

#include <stdio.h>

static void sqrt(void)
{
puts("sqrt overridden");
}
static float sqrtf(float f)
{
puts("sqrtf overridden");
return 0;
}
int main(void)
{
float f=sqrtf(2);
sqrt();
printf("f=%f\n",f);
return 0;
}

Please note this is *not* a complaint and I have absolutely no reason to
suspect you currently get this wrong. It is simply a suggestion of a
test for you new optimisation.

I have seen code (written in Pascal rather than C) which would have
benefited by this type of optimisation, so it could certainly be useful
for some people. Especially useful if the it interacts in all possible
ways with constant propagation so something like...
double d1 = complex_but_constant_expression;
double d2 = sqrt(d1/2);
double d3 = 3*d2;
gives d3 getting assigned a constant value.

Of course, what I've just suggested for the optimisation could make it
far harder for you, so by all means feel free to ignore this suggestion.
It is your product and your time, not mine, and I am not part of your
target audience for the compiler.
 
J

jacob navia

christian.bau said:
In any sane implementation, the sqrt functions will produce correctly
rounded results for any input value. An implementation not doing this
is not IEEE 754 conforming and will be considered broken by most
people. The double precision variant is broken. I think the first
number that demonstrates the brokenness is x = (1 + 3 * 2^-52), where
the correct result is 1 + 1 * 2^-52; your code would get the incorrect
result 1 + 2 * 2^-52.

I obtain 1.0 as the result at compile time.

The following code
#include <math.h>
int main(void)
{
double ld = sqrt(1+3*0.00000000000000022204460492503130808);
double ld1 = 1;

ld1 += 3*0.00000000000000022204460492503130808;
ld1 = sqrt(ld1);

if (ld == ld1)
printf("OK\n");
else
printf("%30.16f\n",ld-ld1);
}

prints

OK.

And in any remotely sane implementation, the result of a function call
would not depend on whether the compiler realized that it can
determine the value of an argument or not. For example, if I write

inline double f (double x) { return sqrt (2.0 * x); }

the result of f (1.0) should never depend on how clever the compiler
is, and whether it figures out that the argument is 2.0 or not.

Well, I do not see any differences...
 
J

jacob navia

I don't follow that - what difference does it make how the identifier
'sqrt' is declared? sqrt is an identifier with external linkage
declared in a standard header. According to 7.3.1p1, "All identifiers
with external linkage in any of the following subclauses (including
the future library directions) are always reserved for use as
identifiers with external linkage), so no such declaration can refer
to a user-defined alternative function, whether it's declared in
<math.h> or in the user code.

WOW!!!

THANKS A LOT!

That will simplify things a lot!

:)
 
F

Flash Gordon

jacob navia wrote, On 20/10/08 19:58:
Walter Banks wrote:


In that case I screw it... I just did not think about that
possibility.

I will test if math.h is included. Thanks.

See other messages in this thread. Walter's example invokes undefined
behaviour so *anything* your compiler does with it is valid. However,
testing if math.h is included might be the easiest way to deal with the
obscure and deliberately nit-picking example I posted.
 
F

Flash Gordon

jacob navia wrote, On 20/10/08 20:13:
WOW!!!

THANKS A LOT!

That will simplify things a lot!

:)

That is *precisely* what rules like that were put in the standard for!
However, beware static functions when math.h is not included.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top