revamping synth_mult()

[Richard Guenther]

On 7/19/06, sbalfour@cisco.com <sbalfour@cisco.com> wrote:
> Folks,
>
> I'm currently looking at substantively revamping synth_mult(), the gcc
> routine for reducing multiplicative constants to shift/add/sub sequences.
>
> My perception here, from experimentation, is that synth_mult() is:
>
> 1. slow (deeply recursive)
> 2. bag of tricks including factoring (factoring is hard)
> 3. result is merely fair to mediocre
>
> Others may think differently.
>
> I also am able to determine from experimentation, that a "pretty good"
> result is readily achievable with linear effort, and furthermore, that a
> "near optimal" or "optimal" result is often only one shift/add pair less
> than the "pretty good" result, but obtaining that near optimal result is
> non-linear in computational complexity.  Maybe it isn't worth it.  Maybe
> we enumerate the oddball cases that fall out (i.e. the ones that are notably
> poorly coded after application of a systematic algorithm).
>
> A search of the literature indicates a small set of such systematic
> algorithms of which factoring is one have been applied to the problem. I
> think my objective here is to do in a systemmatic way, at least as well in
> the average case, and better in the worst case, as the existing algorithm,
> and to do it much faster.  The code improvement probably won't make a
> measurable difference on standard benchmarks.
>
> If anyone has work-inprogress in this area, or a bug/tweak/suggestion,
> I'd be happy to hear about it.  I'm not subscribed yet to the gcc@gcc.gnu.org
> mailing list, so copy me on any direct reply.

There is the pending

http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00313.html

which improves multiplication sequences.

Richard.