|[11 earlier articles]|
|Re: programmer optimizations? email@example.com (David Toland) (1995-01-11)|
|Re: programmer optimizations? firstname.lastname@example.org (1995-01-23)|
|Re: programmer optimizations? email@example.com (1995-01-27)|
|Re: programmer optimizations? firstname.lastname@example.org (1995-01-31)|
|Re: programmer optimizations? c1veeru@WATSON.IBM.COM (Virendra K. Mehta) (1995-02-02)|
|Re: programmer optimizations? email@example.com (1995-02-01)|
|Re: programmer optimizations? firstname.lastname@example.org (1995-02-01)|
|Re: programmer optimizations? email@example.com (1995-02-02)|
|Re: programmer optimizations? firstname.lastname@example.org (Ronald F. Guilmette) (1995-02-04)|
|From:||email@example.com (Bill Leonard)|
|Organization:||Harris Computer Systems, Ft. Lauderdale FL|
|Date:||Wed, 1 Feb 1995 20:33:37 GMT|
firstname.lastname@example.org (Christopher Glaeser) writes:
> > > replacing (n / 4)
> > > by (n >> 2)
> > Unfortunately it seems you cannot always trust the compiler writers
> > to do the right thing here.
> We have evaluated approximately twenty compilers on a variety of
> architectures using Nullstone, an automated compiler performance analysis
> tool, and have made similar observations. Replacing power of 2 multiply,
> divide, and mod with shift or shift/add/sub sequences can improve
> performance on many machines, and is a relatively easy optimization,
Don't know that I would agree about the "relatively easy" part. Shifting
is not semantically equivalent to multiply/divide for signed integers, so
there are some gyrations one must go through to implement multiply/divide
of signed integers using shift.
Also, there is the issue of overflow detection. Some implementations want
to provide reporting of integer overflow, but many machines do not have a
shift instruction that would detect overflow whereas the multiply
> Observed optimization *defects* include the following:
> 1. Some compilers optimize power of 2 multiply, but not divide and/or mod.
Is this for signed, unsigned, or both? I'm not surprised that they would
avoid it for signed integers.
> 2. Some compilers optimize unsigned integer power of 2, but not signed
Again, not surprising.
> 4. Some compilers optimize positive powers of 2 (e.g. 2,4,8), but not
> negative powers of 2 (e.g. -2,-4,-8).
Well, if the multiply only takes 3 cycles, say, and shift and negation each
take one cycle, such an optimization would only save 1 cycle but cost you
an extra instruction fetch. It's debatable in this case whether the
optimization would be worth it. (Of course, if the multiply takes many
more cycles, the compiler is just missing an opportunity.)
> 6. Some compilers generate incorrect code for signed int power of 2
Probably because the compiler writer didn't realize that shift and divide
are not semantically equivalent. :-)
Having said that, I would easily believe there are many compilers out there
that miss some glaring opportunities for optimization. I just wanted to
point out that some opportunities that appear obvious at first turn out
later to not be as good as you first think. A *good* compiler writer will
religiously observe the following 3 rules when contemplating an
1. The optimization must preserve the semantics of the program.
2. The optimization must have a positive effect on performance for at
least the majority of cases. Preferably it will not have a negative
effect on any programs, but at the very least the negative impact
should be minimal or very seldom encountered.
3. Opportunities for the optimization must be common enough to make the
compiler work worthwhile.
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Return to the
Search the comp.compilers archives again.