Re: [PATCH] Improved re-association of signed arithmetic (was: Inefficient end-of-loop value computation)

[Richard Guenther <richard dot guenther at gmail dot com>]

On Tue, May 22, 2012 at 2:04 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> 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.

Btw, reassoc (and your patch?) would have the issue that for
a + (b + c) - a it would yield b + c as result which is not an atom
(but still ok, since it is a pre-existing value that is computed in the IL
already).  The simple forwprop matching catches this as it doesn't
even look into the (b + c) expression but just sees a temporary as
atom here.

Richard.