Re: Prevent infinite recursion between simplification and CSE in FRE

[Marc Glisse <marc dot glisse at inria dot fr>]

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

--
Marc Glisse