On 7/19/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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.
