Order of function evaluation

[Jens.Toerring]

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
--
_ _____ _____
| ||_ _||_ _| Je***********@physik.fu-berlin.de
_ | | | | | |
| |_| | | | | | http://www.physik.fu-berlin.de/~toerring
\___/ens|_|homs|_|oerring

[Sheldon Simms]

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.

[Alex]

Je***********@physik.fu-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

[Glen Herrmannsfeldt]

"Sheldon Simms" <sh**********@yahoo.com> wrote in message
news:pa****************************@yahoo.com...

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[i] *= sqrt(a);
c[i] *= 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

[Chris Torek]

In article <uckmb.9426$9E1.44563@attbi_s52>
Glen Herrmannsfeldt <ga*@ugcs.caltech.edu> 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[i] *= sqrt(a);
c[i] *= 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[i]);
}

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) [phone]
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.

[Glen Herrmannsfeldt]

"Chris Torek" <no****@elf.eng.bsdi.com> wrote in message
news:bn**********@elf.eng.bsdi.com...

In article <uckmb.9426$9E1.44563@attbi_s52>
Glen Herrmannsfeldt <ga*@ugcs.caltech.edu> 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[i] *= sqrt(a);
c[i] *= a;
}

There were compilers that would evaluate sqrt(a) outside the loop, keep theresult 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

[Martin Ambuhl]

Je***********@physik.fu-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

[Kevin Goodsell]

Je***********@physik.fu-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.

[Jens.Toerring]

Je***********@physik.fu-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
--
_ _____ _____
| ||_ _||_ _| Je***********@physik.fu-berlin.de
_ | | | | | |
| |_| | | | | | http://www.physik.fu-berlin.de/~toerring
\___/ens|_|homs|_|oerring

[nobody]

"Glen Herrmannsfeldt" <ga*@ugcs.caltech.edu> 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[i]; /* do something sensible here */

[snip]

[Chris Torek]

[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 <ga*@ugcs.caltech.edu> 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) [phone]
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.

[CBFalconer]

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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Glen Herrmannsfeldt]

"Chris Torek" <no****@elf.eng.bsdi.com> wrote in message
news:bn**********@elf.eng.bsdi.com...

[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 <ga*@ugcs.caltech.edu> wrote:

This one has sometimes bothered me. In many languages, loop parameters areevaluated 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

[Christian Bau]

In article <bn**********@elf.eng.bsdi.com>,
Chris Torek <no****@elf.eng.bsdi.com> 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.

[Dan Pop]

In <bn*************@uni-berlin.de> Je***********@physik.fu-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: Da*****@ifh.de

[Glen Herrmannsfeldt]

"Christian Bau" <ch***********@cbau.freeserve.co.uk> wrote in message
news:ch*********************************@slb-newsm1.svr.pol.co.uk...

(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