From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id F3BAB3858D39 for ; Tue, 26 Oct 2021 19:29:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F3BAB3858D39 Received: from mail-pl1-f197.google.com (mail-pl1-f197.google.com [209.85.214.197]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-154-pUc9t94kN8GnrzZlJocBWQ-1; Tue, 26 Oct 2021 15:29:14 -0400 X-MC-Unique: pUc9t94kN8GnrzZlJocBWQ-1 Received: by mail-pl1-f197.google.com with SMTP id y3-20020a170902d64300b0013fc50eb97eso124977plh.17 for ; Tue, 26 Oct 2021 12:29:14 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=La0cYHwnCB7b+GLwp8INKlAqVxXWnaZE3R6xcdX4Jhg=; b=RCaJDstZmHrDQu8sO/vOs3rfASmR/4dJyUC1mhfX/3hL2DJJ+L0i2IMhD3WyIz8fka zfmDaCwGVSyoT8BiBOjMgWzaDb/R/QiOBjgqvYG70cKfNCklpve964KZyi9vpvgXJNHU EjshoOA4QgpYQKCmoxjkkjFCuh7sbsQS7p6nTXmwBkG3UVqh1Pr25DVpdDbOS0ZYpmFZ hMP4SzDZf6YnQjtJN7usc4t+QjZCfi7wlqUmpRZicKbbhzDe4RUxf419KAhY3tT5tB93 9JmKm2/5utUYIWG9/xdlClEAmuaAmzt4QVmaRM9K/e1y2xDAwYTTcnip57UV9QaQex52 ChFw== X-Gm-Message-State: AOAM532E4tK1vkoEVwUVtcTu0BPr4/te+XLec4S270AE0SgmWQfhFyaf vtUQuJBiWuo+49S2Gi5mPSGkZqFW9CM1cmGwTKcb3Szu4ZS2BvrUcm0tWuS0n3UdZs4/DbsTRtn ekb1yyOH+WbffFwSr+yVrENhO0NIicUJm8A== X-Received: by 2002:a05:6a00:2a9:b0:47b:db92:76a1 with SMTP id q9-20020a056a0002a900b0047bdb9276a1mr22954077pfs.37.1635276553617; Tue, 26 Oct 2021 12:29:13 -0700 (PDT) X-Google-Smtp-Source: ABdhPJz5xrr3dEVVZs+lk43GyM/HUVURBRzSWhaLAf/c3HWH8qkuX5tzsD7PxLBJdj5xaJbKRnyVoSvl+hiFaEdxMOw= X-Received: by 2002:a05:6a00:2a9:b0:47b:db92:76a1 with SMTP id q9-20020a056a0002a900b0047bdb9276a1mr22954051pfs.37.1635276553174; Tue, 26 Oct 2021 12:29:13 -0700 (PDT) MIME-Version: 1.0 References: <20211026174418.3142626-1-ppalka@redhat.com> <20211026184544.GA304296@tucnak> In-Reply-To: <20211026184544.GA304296@tucnak> From: Jason Merrill Date: Tue, 26 Oct 2021 15:29:02 -0400 Message-ID: Subject: Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780] To: Jakub Jelinek Cc: Patrick Palka , gcc-patches List X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-5.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, HTML_MESSAGE, 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 Content-Type: text/plain; charset="UTF-8" X-Content-Filtered-By: Mailman/MimeDel 2.1.29 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-List-Received-Date: Tue, 26 Oct 2021 19:29:18 -0000 On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches < gcc-patches@gcc.gnu.org> wrote: > On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches > wrote: > > 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. > Fair, especially now that it seems that C++23 is removing the diagnostic for a constexpr function that can't produce a constant expression. And as more functions become constexpr, the trial evaluation gets more expensive to get to the point of failure. I wonder if we want to stop calling cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only check whether the operand is already constant. For very large && or || expressions (but not mixed or with ! etc.) another > possibility would be to check if the lhs or rhs have the same code and if > so, linearize the trees and recurse only on the leafs (trees with other > TREE_CODE) and stop when first expression isn't equal to tmp. > This would be good if we wanted to keep the evaluation. Jason