From: martin@mwtech.UUCP (Martin Weitzel)
Newsgroups: comp.lang.c
Subject: Re: unpredictable post-decrement behavior.
Date: 12 Oct 92 19:31:09 GMT
Reply-To: martin@mwtech.UUCP (Martin Weitzel)
Organization: MIKROS Systemware, Darmstadt/W-Germany

In article <1992Oct1.213002.3631@blaze.cs.jhu.edu> wilson@rhombus.cs.jhu.edu (Dwight Wilson) writes:

>It's even worse in a K&R compiler.  K&R (1st edition) stated that
>the compiler was allowed to reorder expressions using mathematically
>commutative and associative operators.  That is, if you wrote 
>'a * b * c', the compiler could decide to reorder that as 'c * a * b' 
>(even if you used parenthesis).  Note that though the operator
>is mathematically commutative and associative, it might not be
>computationally commutative and associative.

Correct so far.

>ANSI revokes this freedom.  If you write a * b * c, you don't know
>the evaluation order, but you do know that the compiler doesn't
>compute[%] a * c, then multiply by b.
>
>-Dwight

Yes and no.  ANSI-C leaves many doors open for the implementor with its
"as if"-rule.  In general a compiler can generate any code it wants as long
as it is not possible to write a program# that finds out the difference to
the `abstract semantics' specified by the ANSI-Standard document.  These
semantics demand that first a * b is computed, multiplying the result by
c.  If the compiler can assure that the result is the same, the real
computation can be done in any order that seems appropriate.

IMHO most compilers will be able to decide that the result doesn't
change for unsigned types, same for signed integers on most hardware
without overflow detection.  But in case of floating types, changes
in the order of evaluation probably may not occur or only if one of a, b
or c is constant and has some special value (e.g. 0 or 1).

Interrestingly, the "as if"-rule can be stressed further up to the point
that a compiler is not obliged to generate code at all if executing the
resulting program produces no output, modifies no files etc (in short: if
the programs execution cannot be noticed).($)

% Nitpicking footnote: As long as a, b, and c are not constants, a compiler
will hardly compute anything itselfs but rather emit the machine code that
will (at some time later) compute a * c ...

#: Of course here I speak of a program in the class of "strictly conforming
programs".  As such implies that multiplication doesn't overflow for the
given values (which has implementation defined results and hence outrules
the program to be strictly conforming), on hardware that detects overflow
you might well be able to write a program whichs output changes if the
compiler re-orders the expression.

$: I'm not quite sure how far the requirements concerning the order of
evaluation expand if the variables in the above example are declared
"volatile".  More specific: I don't know if ANSI-C requires only that the
computation is done according to the abstract semantics, or if also memory
access must follow that order.  It's clear to me that there has to be
exactly one read access to each of the memory locations of a, b and c
if these are volatile.  Though I strongly suppose that most compilers will
keep very close to the abstract semantics if volatile variables are in the
game, I'm not sure about the exact requirements with respect to memory
access.  If one views memory access to a volatile as `side effect' like
increment or assignment, it could well be argued that any access must be
carried out after the previous and before the following sequence point,
but not in a specific order.
-- 
Martin Weitzel, email: martin@mwtech.UUCP, voice: 49-(0)6151-6 56 83