This is the mail archive of the
mailing list for the GCC project.
Re: Bad choices by expand_mult_highpart
- From: Roger Sayle <roger at eyesopen dot com>
- To: Ulrich Weigand <weigand at i1 dot informatik dot uni-erlangen dot de>
- Cc: Richard Sandiford <rsandifo at redhat dot com>, <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 23 Mar 2004 14:47:14 -0700 (MST)
- Subject: Re: Bad choices by expand_mult_highpart
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.