From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id D286E3858403 for ; Mon, 1 Nov 2021 18:45:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D286E3858403 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-230-Vx5eLpHLPqGdjioBmCwd-g-1; Mon, 01 Nov 2021 14:45:53 -0400 X-MC-Unique: Vx5eLpHLPqGdjioBmCwd-g-1 Received: by mail-qv1-f70.google.com with SMTP id hf12-20020a0562140e8c00b00382cdfe644eso17214282qvb.23 for ; Mon, 01 Nov 2021 11:45:53 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:date:to:cc:subject:in-reply-to:message-id :references:mime-version; bh=X/dv3MAzHF6mQClM6GltiHD2pTyMu5xVfgpJZBzUjP0=; b=aBGDoX0PYRO4v20WhCYQgQfaga84vjbo74j1zENom2YVMJ8wWOFKNDMzKs8Es9NMyB VQ9wG7WqcMtGT12cUqeUASBsKnUAPFX64KooU3UdQq9W8XjRiDFybGxg+i/bYeev+G7B kPMDPBvfP/deNQoJBfFXIh3cvne3W2nv2JzikZuxoBbzi8v5Lp5iycL9cLKl2qybVAaf krmYkMbWFMwXTTlP/pxhiXNjvLfAON20KRZJyIdLfVlkTmHxE5prXwDGiu0oUaI3RAvr kg5aAW9w9Jn7yDbXwpOF2TjJMsfqXz4G+Lm3Kq+8VMZQ+Sxht9VraOgUnGVteO6Hv+HC kkzg== X-Gm-Message-State: AOAM532nxRPpuadz+8PeqlX6c+LUu+ntLmyMGlEDdRM6hy3KkK3c0oC2 TmBhhgpxUTP4PzlH8DmSzFHjLrWy2AsTUWrNLsLvFai0RlW0gPOh20ruXbjq/DgYIrP/pqciYPa YhWEEpr5FmglFgCxliQ== X-Received: by 2002:ac8:5c48:: with SMTP id j8mr25140103qtj.317.1635792352692; Mon, 01 Nov 2021 11:45:52 -0700 (PDT) X-Google-Smtp-Source: ABdhPJy27leWvoO0PbbjGqfadYX9/QjlHu8FY546JHGySu7ghAigVo7ty9e8ZE5raRavHIudgHdXsQ== X-Received: by 2002:ac8:5c48:: with SMTP id j8mr25140062qtj.317.1635792352275; Mon, 01 Nov 2021 11:45:52 -0700 (PDT) Received: from [192.168.1.130] (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id h8sm6705377qkn.17.2021.11.01.11.45.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 01 Nov 2021 11:45:51 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Mon, 1 Nov 2021 14:45:50 -0400 (EDT) To: Jakub Jelinek cc: Patrick Palka , Jason Merrill , gcc-patches List Subject: Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780] In-Reply-To: <20211029115922.GA304296@tucnak> Message-ID: <5d8a9b60-a78-7f35-a9f-e7e358496963@idea> References: <99c81449-d68a-31c8-2ce6-fff154508c9@idea> <20211026211108.GE304296@tucnak> <40dcf6d9-a4a-227a-9553-43c13a42b28e@idea> <8f7e4b0e-0de6-b80c-387b-81ebfd340bab@redhat.com> <65132255-53fe-4c2c-a256-4f1deba260ad@idea> <2eb3439b-1e68-5664-ac2e-f85e891c2a1b@redhat.com> <20211028173818.GU304296@tucnak> <874799b0-ac52-5983-2c1f-2e63611a7373@idea> <20211029115922.GA304296@tucnak> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-16.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 01 Nov 2021 18:45:57 -0000 On Fri, 29 Oct 2021, Jakub Jelinek wrote: > On Thu, Oct 28, 2021 at 03:35:20PM -0400, Patrick Palka wrote: > > > Is there a reason to turn this mode of evaluating everything twice if an > > > error should be diagnosed all the time, rather than only if we actually see > > > a TRUTH_*_EXPR we want to handle this way? > > > If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if > > > the first operand is already a constant, that seems like a waste of time. > > > > Hmm yeah, at the very least it wouldn't hurt to check > > processing_template_decl before doing the tf_error shenanigans. I'm not > > sure if we would gain anything by first looking for TRUTH_*_EXPR since > > that'd involve walking the entire expression anyway IIUC. > > I meant actually something like: > --- gcc/cp/constexpr.c.jj 2021-10-28 20:07:48.566193259 +0200 > +++ gcc/cp/constexpr.c 2021-10-29 13:47:48.824026156 +0200 > @@ -8789,7 +8789,7 @@ potential_constant_expression_1 (tree t, > return false; > } > else if (!check_for_uninitialized_const_var > - (tmp, /*constexpr_context_p=*/true, flags)) > + (tmp, /*constexpr_context_p=*/true, flags & ~(1 << 30))) > return false; > } > return RECUR (tmp, want_rval); > @@ -8896,14 +8896,36 @@ potential_constant_expression_1 (tree t, > tree op1 = TREE_OPERAND (t, 1); > if (!RECUR (op0, rval)) > return false; > - if (!(flags & tf_error) && RECUR (op1, rval)) > - /* When quiet, try to avoid expensive trial evaluation by first > - checking potentiality of the second operand. */ > - return true; > - if (!processing_template_decl) > - op0 = cxx_eval_outermost_constant_expr (op0, true); > + if (TREE_CODE (op0) != INTEGER_CST && !processing_template_decl) > + { > + /* If op0 is not a constant, we can either > + cxx_eval_outermost_constant_expr first, or RECUR (op1, rval) > + first. If quiet, perform the latter first, if not quiet > + and it is the outermost such TRUTH_*_EXPR, perform the > + latter first in quiet mode, followed by the former and > + retry with the latter in non-quiet mode. */ > + if ((flags & (1 << 30)) != 0) > + op0 = cxx_eval_outermost_constant_expr (op0, true); > + else if ((flags & tf_error) != 0) > + { > + flags &= ~tf_error; > + if (RECUR (op1, rval)) > + return true; > + op0 = cxx_eval_outermost_constant_expr (op0, true); > + flags |= tf_error | (1 << 30); > + } > + else > + { > + if (RECUR (op1, rval)) > + return true; > + op0 = cxx_eval_outermost_constant_expr (op0, true); > + if (tree_int_cst_equal (op0, tmp)) > + return false; > + return true; > + } > + } > if (tree_int_cst_equal (op0, tmp)) > - return (flags & tf_error) ? RECUR (op1, rval) : false; > + return RECUR (op1, rval); > else > return true; > } > @@ -9112,17 +9134,6 @@ bool > potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now, > tsubst_flags_t flags) > { > - if (flags & tf_error) > - { > - /* Check potentiality quietly first, as that could be performed more > - efficiently in some cases (currently only for TRUTH_*_EXPR). If > - that fails, replay the check noisily to give errors. */ > - flags &= ~tf_error; > - if (potential_constant_expression_1 (t, want_rval, strict, now, flags)) > - return true; > - flags |= tf_error; > - } > - > tree target = NULL_TREE; > return potential_constant_expression_1 (t, want_rval, strict, now, > flags, &target); > > (perhaps with naming the 1 << 30 as tf_something or using different bit for > that). So no doubling of potential_constant_expression_1 evaluation > for tf_error unless a TRUTH_*_EXPR is seen outside of template with > potentially constant first operand other than INTEGER_CST, but similarly to > what you did, make sure that there are at most two calls and not more. That makes sense, though it's somewhat unfortunate that we'd have to use/add an adhoc tsubst_flags_t flag with this approach :/ > > > > As I said, another possibility is something like: > > > /* Try to quietly evaluate T to constant, but don't try too hard. */ > > > > > > static tree > > > potential_constant_expression_eval (tree t) > > > { > > > auto o = make_temp_override (constexpr_ops_limit, > > > MIN (constexpr_ops_limit, 100)); > > > return cxx_eval_outermost_constant_expr (t, true); > > > } > > > and using this new function instead of cxx_eval_outermost_constant_expr (op, true); > > > everywhere in potential_constant_expression_1 should fix the quadraticness > > > too. > > > > This would technically fix the quadraticness but wouldn't it still mean > > that a huge left-associated constant logical expression is quite a bit > > slower to check than an equivalent right-associated one (depending on > > what we set constexpr_ops_limit to)? We should probably do this anyway > > anyway but it doesn't seem sufficient on its own to make equivalent > > left/right-associated logical expressions have the same performance > > behavior IMHO. > > The most expensive would be > #define TEN true && true && true && true && true && true && true && true && true && true && > TEN TEN TEN TEN TEN false > or something similar because if any of the && expressions (other than the > last one) are more expensive to constant evaluate, it would just mean it > would stop the quadratic behavior earlier. Ah yeah, I see what you mean. > > Though, of course this isn't either or, the potential_constant_expression_eval > could be mixed either with your current version, or the one adjusted by > the above untested patch, or by reversion of all the changes + linearization > into a vector. What do you think about combining your linearization idea with checking potentiality of each term before resorting to trial evaluation? The most concise/efficient way of implementing this seems to be using a recursive lambda that simultaneously linearizes and checks for potentiality (and stops at the first non potentially constant term): -- >8 -- gcc/cp/ChangeLog: * constexpr.c (potential_constant_expression_1) [RECUR_QUIETLY]: Define. : Reimplement by linearizing all terms of the con/disjunction while continuing to check potentiality of each term before resorting to trial evaluation. (potential_constant_expression_1): Don't mess with tf_error. --- gcc/cp/constexpr.c | 74 +++++++++++++++++++++++++++++----------------- 1 file changed, 47 insertions(+), 27 deletions(-) diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c index 40fe165c2b7..7855443cdf6 100644 --- a/gcc/cp/constexpr.c +++ b/gcc/cp/constexpr.c @@ -8055,6 +8055,9 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now, { #define RECUR(T,RV) \ potential_constant_expression_1 ((T), (RV), strict, now, flags, jump_target) +#define RECUR_QUIETLY(T,RV) \ + potential_constant_expression_1 ((T), (RV), strict, now, flags & ~tf_error, \ + jump_target) enum { any = false, rval = true }; int i; @@ -8885,27 +8888,55 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now, potentiality. */ case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR: - tmp = boolean_true_node; - goto truth; case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR: - tmp = boolean_false_node; - truth: { - tree op0 = TREE_OPERAND (t, 0); - tree op1 = TREE_OPERAND (t, 1); - if (!RECUR (op0, rval)) - return false; - if (!(flags & tf_error) && RECUR (op1, rval)) - /* When quiet, try to avoid expensive trial evaluation by first - checking potentiality of the second operand. */ + auto normalize_code = [] (tree_code c) -> tree_code { + if (c == TRUTH_ANDIF_EXPR) + c = TRUTH_AND_EXPR; + else if (c == TRUTH_ORIF_EXPR) + c = TRUTH_OR_EXPR; + return c; + }; + auto_vec terms; + /* A recursive lambda that collects the terms of the con/disjunction + R into the vector TERMS, stopping at the first term that isn't + potentially constant. Returns true iff all terms are potentially + constant. */ + auto checked_linearize = [&] (tree r, auto& self) -> bool { + if (normalize_code (TREE_CODE (r)) == normalize_code (TREE_CODE (t))) + return self (TREE_OPERAND (r, 0), self) + && self (TREE_OPERAND (r, 1), self); + else + { + terms.safe_push (r); + return RECUR_QUIETLY (r, rval); + } + }; + /* If all terms of T are potentially constant, then so is T. */ + if (checked_linearize (t, checked_linearize)) return true; - if (!processing_template_decl) - op0 = cxx_eval_outermost_constant_expr (op0, true); - if (tree_int_cst_equal (op0, tmp)) - return (flags & tf_error) ? RECUR (op1, rval) : false; + tree last_term = terms.pop (); + /* Otherwise, if trial evaluation of a potentially constant term + yields something other than the non-short-circuit constant, then + we must conservatively return true. */ + tree nsc_cst; + if (normalize_code (TREE_CODE (t)) == TRUTH_AND_EXPR) + nsc_cst = boolean_true_node; else - return true; + nsc_cst = boolean_false_node; + for (tree term : terms) + { + if (!processing_template_decl) + term = cxx_eval_outermost_constant_expr (term, true); + if (!tree_int_cst_equal (term, nsc_cst)) + return true; + } + /* Otherwise, diagnose non-potentiality of the last term and return + false. */ + if (flags & tf_error) + RECUR (last_term, rval); + return false; } case PLUS_EXPR: @@ -9112,17 +9143,6 @@ bool potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now, tsubst_flags_t flags) { - if (flags & tf_error) - { - /* Check potentiality quietly first, as that could be performed more - efficiently in some cases (currently only for TRUTH_*_EXPR). If - that fails, replay the check noisily to give errors. */ - flags &= ~tf_error; - if (potential_constant_expression_1 (t, want_rval, strict, now, flags)) - return true; - flags |= tf_error; - } - tree target = NULL_TREE; return potential_constant_expression_1 (t, want_rval, strict, now, flags, &target); -- 2.34.0.rc0