Obfuscated SWAP: not portable!

[Chris Torek]

In article <4700044 at m.cs.uiuc.edu> kenny at 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 at mimsy.umd.edu	Path:	uunet!mimsy!chris