Prevent infinite recursion between simplification and CSE in FRE

[Richard Biener]

On Mon, Jun 19, 2017 at 12:09 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 19 Jun 2017, Richard Biener wrote:
>
>> On Sat, Jun 17, 2017 at 9:35 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>
>>> Hello,
>>>
>>> see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80887#c10 for the
>>> context.
>>> FRE can go into an infinite recursion with some match.pd simplifications
>>> (that have been temporarily reverted).
>>>
>>> Limiting the depth of recursive calls is not a great solution, but it is
>>> simple and I don't have a good idea for an alternate solution that does
>>> not
>>> disable a lot of desirable optimizations.
>>>
>>> There are many ways to write the limiter, I went with
>>>
>>>   depth_limiter d;
>>>   if (d > 100) return false;
>>>
>>> but I could also have written the class so the use would look like
>>>
>>>   depth_limiter d(100);
>>>   if (!d) return false;
>>>
>>> for instance.
>>>
>>> 100 was picked arbitrarily, I don't think it is worth having a param for
>>> it,
>>> but we could certainly use a different value.
>>>
>>> Bootstrap and testsuite on powerpc64le-unknown-linux-gnu.
>>
>>
>> I looked into the PR and I can't see anything wrong with the sequence
>> of events (they are just unfortunate...).  Somehow it feels the fix should
>> be somewhere in the used mprts_hook because w/o this hook we cannot
>> run into this kind of recursion.
>
>
> I would have used the depth trick in a function from FRE or SCCVN if I
> could, but the call stack had only the more general functions. I hadn't
> thought of resetting mprts_hook, that's a nice hack.
>
>> We can (and do, there's still at least one open PR ...) run into
>> oscillations
>> between two simplifications and this also happens for GENERIC folding
>> and the patch catches this case as well.
>
>
> Note that my patch was restricted to GIMPLE.
>
>> The consequence of stopping the recursion at an arbitrary point is
>> a missed optimization (in the PR there's no existing value we can
>> value-number to, so for that specific case it doesn't matter -- maybe
>> that's always the case with mprts_hook driven recursions).
>
>
> If there are really cases where the simplification can cascade arbitrarily
> far, we may get a stack overflow from doing normal simplification. Without
> quite reaching a stack overflow, we might also be able to cause quadratic
> time complexity. Restricting the recursion depth (possibly to something
> rather large) seems in line with other caps used in gcc.
>
>> So the nice thing about the patch is that we catch all cases but the
>> bad thing is that we don't anymore ICE on trivially contradicting
>> patterns ...
>
>
> Yes :-(
>
>
>> So the following is a SCCVN local recursion prevention - works on the
>> testcase.  Can you poke holes into it?
>>
>> Index: gcc/tree-ssa-sccvn.c
>> ===================================================================
>> --- gcc/tree-ssa-sccvn.c        (revision 249358)
>> +++ gcc/tree-ssa-sccvn.c        (working copy)
>> @@ -1648,8 +1648,21 @@ vn_lookup_simplify_result (code_helper r
>>   if (!rcode.is_tree_code ())
>>     return NULL_TREE;
>>   vn_nary_op_t vnresult = NULL;
>> -  return vn_nary_op_lookup_pieces (TREE_CODE_LENGTH ((tree_code) rcode),
>> -                                  (tree_code) rcode, type, ops,
>> &vnresult);
>> +  tree res = vn_nary_op_lookup_pieces (TREE_CODE_LENGTH ((tree_code)
>> rcode),
>> +                                      (tree_code) rcode, type, ops,
>> &vnresult);
>> +  /* We can end up endlessly recursing simplifications if the lookup
>> above
>> +     presents us with a def-use chain that mirrors the original
>> simplification.
>> +     See PR80887 for an example.  Limit successful lookup artificially
>> +     to 10 times if we are called as mprts_hook.  */
>> +  if (res && mprts_hook)
>> +    {
>> +      static unsigned cnt;
>> +      if (cnt == 0)
>> +       cnt = 9;
>> +      else if (--cnt == 0)
>> +       mprts_hook = NULL;
>> +    }
>> +  return res;
>> }
>
>
> I don't see how cnt is getting reset. It looks like after 9 non-recursive
> simplifications, a depth 2 simplification will get arbitrarily disabled.

Yes.  It's basically limiting invocations of the hook not recursion depth.
Note that we set the mprts_hook before each "simplification".

> Maybe cnt could be moved outside of the function and reset from
> vn_nary_build_or_lookup_1 (next to where we set mprts_hook)? This will not
> distinguish between a skinny tree of depth 10 and an almost-complete tree of
> depth 3, but that's probably not so important (we can always bump the limit
> of 10 a bit).

But that's what it should do.  Ah, wait - I see what you mean.  Yeah, I guess
I tried to be too clever when restricting changes to vn_lookup_simplify_result
and not the setters of mprts_hook ...

> I'll think about it later, unless you get to it first.

Making 'cnt' globally visible and setting it when we set mprts_hook would work.
I'll see how ugly that gets.

> (I wonder how much we would miss with the trivial "mprts_hook = NULL;" in
> place of your new block of code. Probably too much.)

Probably yes.

Thanks for catching,
Richard.

>
> --
> Marc Glisse