bitwise short-circuiting
David Keppel
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
Chris Torek
could convert
a = 0 & f();
into
(void) f(), a = 0
and
if (1 | g()) s1; else s2;
into
(void) g(); s1;
(s2 may be deleted entirely iff it is not reachable via labels),
and that unless the compiler can determine that f() and g() have
no side effects, any further optimisation is simply wrong. If
the compiler knows that f() is a pure function, e.g.,
static int f() { return 0; }
... a = 0 & f();
it could then delete the call.
--
In-Real-Life: Chris Torek, Univ of MD Computer Science, +1 301 454 7163
(hiding out on trantor.umd.edu until mimsy is reassembled in its new home)
Domain: ch...@mimsy.umd.edu Path: not easily reachable
Robert Firth
>Without further supporting evidence, I will claim that any optimiser
>could convert
>
> a = 0 & f();
>
>into
>
> (void) f(), a = 0
You now have supporting evidence. I just compiled
a := 0 & f()
on my old familiar BCPL/Vax compiler, and got out
BSBW F
CLRL A
Done by a fairly trivial peephole optimiser, in two steps:
(a) if the operation is commutative, put any constant operand on the right
(b) if the operation is logical-and, and the right operand is zero, the
result is zero so flush the left operand (naturally that is only one
of several possible patterns this step will look for)
Your second example needed to be changed, but
a := f() | <all-ones>
indeed reduces to
BSBW F
MCOML #0, A
Hope this helps
----
PS: the stupid program at my site for some reason won't let me post
followups. They get bounced back with mailer messages that are (to
me) incomprehensible. Is anyone able to offer advice? It all worked
in 1987.
The Beach Bum
>could convert
>
> a = 0 & f();
>
>into
>
> (void) f(), a = 0
>
>and
>--
>In-Real-Life: Chris Torek, Univ of MD Computer Science, +1 301 454 7163
>(hiding out on trantor.umd.edu until mimsy is reassembled in its new home)
These are extensions to the common (e) + 0, (e) * 1, etc. optimizations that
many compilers already implement. Replacing '+' with '|' and '*' with
'&' gives the same results, excect all bits must be considered when
performing the optimization, thus:
if (0100 | f())
s2;
can be optimized to
(void) f();
s2;
(Well, really similiar only different since if (0100 + f()) can't be
optimized, BUT, if (0 * f()) and if (0 & f()) both can)
A suggested method to handle this would be to rewrite the tree to
become 'if (f(), 0)' when handed 'if (0 & f())' as input, then let
some other part of the optimizer handle removing the 'then' part of
the statement.
[ This belongs in comp.compilers, but that is a moderated newsgroup
and I'm not in a mood to cross-post over there. ]
- John.
--
John F. Haugh II SNAIL: HECI Exploration Co. Inc.
UUCP: ...!ihnp4!killer!jfh 11910 Greenville Ave, Suite 600
"You can't threaten us, we're Dallas, TX. 75243
the Oil Company!" (214) 231-0993 Ext 260
News system
a = 0 & f();
says:
>(s2 may be deleted entirely iff it is not reachable via labels),
>and that unless the compiler can determine that f() and g() have
>no side effects, any further optimisation is simply wrong.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>In-Real-Life: Chris Torek, Univ of MD Computer Science, +1 301 454 7163
Chris, how do you justify the above assertion? I just got my copy of the
the proposed standard (11 Jan 88 version). On page 51 the semantics of the
bitwise & operator is defined. I quote:
"The usual arithmetic conversions are performed on the operands."
"The result of the binary & operator is the bitwise AND of the
operands (that is, each bit in the result is set if and only if
each of the corresponding bits in the converted operands is set)."
I could not find any thing in the standard that requires evaluation of
side effects of the operands if the result can be determined without
evaluating the operands.
Marv Rubinstein -- Interactive Systems
Henry Spencer
permissible to optimize "0 * a()" to "0"? The V7 compiler did this,
although the C Reference Manual seemed to imply that it shouldn't. As
I recall (it's been a while...), Dennis replied roughly "the optimization
seemed reasonable to me, but I got so much flak about it that I finally
took it out". The current X3J11 draft says likewise: the side effects
must happen, even if the compiler doesn't use the value of the function.
In practice, there are so many sleazy programmers out there that the only
way you can get away with short-circuiting something like this is if the
language spec explicitly permits it from the beginning. Bliss did that.
--
Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology
condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henry
Arthur David Olson
Script started on Mon Feb 22 13:57:52 1988
$ cat try.c
main() { return 0 & func(); }
func() { return 1; }
$ lint -h try.c
try.c:
try.c(1): warning: superfluous operation on zero
...
--
a...@vax2.nlm.nih.gov ADO, VAX, and NIH are Ampex and DEC trademarks
Henry Spencer
> side effects of the operands if the result can be determined without
> evaluating the operands.
However, what you also didn't find was anything permitting incomplete
evaluation of operands. If you read the material on expressions carefully,
you will find it says that the operands get evaluated. Not that they get
evaluated only if necessary. (Except in some special cases like &&.) That
means their side effects must happen, at some point. Optimizers are not
free to change that.
der Mouse
< Chris Torek writing about optimizing expressions like:
< a = 0 & f(); (void) f(), a = 0 if (1 | g()) s1; else s2;
< determine they are side-effect-free]
< Chris, how do you justify the above assertion? I just got my copy of
< the the proposed standard (11 Jan 88 version). On page 51 the
< semantics of the bitwise & operator is defined. I quote:
< [Usual arithmetic conversions happen]
< [Result is bitwise AND of operands]
< I could not find any thing in the standard that requires evaluation
< of side effects of the operands if the result can be determined
< without evaluating the operands.
Oh no. Someone tell us this isn't really so....please....? This would
definitely violate the Principle of Least Surprise, particularly when
there's a constant operand that's a configuration macro or something of
that sort.... Take this to the extreme and you can throw away all
function calls whose results aren't used (and which take no pointer
arguments)!
der Mouse
uucp: mo...@mcgill-vision.uucp
arpa: mo...@larry.mcrcim.mcgill.edu