From patchwork Tue Oct 26 17:44:18 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 46667 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 47F043858032 for ; Tue, 26 Oct 2021 17:45:50 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 47F043858032 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1635270350; bh=x4RtlMwD4vnw6QNDRRGasjkqVfeiPhy0FncXRmw2mwA=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=kX0M3hdhqskqhN7qvNRnsRSVnO2BFZK0BvIt+sH81VgsuvGmgvEov380HGIXItg0e HN+zMLPld4/M0FoaI+Rlm4KqfzgJy+HqV6VvJX3kEPwvCLjGF0GZQng5266SEt9n8p 42IfvRXvCAajhFXyiHIoHticO2iQ7D2Ym/CMB56M= 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 A17CC385802E for ; Tue, 26 Oct 2021 17:44:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A17CC385802E Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-512-FybhggnaMpOuSEh-iZvUHw-1; Tue, 26 Oct 2021 13:44:21 -0400 X-MC-Unique: FybhggnaMpOuSEh-iZvUHw-1 Received: by mail-qt1-f199.google.com with SMTP id p21-20020a05622a00d500b002a9f5e444a2so1448718qtw.7 for ; Tue, 26 Oct 2021 10:44:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=x4RtlMwD4vnw6QNDRRGasjkqVfeiPhy0FncXRmw2mwA=; b=c4/ZGEUz8CO+A0wtJnXKrJzrB+iGik+bapjTHxLzYkLqa23Q6xgqeJu+YlyfskGEEn acMTnGpTuWMffCaz058zP0AqK7ra+H1dipsWCwZ3tezRmk6MCQ/bGdz33+Rj9ETPidnZ +91FgzvwthhEOZaeaCqmbLuTnpplDYVTfe9ZAe/ACwlZ/AqcOtc1AJHGnFJAi6j+mKHO +rwOBHYNDZPEHfWr9uztyO+NSwIS6jbc6q0fldrt4/ao4lAR3z6Gurkw4ycFUEOVyf62 FTdS4mpihXgfvyxr0sM3Zov9dOeVNg51yuczNwXS6qf0soQXbRIF5w3mzYKkH8qMI8AN m1Uw== X-Gm-Message-State: AOAM532t5g5JHLLW/YjuqgjbNW3z/08+ZKfYWXQinkMJtuvvzNhlf9rV dRkWUku9qtLntqMYG7pkGZP0JR6vHlOUDE+9D/DMU40I8GFq0X8canM3omYba9RJk0vrIP0YFhI dX9rq1kWq7rZ+iN7KxGYeVcYmWsHevdp4XouL2lu+baSVAepdWEgQstQASFTp58//oo8= X-Received: by 2002:ac8:7f8c:: with SMTP id z12mr26685562qtj.292.1635270260394; Tue, 26 Oct 2021 10:44:20 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwhwn12Aoqj/aL6Qc1NAuTbYQvC72iKrdm9F6FJJ6MWZF+oMX9YTTtvJ9c7oTiHqsIhWSM6nA== X-Received: by 2002:ac8:7f8c:: with SMTP id z12mr26685540qtj.292.1635270260153; Tue, 26 Oct 2021 10:44:20 -0700 (PDT) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id q13sm616131qtx.80.2021.10.26.10.44.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 Oct 2021 10:44:19 -0700 (PDT) To: gcc-patches@gcc.gnu.org Subject: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780] Date: Tue, 26 Oct 2021 13:44:18 -0400 Message-Id: <20211026174418.3142626-1-ppalka@redhat.com> X-Mailer: git-send-email 2.33.1.711.g9d530dc002 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-15.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Patrick Palka via Gcc-patches From: Patrick Palka Reply-To: Patrick Palka Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" In the testcase below the two left fold expressions each expand into a logical expression with 1024 terms, for which potential_const_expr_1 takes more than a minute to return true. This is because p_c_e_1 performs trial evaluation of the first operand of a &&/|| in order to determine whether to consider its second operand. And because the expanded expression is left-associated, this trial evaluation causes p_c_e_1 to be quadratic in the number of terms of the expression. This patch fixes this quadratic behavior by making p_c_e_1 recurse only into the first operand of a &&/|| when checking for potentiality. This means we'll consider more non-constant expressions as potentially constant compared to the trial evaluation approach, but that should be harmless as later constexpr evaluation of the expression will deem it non-constant anyway. As a nice bonus, this change also reduces compile time for the libstdc++ testcase 20_util/variant/87619.cc by about 15%, even though our uses right folds instead of left folds. Likewise for the testcase in the PR, for which compile time is reduced by 30%. Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for trunk? PR c++/102780 gcc/cp/ChangeLog: * constexpr.c (potential_constant_expression_1) : Only recurse into the first operand, and ignore the second. gcc/testsuite/ChangeLog: * g++.dg/cpp1z/fold13.C: New test. --- gcc/cp/constexpr.c | 21 +++------------------ gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +++++++++++++++++++++++++++++ 2 files changed, 32 insertions(+), 18 deletions(-) create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c index 6f83d303cdd..9fd2c403afb 100644 --- a/gcc/cp/constexpr.c +++ b/gcc/cp/constexpr.c @@ -8880,28 +8880,13 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now, goto binary; } - /* If the first operand is the non-short-circuit constant, look at - the second operand; otherwise we only care about the first one for - potentiality. */ case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR: - tmp = boolean_true_node; - goto truth; case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR: - tmp = boolean_false_node; - truth: - { - tree op = TREE_OPERAND (t, 0); - if (!RECUR (op, rval)) - return false; - if (!processing_template_decl) - op = cxx_eval_outermost_constant_expr (op, true); - if (tree_int_cst_equal (op, tmp)) - return RECUR (TREE_OPERAND (t, 1), rval); - else - return true; - } + /* Only look at the first operand for potentiality since the second + operand may be irrelevant if the first short circuits. */ + return RECUR (TREE_OPERAND (t, 0), rval); case PLUS_EXPR: case MULT_EXPR: diff --git a/gcc/testsuite/g++.dg/cpp1z/fold13.C b/gcc/testsuite/g++.dg/cpp1z/fold13.C new file mode 100644 index 00000000000..b2b8c954be9 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp1z/fold13.C @@ -0,0 +1,29 @@ +// { dg-do compile { target c++17 } } +// Verify constexpr evaluation of a large left fold logical expression +// isn't quadratic in the size of the expanded expression. + +template struct S { static constexpr bool value = true; }; + +template struct integer_sequence { }; + +template + using make_integer_sequence +#if __has_builtin(__make_integer_seq) + = __make_integer_seq; +#else + = integer_sequence; +#endif + +template +constexpr bool f_impl(integer_sequence) { + return (... && S::value); +} + +static_assert(f_impl(make_integer_sequence())); + +template +constexpr bool g_impl(integer_sequence) { + return (... || !S::value); +} + +static_assert(!g_impl(make_integer_sequence()));