15 Nov 1997 15:20:20 -0500

Related articles |
---|

[3 earlier articles] |

Re: Multiply by a constant --> shift-and-adds algorithm? ssolyanik@icdc.com (Sergey Solyanik) (1997-11-09) |

Multiply by a constant --> shift-and-adds algorithm? txr@alumni.caltech.edu (Tim Rentsch) (1997-11-09) |

Re: Multiply by a constant --> shift-and-adds algorithm? n8tm@aol.com (1997-11-11) |

Re: Multiply by a constant --> shift-and-adds algorithm? dube@brachio.IRO.UMontreal.CA (Danny Dube) (1997-11-11) |

Re: Multiply by a constant --> shift-and-adds algorithm? cdg@nullstone.com (Christopher Glaeser) (1997-11-13) |

Re: Multiply by a constant --> shift-and-adds algorithm? ssolyanik@icdc.com (Sergey Solyanik) (1997-11-14) |

Re: Multiply by a constant --> shift-and-adds algorithm? shankar@powertelglobal.com (Shankar Unni) (1997-11-15) |

Multiply by a constant --> shift-and-adds algorithm? preston@tera.tera.com (1997-11-16) |

Re: Multiply by a constant --> shift-and-adds algorithm? cdg@nullstone.com (Christopher Glaeser) (1997-11-18) |

From: | Shankar Unni <shankar@powertelglobal.com> |

Newsgroups: | comp.compilers |

Date: | 15 Nov 1997 15:20:20 -0500 |

Organization: | Powertel Global, Inc. |

References: | 97-11-038 97-11-078 97-11-086 |

Keywords: | arithmetic, optimize, practice |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.