strength reduction of constant multiplication ?

For superscalar processors, multiplication usually is more than ten times
slower than the simple instructions like add, sub, shift, or lea (shift by
1, 2, 3 and add) instructions. It is beneficial to replace the
multiplication by a sequence of the simple instructions (to increase speed
and to provide more opportunity for instruction level parallelism).


For each integer constant, it can be represented as a binary sequence


sum ( ai*2**i | i = 0, ..., k ) where ai = either 0 or 1.


I found an algorithm that can replace multiplication by any constant in
the range of [1, 2**32-1] by a sequence of simple instructions with the
average length no longer than


sum ( ai | i = 0, ..., k ) - 1


Examples.


1. X * 136 = X * (2**3 + 2**7)
can be replace by the following two instructions:


reg = X shfit 7 *** X left shift 7 bits
reg = lea ( reg, X, 3) *** reg add ( X left shift 3 bits )


2. X * 1950 = X * (2 + 2**2 + 2**3 + 2**4 + 2**7 + 2**8 + 2**9 + 2**10)
can be replace by the following five instructions:


reg = lea ( X, X, 1 )
reg = reg shift 5
reg = lea ( reg, X, 1 )
reg1 = X shift 11
reg = reg1 sub reg *** reg1 minus reg


But I found out that for certain cases this algorithm is not optimal. Do
anyone know a reference on this subject (with discuss on approachs,
complexity, and/or optimal solution or NP completeness, etc)?


TIA,


Youfeng Wu, Ph.D. 15450 S.W. Koll Parkway
Compilers, D2-745 Beaverton, OR 97006-6063
Sequent Computer Systems Tel: (503) 578-4273
wu@sequent.com Fax: (503) 578-3228
[This can get pretty hairy, particularly if you allow subtraction as well
as addition. I know it's been studied at some length; someone should have
references. -John]
--

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