16 Nov 1997 22:48:48 -0500

Related articles |
---|

[4 earlier articles] |

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: | preston@tera.tera.com (Preston Briggs) |

Newsgroups: | comp.compilers |

Date: | 16 Nov 1997 22:48:48 -0500 |

Organization: | Compilers Central |

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

Keywords: | optimize, practice |

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

Remember that there are more than 32K "numbers". Lots of compilers

are targeting 32 and 64 bit machines and, if the compiler writers

aren't careful (i.e., if they don't review the literature), they can

make a mistake and chew up lots of compile time.

*>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*

Better use a hash table -- don't want to keep complete records for all

the 64-bit integers.

*>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*

The usual approach (read the literature!) is to have a general

heuristic augmented by an exception table that handles cases where the

heuristic falls down. So the first thing to do is check the exception

table. If the answer is there, great. Otherwise, use the heuristic.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.