From patchwork Thu Jul 11 08:28:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ajit Agarwal X-Patchwork-Id: 1959139 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=ibm.com header.i=@ibm.com header.a=rsa-sha256 header.s=pp1 header.b=sK1bWX9l; 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 4WKSZf1Fj3z1xqj for ; Thu, 11 Jul 2024 18:29:45 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id F3D3A384A456 for ; Thu, 11 Jul 2024 08:29:43 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0b-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id 835123858D3C for ; Thu, 11 Jul 2024 08:28:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 835123858D3C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=linux.ibm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linux.ibm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 835123858D3C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=148.163.158.5 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720686539; cv=none; b=qnNuIOqfd/09G1hD04ThyVdyrhrh6NxZQtaVfKG0n6sD0KpQX2cp5EAqtiB0qp37IKFT4LCdKFnrkX5st+PleA4f4158F8vK5WSexJEUNxvA5pB/X9L90RKt42mCYn+h/BznruPxNjYwy2+LlcBUuF5MxTTIhjs/k51Tt4Xqg4s= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720686539; c=relaxed/simple; bh=gSSEDKFXLLtxLCASbARy6MDsMXuaVt/yeDPb/bn2OA8=; h=DKIM-Signature:Message-ID:Date:MIME-Version:To:From:Subject; b=NA7dMatrR6w8GAAkm1nai3iE93nZNmMMU4bX8uk/MPS5VOW+4DSaP5lhvnm9oEyFz6uPbcqeDP2eOeMoXmnH2O0Y0FR8wdkDPZWYiBPjMy7pul6B7iZo2gUQbawU+vR5lqMUrz8XmTzlHV6um9XbB9tiVUywNvbICQjZqTPM0L8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0353723.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 46B8OTi7003667 for ; Thu, 11 Jul 2024 08:28:54 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ibm.com; h= message-id:date:mime-version:to:from:subject:content-type :content-transfer-encoding; s=pp1; bh=U+/lQmbLZoujaip35vzt1Lr9i0 CoCOAMbMorIEHxrbE=; b=sK1bWX9lSQFfldbLeUSfLT8hU8YpS5hrsD5GCKGHUt cJE0EQUVv/ceOsKeQ5F/APVKiOFDwT6fUak/uK+IgjQ55Vk/eTYRVpwj+xtmw+xt PJ4g+tRVDpuMwAxXyrwFBWUmE8LEfPlPp+UsYaZz0+DZmq2nLa4OWVpK0+w+FD3C Yv67xif3VhngAItsvZmAlx++B1zJM9lWYiKA1hHdLJe+tlR2ZV+IHmlSG0NYMfxs zTQt8T4A1GGGemy9GaRcTetKMh4tH35mGqRK+MusDg0oeKF7tCHuvM5PT2SjKBtQ rml8WFLYD8mJhCQGXSexoMOWx51p+eJD9YoGH3dBeeQg== Received: from ppma21.wdc07v.mail.ibm.com (5b.69.3da9.ip4.static.sl-reverse.com [169.61.105.91]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 40a86agh3r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 11 Jul 2024 08:28:54 +0000 (GMT) Received: from pps.filterd (ppma21.wdc07v.mail.ibm.com [127.0.0.1]) by ppma21.wdc07v.mail.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 46B8JbXh014043 for ; Thu, 11 Jul 2024 08:28:53 GMT Received: from smtprelay07.wdc07v.mail.ibm.com ([172.16.1.74]) by ppma21.wdc07v.mail.ibm.com (PPS) with ESMTPS id 407h8pyu3y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Thu, 11 Jul 2024 08:28:53 +0000 Received: from smtpav05.wdc07v.mail.ibm.com (smtpav05.wdc07v.mail.ibm.com [10.39.53.232]) by smtprelay07.wdc07v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 46B8Sp9P18088464 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Thu, 11 Jul 2024 08:28:53 GMT Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 76F5258061 for ; Thu, 11 Jul 2024 08:28:51 +0000 (GMT) Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id BDED458059 for ; Thu, 11 Jul 2024 08:28:50 +0000 (GMT) Received: from [9.43.107.234] (unknown [9.43.107.234]) by smtpav05.wdc07v.mail.ibm.com (Postfix) with ESMTP for ; Thu, 11 Jul 2024 08:28:50 +0000 (GMT) Message-ID: <32ad22b3-1fa7-47f6-b8e9-877cea9aee00@linux.ibm.com> Date: Thu, 11 Jul 2024 13:58:48 +0530 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: gcc-patches From: Ajit Agarwal Subject: [Patch, tree-optimization, predcom] Improve unroll factor for predictive commoning X-TM-AS-GCONF: 00 X-Proofpoint-GUID: 2y4y4nGCXPC7CyjtxnGjCCK44dgtkLuB X-Proofpoint-ORIG-GUID: 2y4y4nGCXPC7CyjtxnGjCCK44dgtkLuB 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-11_04,2024-07-10_01,2024-05-17_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 lowpriorityscore=0 malwarescore=0 adultscore=0 suspectscore=0 mlxlogscore=999 impostorscore=0 clxscore=1015 spamscore=0 phishscore=0 bulkscore=0 priorityscore=1501 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.19.0-2406140001 definitions=main-2407110054 X-Spam-Status: No, score=-12.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, 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 Hello All: Unroll factor is determined with max distance across loop iterations. The logic for determining the loop unroll factor is based on data dependency across loop iterations. The max distance across loop iterations is the unrolling factor that helps in predictive commoning. Bootstrapped and regtested on powerpc64-linux-gnu. Thanks & Regards Ajit tree-optimization, predcom: Improve unroll factor for predictive commoning Unroll factor is determined with max distance across loop iterations. The logic for determining the loop unroll factor is based on data dependency across loop iterations. The max distance across loop iterations is the unrolling factor that helps in predictive commoning. 2024-07-11 Ajit Kumar Agarwal gcc/ChangeLog: * tree-predcom.cc: Change in determining unroll factor with data dependence across loop iterations. --- gcc/tree-predcom.cc | 51 ++++++++++++++++++++++++++++++++++----------- 1 file changed, 39 insertions(+), 12 deletions(-) diff --git a/gcc/tree-predcom.cc b/gcc/tree-predcom.cc index 9844fee1e97..029b02f5990 100644 --- a/gcc/tree-predcom.cc +++ b/gcc/tree-predcom.cc @@ -409,6 +409,7 @@ public: /* Perform the predictive commoning optimization for chains, make this public for being called in callback execute_pred_commoning_cbck. */ void execute_pred_commoning (bitmap tmp_vars); + unsigned determine_unroll_factor (const vec &chains); private: /* The pointer to the given loop. */ @@ -2400,13 +2401,46 @@ pcom_worker::execute_pred_commoning_chain (chain_p chain, copies as possible. CHAINS is the list of chains that will be optimized. */ -static unsigned -determine_unroll_factor (const vec &chains) +unsigned +pcom_worker::determine_unroll_factor (const vec &chains) { chain_p chain; - unsigned factor = 1, af, nfactor, i; + unsigned factor = 1, i; unsigned max = param_max_unroll_times; + struct data_dependence_relation *ddr; + unsigned nfactor = 0; + int nzfactor = 0; + + /* Best unroll factor is the maximum distance across loop + iterations. */ + FOR_EACH_VEC_ELT (m_dependences, i, ddr) + { + for (unsigned j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++) + { + lambda_vector vec = DDR_DIST_VECT (ddr, j); + widest_int distance = vec[j]; + unsigned offset = distance.to_uhwi (); + if (offset == 0) + continue; + + int dist = offset - nzfactor; + if (dist == 0) + continue; + if (nfactor == 0) + { + nfactor = offset; + nzfactor = offset; + } + else if (dist <= nzfactor) + nfactor = offset; + + if (nfactor > 0 && nfactor <= max) + factor = nfactor; + } + } + + int max_use = 0; FOR_EACH_VEC_ELT (chains, i, chain) { if (chain->type == CT_INVARIANT) @@ -2427,17 +2461,10 @@ determine_unroll_factor (const vec &chains) continue; } - /* The best unroll factor for this chain is equal to the number of - temporary variables that we create for it. */ - af = chain->length; if (chain->has_max_use_after) - af++; - - nfactor = factor * af / gcd (factor, af); - if (nfactor <= max) - factor = nfactor; + max_use++; } - + factor += max_use; return factor; }