From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 113283 invoked by alias); 19 Jun 2017 10:09:36 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 112824 invoked by uid 89); 19 Jun 2017 10:09:35 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.3 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_2,GIT_PATCH_3,KAM_LAZY_DOMAIN_SECURITY,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=caps, skinny X-HELO: mail2-relais-roc.national.inria.fr Received: from mail2-relais-roc.national.inria.fr (HELO mail2-relais-roc.national.inria.fr) (192.134.164.83) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 19 Jun 2017 10:09:33 +0000 Received: from afontenayssb-151-1-46-44.w82-121.abo.wanadoo.fr (HELO stedding) ([82.121.95.44]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 19 Jun 2017 12:09:35 +0200 Date: Mon, 19 Jun 2017 10:09:00 -0000 From: Marc Glisse Reply-To: GCC Patches To: Richard Biener cc: GCC Patches Subject: Re: Prevent infinite recursion between simplification and CSE in FRE In-Reply-To: Message-ID: References: User-Agent: Alpine 2.20 (DEB 67 2015-01-07) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed X-SW-Source: 2017-06/txt/msg01285.txt.bz2 On Mon, 19 Jun 2017, Richard Biener wrote: > On Sat, Jun 17, 2017 at 9:35 AM, Marc Glisse 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