Re: strength reduction of constant multiplication ?

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

Return to the comp.compilers page.
Search the comp.compilers archives again.