>By allowing the following LEA instructions:
>
> LEA( b, i, s ) = b + i << s, where s = 1, 2, or 3
>
>I have an algorithm that achieves:
>
>#insts 53670
>#insts/
>
>The question is how we can push the ratio of #insts/
Well, obviously we can improve the ratio by allowing more powerful
instructions! For example, simply allowing s to equal 1, 2, 3, or 4 will
shorten some sequences. Arbitrary shifts and 3-operand add instructions
would shorten other sequences.
It would probably be more interesting to determine what constant integer
multiplies actually occur and make sure those are handled well. For
example, even the simplest techniques handle *4 and *8 (arising commonly
when accessing arrays of single and double-precision floats) perfectly.
The explicit case of the LEA mentioned above has been explored at
Hewlett-Packard (I gave the reference a while ago). They describe a
rule-based approach that finds optimal sequences quickly for all numbers
less than 10,000 (with 12 exceptions, handled in a little table). Note
that it's much easier to explore the exponential search space in this case
since the shifts are limited to 1, 2, or 3. Of course, I'd still do such
exploring offline!
I've done a little exponential searching (overnight) for optimal sequences
of adds, subtracts, and arbitrary left shifts. For the integers between 1
and 1000, Bernstein's algorithm requires a total of 5512 cycles whereas
the optimal sequences require only 5039.
Preston Briggs
--
Post a followup to this message
Return to the
comp.compilers page.
Search the
comp.compilers archives again.