From patchwork Fri May 27 19:12: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: 97735 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 E233BB6F93 for ; Sat, 28 May 2011 05:12:46 +1000 (EST) Received: (qmail 25524 invoked by alias); 27 May 2011 19:12:45 -0000 Received: (qmail 25507 invoked by uid 22791); 27 May 2011 19:12:43 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, 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; Fri, 27 May 2011 19:12:20 +0000 Received: (qmail 9020 invoked from network); 27 May 2011 19:12:19 -0000 Received: from unknown (HELO ?84.152.188.204?) (bernds@127.0.0.2) by mail.codesourcery.com with ESMTPA; 27 May 2011 19:12:19 -0000 Message-ID: <4DDFF790.9010207@codesourcery.com> Date: Fri, 27 May 2011 19:12:16 +0000 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: [2/2] Rename across ebbs References: <4DDFF6F9.3090605@codesourcery.com> In-Reply-To: <4DDFF6F9.3090605@codesourcery.com> 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 contains the actual changes for renaming across extended basic blocks (where ebb here is a tree where each basic block except the root has exactly one predecessor). All we really have to do is reconstruct some information when starting to scan a different bb; the open_chains list can be rebuilt from the open_chains_set bitmap. Bernd * regrename.c (build_def_use): Return bool, true if we produced a valid set of chains. All callers and declaration changed. Rely on the caller to initialize global state. (closed_chains): Remove variable. (dump_def_use_chain): Take no arg. All callers changed. Use the id_to_chain vector as a source of things to print. (rename_chains): Replace argument with a bitmap of chains that cannot be renamed. All callers changed. Use the id_to_chain vector to find candidate chains for renaming. (struct bb_rename_info): New structure. (init_rename_info, save_rename_info, restore_rename_info): New static functions. (regrename_optimize): Use them to process ebbs rather than single basic blocks and to initialize global state for build_def_use. (scan_rtx_reg): Don't update closed_chains. Index: trunk/gcc/regrename.c =================================================================== --- trunk.orig/gcc/regrename.c +++ trunk/gcc/regrename.c @@ -144,8 +144,7 @@ static void scan_rtx_address (rtx, rtx * 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 +156,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. */ @@ -175,9 +173,11 @@ static HARD_REG_SET live_hard_regs; /* Dump all def/use chains in CHAINS to DUMP_FILE. */ static void -dump_def_use_chain (struct du_head *head) +dump_def_use_chain (void) { - 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; fprintf (dump_file, "Register %s (%d):", @@ -269,13 +269,16 @@ check_new_reg_p (int reg ATTRIBUTE_UNUSE return true; } -/* Process the closed chains starting with ALL_CHAINS and rename - registers if possible. */ +/* Process the chains found in id_to_chain and rename registers if + possible. CANNOT_RENAME_CHAINS is a bitmap containing chains + that cannot be renamed for some reason. */ + static void -rename_chains (du_head_p all_chains) +rename_chains (bitmap cannot_rename_chains) { HARD_REG_SET unavailable; - + du_head_p this_head; + int i; CLEAR_HARD_REG_SET (unavailable); /* Don't clobber traceback for noreturn functions. */ @@ -287,11 +290,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,9 +302,8 @@ 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) + if (this_head->cannot_rename + || bitmap_bit_p (cannot_rename_chains, this_head->id)) continue; best_new_reg = reg; @@ -418,13 +419,100 @@ rename_chains (du_head_p all_chains) } } +/* 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; + /* Copies of the global information. */ + bitmap_head open_chains_set; + HARD_REG_SET live_in_chains; + HARD_REG_SET live_hard_regs; +}; + +/* 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) +{ + df_ref *def_rec; + + p->bb = bb; + bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack); + + CLEAR_HARD_REG_SET (p->live_in_chains); + REG_SET_TO_HARD_REG_SET (p->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 (p->live_hard_regs, DF_REF_REGNO (def)); + } + +} + +/* Save current rename info data into structure P, which will be restored later + to continue scanning at basic block BB. OPEN_SET is the set of open chains + at the start of BB. */ +static void +save_rename_info (struct bb_rename_info *p, basic_block bb, bitmap open_set) +{ + HARD_REG_SET live; + + p->bb = bb; + + bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack); + bitmap_copy (&p->open_chains_set, open_set); + + REG_SET_TO_HARD_REG_SET (live, df_get_live_in (bb)); + + COPY_HARD_REG_SET (p->live_in_chains, live_in_chains); + COPY_HARD_REG_SET (p->live_hard_regs, live_hard_regs); + AND_HARD_REG_SET (p->live_in_chains, live); + AND_HARD_REG_SET (p->live_hard_regs, live); +} + +/* Restore global state from the rename info structure P. Recompute the + open_chains list and the live_in_chains set from the bitmap stored in P. + This function frees the bitmap data associated with P. */ +static void +restore_rename_info (struct bb_rename_info *p) +{ + bitmap_iterator bi; + unsigned int i; + + open_chains = NULL; + bitmap_copy (&open_chains_set, &p->open_chains_set); + bitmap_clear (&p->open_chains_set); + + CLEAR_HARD_REG_SET (live_in_chains); + EXECUTE_IF_SET_IN_BITMAP (&open_chains_set, 0, i, bi) + { + struct du_head *this_chain = VEC_index (du_head_p, id_to_chain, + i); + + this_chain->next_chain = open_chains; + open_chains = this_chain; + if (dump_file) + fprintf (dump_file, " reopening %s (chain %d)\n", + reg_names[this_chain->regno], this_chain->id); + } + COPY_HARD_REG_SET (live_hard_regs, p->live_hard_regs); + COPY_HARD_REG_SET (live_in_chains, p->live_in_chains); +} + /* Perform register renaming on the current function. */ static unsigned int regrename_optimize (void) { + struct bb_rename_info *rename_info; + int ri_index; basic_block bb; char *first_obj; + bitmap_head processed_bbs; + bitmap_initialize (&processed_bbs, &bitmap_default_obstack); df_set_flags (DF_LR_RUN_DCE); df_note_add_problem (); @@ -436,21 +524,99 @@ regrename_optimize (void) gcc_obstack_init (&rename_obstack); first_obj = XOBNEWVAR (&rename_obstack, char, 0); + rename_info = XNEWVEC (struct bb_rename_info, n_basic_blocks); FOR_EACH_BB (bb) { - struct du_head *all_chains = 0; + VEC (int, heap) *bb_queue; + edge e; + edge_iterator ei; + bitmap_head chains_open_at_end; + bitmap_head tmp_chains; + bool fail = false; + if (!bitmap_set_bit (&processed_bbs, bb->index)) + continue; + + ri_index = 0; + current_id = 0; id_to_chain = VEC_alloc (du_head_p, heap, 0); + bb_queue = VEC_alloc (int, heap, 0); + + VEC_safe_push (int, heap, bb_queue, ri_index); + init_rename_info (rename_info + ri_index, bb); + ri_index++; if (dump_file) fprintf (dump_file, "\nBasic block %d:\n", bb->index); - all_chains = build_def_use (bb); + bitmap_initialize (&chains_open_at_end, &bitmap_default_obstack); + bitmap_initialize (&tmp_chains, &bitmap_default_obstack); + + while (!VEC_empty (int, bb_queue)) + { + int this_index = VEC_pop (int, bb_queue); + struct bb_rename_info *this_info = rename_info + this_index; + basic_block bb1 = this_info->bb; + + if (dump_file) + fprintf (dump_file, "processing block %d:\n", bb1->index); + bitmap_set_bit (&processed_bbs, bb1->index); + + restore_rename_info (this_info); + + if (!build_def_use (this_info->bb)) + { + fail = true; + break; + } + + FOR_EACH_EDGE (e, ei, bb1->succs) + { + struct du_head *chain; + regset live = df_get_live_in (e->dest); + if (dump_file) + fprintf (dump_file, "successor block %d: live regs", e->dest->index); + for (chain = open_chains; chain; chain = chain->next_chain) + { + int nregs = chain->nregs; + while (nregs-- > 0) + { + if (REGNO_REG_SET_P (live, chain->regno + nregs)) + { + bitmap_set_bit (&tmp_chains, chain->id); + if (dump_file) + fprintf (dump_file, " %s (%d)", + reg_names[chain->regno], chain->id); + break; + } + } + } + if (dump_file) + fprintf (dump_file, "\n"); + if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) != 0 + || EDGE_COUNT (e->dest->preds) > 1 + || e->dest == EXIT_BLOCK_PTR + || bitmap_bit_p (&processed_bbs, e->dest->index)) + { + if (dump_file) + fprintf (dump_file, " no further processing\n"); + bitmap_ior_into (&chains_open_at_end, &tmp_chains); + } + else + { + VEC_safe_push (int, heap, bb_queue, ri_index); + save_rename_info (rename_info + ri_index, e->dest, &tmp_chains); + ri_index++; + } + bitmap_clear (&tmp_chains); + } + } if (dump_file) - dump_def_use_chain (all_chains); + dump_def_use_chain (); - rename_chains (all_chains); + if (!fail) + rename_chains (&chains_open_at_end); free_chain_data (); obstack_free (&rename_obstack, first_obj); @@ -775,8 +941,6 @@ scan_rtx_reg (rtx insn, rtx *loc, enum r { unsigned nregs; - head->next_chain = closed_chains; - closed_chains = head; bitmap_clear_bit (&open_chains_set, head->id); nregs = head->nregs; @@ -1155,28 +1319,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)) @@ -1418,11 +1568,9 @@ build_def_use (basic_block bb) bitmap_clear (&open_chains_set); if (fail_current_block) - return NULL; + return false; - /* 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; + return true; } static bool