rhg@cpsolv.UUCP (Richard H. Gumpertz) (09/01/89)
The exchange of x and y that has been under discussion:
x ^= y ^= x ^= y
is non-portable because it depends on right-to-left evaluation which is NOT
specified in the C standard. To be portable, use
(x ^= y, x ^= y ^= x) or (y ^= x ^= y, x ^= y)
either of which forces the two assignments to x to be done in a well-defined
order.
Richard H. Gumpertz
I am the company, so no disclaimer is needed! :-)CCDN@levels.sait.edu.au (DAVID NEWALL) (09/04/89)
In article <149@cpsolv.UUCP>, rhg@cpsolv.UUCP (Richard H. Gumpertz) writes: > The exchange of x and y that has been under discussion: > x ^= y ^= x ^= y > is non-portable because it depends on right-to-left evaluation which is NOT > specified in the C standard. I think it is specified. (Perhaps it depends on whose standard you follow?) K&R I, page 19: "The line nl = nw = nc = 0; sets all three variables to zero. This is not a special case, but a consequence of the fact that an assignment has a value and assignments associate right to left." David Newall Phone: +61 8 343 3160 Unix Systems Programmer Fax: +61 8 349 6939 Academic Computing Service E-mail: ccdn@levels.sait.oz.au SA Institute of Technology Post: The Levels, South Australia, 5095
cpcahil@virtech.UUCP (Conor P. Cahill) (09/06/89)
In article <1400@levels.sait.edu.au>, CCDN@levels.sait.edu.au (DAVID NEWALL) writes: > In article <149@cpsolv.UUCP>, rhg@cpsolv.UUCP (Richard H. Gumpertz) writes: > > The exchange of x and y that has been under discussion: > > x ^= y ^= x ^= y > > is non-portable because it depends on right-to-left evaluation which is NOT > > specified in the C standard. > > I think it is specified. (Perhaps it depends on whose standard you follow?) > > K&R I, page 19: > "The line > nl = nw = nc = 0; > sets all three variables to zero. This is not a special case, but a > consequence of the fact that an assignment has a value and assignments > associate right to left." But, you cannot know what the value of x is at the far left of the equation prior to evaluating the "^=". It may be the original value of x, or it may be the latest value of x (modified by the right hand side of the equation. As far as I know, there is no specification as to when the x will be evaluated. -- +-----------------------------------------------------------------------+ | Conor P. Cahill uunet!virtech!cpcahil 703-430-9247 ! | Virtual Technologies Inc., P. O. Box 876, Sterling, VA 22170 | +-----------------------------------------------------------------------+
karzes@mfci.UUCP (Tom Karzes) (09/07/89)
In article <1400@levels.sait.edu.au> CCDN@levels.sait.edu.au (DAVID NEWALL) writes: >In article <149@cpsolv.UUCP>, rhg@cpsolv.UUCP (Richard H. Gumpertz) writes: >> The exchange of x and y that has been under discussion: >> x ^= y ^= x ^= y >> is non-portable because it depends on right-to-left evaluation which is NOT >> specified in the C standard. > >I think it is specified. (Perhaps it depends on whose standard you follow?) > >K&R I, page 19: > "The line > nl = nw = nc = 0; > sets all three variables to zero. This is not a special case, but a > consequence of the fact that an assignment has a value and assignments > associate right to left." No, it is not specified. The K&R example is merely pointing out that the assignment is parsed as: nl = (nw = (nc = 0)); To evaluate the outer assignment, both the destination and the right hand side must be evaluated. The order doesn't matter in this case. The right hand side (nw = (nc = 0)) is evaluated and its value is 0, which is the value used in the outer assignment. In the ^= case, the assignment is parsed as: x ^= (y ^= (x ^= y)); To evaluate the outer assignment, the destination must be evaluated (and unlike the previous example, its value is also needed) and the right hand side must be evaluated. However, in this case the order DOES matter. If the right hand side is evaluated before x is evaluated, then x will have the desired value (the value computed by x ^= y). However, if x is evaluated before the right hand side, then the x ^= y assignment in the right hand side will effectively have been ignored. When evaluating a ^= b, the compiler may generate any of the following: 1. evaluate a, evaluate b, xor, assign 2. evaluate b, evaluate a, xor, assign 3. some hybrid of 1 and 2 If it chooses the first sequence for the outer assignment in the original ^= example, the example will fail. In fact, I'm not even certain that all side effects resulting from the evaluation of a and b must be completed before the assignment takes place. (E.g., could x = 2 + (x = 5); perform the actual assignment for (x = 5) after the outer assignment? If it knows that the value of (x = 5) is 5, could it delay the store to x? I don't believe assignment consitutes a sequence point in its own right. One could imagine "evaluate 5, evaluate 2, add, assign result, 7, to x, assign previous result, 5, to x".)
diamond@csl.sony.co.jp (Norman Diamond) (09/08/89)
In article <149@cpsolv.UUCP>, rhg@cpsolv.UUCP (Richard H. Gumpertz) writes: >> The exchange of x and y that has been under discussion: >> x ^= y ^= x ^= y >> is non-portable because it depends on right-to-left evaluation which is NOT >> specified in the C standard. True, though perhaps a bit too terse for some people. In article <1400@levels.sait.edu.au> CCDN@levels.sait.edu.au (DAVID NEWALL) writes: >I think it is specified. (Perhaps it depends on whose standard you follow?) >K&R I, page 19: > "The line > nl = nw = nc = 0; > sets all three variables to zero. This is not a special case, but a > consequence of the fact that an assignment has a value and assignments > associate right to left." OK, let's try to make it perfectly clear. x ^= y ^= x ^= y [3] [2] [1] The order of evaluation is [1], [2], [3]. But what about the operands? [1] middle x = old x ^ old y [2] new y = old y ^ middle x [3] new x = which x ^ new y If new x = middle x ^ new y, it works. But if new x = old x ^ new y, it doesn't work. Neither K&R nor the pants say when the operand value of x is fetched for assignment [3]. It could be either before or after assignment [1] completes. -- -- Norman Diamond, Sony Corporation (diamond@ws.sony.junet) The above opinions are inherited by your machine's init process (pid 1), after being disowned and orphaned. However, if you see this at Waterloo or Anterior, then their administrators must have approved of these opinions.
rhg@cpsolv.UUCP (Richard H. Gumpertz) (09/08/89)
"x ^= y ^= x ^= y" differs from "x = y = z = 0" in that the former makes TWO
assignments to x. Side effects (i.e., assignments to variables) need only be
completed at "sequence points"; between sequence points, any order of
evaluation (including assignment operators) is allowed!
The following are all legal interpretations of the sequence in question,
yet may yield different results:
(t = x ^= y, x ^= y ^= t)
(t = x, y ^= x ^= y, x = t ^ y)
(t = x ^ y, x ^= y ^= t, x = t)
I am sure there are other interpretations as well.kenny@m.cs.uiuc.edu (09/11/89)
With respect to the action taken by x ^= y ^= x ^= y, I'm now confused
by the discussions of order of evaluation -- and I *thought* I
understood this stuff. If it were any lesser a light that Chris Torek
posting, I'd have said, `wrong, wrong, wrong!', but now I suspect that
I'm misunderstanding something.
OK, to begin with, we all seem to be agreed that there's only one
possible way to parse this expression, given the right-to-left
associativity of ^=:
^= <- A
/ \
x ^= <- B
/ \
y ^= <- C
/ \
x y
Now, if I read the Standard right, there is also only one possible
order of evaluation. C must be evaluated first, then B, and then A.
This is constrained because evaluating B requires the result of C, and
evaluating A requires the result of B. Order of evaluation therefore
also has nothing to do with the problem.
Where the trouble comes from is rather the evaluation of side effects.
When evaluating expression C, the compiler is free to stash its value
away, and not store it in x immediately. It is possible that by the
time that the compiler is evaluating expression A, the new value of x
will not have been stored, and that expression A will work on the old
value.
The result will be that y will always get the correct value. x may or
may not get the correct value; it may rather get its original value
xor'ed with the new value of y; that is to say, zero.
These two are the only possibilities, since there is only one
side-effect assignment in the entire expression. It isn't possible,
for instance, for expression A to use the old value of y; it isn't
using y at all, but rather the result of expression B.
Have I gone astray here?
| / o Kevin Kenny (217) 333-5821
|< /) | | | |/\ Department of Computer Science o , o ,
| \ X_ \/ | | | University of Illinois 40 07 N 88 13 W
kenny@cs.uiuc.edu 1304 W. Springfield Ave.
uunet!uiucdcs!kenny Urbana, IL 61801 AD ASTRA PER ARDUA
k-kenny@uiuc.edu
kenny%cs@uiucvmd.bitnetchris@mimsy.UUCP (Chris Torek) (09/12/89)
In article <4700044@m.cs.uiuc.edu> kenny@m.cs.uiuc.edu writes: >... we all seem to be agreed that there's only one possible way to >parse [x ^= y ^= x ^= y] ... Right. > ^= <- A > / \ > x ^= <- B > / \ > y ^= <- C > / \ > x y > >Now, if I read the Standard right, there is also only one possible >order of evaluation. C must be evaluated first, then B, and then A. >This is constrained because evaluating B requires the result of C, and >evaluating A requires the result of B. While it is true that evaluation of B cannot be *finished* until the result of C is known, and likewise A-and-B, it is *not* true that C must be even partially evaluated before B is begun. If this were all there was to it, the following statement would be true: >Where the trouble comes from is rather the evaluation of side effects. The trouble comes about because of side effects---that is, in a side- effect-free expression, the order of evaluation is (not including overflow and other exceptions) irrelevant because it is not observable. >When evaluating expression C, the compiler is free to stash its value >away, and not store it in x immediately. It is possible that by the >time that the compiler is evaluating expression A, the new value of x >will not have been stored, and that expression A will work on the old >value. This is true, but is not the whole story. The compiler can instead begin evaluating A, to the extent of fetching the current value of x, then discover that it needs to evaluate B before it can finish. It can then begin evaluating B, to the extent of fetching the current value of y, and then discover that it needs C; it evaluates C by fetching x, then fetching y, then computing the xor, then storing in x; it then finishes B by xoring the saved value of y with the value computed at C and storing in x; and then it finishes A by xoring the saved value of x with the value computed at B. >The result will be that y will always get the correct value. x may or >may not get the correct value; it may rather get its original value >xor'ed with the new value of y; that is to say, zero. Note that we have achieved the same result with two different methods. If you prefer, here are the (pseudo) assembly language steps: # (a): evaluation order is C, B, A, store, store, store # (pre-peephole-optimisation) load r1,y load r2,x xor r1,r2,r3 | result of C in r3 load r4,y xor r3,r4,r5 | result of B in r5 load r6,x xor r5,r6,r7 | result of A in r7 store r7,x | store result of A store r5,y | store result of B store r3,x | store result of C # The preceding 3 could actually happen in any order, # although `A,B,C' or `C,B,A' are most likely from real # compilers. # # Peephole optimisation would replace r4 and r6 with # r1 and r2 respectively, and eliminate one of the two # stores to x; the result would be optimal for a machine # with a large register set and a two-or-more-register-deep # write buffer. # # This evaluation order is natural to some simple RISC compilers. % (b): evaluation order is A .. B .. C .. finish B .. finish A % x ^= y ^= x ^= y /x x /y y /x x y xor dup 3 1 roll def xor dup 3 1 roll def xor dup 3 1 roll def pop % (it might be 3 -1 roll everywhere; I always have to look this up). % This evaluation order is natural to simple C-to-PostScript % compilers. A small but useful optimisation would be to change % var op= expr % from % /var var <eval-rhs> dup 3 1 roll def % to % /var var <eval-rhs> def % when the value of the expression itself is not needed. This % changes the last two lines to `xor def'. >These two are the only possibilities, since there is only one >side-effect assignment in the entire expression. This is correct, because the side effect is the only way that the evaluation order becomes observable. >Have I gone astray here? Only in the mechanics of what is going on `under the hood', as it were. As long as we ignore things like overflow exceptions, evaluation order is irrelevant unless side effects get in the way. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
tim@cayman.amd.com (Tim Olson) (09/12/89)
In article <4700044@m.cs.uiuc.edu> kenny@m.cs.uiuc.edu writes: | | OK, to begin with, we all seem to be agreed that there's only one | possible way to parse this expression, given the right-to-left | associativity of ^=: | | ^= <- A | / \ | x ^= <- B | / \ | y ^= <- C | / \ | x y Right. | Now, if I read the Standard right, there is also only one possible | order of evaluation. C must be evaluated first, then B, and then A. | This is constrained because evaluating B requires the result of C, and | evaluating A requires the result of B. Order of evaluation therefore | also has nothing to do with the problem. I think your confusion lies in what is meant by "evaluation". Evaluation consists of fetching the operands, performing the operation, and storing the result. You are correct that the ^= operators must be performed in the order C,B,A, due to the associativity rule, but the operands may be fetched in any order. Consider code generated for a "load-store" architecture (one that only accesses memory via loads & stores, and performs operations on registers); the code sequences below are all valid: load r0, x load r0, x load r1, y load r1, y xor r0, r0, r1 load r2, x store r0, x load r3, y load r1, y xor r2, r2, r3 xor r1, r1, r0 xor r1, r1, r2 store r1, y xor r0, r0, r1 load r0, x store r2, x xor r0, r0, r1 store r1, y store r0, x store r0, x this results in this results in x' = y x' = x^y y' = x y' = x^y -- Tim Olson Advanced Micro Devices (tim@amd.com)