Path: utzoo!mnetor!uunet!husc6!mit-eddie!ll-xn!ames!elroy!mahendo!jplgodo!wlbr!voder!tolerant!vsi1!steve
From: steve@vsi1.UUCP (Steve Maurer)
Newsgroups: comp.lang.c
Subject: Bad optimizations (was Re: comma operator)
Message-ID: <269@vsi1.UUCP>
Date: 20 Jan 88 22:19:42 GMT
References: <3819@sigi.Colorado.EDU> <5080013@hpfcdc.HP.COM> <7120@brl-smoke.ARPA> <3887@sigi.Colorado.EDU>
Reply-To: steve@vsi1.UUCP (Steve Maurer)
Organization: Vicom Systems Inc. San Jose, Cal.
Lines: 72
Keywords: optimization swap assembly C sun compiler
Summary: Optimization isn't really optimization in a HLL

[lineater]
SWARBRICK FRANCIS JOHN writes:
>
> #define swap(a,b) ((a) = ((b) = ((a) = (a) ^ (b)) ^ (b)) ^ (a))
>
> Try that, and tell me what you think.  A super-genius friend of mine figured
> it out.  He says it will work for anything (int, char *, etc.).  But it
> sure boggles my mind...
>
    It boggles mine as well.    Just from looking at it, it looks like
the resulting Assembly would be a mess, even in the simplistic case of
integers.    However, just to try this out, I decided to compile the
following section of code on our Sun3 (without optimization).

    #define swap(a,b) ((a) = ((b) = ((a) = (a) ^ (b)) ^ (b)) ^ (a))
    #define swap2(A, B, TYPE)  { TYPE temp; temp = A; A = B; B = temp; }

    main()
    {
    int a = 3, b = 5;

    swap(a, b);
    foo_marker();	/* marker to deleniate code sections */
    swap2(a, b, int);
    }

The resulting code (without headers or trailers) was as follows:

    movl	a6@(-0x4),d0		<-- xor method
    movl	a6@(-0x8),d1
    eorl	d1,d0
    movl	d0,a6@(-0x4)
    movl	a6@(-0x8),d1
    eorl	d1,d0
    movl	d0,a6@(-0x8)
    movl	a6@(-0x4),d1
    eorl	d1,d0
    movl	d0,a6@(-0x4)

    jbsr	_foo_marker

    movl	a6@(-0x4),a6@(-0xc)	<-- move method
    movl	a6@(-0x8),a6@(-0x4)
    movl	a6@(-0xc),a6@(-0x8)

The resulting code is approximately 3 times longer!   This is
partly due to the superflous storing of intermediate results that
the compiler makes, because it isn't sure in that portion of the
parse tree whether the new result is going to be used.

    In other words, "optimal moves" don't necessarily work in HLL's.


Here is the same exclusive or swap() macro, under Sun's optimizer:

    eorl	d1,d0
    movl	d0,a6@(-4)
    eorl	d1,d0
    movl	d0,a6@(-8)
    movl	a6@(-4),d1
    eorl	d1,d0
    movl	d0,a6@(-4)

As you can see, some, but not all that much better.

This isn't really Sun's fault, I might add.   Most compilers would do
just about the same, or perhaps worse.  Of course, an extrodinarily
optimized compiler (one in which i = 5; i = 6; would delete the i = 5;
statement altogether), might approximate the original intent of the
code, but I doubt it.

					Steve Maurer