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.129.124]) by sourceware.org (Postfix) with ESMTPS id E1AA53857C66 for ; Thu, 19 Oct 2023 13:39:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E1AA53857C66 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org E1AA53857C66 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697722775; cv=none; b=oOJm8fs/ZU71bkZqQ156jyujYu+Q8AqMwIGxi5M9TMsDqaVwpN0JGMzTs59lqp2fkN5KhAyDZ/ZtAaB++Ig8jkwBo6JV6iu8aLINNCvDlVUthY+bB6qe/GWjOhEgcfun96W72jK/fb4vcsAAzsEVPMd56+O2QMZdVNmI9Yok5Os= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1697722775; c=relaxed/simple; bh=azjChjWyu6jLj2bfxCaGDFQqXAefRSkyWtedSwQ7+D8=; h=DKIM-Signature:From:Date:To:Subject:Message-ID:MIME-Version; b=YlTHe7FVeOUOQBSNrQGVvXdXcBhA4YT2BNnc1J2vMiwZxH7rwLuwIafh3fTT4Dqugefhdv4K1/hsbHC98aG+vylGM1aPTFpRKIkSEHRsRQZRNwt2vYXlkt4uIu8u+P+mnE41G6GaPDdMbp6asPk9abKyXpYhmzRc8ulI3Iq3OMo= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1697722773; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=r0MxsoVYahR+ClwtqGheNJLN8Yjm/6Q90ypc+Jtnqus=; b=cIJM7oif9G79/5jgkp6K3gCVqmsyd8yVmE2ebcoaaJ4oC5b/lHLYmwV/p2Rth3TeH/LXDb 3YCBke/WjY9vPSU91X+Qbjoha3M6xicYiFZ5AiV/k5iNeW9Bf4aziBpAHsfdSP/nPWtA2V g/wQJjAza2QUsu8SNZstYbROHhHVqBQ= Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-121-2bXsJeleMP6y8rFES56wgw-1; Thu, 19 Oct 2023 09:39:30 -0400 X-MC-Unique: 2bXsJeleMP6y8rFES56wgw-1 Received: by mail-qk1-f197.google.com with SMTP id af79cd13be357-77892d78dd3so210453685a.0 for ; Thu, 19 Oct 2023 06:39:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697722769; x=1698327569; h=mime-version:references:message-id:in-reply-to:subject:cc:to:date :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=r0MxsoVYahR+ClwtqGheNJLN8Yjm/6Q90ypc+Jtnqus=; b=ahGX2ceCm83VrHTr2IVXXtwpZvr4V4CZ9fzsYk6AlQlNUInmgjTrPpouyrGrmllgjp AWe1ZuhePN71tkWpeObabjHud5a/3BMFokzH4ddSJw76L/vbXxGjWksS7RmdSx0AmCfc amYywTKszzWbrRI4HJ/jhVXSSwzLzRM45WNGUZRufB6rZL8TuNz6mtArC5nvF0sbhg6b P1KPEBqSTM1CK8LpkZRHJDRzzBWO+dCQBdx7KDt7dazQmYce/gKXZDkHt6SDfX4H2wnB /LVw786S8xJA5OarGJT5/hgJvVk0gVgDUno/lr16kVztApecm5wzCPGAnRZ7sCjDDvqF M/hA== X-Gm-Message-State: AOJu0YwNLbZMqvzhEWHux79r4Dp60V0zhhffsAe+nIa4v3w3xGWx97Xl noYASFV8xQ8WXe/OPBo1n7LuGjab2KXVOnJcEemKo1Qui0Ole1g9cke993FiLh6Q/6j4canFfF8 uQxFJCB/EuO3U3Re0fQ== X-Received: by 2002:a05:620a:44ce:b0:777:2ac8:b434 with SMTP id y14-20020a05620a44ce00b007772ac8b434mr2557571qkp.72.1697722769461; Thu, 19 Oct 2023 06:39:29 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFbphIVLHEY/erVf3bEDY+0ScMXa/73Et4YfRK5M8g1ZrYD/O+4XDpyPI7SehyO5Fpj7FB8iw== X-Received: by 2002:a05:620a:44ce:b0:777:2ac8:b434 with SMTP id y14-20020a05620a44ce00b007772ac8b434mr2557549qkp.72.1697722769092; Thu, 19 Oct 2023 06:39:29 -0700 (PDT) Received: from [192.168.1.130] (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id u20-20020ae9c014000000b0077263636a95sm745664qkk.93.2023.10.19.06.39.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Oct 2023 06:39:28 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Thu, 19 Oct 2023 09:39:27 -0400 (EDT) To: Marek Polacek cc: Jason Merrill , GCC Patches Subject: Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] In-Reply-To: Message-ID: <180498f7-1f22-8889-862d-f796b3f16326@idea> References: <20231012210426.755503-1-polacek@redhat.com> <58e6893f-178e-4732-9c96-b52c38ad37c5@redhat.com> <14185c7f-42c2-4cf3-bfe1-bcc286aa07da@redhat.com> 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=-13.8 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_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Tue, 17 Oct 2023, Marek Polacek wrote: > On Tue, Oct 17, 2023 at 04:49:52PM -0400, Jason Merrill wrote: > > On 10/16/23 20:39, Marek Polacek wrote: > > > On Sat, Oct 14, 2023 at 01:13:22AM -0400, Jason Merrill wrote: > > > > On 10/13/23 14:53, Marek Polacek wrote: > > > > > On Thu, Oct 12, 2023 at 09:41:43PM -0400, Jason Merrill wrote: > > > > > > On 10/12/23 17:04, Marek Polacek wrote: > > > > > > > Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? > > > > > > > > > > > > > > -- >8 -- > > > > > > > My recent patch introducing cp_fold_immediate_r caused exponential > > > > > > > compile time with nested COND_EXPRs. The problem is that the COND_EXPR > > > > > > > case recursively walks the arms of a COND_EXPR, but after processing > > > > > > > both arms it doesn't end the walk; it proceeds to walk the > > > > > > > sub-expressions of the outermost COND_EXPR, triggering again walking > > > > > > > the arms of the nested COND_EXPR, and so on. This patch brings the > > > > > > > compile time down to about 0m0.033s. > > > > > > > > > > > > > > I've added some debug prints to make sure that the rest of cp_fold_r > > > > > > > is still performed as before. > > > > > > > > > > > > > > PR c++/111660 > > > > > > > > > > > > > > gcc/cp/ChangeLog: > > > > > > > > > > > > > > * cp-gimplify.cc (cp_fold_immediate_r) : Return > > > > > > > integer_zero_node instead of break;. > > > > > > > (cp_fold_immediate): Return true if cp_fold_immediate_r returned > > > > > > > error_mark_node. > > > > > > > > > > > > > > gcc/testsuite/ChangeLog: > > > > > > > > > > > > > > * g++.dg/cpp0x/hog1.C: New test. > > > > > > > --- > > > > > > > gcc/cp/cp-gimplify.cc | 9 ++-- > > > > > > > gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 +++++++++++++++++++++++++++++++ > > > > > > > 2 files changed, 82 insertions(+), 4 deletions(-) > > > > > > > create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C > > > > > > > > > > > > > > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc > > > > > > > index bdf6e5f98ff..ca622ca169a 100644 > > > > > > > --- a/gcc/cp/cp-gimplify.cc > > > > > > > +++ b/gcc/cp/cp-gimplify.cc > > > > > > > @@ -1063,16 +1063,16 @@ cp_fold_immediate_r (tree *stmt_p, int *walk_subtrees, void *data_) > > > > > > > break; > > > > > > > if (TREE_OPERAND (stmt, 1) > > > > > > > && cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data, > > > > > > > - nullptr)) > > > > > > > + nullptr) == error_mark_node) > > > > > > > return error_mark_node; > > > > > > > if (TREE_OPERAND (stmt, 2) > > > > > > > && cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data, > > > > > > > - nullptr)) > > > > > > > + nullptr) == error_mark_node) > > > > > > > return error_mark_node; > > > > > > > /* We're done here. Don't clear *walk_subtrees here though: we're called > > > > > > > from cp_fold_r and we must let it recurse on the expression with > > > > > > > cp_fold. */ > > > > > > > - break; > > > > > > > + return integer_zero_node; > > > > > > > > > > > > I'm concerned this will end up missing something like > > > > > > > > > > > > 1 ? 1 : ((1 ? 1 : 1), immediate()) > > > > > > > > > > > > as the integer_zero_node from the inner ?: will prevent walk_tree from > > > > > > looking any farther. > > > > > > > > > > You are right. The line above works as expected, but > > > > > > > > > > 1 ? 1 : ((1 ? 1 : id (42)), id (i)); > > > > > > > > > > shows the problem (when the expression isn't used as an initializer). > > > > > > > > > > > Maybe we want to handle COND_EXPR in cp_fold_r instead of here? > > > > > > > > > > I hope this version is better. > > > > > > > > > > Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? > > > > > > > > > > -- >8 -- > > > > > My recent patch introducing cp_fold_immediate_r caused exponential > > > > > compile time with nested COND_EXPRs. The problem is that the COND_EXPR > > > > > case recursively walks the arms of a COND_EXPR, but after processing > > > > > both arms it doesn't end the walk; it proceeds to walk the > > > > > sub-expressions of the outermost COND_EXPR, triggering again walking > > > > > the arms of the nested COND_EXPR, and so on. This patch brings the > > > > > compile time down to about 0m0.033s. > > > > > > > > Is this number still accurate for this version? > > > > > > It is. I ran time(1) a few more times and the results were 0m0.033s - 0m0.035s. > > > That said, ... > > > > > > > This change seems algorithmically better than the current code, but still > > > > problematic: if we have nested COND_EXPR A/B/C/D/E, it looks like we will > > > > end up cp_fold_immediate_r walking the arms of E five times, once for each > > > > COND_EXPR. > > > > > > ...this is accurate. I should have addressed the redundant folding in v2 > > > even though the compilation is pretty much immediate. > > > > What I was thinking by handling COND_EXPR in cp_fold_r was to cp_fold_r walk > > > > its subtrees (or cp_fold_immediate_r if it's clear from op0 that the branch > > > > isn't taken) so we can clear *walk_subtrees and we don't fold_imm walk a > > > > node more than once. > > > > > > I agree I should do better here. How's this, then? I've added > > > debug_generic_expr to cp_fold_immediate_r to see if it gets the same > > > expr multiple times and it doesn't seem to. > > > > > > Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? > > > > > > -- >8 -- > > > My recent patch introducing cp_fold_immediate_r caused exponential > > > compile time with nested COND_EXPRs. The problem is that the COND_EXPR > > > case recursively walks the arms of a COND_EXPR, but after processing > > > both arms it doesn't end the walk; it proceeds to walk the > > > sub-expressions of the outermost COND_EXPR, triggering again walking > > > the arms of the nested COND_EXPR, and so on. This patch brings the > > > compile time down to about 0m0.030s. > > > > > > The ff_fold_immediate flag is unused after this patch but since I'm > > > using it in the P2564 patch, I'm not removing it now. Maybe at_eof > > > can be used instead and then we can remove ff_fold_immediate. > > > > > > PR c++/111660 > > > > > > gcc/cp/ChangeLog: > > > > > > * cp-gimplify.cc (cp_fold_immediate_r) : Don't > > > handle it here. > > > (cp_fold_r): Handle COND_EXPR here. > > > > > > gcc/testsuite/ChangeLog: > > > > > > * g++.dg/cpp0x/hog1.C: New test. > > > * g++.dg/cpp2a/consteval36.C: New test. > > > --- > > > gcc/cp/cp-gimplify.cc | 52 +++++++++------- > > > gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 ++++++++++++++++++++++++ > > > gcc/testsuite/g++.dg/cpp2a/consteval36.C | 22 +++++++ > > > 3 files changed, 128 insertions(+), 23 deletions(-) > > > create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C > > > create mode 100644 gcc/testsuite/g++.dg/cpp2a/consteval36.C > > > > > > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc > > > index bdf6e5f98ff..a282c3930a3 100644 > > > --- a/gcc/cp/cp-gimplify.cc > > > +++ b/gcc/cp/cp-gimplify.cc > > > @@ -1052,27 +1052,6 @@ cp_fold_immediate_r (tree *stmt_p, int *walk_subtrees, void *data_) > > > switch (TREE_CODE (stmt)) > > > { > > > - /* Unfortunately we must handle code like > > > - false ? bar () : 42 > > > - where we have to check bar too. The cp_fold call in cp_fold_r could > > > - fold the ?: into a constant before we see it here. */ > > > - case COND_EXPR: > > > - /* If we are called from cp_fold_immediate, we don't need to worry about > > > - cp_fold folding away the COND_EXPR. */ > > > - if (data->flags & ff_fold_immediate) > > > - break; > > > - if (TREE_OPERAND (stmt, 1) > > > - && cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data, > > > - nullptr)) > > > - return error_mark_node; > > > - if (TREE_OPERAND (stmt, 2) > > > - && cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data, > > > - nullptr)) > > > - return error_mark_node; > > > - /* We're done here. Don't clear *walk_subtrees here though: we're called > > > - from cp_fold_r and we must let it recurse on the expression with > > > - cp_fold. */ > > > - break; > > > case PTRMEM_CST: > > > if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL > > > && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt))) > > > @@ -1162,8 +1141,35 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) > > > tree stmt = *stmt_p; > > > enum tree_code code = TREE_CODE (stmt); > > > - if (cxx_dialect > cxx17) > > > - cp_fold_immediate_r (stmt_p, walk_subtrees, data); > > > + if (cxx_dialect >= cxx20) > > > + { > > > + /* Unfortunately we must handle code like > > > + false ? bar () : 42 > > > + where we have to check bar too. The cp_fold call below could > > > + fold the ?: into a constant before we've checked it. */ > > > + if (code == COND_EXPR) > > > + { > > > + auto then_fn = cp_fold_r, else_fn = cp_fold_r; > > > + /* See if we can figure out if either of the branches is dead. If it > > > + is, we don't need to do everything that cp_fold_r does. */ > > > + tree cond = maybe_constant_value (TREE_OPERAND (stmt, 0)); > > > + if (integer_zerop (cond)) > > > + then_fn = cp_fold_immediate_r; > > > + else if (TREE_CODE (cond) == INTEGER_CST) > > > + else_fn = cp_fold_immediate_r; > > > + > > > + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); > > > > I wonder about doing this before maybe_constant_value, to hopefully reduce > > the redundant calculations? OK either way. > > Yeah, I was toying with that, I had > > foo() ? x : y > > where foo was a constexpr function but the cp_fold_r on op0 didn't eval it > to a constant :(. IIUC that's because cp_fold evaluates constexpr calls only with -O, so doing cp_fold_r before maybe_constant_value on the condition should still be desirable in that case? > > Thanks, > > Marek > >