From patchwork Mon Sep 30 08:04:07 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Artemiy Volkov X-Patchwork-Id: 1990777 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=sbpzjhCN; dkim=pass (2048-bit key; unprotected) header.d=synopsys.com header.i=@synopsys.com header.a=rsa-sha256 header.s=mail header.b=CmJq0gnF; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; 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 [8.43.85.97]) (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 4XHDDK6hgDz1xsq for ; Mon, 30 Sep 2024 18:06:25 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 204EE3860008 for ; Mon, 30 Sep 2024 08:06:24 +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 419D5385EC17 for ; Mon, 30 Sep 2024 08:04:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 419D5385EC17 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 419D5385EC17 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=hIYkQcZkEU6Q3jX4QTw2ESnUa6MWZX/bSVgOg7IWD59IDaj9KwgO4P8VuWgxbVM2+oW1cdeS5RoNxQTDN3f91SFZfoDNTqeCmMzJnHaWbp35ayqEi16yx6DfHqQwSnfWe8n3OudEWL41DBguZAaaYXt95QXkGsmzX9WAcXHxliQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1727683484; c=relaxed/simple; bh=KaSL0/S6MgFnUukKwkC0Wf+22ZPH+P9wra85mnlAb4c=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=Y2a38AJ888q25TXyIeIkpxgLs84e+fA6enTmZ4QgOExf4q5SKE/0F6P6VIvZndCZBZWAi0pLW+hax1UsymcxukPcp20J6AHt6BhVAMddd5UN3o4TN1C/k0u9z2qdIMbNNxLAjFO0/cSme/atLVa2LWnwMhfnN1kvvruRkTzazmE= 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 48U61iUb008337; Mon, 30 Sep 2024 01:04:41 -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=q9hSVx2A Feuc+190k3EpgxUzm1TVqWJvwFCTzNdyRhM=; b=sbpzjhCNpCA79Lz4ZnpxSsvA E3HCddaOQ4uQbRghyl3GmvKdTeb2+kMp6VDoEJ73SNcEUaYtdGStNKXCnm9rLCNW CF+qZy9bK3IpMIHtBoHdGF2Aoa3h2FtrYz9cpJs17Cc/MNdWNXISw+gqF9ZFleYJ cddbUsaPKXL6aikJUMXy/Kr6cfFj/CQ/Olh86d7DIIQ9Z6kjIiTf3M/F6NzXmd7z VY5+VFWvmToRXFjpzQVpQKX7r6IqMjroS4mi/Ehv9pbWwj3E9FT+an19YIgv/OvH HqD5Uu8BlwbJFFpt2VNXnrkG1Um39XWe7oEtVRNJaAVxeIGUd40JHQ6eUzNX7g== Received: from smtprelay-out1.synopsys.com (smtprelay-out1.synopsys.com [149.117.87.133]) by mx0a-00230701.pphosted.com (PPS) with ESMTPS id 41xgtn7d2u-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=1727683480; bh=KaSL0/S6MgFnUukKwkC0Wf+22ZPH+P9wra85mnlAb4c=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=CmJq0gnFuqrFjA93tbAHcPNqOt65U3TCKtD1c0ZUMsqxmTVw7PUdgfqbBJtbAYH1s 8TAh/90vEPNR3K1Ga7jcMvptoJ1TVv80cJudsYKHQtCG5n/2RGuJ+Uvywzkuh2y2ho mbzHNgdBSkoM5bpZYuHhP9YsFm8wmojRbBVl32ZjSEQ9fcC5BfYl7dyInArYch7F3d h4wFxwHizZpLDP208rPlfwGXgxLWT3mvp5V2UOGhqTu7ensSbJvtHuuuWM1BWvOgDY 1gZSvtWgm29noDhxagTCswzJ6S37KQ1OEN3loOgoO+CAYk3lI7iGkUKDRTpYsCbXY2 IuCay5q/5wPlw== 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 78C0940561; Mon, 30 Sep 2024 08:04:40 +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 19EAAA0071; 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 3/4] tree-optimization/116024 - simplify C1-X cmp C2 for wrapping signed types Date: Mon, 30 Sep 2024 01:04:07 -0700 Message-ID: <20240930080408.2501963-4-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: 7SVwygWb3viZcFseWrGW9FsbzS_4zBB_ X-Proofpoint-ORIG-GUID: 7SVwygWb3viZcFseWrGW9FsbzS_4zBB_ X-Authority-Analysis: v=2.4 cv=faX/yFQF 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=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.6 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 a wrapping signed 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 values of -INF, -INF + 1, ..., C2 - 1; - Therefore, X is one of C1 - -INF, C1 - (-INF + 1), ..., C1 - C2 + 1; - Subtracting (C1 + 1), X - (C1 + 1) is one of - (-INF) - 1, - (-INF) - 2, ..., -C2; - Using the fact that - (-INF) - 1 is +INF, derive that X - (C1 + 1) spans the values +INF, +INF - 1, ..., -C2; - Thus, the original expression can be simplified to X - (C1 + 1) > -C2 - 1. (c) Similarly, C1 - X <= C2 is equivalent to X - (C1 + 1) >= -C2 - 1. (d) The >= and > cases are negations of (b) and (c), respectively. (e) In all cases, the expression -C2 - 1 can be shortened to bit_not (C2). This transformation allows to occasionally save load-immediate / subtraction instructions, e.g. the following statement: 10 - (int)f() >= 20; now compiles to addi a0,a0,-11 slti a0,a0,-20 instead of li a5,10 sub a0,a5,a0 slti t0,a0,20 xori a0,t0,1 on 32-bit RISC-V when compiled with -fwrapv. 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-fwrapv.c: New test. Signed-off-by: Artemiy Volkov --- gcc/match.pd | 21 +++++- .../gcc.dg/tree-ssa/pr116024-1-fwrapv.c | 65 +++++++++++++++++++ 2 files changed, 85 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr116024-1-fwrapv.c diff --git a/gcc/match.pd b/gcc/match.pd index 46195a603d0..3b973887470 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -9041,7 +9041,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (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))))))) + (plus @0 { build_one_cst (TREE_TYPE (@1)); }))) @2))) +/* For wrapping signed types (-fwrapv), transform like so (using < as example): + C1 - X < C2 + ==> C1 - X = { -INF, -INF + 1, ..., C2 - 1 } + ==> X = { C1 - (-INF), C1 - (-INF + 1), ..., C1 - C2 + 1 } + ==> X - (C1 + 1) = { - (-INF) - 1, - (-INF) - 2, ..., -C2 } + ==> X - (C1 + 1) = { +INF, +INF - 1, ..., -C2 } + ==> X - (C1 + 1) > -C2 - 1 + ==> X - (C1 + 1) > bit_not (C2) + + Similarly, + C1 - X <= C2 ==> X - (C1 + 1) >= bit_not (C2); + C1 - X >= C2 ==> X - (C1 + 1) <= bit_not (C2); + C1 - X > C2 ==> X - (C1 + 1) < bit_not (C2). */ + (if (!TYPE_UNSIGNED (TREE_TYPE (@1)) + && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@1))) + (if (cmp == EQ_EXPR || cmp == NE_EXPR) + (cmp @1 (minus @0 @2)) + (rcmp (minus @1 (plus @0 { build_one_cst (TREE_TYPE (@1)); })) + (bit_not @2)))))))) /* Canonicalizations of BIT_FIELD_REFs. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr116024-1-fwrapv.c b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-1-fwrapv.c new file mode 100644 index 00000000000..24e1abef774 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr116024-1-fwrapv.c @@ -0,0 +1,65 @@ +/* PR tree-optimization/116024 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-forwprop1-details -fwrapv" } */ + +#include + +uint32_t f(void); + +int32_t i2(void) +{ + int32_t l = 10 - (int32_t)f(); + return l <= 20; // f() - 11 >= -21 +} + +int32_t i2a(void) +{ + int32_t l = 10 - (int32_t)f(); + return l < 30; // f() - 11 > -31 +} + +int32_t i2b(void) +{ + int32_t l = 200 - (int32_t)f(); + return l <= 100; // f() - 201 >= -101 +} + +int32_t i2c(void) +{ + int32_t l = 300 - (int32_t)f(); + return l < 100; // f() - 301 > -101 +} + +int32_t i2d(void) +{ + int32_t l = 1000 - (int32_t)f(); + return l >= 2000; // f() - 1001 <= -2001 +} + +int32_t i2e(void) +{ + int32_t l = 1000 - (int32_t)f(); + return l > 3000; // f() - 1001 < -3001 +} + +int32_t i2f(void) +{ + int32_t l = 20000 - (int32_t)f(); + return l >= 10000; // f() - 20001 <= -10001 +} + +int32_t i2g(void) +{ + int32_t l = 30000 - (int32_t)f(); + return l > 10000; // f() - 30001 < -10001 +} + +/* { dg-final { scan-tree-dump-times "Removing dead stmt:.*?- _" 8 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -11.*\n.*>= -21" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -11.*\n.*>= -30" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -201.*\n.*>= -101" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -301.*\n.*>= -100" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -1001.*\n.*< -2000" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -1001.*\n.*< -3001" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -20001.*\n.*< -10000" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to.* \\+ -30001.*\n.*< -10001" 1 "forwprop1" } } */