Re: Prevent infinite recursion between simplification and CSE in FRE

[Richard Biener <richard.guenther@gmail.com>]

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?

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;
 }

 /* Return a value-number for RCODE OPS... either by looking up an existing


> 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