[PATCH] fwprop: Prevent infinite looping (PR79405)

[Richard Biener]

On Fri, Mar 24, 2017 at 10:39 AM, Segher Boessenkool
<segher@kernel.crashing.org> wrote:
> On Fri, Mar 24, 2017 at 09:13:59AM +0100, Richard Biener wrote:
>> >> https://gcc.gnu.org/ml/gcc-patches/2017-02/msg01485.html
>> >>
>> >> ?
>> >
>> > What about it?  That suggestion would make fwprop do *less* useful work,
>> > while in principle the problem is that it *already* does not enough!
>>
>> Ok, not knowing a lot about fwprop I take your word for it (but GIMPLE level
>> forwprop works that way and certainly you can't substitute a def into a use
>> that is before the def).
>
> When fwprop has done a propagation it makes fresh new uses for all the
> sources of the resulting insn, which it adds at the end of the table.
> It doesn't reuse the original uses.

Yes, that's what I suspected.

>> > If fwprop actually tried all propagations (and never tried substituting
>> > X with X, which it currently does), there would be no problem.
>>
>> To me it looked like fwprop tries to iterate over all propagations but
>> it iterates over a changing data structure which is why it "oscillates".
>> But I didn't actually verify that theory (in fact, I just very much disliked
>> Berns patch give its compile-time cost).
>
> We have, in order, in one bb:
>
>   B = A|Z
>   A = B
>   D = A
>
> where each of those is the only set of its dest.  Now the first thing
> tried is propagating the first into the second.  This fails.  Then,
> Z is found to be zero, so we get
>
>   B = A
>   A = B
>   D = A
>
> If the first was now propagated into the second again, all is fine
> (all three vars are set to A).  But this is not tried again.  The
> second is propagated into the third, giving
>
>   B = A
>   A = B
>   D = B
>
> and then the first is propagated into the third, and we repeat
> forever.
>
>> > This patch is a workaround; it makes no difference on pretty much any
>> > code, except this single testcase (which has undefined behaviour,
>> > uninitialised variables).
>>
>> Yeah, your fix looks similar to the other hack I suggested.
>
> I have implemented the "retry things" as well fwiw, but a) it is too
> big and invasive for stage 4, and b) it kind of sucks, needs more
> work, even more invasive.  The workaround is cheap and solves the
> immediate problem.

Agreed, still iterating over the DF uses in the first place looks like
the bug (given this "all uses" data structure changes during propagation!).

I'd have done

  for (BBs in RPO order)
    for (insn in BB)
repeat:
      for (use in insn)
         if (propagate_into (use))
           goto repeat;

Richard.

>
> Segher