This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Prevent infinite recursion between simplification and CSE in FRE

On Mon, 19 Jun 2017, Richard Biener wrote:

On Sat, Jun 17, 2017 at 9:35 AM, Marc Glisse <> wrote:

see 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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]