From: Jason Merrill <jason@redhat.com>
To: Marek Polacek <polacek@redhat.com>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660]
Date: Tue, 17 Oct 2023 16:49:52 -0400 [thread overview]
Message-ID: <14185c7f-42c2-4cf3-bfe1-bcc286aa07da@redhat.com> (raw)
In-Reply-To: <ZS3X2OsF1uE/DRW4@redhat.com>
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) <case COND_EXPR>: 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) <case COND_EXPR>: 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.
> + if (TREE_OPERAND (stmt, 1))
> + cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data,
> + nullptr);
> + if (TREE_OPERAND (stmt, 2))
> + cp_walk_tree (&TREE_OPERAND (stmt, 2), else_fn, data,
> + nullptr);
> + *walk_subtrees = 0;
> + /* Don't return yet, still need the cp_fold below. */
> + }
> + cp_fold_immediate_r (stmt_p, walk_subtrees, data);
> + }
>
> *stmt_p = stmt = cp_fold (*stmt_p, data->flags);
>
> diff --git a/gcc/testsuite/g++.dg/cpp0x/hog1.C b/gcc/testsuite/g++.dg/cpp0x/hog1.C
> new file mode 100644
> index 00000000000..105a2e912c4
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp0x/hog1.C
> @@ -0,0 +1,77 @@
> +// PR c++/111660
> +// { dg-do compile { target c++11 } }
> +
> +enum Value {
> + LPAREN,
> + RPAREN,
> + LBRACE,
> + RBRACE,
> + LBRACK,
> + RBRACK,
> + CONDITIONAL,
> + COLON,
> + SEMICOLON,
> + COMMA,
> + PERIOD,
> + BIT_OR,
> + BIT_AND,
> + BIT_XOR,
> + BIT_NOT,
> + NOT,
> + LT,
> + GT,
> + MOD,
> + ASSIGN,
> + ADD,
> + SUB,
> + MUL,
> + DIV,
> + PRIVATE_NAME,
> + STRING,
> + TEMPLATE_SPAN,
> + IDENTIFIER,
> + WHITESPACE,
> + ILLEGAL,
> +};
> +
> +constexpr Value GetOneCharToken(char c) {
> + return
> + c == '(' ? LPAREN :
> + c == ')' ? RPAREN :
> + c == '{' ? LBRACE :
> + c == '}' ? RBRACE :
> + c == '[' ? LBRACK :
> + c == ']' ? RBRACK :
> + c == '?' ? CONDITIONAL :
> + c == ':' ? COLON :
> + c == ';' ? SEMICOLON :
> + c == ',' ? COMMA :
> + c == '.' ? PERIOD :
> + c == '|' ? BIT_OR :
> + c == '&' ? BIT_AND :
> + c == '^' ? BIT_XOR :
> + c == '~' ? BIT_NOT :
> + c == '!' ? NOT :
> + c == '<' ? LT :
> + c == '>' ? GT :
> + c == '%' ? MOD :
> + c == '=' ? ASSIGN :
> + c == '+' ? ADD :
> + c == '-' ? SUB :
> + c == '*' ? MUL :
> + c == '/' ? DIV :
> + c == '#' ? PRIVATE_NAME :
> + c == '"' ? STRING :
> + c == '\'' ? STRING :
> + c == '`' ? TEMPLATE_SPAN :
> + c == '\\' ? IDENTIFIER :
> + c == ' ' ? WHITESPACE :
> + c == '\t' ? WHITESPACE :
> + c == '\v' ? WHITESPACE :
> + c == '\f' ? WHITESPACE :
> + c == '\r' ? WHITESPACE :
> + c == '\n' ? WHITESPACE :
> + ILLEGAL;
> +}
> +
> +int main() {}
> diff --git a/gcc/testsuite/g++.dg/cpp2a/consteval36.C b/gcc/testsuite/g++.dg/cpp2a/consteval36.C
> new file mode 100644
> index 00000000000..9c470e4b7d7
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/consteval36.C
> @@ -0,0 +1,22 @@
> +// PR c++/111660
> +// { dg-do compile { target c++20 } }
> +
> +consteval int id (int i) { return i; }
> +
> +void
> +g (int i)
> +{
> + 1 ? 1 : ((1 ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? 1 : 1), id (i), 1); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((i ? 1 : 1), id (i), 1); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? i : 1), id (i), 1); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? 1 : i), id (i), 1); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((i ? -i : i), id (i), 1); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? 1 : id (i)), id (42), 1); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? 1 : id (42)), id (i)); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? 1 : id (42)), id (i), 1); // { dg-error "'i' is not a constant expression" }
> + id (i) ? 1 : ((1 ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((1 ? 1 : id (i)), id (i)); // { dg-error "'i' is not a constant expression" }
> + 1 ? id (i) : ((1 ? 1 : id (i)), id (i)); // { dg-error "'i' is not a constant expression" }
> + 1 ? 1 : ((id (i) ? 1 : 1), id (i)); // { dg-error "'i' is not a constant expression" }
> +}
>
> base-commit: 328745607c5d403a1c7b6bc2ecaa1574ee42122f
next prev parent reply other threads:[~2023-10-17 20:49 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-10-12 21:04 [PATCH] " Marek Polacek
2023-10-13 1:41 ` Jason Merrill
2023-10-13 18:53 ` [PATCH v2] " Marek Polacek
2023-10-14 5:13 ` Jason Merrill
2023-10-17 0:39 ` [PATCH v3] " Marek Polacek
2023-10-17 20:49 ` Jason Merrill [this message]
2023-10-17 20:54 ` Marek Polacek
2023-10-19 13:39 ` Patrick Palka
2023-10-19 14:06 ` Jason Merrill
2023-10-19 14:14 ` Marek Polacek
2023-10-19 16:32 ` Jason Merrill
2023-10-19 16:55 ` Marek Polacek
2023-10-19 17:02 ` Jason Merrill
2023-10-19 18:45 ` Marek Polacek
2023-10-19 20:11 ` Jason Merrill
2023-10-19 14:09 ` Marek Polacek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=14185c7f-42c2-4cf3-bfe1-bcc286aa07da@redhat.com \
--to=jason@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=polacek@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).