Wed, 21 Oct 1992 21:43:58 GMT

Related articles |
---|

Strength reduction of constant multipliers cliffc@cs.rice.edu (1992-10-13) |

multiplication by constant - quick comparison of algorithms wu@sequent.com (Youfeng Wu) (1992-10-21) |

Re: multiplication by constant - quick comparison of algorithms preston@helena.cs.rice.edu (1992-10-21) |

Re: multiplication by constant - quick comparison of algorithms bgb@iexist.att.com (1992-10-25) |

Re: multiplication by constant - quick comparison of algorithms chased@rbbb.Eng.Sun.COM (1992-10-27) |

Re: multiplication by constant - quick comparison of algorithms joe@babel.ho.att.com (1992-10-28) |

Newsgroups: | comp.compilers |

From: | preston@helena.cs.rice.edu (Preston Briggs) |

Organization: | Rice University, Houston |

Date: | Wed, 21 Oct 1992 21:43:58 GMT |

References: | 92-10-057 92-10-079 |

Keywords: | arithmetic, optimize |

Youfeng Wu <wu@sequent.com> writes:

*>By allowing the following LEA instructions:*

*>*

*> LEA( b, i, s ) = b + i << s, where s = 1, 2, or 3*

*>*

*>I have an algorithm that achieves:*

*>*

*>#insts 53670*

*>#insts/*

Well, obviously we can improve the ratio by allowing more powerful

instructions! For example, simply allowing s to equal 1, 2, 3, or 4 will

shorten some sequences. Arbitrary shifts and 3-operand add instructions

would shorten other sequences.

It would probably be more interesting to determine what constant integer

multiplies actually occur and make sure those are handled well. For

example, even the simplest techniques handle *4 and *8 (arising commonly

when accessing arrays of single and double-precision floats) perfectly.

The explicit case of the LEA mentioned above has been explored at

Hewlett-Packard (I gave the reference a while ago). They describe a

rule-based approach that finds optimal sequences quickly for all numbers

less than 10,000 (with 12 exceptions, handled in a little table). Note

that it's much easier to explore the exponential search space in this case

since the shifts are limited to 1, 2, or 3. Of course, I'd still do such

exploring offline!

I've done a little exponential searching (overnight) for optimal sequences

of adds, subtracts, and arbitrary left shifts. For the integers between 1

and 1000, Bernstein's algorithm requires a total of 5512 cycles whereas

the optimal sequences require only 5039.

Preston Briggs

--

Return to the
comp.compilers page.

Search the
comp.compilers archives again.