# strength reduction of constant multiplication ?

## Youfeng Wu <wu@sequent.com>Thu, 8 Oct 1992 22:20:58 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: Youfeng Wu Organization: Compilers Central Date: Thu, 8 Oct 1992 22:20:58 GMT Keywords: arithmetic, theory, question, comment

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

Post a followup to this message