Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!iuvax!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!m.cs.uiuc.edu!kenny
From: kenny@m.cs.uiuc.edu
Newsgroups: comp.lang.c
Subject: Re: Obfuscated SWAP: not portable!
Message-ID: <4700044@m.cs.uiuc.edu>
Date: 11 Sep 89 16:17:00 GMT
References: <149@cpsolv.UUCP>
Lines: 50
Nf-ID: #R:cpsolv.UUCP:149:m.cs.uiuc.edu:4700044:000:2142
Nf-From: m.cs.uiuc.edu!kenny    Sep 11 11:17:00 1989


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.bitnet