Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!uwm.edu!rpi!not-for-mail
From: ka...@gabi-soft.de (James Kanze)
Newsgroups: comp.lang.c++.moderated
Subject: Re: THE POSTINCREMENT TIME
Date: 24 Apr 2003 19:15:27 -0400
Organization: http://groups.google.com/
Lines: 135
Sender: cppm...@netlab.cs.rpi.edu
Approved: ku...@inf.uni-konstanz.de
Message-ID: <d6651fb6.0304240155.5e5d9a92@posting.google.com>
References: <3E9BFD38.3010000@eurocom.od.ua>
 <k92s9vkhgsi1leda5gv9ihq4n191c4lbt3@4ax.com>
 <9e3a34f7.0304180207.46e672e0@posting.google.com>
 <O4Z2KkClvco+Ewi3@robinton.demon.co.uk>
 <9e3a34f7.0304211139.35a62019@posting.google.com>
 <d6651fb6.0304220720.76b64043@posting.google.com>
 <0dmbav8iogrogrh1otrd0aki2d7fe422pj@4ax.com>
 <9e3a34f7.0304230547.6ce135fb@posting.google.com>
NNTP-Posting-Host: netlab.cs.rpi.edu
X-Original-Date: 24 Apr 2003 02:55:50 -0700
X-Submission-Address: c++-sub...@netlab.cs.rpi.edu
X-Auth: PGPMoose V1.1 PGP comp.lang.c++.moderated
	iQBVAwUAPqhwDEHMCo9UcraBAQEJ0QH/aeDCO4y2pEUIlxgpRdvBDkEJ3ko5Lzwz
	ADQF4TZQRdQU68v32CfSavautk6tkzu7oxhFJQWnmJ/5XtV+gscoKQ==
	=UGMc

terj...@chello.no (Terje Slettebø) wrote in message
news:<9e3a34f7.0304230547.6ce135fb@posting.google.com>...
> John Potter <jpot...@falcon.lhup.edu> wrote in message
> news:<0dmbav8iogrogrh1otrd0aki2d7fe422pj@4ax.com>...
    [...]
> I still wonder why it would be undefined behaviour in the case of pass
> by value. To rewrite it like that:

> int f (int, int);
> int g (int); // Note
> int h (int);
> int c(21);
> int p(f(g(c),h(c++)));

> To evaluate f(), it needs to evaluate g(c) and h(h++). However, as I
> understand, it can't interleave their evaluation.

Why not?  §5/4: "Except where noted, the order of evaluation of operands
of individual operators and subexpressions of individual expressions,
and the order in which side effects take place, is unspecified."

In practice, about the only things that limit reordering are:

  - causal necessity (in an expression like a + b, the compiler must
    evaluate a and b before doing the addition), and

  - sequence points (in the above, the call to h is a sequence point, so
    the side effects of c++ must have taken place before the call).

Within an expression, these only introduce partial ordering.  Thus, if
we consider the following simple operations: read c for g, read c for
incr, incr, store results of incr, call g, call h, call f, we have the
following ordering restrictions (using < to mean "must be before":

    read c for g          < call g                  causal necessity
    read c for incr       < incr                    causal necessity
    incr                  < store results of incr   causal necessity
    incr                  < call h                  causal necessity
    store results of incr < call h                  sequence point
    call g                < call f                  causal necessity
    call h                < call f                  causal necessity

(Those "causal necessity" before a function call could also be
attributed to the sequence point.  But even without a sequence point,
they would be necessary.)

Any reordering which respects the above constraints is a legal execution
path for the abstract machine.  If any legal execution path results in
undefined behavior, the behavior is undefined.  Accessing a variable
that is modified without an intervening sequence point (e.g. a function
call) other than to determine the new value (which of course, introduces
implicit ordering due to causal necessity) is undefined behavior.  (The
reasoning behind this rule is that in practice, even reading and writing
values are not atomic operations, and if there is no ordering
constraint, the compiler may schedule them such that they overlap.
Which really does give strange behavior on certain machines.)

In this case, one possible ordering is:

    read c for incr
    incr
    store results of incr
    read c for c
    ...

According to the standard, I have undefined behavior, because I have
read a variable (c) which is being modified, for a reason other than
determining the new value, and there is NO intervening sequence point.
The reason for this rule is that on some real hardware, the store and
the read above might overlap, and really give undefined behavior.  (I
believe that at the time this issue was being discussed in the C
standard, someone pointed out a machine, perhaps only theoretical, in
which such a sequencing would result in a hardware deadlock.)

At any rate, the important thing to realize is that the ordering is only
partial.  (At some point in the history of the C standard, there was
even a question as to whether the C standard allowed interleaving of the
two functions.  After all, the function call to h isn't in any way
ordered by the sequence points in the call to g, and vice versa.  The
decision of the C committee was that interleaving functions was illegal,
since it would effectively make the program act as if it were
multi-threaded.)

> To list some possibilities, like you did in an earlier posting:

Some isn't enough.  The fact that there are one or two possibilities
which don't cause problems isn't enough.

> Evaluate g(c)
> -------------
> Evaluate c
> Call g()

> Evaluate h(c++)
> ---------------
> Evaluate c++
> Call h()

> Call f()

> Or the other way around, for g(c) and h(c++).

> In order to evaluate c and c++ right after each other, with no
> intervening sequence point, it seems it would need to first partly
> evaluate g(c) (only evaluating the c part, but not calling the
> function), and then partially evaluate h(c++).

> Can it do that?

Of course it can.

> Any reference to the standard regarding this would also be
> appreciated.

See above.  Given that, the burden of proof is now on the other side:
you must show some passage ("otherwise noted") to forbid the specified
reordering.  (In this case, I'm pretty sure that there isn't one.)

If I recall right, the classical example when the issue was being
discussed in C was something like:

    (i++, j) + (j++, i)

The comma operators ensure sequence points.  However, the sequence
points don't ensure any ordering between elements in the two
sub-expressions of the +.  This expression thus has undefined behavior.

--
James Kanze             GABI Software             mailto:ka...@gabi-soft.fr
Conseils en informatique orientée objet/
                           Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, Tél. : +33 (0)1 30 23 45 16

      [ Send an empty e-mail to c++-h...@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]