Fri, 9 Oct 1992 03:10:09 GMT

Related articles |
---|

strength reduction of constant multiplication ? wu@sequent.com (Youfeng Wu) (1992-10-08) |

Re: strength reduction of constant multiplication ? preston@dawn.cs.rice.edu (1992-10-09) |

Re: strength reduction of constant multiplication ? macrakis@osf.org (1992-10-12) |

Newsgroups: | comp.compilers |

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

Organization: | Rice University, Houston |

Date: | Fri, 9 Oct 1992 03:10:09 GMT |

References: | 92-10-036 |

Keywords: | arithmetic, theory |

Youfeng Wu <wu@sequent.com> writes:

*>[discussion of converting integer multiply by constant into simpler*

*>instructions] *

I believe the problem of finding the optimal sequence of adds and left

shifts is NP-complete if we attempt to reuse intermediate results. Adding

subtract and right shift doesn't simplify the problem, though it can lead

to shorter solutions.

For example, multiplication by 22 without reusing intermediates seems to

take 5 instructions (of a certain limited form)

x4 = x1 << 2

x5 = x4 + x1

x10 = x5 << 1

x11 = x10 + x1

x22 = x11 << 1

If we allow the reuse of intermediates results (which will cost additional

registers), we can find a shorter solution:

x2 = x1 << 1

x3 = x2 + x1

x24 = x3 << 3

x22 = x24 - x2

I've only shown simple instructions. Naturally, shorter solutions using

special shift and add instructions are possible.

In practice, it probably suffices to use any heuristic approach that works

well for small integers, especially if supplemented by an exception table.

The idea of the exception table is to record (in a hash table, for

instance) the cases for which your heuristic is non-optimal and their

optimal solution (derived once at great expense by the compiler writer

using some sort of branch-and-bound exponential searcher).

The following paper describes the approach used in the PL.8 compiler:

title="Multiplication by Integer Constants",

author="Robert Bernstein",

journal="Software -- Practice and Experience",

volume=16,

number=7,

month=jul,

year=1986,

pages="641--652"

A second reference describes a similar approach used by HP

Integer Multiplication and Division on the HP Precision

Architecture

Magenheimer, Peters, Pettis, and Zuras

Proceedings of ASPLOS II

The mathematically inclined will resort to Knuth, Volume 2.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.