From patchwork Thu Aug 25 13:51:16 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernd Schmidt X-Patchwork-Id: 111574 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 66EB7B6F7E for ; Thu, 25 Aug 2011 23:53:13 +1000 (EST) Received: (qmail 29538 invoked by alias); 25 Aug 2011 13:53:09 -0000 Received: (qmail 29515 invoked by uid 22791); 25 Aug 2011 13:53:07 -0000 X-SWARE-Spam-Status: No, hits=-2.0 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 25 Aug 2011 13:52:50 +0000 Received: (qmail 8942 invoked from network); 25 Aug 2011 13:52:47 -0000 Received: from unknown (HELO ?84.152.163.45?) (bernds@127.0.0.2) by mail.codesourcery.com with ESMTPA; 25 Aug 2011 13:52:47 -0000 Message-ID: <4E565354.3080705@codesourcery.com> Date: Thu, 25 Aug 2011 15:51:16 +0200 From: Bernd Schmidt User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.18) Gecko/20110801 Lightning/1.0b3pre Thunderbird/3.1.11 MIME-Version: 1.0 To: GCC Patches , richard.sandiford@linaro.org Subject: Re: Rename across basic block boundaries References: <4E00A296.4000306@codesourcery.com> In-Reply-To: Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On 08/24/11 13:12, Richard Sandiford wrote: > Sorry, I'm find this a bit tough to review. Could you provide some > overview comments somewhere to say what the new algorithm is? Will resubmit. To make the patch smaller next time, I've committed the following as obvious (BSRT i686-linux). Bernd Index: gcc/ChangeLog =================================================================== --- gcc/ChangeLog (revision 178062) +++ gcc/ChangeLog (working copy) @@ -1,5 +1,12 @@ +2011-08-25 Bernd Schmidt + + * regrename.c (scan_rtx_reg, scan_rtx_address, build_def_use, + dump_def_use_chain): Don't declare. + (mark_conflict, create_new_chain): Move before users. + (regrename_optimize): Move to near end of file. + 2011-08-25 Georg-Johann Lay - + * config/avr/avr.c (STR_PREFIX_P): New Define. (avr_asm_declare_function_name): Use it. (avr_asm_named_section): Use it. Index: gcc/regrename.c =================================================================== --- gcc/regrename.c (revision 178057) +++ gcc/regrename.c (working copy) @@ -138,14 +138,8 @@ static int this_tick = 0; static struct obstack rename_obstack; static void do_replace (struct du_head *, int); -static void scan_rtx_reg (rtx, rtx *, enum reg_class, - enum scan_actions, enum op_type); -static void scan_rtx_address (rtx, rtx *, enum reg_class, - enum scan_actions, enum machine_mode); static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions, enum op_type); -static struct du_head *build_def_use (basic_block); -static void dump_def_use_chain (struct du_head *); typedef struct du_head *du_head_p; DEF_VEC_P (du_head_p); @@ -204,6 +198,84 @@ free_chain_data (void) VEC_free (du_head_p, heap, id_to_chain); } +/* Walk all chains starting with CHAINS and record that they conflict with + another chain whose id is ID. */ + +static void +mark_conflict (struct du_head *chains, unsigned id) +{ + while (chains) + { + bitmap_set_bit (&chains->conflicts, id); + chains = chains->next_chain; + } +} + +/* Create a new chain for THIS_NREGS registers starting at THIS_REGNO, + and record its occurrence in *LOC, which is being written to in INSN. + This access requires a register of class CL. */ + +static void +create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc, + rtx insn, enum reg_class cl) +{ + struct du_head *head = XOBNEW (&rename_obstack, struct du_head); + struct du_chain *this_du; + int nregs; + + head->next_chain = open_chains; + open_chains = head; + head->regno = this_regno; + head->nregs = this_nregs; + head->need_caller_save_reg = 0; + head->cannot_rename = 0; + + VEC_safe_push (du_head_p, heap, id_to_chain, head); + head->id = current_id++; + + bitmap_initialize (&head->conflicts, &bitmap_default_obstack); + bitmap_copy (&head->conflicts, &open_chains_set); + mark_conflict (open_chains, head->id); + + /* Since we're tracking this as a chain now, remove it from the + list of conflicting live hard registers and track it in + live_in_chains instead. */ + nregs = head->nregs; + while (nregs-- > 0) + { + SET_HARD_REG_BIT (live_in_chains, head->regno + nregs); + CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs); + } + + COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs); + bitmap_set_bit (&open_chains_set, head->id); + + open_chains = head; + + if (dump_file) + { + fprintf (dump_file, "Creating chain %s (%d)", + reg_names[head->regno], head->id); + if (insn != NULL_RTX) + fprintf (dump_file, " at insn %d", INSN_UID (insn)); + fprintf (dump_file, "\n"); + } + + if (insn == NULL_RTX) + { + head->first = head->last = NULL; + return; + } + + this_du = XOBNEW (&rename_obstack, struct du_chain); + head->first = head->last = this_du; + + this_du->next_use = 0; + this_du->loc = loc; + this_du->insn = insn; + this_du->cl = cl; +} + /* For a def-use chain HEAD, find which registers overlap its lifetime and set the corresponding bits in *PSET. */ @@ -416,52 +488,6 @@ rename_chains (du_head_p all_chains) } } -/* Perform register renaming on the current function. */ - -static unsigned int -regrename_optimize (void) -{ - basic_block bb; - char *first_obj; - - df_set_flags (DF_LR_RUN_DCE); - df_note_add_problem (); - df_analyze (); - df_set_flags (DF_DEFER_INSN_RESCAN); - - memset (tick, 0, sizeof tick); - - gcc_obstack_init (&rename_obstack); - first_obj = XOBNEWVAR (&rename_obstack, char, 0); - - FOR_EACH_BB (bb) - { - struct du_head *all_chains = 0; - - id_to_chain = VEC_alloc (du_head_p, heap, 0); - - if (dump_file) - fprintf (dump_file, "\nBasic block %d:\n", bb->index); - - all_chains = build_def_use (bb); - - if (dump_file) - dump_def_use_chain (all_chains); - - rename_chains (all_chains); - - free_chain_data (); - obstack_free (&rename_obstack, first_obj); - } - - obstack_free (&rename_obstack, NULL); - - if (dump_file) - fputc ('\n', dump_file); - - return 0; -} - static void do_replace (struct du_head *head, int reg) { @@ -492,19 +518,6 @@ do_replace (struct du_head *head, int re } -/* Walk all chains starting with CHAINS and record that they conflict with - another chain whose id is ID. */ - -static void -mark_conflict (struct du_head *chains, unsigned id) -{ - while (chains) - { - bitmap_set_bit (&chains->conflicts, id); - chains = chains->next_chain; - } -} - /* True if we found a register with a size mismatch, which means that we can't track its lifetime accurately. If so, we abort the current block without renaming. */ @@ -570,71 +583,6 @@ note_sets_clobbers (rtx x, const_rtx set add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x)); } -/* Create a new chain for THIS_NREGS registers starting at THIS_REGNO, - and record its occurrence in *LOC, which is being written to in INSN. - This access requires a register of class CL. */ - -static void -create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc, - rtx insn, enum reg_class cl) -{ - struct du_head *head = XOBNEW (&rename_obstack, struct du_head); - struct du_chain *this_du; - int nregs; - - head->next_chain = open_chains; - open_chains = head; - head->regno = this_regno; - head->nregs = this_nregs; - head->need_caller_save_reg = 0; - head->cannot_rename = 0; - - VEC_safe_push (du_head_p, heap, id_to_chain, head); - head->id = current_id++; - - bitmap_initialize (&head->conflicts, &bitmap_default_obstack); - bitmap_copy (&head->conflicts, &open_chains_set); - mark_conflict (open_chains, head->id); - - /* Since we're tracking this as a chain now, remove it from the - list of conflicting live hard registers and track it in - live_in_chains instead. */ - nregs = head->nregs; - while (nregs-- > 0) - { - SET_HARD_REG_BIT (live_in_chains, head->regno + nregs); - CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs); - } - - COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs); - bitmap_set_bit (&open_chains_set, head->id); - - open_chains = head; - - if (dump_file) - { - fprintf (dump_file, "Creating chain %s (%d)", - reg_names[head->regno], head->id); - if (insn != NULL_RTX) - fprintf (dump_file, " at insn %d", INSN_UID (insn)); - fprintf (dump_file, "\n"); - } - - if (insn == NULL_RTX) - { - head->first = head->last = NULL; - return; - } - - this_du = XOBNEW (&rename_obstack, struct du_chain); - head->first = head->last = this_du; - - this_du->next_use = 0; - this_du->loc = loc; - this_du->insn = insn; - this_du->cl = cl; -} - static void scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action, enum op_type type) @@ -1400,6 +1348,52 @@ build_def_use (basic_block bb) return closed_chains; } +/* Perform register renaming on the current function. */ + +static unsigned int +regrename_optimize (void) +{ + basic_block bb; + char *first_obj; + + df_set_flags (DF_LR_RUN_DCE); + df_note_add_problem (); + df_analyze (); + df_set_flags (DF_DEFER_INSN_RESCAN); + + memset (tick, 0, sizeof tick); + + gcc_obstack_init (&rename_obstack); + first_obj = XOBNEWVAR (&rename_obstack, char, 0); + + FOR_EACH_BB (bb) + { + struct du_head *all_chains = 0; + + id_to_chain = VEC_alloc (du_head_p, heap, 0); + + if (dump_file) + fprintf (dump_file, "\nBasic block %d:\n", bb->index); + + all_chains = build_def_use (bb); + + if (dump_file) + dump_def_use_chain (all_chains); + + rename_chains (all_chains); + + free_chain_data (); + obstack_free (&rename_obstack, first_obj); + } + + obstack_free (&rename_obstack, NULL); + + if (dump_file) + fputc ('\n', dump_file); + + return 0; +} + static bool gate_handle_regrename (void) {