Re: Multiply by a constant --> shift-and-adds algorithm?

Sergey Solyanik wrote:


> Christopher Glaeser wrote:
> > When testing various
> > compilers with different repeating bit patterns, I have measured compile
> > times of several minutes per constant, and on rare occasion, have
> > measured compile times as high as one hour per constant.
>
> Do you have examples? My version (and it is optimal) runs in
> couple of seconds for _ALL_ 32K numbers (executed in a loop from
> 1 to 32000, total time). One hour per constant seems uncomprehensible...


Exactly.


And even if it *did* take a bit of time, you'd only do this once: you
can then set up a static lookup table for each constant, and the
optimizer can do a simple lookup to issue a series of shifts and adds
instead of a multiply.


For instance, as far back as 1985, HP's optimizer (and assembler, for
that matter) used to have a lookup table for all constants upto 1037
(I believe), which was the highest number you could multiply with
using not more than 5 shift-add instructions (== 5 cycles - HP-PA has
SH1ADD, SH2ADD and SH3ADD instructions). Naturally, there are other
heuristics as well, like multiplying by constants equal to or near
powers of 2 (which can be done with a shift followed by a series of
shift-adds).
--
Shankar Unni Powertel Global, Inc.
(650) 259-1700 shankar@powertelglobal.com
(650) 259-1702 (fax) shankar@webnexus.com
--

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