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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTPS id 3BDC93858D39 for ; Tue, 26 Oct 2021 18:45:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3BDC93858D39 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-559-FLSQMtTROOyOhJxcfLqjAg-1; Tue, 26 Oct 2021 14:45:48 -0400 X-MC-Unique: FLSQMtTROOyOhJxcfLqjAg-1 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id A617B802B52 for ; Tue, 26 Oct 2021 18:45:47 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.193.172]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 356C71002EE2; Tue, 26 Oct 2021 18:45:47 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.16.1/8.16.1) with ESMTPS id 19QIjirT4064421 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 26 Oct 2021 20:45:44 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.16.1/8.16.1/Submit) id 19QIjivH4064420; Tue, 26 Oct 2021 20:45:44 +0200 Date: Tue, 26 Oct 2021 20:45:44 +0200 From: Jakub Jelinek To: Patrick Palka Cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780] Message-ID: <20211026184544.GA304296@tucnak> Reply-To: Jakub Jelinek References: <20211026174418.3142626-1-ppalka@redhat.com> MIME-Version: 1.0 In-Reply-To: <20211026174418.3142626-1-ppalka@redhat.com> X-Scanned-By: MIMEDefang 2.84 on 10.5.11.22 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, 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-List-Received-Date: Tue, 26 Oct 2021 18:45:51 -0000 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. 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. For mixed &&/|| or with ! that could still be expensive though. Jakub