# Re: strength reduction of constant multiplication ?

## preston@dawn.cs.rice.edu (Preston Briggs)Fri, 9 Oct 1992 03:10:09 GMT

From comp.compilers

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)
| List of all articles for this month |

 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