Thu, 8 Oct 1992 22:20:58 GMT

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

Newsgroups: | comp.compilers |

From: | Youfeng Wu <wu@sequent.com> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.