* [PATCH] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] @ 2023-10-12 21:04 Marek Polacek 2023-10-13 1:41 ` Jason Merrill 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-12 21:04 UTC (permalink / raw) To: GCC Patches, Jason Merrill 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; case PTRMEM_CST: if (TREE_CODE (PTRMEM_CST_MEMBER (stmt)) == FUNCTION_DECL && DECL_IMMEDIATE_FUNCTION_P (PTRMEM_CST_MEMBER (stmt))) @@ -1145,7 +1145,8 @@ cp_fold_immediate (tree *tp, mce_value manifestly_const_eval) flags |= ff_mce_false; cp_fold_data data (flags); - return !!cp_walk_tree_without_duplicates (tp, cp_fold_immediate_r, &data); + tree r = cp_walk_tree_without_duplicates (tp, cp_fold_immediate_r, &data); + return r == error_mark_node; } /* Perform any pre-gimplification folding of C++ front end trees to 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() {} base-commit: 8bd11fa4ffcf8bceb6511a9d6918c90a34b705b5 -- 2.41.0 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-12 21:04 [PATCH] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] Marek Polacek @ 2023-10-13 1:41 ` Jason Merrill 2023-10-13 18:53 ` [PATCH v2] " Marek Polacek 0 siblings, 1 reply; 16+ messages in thread From: Jason Merrill @ 2023-10-13 1:41 UTC (permalink / raw) To: Marek Polacek, GCC Patches 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. Maybe we want to handle COND_EXPR in cp_fold_r instead of here? Jason ^ permalink raw reply [flat|nested] 16+ messages in thread
* [PATCH v2] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-13 1:41 ` Jason Merrill @ 2023-10-13 18:53 ` Marek Polacek 2023-10-14 5:13 ` Jason Merrill 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-13 18:53 UTC (permalink / raw) To: Jason Merrill; +Cc: GCC Patches 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. 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. 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 | 38 +++++------- gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 ++++++++++++++++++++++++ gcc/testsuite/g++.dg/cpp2a/consteval36.C | 18 ++++++ 3 files changed, 111 insertions(+), 22 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..801cba141cb 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))) @@ -1163,7 +1142,22 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) enum tree_code code = TREE_CODE (stmt); if (cxx_dialect > cxx17) - cp_fold_immediate_r (stmt_p, walk_subtrees, data); + { + /* 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) + { + if (TREE_OPERAND (stmt, 1)) + cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data, + nullptr); + if (TREE_OPERAND (stmt, 2)) + cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data, + nullptr); + } + 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..d6aea214d61 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp2a/consteval36.C @@ -0,0 +1,18 @@ +// 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" } +} base-commit: 8be20f3b0bded7f9b690b27cbee58b283dbe827b -- 2.41.0 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v2] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 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 0 siblings, 1 reply; 16+ messages in thread From: Jason Merrill @ 2023-10-14 5:13 UTC (permalink / raw) To: Marek Polacek; +Cc: GCC Patches 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? 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. 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. > 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. > > 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 | 38 +++++------- > gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 ++++++++++++++++++++++++ > gcc/testsuite/g++.dg/cpp2a/consteval36.C | 18 ++++++ > 3 files changed, 111 insertions(+), 22 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..801cba141cb 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))) > @@ -1163,7 +1142,22 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) > enum tree_code code = TREE_CODE (stmt); > > if (cxx_dialect > cxx17) > - cp_fold_immediate_r (stmt_p, walk_subtrees, data); > + { > + /* 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) > + { > + if (TREE_OPERAND (stmt, 1)) > + cp_walk_tree (&TREE_OPERAND (stmt, 1), cp_fold_immediate_r, data, > + nullptr); > + if (TREE_OPERAND (stmt, 2)) > + cp_walk_tree (&TREE_OPERAND (stmt, 2), cp_fold_immediate_r, data, > + nullptr); > + } > + 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..d6aea214d61 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/cpp2a/consteval36.C > @@ -0,0 +1,18 @@ > +// 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" } > +} > > base-commit: 8be20f3b0bded7f9b690b27cbee58b283dbe827b ^ permalink raw reply [flat|nested] 16+ messages in thread
* [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-14 5:13 ` Jason Merrill @ 2023-10-17 0:39 ` Marek Polacek 2023-10-17 20:49 ` Jason Merrill 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-17 0:39 UTC (permalink / raw) To: Jason Merrill; +Cc: GCC Patches 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); + 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 -- 2.41.0 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-17 0:39 ` [PATCH v3] " Marek Polacek @ 2023-10-17 20:49 ` Jason Merrill 2023-10-17 20:54 ` Marek Polacek 0 siblings, 1 reply; 16+ messages in thread From: Jason Merrill @ 2023-10-17 20:49 UTC (permalink / raw) To: Marek Polacek; +Cc: GCC Patches 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 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-17 20:49 ` Jason Merrill @ 2023-10-17 20:54 ` Marek Polacek 2023-10-19 13:39 ` Patrick Palka 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-17 20:54 UTC (permalink / raw) To: Jason Merrill; +Cc: GCC Patches 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) <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. 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 :(. Thanks, Marek ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 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:09 ` Marek Polacek 0 siblings, 2 replies; 16+ messages in thread From: Patrick Palka @ 2023-10-19 13:39 UTC (permalink / raw) To: Marek Polacek; +Cc: Jason Merrill, GCC Patches 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) <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. > > 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 > > ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 13:39 ` Patrick Palka @ 2023-10-19 14:06 ` Jason Merrill 2023-10-19 14:14 ` Marek Polacek 2023-10-19 14:09 ` Marek Polacek 1 sibling, 1 reply; 16+ messages in thread From: Jason Merrill @ 2023-10-19 14:06 UTC (permalink / raw) To: Patrick Palka, Marek Polacek; +Cc: GCC Patches On 10/19/23 09:39, Patrick Palka wrote: > 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) <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. >> >> 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? Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would think that folding the COND_EXPR also won't discard the other branch, so we shouldn't need to work harder to get a constant here, so we don't need to call maybe_constant_value at all? Jason ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 14:06 ` Jason Merrill @ 2023-10-19 14:14 ` Marek Polacek 2023-10-19 16:32 ` Jason Merrill 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-19 14:14 UTC (permalink / raw) To: Jason Merrill; +Cc: Patrick Palka, GCC Patches On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote: > On 10/19/23 09:39, Patrick Palka wrote: > > 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) <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. > > > > > > 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? > > Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would > think that folding the COND_EXPR also won't discard the other branch, so we > shouldn't need to work harder to get a constant here, so we don't need to > call maybe_constant_value at all? Sorry, I hadn't seen this message when I posted the tweak. But the maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make sense because it can render a branch dead even on -O0. Right? Marek ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 14:14 ` Marek Polacek @ 2023-10-19 16:32 ` Jason Merrill 2023-10-19 16:55 ` Marek Polacek 0 siblings, 1 reply; 16+ messages in thread From: Jason Merrill @ 2023-10-19 16:32 UTC (permalink / raw) To: Marek Polacek; +Cc: Patrick Palka, GCC Patches On 10/19/23 10:14, Marek Polacek wrote: > On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote: >> On 10/19/23 09:39, Patrick Palka wrote: >>> 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) <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. >>>> >>>> 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? >> >> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would >> think that folding the COND_EXPR also won't discard the other branch, so we >> shouldn't need to work harder to get a constant here, so we don't need to >> call maybe_constant_value at all? > > Sorry, I hadn't seen this message when I posted the tweak. But the > maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make > sense because it can render a branch dead even on -O0. Right? But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard the branch, so we don't need to do the extra work to find out that it's actually dead. Jason ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 16:32 ` Jason Merrill @ 2023-10-19 16:55 ` Marek Polacek 2023-10-19 17:02 ` Jason Merrill 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-19 16:55 UTC (permalink / raw) To: Jason Merrill; +Cc: Patrick Palka, GCC Patches On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote: > On 10/19/23 10:14, Marek Polacek wrote: > > On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote: > > > On 10/19/23 09:39, Patrick Palka wrote: > > > > 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) <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. > > > > > > > > > > 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? > > > > > > Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would > > > think that folding the COND_EXPR also won't discard the other branch, so we > > > shouldn't need to work harder to get a constant here, so we don't need to > > > call maybe_constant_value at all? > > > > Sorry, I hadn't seen this message when I posted the tweak. But the > > maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make > > sense because it can render a branch dead even on -O0. Right? > > But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard > the branch, so we don't need to do the extra work to find out that it's > actually dead. Hmm, so how about this? Thus far dg.exp passed. -- >8 -- This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O. cp_fold has: 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) 3144 && !flag_no_inline) ... 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, flag_no_inline is 1 for -O0: 1124 if (opts->x_optimize == 0) 1125 { 1126 /* Inlining does not work if not optimizing, 1127 so force it not to be done. */ 1128 opts->x_warn_inline = 0; 1129 opts->x_flag_no_inline = 1; 1130 } but otherwise it's 0 and cp_fold will maybe_constant_value calls to constexpr functions. And if it doesn't, then folding the COND_EXPR will keep both arms, and we can avoid calling maybe_constant_value. gcc/cp/ChangeLog: * cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value. --- gcc/cp/cp-gimplify.cc | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc index a282c3930a3..385042aeef2 100644 --- a/gcc/cp/cp-gimplify.cc +++ b/gcc/cp/cp-gimplify.cc @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) 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)) + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); + if (integer_zerop (TREE_OPERAND (stmt, 0))) then_fn = cp_fold_immediate_r; - else if (TREE_CODE (cond) == INTEGER_CST) + else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST) else_fn = cp_fold_immediate_r; - cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); if (TREE_OPERAND (stmt, 1)) cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data, nullptr); base-commit: 00e7c49fa04a3766e4726322b427621a74b78c71 -- 2.41.0 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 16:55 ` Marek Polacek @ 2023-10-19 17:02 ` Jason Merrill 2023-10-19 18:45 ` Marek Polacek 0 siblings, 1 reply; 16+ messages in thread From: Jason Merrill @ 2023-10-19 17:02 UTC (permalink / raw) To: Marek Polacek; +Cc: Patrick Palka, GCC Patches On 10/19/23 12:55, Marek Polacek wrote: > On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote: >> On 10/19/23 10:14, Marek Polacek wrote: >>> On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote: >>>> On 10/19/23 09:39, Patrick Palka wrote: >>>>> 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) <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. >>>>>> >>>>>> 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? >>>> >>>> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would >>>> think that folding the COND_EXPR also won't discard the other branch, so we >>>> shouldn't need to work harder to get a constant here, so we don't need to >>>> call maybe_constant_value at all? >>> >>> Sorry, I hadn't seen this message when I posted the tweak. But the >>> maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make >>> sense because it can render a branch dead even on -O0. Right? >> >> But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard >> the branch, so we don't need to do the extra work to find out that it's >> actually dead. > > Hmm, so how about this? Thus far dg.exp passed. > > -- >8 -- > This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the > COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O. > cp_fold has: > > 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) > 3144 && !flag_no_inline) > ... > 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, > > flag_no_inline is 1 for -O0: > > 1124 if (opts->x_optimize == 0) > 1125 { > 1126 /* Inlining does not work if not optimizing, > 1127 so force it not to be done. */ > 1128 opts->x_warn_inline = 0; > 1129 opts->x_flag_no_inline = 1; > 1130 } > > but otherwise it's 0 and cp_fold will maybe_constant_value calls to > constexpr functions. And if it doesn't, then folding the COND_EXPR > will keep both arms, and we can avoid calling maybe_constant_value. > > gcc/cp/ChangeLog: > > * cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value. > --- > gcc/cp/cp-gimplify.cc | 7 +++---- > 1 file changed, 3 insertions(+), 4 deletions(-) > > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc > index a282c3930a3..385042aeef2 100644 > --- a/gcc/cp/cp-gimplify.cc > +++ b/gcc/cp/cp-gimplify.cc > @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) > 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)) > + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); > + if (integer_zerop (TREE_OPERAND (stmt, 0))) > then_fn = cp_fold_immediate_r; > - else if (TREE_CODE (cond) == INTEGER_CST) > + else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST) You probably want to STRIP_NOPS before checking the TREE_CODE, like fold_ternary_loc and integer_zerop do. Jason ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 17:02 ` Jason Merrill @ 2023-10-19 18:45 ` Marek Polacek 2023-10-19 20:11 ` Jason Merrill 0 siblings, 1 reply; 16+ messages in thread From: Marek Polacek @ 2023-10-19 18:45 UTC (permalink / raw) To: Jason Merrill; +Cc: Patrick Palka, GCC Patches On Thu, Oct 19, 2023 at 01:02:33PM -0400, Jason Merrill wrote: > On 10/19/23 12:55, Marek Polacek wrote: > > On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote: > > > On 10/19/23 10:14, Marek Polacek wrote: > > > > On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote: > > > > > On 10/19/23 09:39, Patrick Palka wrote: > > > > > > On Tue, 17 Oct 2023, Marek Polacek wrote: [...] > > > > > > > > > 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? > > > > > > > > > > Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would > > > > > think that folding the COND_EXPR also won't discard the other branch, so we > > > > > shouldn't need to work harder to get a constant here, so we don't need to > > > > > call maybe_constant_value at all? > > > > > > > > Sorry, I hadn't seen this message when I posted the tweak. But the > > > > maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make > > > > sense because it can render a branch dead even on -O0. Right? > > > > > > But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard > > > the branch, so we don't need to do the extra work to find out that it's > > > actually dead. > > > > Hmm, so how about this? Thus far dg.exp passed. > > > > -- >8 -- > > This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the > > COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O. > > cp_fold has: > > > > 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) > > 3144 && !flag_no_inline) > > ... > > 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, > > > > flag_no_inline is 1 for -O0: > > > > 1124 if (opts->x_optimize == 0) > > 1125 { > > 1126 /* Inlining does not work if not optimizing, > > 1127 so force it not to be done. */ > > 1128 opts->x_warn_inline = 0; > > 1129 opts->x_flag_no_inline = 1; > > 1130 } > > > > but otherwise it's 0 and cp_fold will maybe_constant_value calls to > > constexpr functions. And if it doesn't, then folding the COND_EXPR > > will keep both arms, and we can avoid calling maybe_constant_value. > > > > gcc/cp/ChangeLog: > > > > * cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value. > > --- > > gcc/cp/cp-gimplify.cc | 7 +++---- > > 1 file changed, 3 insertions(+), 4 deletions(-) > > > > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc > > index a282c3930a3..385042aeef2 100644 > > --- a/gcc/cp/cp-gimplify.cc > > +++ b/gcc/cp/cp-gimplify.cc > > @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) > > 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)) > > + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); > > + if (integer_zerop (TREE_OPERAND (stmt, 0))) > > then_fn = cp_fold_immediate_r; > > - else if (TREE_CODE (cond) == INTEGER_CST) > > + else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST) > > You probably want to STRIP_NOPS before checking the TREE_CODE, like > fold_ternary_loc and integer_zerop do. Ok, or use integer_nonzerop like Patrick suggested: Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? -- >8 -- This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O. cp_fold has: 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) 3144 && !flag_no_inline) ... 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, flag_no_inline is 1 for -O0: 1124 if (opts->x_optimize == 0) 1125 { 1126 /* Inlining does not work if not optimizing, 1127 so force it not to be done. */ 1128 opts->x_warn_inline = 0; 1129 opts->x_flag_no_inline = 1; 1130 } but otherwise it's 0 and cp_fold will maybe_constant_value calls to constexpr functions. And if it doesn't, then folding the COND_EXPR will keep both arms, and we can avoid calling maybe_constant_value. gcc/cp/ChangeLog: * cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value. --- gcc/cp/cp-gimplify.cc | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc index a282c3930a3..33e9411f10c 100644 --- a/gcc/cp/cp-gimplify.cc +++ b/gcc/cp/cp-gimplify.cc @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) 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)) + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); + if (integer_zerop (TREE_OPERAND (stmt, 0))) then_fn = cp_fold_immediate_r; - else if (TREE_CODE (cond) == INTEGER_CST) + else if (integer_nonzerop (TREE_OPERAND (stmt, 0))) else_fn = cp_fold_immediate_r; - cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); if (TREE_OPERAND (stmt, 1)) cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data, nullptr); base-commit: d8e4e7def3338344a761d841010e98d017c58b0a -- 2.41.0 ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 18:45 ` Marek Polacek @ 2023-10-19 20:11 ` Jason Merrill 0 siblings, 0 replies; 16+ messages in thread From: Jason Merrill @ 2023-10-19 20:11 UTC (permalink / raw) To: Marek Polacek; +Cc: Patrick Palka, GCC Patches On 10/19/23 14:45, Marek Polacek wrote: > On Thu, Oct 19, 2023 at 01:02:33PM -0400, Jason Merrill wrote: >> On 10/19/23 12:55, Marek Polacek wrote: >>> On Thu, Oct 19, 2023 at 12:32:49PM -0400, Jason Merrill wrote: >>>> On 10/19/23 10:14, Marek Polacek wrote: >>>>> On Thu, Oct 19, 2023 at 10:06:01AM -0400, Jason Merrill wrote: >>>>>> On 10/19/23 09:39, Patrick Palka wrote: >>>>>>> On Tue, 17 Oct 2023, Marek Polacek wrote: > [...] >>>>>>>>>> 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? >>>>>> >>>>>> Hmm, and if the cp_fold_r doesn't reduce the test to a constant, I would >>>>>> think that folding the COND_EXPR also won't discard the other branch, so we >>>>>> shouldn't need to work harder to get a constant here, so we don't need to >>>>>> call maybe_constant_value at all? >>>>> >>>>> Sorry, I hadn't seen this message when I posted the tweak. But the >>>>> maybe_constant_value call on TREE_OPERAND (stmt, 0) should still make >>>>> sense because it can render a branch dead even on -O0. Right? >>>> >>>> But if op0 isn't constant after cp_fold, folding the COND_EXPR won't discard >>>> the branch, so we don't need to do the extra work to find out that it's >>>> actually dead. >>> >>> Hmm, so how about this? Thus far dg.exp passed. >>> >>> -- >8 -- >>> This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the >>> COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O. >>> cp_fold has: >>> >>> 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) >>> 3144 && !flag_no_inline) >>> ... >>> 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, >>> >>> flag_no_inline is 1 for -O0: >>> >>> 1124 if (opts->x_optimize == 0) >>> 1125 { >>> 1126 /* Inlining does not work if not optimizing, >>> 1127 so force it not to be done. */ >>> 1128 opts->x_warn_inline = 0; >>> 1129 opts->x_flag_no_inline = 1; >>> 1130 } >>> >>> but otherwise it's 0 and cp_fold will maybe_constant_value calls to >>> constexpr functions. And if it doesn't, then folding the COND_EXPR >>> will keep both arms, and we can avoid calling maybe_constant_value. >>> >>> gcc/cp/ChangeLog: >>> >>> * cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value. >>> --- >>> gcc/cp/cp-gimplify.cc | 7 +++---- >>> 1 file changed, 3 insertions(+), 4 deletions(-) >>> >>> diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc >>> index a282c3930a3..385042aeef2 100644 >>> --- a/gcc/cp/cp-gimplify.cc >>> +++ b/gcc/cp/cp-gimplify.cc >>> @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) >>> 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)) >>> + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); >>> + if (integer_zerop (TREE_OPERAND (stmt, 0))) >>> then_fn = cp_fold_immediate_r; >>> - else if (TREE_CODE (cond) == INTEGER_CST) >>> + else if (TREE_CODE (TREE_OPERAND (stmt, 0)) == INTEGER_CST) >> >> You probably want to STRIP_NOPS before checking the TREE_CODE, like >> fold_ternary_loc and integer_zerop do. > > Ok, or use integer_nonzerop like Patrick suggested: > > Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? OK. > -- >8 -- > This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the > COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O. > cp_fold has: > > 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) > 3144 && !flag_no_inline) > ... > 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, > > flag_no_inline is 1 for -O0: > > 1124 if (opts->x_optimize == 0) > 1125 { > 1126 /* Inlining does not work if not optimizing, > 1127 so force it not to be done. */ > 1128 opts->x_warn_inline = 0; > 1129 opts->x_flag_no_inline = 1; > 1130 } > > but otherwise it's 0 and cp_fold will maybe_constant_value calls to > constexpr functions. And if it doesn't, then folding the COND_EXPR > will keep both arms, and we can avoid calling maybe_constant_value. > > gcc/cp/ChangeLog: > > * cp-gimplify.cc (cp_fold_r): Don't call maybe_constant_value. > --- > gcc/cp/cp-gimplify.cc | 7 +++---- > 1 file changed, 3 insertions(+), 4 deletions(-) > > diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc > index a282c3930a3..33e9411f10c 100644 > --- a/gcc/cp/cp-gimplify.cc > +++ b/gcc/cp/cp-gimplify.cc > @@ -1152,13 +1152,12 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) > 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)) > + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); > + if (integer_zerop (TREE_OPERAND (stmt, 0))) > then_fn = cp_fold_immediate_r; > - else if (TREE_CODE (cond) == INTEGER_CST) > + else if (integer_nonzerop (TREE_OPERAND (stmt, 0))) > else_fn = cp_fold_immediate_r; > > - cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); > if (TREE_OPERAND (stmt, 1)) > cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data, > nullptr); > > base-commit: d8e4e7def3338344a761d841010e98d017c58b0a ^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH v3] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 2023-10-19 13:39 ` Patrick Palka 2023-10-19 14:06 ` Jason Merrill @ 2023-10-19 14:09 ` Marek Polacek 1 sibling, 0 replies; 16+ messages in thread From: Marek Polacek @ 2023-10-19 14:09 UTC (permalink / raw) To: Patrick Palka; +Cc: Jason Merrill, GCC Patches On Thu, Oct 19, 2023 at 09:39:27AM -0400, Patrick Palka wrote: > 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: > > > > - 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? Ah yeah, it depends on whether -fno-inline is on or off as described below. OK if testing passes? Thanks, -- >8 -- This patch is an optimization tweak for cp_fold_r. If we cp_fold_r the COND_EXPR's op0 first, we may be able to evaluate it to a constant if -O, saving some work. cp_fold has: 3143 if (callee && DECL_DECLARED_CONSTEXPR_P (callee) 3144 && !flag_no_inline) ... 3151 r = maybe_constant_value (x, /*decl=*/NULL_TREE, flag_no_inline is 1 for -O0: 1124 if (opts->x_optimize == 0) 1125 { 1126 /* Inlining does not work if not optimizing, 1127 so force it not to be done. */ 1128 opts->x_warn_inline = 0; 1129 opts->x_flag_no_inline = 1; 1130 } but otherwise it's 0 and cp_fold will maybe_constant_value calls to constexpr functions. gcc/cp/ChangeLog: * cp-gimplify.cc (cp_fold_r): cp_fold_r the first operand of a COND_EXPR before calling maybe_constant_value. --- gcc/cp/cp-gimplify.cc | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/gcc/cp/cp-gimplify.cc b/gcc/cp/cp-gimplify.cc index a282c3930a3..746de86dfa6 100644 --- a/gcc/cp/cp-gimplify.cc +++ b/gcc/cp/cp-gimplify.cc @@ -1151,14 +1151,16 @@ cp_fold_r (tree *stmt_p, int *walk_subtrees, void *data_) { 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. */ + is, we don't need to do everything that cp_fold_r does. If we + cp_fold_r first, there's a chance it will evaluate the condition to + a constant so maybe_constant_value won't have a lot of work to do. */ + cp_walk_tree (&TREE_OPERAND (stmt, 0), cp_fold_r, data, nullptr); 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); if (TREE_OPERAND (stmt, 1)) cp_walk_tree (&TREE_OPERAND (stmt, 1), then_fn, data, nullptr); base-commit: 19cc4b9d74940f29c961e2a5a8b1fa84992d3d30 -- 2.41.0 ^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2023-10-19 20:11 UTC | newest] Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-10-12 21:04 [PATCH] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] 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 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
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).