This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Improved re-association of signed arithmetic (was: Inefficient end-of-loop value computation)
On Tue, May 22, 2012 at 1:58 PM, Ulrich Weigand <uweigand@de.ibm.com> wrote:
> Richard Guenther wrote:
>> On Fri, May 18, 2012 at 10:27 PM, Ulrich Weigand <uweigand@de.ibm.com> wrote:
>> > The following patch rewrites associate_plusminus to remove all the
>> > explicitly coded special cases, and instead performs a scan of the
>> > plus/minus tree similar to what is done in tree-ssa-reassoc (and also
>> > in simplify-rtx for that matter). ?If this results in an expression
>> > tree that collapses to just a single operand, or just a single newly
>> > introduced operation, and -in the latter case- one of the two rules
>> > above ensure the new operation is safe, the transformation is performed.
>> >
>> > This still passes all reassoc tests, and in fact allows to remove XFAILs
>> > from two of them. ?It also catches the end-of-loop value computation case.
>> >
>> > Tested on i386-linux with no regressions.
>> >
>> > OK for mainline?
>>
>> The point of the special-cases in forwprop was to make them fast to
>> detect - forwprop should be a pattern-matching thing, much like
>> combine on RTL.
>
> Well, the problem is that you can really make the decision whether or not
> reassociation is allowed after you've seen the whole plus-minus tree.
>
> For example, it is valid to transform "(a + (b + c)) - c" into "a + b" --
> but the only potential "intermediate" transform, "a + (b + c)" into
> "(a + b) + c", is of course not valid in general. ?It only becomes valid
> due to the outer context "... - c" in which it is executed ...
>
>> So, instead of changing forwprop this way can you adjust tree-ssa-reassoc.c
>> to (again) associate !TYPE_OVERFLOW_WRAPS operations but make
>> sure we throw away results that would possibly introduce undefined overflow
>> for !TYPE_OVERFLOW_WRAPS types? ?There is a reassoc pass after
>> loop optimizations, so that should fix it as well, no?
>
> I had thought of that as well. ?But it is not quite that simple -- the
> problem is that tree-ssa-reassoc.c as part of its core algorithm reassociates
> expressions all the time while even still building up the tree, see e.g.
> linearize_expr or break_up_subtract. ?Those steps may all be invalid in
> general, but we only know whether that is true at the very end, once we've
> built up the full tree -- but at that point it is already too late.
Hmm, really? I had not realized it does something it cannot undo later ...
but well ISTR patches floating around for re-organizing how we do
the break_up_subtract / negate stuff. Micha?
> I guess it might be possible to re-work tree-ssa-reassoc to *first* build
> up the tree without changing any statements, then make the decision whether
> we can re-associate, and only then actually perform modifications. ?I'll
> have to think about that a bit more.
Yes, I think that's what we want.
> If we manage to do that, would you then suggest we should remove the
> associate_plusminus phase in tree-ssa-forwprop.c again?
Not sure about removing it - simplifying the simple cases early enough
might be useful. But yes, I installed them all to avoid regressing too much
as I "fixed" reassoc not to associate expressions with undefined overflow.
Richard.
> Bye,
> Ulrich
>
> --
> ?Dr. Ulrich Weigand
> ?GNU Toolchain for Linux on System z and Cell BE
> ?Ulrich.Weigand@de.ibm.com
>