Constant expression optimization

Discussion in 'C Programming' started by jacob navia, Oct 20, 2008.

  1. jacob navia

    jacob navia Guest

    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.



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 20, 2008
    #1
    1. Advertising

  2. jacob navia

    Guest

    On Oct 20, 8:19 pm, jacob navia <> wrote:
    > 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.


    <snip>

    > 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.
     
    , Oct 20, 2008
    #2
    1. Advertising

  3. jacob navia

    Walter Banks Guest

    jacob navia wrote:

    > 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..
     
    Walter Banks, Oct 20, 2008
    #3
  4. jacob navia <> writes:

    > 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?
     
    Nate Eldredge, Oct 20, 2008
    #4
  5. jacob navia

    Default User Guest

    Nate Eldredge wrote:

    > jacob navia <> writes:
    >
    > > 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?


    What would you imagine?




    Brian
     
    Default User, Oct 20, 2008
    #5
  6. jacob navia

    Guest

    On Oct 20, 9:00 pm, Walter Banks <> wrote:
    > jacob navia wrote:
    > > 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.
    >


    <snip>

    > 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. ;-)
     
    , Oct 20, 2008
    #6
  7. jacob navia

    Ian Collins Guest

    Walter Banks wrote:
    >
    > jacob navia wrote:
    >
    >> 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
    >

    These optimisations are already common.

    --
    Ian Collins
     
    Ian Collins, Oct 20, 2008
    #7
  8. "Default User" <> writes:

    > Nate Eldredge wrote:
    >
    >> jacob navia <> writes:
    >>
    >> > 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?

    >
    > 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.
     
    Nate Eldredge, Oct 20, 2008
    #8
  9. jacob navia

    Default User Guest

    Nate Eldredge wrote:

    > "Default User" <> writes:
    >
    > > Nate Eldredge wrote:


    > >> What will sqrt(-1.0) do?

    > >
    > > What would you imagine?

    >
    > Well, by my reading of 7.12 (9) and 7.12.7.5 (2)


    You aren't much fun.




    Brian
     
    Default User, Oct 20, 2008
    #9
  10. jacob navia

    jacob navia Guest

    Eric Sosman wrote:
    > 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.

    >> 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?

    >
    > 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.


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 20, 2008
    #10
  11. jacob navia

    Guest

    christian.bau wrote:
    > On Oct 20, 7:00�pm, Walter Banks <> wrote:
    >
    > > 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 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.
     
    , Oct 20, 2008
    #11
  12. jacob navia

    jacob navia Guest

    Walter Banks wrote:
    >
    > jacob navia wrote:
    >
    >> 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.
    >


    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.


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 20, 2008
    #12
  13. jacob navia

    jacob navia Guest

    Nate Eldredge wrote:
    > jacob navia <> writes:
    >
    >> 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?
    >


    Store a NAN.

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 20, 2008
    #13
  14. jacob navia <> writes:

    > Nate Eldredge wrote:
    >> jacob navia <> writes:
    >>
    >>> 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?
    >>

    >
    > Store a NAN.


    I'm not sure that's conforming. See my post <>.
     
    Nate Eldredge, Oct 20, 2008
    #14
  15. jacob navia

    Flash Gordon Guest

    Walter Banks wrote, On 20/10/08 19:00:
    >
    > jacob navia wrote:
    >
    >> 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.


    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.
    --
    Flash Gordon
    If spamming me sent it to
    If emailing me use my reply-to address
    See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/
     
    Flash Gordon, Oct 20, 2008
    #15
  16. jacob navia

    jacob navia Guest

    christian.bau wrote:
    > 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...

    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 20, 2008
    #16
  17. jacob navia

    jacob navia Guest

    wrote:
    > christian.bau wrote:
    >> On Oct 20, 7:00�pm, Walter Banks <> wrote:
    >>
    >>> 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 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.


    WOW!!!

    THANKS A LOT!

    That will simplify things a lot!

    :)


    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Oct 20, 2008
    #17
  18. jacob navia

    Flash Gordon Guest

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


    <snip>

    >> 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.


    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.
    --
    Flash Gordon
    If spamming me sent it to
    If emailing me use my reply-to address
    See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/
     
    Flash Gordon, Oct 20, 2008
    #18
  19. jacob navia

    Flash Gordon Guest

    jacob navia wrote, On 20/10/08 20:13:
    > wrote:
    >> christian.bau wrote:
    >>> On Oct 20, 7:00�pm, Walter Banks <> wrote:
    >>>
    >>>> 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 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.

    >
    > 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.
    --
    Flash Gordon
    If spamming me sent it to
    If emailing me use my reply-to address
    See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/
     
    Flash Gordon, Oct 20, 2008
    #19
  20. jacob navia <> writes:

    > WOW!!!
    >
    > THANKS A LOT!
    >
    > That will simplify things a lot!
    >
    > :)


    You still have to pay attention to static.

    Yours,

    --
    Jean-Marc
     
    Jean-Marc Bourguet, Oct 20, 2008
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    13
    Views:
    13,037
    Kai-Uwe Bux
    Jan 22, 2007
  2. Philipp
    Replies:
    26
    Views:
    2,445
    Ramon F Herrera
    Nov 25, 2007
  3. Adem
    Replies:
    42
    Views:
    2,881
    James Kuyper
    Nov 4, 2008
  4. Adem
    Replies:
    45
    Views:
    1,869
    James Kuyper
    Nov 4, 2008
  5. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    904
    Thad Smith
    Nov 24, 2008
Loading...

Share This Page