|strength reduction of constant multiplication ? email@example.com (Youfeng Wu) (1992-10-08)|
|Re: strength reduction of constant multiplication ? firstname.lastname@example.org (1992-10-09)|
|Re: strength reduction of constant multiplication ? email@example.com (1992-10-12)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Fri, 9 Oct 1992 03:10:09 GMT|
Youfeng Wu <email@example.com> writes:
>[discussion of converting integer multiply by constant into simpler
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",
journal="Software -- Practice and Experience",
A second reference describes a similar approach used by HP
Integer Multiplication and Division on the HP Precision
Magenheimer, Peters, Pettis, and Zuras
Proceedings of ASPLOS II
The mathematically inclined will resort to Knuth, Volume 2.
Return to the
Search the comp.compilers archives again.