This is the mail archive of the
mailing list for the GCC project.
Re: [patch] Fold x + x to x * 2
- From: Roger Sayle <roger at eyesopen dot com>
- To: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Sun, 7 Nov 2004 14:39:18 -0700 (MST)
- Subject: Re: [patch] Fold x + x to x * 2
On Sat, 6 Nov 2004, Zdenek Dvorak wrote:
> * fold-const.c (fold_mult_into, fold_sum_of_mult): New functions.
> (fold): Use them.
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
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
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?