[PATCH] Optimize x*x*x*x*x*x using 3 multiplications.

[Roger Sayle]

On Thu, 31 Jul 2003, Richard Henderson wrote:
> On Wed, Jul 30, 2003 at 09:53:36PM -0600, Roger Sayle wrote:
> > I'm not sure whether reassociation alone could work out that x^23
> > is better calculated as x^13*x^10 instead of x^22*x.
>
> Yields 7 multiplications via bottom-up reassociation.
> Yields a different set of 7 multiplications via top-down reassociation.
> Your power table yields 6 multiplications total.  Hmm...

You might have guessed 23 wasn't chosen at random.  The minimal addition
chain problem is NP-complete, so a lookup table of optimal results really
helps.  I apologise for loading the dice.



> So while reassociation can produce similar results for some inputs,
> (e.g. the x^6 in the subject line) it can't for all inputs.  I can't
> argue with results like that.

Reassociaton!  I now have a name for my pain.  I've just been reading
up on reassociation-based optimization in compilers and several of GCC's
deficiencies on my wish list turn out to be reassociation related.
For example, how "(x & c1) & c2" isn't reduced in simplify_rtx, or
how the following code:

extern int z1, z2;
void foo(int x, int y, int z)
{
  z1 = (x+y)+z;
  z2 = x+(y+z);
}

gets optimized to z2 = z1 with MSVC but not by GCC.  Or for the current
example, x*y*y*x*x*y which could be simplified via pow(x,3)*pow(y,3) into
pow(x*y,3), and so on, etc...  I now have a new life goal to implement
better reassociation in GCC's constant folding and RTL optimizers.



> > I haven't checked but I'd guess GCC also handles "x+x+x+x+x+x" the same
> > way as my patch, i.e. by representing it internally by a multiplication.
>
> Yes, it should.

Arghh!!  I just tried the experiment:

foo:
        fldl    4(%esp)
        fld     %st(0)
        fadd    %st(1), %st
        fadd    %st(1), %st
        fadd    %st(1), %st
        fadd    %st(1), %st
        faddp   %st, %st(1)
        ret


Even with -ffast-math.  Yet another new entry on my TODO list!



> > It's probably not clear from the immediate context of the patch, but
> > the transformation to convert x*x into pow(x,2) is already nested inside
> > an "if (flag_unsafe_math_optimizations)" condition [fold-const.c:5944].
>
> Ah.
>
> > I could repeat the flag_unsafe_math_optimizations check redundantly
> > if you think that would make things clearer?
>
> No, that's ok.


Can I take that as an approval for the current patch?


Roger
--