From patchwork Tue May 17 17:51:24 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roger Sayle X-Patchwork-Id: 1632485 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=nextmovesoftware.com header.i=@nextmovesoftware.com header.a=rsa-sha256 header.s=default header.b=JoH57gJP; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4L2kFp4s1hz9s0w for ; Wed, 18 May 2022 03:51:41 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 51FB13857827 for ; Tue, 17 May 2022 17:51:39 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from server.nextmovesoftware.com (server.nextmovesoftware.com [162.254.253.69]) by sourceware.org (Postfix) with ESMTPS id 0EF093858D3C for ; Tue, 17 May 2022 17:51:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0EF093858D3C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=nextmovesoftware.com DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=nextmovesoftware.com; s=default; h=Content-Type:MIME-Version:Message-ID: Date:Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=32Ro1wnWri/YSQObVLUA5G94D/2May/eAQy6FFvIWII=; b=JoH57gJPdw12eF1anhMmhplrpR 3Nc+31KzkLPcCC6HKG9WjS7BFW752qQjSZUNSVs+MEmi+jEzLI+ka9ihA9XCqWkRQm5LfMIsqdV8V ccZQonYAn2Bbt3y9Kb0hZDM1lSBXIEPs+fKuPD2sn0A96KPlxQbaoQi+9by5ibCUqs/xAowRIrinR ACRa2kGceMFRXk54IiBK9FxV0R6uQ+6ek4Ceqt9nUdvCDegLpKCYc6JcDdJPk7xBY90QyjGzk+Yjx XYb2out0MBHEWk20czY5TPAHWQuwrrrXL52nmoqiH/215cVlmtLYPYHtd61S4LJypeSXY0++3pAVz USpht7sg==; Received: from host109-154-46-241.range109-154.btcentralplus.com ([109.154.46.241]:51747 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1nr1Ly-0003rE-H9; Tue, 17 May 2022 13:51:26 -0400 From: "Roger Sayle" To: Subject: [PATCH] Simplify logic in tree-scalar-evolution's expensive_expression_p. Date: Tue, 17 May 2022 18:51:24 +0100 Message-ID: <011c01d86a16$baaf6030$300e2090$@nextmovesoftware.com> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdhqFM2odeSGu9UMSWydGeOjxnZR1Q== Content-Language: en-gb X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - server.nextmovesoftware.com X-AntiAbuse: Original Domain - gcc.gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - nextmovesoftware.com X-Get-Message-Sender-Via: server.nextmovesoftware.com: authenticated_id: roger@nextmovesoftware.com X-Authenticated-Sender: server.nextmovesoftware.com: roger@nextmovesoftware.com X-Source: X-Source-Args: X-Source-Dir: X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch simplifies tree-scalar-evolution's expensive_expression_p, but produces identical results; the replacement implementation is just smaller (uses less memory), faster and easier to understand. The current idiom (introduced to fix PR90726) looks like: hash_map cache; uint64_t expanded_size = 0; return (expression_expensive_p (expr, cache, expanded_size) || expanded_size > cache.elements ()); Here the recursive function computes expanded_size, effectively the number of tree nodes visited, which is then only used in the comparison against cache.elements(), i.e. to check whether the number of visited nodes is greater than the number of unique visited nodes. This is equivalent to instead checking where expression_expensive_p's recursion visits any node more than once. Instead of using a map to cache the "cost" of revisited sub-trees, the same outcome can be determined using a set, and immediately returning true as soon as encountering a previously seen tree node, avoiding the unnecessary "cost"/expanded_size computation. [A simplification analogous to checking STL's empty() instead of comparing size() with zero]. The semantics of expensive_expression_p (both before and after) are quite reasonable, as calling unshare_expr on a generic tree can result in an exponential growth in the number of gimple statements, hence any "shared" nodes are indeed expensive. If shared nodes are to be allowed, they'll need to be managed explicitly with SAVE_EXPR (or similar mechanism) that avoids exponential growth. This patch has been tested on x86_64-pc-linux-gnu with make bootstrap and make -k check, both with and without --target_board=unix{-m32}, with no new failures. Is this a reasonable clean-up for mainline? 2022-05-17 Roger Sayle gcc/ChangeLog * tree_scalar_evolution.cc (expression_expensive_p): Change type of cache from hash_map to hash_set, and remove cost argument. When expr appears in the hash_set, return true. Calculation of cost (and updating hash_map) is no longer required. (expression_expensive_p): Simplify top-level implementation. Thanks in advance, Roger diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc index 72ceb40..347dede 100644 --- a/gcc/tree-scalar-evolution.cc +++ b/gcc/tree-scalar-evolution.cc @@ -3352,8 +3352,7 @@ scev_finalize (void) for scev_const_prop. */ static bool -expression_expensive_p (tree expr, hash_map &cache, - uint64_t &cost) +expression_expensive_p (tree expr, hash_set &cache) { enum tree_code code; @@ -3377,19 +3376,11 @@ expression_expensive_p (tree expr, hash_map &cache, return true; } - bool visited_p; - uint64_t &local_cost = cache.get_or_insert (expr, &visited_p); - if (visited_p) - { - uint64_t tem = cost + local_cost; - if (tem < cost) - return true; - cost = tem; - return false; - } - local_cost = 1; + /* If we've encountered this expression before, it would be duplicated + by unshare_expr, which makes this expression expensive. */ + if (cache.add (expr)) + return true; - uint64_t op_cost = 0; if (code == CALL_EXPR) { tree arg; @@ -3431,16 +3422,14 @@ expression_expensive_p (tree expr, hash_map &cache, } FOR_EACH_CALL_EXPR_ARG (arg, iter, expr) - if (expression_expensive_p (arg, cache, op_cost)) + if (expression_expensive_p (arg, cache)) return true; - *cache.get (expr) += op_cost; - cost += op_cost + 1; return false; } if (code == COND_EXPR) { - if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost) + if (expression_expensive_p (TREE_OPERAND (expr, 0), cache) || (EXPR_P (TREE_OPERAND (expr, 1)) && EXPR_P (TREE_OPERAND (expr, 2))) /* If either branch has side effects or could trap. */ @@ -3448,13 +3437,9 @@ expression_expensive_p (tree expr, hash_map &cache, || generic_expr_could_trap_p (TREE_OPERAND (expr, 1)) || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0)) || generic_expr_could_trap_p (TREE_OPERAND (expr, 0)) - || expression_expensive_p (TREE_OPERAND (expr, 1), - cache, op_cost) - || expression_expensive_p (TREE_OPERAND (expr, 2), - cache, op_cost)) + || expression_expensive_p (TREE_OPERAND (expr, 1), cache) + || expression_expensive_p (TREE_OPERAND (expr, 2), cache)) return true; - *cache.get (expr) += op_cost; - cost += op_cost + 1; return false; } @@ -3462,15 +3447,13 @@ expression_expensive_p (tree expr, hash_map &cache, { case tcc_binary: case tcc_comparison: - if (expression_expensive_p (TREE_OPERAND (expr, 1), cache, op_cost)) + if (expression_expensive_p (TREE_OPERAND (expr, 1), cache)) return true; /* Fallthru. */ case tcc_unary: - if (expression_expensive_p (TREE_OPERAND (expr, 0), cache, op_cost)) + if (expression_expensive_p (TREE_OPERAND (expr, 0), cache)) return true; - *cache.get (expr) += op_cost; - cost += op_cost + 1; return false; default: @@ -3481,10 +3464,8 @@ expression_expensive_p (tree expr, hash_map &cache, bool expression_expensive_p (tree expr) { - hash_map cache; - uint64_t expanded_size = 0; - return (expression_expensive_p (expr, cache, expanded_size) - || expanded_size > cache.elements ()); + hash_set cache; + return expression_expensive_p (expr, cache); } /* Do final value replacement for LOOP, return true if we did anything. */