From patchwork Wed Aug 5 10:09:04 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Henrique Barboza X-Patchwork-Id: 140642 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from vm01.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 44DEE4B99F53 for ; Wed, 5 Aug 2026 10:09:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 44DEE4B99F53 Authentication-Results: sourceware.org; dkim=pass (2048-bit key, unprotected) header.d=qualcomm.com header.i=@qualcomm.com header.a=rsa-sha256 header.s=qcppdkim1 header.b=ew7eidPg; dkim=pass (2048-bit key, unprotected) header.d=oss.qualcomm.com header.i=@oss.qualcomm.com header.a=rsa-sha256 header.s=google header.b=hsSiFmW7 X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-0031df01.pphosted.com (mx0a-0031df01.pphosted.com [205.220.168.131]) by sourceware.org (Postfix) with ESMTPS id 78E974BA2E1F for ; Wed, 5 Aug 2026 10:09:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 78E974BA2E1F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=oss.qualcomm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=oss.qualcomm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 78E974BA2E1F Authentication-Results: sourceware.org; arc=none smtp.remote-ip=205.220.168.131 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1785924554; cv=none; b=oRb2b8wdLU4LqvEuDnjBF1XkWm2jkcy5bca1hSnEfM8wPYvRQ7fPGZd99PoVNx8qzxAjqHl+Ftd+Ngb7N2yEP+zBUXl1/rzdGwkaU5fZtW2S/Kfq2S9eqwmpgUMsfFEvxoPgzixv8739/5izuUReAfUc7AVoec60gp7VPYrXE3E= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1785924554; c=relaxed/simple; bh=yBOB3AH36KUgfH7b2g8pxJfC/y1Va3X+M0Xz9y0oDHM=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=rxf6cPZrKojkcdZeGYW0NXV79oHC6Osl3Pywxpcrx1pFMnepnvMksRdeXGQI7PaHRjsWQf7Q8PWOHq3SYlDHcGW5kv7ZNp7KZSiexDu9mZDAAio/Z1td1z+tlCQdpVMTn6w2BXURXAn5TTXek8TYGSl4X88Ie2nDy6ns7PEO/vk= ARC-Authentication-Results: i=1; sourceware.org; dkim=pass (2048-bit key, unprotected) header.d=qualcomm.com header.i=@qualcomm.com header.a=rsa-sha256 header.s=qcppdkim1 header.b=ew7eidPg; dkim=pass (2048-bit key, unprotected) header.d=oss.qualcomm.com header.i=@oss.qualcomm.com header.a=rsa-sha256 header.s=google header.b=hsSiFmW7 DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 78E974BA2E1F Received: from pps.filterd (m0279864.ppops.net [127.0.0.1]) by mx0a-0031df01.pphosted.com (8.18.1.11/8.18.1.11) with ESMTP id 6758dZbj1713211 for ; Wed, 5 Aug 2026 10:09:13 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=qualcomm.com; h= cc:content-transfer-encoding:date:from:message-id:mime-version :subject:to; s=qcppdkim1; bh=/JBiKJg5Pg6rGFeWMnxaV8mCreouPiv3Rdc m2bgNtrs=; b=ew7eidPggVWYHyAq7WW4SaE6OOE7Sv00ZhISmna/CkAv+imaeZn UA5eLe0PkhZYMRcPIX9mqh/sC57RqZOSNhwwyEqoWEnXZqtANiN2ltZV7evtVXdu YMUNmJ8mg6A2g1N10jk+mnX++dRy90NjngBm91N12KPYkTGbkDqCsY22v1yyBYD7 7inMTrwXJQpMisPskaqNN2g0ZkNFCcaOuHo4LCP29OCZxNNuKR0O7DfeBsHWfs59 WyDg/9E2tRCkwhfSF4v0cVLLZZIsLP4gtljunSbxZ5NWgHbqPqp08i2ircd9C/wU Aj/PFVEAAxmwRqOxRCqrWn+pPiiU0WQTwpg== Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by mx0a-0031df01.pphosted.com (PPS) with ESMTPS id 4fuwbqsk97-1 (version=TLSv1.3 cipher=TLS_AES_128_GCM_SHA256 bits=128 verify=NOT) for ; Wed, 05 Aug 2026 10:09:13 +0000 (GMT) Received: by mail-qv1-f70.google.com with SMTP id 6a1803df08f44-9087fb77109so6850876d6.3 for ; Wed, 05 Aug 2026 03:09:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oss.qualcomm.com; s=google; t=1785924552; x=1786529352; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to:content-type; bh=/JBiKJg5Pg6rGFeWMnxaV8mCreouPiv3Rdcm2bgNtrs=; b=hsSiFmW7M3sE2wpcO2pPwbi/ky7tC/ksFNLuCzsjb2FhJbAdHP2b5pSVUdZP3Ffv2I gLrBa9xc+oCt+1PvVG7n3Be2x2OfcE9J4GquZwJeqKCqIqNuX+nj+iBYyA/7zGMfWxt9 NSMu29zWm34TAcpXZMgfhae57VVrUAlIy5s+1MlEHjZkrWe3a8tw3ZIFiksrpsBoaTeh nEjWnANQha8xw4kJikaJ9EsG6TTsFfroTjNFThmVbwD3Cbpt2MnaJl6RDmhKVdRg6mJ6 e4E2nyp8TqQgZ3BaF75Lqto+ORZS1n8Dys2nLCHd2/F3pM8hCGj1Fn5e3+bEn+LtPRd1 totA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1785924552; x=1786529352; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to:content-type; bh=/JBiKJg5Pg6rGFeWMnxaV8mCreouPiv3Rdcm2bgNtrs=; b=YiFiBAl329yE1eal5ZMiL2UDyjczHxO36jUqDslEls7enyi8hvX+VWIyUNC6kX/9q8 yNM8gZNTHkxrDYEeImlwL3lx6C21v+OdhzNMF31OZnHwksjHQjrcih08DX8yiPNnfBU+ WrZ5H3RNR2r0fg7j0Kpj/48JRgZQ2bls2ZoyDF+CFUZnfWtIW5wMnQWqX5g2jqg3KASo vR2d0XPtkfZmzbKqSjwSqg8/opQcXzq1ftCmA6KpN69EaqdHQ9/WI9vzFrEVkejESmpr 1Uj/8eMJQakc40bJfQMAWmc/Ilb8xxUpaPNZr/QIsx3aB4U1wKIMOoybpx986Aj82Lfd 4rBw== X-Gm-Message-State: AOJu0Yyuw7ncYWnsSWcLO3o8z7RT/4dk9NwxTPV3hJP/a++JlmvLobaj P2loNjp9gi32hcgff1f1VHkaCJTPZ7MkjNsd4Xf56gVSWr1uAd16c0YWas3vaYQolhkHNfIkSWh MyoDXd+kylISzHE+h1GzkESWQhCN2TY64I5zgqXXAKkXS0Dkyr7PNHknyZVBTlS18O5ip X-Gm-Gg: AR+sD10lRmMVFBnIuxDPsIAmpUXroKWi2t6a5qbhK+7XPP+7rxLetdTyZCSOuGPw4da kqppBK6RKrkIJxCYxw7xTQFzPtFnL5PQCA4TvVYgBVLwacN85t6i3VXJrP3KvG2tz7fvhH0gFVS JedraFtmj/W0YFgtAaQ/mUcDF5ty8qfXt/mGf/4LPaFhcLeP9446JxitboCQRqZofPb3DLHkj27 P9TkadLFVwGugn6BmQq4DvEhmCsUoET0tNUFii1v3H9sXkEQ7BRrXZ+ElGU43vD3cObsI8WG1s+ 43ywszU4dXUU1iUPiVD3rNKhs7tVVrWF+zsEkm43GBGWRgaP7M3UlHuUHloGgnaupeBiG/G/nNR VpuEyu83qrstUiAGXWaHWpgJcNMprwdFy5NW/Ww== X-Received: by 2002:ad4:4eeb:0:b0:908:7fce:f111 with SMTP id 6a1803df08f44-90881098aecmr61823586d6.6.1785924551866; Wed, 05 Aug 2026 03:09:11 -0700 (PDT) X-Received: by 2002:ad4:4eeb:0:b0:908:7fce:f111 with SMTP id 6a1803df08f44-90881098aecmr61822616d6.6.1785924551268; Wed, 05 Aug 2026 03:09:11 -0700 (PDT) Received: from QCOM-UWl2o8bcGT.qualcomm.com ([187.11.154.152]) by smtp.gmail.com with ESMTPSA id 6a1803df08f44-9087ffe0f93sm22339366d6.21.2026.08.05.03.09.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 05 Aug 2026 03:09:10 -0700 (PDT) From: Daniel Barboza To: gcc-patches@gcc.gnu.org Cc: jeffrey.law@oss.qualcomm.com, andrew.pinski@oss.qualcomm.com, Daniel Barboza Subject: [PATCH v4] forwprop: add simplify_phi_result_op() [PR101179] Date: Wed, 5 Aug 2026 07:09:04 -0300 Message-ID: <20260805100905.2858219-1-daniel.barboza@oss.qualcomm.com> X-Mailer: git-send-email 2.43.0 MIME-Version: 1.0 X-Proofpoint-ORIG-GUID: oDvt5-fPgoa0rTr6iDRlz6o7qgq5gIVp X-Authority-Analysis: v=2.4 cv=B+uJFutM c=1 sm=1 tr=0 ts=6a730bc9 cx=c_pps a=oc9J++0uMp73DTRD5QyR2A==:117 a=iMfxv9gflPUPBcmW7/Gq5Q==:17 a=Sv0fKeRqtYgA:10 a=s4-Qcg_JpJYA:10 a=VkNPw1HP01LnGYTKEx00:22 a=u7WPNUs3qKkmUXheDGA7:22 a=DJpcGTmdVt4CTyJn9g5Z:22 a=mDV3o1hIAAAA:8 a=Y8zQBDNnXKd2mwRfF8EA:9 a=iYH6xdkBrDN1Jqds4HTS:22 X-Proofpoint-GUID: oDvt5-fPgoa0rTr6iDRlz6o7qgq5gIVp X-Proofpoint-Spam-Info: AW1haW4tMjYwODA1MDA4MCBTYWx0ZWRfX1pezDcfdjAHO /y3hGoglEk1sidNLMqlGp4UnVZRVeQDW+xO8bBzxRMWIbx9yOP8/MyVTfX9eImC1rLKoZK2AqjB Yo2rM264RoNNRnMEHJnz6EmXYen5KLk= X-Proofpoint-Spam-Details-Enc: AW1haW4tMjYwODA1MDA4MCBTYWx0ZWRfX3cNo0nqKmCXC Sm6sgu45bJXL8hYSFNb9p0LB+pBeIFxtQzYezBbBOiiPsKYlcgGLsvP9rLOKwW4QicPnPfOULbX bPItFr+tRd+H1GvJFd5pjNlmTqRCco94x7NYL0oDcVKXyuMeKzSDo7HQG5O4PyOUzCFJxZuNpIz ljaYBtlW/bS2CYSMOv+PCDzk7rLPA9pnteD47dBNAJJ8rfgOJU3MvzsjIzWRqo9THcEP1w/b6pv 1QiKalo1WAtjEy6WxvSpPPbOECqJCwxnJfe+hBs0ACKhlrZ68Dt37tzYqXungpUmNlPnnAPxo4n rSzG9cQs3WeB/WTj3py3tPx+DCBYRGz4vTnHen2rLS/f8kP5GaKQIjBAk3r653EN/DN1F23p6sP NqqlbbMJzsocikOJyKrbU3cViO13nQMvMDRSaSv9iRqMCbFYrIjV+P+pEivy/8TK7Nn9+62+uuO Zd4Mj9DGN49zECW7fLg== X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1176,Hydra:6.1.134,FMLib:17.12.100.49 definitions=2026-08-05_03,2026-08-04_02,2025-10-01_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 clxscore=1015 spamscore=0 lowpriorityscore=0 bulkscore=0 phishscore=0 priorityscore=1501 suspectscore=0 malwarescore=0 adultscore=0 impostorscore=0 classifier=typeunknown authscore=0 authtc= authcc= route=outbound adjust=0 reason=mlx scancount=1 engine=8.22.0-2606150000 definitions=main-2608050080 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, KAM_SHORT, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_LOW, RCVD_IN_PBL, SPF_HELO_NONE, SPF_PASS, TXREP shortcircuit=no autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on 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~patchwork=sourceware.org@gcc.gnu.org This new forwprop step is my attempt to implement Richi's suggestions from v1 of this work [1] where he suggested to push things out of match.pd. The idea is to simplify DIV/MOD into RSHIFT/BIT_AND ops in which the divisor are pow2 integers in a PHI. E.g.: phi_var = PHI <16,4> _x = _y % phi_var Can be turned into: phi_var = PHI <15,3> _x = _y & phi_var As long as we know that _y is a positive number or '_x' is a single use with a zero comparison. Most of 101179 use cases are solved by this change. PHI with 2+ args are supported as long as every phi_arg meets the criteria. Boostrapped and regression tested with x86_64, aarch64 and riscv64. [1] https://gcc.gnu.org/pipermail/gcc-patches/2026-May/716303.html PR tree-optimization/101179 gcc/ChangeLog: * tree-ssa-forwprop.cc (simplify_phi_result_op): New phiopt step where MOD/DIV ops with pow2 divisors can be simplified to BIT_AND/RSHIFT. (pass_forwprop::execute): Call simplify_phi_result_op. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr101179.c: New test. --- Changes from v3: - handle PHIs with multiple args; - use as_a; - create a new PHI instead of editing the existing one; - move rhs1 check and tree_code check up, before the PHI checks; - use wi::to_wide and wide_int_to_tree to skip the tree_fits_uhwi check; - v3 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-July/725937.html gcc/testsuite/gcc.dg/tree-ssa/pr101179.c | 77 +++++++++++++++ gcc/tree-ssa-forwprop.cc | 118 +++++++++++++++++++++++ 2 files changed, 195 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr101179.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c b/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c new file mode 100644 index 00000000000..5f996e7260d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr101179.c @@ -0,0 +1,77 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-phiopt1" } */ + +typedef unsigned uint; + +int f1 (int y, _Bool x) +{ + return y % (x ? 16 : 4) == 0; +} + +/* We can't turn this into bit_and because there's no + guarantee 'y' is a positive val. */ +int f2 (int y, _Bool x) +{ + return y % (x ? 16 : 4); +} + +uint f3 (uint y, _Bool x) +{ + return y % (x ? 16 : 4) == 0; +} + +uint f4 (uint y, _Bool x) +{ + return y % (x ? 16 : 4); +} + +int f5 (int y, int x) +{ + int op = 64; + + if (x > 40) op = 32; + else if (x > 20) op = 16; + else if (x > 10) op = 4; + + return y % op == 0; +} + +int g1 (int y, _Bool x) +{ + return y / (x ? 16 : 4) == 0; +} + +/* We can't turn this into rshift because there's no + guarantee 'y' is a positive val. */ +int g2 (int y, _Bool x) +{ + return y / (x ? 16 : 4); +} + +/* This will be turned by match.pd into: + "(X / Y) == 0 -> X < Y if X, Y are unsigned." + We're adding it here for completioness. */ +uint g3 (uint y, _Bool x) +{ + return y / (x ? 16 : 4) == 0; +} + +uint g4 (uint y, _Bool x) +{ + return y / (x ? 16 : 4); +} + +int g5 (int y, int x) +{ + int op = 64; + + if (x > 40) op = 32; + else if (x > 20) op = 16; + else if (x > 10) op = 4; + + return y / op == 0; +} +/* { dg-final { scan-tree-dump-times " \& " 4 "phiopt1" } } */ +/* { dg-final { scan-tree-dump-times " \% " 1 "phiopt1" } } */ +/* { dg-final { scan-tree-dump-times " >> " 3 "phiopt1" } } */ +/* { dg-final { scan-tree-dump-times " \\/ " 1 "phiopt1" } } */ diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index 75f06c6ba41..ba1ca37027f 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3623,6 +3623,116 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) return true; } +/* Verify if we have the following structure: + + iftmp1 = PHI + _ssa1 = _ssa2 MOD|DIV iftmp1; + _ssa3 = _ssa1 EQ|NE 0; + + And, as long as "_ssa2" is either known to be positive or + "_ssa1" is single use in a zero comparison, change the PHI + args and "_ssa1" stmt to a cheaper alternative. + + For MOD: + + iftmp1 = PHI <(pow2a - 1), (pow2b - 1), (pow2c - 1), ...> + _ssa1 = _ssa2 & iftmp1; + + For DIV: + + iftmp1 = PHI + _ssa1 = _ssa2 >> iftmp1; */ +static bool +simplify_phi_result_op (gimple *stmt, tree_code code) +{ + tree_code new_code; + switch (code) + { + case TRUNC_MOD_EXPR: + case CEIL_MOD_EXPR: + case FLOOR_MOD_EXPR: + case ROUND_MOD_EXPR: + new_code = BIT_AND_EXPR; + break; + case TRUNC_DIV_EXPR: + case CEIL_DIV_EXPR: + case FLOOR_DIV_EXPR: + case ROUND_DIV_EXPR: + new_code = RSHIFT_EXPR; + break; + + default: + return false; + } + + /* If rhs1 is a known positive value we can always apply these + simplification. Otherwise see if lhs is single_use with a + EQ|NE 0 cmp. */ + tree rhs1 = gimple_assign_rhs1 (stmt); + if (!tree_expr_nonnegative_p (rhs1)) + { + gimple *cmp_stmt; + use_operand_p use_p; + + if (!single_imm_use (gimple_assign_lhs (stmt), &use_p, &cmp_stmt) + || !cmp_stmt + || !is_gimple_assign (cmp_stmt)) + return false; + + if (!(gimple_assign_rhs_code (cmp_stmt) == NE_EXPR + || gimple_assign_rhs_code (cmp_stmt) == EQ_EXPR)) + return false; + + if (!integer_zerop (gimple_assign_rhs2 (cmp_stmt))) + return false; + } + + gphi *phi = as_a (SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt))); + + for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) + if (!integer_pow2p (gimple_phi_arg_def (phi, i))) + return false; + + tree type = TREE_TYPE (gimple_phi_result (phi)); + tree new_phires = make_ssa_name (type); + gphi *new_phi = create_phi_node (new_phires, phi->bb); + + for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) + { + tree phi_arg = gimple_phi_arg_def (phi, i); + tree arg; + + if (new_code == RSHIFT_EXPR) + arg = wide_int_to_tree (type, wi::exact_log2 (wi::to_wide (phi_arg))); + else + arg = wide_int_to_tree (type, wi::to_wide (phi_arg) - 1); + + SET_PHI_ARG_DEF (new_phi, i, arg); + } + + /* Add a gimple_convert to integer_type_node for new_phires + since it might be a long long which we want to convert + into an integer or a bit_int that we want to convert into + an integer. */ + gimple_stmt_iterator gsi; + if (new_code == RSHIFT_EXPR) + { + gsi = gsi_for_stmt (stmt); + new_phires = gimple_convert (&gsi, true, GSI_SAME_STMT, + gimple_location (stmt), + integer_type_node, new_phires); + } + + gimple_assign_set_rhs1 (stmt, rhs1); + gimple_assign_set_rhs2 (stmt, new_phires); + gimple_assign_set_rhs_code (stmt, new_code); + update_stmt (stmt); + + gsi = gsi_for_phi (phi); + gsi_remove (&gsi, true); + + return true; +} /* Determine whether applying the 2 permutations (mask1 then mask2) gives back one of the input. */ @@ -5894,6 +6004,14 @@ pass_forwprop::execute (function *fun) changed |= simplify_vector_constructor (&gsi); else if (code == ARRAY_REF) changed |= simplify_count_zeroes (&gsi); + else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS + && TREE_CODE ( + gimple_assign_rhs2 (stmt)) == SSA_NAME + && has_single_use (gimple_assign_rhs2 (stmt)) + && SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt)) + && is_a (SSA_NAME_DEF_STMT ( + gimple_assign_rhs2 (stmt)))) + changed |= simplify_phi_result_op (stmt, code); break; }