From patchwork Tue Jun 21 13:54:30 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernd Schmidt X-Patchwork-Id: 101291 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 982C8B6F7B for ; Tue, 21 Jun 2011 23:55:06 +1000 (EST) Received: (qmail 9199 invoked by alias); 21 Jun 2011 13:55:04 -0000 Received: (qmail 9124 invoked by uid 22791); 21 Jun 2011 13:55:00 -0000 X-SWARE-Spam-Status: No, hits=-0.8 required=5.0 tests=AWL, BAYES_20, T_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; Tue, 21 Jun 2011 13:54:41 +0000 Received: (qmail 8552 invoked from network); 21 Jun 2011 13:54:40 -0000 Received: from unknown (HELO ?84.152.222.116?) (bernds@127.0.0.2) by mail.codesourcery.com with ESMTPA; 21 Jun 2011 13:54:40 -0000 Message-ID: <4E00A296.4000306@codesourcery.com> Date: Tue, 21 Jun 2011 15:54:30 +0200 From: Bernd Schmidt User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110516 Lightning/1.0b3pre Thunderbird/3.1.10 MIME-Version: 1.0 To: GCC Patches Subject: Rename across basic block boundaries 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 This patch requires http://gcc.gnu.org/ml/gcc-patches/2011-05/msg02193.html as a prerequisite, and supersedes http://gcc.gnu.org/ml/gcc-patches/2011-05/msg02194.html The idea here is to allow regrename to operate across basic block boundaries. This helps for targets that use sched_ebb (such as C6X), and by exposing more chains, we also help on targets that can benefit from PREFERRED_RENAME_CLASS (again, C6X). The previous patch I posted only works on extended basic blocks, but what I really wanted was to have this analysis also work for loops. Another drawback of the previous patch was that it scanned ebbs as one large block, which could potentially lead to worse optimization if we encountered a situation that makes us fail the entire block. This version, when reaching the end of a basic block, records state which is used to initialize open chains when starting to scan its successors. We still only ever scan each block once; for loops, it's typically good enough to have data from one incoming edge. If for some reason we can't match up all outgoing and incoming edges, we just fail to merge them, behaviour then reverts to what we currently have (renaming inside a single block). One change in behaviour is that tick isn't reset for each basic block. However, this shouldn't be a problem as it just randomizes the order in which we choose registers. Bootstrapped and tested on i686-linux (with -frename-registers forced on for -O2); and a variant of it tested in a 4.5 C6X tree. Benchmarking on C6X suggested that it helps with certain performance issues. Ok (this and the preliminary patch)? Bernd * regrename.c (struct du_head): Make nregs signed. (scan_rtx_reg, scan_rtx_address, dump_def_use_chain): Remove declarations. (closed_chains): Remove. (chain_from_id): New static function. (dump_def_use_chain): Change argument to be an int, indicating the first ID to print. All callers changed. (mark_conflict, create_new_chain): Move upwards in the file. (merge_overlapping_regs): Use chain_from_id. Assert that chains don't conflict with themselves. (rename_chains): Take no argument. Iterate over id_to_chain rather to find chains to rename. Clear tick before the main loop. (struct incoming_reg_info): New struct. (struct bb_rename_info): New struct. (init_rename_info, set_incoming_from_chain, merge_chains): New static functions. (regrename_analyze): New static function, broken out of regrename_optimize. Record and make use of open chain information at basic block boundaries, and merge chains where possible. (scan_rtx_reg): Make this_nregs signed. Don't update closed_chains. (build_def_use): Return a bool to indicate success. All callers changed. Don't initialize global data here. (regrename_optimize): Move most code out of here into regrename_analyze. * regs.h (add_range_to_hard_reg_set, remove_range_from_hard_reg_set, range_overlaps_hard_reg_set_p, range_in_hard_reg_set_p): New static inline functions. Index: trunk/gcc/regrename.c =================================================================== --- trunk.orig/gcc/regrename.c +++ trunk/gcc/regrename.c @@ -75,8 +75,9 @@ struct du_head struct du_head *next_chain; /* The first and last elements of this chain. */ struct du_chain *first, *last; - /* Describes the register being tracked. */ - unsigned regno, nregs; + /* Describe the register being tracked, register number and count. */ + unsigned regno; + int nregs; /* A unique id to be used as an index into the conflicts bitmaps. */ unsigned id; @@ -138,14 +139,9 @@ 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 *); +static bool build_def_use (basic_block); typedef struct du_head *du_head_p; DEF_VEC_P (du_head_p); @@ -157,9 +153,8 @@ static unsigned current_id; /* A mapping of unique id numbers to chains. */ static VEC(du_head_p, heap) *id_to_chain; -/* List of currently open chains, and closed chains that can be renamed. */ +/* List of currently open chains. */ static struct du_head *open_chains; -static struct du_head *closed_chains; /* Bitmap of open chains. The bits set always match the list found in open_chains. */ @@ -172,14 +167,32 @@ static HARD_REG_SET live_in_chains; between this and live_in_chains is empty. */ static HARD_REG_SET live_hard_regs; -/* Dump all def/use chains in CHAINS to DUMP_FILE. */ +/* Return the chain corresponding to id number ID. Take into account that + chains may have been merged. */ +static du_head_p +chain_from_id (unsigned int id) +{ + for (;;) + { + du_head_p chain = VEC_index (du_head_p, id_to_chain, id); + if (chain->id == id) + return chain; + id = chain->id; + } +} + +/* Dump all def/use chains, starting at id FROM. */ static void -dump_def_use_chain (struct du_head *head) +dump_def_use_chain (int from) { - while (head) + du_head_p head; + int i; + FOR_EACH_VEC_ELT (du_head_p, id_to_chain, i, head) { struct du_chain *this_du = head->first; + if (i < from) + continue; fprintf (dump_file, "Register %s (%d):", reg_names[head->regno], head->nregs); while (this_du) @@ -204,6 +217,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 du_head_p +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; + 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 head; + } + + 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; + return head; +} + /* For a def-use chain HEAD, find which registers overlap its lifetime and set the corresponding bits in *PSET. */ @@ -215,8 +306,9 @@ merge_overlapping_regs (HARD_REG_SET *ps IOR_HARD_REG_SET (*pset, head->hard_conflicts); EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi) { - du_head_p other = VEC_index (du_head_p, id_to_chain, i); + du_head_p other = chain_from_id (i); unsigned j = other->nregs; + gcc_assert (other != head); while (j-- > 0) SET_HARD_REG_BIT (*pset, other->regno + j); } @@ -269,13 +361,15 @@ check_new_reg_p (int reg ATTRIBUTE_UNUSE return true; } -/* Process the closed chains starting with ALL_CHAINS and rename - registers if possible. */ +/* Perform register renaming on the current function. */ static void -rename_chains (du_head_p all_chains) +rename_chains (void) { HARD_REG_SET unavailable; + du_head_p this_head; + int i; + memset (tick, 0, sizeof tick); CLEAR_HARD_REG_SET (unavailable); /* Don't clobber traceback for noreturn functions. */ @@ -287,11 +381,10 @@ rename_chains (du_head_p all_chains) #endif } - while (all_chains) + FOR_EACH_VEC_ELT (du_head_p, id_to_chain, i, this_head) { int new_reg, best_new_reg, best_nregs; int n_uses; - struct du_head *this_head = all_chains; struct du_chain *tmp; HARD_REG_SET this_unavailable; int reg = this_head->regno; @@ -300,8 +393,6 @@ rename_chains (du_head_p all_chains) enum reg_class preferred_class; bool has_preferred_class; - all_chains = this_head->next_chain; - if (this_head->cannot_rename) continue; @@ -418,50 +509,401 @@ rename_chains (du_head_p all_chains) } } -/* Perform register renaming on the current function. */ +struct incoming_reg_info { + int nregs; + bool unusable; +}; -static unsigned int -regrename_optimize (void) +/* A structure recording information about each basic block. It is saved + and restored around basic block boundaries. */ +struct bb_rename_info { + /* The basic block corresponding to this structure. */ basic_block bb; - char *first_obj; + /* Copies of the global information. */ + bitmap_head open_chains_set; + bitmap_head incoming_open_chains_set; + unsigned n_preds; + struct incoming_reg_info incoming[FIRST_PSEUDO_REGISTER]; +}; - df_set_flags (DF_LR_RUN_DCE); - df_note_add_problem (); - df_analyze (); - df_set_flags (DF_DEFER_INSN_RESCAN); +/* Initialize a rename_info structure P for basic block BB, which starts a new + scan. */ +static void +init_rename_info (struct bb_rename_info *p, basic_block bb) +{ + int i; + df_ref *def_rec; + HARD_REG_SET start_chains_set; - memset (tick, 0, sizeof tick); + p->bb = bb; + bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack); + bitmap_initialize (&p->incoming_open_chains_set, &bitmap_default_obstack); - gcc_obstack_init (&rename_obstack); - first_obj = XOBNEWVAR (&rename_obstack, char, 0); + open_chains = NULL; + bitmap_clear (&open_chains_set); + + CLEAR_HARD_REG_SET (live_in_chains); + REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb)); + for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def)); + } + + CLEAR_HARD_REG_SET (start_chains_set); + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + { + struct incoming_reg_info *iri = p->incoming + i; + if (iri->nregs > 0 && !iri->unusable + && range_in_hard_reg_set_p (live_hard_regs, i, iri->nregs)) + { + SET_HARD_REG_BIT (start_chains_set, i); + remove_range_from_hard_reg_set (&live_hard_regs, i, iri->nregs); + } + } + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + { + struct incoming_reg_info *iri = p->incoming + i; + if (TEST_HARD_REG_BIT (start_chains_set, i)) + { + du_head_p chain; + if (dump_file) + fprintf (dump_file, "opening incoming chain\n"); + chain = create_new_chain (i, iri->nregs, NULL, NULL_RTX, NO_REGS); + bitmap_set_bit (&p->incoming_open_chains_set, chain->id); + } + } +} + +/* Record in RI that the block corresponding to it has an incoming + live value, described by CHAIN. */ +static void +set_incoming_from_chain (struct bb_rename_info *ri, du_head_p chain) +{ + int min_reg, max_reg, i; + int incoming_nregs = ri->incoming[chain->regno].nregs; + int nregs; + + /* If we've recorded the same information before, everything is fine. */ + if (incoming_nregs == chain->nregs) + { + if (dump_file) + fprintf (dump_file, "reg %d/%d already recorded\n", + chain->regno, chain->nregs); + return; + } + + /* If we have no information for any of the involved registers, update + the incoming array. */ + nregs = chain->nregs; + while (nregs-- > 0) + if (ri->incoming[chain->regno + nregs].nregs != 0 + || ri->incoming[chain->regno + nregs].unusable) + break; + if (nregs < 0) + { + nregs = chain->nregs; + ri->incoming[chain->regno].nregs = nregs; + while (nregs-- > 1) + ri->incoming[chain->regno + nregs].nregs = -nregs; + if (dump_file) + fprintf (dump_file, "recorded reg %d/%d\n", + chain->regno, chain->nregs); + return; + } + + /* There must be some kind of conflict. Set the unusable for all + overlapping registers. */ + min_reg = chain->regno; + if (incoming_nregs < 0) + min_reg += incoming_nregs; + max_reg = chain->regno + chain->nregs; + for (i = min_reg; i < max_reg; i++) + { + ri->incoming[i].unusable = true; + } +} + +/* Merge the two chains C1 and C2 so that all conflict information is + recorded and C1, and the id of C2 is changed to that of C1. */ +static void +merge_chains (du_head_p c1, du_head_p c2) +{ + if (c1 == c2) + return; + + if (c2->first != NULL) + { + if (c1->first == NULL) + c1->first = c2->first; + else + c1->last->next_use = c2->first; + c1->last = c2->last; + } + + c2->first = c2->last = NULL; + c2->id = c1->id; + + IOR_HARD_REG_SET (c1->hard_conflicts, c2->hard_conflicts); + bitmap_ior_into (&c1->conflicts, &c2->conflicts); + + c1->need_caller_save_reg |= c2->need_caller_save_reg; + c1->cannot_rename |= c2->cannot_rename; +} +/* Analyze the current function and build chains for renaming. */ + +static void +regrename_analyze (void) +{ + struct bb_rename_info *rename_info; + int i, ri_index, n_processed; + basic_block bb; + bitmap_head processed_bbs; + VEC (basic_block, heap) *bb_queue; + + rename_info = XCNEWVEC (struct bb_rename_info, n_basic_blocks); + ri_index = 0; FOR_EACH_BB (bb) { - struct du_head *all_chains = 0; + struct bb_rename_info *ri = rename_info + ri_index; + ri->bb = bb; + ri->n_preds = EDGE_COUNT (bb->preds); + bb->aux = ri; + ri_index++; + } - id_to_chain = VEC_alloc (du_head_p, heap, 0); + current_id = 0; + id_to_chain = VEC_alloc (du_head_p, heap, 0); + bitmap_initialize (&open_chains_set, &bitmap_default_obstack); + + bb_queue = VEC_alloc (basic_block, heap, 0); + + n_processed = 0; + bitmap_initialize (&processed_bbs, &bitmap_default_obstack); + VEC_safe_push (basic_block, heap, bb_queue, single_succ (ENTRY_BLOCK_PTR)); + + while (!VEC_empty (basic_block, bb_queue)) + { + bool success; + edge e; + edge_iterator ei; + basic_block bb1 = VEC_pop (basic_block, bb_queue); + struct bb_rename_info *this_info = (struct bb_rename_info *)bb1->aux; + int old_length = VEC_length (du_head_p, id_to_chain); if (dump_file) - fprintf (dump_file, "\nBasic block %d:\n", bb->index); + fprintf (dump_file, "\nprocessing block %d:\n", bb1->index); + + bitmap_set_bit (&processed_bbs, bb1->index); + n_processed++; + init_rename_info (this_info, bb1); - all_chains = build_def_use (bb); + success = build_def_use (bb1); + if (success) + { + if (dump_file) + dump_def_use_chain (old_length); + bitmap_copy (&this_info->open_chains_set, &open_chains_set); + } + else + { + if (dump_file) + fprintf (dump_file, "failed\n"); + bb1->aux = NULL; + VEC_truncate (du_head_p, id_to_chain, old_length); + current_id = old_length; + bitmap_clear (&this_info->incoming_open_chains_set); + open_chains = NULL; + } + + FOR_EACH_EDGE (e, ei, bb1->succs) + { + struct bb_rename_info *dest_ri; + struct du_head *chain; + + if (dump_file) + fprintf (dump_file, "successor block %d\n", e->dest->index); + + if (e->flags & (EDGE_EH | EDGE_ABNORMAL)) + continue; + dest_ri = (struct bb_rename_info *)e->dest->aux; + if (dest_ri == NULL) + continue; + gcc_assert (dest_ri->n_preds > 0); + dest_ri->n_preds--; + if (dest_ri->n_preds == 0 + && !bitmap_bit_p (&processed_bbs, dest_ri->bb->index)) + VEC_safe_push (basic_block, heap, bb_queue, e->dest); + if (success) + for (chain = open_chains; chain; chain = chain->next_chain) + set_incoming_from_chain (dest_ri, chain); + } + + if (VEC_empty (basic_block, bb_queue) + && n_processed < ri_index) + { + basic_block best = NULL; + FOR_EACH_BB (bb) + { + struct bb_rename_info *ri = (struct bb_rename_info *)bb->aux; + if (!bitmap_bit_p (&processed_bbs, bb->index) + && (best == 0 + || ri->n_preds != EDGE_COUNT (bb->preds))) + best = bb; + } + if (dump_file) + fprintf (dump_file, "\npicking new start block %d\n", best->index); + VEC_safe_push (basic_block, heap, bb_queue, best); + } + } + bitmap_clear (&processed_bbs); + VEC_free (basic_block, heap, bb_queue); + + for (i = 0; i < ri_index; i++) + { + struct bb_rename_info *bb_ri = rename_info + i; + unsigned j; + bitmap_iterator bi; + + if (bb_ri->bb->aux == NULL) + continue; if (dump_file) - dump_def_use_chain (all_chains); + fprintf (dump_file, "processing bb %d in edges\n", bb_ri->bb->index); + + EXECUTE_IF_SET_IN_BITMAP (&bb_ri->incoming_open_chains_set, 0, j, bi) + { + edge e; + edge_iterator ei; + struct du_head *chain = chain_from_id (j); + int n_preds_used = 0, n_preds_joined = 0; + + FOR_EACH_EDGE (e, ei, bb_ri->bb->preds) + { + struct bb_rename_info *src_ri; + unsigned k; + bitmap_iterator bi2; + HARD_REG_SET live; + bool success = false; + + REG_SET_TO_HARD_REG_SET (live, df_get_live_out (e->src)); + if (!range_overlaps_hard_reg_set_p (live, chain->regno, + chain->nregs)) + continue; + n_preds_used++; + + if (e->flags & (EDGE_EH | EDGE_ABNORMAL)) + continue; - rename_chains (all_chains); + src_ri = (struct bb_rename_info *)e->src->aux; + if (src_ri == NULL) + continue; + + EXECUTE_IF_SET_IN_BITMAP (&src_ri->open_chains_set, + 0, k, bi2) + { + struct du_head *outgoing_chain = chain_from_id (k); - free_chain_data (); - obstack_free (&rename_obstack, first_obj); + if (outgoing_chain->regno == chain->regno + && outgoing_chain->nregs == chain->nregs) + { + n_preds_joined++; + success = true; + break; + } + } + if (!success && dump_file) + fprintf (dump_file, "failure to match with pred block %d\n", + e->src->index); + } + if (n_preds_joined < n_preds_used) + { + if (dump_file) + fprintf (dump_file, "cannot rename chain %d\n", j); + chain->cannot_rename = 1; + } + } } + for (i = 0; i < ri_index; i++) + { + struct bb_rename_info *bb_ri = rename_info + i; + unsigned j; + bitmap_iterator bi; - obstack_free (&rename_obstack, NULL); + if (bb_ri->bb->aux == NULL) + continue; - if (dump_file) - fputc ('\n', dump_file); + if (dump_file) + fprintf (dump_file, "processing bb %d out edges\n", bb_ri->bb->index); - return 0; + EXECUTE_IF_SET_IN_BITMAP (&bb_ri->open_chains_set, 0, j, bi) + { + edge e; + edge_iterator ei; + struct du_head *chain = chain_from_id (j); + int n_succs_used = 0, n_succs_joined = 0; + + FOR_EACH_EDGE (e, ei, bb_ri->bb->succs) + { + bool printed = false; + struct bb_rename_info *dest_ri; + unsigned k; + bitmap_iterator bi2; + HARD_REG_SET live; + + REG_SET_TO_HARD_REG_SET (live, df_get_live_in (e->dest)); + if (!range_overlaps_hard_reg_set_p (live, chain->regno, + chain->nregs)) + continue; + + n_succs_used++; + + dest_ri = (struct bb_rename_info *)e->dest->aux; + if (dest_ri == NULL) + continue; + + EXECUTE_IF_SET_IN_BITMAP (&dest_ri->incoming_open_chains_set, + 0, k, bi2) + { + struct du_head *incoming_chain = chain_from_id (k); + + if (incoming_chain->regno == chain->regno + && incoming_chain->nregs == chain->nregs) + { + if (dump_file) + { + if (!printed) + fprintf (dump_file, "merging blocks for edge %d -> %d\n", + e->src->index, e->dest->index); + printed = true; + fprintf (dump_file, " merging chains %d (->%d) and %d (->%d) [%s]\n", + k, incoming_chain->id, j, chain->id, + reg_names[incoming_chain->regno]); + } + + merge_chains (chain, incoming_chain); + n_succs_joined++; + break; + } + } + } + if (n_succs_joined < n_succs_used) + { + if (dump_file) + fprintf (dump_file, "cannot rename chain %d\n", + j); + chain->cannot_rename = 1; + } + } + } + + free (rename_info); + + FOR_EACH_BB (bb) + bb->aux = NULL; } static void @@ -470,8 +912,6 @@ do_replace (struct du_head *head, int re struct du_chain *chain; unsigned int base_regno = head->regno; - gcc_assert (! DEBUG_INSN_P (head->first->insn)); - for (chain = head->first; chain; chain = chain->next_use) { unsigned int regno = ORIGINAL_REGNO (*chain->loc); @@ -494,19 +934,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. */ @@ -572,71 +999,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) @@ -645,7 +1007,7 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r rtx x = *loc; enum machine_mode mode = GET_MODE (x); unsigned this_regno = REGNO (x); - unsigned this_nregs = hard_regno_nregs[this_regno][mode]; + int this_nregs = hard_regno_nregs[this_regno][mode]; if (action == mark_write) { @@ -745,8 +1107,6 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r if (subset && !superset) head->cannot_rename = 1; - head->next_chain = closed_chains; - closed_chains = head; bitmap_clear_bit (&open_chains_set, head->id); nregs = head->nregs; @@ -1132,28 +1492,14 @@ record_out_operands (rtx insn, bool earl /* Build def/use chain. */ -static struct du_head * +static bool build_def_use (basic_block bb) { rtx insn; - df_ref *def_rec; unsigned HOST_WIDE_INT untracked_operands; - open_chains = closed_chains = NULL; - fail_current_block = false; - current_id = 0; - bitmap_initialize (&open_chains_set, &bitmap_default_obstack); - CLEAR_HARD_REG_SET (live_in_chains); - REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb)); - for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++) - { - df_ref def = *def_rec; - if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) - SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def)); - } - for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) { if (NONDEBUG_INSN_P (insn)) @@ -1392,14 +1738,32 @@ build_def_use (basic_block bb) break; } - bitmap_clear (&open_chains_set); - if (fail_current_block) - return NULL; + return false; + + return true; +} + +/* Perform register renaming on the current function. */ + +static unsigned int +regrename_optimize (void) +{ + df_set_flags (DF_LR_RUN_DCE); + df_note_add_problem (); + df_analyze (); + df_set_flags (DF_DEFER_INSN_RESCAN); + + gcc_obstack_init (&rename_obstack); - /* Since we close every chain when we find a REG_DEAD note, anything that - is still open lives past the basic block, so it can't be renamed. */ - return closed_chains; + regrename_analyze (); + + rename_chains (); + + free_chain_data (); + obstack_free (&rename_obstack, NULL); + + return 0; } static bool Index: trunk/gcc/regs.h =================================================================== --- trunk.orig/gcc/regs.h +++ trunk/gcc/regs.h @@ -397,4 +397,48 @@ overlaps_hard_reg_set_p (const HARD_REG_ return false; } +/* Like add_to_hard_reg_set, but use a REGNO/NREGS range instead of + REGNO and MODE. */ + +static inline void +add_range_to_hard_reg_set (HARD_REG_SET *regs, unsigned int regno, + int nregs) +{ + while (nregs-- > 0) + SET_HARD_REG_BIT (*regs, regno + nregs); +} + +/* Likewise, but remove the registers. */ + +static inline void +remove_range_from_hard_reg_set (HARD_REG_SET *regs, unsigned int regno, + int nregs) +{ + while (nregs-- > 0) + CLEAR_HARD_REG_BIT (*regs, regno + nregs); +} + +/* Like overlaps_hard_reg_set_p, but use a REGNO/NREGS range instead of + REGNO and MODE. */ +static inline bool +range_overlaps_hard_reg_set_p (const HARD_REG_SET set, unsigned regno, + int nregs) +{ + while (nregs-- > 0) + if (TEST_HARD_REG_BIT (set, regno + nregs)) + return true; + return false; +} + +/* Like in_hard_reg_set_p, but use a REGNO/NREGS range instead of + REGNO and MODE. */ +static inline bool +range_in_hard_reg_set_p (const HARD_REG_SET set, unsigned regno, int nregs) +{ + while (nregs-- > 0) + if (!TEST_HARD_REG_BIT (set, regno + nregs)) + return false; + return true; +} + #endif /* GCC_REGS_H */