Prevent infinite recursion between simplification and CSE in FRE

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.

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.

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).

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 ...

So the following is a SCCVN local recursion prevention - works on the
testcase.  Can you poke holes into it?



> 2017-06-19  Marc Glisse  <marc.glisse@inria.fr>
>
>         * gimple-match-head.c (depth_limiter): New class.
>         * genmatch.c (decision_tree::gen): Use it.
>
> --
> Marc Glisse

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. 
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).

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

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

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