Order of function evaluation

Discussion in 'C Programming' started by Jens.Toerring@physik.fu-berlin.de, Oct 25, 2003.

  1. -berlin.de

    -berlin.de Guest

    Hi,

    I have a possibly rather stupid question about the order of evaluation
    in a statement like this:

    result = foo( x ) - bar( y );

    How can I make 100% sure that foo(x) is evaluated before bar(y), where
    foo() and bar() can be either functions or macros? I got into problems
    with this when writing some hardware-related stuff where foo() and bar()
    are functions or macros (I want to make sure the solution is independent
    of this) that read certain hardware registers and that need to be read
    in a specific order. The compiler "optimized" the code by reversing the
    reads, which isn't a very good idea in this case. For the time being I
    found that rewritting the above as

    result = foo( x );
    result -= bar( y );

    gets rid of the problem, but I am not sure if this really guarantees
    that foo(x) is evaluated before bar(y) when I use a different compiler
    or a different version. I also don't see at the moment if this can be
    resolved by e.g. declaring 'result' as 'volatile', but perhaps I am
    too stupid to see the obvious.
    Thanks, Jens
    --
    _ _____ _____
    | ||_ _||_ _| -berlin.de
    _ | | | | | |
    | |_| | | | | | http://www.physik.fu-berlin.de/~toerring
    \___/ens|_|homs|_|oerring
    -berlin.de, Oct 25, 2003
    #1
    1. Advertising

  2. -berlin.de

    Alex Guest

    -berlin.de wrote:

    <snip>

    > result = foo( x );
    > result -= bar( y );


    > gets rid of the problem, but I am not sure if this really guarantees
    > that foo(x) is evaluated before bar(y) when I use a different compiler



    Because there is a sequence point at the end of the first line, you
    can be sure that foo() is evaluated first.

    Alex
    Alex, Oct 25, 2003
    #2
    1. Advertising

  3. On Fri, 24 Oct 2003 23:41:34 +0000, Jens.Toerring wrote:

    > I have a possibly rather stupid question about the order of evaluation
    > in a statement like this:
    >
    > result = foo( x ) - bar( y );
    >
    > How can I make 100% sure that foo(x) is evaluated before bar(y), where
    > foo() and bar() can be either functions or macros?

    ...
    > For the time being I found that rewriting the above as
    >
    > result = foo( x );
    > result -= bar( y );
    >
    > gets rid of the problem, but I am not sure if this really guarantees
    > that foo(x) is evaluated before bar(y)...


    Indeed it does. This is because in the second case, there is a sequence
    point after the first line. And at that sequence point all sides effects
    associated with the evaluation of the assignment expression (i.e. - the
    store to result) must be complete. That is, the value of result must
    have been updated. Then the second line executes.

    The compiler is not free to reverse the order of the lines because
    the store to result must happen at the end of the first line(*). If
    the compiler swapped them around the resulting code would be
    equivalent to

    result = foo(x);

    In the first case, there is only one sequence point at the end of the
    single line and since the compiler doesn't actually have to complete
    any side effects until then, it is free to rearrange the evaluation
    of foo() and bar().

    Some refs:

    5.1.2.3 Program execution
    2 Accessing a volatile object, modifying an object, modifying a
    file, or calling a function that does any of those operations
    are all side effects, which are changes in the state of the
    execution environment. Evaluation of an expression may produce
    side effects. At certain specified points in the execution
    sequence called sequence points, all side effects of previous
    evaluations shall be complete and no side effects of subsequent
    evaluations shall have taken place.

    Annex C (Informative) Sequence Points
    1 The following are the sequence points described in 5.1.2.3:
    - The call to a function, after the arguments have been
    evaluated (6.5.2.2).
    ...
    - The end of a full expression: an initializer (6.7.8); the
    expression in an expression statement (6.8.3);
    ...

    -Sheldon

    (*) Actually the program must only function "as if" the store had
    occurred.
    Sheldon Simms, Oct 25, 2003
    #3
  4. "Sheldon Simms" <> wrote in message
    news:p...
    > On Fri, 24 Oct 2003 23:41:34 +0000, Jens.Toerring wrote:
    >
    > > I have a possibly rather stupid question about the order of evaluation
    > > in a statement like this:
    > >
    > > result = foo( x ) - bar( y );
    > >
    > > How can I make 100% sure that foo(x) is evaluated before bar(y), where
    > > foo() and bar() can be either functions or macros?


    (snip)

    > In the first case, there is only one sequence point at the end of the
    > single line and since the compiler doesn't actually have to complete
    > any side effects until then, it is free to rearrange the evaluation
    > of foo() and bar().
    >
    > Some refs:
    >
    > 5.1.2.3 Program execution
    > 2 Accessing a volatile object, modifying an object, modifying a
    > file, or calling a function that does any of those operations
    > are all side effects, which are changes in the state of the
    > execution environment. Evaluation of an expression may produce
    > side effects. At certain specified points in the execution
    > sequence called sequence points, all side effects of previous
    > evaluations shall be complete and no side effects of subsequent
    > evaluations shall have taken place.


    I am not at all sure what optimizers are allowed to do. At least in Fortran
    there once was a traditional optimization of moving invariant expressions
    out of loops. Though doing that for function calls can sometimes cause
    problems.

    One favorite example from Fortran, but translated to C goes something like:

    for(i=0;i<n;i++) {
    if(a>0) b *= sqrt(a);
    c *= a;
    }


    There were compilers that would evaluate sqrt(a) outside the loop, keep the
    result in a register and use it in the multiply.

    Function calls don't tend to allow that optimization in general, though. I
    believe that C compilers can still do common subexpression elimination,
    except in the case of volatile variables.

    -- glen
    Glen Herrmannsfeldt, Oct 25, 2003
    #4
  5. -berlin.de

    Chris Torek Guest

    In article <uckmb.9426$9E1.44563@attbi_s52>
    Glen Herrmannsfeldt <> writes:
    >I am not at all sure what optimizers are allowed to do.


    The short version is "anything you cannot tell they have done,
    other than by the fact that your program runs faster". :)

    There is a constraint on this, however: you must write code that
    conforms to the appropriate standard (one of the C or Fortran
    standards). Suppose you write code that the standard says has
    "undefined behavior", and the compiler assumes that you have
    not written such code. The optimizer in the compiler is allowed
    to run with this assumption and make changes that *are* visible
    (other than in terms of execution time). This is, in effect,
    "your fault" and not the "compiler's fault".

    >At least in Fortran there once was a traditional optimization of
    >moving invariant expressions out of loops. ...


    This is a typical optimization in any compiled, imperative language.
    The theory is that loops -- especially inner loops, when loops are
    nested -- contain code that will be run quite a bit, so if there is
    some way to move some computation outside the loop and run it just
    once, instead of every time, that should help a lot. Another
    technique is "strength reduction", in which a "strong" operation
    (like a multiplication) is "reduced" to an equivalent "weaker" one
    (such as repeated addition) that should go faster:

    for i in [0..N1) do
    for j in [0..N2) do
    op(arr[i;j])

    The subscript operation here may (depending on the language) involve
    multiplication, but the result will be the sequence {0,4,8,12,16,...}
    or some such. Instead of doing a multiply, the two loops can be
    replaced with something like:

    for ix in [0..N1 * N2) do
    op(arr{reinterpreted as one-dimensional}[ix])

    which might translate to (non-portable, because the array subscripts
    are out of bounds, but the compiler can do it simply by changing the
    bounds it applies) C as:

    for (ix = 0, iy = N1 * N2; ix < iy; ix++)
    op(arr[0][ix])

    >One favorite example from Fortran, but translated to C goes something like:
    >
    >for(i=0;i<n;i++) {
    > if(a>0) b *= sqrt(a);
    > c *= a;
    > }
    >
    >There were compilers that would evaluate sqrt(a) outside the loop, keep the
    >result in a register and use it in the multiply.


    C compilers can do this too, because the name sqrt() is reserved
    to the implementation, and the compiler can recognize the call.
    It gets hairy around the edges though, because if "a" is negative,
    each (removed) call to sqrt() must (at least appear to) set errno
    to EDOM. (The compiler can hoist the errno-setting if it can prove
    that errno is not changed elsewhere in the loop, or move it below
    the loop, or even remove it entirely, if it can prove that errno
    is not examined. And of course, the problem never comes up if the
    compiler can prove that a >= 0.)

    >Function calls don't tend to allow that optimization in general, though.


    Any function that is known to be a "pure" function -- that is, one
    free of "side effects" -- can be hoisted out of a loop. (Indeed,
    any "loop invariant" can be so treated. Optimizers thus spend a
    lot of effort finding such invariants.) In languages that eliminate
    side effects entirely, such as typical functional programming
    languages, the test "is function F a pure function" is trivial.
    In C, programmers can never declare their functions pure, but in
    C99, programmers can expose the entire contents of the function
    via the new "inline" keyword, and the compiler can try to figure
    this out for itself. In GNUC -- a language almost but not entirely
    unlike C [ok, actually a lot like C, and apologies to Douglas Adams
    :) ] -- programmers can use the horrible __attribute__ syntax to
    declare a function "pure". Implementors writing their own
    implementations know which functions are pure (e.g., strlen(),
    provided the contents of the buffer on which it is operating also
    remain unchanged) are pure and which are not (e.g., rand() and
    strtok()).

    In C, however, even knowing that something *is* a pure function is
    not always sufficient. The strlen() case is a good example. Just
    because strlen("abc") is always 3 does not mean that:

    void f(char *p1, char *p2) {
    size_t i;

    for (i = 0; i < strlen(p1); i++)
    do_something(p2);
    }

    can have its loop transformed into:

    for (i = 0, lim = strlen(p1); i < lim; i++)

    In particular, if do_something() has access to the same pointer
    value stored in p1 in f(), it could modify p1[k] (for some valid
    k), changing the result of strlen() partway through the loop. We
    need to know that the contents of p1[k] never changes. The "const"
    qualifier in C, which sounds like it should mean "constant", does
    not do the trick: it is just a promise -- not even an enforceable
    one, thanks to casts -- that the programmer will not modify p1[k]
    using the variable named "p1". If do_something() has a
    non-const-qualified "char *p3" that has the same value as p1, and
    do_something writes on p3[k], this (visibly) changes p1[k] as well.

    C99 adds a "restrict" qualifier that does the trick (using a rather
    large hammer, as it were). Fortran escapes the problem by effectively
    declaring *all* array parameters as "restrict"ed, in C99 terms.
    Functional programming languages generally escape it by not having
    (user-visible) pointers in the first place. :)

    Of course, in any programming language, the programmer can hoist
    loop invariants "manually", as it were. If the programmer knows
    that strlen(p1) is not going to -- or even just "not supposed to"
    -- change inside the loop, the programmer can add a loop-limit
    variable and write "i < lim" instead of "i < strlen(p1)". One
    difference between C and most other compiled languages here is that
    many or even most of C's abstractions are typically quite a bit
    "closer to the machine", as it were, and an experienced C programmer
    can often tell not only which expressions are invariant, but also
    which ones the compiler will fail to discover for itself. But this
    can cut both ways: C programmers sometimes tend to do too much of
    this, and not enough algorithmic replacement. Or they may have
    experience with only one (or a few) machines, and assume too much
    about the C standard's virtual machine. (Pointer conversions, to
    take just one example, are actually *conversions*, and result in
    new and different bit patterns on some hardware, even though many
    modern machines have only one pointer format and hence implement
    pointer casts with no actual machine instructions.)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://67.40.109.61/torek/index.html (for the moment)
    Reading email is like searching for food in the garbage, thanks to spammers.
    Chris Torek, Oct 25, 2003
    #5
  6. "Chris Torek" <> wrote in message
    news:bncp87$4ci$...
    > In article <uckmb.9426$9E1.44563@attbi_s52>
    > Glen Herrmannsfeldt <> writes:
    > >I am not at all sure what optimizers are allowed to do.

    >
    > The short version is "anything you cannot tell they have done,
    > other than by the fact that your program runs faster". :)
    >
    > There is a constraint on this, however: you must write code that
    > conforms to the appropriate standard (one of the C or Fortran
    > standards). Suppose you write code that the standard says has
    > "undefined behavior", and the compiler assumes that you have
    > not written such code. The optimizer in the compiler is allowed
    > to run with this assumption and make changes that *are* visible
    > (other than in terms of execution time). This is, in effect,
    > "your fault" and not the "compiler's fault".
    >
    > >At least in Fortran there once was a traditional optimization of
    > >moving invariant expressions out of loops. ...

    >
    > This is a typical optimization in any compiled, imperative language.
    > The theory is that loops -- especially inner loops, when loops are
    > nested -- contain code that will be run quite a bit, so if there is
    > some way to move some computation outside the loop and run it just
    > once, instead of every time, that should help a lot

    (snip)

    > >One favorite example from Fortran, but translated to C goes something

    like:
    > >
    > >for(i=0;i<n;i++) {
    > > if(a>0) b *= sqrt(a);
    > > c *= a;
    > > }
    > >
    > >There were compilers that would evaluate sqrt(a) outside the loop, keep

    the
    > >result in a register and use it in the multiply.

    >
    > C compilers can do this too, because the name sqrt() is reserved
    > to the implementation, and the compiler can recognize the call.
    > It gets hairy around the edges though, because if "a" is negative,
    > each (removed) call to sqrt() must (at least appear to) set errno
    > to EDOM. (The compiler can hoist the errno-setting if it can prove
    > that errno is not changed elsewhere in the loop, or move it below
    > the loop, or even remove it entirely, if it can prove that errno
    > is not examined. And of course, the problem never comes up if the
    > compiler can prove that a >= 0.)


    Hmm. It also should not set errno before the loop, unless it can be sure it
    isn't tested too early in the loop.

    It is a little easier than Fortran where, at least the ones I knew, it
    prints out a message. Also, I think the example I remember had a more
    complicated if statement, so that it would be harder for the compiler to
    separate the tests.

    > >Function calls don't tend to allow that optimization in general, though.



    (snip)

    > C99 adds a "restrict" qualifier that does the trick (using a rather
    > large hammer, as it were). Fortran escapes the problem by effectively
    > declaring *all* array parameters as "restrict"ed, in C99 terms.
    > Functional programming languages generally escape it by not having
    > (user-visible) pointers in the first place. :)


    One that seems to come up reasonably often is passing the same array as more
    than one argument to a subroutine. I don't know how C99 restrict works, but
    it may be similar to that. The compiler is allowed to assume that the
    arrays are different.

    > Of course, in any programming language, the programmer can hoist
    > loop invariants "manually", as it were. If the programmer knows
    > that strlen(p1) is not going to -- or even just "not supposed to"
    > -- change inside the loop, the programmer can add a loop-limit
    > variable and write "i < lim" instead of "i < strlen(p1)".


    This one has sometimes bothered me. In many languages, loop parameters are
    evaluated once and the value used throughout.

    for(i=0;i<strlen(p1);i++)

    at least implies evaluation of strlen() each time. If p1 is long, one can
    expect a significant amount of time spent in strlen(). I don't know how
    many optimize that, but in general I assume that they don't. I have at
    least once written:

    for(i=strlen(p1)-1;i>=0;i--)

    just for that reason.

    > One
    > difference between C and most other compiled languages here is that
    > many or even most of C's abstractions are typically quite a bit
    > "closer to the machine", as it were, and an experienced C programmer
    > can often tell not only which expressions are invariant, but also
    > which ones the compiler will fail to discover for itself.


    Maybe, but I don't think I have any idea which compilers will notice
    strlen() invariance inside a loop.

    > But this
    > can cut both ways: C programmers sometimes tend to do too much of
    > this, and not enough algorithmic replacement. Or they may have
    > experience with only one (or a few) machines, and assume too much
    > about the C standard's virtual machine. (Pointer conversions, to
    > take just one example, are actually *conversions*, and result in
    > new and different bit patterns on some hardware, even though many
    > modern machines have only one pointer format and hence implement
    > pointer casts with no actual machine instructions.)


    And even if the bit patterns are the same, alignment restrictions may be
    different.

    -- glen
    Glen Herrmannsfeldt, Oct 25, 2003
    #6
  7. -berlin.de wrote:

    > Hi,
    >
    > I have a possibly rather stupid question about the order of evaluation
    > in a statement like this:
    >
    > result = foo( x ) - bar( y );
    >
    > How can I make 100% sure that foo(x) is evaluated before bar(y), where
    > foo() and bar() can be either functions or macros?


    Like this:
    > result = foo( x );
    > result -= bar( y );




    --
    Martin Ambuhl
    Martin Ambuhl, Oct 25, 2003
    #7
  8. -berlin.de wrote:
    > Hi,
    >
    > I have a possibly rather stupid question about the order of evaluation
    > in a statement like this:
    >
    > result = foo( x ) - bar( y );
    >
    > How can I make 100% sure that foo(x) is evaluated before bar(y), where
    > foo() and bar() can be either functions or macros?


    <snip>

    >
    > result = foo( x );
    > result -= bar( y );
    >


    Like others said, this should do it... in theory.

    Suppose that foo and bar are defined this way:

    #define foo(x) ((x) + *p)
    #define bar(x) ((x) - *p)

    where 'p' is a pointer to some kind of register or memory-mapped I/O
    port. In this case, the compiler could "know" that the expression '*p'
    doesn't change in those two lines, and could therefore store the result
    from the foo call and use it in the bar call. This could give incorrect
    results if *p can, in fact, change after it's used in foo, before it's
    used in bar.

    Cases like these are why we have the 'volatile' qualifier. In the
    example above, 'p' should be declared with volatile. The standard
    doesn't require that this solves the problem as far as I know, but the
    intended purpose of volatile is to tell the compiler to expect the thing
    to change in ways it can't predict, so it *should* work.

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
    Kevin Goodsell, Oct 25, 2003
    #8
  9. -berlin.de

    nobody Guest

    "Glen Herrmannsfeldt" <> wrote in message
    news:0qnmb.9498$mZ5.55796@attbi_s54...
    >

    [snip]
    >
    > This one has sometimes bothered me. In many languages, loop parameters

    are
    > evaluated once and the value used throughout.
    >
    > for(i=0;i<strlen(p1);i++)
    >
    > at least implies evaluation of strlen() each time. If p1 is long, one can
    > expect a significant amount of time spent in strlen(). I don't know how
    > many optimize that, but in general I assume that they don't. I have at
    > least once written:
    >
    > for(i=strlen(p1)-1;i>=0;i--)
    >
    > just for that reason.
    >

    I think you are right, but I personally prefer (in case that "work"
    can be done in reverse order):

    int i = strlen(s);
    while (i--)
    s; /* do something sensible here */

    [snip]
    nobody, Oct 25, 2003
    #9
  10. -berlin.de

    -berlin.de Guest

    -berlin.de wrote:

    Thank you everyone for your help. Perhaps I was getting a bit too
    paranoid, but I was worried about the compiler for some reasons
    of its own "optimzing"

    result = foo( x );
    result -= bar( y );

    into

    result = - bar( y );
    result += foo( x );

    because 'result' isn't used in between the lines (that's why I was
    thinking if it might be required to declare 'result' as volatile)
    and not realizing that the function calls could have some non-trival
    (and time-critical) side effects. But I guess according to what you
    told me I can savely assume that the compiler won't play this kind
    of tricks on me.
    Regards, Jens
    --
    _ _____ _____
    | ||_ _||_ _| -berlin.de
    _ | | | | | |
    | |_| | | | | | http://www.physik.fu-berlin.de/~toerring
    \___/ens|_|homs|_|oerring
    -berlin.de, Oct 25, 2003
    #10
  11. -berlin.de

    Chris Torek Guest

    [Cross-posting reduced, now restricted to comp.lang.c only.]

    [I used an example about hoisting strlen() calls out of a "for"
    loop in C, which -- if done in the time-consuming part of a program
    -- changes an algorithm from O(n^2) to O(n), where n is the length
    of the strings.]

    In article <0qnmb.9498$mZ5.55796@attbi_s54>,
    Glen Herrmannsfeldt <> wrote:
    >This one has sometimes bothered me. In many languages, loop parameters are
    >evaluated once and the value used throughout.
    >
    >for(i=0;i<strlen(p1);i++)
    >
    >at least implies evaluation of strlen() each time. ...


    Yes. This kind of optimization, in the right place, is a big win
    (and even in the wrong place it is rarely a loss anyway). So C
    compilers "ought to" work hard to do it, if such code is common.
    It is difficult to optimize out, however, and such code is thus
    not all that common in the first place.

    On a more general note: languages that evaluate loop limits once
    -- there are quite a few -- often have a more restricted loop
    syntax. For instance, Pascal has:

    "for" var ":=" start "to" end

    with optional "step", and the "to" can be replaced by "downto" to
    count down instead of up, but no equivalent to C's:

    for (p = head; p != NULL; p = p->next)

    (which, in the code I deal with, is just about as common, if not
    more common, than the counting loop form). Fortran's DO loop is
    similar to Pascal's.

    But while these loop forms are rigid and thus too often useless,
    they still bypass a real problem in C. Suppose you want to run an
    "unsigned int" over all possible values. You might try writing:

    unsigned int ui;
    ...
    for (ui = 0; ui <= UINT_MAX; ui++)

    but this turns out to be an infinite loop: when ui == UINT_MAX,
    which should be the last trip through the loop, the end-of-loop
    increment changes ui from UINT_MAX to 0, which is still less than
    or equal to UINT_MAX. The same problem occurs with ordinary signed
    ints, except that the behavior on incrementing from INT_MAX is
    undefined. Actual machines mostly give you INT_MIN, which will
    test "<= INT_MAX", likewise leading to an infinite loop. A "nicer"
    (in some sense) system might point out the overflow instead.

    In Pascal, the loop limits are evaluated once at the top of the
    loop, then the number of trips is determined, and the loop runs
    that many times, no matter what. This solves the INT_MAX problem
    at the expense of inflexibility. For these corner cases in C,
    you must write something like:

    if (first_value <= last_value) {
    unsigned int n_trips_minus_1 = last_value - first_value;
    i = first_value;
    do {
    ... loop contents ...
    } while (--n_trips_minus_one != 0 && (i++, 1));
    }

    (replace "unsigned int" with "unsigned long" if needed; note that
    LAST_VALUE can be INT_MAX or UINT_MAX so we must use the loop's
    final value, not one beyond it). The ugly tricky bit where the
    "i++" is executed if and only if the loop will be continued is not
    required if "i" has unsigned type (or if signed overflow leading
    to undefined behavior does not bother you :) ) -- in this case:

    do {
    ... loop contents ...
    i++;
    } while (--n_trips_minus_one);

    suffices.

    In some of the more common cases, a bit of thought will do the
    trick without all this machinery -- for instance, the "loop over
    all possible unsigned int values" loop does not need a trip
    counter, just the test moved to the bottom:

    ui = 0;
    do {
    ... loop contents ...
    } while (++ui != 0);

    but it still might be nice to have, in C, a special syntax that
    "does the right thing" for counting loops.

    The danger in going down this road is that one eventually winds up
    with a language like Common Lisp, with 13571278165125 forms of loop
    construct. :)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://67.40.109.61/torek/index.html (for the moment)
    Reading email is like searching for food in the garbage, thanks to spammers.
    Chris Torek, Oct 26, 2003
    #11
  12. -berlin.de

    CBFalconer Guest

    Chris Torek wrote:
    >

    .... snip ...
    > >
    > >at least implies evaluation of strlen() each time. ...

    >
    > Yes. This kind of optimization, in the right place, is a big win
    > (and even in the wrong place it is rarely a loss anyway). So C
    > compilers "ought to" work hard to do it, if such code is common.
    > It is difficult to optimize out, however, and such code is thus
    > not all that common in the first place.
    >
    > On a more general note: languages that evaluate loop limits once
    > -- there are quite a few -- often have a more restricted loop
    > syntax. For instance, Pascal has:
    >
    > "for" var ":=" start "to" end
    >
    > with optional "step", and the "to" can be replaced by "downto" to
    > count down instead of up, but no equivalent to C's:
    >
    > for (p = head; p != NULL; p = p->next)
    >

    .... snip ...
    >
    > In Pascal, the loop limits are evaluated once at the top of the
    > loop, then the number of trips is determined, and the loop runs
    > that many times, no matter what. This solves the INT_MAX problem
    > at the expense of inflexibility. For these corner cases in C,
    > you must write something like:


    Not quite. The Pascal for has a termination point, not
    condition. There is no need to evaluate the number of repetitions
    in advance, although that may be done. Many Pascal systems have
    had a bug in "FOR i := 1 TO maxint DO ...". However the critical
    points are that the initial and terminal conditions are evaluated
    before the loop is entered, and that the value of i may not be
    altered within the loop, nor meaningfully referenced after loop
    termination. Having stamped these bugs out years ago in my own
    code, I am quite aware of them.

    As another example:

    i := 5;
    FOR i := 1 TO i + 5 DO ...;
    writeln(i); (* is indeterminate *)

    executes for i values of 1 through 10.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
    CBFalconer, Oct 27, 2003
    #12
  13. "Chris Torek" <> wrote in message
    news:bnhme6$7oq$...
    > [Cross-posting reduced, now restricted to comp.lang.c only.]
    >
    > [I used an example about hoisting strlen() calls out of a "for"
    > loop in C, which -- if done in the time-consuming part of a program
    > -- changes an algorithm from O(n^2) to O(n), where n is the length
    > of the strings.]
    >
    > In article <0qnmb.9498$mZ5.55796@attbi_s54>,
    > Glen Herrmannsfeldt <> wrote:
    > >This one has sometimes bothered me. In many languages, loop parameters

    are
    > >evaluated once and the value used throughout.
    > >
    > >for(i=0;i<strlen(p1);i++)
    > >
    > >at least implies evaluation of strlen() each time. ...

    >
    > Yes. This kind of optimization, in the right place, is a big win
    > (and even in the wrong place it is rarely a loss anyway). So C
    > compilers "ought to" work hard to do it, if such code is common.
    > It is difficult to optimize out, however, and such code is thus
    > not all that common in the first place.
    >
    > On a more general note: languages that evaluate loop limits once
    > -- there are quite a few -- often have a more restricted loop
    > syntax. For instance, Pascal has:
    >
    > "for" var ":=" start "to" end
    >
    > with optional "step", and the "to" can be replaced by "downto" to
    > count down instead of up, but no equivalent to C's:


    I looked up what PL/I does for this. The limits are evaluated once and used
    for the loop. The BY (increment) can be positive or negative, (or zero) and
    the loop works appropriately. One I hadn't though of before, the address
    of the loop variable is also computed once and used throughout. This is
    significant because of the way PL/I does pointers, and also CONTROLLED
    variables. PL/I DO loops with TO and/or BY can also have a WHILE test at
    the same time. If both TO and BY are omited the loop is only done once. A
    list of values, or TO/BY sets can also be supplied.

    > for (p = head; p != NULL; p = p->next)


    Well, it could be done with a WHILE loop in languages that have one.
    Putting the initialization and updating in the same statement is a little
    convenient, though.

    > (which, in the code I deal with, is just about as common, if not
    > more common, than the counting loop form). Fortran's DO loop is
    > similar to Pascal's.


    > But while these loop forms are rigid and thus too often useless,
    > they still bypass a real problem in C. Suppose you want to run an
    > "unsigned int" over all possible values. You might try writing:
    >
    > unsigned int ui;
    > ...
    > for (ui = 0; ui <= UINT_MAX; ui++)


    I wouldn't be surprised if the other languages don't catch this one, either.
    IBM declared 32 bit addressing on the 360/67 a bug because the loop
    instructions would fail in cases like this. If you were looping over
    addresses, and hadn't checked where you were in virtual address space, you
    could unintentionally run into this problem.

    > but this turns out to be an infinite loop: when ui == UINT_MAX,
    > which should be the last trip through the loop, the end-of-loop
    > increment changes ui from UINT_MAX to 0, which is still less than
    > or equal to UINT_MAX. The same problem occurs with ordinary signed
    > ints, except that the behavior on incrementing from INT_MAX is
    > undefined. Actual machines mostly give you INT_MIN, which will
    > test "<= INT_MAX", likewise leading to an infinite loop. A "nicer"
    > (in some sense) system might point out the overflow instead.


    > In Pascal, the loop limits are evaluated once at the top of the
    > loop, then the number of trips is determined, and the loop runs
    > that many times, no matter what. This solves the INT_MAX problem
    > at the expense of inflexibility. For these corner cases in C,
    > you must write something like:


    There was some discussion not so long ago about Fortran's treatment of
    floating point variables in DO loops. They were not allowed in Fortran-66,
    but added later. In that case, also, the number of trip is determined in
    advance, such that, in certain rounding cases, the terminating condition
    might not occur at the end of the loop!

    > if (first_value <= last_value) {
    > unsigned int n_trips_minus_1 = last_value - first_value;
    > i = first_value;
    > do {
    > ... loop contents ...
    > } while (--n_trips_minus_one != 0 && (i++, 1));
    > }
    >


    (snip of more loops going to UINT_MAX)

    -- glen
    Glen Herrmannsfeldt, Oct 27, 2003
    #13
  14. In article <bnhme6$7oq$>,
    Chris Torek <> wrote:

    > In some of the more common cases, a bit of thought will do the
    > trick without all this machinery -- for instance, the "loop over
    > all possible unsigned int values" loop does not need a trip
    > counter, just the test moved to the bottom:
    >
    > ui = 0;
    > do {
    > ... loop contents ...
    > } while (++ui != 0);
    >
    > but it still might be nice to have, in C, a special syntax that
    > "does the right thing" for counting loops.


    A suggestion (which will never make it into the C Standard, but I quite
    like it):

    Step 1: Change the syntax so that expressions of the form a <= b <= c
    become illegal. That is no big loss, and writing them as (a <= b) <= c
    would be much better anyway. (Has anybody ever used such an expression? )

    Step 2: An alternative syntax for the for loop:

    for (expr1 <= lvalue <= expr2)

    Semantics: expr1, expr2 and the address of lvalue are evaluated once
    without intervening sequence point; then expr1 and expr2 are converted
    to the type of lvalue.

    If lvalue is an integer, then the loop body is executed with lvalue
    being set to all values x such that expr1 <= x <= expr2 in ascending
    order. If lvalue is a non-void pointer then the loop is executed with
    all pointer values (expr1 + x) such that expr1 <= expr1 + x <= expr2. If
    lvalue is a floating point variable, then lvalue is set to all integer
    values such that expr1 <= x <= expr2; if any of these integers cannot be
    represented as a floating-point number then behavior is undefined.

    Instead of <=, any combination of <= and < can be used with the obvious
    changes. Instead of <= and <, any combination of >= and > can be used
    with the obvious changes, and the values will be used in descending
    order.

    If lvalue is modified inside the loop other than by the loop semantics,
    behavior is undefined. The value of (lvalue) after execution of the loop
    is undefined.
    Christian Bau, Oct 27, 2003
    #14
  15. -berlin.de

    Dan Pop Guest

    In <bncdbe$1020c4$> -berlin.de writes:

    > I have a possibly rather stupid question about the order of evaluation
    >in a statement like this:
    >
    >result = foo( x ) - bar( y );
    >
    >How can I make 100% sure that foo(x) is evaluated before bar(y), where
    >foo() and bar() can be either functions or macros?


    Certainly not by writing the expression this way.

    >I got into problems
    >with this when writing some hardware-related stuff where foo() and bar()
    >are functions or macros (I want to make sure the solution is independent
    >of this) that read certain hardware registers and that need to be read
    >in a specific order. The compiler "optimized" the code by reversing the
    >reads, which isn't a very good idea in this case. For the time being I
    >found that rewritting the above as
    >
    >result = foo( x );
    >result -= bar( y );
    >
    >gets rid of the problem, but I am not sure if this really guarantees
    >that foo(x) is evaluated before bar(y) when I use a different compiler
    >or a different version.


    It's safe enough: the compiler can't assume that foo() and/or bar() are
    pure functions and without such assumptions the order of evaluation cannot
    be altered. Imagine that foo() contains printf("Hello, "); and bar
    contains printf("world!\n");. In the abstract C machine, the output
    is "Hello, world!\n" and no conforming C implementation is allowed to
    generate a different output.

    You can still evaluate the thing as a single expression:

    result = foo(x), result -= bar(y);

    but it's the same thing as your solution, for all intents and purposes.

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
    Dan Pop, Oct 27, 2003
    #15
  16. new forall statement?

    "Christian Bau" <> wrote in message
    news:...

    (snip regarding the termination of for loops at UINT_MAX or INT_MAX)

    > A suggestion (which will never make it into the C Standard, but I quite
    > like it):
    >
    > Step 1: Change the syntax so that expressions of the form a <= b <= c
    > become illegal. That is no big loss, and writing them as (a <= b) <= c
    > would be much better anyway. (Has anybody ever used such an expression? )
    >
    > Step 2: An alternative syntax for the for loop:
    >
    > for (expr1 <= lvalue <= expr2)
    >
    > Semantics: expr1, expr2 and the address of lvalue are evaluated once
    > without intervening sequence point; then expr1 and expr2 are converted
    > to the type of lvalue.
    >
    > If lvalue is an integer, then the loop body is executed with lvalue
    > being set to all values x such that expr1 <= x <= expr2 in ascending
    > order. If lvalue is a non-void pointer then the loop is executed with
    > all pointer values (expr1 + x) such that expr1 <= expr1 + x <= expr2. If
    > lvalue is a floating point variable, then lvalue is set to all integer
    > values such that expr1 <= x <= expr2; if any of these integers cannot be
    > represented as a floating-point number then behavior is undefined.
    >
    > Instead of <=, any combination of <= and < can be used with the obvious
    > changes. Instead of <= and <, any combination of >= and > can be used
    > with the obvious changes, and the values will be used in descending
    > order.
    >
    > If lvalue is modified inside the loop other than by the loop semantics,
    > behavior is undefined. The value of (lvalue) after execution of the loop
    > is undefined.


    I think I don't like it as overloading the for statement, and also the
    relational operators. Note that expr1 <= expr2 <= expr3 already has meaning
    in the C language, and it isn't what you want.

    There are some extensions to C for parallel machines that use a forall
    statement. My suggestion, instead, is to add a forall statement to C, with
    reasonably syntax, and including the requirement that the bounds be
    evaluated once and that the loop variable not be changed inside the loop.
    In addition, it should allow the compiler to reorder the execution of the
    loop body, such as executing it in parallel on machines that allow that.

    It would slowly gain use, as people realized that evaluating the bounds once
    can be an advantage, and the requirements on the loop variable can help
    optimizing compilers even on serial machines.

    -- glen
    Glen Herrmannsfeldt, Oct 27, 2003
    #16
    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. cheeser
    Replies:
    3
    Views:
    394
    =?iso-8859-1?Q?Juli=E1n?= Albo
    Oct 5, 2003
  2. Ilias Lazaridis
    Replies:
    2
    Views:
    388
    Ilias Lazaridis
    Apr 24, 2005
  3. subnet

    Order of function parameters evaluation

    subnet, Mar 7, 2005, in forum: C Programming
    Replies:
    13
    Views:
    501
    CBFalconer
    Mar 9, 2005
  4. Ilias Lazaridis
    Replies:
    74
    Views:
    745
    Ilias Lazaridis
    Apr 4, 2005
  5. Ilias Lazaridis
    Replies:
    18
    Views:
    328
    Bill Guindon
    Apr 9, 2005
Loading...

Share This Page