Re: Strength reduction of constant multipliers

Interestingly enough, Dr. Dobbs Journal gave a nice example program for
doing strength reduction of constant multipliers.


Also, I have implemented that in the SAS/C Mainframe compiler, versions
5.00 and greater. My own testing indicated that for a simple algorithm,
sequences up to about 9/10 shift/add, shift/sub instructions beat a
multiply instruction hands down. Actually, I could reasonably claim that
the sequence could be as long as 14 instructions, but we settled on 9,
because of possible timing problems in the test. It's difficult to get
reliable numbers under MVS, and the timings can be vastly different for
the different IBM/370 implementations.


An interesting twist to the problem is that for the IBM/370, two adds are
faster than faster than a shift by 4. Making the problem of optimal
sequences even more difficult.


My goal, however, was not to provide optimal sequences, just something
better than a multiply instruction. The approach is to run a star chain
analysis, determining the length of the would-be sequence. If it is
greater than some threshold; (the aforementioned '9') use a multiply,
otherwise you've found something better.


        - Dave Rivers -
        (sastdr@unx.sas.com)
--

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