On Mon, Jun 19, 2017 at 12:09 PM, Marc Glisse <marc.gli...@inria.fr> wrote: > On Mon, 19 Jun 2017, Richard Biener wrote: > >> On Sat, Jun 17, 2017 at 9:35 AM, Marc Glisse <marc.gli...@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
