Re: [patch] Fold x + x to x * 2

[Roger Sayle <roger at eyesopen dot com>]

On Sat, 6 Nov 2004, Zdenek Dvorak wrote:
> 	* fold-const.c (fold_mult_into, fold_sum_of_mult): New functions.
> 	(fold): Use them.

Hi Zdenek,

I don't think this patch (even with minor corrections) is suitable for
stage3.  In addition to the trapping math issues mentioned previously,
I'm concerned that you're efforts to partially implement full arithmetic
reassociation in "fold" could potentially have disasterous compile-time
and memory usage overheads.

Consider the effectos of your unbounded O(n^2) recursion on

int foo()
{
  return a + b + c + d + e + f + g + h + i + j + k + l + m + n + ...;
}

There was a concern about performance issues attempting reassociation
on RTL expressions, which are bounded to be at most three or four
additions, but fold is called on unbounded trees.  Additionally the
C/C++ parsers do (and should) call fold after parsing "a + b", then
after "a + b + c", then after "a + b + c + d"....

As a simple case study, consider how many instructions your implementation
actually requires to convert "x + x" into "x * 2", as mentioned in the
title.


But I agree that your problem of "x + x + x + x" generated by tree
transformations needs to be fixed.  Its probably not urgent given that
LNO and tree-ssa and much of stage3 never even noticed this.  Let me
see what I can come up with, probably a local solution that addresses
your needs, leaving an implementation of full reassociation, including
negation, subtraction and left shifts to 4.1.  We'll probably even
need several complementary patches should we decide that "x*2" is the
canonical form of "x+1", including a new fast path for synth_mult.


Do you have any timing figures for your patch?

Roger
--