Re: Multiplication by a constant - how?

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

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