From patchwork Sat Jun 29 12:37:06 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ajit Agarwal X-Patchwork-Id: 1954322 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=n//gi+tJ; 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 4WBmqp1kp7z1xpT for ; Sun, 30 Jun 2024 21:17:58 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 716883858C39 for ; Sun, 30 Jun 2024 11:17:56 +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 2DC3A3858D3C for ; Sun, 30 Jun 2024 11:17:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2DC3A3858D3C 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 2DC3A3858D3C 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=1719746255; cv=none; b=HXqCnXz95ERAT+Rei4XprWFBjQPj/StQ+z4Tc2Qm90M2N2q57nfTfBZx01VuE5Yvj0lDLIQwuh3v3olH+D4zAX37PTrukaZ56+KbztDVPlOxOsmc+3pMqfXZQB7AWZZy1KKF/nDS2Id8Xw/iV7IUqdZF9SMNkSf1QszwoEvqAtE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1719746255; c=relaxed/simple; bh=vGXiwCV+XPJE3WkzBHZ5ppzQKXVtJXzDs2qJ9h8dESU=; h=DKIM-Signature:Message-ID:Date:MIME-Version:To:From:Subject; b=AZjmENdDi9V2rF2Bp/kVGCmA736GaPCrkBpBU6to30dToIazrzYG/KZyD6sB+/mS+b97xhfX8t9x5/z1/EJIVZmeBFheT+sVLpQwKhJqalWT/BH5TKEDNzwspRHKv4Fgl1mSyyT0QdMNaiexK5G9r6cNd/dIcwqI4FFo2XGW/zc= 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 45TCT9pa015977 for ; Sat, 29 Jun 2024 12:37:12 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=E+XAdB04CZEtRc6+UF/5SSbzkD xaAuM3zjk0+SdvIKg=; b=n//gi+tJXtmaVXZMGSX0uw4xiIdBi+4VZvQa16ZkTy RvZeizuNPvCg4GCt1cCy+LYH7luEIZrIaO5W6H/1CfW9zuUtadw/LuOxibcvZEr0 qdjVIC5alw6TBPU/jV3r0/RFWM2fLKvOvWcpYUSg96qUOKye+CSv74PSP8/VGlnN FvHljMO3C14phP7MuwXF2ooVoaIvu0THFjpLkq71cQRUzGHKBrwU3mpdemV3JlaH LBM7PBIDIUycq8k4apnYQApxNwBlP8RmIszpwI4mhJzRoz2GZrCGEI95kyh8CMqR SvOb7IXkBqGRz8Ug0VicC1RvkQPC7Gmkg60TcjXaCk2A== Received: from ppma11.dal12v.mail.ibm.com (db.9e.1632.ip4.static.sl-reverse.com [50.22.158.219]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 402ja600a2-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Sat, 29 Jun 2024 12:37:12 +0000 (GMT) Received: from pps.filterd (ppma11.dal12v.mail.ibm.com [127.0.0.1]) by ppma11.dal12v.mail.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 45TC3qWS000411 for ; Sat, 29 Jun 2024 12:37:11 GMT Received: from smtprelay02.wdc07v.mail.ibm.com ([172.16.1.69]) by ppma11.dal12v.mail.ibm.com (PPS) with ESMTPS id 3yxbn3w3sd-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Sat, 29 Jun 2024 12:37:11 +0000 Received: from smtpav05.wdc07v.mail.ibm.com (smtpav05.wdc07v.mail.ibm.com [10.39.53.232]) by smtprelay02.wdc07v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 45TCb9S327067082 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Sat, 29 Jun 2024 12:37:11 GMT Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 2FE735806B for ; Sat, 29 Jun 2024 12:37:09 +0000 (GMT) Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 21E1558069 for ; Sat, 29 Jun 2024 12:37:08 +0000 (GMT) Received: from [9.43.28.106] (unknown [9.43.28.106]) by smtpav05.wdc07v.mail.ibm.com (Postfix) with ESMTP for ; Sat, 29 Jun 2024 12:37:07 +0000 (GMT) Message-ID: Date: Sat, 29 Jun 2024 18:07:06 +0530 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: gcc-patches From: Ajit Agarwal Subject: [Patch, rtl-optimization, loop-unroll] Loop unroll factor based on register pressure X-TM-AS-GCONF: 00 X-Proofpoint-GUID: XDocrvEmbHAaB8Ci-pf8EjcKu2Gor7sT X-Proofpoint-ORIG-GUID: XDocrvEmbHAaB8Ci-pf8EjcKu2Gor7sT 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-06-29_04,2024-06-28_01,2024-05-17_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 lowpriorityscore=0 priorityscore=1501 malwarescore=0 spamscore=0 mlxlogscore=999 mlxscore=0 bulkscore=0 adultscore=0 phishscore=0 suspectscore=0 impostorscore=0 clxscore=1015 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.19.0-2406140001 definitions=main-2406290090 X-Spam-Status: No, score=-12.2 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: This patch determines unroll factor based on loop register pressure. Unroll factor is quotient of max of available registers in loop by number of liveness. If available registers increases unroll factor increases. Wherein unroll factor decreases if number of liveness increases. Loop unrolling is based on loop variables that determines unroll factor. Loop variables of the loop are the variables that increases register pressure and take advantage of existing register pressure calculation. Available registers are determined by the number of hard registers available for each register class minus max reg pressure of loop for given register class. Bootstrapped and regtested on powerpc64-linux-gnu. Thanks & Regards Ajit rtl-optimization: Loop unroll factor based on register pressure Unroll factor is calculated based on loop register pressure. Unroll factor is quotient of max of available registers in loop by number of liveness. If available registers increases unroll factor increases. Wherein unroll factor decreases if number of liveness increases. Loop unrolling is based on loop variables that determines unroll factor. Loop variables of the loop are the variables that increases register pressure and take advantage of existing register pressure calculation. Available registers are determined by the number of hard registers available for each register class minus max reg pressure of loop for given register class. 2024-06-29 Ajit Kumar Agarwal gcc/ChangeLog: * loop-unroll.cc: Add calculation of register pressure of the loop and use of that to calculate unroll factor. --- gcc/loop-unroll.cc | 331 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 328 insertions(+), 3 deletions(-) diff --git a/gcc/loop-unroll.cc b/gcc/loop-unroll.cc index bfdfe6c2bb7..6936ba7afb9 100644 --- a/gcc/loop-unroll.cc +++ b/gcc/loop-unroll.cc @@ -35,6 +35,11 @@ along with GCC; see the file COPYING3. If not see #include "dojump.h" #include "expr.h" #include "dumpfile.h" +#include "regs.h" +#include "ira.h" +#include "rtl-iter.h" +#include "regset.h" +#include "df.h" /* This pass performs loop unrolling. We only perform this optimization on innermost loops (with single exception) because @@ -65,6 +70,38 @@ along with GCC; see the file COPYING3. If not see showed that this choice may affect performance in order of several %. */ +class loop_data +{ +public: + class loop *outermost_exit; /* The outermost exit of the loop. */ + bool has_call; /* True if the loop contains a call. */ + /* Maximal register pressure inside loop for given register class + (defined only for the pressure classes). */ + int max_reg_pressure[N_REG_CLASSES]; + /* Loop regs referenced and live pseudo-registers. */ + bitmap_head regs_ref; + bitmap_head regs_live; +}; + +#define LOOP_DATA(LOOP) ((class loop_data *) (LOOP)->aux) + +/* Record all regs that are set in any one insn. Communication from + mark_reg_{store,clobber} and global_conflicts. Asm can refer to + all hard-registers. */ +static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS + ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2]; +/* Number of regs stored in the previous array. */ +static int n_regs_set; + +/* Currently processed loop. */ +static class loop *curr_loop; + +/* Registers currently living. */ +static bitmap_head curr_regs_live; + +/* Current reg pressure for each pressure class. */ +static int curr_reg_pressure[N_REG_CLASSES]; + /* Information about induction variables to split. */ struct iv_to_split @@ -272,11 +309,262 @@ decide_unrolling (int flags) } } +/* Return pressure class and number of needed hard registers (through + *NREGS) of register REGNO. */ +static enum reg_class +get_regno_pressure_class (int regno, int *nregs) +{ + if (regno >= FIRST_PSEUDO_REGISTER) + { + enum reg_class pressure_class; + pressure_class = reg_allocno_class (regno); + pressure_class = ira_pressure_class_translate[pressure_class]; + *nregs + = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)]; + return pressure_class; + } + else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno) + && ! TEST_HARD_REG_BIT (eliminable_regset, regno)) + { + *nregs = 1; + return ira_pressure_class_translate[REGNO_REG_CLASS (regno)]; + } + else + { + *nregs = 0; + return NO_REGS; + } +} + +/* Increase (if INCR_P) or decrease current register pressure for + register REGNO. */ +static void +change_pressure (int regno, bool incr_p) +{ + int nregs; + enum reg_class pressure_class; + + pressure_class = get_regno_pressure_class (regno, &nregs); + if (! incr_p) + curr_reg_pressure[pressure_class] -= nregs; + else + { + curr_reg_pressure[pressure_class] += nregs; + if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class] + < curr_reg_pressure[pressure_class]) + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class] + = curr_reg_pressure[pressure_class]; + } +} + +/* Mark REGNO birth. */ +static void +mark_regno_live (int regno) +{ + class loop *loop; + + for (loop = curr_loop; + loop != current_loops->tree_root; + loop = loop_outer (loop)) + bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno); + if (!bitmap_set_bit (&curr_regs_live, regno)) + return; + change_pressure (regno, true); +} + +/* Mark REGNO death. */ +static void +mark_regno_death (int regno) +{ + if (! bitmap_clear_bit (&curr_regs_live, regno)) + return; + change_pressure (regno, false); +} + +/* Mark setting register REG. */ +static void +mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED, + void *data ATTRIBUTE_UNUSED) +{ + if (GET_CODE (reg) == SUBREG) + reg = SUBREG_REG (reg); + + if (! REG_P (reg)) + return; + + regs_set[n_regs_set++] = reg; + + unsigned int end_regno = END_REGNO (reg); + for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno) + mark_regno_live (regno); +} + +/* Mark clobbering register REG. */ +static void +mark_reg_clobber (rtx reg, const_rtx setter, void *data) +{ + if (GET_CODE (setter) == CLOBBER) + mark_reg_store (reg, setter, data); +} + +/* Mark register REG death. */ +static void +mark_reg_death (rtx reg) +{ + unsigned int end_regno = END_REGNO (reg); + for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno) + mark_regno_death (regno); +} + +/* Mark occurrence of registers in X for the current loop. */ +static void +mark_ref_regs (rtx x) +{ + RTX_CODE code; + int i; + const char *fmt; + + if (!x) + return; + + code = GET_CODE (x); + if (code == REG) + { + class loop *loop; + + for (loop = curr_loop; + loop != current_loops->tree_root; + loop = loop_outer (loop)) + bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x)); + return; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + if (fmt[i] == 'e') + mark_ref_regs (XEXP (x, i)); + else if (fmt[i] == 'E') + { + int j; + + for (j = 0; j < XVECLEN (x, i); j++) + mark_ref_regs (XVECEXP (x, i, j)); + } +} + +/* Calculate register pressure in the loops. */ +static void +calculate_loop_reg_pressure (void) +{ + int i; + unsigned int j; + bitmap_iterator bi; + basic_block bb; + rtx_insn *insn; + rtx link; + class loop *parent; + + for (auto loop : loops_list (cfun, 0)) + if (loop->aux == NULL) + { + loop->aux = xcalloc (1, sizeof (class loop_data)); + bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack); + bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack); + } + ira_setup_eliminable_regset (); + bitmap_initialize (&curr_regs_live, ®_obstack); + FOR_EACH_BB_FN (bb, cfun) + { + curr_loop = bb->loop_father; + if (curr_loop == current_loops->tree_root) + continue; + + for (class loop *loop = curr_loop; + loop != current_loops->tree_root; + loop = loop_outer (loop)) + bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb)); + + bitmap_copy (&curr_regs_live, DF_LR_IN (bb)); + for (i = 0; i < ira_pressure_classes_num; i++) + curr_reg_pressure[ira_pressure_classes[i]] = 0; + EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi) + change_pressure (j, true); + + FOR_BB_INSNS (bb, insn) + { + if (! NONDEBUG_INSN_P (insn)) + continue; + + mark_ref_regs (PATTERN (insn)); + n_regs_set = 0; + note_stores (insn, mark_reg_clobber, NULL); + + /* Mark any registers dead after INSN as dead now. */ + + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == REG_DEAD) + mark_reg_death (XEXP (link, 0)); + + /* Mark any registers set in INSN as live, + and mark them as conflicting with all other live regs. + Clobbers are processed again, so they conflict with + the registers that are set. */ + + note_stores (insn, mark_reg_store, NULL); + + if (AUTO_INC_DEC) + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == REG_INC) + mark_reg_store (XEXP (link, 0), NULL_RTX, NULL); + + while (n_regs_set-- > 0) + { + rtx note = find_regno_note (insn, REG_UNUSED, + REGNO (regs_set[n_regs_set])); + if (! note) + continue; + + mark_reg_death (XEXP (note, 0)); + } + } + } + bitmap_release (&curr_regs_live); + if (dump_file == NULL) + return; + for (auto loop : loops_list (cfun, 0)) + { + parent = loop_outer (loop); + fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n", + loop->num, (parent == NULL ? -1 : parent->num), + loop->header->index, loop_depth (loop)); + fprintf (dump_file, "\n ref. regnos:"); + EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi) + fprintf (dump_file, " %d", j); + fprintf (dump_file, "\n live regnos:"); + EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi) + fprintf (dump_file, " %d", j); + fprintf (dump_file, "\n Pressure:"); + for (i = 0; (int) i < ira_pressure_classes_num; i++) + { + enum reg_class pressure_class; + + pressure_class = ira_pressure_classes[i]; + if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0) + continue; + fprintf (dump_file, " %s=%d", reg_class_names[pressure_class], + LOOP_DATA (loop)->max_reg_pressure[pressure_class]); + } + fprintf (dump_file, "\n"); + } +} + /* Unroll LOOPS. */ void unroll_loops (int flags) { bool changed = false; + df_analyze (); + calculate_loop_reg_pressure (); /* Now decide rest of unrolling. */ decide_unrolling (flags); @@ -339,6 +627,40 @@ loop_exit_at_end_p (class loop *loop) return true; } +/* Determine unroll factor for a given LOOP. Unroll factor + is calculated with quotient of maximum number of available registers + with number of liveness. + If available registers is more unrolling factor is more. And if + number of liveness is more unroll factor is less. */ +int +determine_unroll_factor (class loop *loop) +{ + int nunroll = 0; + int avail = 0; + int max_pressure = 0; + int num_live = 0; + for (int i = 0; (int) i < ira_pressure_classes_num; i++) + { + enum reg_class pressure_class; + + pressure_class = ira_pressure_classes[i]; + max_pressure = LOOP_DATA (loop)->max_reg_pressure[pressure_class]; + if (max_pressure == 0) + continue; + + if (((ira_class_hard_regs_num[pressure_class] - max_pressure) > avail) + || avail == 0) + avail = ira_class_hard_regs_num[pressure_class] - max_pressure; + + num_live++; + } + + if (avail > 0 && num_live > 0) + nunroll = avail / num_live; + + return nunroll; +} + /* Decide whether to unroll LOOP iterating constant number of times and how much. */ @@ -357,10 +679,11 @@ decide_unroll_constant_iterations (class loop *loop, int flags) dump_printf (MSG_NOTE, "considering unrolling loop with constant " "number of iterations\n"); - /* nunroll = total number of copies of the original loop body in unrolled loop (i.e. if it is 2, we have to duplicate loop body once). */ - nunroll = param_max_unrolled_insns / loop->ninsns; + nunroll = determine_unroll_factor (loop); + if (nunroll <= 0) + nunroll = param_max_unrolled_insns / loop->ninsns; nunroll_by_av = param_max_average_unrolled_insns / loop->av_ninsns; if (nunroll > nunroll_by_av) @@ -678,7 +1001,9 @@ decide_unroll_runtime_iterations (class loop *loop, int flags) /* nunroll = total number of copies of the original loop body in unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */ - nunroll = param_max_unrolled_insns / loop->ninsns; + nunroll = determine_unroll_factor (loop); + if (nunroll <= 0) + nunroll = param_max_unrolled_insns / loop->ninsns; nunroll_by_av = param_max_average_unrolled_insns / loop->av_ninsns; if (nunroll > nunroll_by_av) nunroll = nunroll_by_av;