Re: programmer optimizations?

cdg@nullstone.com (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
instruction would.


> 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
> integer.


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
> divide.


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
optimization:


      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.


--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.hcsc.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.