18 Nov 1997 12:20:09 -0500

Related articles |
---|

[5 earlier articles] |

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

const_int * (int / const_int) by shift adds? cef@geodesic.com (Charles Fiterman) (1997-11-20) |

From: | Christopher Glaeser <cdg@nullstone.com> |

Newsgroups: | comp.compilers |

Date: | 18 Nov 1997 12:20:09 -0500 |

Organization: | Compilers Central |

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

Keywords: | optimize, arithmetic, practice |

Sergey Solyanik wrote:

*> Do you have examples? ...*

*> One hour per constant seems uncomprehensible...*

The constants that caused the excessive compilation times had one or

more repeating patterns. Examples include numbers with a binary

pattern such as 10101 repeated two or three times in a 32-bit integer.

I have isolated compile-time problems due to multiply by a constant in

several production compilers (one, as I mentioned, requiring an hour

per constant). The vendors of these compilers are Nullstone

licensees, and the problems have been corrected in current releases.

Since I didn't have access to the compiler source code, I don't know

if the problems were caused during the shift/add expansion, or during

subsequent phases such as register allocation and instruction

scheduling.

While on the topic of integer multiply optimization, I should mention

two other types of problems that I occasionally isolate in production

compilers. The first is unnecessarily limiting the power-of-two

optimization to a power-of-two subrange, even though larger shift

amounts are available in the ISA. An example would be converting

multiply by 2**1 through 2**8 to a shift, but leaving 2**9 through

2**31 as a slower multiply. The second is optimizing signed integer

multiply, but not unsigned integer multiply, or vice versa.

Best regards,

Christopher Glaeser cdg@nullstone.com

Nullstone Corporation http://www.nullstone.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.