21 Mar 1997 10:13:40 -0500

Related articles |
---|

Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-14) |

Re: Multiplication by a constant - how? rweaver@ix.netcom.com (1997-03-16) |

Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16) |

Re: Multiplication by a constant - how? d.sand@ix.netcom.com (Duane Sand) (1997-03-16) |

Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16) |

Re: Multiplication by a constant - how? dlmoore@ix.netcom.com (David L Moore) (1997-03-16) |

Re: Multiplication by a constant - how? preston@tera.com (1997-03-21) |

Re: Multiplication by a constant - how? torbenm@diku.dk (1997-03-21) |

Re: Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-27) |

Re: Multiplication by a constant - how? cdg@nullstone.com (Christopher Glaeser) (1997-03-31) |

Re: Multiplication by a constant - how? preston@cs.rice.edu (1997-04-02) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 21 Mar 1997 10:13:40 -0500 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 97-03-062 97-03-092 |

Keywords: | arithmetic, optimize |

David L Moore <dlmoore@ix.netcom.com> writes:

*>So, to find an optimal sequence you have to look for repeated*

*>bit-patterns that can be extracted and handled all at once. I have*

*>never seen an optimal scheme for this either (obviously, you can try*

*>exhaustive enumeration).*

I believe it has been proven that a related problem is NP-hard. This

problem is: given that you start with the constants 0 and 1, what is

the smallest number of additions and subtractions required to obtain a

specific constant. The reason this is similar is that if (if you

impose a few additional constraints) you start with a value x instead

of the constant 1, you multiply x by that constant instead of just

building the constant. Not that adding a number to itself is a left

shift by one bit. This problem does not take multi-bit shifts or

bitwise logical operations into account, but I can't believe these

makes the problem any simpler.

Has anyone tried using LZ compression techniques to find the common

subsequences? Or is this uninteresting because the number of bits is

small?

*>These days the question is rather moot since most hardware can do a*

*>general integer multiply in a few cycles.*

However, you still need time to build the constant you want to

multiply by. You can load this constant from a constant pool, but that

takes time. It may well be that the total cost of building/loading a

constant and then using a multiply instruction is costlier than using

a shift/add method of multiplication in more cases than you would

expect just by looking at the multiply speed.

*> Notice that the code the Microsoft compiler is generating cannot be*

*> multi-way issued, which is likely to be bad on many current chips.*

It would be interesting to generate sequences that might not be

minimal length, but minimal critical path, as these would schedule

better.

Torben Mogensen (torbenm@diku.dk)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.