From patchwork Sat Jun 29 12:19:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ajit Agarwal X-Patchwork-Id: 1954292 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=aSKGpnd4; 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 4WBXlx522Fz1xpP for ; Sun, 30 Jun 2024 12:13:47 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5CBEA38114C9 for ; Sun, 30 Jun 2024 02:13:45 +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 021DD389EC9F for ; Sun, 30 Jun 2024 02:11:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 021DD389EC9F 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 021DD389EC9F 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=1719713522; cv=none; b=XFiEbDuj6lhe3W5F9g3fApHQh+fcuqE0V05n0PCgojmEumvskvbBPTxhRZ+G64e5x7u8hs87LjyUHDukAQcpriLjztJPZ0EcqgHjLDLraOelf5yOncQwUe4nbeIash8HVzhaX2ICT2TSg7hWMFefn2XZPJl0XrOdx1uy2euAooA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1719713522; c=relaxed/simple; bh=atxH/dg/AoiRMH+WtOncqCkhUSWkCafzoQXSwkR+oMM=; h=DKIM-Signature:Message-ID:Date:MIME-Version:To:From:Subject; b=S1gzEs6REiPyYig07kmSDIKANxK2WHTfO8t0eo9sO/16uVtK1Q2SEpfKtYoebZPblZmbKKh4UGNhVV0XCsOic7+FU+Vl3u1XWQQmoDmFauTQae2AilU6kim02YWYfQmabZMM6CwWG1sn1GpbWIJmssFVoRmN/SjIfUI7c53ruck= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from pps.filterd (m0353722.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 45TBumua009294 for ; Sat, 29 Jun 2024 12:19:27 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=P8kxdUkQQ5YpBD90HV6xDGBuOZ oZgl7Mm8irUAeH7oQ=; b=aSKGpnd4rJJ/2lWtKMglMQwIyPaWAhwzDQk3P0bLku xmfDpW0ODEOX9X/Q1uSLJJXbKbPYDcRFvW77e6cnvCEiVT/pCgPlPaify3ay/Pin 1hn34TaEITAwhSyh79inuRaTFp/HiO7Ylra2Kx/caq4apvQ9yywXvu0Wc6WW+iJh t4DJ2BXhZAbforPyOTtrufIsCjHHZFsSE5a3vLfDqopiZqTEFen+WavXZSP1I7HZ vl9CVze4uTg3ePrKHu0S/L0J9bbw6WGO1XwmdYFiY7O75o7rAZ9i9quqH7ggkTat v8Rz9V6LAsxyG1kje2r+loAm3oL968tmOgfRbVVJ/bQA== Received: from ppma12.dal12v.mail.ibm.com (dc.9e.1632.ip4.static.sl-reverse.com [50.22.158.220]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 402fq6r82h-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Sat, 29 Jun 2024 12:19:27 +0000 (GMT) Received: from pps.filterd (ppma12.dal12v.mail.ibm.com [127.0.0.1]) by ppma12.dal12v.mail.ibm.com (8.17.1.19/8.17.1.19) with ESMTP id 45T8QiWu018131 for ; Sat, 29 Jun 2024 12:19:26 GMT Received: from smtprelay02.wdc07v.mail.ibm.com ([172.16.1.69]) by ppma12.dal12v.mail.ibm.com (PPS) with ESMTPS id 3yx8xuwq8u-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for ; Sat, 29 Jun 2024 12:19:26 +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 45TCJNt526280448 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Sat, 29 Jun 2024 12:19:25 GMT Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id B15F85805D for ; Sat, 29 Jun 2024 12:19:23 +0000 (GMT) Received: from smtpav05.wdc07v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 6EF7C58043 for ; Sat, 29 Jun 2024 12:19:22 +0000 (GMT) Received: from [9.43.67.220] (unknown [9.43.67.220]) by smtpav05.wdc07v.mail.ibm.com (Postfix) with ESMTP for ; Sat, 29 Jun 2024 12:19:22 +0000 (GMT) Message-ID: Date: Sat, 29 Jun 2024 17:49:20 +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 factor based on register pressure X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: CVZntSthfFAZCAGXYkJZpyDhfzZPOz9v X-Proofpoint-GUID: CVZntSthfFAZCAGXYkJZpyDhfzZPOz9v 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 adultscore=0 spamscore=0 clxscore=1015 impostorscore=0 phishscore=0 priorityscore=1501 mlxlogscore=999 suspectscore=0 malwarescore=0 mlxscore=0 bulkscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.19.0-2406140001 definitions=main-2406290088 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: 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;