Path: utzoo!mnetor!uunet!husc6!mit-eddie!uw-beaver!uw-june!pardo
From: pardo@june.cs.washington.edu (David Keppel)
Newsgroups: comp.lang.c
Subject: bitwise short-circuiting
Message-ID: <4224@june.cs.washington.edu>
Date: 15 Feb 88 18:19:37 GMT
Reply-To: pardo@uw-june.UUCP (David Keppel)
Organization: U of Washington, Computer Science, Seattle
Lines: 59
Keywords: bitwise optimize open-eyes
Summary: Long.  (is this a new topic?)
Distribution:


I've been having a discussion with a friend of mine about evaluation
of the operands in a bitwise operators.  It is (was?) my assumption from
looking at K&R that the compiler could short-circuit special cases if it
wanted to, reorder at will, etc., on things like:

	x = 0 & a;		/* 0 & anything => 0 */
	x = 0 & f();		/* ditto, but what about side effects? */
	x = f() & 0;		/* ditto, but what about side effects? */
	if (1 | a) { ... }	/* bitwise, but always has >= 1 bit set */

Where the compiler knows, at compile-time, exactly what the result value
must be.  The relevant section of K&R seem to be A:7.8 and A:7.9 (page
190) which don't say anything about what the compiler can/can't do.
(Therefore it can do anything it wants to ?-)  I'd like to hear from
people what current compilers can/can't do and what (if anything) ANSI
has to say that is different.  Specifically, I'd like to know about:

(a) order of evaluation
(b) side effects
(c) short circuiting
(d) boolean effect

In general I would expect the compiler to rearrange the expressions for
the greatest efficiency, ignore possible side-effects, not provide short-
circuiting unless it can be determined at compile-time, and be more generous
in the calculation of "short circuit" when the expression is used in a
strictly boolean context (in an "if" with no embedded assignment, say).

Also, (if it is still relevant after answering the above) we've tried the
following on pcc (Ultrix) and Green Hills 32K.  If you have another compiler
you think would produce much better code, I'd like to see it.

    int
dmi( a, b )
    register int	a, b;
{
    int		fa(), fb();
    register int	d = 0;

    if( 0 & a ){d=1;};		/* never need to look at a */
    if( 0 | a ){d=1;};		/* always need to look at a */
    if( 1 | a ){d=2;};		/* never need to look at a */
    if( ~0 | a ){d=3;};		/* never need to look at a */
    if( a | b ){d=4;};		/* could rearrange */
    if( fa() & fb() ){d=5;};	/* need to look at fa() and fb() */
    if( fa() | fb() ){d=6;};	/* sometimes only need to look at one */
    if( 0 & fa() ){d=7;};	/* never need to look at fa() */
    if( 1 | fa() ){d=8;};	/* never need to look at fa() */
    if( ~0 | fa() ){d=9;};	/* never need to look at fa() */
    return( d );
}

BTW: Green Hills does some optimization (not much) and leaves useless code,
such as "compare 0 to 0 and branch if equal, else d = 1", where the
compiler ought to know that the branch will always be taken.  Ultrix pcc
(compiling -O) does no optimization and does change the order of operand
evaluation.

	;-D on  (Now if I could just write "-O")  Pardo