From patchwork Thu Oct 12 21:04:26 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marek Polacek X-Patchwork-Id: 152188 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:612c:2908:b0:403:3b70:6f57 with SMTP id ib8csp1498067vqb; Thu, 12 Oct 2023 14:05:07 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHMWtD4Gw/4UrSfNUcVRuc4GD4x6/lfh8riy8gVnzi9oL2x9TFN+eEOGf1W0erVWAvDztgE X-Received: by 2002:ac8:7f94:0:b0:418:f63f:7fe with SMTP id z20-20020ac87f94000000b00418f63f07femr33207338qtj.30.1697144706988; Thu, 12 Oct 2023 14:05:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1697144706; cv=none; d=google.com; s=arc-20160816; b=FsCV9Dtp5LLd7KmIO8pofyT4sP7LWp5qtF/uxdqUyBVIiiSWpQHttSMsDnUbEhnw3+ nO+LDeD+J+zXIx71/04kN53uRPpNQiP4OxCxfIHy/XUZfKt8wiwfE9/veIBhElxLJHVk vMRNWOzSSInbaTexCaECw3F+kNs1SZgzijidv9qlePxrB3qBhY25EzxGnMoL9FKRcBeN 09rIydRFcb68zVSt/e5Bic23OEn0/mYMq00A+Bz3+9J1pB9psi6YwaEF4vwp++Yd7fpI N4RqzDzEHsp9YZd4X+RLPWovPt58dYSx0L9IFZzRJA61t9o7+NArTnLOL8DJasRrs2nH Yv7w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:message-id:date:subject:to:from:dkim-signature :dmarc-filter:delivered-to; bh=vjx9GH6VqLjdJ0Rtr3F3P+CR02dc7u+U579Dwj8Xexg=; fh=2BFo3VQCimnyWTJsWe6sNdepvNrW+J/2ctoM6N7MZ0Y=; b=BU0VXuLefP5K/TQtVVBRJ/mP8/hFQyjT8JcKM+QlUfOL4T231SRGHKKqA32CPs8KM9 QAmbQPrkP7E3e7Ua/RySai6Bmp76GTkhoZyNzYUr/ehqRwrDkpdwrEXlWPGdbkDdS4TJ g+SrnQ8XpR/V3GfoMF30mHFrmJim15e6dbLWEKR4x+1uUBNwe33Vzlt84b6Jg7Am7Vao me8FwXonnQKg6FrsxiCo7M4LJqPvkrsrcG4hvdE2/0PwfJ7g2OB1O5KjE0PtcIFwQsG0 5OHxmAP0bIabzFuE/ouL940uHi2GD99LXKue1o2LcENcsHXtp7X2uVvHREo69mRFJw6r 4wvQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=RK+25t8u; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id w18-20020a05622a135200b00417a09a99b2si184876qtk.724.2023.10.12.14.05.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 12 Oct 2023 14:05:06 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=RK+25t8u; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BC35D385701C for ; Thu, 12 Oct 2023 21:05:06 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 3C54C3857438 for ; Thu, 12 Oct 2023 21:04:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3C54C3857438 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1697144681; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=vjx9GH6VqLjdJ0Rtr3F3P+CR02dc7u+U579Dwj8Xexg=; b=RK+25t8u05ZWC66O2zWOoYZCDEskVSnh0Lze5Nbzi635Ary0WySuJ8Qt9rQKrxXp1l3lW3 eOOYrchZg04Upf5TUIv6SVVBbeC5dZqw8+lhtigU24Ofth6f2lww5Dtl1gSDbT+iXUcKgn 4zg6ltBluhppT2c9OGxH2UZhpo1yXkA= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-682-ZkwYzucXPd2kzDJcImxTwQ-1; Thu, 12 Oct 2023 17:04:40 -0400 X-MC-Unique: ZkwYzucXPd2kzDJcImxTwQ-1 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.rdu2.redhat.com [10.11.54.5]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id ECB4F86384A for ; Thu, 12 Oct 2023 21:04:39 +0000 (UTC) Received: from pdp-11.redhat.com (unknown [10.22.17.145]) by smtp.corp.redhat.com (Postfix) with ESMTP id CE180906CF; Thu, 12 Oct 2023 21:04:39 +0000 (UTC) From: Marek Polacek To: GCC Patches , Jason Merrill Subject: [PATCH] c++: Fix compile-time-hog in cp_fold_immediate_r [PR111660] Date: Thu, 12 Oct 2023 17:04:26 -0400 Message-ID: <20231012210426.755503-1-polacek@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.5 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1779585207875623275 X-GMAIL-MSGID: 1779585207875623275 Bootstrapped/regtested on x86_64-pc-linux-gnu, ok for trunk? -- >8 -- My recent patch introducing cp_fold_immediate_r caused exponential compile time with nested COND_EXPRs. The problem is that the COND_EXPR case recursively walks the arms of a COND_EXPR, but after processing both arms it doesn't end the walk; it proceeds to walk the sub-expressions of the outermost COND_EXPR, triggering again walking the arms of the nested COND_EXPR, and so on. This patch brings the compile time down to about 0m0.033s. I've added some debug prints to make sure that the rest of cp_fold_r is still performed as before. PR c++/111660 gcc/cp/ChangeLog: * cp-gimplify.cc (cp_fold_immediate_r) : Return integer_zero_node instead of break;. (cp_fold_immediate): Return true if cp_fold_immediate_r returned error_mark_node. gcc/testsuite/ChangeLog: * g++.dg/cpp0x/hog1.C: New test. --- gcc/cp/cp-gimplify.cc | 9 ++-- gcc/testsuite/g++.dg/cpp0x/hog1.C | 77 +++++++++++++++++++++++++++++++ 2 files changed, 82 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/g++.dg/cpp0x/hog1.C base-commit: 8bd11fa4ffcf8bceb6511a9d6918c90a34b705b5 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() {}