pardo@june.cs.washington.edu (David Keppel) (02/16/88)
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") Pardochris@trantor.umd.edu (Chris Torek) (02/16/88)
Without further supporting evidence, I will claim that any optimiser
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: chris@mimsy.umd.edu Path: not easily reachablejfh@killer.UUCP (The Beach Bum) (02/18/88)
In article <2303@umd5.umd.edu> chris@trantor.umd.edu (Chris Torek) writes: >Without further supporting evidence, I will claim that any optimiser >could convert > > a = 0 & f(); > >into > > (void) f(), a = 0 > >and [ more examples deleted for brievity ] >-- >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@ism780c.UUCP (News system) (02/20/88)
Chris Torek writing about optimizing expressions like:
a = 0 & f();
(void) f(), a = 0
if (1 | g()) s1; else s2;
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 Systemshenry@utzoo.uucp (Henry Spencer) (02/22/88)
I talked to Dennis some years ago about a related issue: should it be
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!henryado@elsie.UUCP (Arthur David Olson) (02/23/88)
We let lint worry about such stuff here at elsie:
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
...
--
ado@vax2.nlm.nih.gov ADO, VAX, and NIH are Ampex and DEC trademarkshenry@utzoo.uucp (Henry Spencer) (02/26/88)
> 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. 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. -- Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henry
mouse@mcgill-vision.UUCP (der Mouse) (03/10/88)
In article <9130@ism780c.UUCP>, news@ism780c.UUCP (News system) writes:
< Chris Torek writing about optimizing expressions like:
< a = 0 & f(); (void) f(), a = 0 if (1 | g()) s1; else s2;
< [says that f() and g() can't be eliminated unless the compiler can
< 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: mouse@mcgill-vision.uucp
arpa: mouse@larry.mcrcim.mcgill.edu