From patchwork Wed Jul 17 11:28:49 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eikansh Gupta X-Patchwork-Id: 1961593 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=quicinc.com header.i=@quicinc.com header.a=rsa-sha256 header.s=qcppdkim1 header.b=IU5zmxME; 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 4WPDHZ2xTCz1xqc for ; Wed, 17 Jul 2024 21:29:46 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 16D8B385841D for ; Wed, 17 Jul 2024 11:29:44 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0b-0031df01.pphosted.com (mx0b-0031df01.pphosted.com [205.220.180.131]) by sourceware.org (Postfix) with ESMTPS id A67A03858D34 for ; Wed, 17 Jul 2024 11:29:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A67A03858D34 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=quicinc.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=quicinc.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org A67A03858D34 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=205.220.180.131 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721215765; cv=none; b=v/LuDcC820NpfZPRWXhbr8DCdZd5q3SWNEwzxkAU8Zo9GpJLx5vUXCJ/Ftv2YKAbjOV1jUOHwQgNuBm3p6d2v2d5AgfMmBFKguaJODhtqJH/s50qaxaJ3UjvWhfRAhUvF8XqT0K1S0p/lvp6BgKHKXcaeTmS7G53Bvoh/JApqp0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721215765; c=relaxed/simple; bh=94PDrMC4s493K2A4wwsbYJnbYA1jxqrpn7owT7UNldM=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=Govz4YzL02z/wZkeSPMIaWv2jkgSdWzet69H8KeC6waoPERLDVJT2jHbFOQWHLMQJB27ispSh0x1sFRdhbMSuQLzbghmjTBs9lLmRvFfrWE7RBvugsjJJEzIfs0uGed1uv8qP0hJyMUnrbNnz6dxU7P9iK6XCwoWMmDLqwgC+94= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0279872.ppops.net [127.0.0.1]) by mx0a-0031df01.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 46H70p9e023107 for ; Wed, 17 Jul 2024 11:29:23 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=quicinc.com; h= cc:content-type:date:from:message-id:mime-version:subject:to; s= qcppdkim1; bh=W6iWZEulw2ZjiWKjL8ll/a0ff16Rps4biMHkNCVzGPU=; b=IU 5zmxMEAVQDIj6zc4r02JfdabhuCANwROAwZ5GXCkkjJ68LjXYMzPA6UkNzxmYcRn sHMPY5lF56UKZ9wOdKMTKyxWOB9m3lP76k0TN3+4ag+aWrt1uSIf6qxRnBF4of5o 3AlNx9lEjr54h2MysJ8vbQWti+CwuJzRrSZEsh3C70vUOLcggyJwefxB8aaSjn6x 99eDfrhiNxtOpFHWNNKjrVwyxTxFNHft6U3qAovR/QlfexvCQaInx2FRGZszHa8b 9CrjQ7nU+ajT4ZXsgfBuIYiw9byoHZAvirxnkmYGOPOwpJKIXFbTE77DwRU+ZHX5 k4XAEZhmPnKC/ElX3m8w== Received: from nalasppmta01.qualcomm.com (Global_NAT1.qualcomm.com [129.46.96.20]) by mx0a-0031df01.pphosted.com (PPS) with ESMTPS id 40dwfnj6xc-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Wed, 17 Jul 2024 11:29:22 +0000 (GMT) Received: from nalasex01b.na.qualcomm.com (nalasex01b.na.qualcomm.com [10.47.209.197]) by NALASPPMTA01.qualcomm.com (8.17.1.19/8.17.1.19) with ESMTPS id 46HBTLoT007048 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Wed, 17 Jul 2024 11:29:21 GMT Received: from hu-eikagupt-hyd.qualcomm.com (10.80.80.8) by nalasex01b.na.qualcomm.com (10.47.209.197) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.9; Wed, 17 Jul 2024 04:29:20 -0700 From: Eikansh Gupta To: CC: Eikansh Gupta Subject: [PATCH] MATCH: Add simplification for MAX and MIN to match.pd [PR109878] Date: Wed, 17 Jul 2024 16:58:49 +0530 Message-ID: <20240717112849.27656-1-quic_eikagupt@quicinc.com> X-Mailer: git-send-email 2.17.1 MIME-Version: 1.0 X-Originating-IP: [10.80.80.8] X-ClientProxiedBy: nasanex01b.na.qualcomm.com (10.46.141.250) To nalasex01b.na.qualcomm.com (10.47.209.197) X-QCInternal: smtphost X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=5800 signatures=585085 X-Proofpoint-GUID: cRdgq9STWDOQDc_j5c7HeMhDEG84Outt X-Proofpoint-ORIG-GUID: cRdgq9STWDOQDc_j5c7HeMhDEG84Outt X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1039,Hydra:6.0.680,FMLib:17.12.28.16 definitions=2024-07-17_06,2024-07-17_01,2024-05-17_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 impostorscore=0 lowpriorityscore=0 bulkscore=0 malwarescore=0 suspectscore=0 priorityscore=1501 clxscore=1015 spamscore=0 mlxscore=0 phishscore=0 mlxlogscore=858 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.19.0-2407110000 definitions=main-2407170088 X-Spam-Status: No, score=-13.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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 Min and max could be optimized if both operands are defined by (same) variable restricted by an and(&). For signed types, optimization can be done when both constant have same sign bit. The patch also adds optimization for specific case of min/max(a, a&1). This patch adds match pattern for: max (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST1 min (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST0 min (a, a & 1) --> a & 1 max (a, a & 1) --> a PR tree-optimization/109878 gcc/ChangeLog: * match.pd min/max (a & CST0, a & CST1): New pattern. min/max (a, a & 1): New pattern. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr109878.c: New test. * gcc.dg/tree-ssa/pr109878-1.c: New test. * gcc.dg/tree-ssa/pr109878-2.c: New test. * gcc.dg/tree-ssa/pr109878-3.c: New test. Signed-off-by: Eikansh Gupta --- gcc/match.pd | 22 ++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c | 64 ++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c | 31 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c | 26 +++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr109878.c | 64 ++++++++++++++++++++++ 5 files changed, 207 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr109878.c diff --git a/gcc/match.pd b/gcc/match.pd index 24a0bbead3e..029ec0b487f 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -4310,6 +4310,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) @0 @2))) +/* min (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST0 */ +/* max (a & CST0, a & CST1) -> a & CST0 IFF CST0 & CST1 == CST1 */ +/* If signed a, then both the constants should have same sign. */ +(for minmax (min max) + (simplify + (minmax:c (bit_and@3 @0 INTEGER_CST@1) (bit_and@4 @0 INTEGER_CST@2)) + (if (TYPE_UNSIGNED (type) + || ((tree_int_cst_sgn (@1) <= 0) == (tree_int_cst_sgn (@2) <= 0))) + (if ((wi::to_wide (@1) & wi::to_wide (@2)) + == ((minmax == MIN_EXPR) ? wi::to_wide (@1) : wi::to_wide (@2))) + @3)))) + +/* min (a, a & 1) --> a & 1 */ +/* max (a, a & 1) --> a */ +(for minmax (min max) + (simplify + (minmax:c @0 (bit_and@1 @0 integer_onep)) + (if (TYPE_UNSIGNED(type)) + (if (minmax == MIN_EXPR) + @1 + @0)))) + /* Simplify min (&var[off0], &var[off1]) etc. depending on whether the addresses are known to be less, equal or greater. */ (for minmax (min max) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c new file mode 100644 index 00000000000..509e59adea1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-1.c @@ -0,0 +1,64 @@ +/* PR tree-optimization/109878 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ + +/* All the constant pair used here satisfy the condition: + (cst0 & cst1 == cst0) || (cst0 & cst1 == cst1). + If the above condition is true, then MIN_EXPR is not needed. */ +int min_and(int a, int b) { + b = a & 3; + a = a & 1; + if (b < a) + return b; + else + return a; +} + +int min_and1(int a, int b) { + b = a & 3; + a = a & 15; + if (b < a) + return b; + else + return a; +} + +int min_and2(int a, int b) { + b = a & -7; + a = a & -3; + if (b < a) + return b; + else + return a; +} + +int min_and3(int a, int b) { + b = a & -5; + a = a & -13; + if (b < a) + return b; + else + return a; +} + +/* When constants are of opposite signs, the simplification will only + work for unsigned types. */ +unsigned int min_and4(unsigned int a, unsigned int b) { + b = a & 3; + a = a & -5; + if (b < a) + return b; + else + return a; +} + +unsigned int min_and5(unsigned int a, unsigned int b) { + b = a & -3; + a = a & 5; + if (b < a) + return b; + else + return a; +} + +/* { dg-final { scan-tree-dump-not " MIN_EXPR " "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c new file mode 100644 index 00000000000..62846d5d784 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-2.c @@ -0,0 +1,31 @@ +/* PR tree-optimization/109878 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ + +/* The testcases here should not get optimized with the patch. + For constant pair the condition: + (cst0 & cst1 == cst0) || (cst0 & cst1 == cst1) + is false for the constants used here. */ +int max_and(int a, int b) { + + b = a & 3; + a = a & 5; + if (b > a) + return b; + else + return a; +} + +/* The constants in this function satisfy the condition but a is signed. + For signed types both the constants should have same sign. */ +int min_and(int a, int b) { + b = a & 1; + a = a & -3; + if (b < a) + return b; + else + return a; +} + +/* { dg-final { scan-tree-dump " MIN_EXPR " "optimized" } } */ +/* { dg-final { scan-tree-dump " MAX_EXPR " "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c new file mode 100644 index 00000000000..c0b79ae4096 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878-3.c @@ -0,0 +1,26 @@ +/* PR tree-optimization/109878 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ + +/* For unsigned types, min(a, a&1) should be simplified to a&1 and + should not generate MIN_EXPR. */ +unsigned int min_1(unsigned int a, unsigned int b) { + b = a & 1; + if (b < a) + return b; + else + return a; +} + +/* For unsigned types, max(a, a&1) should be simplified to a and + should not generate MAX_EXPR. */ +unsigned int max_1(unsigned int a, unsigned int b) { + b = a & 1; + if (b > a) + return b; + else + return a; +} + +/* { dg-final { scan-tree-dump-not " MIN_EXPR " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " MAX_EXPR " "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr109878.c b/gcc/testsuite/gcc.dg/tree-ssa/pr109878.c new file mode 100644 index 00000000000..6f13bafcf14 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr109878.c @@ -0,0 +1,64 @@ +/* PR tree-optimization/109878 */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ + +/* All the constant pair used here satisfy the condition: + (cst0 & cst1 == cst0) || (cst0 & cst1 == cst1). + If the above condition is true, then MAX_EXPR is not needed. */ +int max_and(int a, int b) { + b = a & 3; + a = a & 1; + if (b > a) + return b; + else + return a; +} + +int max_and1(int a, int b) { + b = a & 3; + a = a & 15; + if (b > a) + return b; + else + return a; +} + +int max_and2(int a, int b) { + b = a & -7; + a = a & -3; + if (b > a) + return b; + else + return a; +} + +int max_and3(int a, int b) { + b = a & -5; + a = a & -13; + if (b > a) + return b; + else + return a; +} + +/* When constants are of opposite signs, the simplification will only + work for unsigned types. */ +unsigned int max_and4(unsigned int a, unsigned int b) { + b = a & 3; + a = a & -5; + if (b > a) + return b; + else + return a; +} + +unsigned int max_and5(unsigned int a, unsigned int b) { + b = a & -3; + a = a & 5; + if (b > a) + return b; + else + return a; +} + +/* { dg-final { scan-tree-dump-not " MAX_EXPR " "optimized" } } */