From patchwork Mon Sep 30 08:04:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Artemiy Volkov X-Patchwork-Id: 1990780 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=hSd4pMJi; dkim=pass (2048-bit key; unprotected) header.d=synopsys.com header.i=@synopsys.com header.a=rsa-sha256 header.s=mail header.b=R4f8waKN; 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 4XHDG21H8lz1xsq for ; Mon, 30 Sep 2024 18:07:54 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 084FC385EC34 for ; Mon, 30 Sep 2024 08:07:52 +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 E8F9B385F01C for ; Mon, 30 Sep 2024 08:04:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E8F9B385F01C 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 E8F9B385F01C 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=1727683487; cv=none; b=mC0hZ+t4NELgJ2ViKyUpgBIdS1sldNWT9dWYpRW8Z5sh8If7ZEJLb4SwDLyBQU9KSlOgwfkWPobCOKn8sEE1JBh/V/EMalnF93Q6XnwHrV5bFQVsTJv02uRZtUyY9NQbE+Vm+lcJrh7ueNeuJWm10S2m6VfNMUxtH2Gxidg0GC8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727683487; c=relaxed/simple; bh=75oNLPo+2rfTRjGDJR+lakR79JeNEZ11ukmErWVHJ14=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=wm5jts2KsT63PG5j3lgulJ7CfzlKosqaURvIlQZuf+ZHmH9gBgXnDeyAoU6lSG0f0wMN4Nlg2cxcvug51zN0E1DSRRM0uKCuaK3wO8CVDzuQczPKdzAtz5dsbL39EBWbQzfDBLM71H5bzmDQwJMknybzMYj2z1+Xo3vT5PMN+zU= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0297266.ppops.net [127.0.0.1]) by mx0a-00230701.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 48U69Vfu017537; Mon, 30 Sep 2024 01:04:42 -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=+FUei9C+ WdGt77ij/4urriLt8AoQO3/ibBWhlhtwGPM=; b=hSd4pMJi+cqOb/5l2hwHm3TQ RgozhxPUOQYjyDBlZj808+DBLEASyqfkQHV6XWeMRE/bFxITcGOkAG/SlCbYX+Dp VCACaue0FniDjpWSO6lAuUDhxM4P4kAq24tHuxg7LwdS7G65yIVfoaR1274d8IzK HVSXY0MD1pZ10CAXS9/OjVv8cV889LDdRJXs6uCpcne/P7ZGkMdE362Uo7imDMvQ rDrfckjCGsxoMSEcuM0SKQIaJuFYgzAkusLh4R8tHbsFEv4XgoPJeMjg3PZaVkRz DatHE25JzZnWE8JQSrW5na3NUmISZTu/tO+iaNjadI1a1IzpayZ7KC+TqMXAxw== Received: from smtprelay-out1.synopsys.com (smtprelay-out1.synopsys.com [149.117.87.133]) by mx0a-00230701.pphosted.com (PPS) with ESMTPS id 41ybr32p2y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 30 Sep 2024 01:04:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=synopsys.com; s=mail; t=1727683481; bh=75oNLPo+2rfTRjGDJR+lakR79JeNEZ11ukmErWVHJ14=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=R4f8waKNDDs8yghsIfxgVXd1/vF2wFsl+f3Hx386UhxeT/b2rC8mYI2C0tBn2ZozB fapMaYlcEUcV29Q4V8WIqLVJ9PoNkN8nIsYNJLzLISRmuZfouuU+VNtk0uybo3RHVI SWJ0NU4fq93wAGwbLmtlb3tH7oPmbM8Ao6mIFfiAB8wmYyBmaCqTpeC6uT762Mia4v D3elWAzCuGQnKuhvTSfOnHGZ6+vIG6DV7PDEmx9en6+GoxNJFqiZ4qWcqaCUgUJvNd QNQvYZEEVU45KOI8zEV5DXtsATxEbGfsOOKx9IbuGE+P3HFUJOvsU02vWuw9WWzQWI Ye+tyjRXZN6bQ== 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 2EA184048F; Mon, 30 Sep 2024 08:04:41 +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 D4C71A0071; Mon, 30 Sep 2024 08:04:40 +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 4/4] tree-optimization/116024 - simplify some cases of X +- C1 cmp C2 Date: Mon, 30 Sep 2024 01:04:08 -0700 Message-ID: <20240930080408.2501963-5-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-Authority-Analysis: v=2.4 cv=NpODcNdJ c=1 sm=1 tr=0 ts=66fa5b99 cx=c_pps a=t4gDRyhI9k+KZ5gXRQysFQ==:117 a=t4gDRyhI9k+KZ5gXRQysFQ==:17 a=EaEq8P2WXUwA:10 a=qPHU084jO2kA:10 a=jIQo8A4GAAAA:8 a=PRY1uSrw7YHn5vZb0VwA:9 a=Lf5xNeLK5dgiOs8hzIjU:22 X-Proofpoint-ORIG-GUID: SPjGAY0BtgkVB0ZGNIEBjneYiHVt2g5- X-Proofpoint-GUID: SPjGAY0BtgkVB0ZGNIEBjneYiHVt2g5- 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 lowpriorityscore=0 priorityscore=1501 suspectscore=0 phishscore=0 spamscore=0 mlxscore=0 clxscore=1015 adultscore=0 mlxlogscore=999 malwarescore=0 bulkscore=0 impostorscore=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.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_NUMSUBJECT, KAM_SHORT, 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 Whenever C1 and C2 are integer constants, X is of a wrapping type, and cmp is a relational operator, the expression X +- C1 cmp C2 can be simplified in the following cases: (a) If cmp is <= and C2 -+ C1 == +INF(1), we can transform the initial comparison in the following way: X +- C1 <= C2 -INF <= X +- C1 <= C2 (add left hand side which holds for any X, C1) -INF -+ C1 <= X <= C2 -+ C1 (add -+C1 to all 3 expressions) -INF -+ C1 <= X <= +INF (due to (1)) -INF -+ C1 <= X (eliminate the right hand side since it holds for any X) (b) By analogy, if cmp if >= and C2 -+ C1 == -INF(1), use the following sequence of transformations: X +- C1 >= C2 +INF >= X +- C1 >= C2 (add left hand side which holds for any X, C1) +INF -+ C1 >= X >= C2 -+ C1 (add -+C1 to all 3 expressions) +INF -+ C1 >= X >= -INF (due to (1)) +INF -+ C1 >= X (eliminate the right hand side since it holds for any X) (c) The > and < cases are negations of (a) and (b), respectively. This transformation allows to occasionally save add / sub instructions, for instance the expression 3 + (uint32_t)f() < 2 compiles to cmn w0, #4 cset w0, ls instead of add w0, w0, 3 cmp w0, 2 cset w0, ls on aarch64. Testcases that go together with this patch have been split into two separate files, one containing testcases for unsigned variables and the other for wrapping signed ones (and thus compiled with -fwrapv). Additionally, one aarch64 test has been adjusted since the patch has caused the generated code to change from cmn w0, #2 csinc w0, w1, wzr, cc (x < -2) to cmn w0, #3 csinc w0, w1, wzr, cs (x <= -3) 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-2.c: New test. * gcc.dg/tree-ssa/pr116024-2-fwrapv.c: Ditto. * gcc.target/aarch64/gtu_to_ltu_cmp_1.c: Adjust. Signed-off-by: Artemiy Volkov --- gcc/match.pd | 43 ++++++++++++++++++- .../gcc.dg/tree-ssa/pr116024-2-fwrapv.c | 38 ++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr116024-2.c | 37 ++++++++++++++++ .../gcc.target/aarch64/gtu_to_ltu_cmp_1.c | 2 +- 4 files changed, 118 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr116024-2-fwrapv.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr116024-2.c diff --git a/gcc/match.pd b/gcc/match.pd index 3b973887470..30e66d3dbfa 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -8967,6 +8967,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (cmp @0 { TREE_OVERFLOW (res) ? drop_tree_overflow (res) : res; })))))))) (for cmp (lt le gt ge) + rcmp (gt ge lt le) (for op (plus minus) rop (minus plus) (simplify @@ -8994,7 +8995,47 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) "X cmp C2 -+ C1"), WARN_STRICT_OVERFLOW_COMPARISON); } - (cmp @0 { res; }))))))))) + (cmp @0 { res; }))))) +/* For wrapping types, simplify the following cases of X +- C1 CMP C2: + + (a) If CMP is <= and C2 -+ C1 == +INF (1), simplify to X >= -INF -+ C1 + by observing the following: + + X +- C1 <= C2 + ==> -INF <= X +- C1 <= C2 (add left hand side which holds for any X, C1) + ==> -INF -+ C1 <= X <= C2 -+ C1 (add -+C1 to all 3 expressions) + ==> -INF -+ C1 <= X <= +INF (due to (1)) + ==> -INF -+ C1 <= X (eliminate the right hand side since it holds for any X) + + (b) Similarly, if CMP is >= and C2 -+ C1 == -INF (1): + + X +- C1 >= C2 + ==> +INF >= X +- C1 >= C2 (add left hand side which holds for any X, C1) + ==> +INF -+ C1 >= X >= C2 -+ C1 (add -+C1 to all 3 expressions) + ==> +INF -+ C1 >= X >= -INF (due to (1)) + ==> +INF -+ C1 >= X (eliminate the right hand side since it holds for any X) + + (c) The > and < cases are negations of (a) and (b), respectively. */ + (if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))) + (with + { + wide_int max = wi::max_value (TREE_TYPE (@0)); + wide_int min = wi::min_value (TREE_TYPE (@0)); + + wide_int c2 = rop == PLUS_EXPR + ? wi::add (wi::to_wide (@2), wi::to_wide (@1)) + : wi::sub (wi::to_wide (@2), wi::to_wide (@1)); + } + (if (((cmp == LE_EXPR || cmp == GT_EXPR) && wi::eq_p (c2, max)) + || ((cmp == LT_EXPR || cmp == GE_EXPR) && wi::eq_p (c2, min))) + (with + { + wide_int c1 = rop == PLUS_EXPR + ? wi::add (wi::bit_not (c2), wi::to_wide (@1)) + : wi::sub (wi::bit_not (c2), wi::to_wide (@1)); + tree c1_cst = wide_int_to_tree (TREE_TYPE (@0), c1); + } + (rcmp @0 { c1_cst; }))))))))) /* Invert sign of X in comparisons of the form C1 - X CMP C2. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr116024-2-fwrapv.c b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-2-fwrapv.c new file mode 100644 index 00000000000..b9e88ba79fc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-2-fwrapv.c @@ -0,0 +1,38 @@ +/* PR tree-optimization/116024 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-forwprop1-details -fwrapv" } */ + +#include +#include + +uint32_t f(void); + +int32_t i3(void) +{ + int32_t l = -10 + (int32_t)f(); + return l <= INT32_MAX - 10; // f() >= INT32_MIN + 10 +} + +int32_t i3a(void) +{ + int32_t l = -20 + (int32_t)f(); + return l < INT32_MAX - 19; // f() > INT32_MAX + 20 +} + +int32_t i3b(void) +{ + int32_t l = 30 + (int32_t)f(); + return l >= INT32_MIN + 30; // f() <= INT32_MAX - 30 +} + +int32_t i3c(void) +{ + int32_t l = 40 + (int32_t)f(); + return l > INT32_MIN + 39; // f() < INT32_MIN - 40 +} + +/* { dg-final { scan-tree-dump-times "Removing dead stmt:.*? \\+" 4 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* >= -2147483638" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* >= -2147483628" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* <= 2147483617" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* <= 2147483607" 1 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr116024-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-2.c new file mode 100644 index 00000000000..f7ff0776826 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-2.c @@ -0,0 +1,37 @@ +/* PR tree-optimization/116024 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-forwprop1-details" } */ + +#include + +uint32_t f(void); + +int32_t i3(void) +{ + uint32_t l = 10 + (uint32_t)f(); + return l <= 9; // f() >= -10u +} + +int32_t i3a(void) +{ + uint32_t l = 20 + (uint32_t)f(); + return l < 20; // f() > -21u +} + +int32_t i3b(void) +{ + uint32_t l = 30 + (uint32_t)f(); + return l >= 30; // f() <= -31u +} + +int32_t i3c(void) +{ + uint32_t l = 40 + (uint32_t)f(); + return l > 39; // f() < -39u +} + +/* { dg-final { scan-tree-dump-times "Removing dead stmt:.*? \\+" 4 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* > 4294967285" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* > 4294967275" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* <= 4294967265" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* <= 4294967255" 1 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.target/aarch64/gtu_to_ltu_cmp_1.c b/gcc/testsuite/gcc.target/aarch64/gtu_to_ltu_cmp_1.c index 81c536c90af..bfcec6719de 100644 --- a/gcc/testsuite/gcc.target/aarch64/gtu_to_ltu_cmp_1.c +++ b/gcc/testsuite/gcc.target/aarch64/gtu_to_ltu_cmp_1.c @@ -10,4 +10,4 @@ f1 (int x, int t) return t; } -/* { dg-final { scan-assembler-times "cmn\\tw\[0-9\]+, #2" 1 } } */ +/* { dg-final { scan-assembler-times "cmn\\tw\[0-9\]+, #3" 1 } } */