From patchwork Mon Sep 30 08:04:06 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Artemiy Volkov X-Patchwork-Id: 1990773 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=synopsys.com header.i=@synopsys.com header.a=rsa-sha256 header.s=pfptdkimsnps header.b=WQ7YE93o; dkim=pass (2048-bit key; unprotected) header.d=synopsys.com header.i=@synopsys.com header.a=rsa-sha256 header.s=mail header.b=S+E8Fthb; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XHDBz50nPz1xsq for ; Mon, 30 Sep 2024 18:05:15 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 89B773860762 for ; Mon, 30 Sep 2024 08:05:13 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-00230701.pphosted.com (mx0a-00230701.pphosted.com [148.163.156.19]) by sourceware.org (Postfix) with ESMTPS id 36301385EC15 for ; Mon, 30 Sep 2024 08:04:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 36301385EC15 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=synopsys.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=synopsys.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 36301385EC15 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=148.163.156.19 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727683484; cv=none; b=cAu1DrTMU1ISep01MtR7V0lCM1qn51jJdiV5/1jHIkYVF4Zjqz5YQzEFEsonc2Y9KrkgoIAhJD/6yLStnfjm7mdpGH1y6neezWflneft5ViosvlmaMyBUTsSVq81CV9VwFviClGtlsHYzoILxY0mtg4QG1pAwO0k/qlD/ER8Mp8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727683484; c=relaxed/simple; bh=QojDTvvH+hrijZ5qqqKt7ob8tfrMMi2ZRG96S/SYkSw=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=TzQ244xFj4LC7rlJhjopuwy2DP08aYRojdNS5p4J5kb2isOVOTgBVPmxI8YlbuFQD6bmiHmc5B0GqJPxw3UAqLebzMKINCvo2LyYL70jeHVXo/uYPTjejAXlF8Kgczx7UYp1ZzF2MZ/HVzDnzyu8r0jAScnIHWPXteFXR+UiODs= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0098571.ppops.net [127.0.0.1]) by mx0a-00230701.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 48U61iUZ008337; Mon, 30 Sep 2024 01:04:40 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=synopsys.com; h= cc:content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=pfptdkimsnps; bh=x9mSFxr6 moAK0Qv+9eN+difOXApF3CI8rRPbLuFXzkk=; b=WQ7YE93ojivbZDjEJQBEfOxn j8F8cyGj5S+T11OVRS3MDKu8eInFOgUpFFoazXjH7yi9/Vk/HOHFF/5j8Y4nBqC3 onmDyajGqd1fL1qZNWj4tQol9SKibzG+sVaDF8ZWJ8llTYGNvIXP3Ru4+ZL4gVcC a/w3z4zZhZpgCEZT5JpY4PbvGEoTARt6rFrYE1gQ1Z0z9uwmslQP53cGp9W7P3rj yYaCkqKJeZMzAXU5/xkqSGhQJawMLD+WLSI+7LMS6VN4kkRmdxgLq0HIUWYYT5l8 UeqtdDjntESFaZ2r3FV+zB69Jj5A4bBJ1nRv44/0UXbabgMl0izBCGUSzlJ7pQ== Received: from smtprelay-out1.synopsys.com (smtprelay-out1.synopsys.com [149.117.87.133]) by mx0a-00230701.pphosted.com (PPS) with ESMTPS id 41xgtn7d2p-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 30 Sep 2024 01:04:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=synopsys.com; s=mail; t=1727683479; bh=QojDTvvH+hrijZ5qqqKt7ob8tfrMMi2ZRG96S/SYkSw=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=S+E8FthbhzD1yzg26fawOyqOiMLLCSYkUZ42YoGAZ4QT73vow6HJGkIMLTwunQOR+ z/ylJ/zQnSYsl8IJFuTV6B1PxmCoS6hzvXkfbvcHRA7auUa1kMEVQawnplGvqwCq55 bv/GF6uDgkzJACsnQgetIgW2vwVSJHZBqgxdUKlc9BAFoFRY9PFuJH0+QYWdzRUb8a oYgPtwn3pfpy6KVPpfx/F1GUt0RRZzmhAFK8G0YD3FRO9KXOkhNz8NeIyP+DLNB8rb h6QWwKdBiRuC7knelsvUPbcaRD2gTJ0H5BJq2KKXOVLvAW4OEIkRLq+5vFyg9MYtN4 DZaFk3zSzSslA== Received: from mailhost.synopsys.com (badc-mailhost1.synopsys.com [10.192.0.17]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) client-signature RSA-PSS (2048 bits)) (Client CN "mailhost.synopsys.com", Issuer "SNPSica2" (verified OK)) by smtprelay-out1.synopsys.com (Postfix) with ESMTPS id 2FF594048F; Mon, 30 Sep 2024 08:04:39 +0000 (UTC) Received: from us01arcgnu3.internal.synopsys.com (us01arcgnu3.internal.synopsys.com [10.194.34.166]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) (Client did not present a certificate) by mailhost.synopsys.com (Postfix) with ESMTPSA id F115AA00B0; Mon, 30 Sep 2024 08:04:38 +0000 (UTC) X-SNPS-Relay: synopsys.com From: Artemiy Volkov To: gcc-patches@gcc.gnu.org Cc: rguenther@suse.de, jeffreyalaw@gmail.com, quic_apinski@quicinc.com, Artemiy Volkov Subject: [PATCH v4 2/4] tree-optimization/116024 - simplify C1-X cmp C2 for unsigned types Date: Mon, 30 Sep 2024 01:04:06 -0700 Message-ID: <20240930080408.2501963-3-artemiy@synopsys.com> X-Mailer: git-send-email 2.44.2 In-Reply-To: <20240930080408.2501963-1-artemiy@synopsys.com> References: <20240930080408.2501963-1-artemiy@synopsys.com> MIME-Version: 1.0 X-Proofpoint-GUID: ndaYf2CO8woZLrM3a8JnI6WNRrDBsbnx X-Proofpoint-ORIG-GUID: ndaYf2CO8woZLrM3a8JnI6WNRrDBsbnx X-Authority-Analysis: v=2.4 cv=faX/yFQF c=1 sm=1 tr=0 ts=66fa5b98 cx=c_pps a=t4gDRyhI9k+KZ5gXRQysFQ==:117 a=t4gDRyhI9k+KZ5gXRQysFQ==:17 a=EaEq8P2WXUwA:10 a=qPHU084jO2kA:10 a=jIQo8A4GAAAA:8 a=rGqp4SXJTxKLiM_M_kEA:9 a=Lf5xNeLK5dgiOs8hzIjU:22 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1039,Hydra:6.0.680,FMLib:17.12.60.29 definitions=2024-09-06_09,2024-09-06_01,2024-09-02_01 X-Proofpoint-Spam-Details: rule=outbound_active_cloned_notspam policy=outbound_active_cloned score=0 bulkscore=0 clxscore=1015 suspectscore=0 adultscore=0 impostorscore=0 lowpriorityscore=0 phishscore=0 spamscore=0 priorityscore=1501 mlxlogscore=999 malwarescore=0 mlxscore=0 classifier=spam authscore=0 adjust=0 reason=mlx scancount=1 engine=8.19.0-2408220000 definitions=main-2409300057 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, 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~incoming=patchwork.ozlabs.org@gcc.gnu.org Implement a match.pd transformation inverting the sign of X in C1 - X cmp C2, where C1 and C2 are integer constants and X is of an unsigned type, by observing that: (a) If cmp is == or !=, simply move X and C2 to opposite sides of the comparison to arrive at X cmp C1 - C2. (b) If cmp is <: - C1 - X < C2 means that C1 - X spans the range of 0, 1, ..., C2 - 1; - This means that X spans the range of C1 - (C2 - 1), C1 - (C2 - 2), ..., C1; - Subtracting C1 - (C2 - 1), X - (C1 - (C2 - 1)) is one of 0, 1, ..., C1 - (C1 - (C2 - 1)); - Simplifying the above, X - (C1 - C2 + 1) is one of 0, 1, ..., C2 - 1; - Summarizing, the expression C1 - X < C2 can be transformed into X - (C1 - C2 + 1) < C2. (c) Similarly, if cmp is <=: - C1 - X <= C2 means that C1 - X is one of 0, 1, ..., C2; - It follows that X is one of C1 - C2, C1 - (C2 - 1), ..., C1; - Subtracting C1 - C2, X - (C1 - C2) has range 0, 1, ..., C2; - Thus, the expression C1 - X <= C2 can be transformed into X - (C1 - C2) <= C2. (d) The >= and > cases are negations of (b) and (c), respectively. This transformation allows to occasionally save load-immediate / subtraction instructions, e.g. the following statement: 300 - (unsigned int)f() < 100; now compiles to addi a0,a0,-201 sltiu a0,a0,100 instead of li a5,300 sub a0,a5,a0 sltiu a0,a0,100 on 32-bit RISC-V. Additional examples can be found in the newly added test file. This patch has been bootstrapped and regtested on aarch64, x86_64, and i386, and additionally regtested on riscv32. gcc/ChangeLog: PR tree-optimization/116024 * match.pd: New transformation around integer comparison. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr116024-1.c: New test. Signed-off-by: Artemiy Volkov --- gcc/match.pd | 23 +++++++- gcc/testsuite/gcc.dg/tree-ssa/pr116024-1.c | 65 ++++++++++++++++++++++ 2 files changed, 87 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr116024-1.c diff --git a/gcc/match.pd b/gcc/match.pd index b074f49eebd..46195a603d0 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -9020,7 +9020,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) TYPE_SIGN (TREE_TYPE (@0))); constant_boolean_node (less == ovf_high, type); }) - (rcmp @1 { res; })))))) + (rcmp @1 { res; }))) +/* For unsigned types, transform like so (using < as example): + C1 - X < C2 + ==> C1 - X = { 0, 1, ..., C2 - 1 } + ==> X = { C1 - (C2 - 1), ..., C1 + 1, C1 } + ==> X - (C1 - (C2 - 1)) = { 0, 1, ..., C1 - (C1 - (C2 - 1)) } + ==> X - (C1 - C2 + 1) = { 0, 1, ..., C2 - 1 } + ==> X - (C1 - C2 + 1) < C2. + + Similarly, + C1 - X <= C2 ==> X - (C1 - C2) <= C2; + C1 - X >= C2 ==> X - (C1 - C2 + 1) >= C2; + C1 - X > C2 ==> X - (C1 - C2) > C2. */ + (if (TYPE_UNSIGNED (TREE_TYPE (@1))) + (switch + (if (cmp == EQ_EXPR || cmp == NE_EXPR) + (cmp @1 (minus @0 @2))) + (if (cmp == LE_EXPR || cmp == GT_EXPR) + (cmp (plus @1 (minus @2 @0)) @2)) + (if (cmp == LT_EXPR || cmp == GE_EXPR) + (cmp (plus @1 (minus @2 + (plus @0 { build_one_cst (TREE_TYPE (@1)); }))) @2))))))) /* Canonicalizations of BIT_FIELD_REFs. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr116024-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-1.c new file mode 100644 index 00000000000..91cb6a7c4f1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-1.c @@ -0,0 +1,65 @@ +/* PR tree-optimization/116024 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-forwprop1-details" } */ + +#include + +uint32_t f(void); + +int32_t i2(void) +{ + uint32_t l = 10 - (uint32_t)f(); + return l <= 20; // f() + 10 <= 20 +} + +int32_t i2a(void) +{ + uint32_t l = 10 - (uint32_t)f(); + return l < 30; // f() + 19 < 30 +} + +int32_t i2b(void) +{ + uint32_t l = 200 - (uint32_t)f(); + return l <= 100; // f() - 100 <= 100 +} + +int32_t i2c(void) +{ + uint32_t l = 300 - (uint32_t)f(); + return l < 100; // f() - 201 < 100 +} + +int32_t i2d(void) +{ + uint32_t l = 1000 - (uint32_t)f(); + return l >= 2000; // f() + 999 >= 2000 +} + +int32_t i2e(void) +{ + uint32_t l = 1000 - (uint32_t)f(); + return l > 3000; // f() + 2000 > 3000 +} + +int32_t i2f(void) +{ + uint32_t l = 20000 - (uint32_t)f(); + return l >= 10000; // f() - 10001 >= 10000 +} + +int32_t i2g(void) +{ + uint32_t l = 30000 - (uint32_t)f(); + return l > 10000; // f() - 20000 > 10000 +} + +/* { dg-final { scan-tree-dump-times "Removing dead stmt:.*?- _" 8 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 10.*\n.*<= 20" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 19.*\n.*<= 29" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 4294967196.*\n.*<= 100" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 4294967095.*\n.*<= 99" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 999.*\n.*> 1999" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 2000.*\n.*> 3000" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 4294957295.*\n.*> 9999" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ 4294947296.*\n.*> 10000" 1 "forwprop1" } } */