Re: Bad choices by expand_mult_highpart

[Roger Sayle <roger at eyesopen dot com>]

On Tue, 23 Mar 2004, Ulrich Weigand wrote:
> Isn't this really a well-known problem ("addition chains") where
> optimal algorithms have been found?  Look e.g. at how powi is handled
> in builtins.c.

synth_mult and friends are actually even harder/more complex than
regular addition chains, as GCC for example, considers calculating x*7
as (x*8)-x, i.e. it considers subtractions as well as additions/shifts.

Of course, powi could potentially calculate pow(x,7) as pow(x,8)/x,
but even with just shifts/squares and additions/multiplications the
optimal "addition chain" problem is NP.  GCC's synth_mult heuristics,
however, do a remarkably impressive job.  Torbjorn's algorithm effectively
dynamically constructs powi's addition-chain table on-the-fly using
the target's rtx_costs.


>> So, patch withdrawn.  I'll try to stop wasting everyone's time
>> and embarrassing myself further. ;(

Personally, I'm delighted that someone takes the time to look into
this stuff every few years or so.  To paraphrase Richard Sandiford's
earlier e-mail "changes were unintentional" but "saves 14 instructions
on x/-7 on mips64"!  If only I were so lucky, to dramatically improve
things by accident.

Roger
--