X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fbt-load.c;h=bf9214b1ae4deb27d6b585a0d770dae86ebe14d4;hp=4bcf76c3f224a2c0ac6f0b927b81b85e8b4a9a92;hb=2c18e34627232a0e46c6ca336e0976d7dfce5e1e;hpb=917bbcab602907861c40cfad1cc5337aaf9d0f1d diff --git a/gcc/bt-load.c b/gcc/bt-load.c index 4bcf76c3f22..bf9214b1ae4 100644 --- a/gcc/bt-load.c +++ b/gcc/bt-load.c @@ -1,11 +1,12 @@ /* Perform branch target register load optimizations. - Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -14,21 +15,16 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" -#include "bitmap.h" -#include "sbitmap.h" #include "rtl.h" #include "hard-reg-set.h" -#include "basic-block.h" #include "regs.h" -#include "obstack.h" #include "fibheap.h" #include "output.h" #include "target.h" @@ -36,7 +32,12 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "flags.h" #include "insn-attr.h" #include "function.h" +#include "except.h" #include "tm_p.h" +#include "toplev.h" +#include "tree-pass.h" +#include "recog.h" +#include "df.h" /* Target register optimizations - these are performed after reload. */ @@ -101,13 +102,17 @@ typedef struct btr_def_s as appropriate. */ char other_btr_uses_before_def; char other_btr_uses_after_use; + /* We set own_end when we have moved a definition into a dominator. + Thus, when a later combination removes this definition again, we know + to clear out trs_live_at_end again. */ + char own_end; bitmap live_range; } *btr_def; static int issue_rate; -static int basic_block_freq (basic_block); -static int insn_sets_btr_p (rtx, int, int *); +static int basic_block_freq (const_basic_block); +static int insn_sets_btr_p (const_rtx, int, int *); static rtx *find_btr_use (rtx); static int btr_referenced_p (rtx, rtx *); static int find_btr_reference (rtx *, void *); @@ -126,17 +131,17 @@ static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int); static void build_btr_def_use_webs (fibheap_t); static int block_at_edge_of_live_range_p (int, btr_def); static void clear_btr_from_live_range (btr_def def); -static void add_btr_to_live_range (btr_def); +static void add_btr_to_live_range (btr_def, int); static void augment_live_range (bitmap, HARD_REG_SET *, basic_block, - basic_block); + basic_block, int); static int choose_btr (HARD_REG_SET); static void combine_btr_defs (btr_def, HARD_REG_SET *); static void btr_def_live_range (btr_def, HARD_REG_SET *); static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *); static int migrate_btr_def (btr_def, int); static void migrate_btr_defs (enum reg_class, int); -static int can_move_up (basic_block, rtx, int); -static void note_btr_set (rtx, rtx, void *); +static int can_move_up (const_basic_block, const_rtx, int); +static void note_btr_set (rtx, const_rtx, void *); /* The following code performs code motion of target load instructions (instructions that set branch target registers), to move them @@ -155,13 +160,14 @@ static void note_btr_set (rtx, rtx, void *); migrating branch target load instructions. */ static struct obstack migrate_btrl_obstack; -/* Basic block dominator information used when migrating PT instructions */ -static dominance_info dom; - /* Array indexed by basic block number, giving the set of registers live in that block. */ static HARD_REG_SET *btrs_live; +/* Array indexed by basic block number, giving the set of registers live at + the end of that block, including any uses by a final jump insn, if any. */ +static HARD_REG_SET *btrs_live_at_end; + /* Set of all target registers that we are willing to allocate. */ static HARD_REG_SET all_btrs; @@ -171,10 +177,9 @@ static int first_btr, last_btr; -/* Return an estimate of the frequency of execution of block bb. - If we have a profiling count available, we could use it here. */ +/* Return an estimate of the frequency of execution of block bb. */ static int -basic_block_freq (basic_block bb) +basic_block_freq (const_basic_block bb) { return bb->frequency; } @@ -189,20 +194,17 @@ static int find_btr_reference (rtx *px, void *preg) { rtx x; - int regno, i; if (px == preg) return -1; x = *px; - if (GET_CODE (x) != REG) + if (!REG_P (x)) return 0; - regno = REGNO (x); - for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1; i >= 0; i--) - if (TEST_HARD_REG_BIT (all_btrs, regno+i)) - { - btr_reference_found = px; - return 1; - } + if (overlaps_hard_reg_set_p (all_btrs, GET_MODE (x), REGNO (x))) + { + btr_reference_found = px; + return 1; + } return -1; } @@ -220,11 +222,11 @@ btr_referenced_p (rtx x, rtx *excludep) If such a set is found and REGNO is nonzero, assign the register number of the destination register to *REGNO. */ static int -insn_sets_btr_p (rtx insn, int check_const, int *regno) +insn_sets_btr_p (const_rtx insn, int check_const, int *regno) { rtx set; - if (GET_CODE (insn) == INSN + if (NONJUMP_INSN_P (insn) && (set = single_set (insn))) { rtx dest = SET_DEST (set); @@ -233,11 +235,11 @@ insn_sets_btr_p (rtx insn, int check_const, int *regno) if (GET_CODE (dest) == SUBREG) dest = XEXP (dest, 0); - if (GET_CODE (dest) == REG + if (REG_P (dest) && TEST_HARD_REG_BIT (all_btrs, REGNO (dest))) { - if (btr_referenced_p (src, NULL)) - abort(); + gcc_assert (!btr_referenced_p (src, NULL)); + if (!check_const || CONSTANT_P (src)) { if (regno) @@ -277,9 +279,8 @@ find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def) if (!this_group) { - this_group = (btr_def_group) - obstack_alloc (&migrate_btrl_obstack, - sizeof (struct btr_def_group_s)); + this_group = obstack_alloc (&migrate_btrl_obstack, + sizeof (struct btr_def_group_s)); this_group->src = def_src; this_group->members = NULL; this_group->next = *all_btr_def_groups; @@ -301,8 +302,8 @@ add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn, unsigned int dest_reg, int other_btr_uses_before_def, btr_def_group *all_btr_def_groups) { - btr_def this = (btr_def) - obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s)); + btr_def this + = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s)); this->bb = bb; this->luid = insn_luid; this->insn = insn; @@ -319,8 +320,8 @@ add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn, fibheap_insert (all_btr_defs, -this->cost, this); - if (rtl_dump_file) - fprintf (rtl_dump_file, + if (dump_file) + fprintf (dump_file, "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n", dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"), this->cost); @@ -353,8 +354,7 @@ new_btr_user (basic_block bb, int insn_luid, rtx insn) usep = NULL; } use = usep ? *usep : NULL_RTX; - user = (btr_user) - obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s)); + user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s)); user->bb = bb; user->luid = insn_luid; user->insn = insn; @@ -364,13 +364,13 @@ new_btr_user (basic_block bb, int insn_luid, rtx insn) user->n_reaching_defs = 0; user->first_reaching_def = -1; - if (rtl_dump_file) + if (dump_file) { - fprintf (rtl_dump_file, "Uses target reg: { bb %d, insn %d }", + fprintf (dump_file, "Uses target reg: { bb %d, insn %d }", bb->index, INSN_UID (insn)); if (user->use) - fprintf (rtl_dump_file, ": unambiguous use of reg %d\n", + fprintf (dump_file, ": unambiguous use of reg %d\n", REGNO (user->use)); } @@ -384,16 +384,16 @@ dump_hard_reg_set (HARD_REG_SET s) int reg; for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) if (TEST_HARD_REG_BIT (s, reg)) - fprintf (rtl_dump_file, " %d", reg); + fprintf (dump_file, " %d", reg); } /* Write the set of target regs live in block BB to the dump file. */ static void dump_btrs_live (int bb) { - fprintf (rtl_dump_file, "BB%d live:", bb); + fprintf (dump_file, "BB%d live:", bb); dump_hard_reg_set (btrs_live[bb]); - fprintf (rtl_dump_file, "\n"); + fprintf (dump_file, "\n"); } /* REGNO is the number of a branch target register that is being used or @@ -423,15 +423,15 @@ typedef struct { straightforward definitions. DATA points to information about the current basic block that needs updating. */ static void -note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data) +note_btr_set (rtx dest, const_rtx set ATTRIBUTE_UNUSED, void *data) { defs_uses_info *info = data; int regno, end_regno; - if (GET_CODE (dest) != REG) + if (!REG_P (dest)) return; regno = REGNO (dest); - end_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)); + end_regno = END_HARD_REGNO (dest); for (; regno < end_regno; regno++) if (TEST_HARD_REG_BIT (all_btrs, regno)) { @@ -460,13 +460,14 @@ compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, defs_uses_info info; sbitmap_vector_zero (bb_gen, n_basic_blocks); - for (i = 0; i < n_basic_blocks; i++) + for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) { basic_block bb = BASIC_BLOCK (i); int reg; btr_def defs_this_bb = NULL; rtx insn; rtx last; + int can_throw = 0; info.users_this_bb = NULL; info.bb_gen = bb_gen[i]; @@ -476,10 +477,10 @@ compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, CLEAR_HARD_REG_SET (info.btrs_written_in_block); for (reg = first_btr; reg <= last_btr; reg++) if (TEST_HARD_REG_BIT (all_btrs, reg) - && REGNO_REG_SET_P (bb->global_live_at_start, reg)) + && REGNO_REG_SET_P (df_get_live_in (bb), reg)) SET_HARD_REG_BIT (info.btrs_live_in_block, reg); - for (insn = bb->head, last = NEXT_INSN (bb->end); + for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; insn = NEXT_INSN (insn), insn_luid++) { @@ -506,6 +507,22 @@ compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, SET_BIT (btr_defset[regno - first_btr], insn_uid); note_other_use_this_block (regno, info.users_this_bb); } + /* Check for the blockage emitted by expand_nl_goto_receiver. */ + else if (current_function_has_nonlocal_label + && GET_CODE (PATTERN (insn)) == UNSPEC_VOLATILE) + { + btr_user user; + + /* Do the equivalent of calling note_other_use_this_block + for every target register. */ + for (user = info.users_this_bb; user != NULL; + user = user->next) + if (user->use) + user->other_use_this_block = 1; + IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs); + IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs); + sbitmap_zero (info.bb_gen); + } else { if (btr_referenced_p (PATTERN (insn), NULL)) @@ -533,7 +550,7 @@ compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, user->next = info.users_this_bb; info.users_this_bb = user; } - if (GET_CODE (insn) == CALL_INSN) + if (CALL_P (insn)) { HARD_REG_SET *clobbered = &call_used_reg_set; HARD_REG_SET call_saved; @@ -549,7 +566,7 @@ compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, call_used_reg_set); clobbered = &call_saved; } - + for (regno = first_btr; regno <= last_btr; regno++) if (TEST_HARD_REG_BIT (*clobbered, regno)) note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info); @@ -560,7 +577,36 @@ compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block); COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block); - if (rtl_dump_file) + + REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], df_get_live_out (bb)); + /* If this block ends in a jump insn, add any uses or even clobbers + of branch target registers that it might have. */ + for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); ) + insn = PREV_INSN (insn); + /* ??? for the fall-through edge, it would make sense to insert the + btr set on the edge, but that would require to split the block + early on so that we can distinguish between dominance from the fall + through edge - which can use the call-clobbered registers - from + dominance by the throw edge. */ + if (can_throw_internal (insn)) + { + HARD_REG_SET tmp; + + COPY_HARD_REG_SET (tmp, call_used_reg_set); + AND_HARD_REG_SET (tmp, all_btrs); + IOR_HARD_REG_SET (btrs_live_at_end[i], tmp); + can_throw = 1; + } + if (can_throw || JUMP_P (insn)) + { + int regno; + + for (regno = first_btr; regno <= last_btr; regno++) + if (refers_to_regno_p (regno, regno+1, insn, NULL)) + SET_HARD_REG_BIT (btrs_live_at_end[i], regno); + } + + if (dump_file) dump_btrs_live(i); } } @@ -575,7 +621,7 @@ compute_kill (sbitmap *bb_kill, sbitmap *btr_defset, /* For each basic block, form the set BB_KILL - the set of definitions that the block kills. */ sbitmap_vector_zero (bb_kill, n_basic_blocks); - for (i = 0; i < n_basic_blocks; i++) + for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) { for (regno = first_btr; regno <= last_btr; regno++) if (TEST_HARD_REG_BIT (all_btrs, regno) @@ -598,14 +644,14 @@ compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid) int changed; sbitmap bb_in = sbitmap_alloc (max_uid); - for (i = 0; i < n_basic_blocks; i++) + for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) sbitmap_copy (bb_out[i], bb_gen[i]); changed = 1; while (changed) { changed = 0; - for (i = 0; i < n_basic_blocks; i++) + for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) { sbitmap_union_of_preds (bb_in, bb_out, i); changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i], @@ -624,14 +670,14 @@ link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, /* Link uses to the uses lists of all of their reaching defs. Count up the number of reaching defs of each use. */ - for (i = 0; i < n_basic_blocks; i++) + for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) { basic_block bb = BASIC_BLOCK (i); rtx insn; rtx last; sbitmap_union_of_preds (reaching_defs, bb_out, i); - for (insn = bb->head, last = NEXT_INSN (bb->end); + for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; insn = NEXT_INSN (insn)) { @@ -654,7 +700,8 @@ link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, { /* Find all the reaching defs for this use. */ sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid); - int uid; + unsigned int uid = 0; + sbitmap_iterator sbi; if (user->use) sbitmap_a_and_b ( @@ -675,14 +722,14 @@ link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, reaching_defs, btr_defset[reg - first_btr]); } - EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, + EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, sbi) { btr_def def = def_array[uid]; /* We now know that def reaches user. */ - if (rtl_dump_file) - fprintf (rtl_dump_file, + if (dump_file) + fprintf (dump_file, "Def in insn %d reaches use in insn %d\n", uid, insn_uid); @@ -696,8 +743,8 @@ link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, def->has_ambiguous_use = 1; def_array[user->first_reaching_def] ->has_ambiguous_use = 1; - if (rtl_dump_file) - fprintf (rtl_dump_file, + if (dump_file) + fprintf (dump_file, "(use %d has multiple reaching defs)\n", insn_uid); } @@ -707,11 +754,11 @@ link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, def->other_btr_uses_after_use = 1; user->next = def->uses; def->uses = user; - }); + } sbitmap_free (reaching_defs_of_reg); } - if (GET_CODE (insn) == CALL_INSN) + if (CALL_P (insn)) { int regno; @@ -731,13 +778,12 @@ static void build_btr_def_use_webs (fibheap_t all_btr_defs) { const int max_uid = get_max_uid (); - btr_def *def_array = xcalloc (max_uid, sizeof (btr_def)); - btr_user *use_array = xcalloc (max_uid, sizeof (btr_user)); + btr_def *def_array = XCNEWVEC (btr_def, max_uid); + btr_user *use_array = XCNEWVEC (btr_user, max_uid); sbitmap *btr_defset = sbitmap_vector_alloc ( (last_btr - first_btr) + 1, max_uid); sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid); - HARD_REG_SET *btrs_written = (HARD_REG_SET *) xcalloc ( - n_basic_blocks, sizeof (HARD_REG_SET)); + HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET, n_basic_blocks); sbitmap *bb_kill; sbitmap *bb_out; @@ -793,37 +839,49 @@ block_at_edge_of_live_range_p (int bb, btr_def def) static void clear_btr_from_live_range (btr_def def) { - int bb; - - EXECUTE_IF_SET_IN_BITMAP - (def->live_range, 0, bb, - { - if ((!def->other_btr_uses_before_def - && !def->other_btr_uses_after_use) - || !block_at_edge_of_live_range_p (bb, def)) - { - CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr); - if (rtl_dump_file) - dump_btrs_live (bb); - } - }); + unsigned bb; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) + { + if ((!def->other_btr_uses_before_def + && !def->other_btr_uses_after_use) + || !block_at_edge_of_live_range_p (bb, def)) + { + CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr); + CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); + if (dump_file) + dump_btrs_live (bb); + } + } + if (def->own_end) + CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr); } /* We are adding the def/use web DEF. Add the target register used in this web to the live set of all of the basic blocks that contain - the live range of the web. */ + the live range of the web. + If OWN_END is set, also show that the register is live from our + definitions at the end of the basic block where it is defined. */ static void -add_btr_to_live_range (btr_def def) +add_btr_to_live_range (btr_def def, int own_end) { - int bb; - EXECUTE_IF_SET_IN_BITMAP - (def->live_range, 0, bb, - { - SET_HARD_REG_BIT (btrs_live[bb], def->btr); - if (rtl_dump_file) - dump_btrs_live (bb); - }); + unsigned bb; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) + { + SET_HARD_REG_BIT (btrs_live[bb], def->btr); + SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); + if (dump_file) + dump_btrs_live (bb); + } + if (own_end) + { + SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr); + def->own_end = 1; + } } /* Update a live range to contain the basic block NEW_BLOCK, and all @@ -832,40 +890,59 @@ add_btr_to_live_range (btr_def def) all other blocks in the existing live range. Also add to the set BTRS_LIVE_IN_RANGE all target registers that are live in the blocks that we add to the live range. + If FULL_RANGE is set, include the full live range of NEW_BB; + otherwise, if NEW_BB dominates HEAD_BB, only add registers that + are life at the end of NEW_BB for NEW_BB itself. It is a precondition that either NEW_BLOCK dominates HEAD,or HEAD dom NEW_BLOCK. This is used to speed up the implementation of this function. */ static void augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range, - basic_block head_bb, basic_block new_bb) + basic_block head_bb, basic_block new_bb, int full_range) { basic_block *worklist, *tos; - tos = worklist = - (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1)); + tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); - if (dominated_by_p (dom, new_bb, head_bb)) - *tos++ = new_bb; - else if (dominated_by_p (dom, head_bb, new_bb)) + if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb)) + { + if (new_bb == head_bb) + { + if (full_range) + IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]); + free (tos); + return; + } + *tos++ = new_bb; + } + else { edge e; + edge_iterator ei; int new_block = new_bb->index; + gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb)); + + IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]); bitmap_set_bit (live_range, new_block); - IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]); - if (rtl_dump_file) + /* A previous btr migration could have caused a register to be + live just at the end of new_block which we need in full, so + use trs_live_at_end even if full_range is set. */ + IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]); + if (full_range) + IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]); + if (dump_file) { - fprintf (rtl_dump_file, - "Adding block %d to live range\n", new_block); - fprintf (rtl_dump_file,"Now live btrs are "); + fprintf (dump_file, + "Adding end of block %d and rest of %d to live range\n", + new_block, head_bb->index); + fprintf (dump_file,"Now live btrs are "); dump_hard_reg_set (*btrs_live_in_range); - fprintf (rtl_dump_file, "\n"); + fprintf (dump_file, "\n"); } - for (e = head_bb->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, head_bb->preds) *tos++ = e->src; } - else - abort(); while (tos != worklist) { @@ -873,20 +950,25 @@ augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range, if (!bitmap_bit_p (live_range, bb->index)) { edge e; + edge_iterator ei; bitmap_set_bit (live_range, bb->index); IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[bb->index]); - if (rtl_dump_file) + /* A previous btr migration could have caused a register to be + live just at the end of a block which we need in full. */ + IOR_HARD_REG_SET (*btrs_live_in_range, + btrs_live_at_end[bb->index]); + if (dump_file) { - fprintf (rtl_dump_file, + fprintf (dump_file, "Adding block %d to live range\n", bb->index); - fprintf (rtl_dump_file,"Now live btrs are "); + fprintf (dump_file,"Now live btrs are "); dump_hard_reg_set (*btrs_live_in_range); - fprintf (rtl_dump_file, "\n"); + fprintf (dump_file, "\n"); } - for (e = bb->pred; e != NULL; e = e->pred_next) + FOR_EACH_EDGE (e, ei, bb->preds) { basic_block pred = e->src; if (!bitmap_bit_p (live_range, pred->index)) @@ -904,20 +986,19 @@ static int choose_btr (HARD_REG_SET used_btrs) { int i; - GO_IF_HARD_REG_SUBSET (all_btrs, used_btrs, give_up); - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - { + if (!hard_reg_set_subset_p (all_btrs, used_btrs)) + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + { #ifdef REG_ALLOC_ORDER - int regno = reg_alloc_order[i]; + int regno = reg_alloc_order[i]; #else - int regno = i; + int regno = i; #endif - if (TEST_HARD_REG_BIT (all_btrs, regno) - && !TEST_HARD_REG_BIT (used_btrs, regno)) - return regno; - } -give_up: + if (TEST_HARD_REG_BIT (all_btrs, regno) + && !TEST_HARD_REG_BIT (used_btrs, regno)) + return regno; + } return -1; } @@ -933,14 +1014,19 @@ btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range) { btr_user user; - def->live_range = BITMAP_XMALLOC (); + def->live_range = BITMAP_ALLOC (NULL); bitmap_set_bit (def->live_range, def->bb->index); - COPY_HARD_REG_SET (*btrs_live_in_range, btrs_live[def->bb->index]); + COPY_HARD_REG_SET (*btrs_live_in_range, + (flag_btr_bb_exclusive + ? btrs_live : btrs_live_at_end)[def->bb->index]); for (user = def->uses; user != NULL; user = user->next) augment_live_range (def->live_range, btrs_live_in_range, - def->bb, user->bb); + def->bb, user->bb, + (flag_btr_bb_exclusive + || user->insn != BB_END (def->bb) + || !JUMP_P (user->insn))); } else { @@ -948,15 +1034,17 @@ btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range) the set of target registers live over it, because migration of other PT instructions may have affected it. */ - int bb; + unsigned bb; + unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index; + bitmap_iterator bi; CLEAR_HARD_REG_SET (*btrs_live_in_range); - EXECUTE_IF_SET_IN_BITMAP - (def->live_range, 0, bb, - { - IOR_HARD_REG_SET (*btrs_live_in_range, - btrs_live[bb]); - }); + EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) + { + IOR_HARD_REG_SET (*btrs_live_in_range, + (def_bb == bb + ? btrs_live_at_end : btrs_live) [bb]); + } } if (!def->other_btr_uses_before_def && !def->other_btr_uses_after_use) @@ -978,7 +1066,7 @@ combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) if (other_def != def && other_def->uses != NULL && ! other_def->has_ambiguous_use - && dominated_by_p (dom, other_def->bb, def->bb)) + && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb)) { /* def->bb dominates the other def, so def and other_def could be combined. */ @@ -986,7 +1074,7 @@ combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) target registers live over the merged range. */ int btr; HARD_REG_SET combined_btrs_live; - bitmap combined_live_range = BITMAP_XMALLOC (); + bitmap combined_live_range = BITMAP_ALLOC (NULL); btr_user user; if (other_def->live_range == NULL) @@ -999,14 +1087,17 @@ combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) for (user = other_def->uses; user != NULL; user = user->next) augment_live_range (combined_live_range, &combined_btrs_live, - def->bb, user->bb); + def->bb, user->bb, + (flag_btr_bb_exclusive + || user->insn != BB_END (def->bb) + || !JUMP_P (user->insn))); btr = choose_btr (combined_btrs_live); if (btr != -1) { /* We can combine them. */ - if (rtl_dump_file) - fprintf (rtl_dump_file, + if (dump_file) + fprintf (dump_file, "Combining def in insn %d with def in insn %d\n", INSN_UID (other_def->insn), INSN_UID (def->insn)); @@ -1033,7 +1124,7 @@ combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) clear_btr_from_live_range (other_def); other_def->uses = NULL; bitmap_copy (def->live_range, combined_live_range); - if (other_def->other_btr_uses_after_use) + if (other_def->btr == btr && other_def->other_btr_uses_after_use) def->other_btr_uses_after_use = 1; COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live); @@ -1041,7 +1132,7 @@ combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) delete_insn (other_def->insn); } - BITMAP_XFREE (combined_live_range); + BITMAP_FREE (combined_live_range); } } } @@ -1062,7 +1153,7 @@ move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, Replace all uses of the old target register definition by uses of the new definition. Delete the old definition. */ basic_block b = new_def_bb; - rtx insp = b->head; + rtx insp = BB_HEAD (b); rtx old_insn = def->insn; rtx src; rtx btr_rtx; @@ -1071,8 +1162,8 @@ move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, btr_user user; rtx set; - if (rtl_dump_file) - fprintf(rtl_dump_file, "migrating to basic block %d, using reg %d\n", + if (dump_file) + fprintf(dump_file, "migrating to basic block %d, using reg %d\n", new_def_bb->index, btr); clear_btr_from_live_range (def); @@ -1080,32 +1171,43 @@ move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, def->bb = new_def_bb; def->luid = 0; def->cost = basic_block_freq (new_def_bb); - def->other_btr_uses_before_def = 0; bitmap_copy (def->live_range, live_range); combine_btr_defs (def, btrs_live_in_range); btr = def->btr; - add_btr_to_live_range (def); - if (GET_CODE (insp) == CODE_LABEL) + def->other_btr_uses_before_def + = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0; + add_btr_to_live_range (def, 1); + if (LABEL_P (insp)) insp = NEXT_INSN (insp); /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some optimizations can result in insp being both first and last insn of its basic block. */ /* ?? some assertions to check that insp is sensible? */ + if (def->other_btr_uses_before_def) + { + insp = BB_END (b); + for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp)) + gcc_assert (insp != BB_HEAD (b)); + + if (JUMP_P (insp) || can_throw_internal (insp)) + insp = PREV_INSN (insp); + } + set = single_set (old_insn); src = SET_SRC (set); btr_mode = GET_MODE (SET_DEST (set)); - btr_rtx = gen_rtx (REG, btr_mode, btr); + btr_rtx = gen_rtx_REG (btr_mode, btr); new_insn = gen_move_insn (btr_rtx, src); /* Insert target register initialization at head of basic block. */ def->insn = emit_insn_after (new_insn, insp); - regs_ever_live[btr] = 1; + df_set_regs_ever_live (btr, true); - if (rtl_dump_file) - fprintf (rtl_dump_file, "New pt is insn %d, inserted after insn %d\n", + if (dump_file) + fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n", INSN_UID (def->insn), INSN_UID (insp)); /* Delete the old target register initialization. */ @@ -1124,8 +1226,8 @@ move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, || GET_MODE (user->use) == VOIDmode) replacement_rtx = btr_rtx; else - replacement_rtx = gen_rtx (REG, GET_MODE (user->use), btr); - replace_rtx (user->insn, user->use, replacement_rtx); + replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr); + validate_replace_rtx (user->use, replacement_rtx, user->insn); user->use = replacement_rtx; } } @@ -1133,9 +1235,9 @@ move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, /* We anticipate intra-block scheduling to be done. See if INSN could move up within BB by N_INSNS. */ static int -can_move_up (basic_block bb, rtx insn, int n_insns) +can_move_up (const_basic_block bb, const_rtx insn, int n_insns) { - while (insn != bb->head && n_insns > 0) + while (insn != BB_HEAD (bb) && n_insns > 0) { insn = PREV_INSN (insn); /* ??? What if we have an anti-dependency that actually prevents the @@ -1177,18 +1279,18 @@ migrate_btr_def (btr_def def, int min_cost) int give_up = 0; int def_moved = 0; btr_user user; - int def_latency = 1; + int def_latency; - if (rtl_dump_file) - fprintf (rtl_dump_file, + if (dump_file) + fprintf (dump_file, "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ", INSN_UID (def->insn), def->cost, min_cost); if (!def->group || def->has_ambiguous_use) /* These defs are not migratable. */ { - if (rtl_dump_file) - fprintf (rtl_dump_file, "it's not migratable\n"); + if (dump_file) + fprintf (dump_file, "it's not migratable\n"); return 0; } @@ -1197,24 +1299,21 @@ migrate_btr_def (btr_def def, int min_cost) no need to consider it further. */ { - if (rtl_dump_file) - fprintf (rtl_dump_file, "it's already combined with another pt\n"); + if (dump_file) + fprintf (dump_file, "it's already combined with another pt\n"); return 0; } btr_def_live_range (def, &btrs_live_in_range); - live_range = BITMAP_XMALLOC (); + live_range = BITMAP_ALLOC (NULL); bitmap_copy (live_range, def->live_range); #ifdef INSN_SCHEDULING - if ((*targetm.sched.use_dfa_pipeline_interface) ()) - def_latency = insn_default_latency (def->insn); - else - def_latency = result_ready_cost (def->insn); + def_latency = insn_default_latency (def->insn) * issue_rate; +#else + def_latency = issue_rate; #endif - def_latency *= issue_rate; - for (user = def->uses; user != NULL; user = user->next) { if (user->bb == def->bb @@ -1230,27 +1329,37 @@ migrate_btr_def (btr_def def, int min_cost) def_basic_block_freq = basic_block_freq (def->bb); - for (try = get_immediate_dominator (dom, def->bb); + for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb); !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost; - try = get_immediate_dominator (dom, try)) + try = get_immediate_dominator (CDI_DOMINATORS, try)) { /* Try to move the instruction that sets the target register into basic block TRY. */ int try_freq = basic_block_freq (try); + edge_iterator ei; + edge e; - if (rtl_dump_file) - fprintf (rtl_dump_file, "trying block %d ...", try->index); + /* If TRY has abnormal edges, skip it. */ + FOR_EACH_EDGE (e, ei, try->succs) + if (e->flags & EDGE_COMPLEX) + break; + if (e) + continue; + + if (dump_file) + fprintf (dump_file, "trying block %d ...", try->index); if (try_freq < def_basic_block_freq || (try_freq == def_basic_block_freq && btr_used_near_def)) { int btr; - augment_live_range (live_range, &btrs_live_in_range, def->bb, try); - if (rtl_dump_file) + augment_live_range (live_range, &btrs_live_in_range, def->bb, try, + flag_btr_bb_exclusive); + if (dump_file) { - fprintf (rtl_dump_file, "Now btrs live in range are: "); + fprintf (dump_file, "Now btrs live in range are: "); dump_hard_reg_set (btrs_live_in_range); - fprintf (rtl_dump_file, "\n"); + fprintf (dump_file, "\n"); } btr = choose_btr (btrs_live_in_range); if (btr != -1) @@ -1266,8 +1375,8 @@ migrate_btr_def (btr_def def, int min_cost) /* There are no free target registers available to move this far forward, so give up */ give_up = 1; - if (rtl_dump_file) - fprintf (rtl_dump_file, + if (dump_file) + fprintf (dump_file, "giving up because there are no free target registers\n"); } @@ -1276,10 +1385,10 @@ migrate_btr_def (btr_def def, int min_cost) if (!def_moved) { give_up = 1; - if (rtl_dump_file) - fprintf (rtl_dump_file, "failed to move\n"); + if (dump_file) + fprintf (dump_file, "failed to move\n"); } - BITMAP_XFREE (live_range); + BITMAP_FREE (live_range); return !give_up; } @@ -1292,25 +1401,26 @@ migrate_btr_defs (enum reg_class btr_class, int allow_callee_save) int reg; gcc_obstack_init (&migrate_btrl_obstack); - if (rtl_dump_file) + if (dump_file) { int i; - for (i = 0; i < n_basic_blocks; i++) + for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) { basic_block bb = BASIC_BLOCK (i); - fprintf(rtl_dump_file, + fprintf(dump_file, "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC " loop-depth = %d idom = %d\n", i, (HOST_WIDEST_INT) bb->count, bb->loop_depth, - get_immediate_dominator (dom, bb)->index); + get_immediate_dominator (CDI_DOMINATORS, bb)->index); } } CLEAR_HARD_REG_SET (all_btrs); for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg) - && (allow_callee_save || call_used_regs[reg] || regs_ever_live[reg])) + && (allow_callee_save || call_used_regs[reg] + || df_regs_ever_live_p (reg))) { SET_HARD_REG_BIT (all_btrs, reg); last_btr = reg; @@ -1318,68 +1428,145 @@ migrate_btr_defs (enum reg_class btr_class, int allow_callee_save) first_btr = reg; } - btrs_live = - (HARD_REG_SET *) xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); + btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); + btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); build_btr_def_use_webs (all_btr_defs); while (!fibheap_empty (all_btr_defs)) { - btr_def def = - (btr_def) fibheap_extract_min (all_btr_defs); + btr_def def = fibheap_extract_min (all_btr_defs); int min_cost = -fibheap_min_key (all_btr_defs); if (migrate_btr_def (def, min_cost)) { fibheap_insert (all_btr_defs, -def->cost, (void *) def); - if (rtl_dump_file) + if (dump_file) { - fprintf (rtl_dump_file, + fprintf (dump_file, "Putting insn %d back on queue with priority %d\n", INSN_UID (def->insn), def->cost); } } else - { - if (def->live_range) - BITMAP_XFREE (def->live_range); - } + BITMAP_FREE (def->live_range); } free (btrs_live); + free (btrs_live_at_end); obstack_free (&migrate_btrl_obstack, NULL); fibheap_delete (all_btr_defs); } -void -branch_target_load_optimize (rtx insns, bool after_prologue_epilogue_gen) +static void +branch_target_load_optimize (bool after_prologue_epilogue_gen) { - enum reg_class class = (*targetm.branch_target_register_class) (); + enum reg_class class = targetm.branch_target_register_class (); if (class != NO_REGS) { /* Initialize issue_rate. */ if (targetm.sched.issue_rate) - issue_rate = (*targetm.sched.issue_rate) (); + issue_rate = targetm.sched.issue_rate (); else issue_rate = 1; - /* Build the CFG for migrate_btr_defs. */ + if (!after_prologue_epilogue_gen) + { + /* Build the CFG for migrate_btr_defs. */ #if 1 - /* This may or may not be needed, depending on where we - run this phase. */ - cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0); + /* This may or may not be needed, depending on where we + run this phase. */ + cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0); #endif + } + df_analyze (); - life_analysis (insns, NULL, 0); /* Dominator info is also needed for migrate_btr_def. */ - dom = calculate_dominance_info (CDI_DOMINATORS); + calculate_dominance_info (CDI_DOMINATORS); migrate_btr_defs (class, - ((*targetm.branch_target_register_callee_saved) + (targetm.branch_target_register_callee_saved (after_prologue_epilogue_gen))); - free_dominance_info (dom); + free_dominance_info (CDI_DOMINATORS); + } +} + +static bool +gate_handle_branch_target_load_optimize1 (void) +{ + return flag_branch_target_load_optimize; +} + + +static unsigned int +rest_of_handle_branch_target_load_optimize1 (void) +{ + branch_target_load_optimize (epilogue_completed); + return 0; +} + +struct tree_opt_pass pass_branch_target_load_optimize1 = +{ + "btl1", /* name */ + gate_handle_branch_target_load_optimize1, /* gate */ + rest_of_handle_branch_target_load_optimize1, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | + TODO_ggc_collect, /* todo_flags_finish */ + 'd' /* letter */ +}; + +static bool +gate_handle_branch_target_load_optimize2 (void) +{ + return (optimize > 0 && flag_branch_target_load_optimize2); +} + + +static unsigned int +rest_of_handle_branch_target_load_optimize2 (void) +{ + static int warned = 0; + + /* Leave this a warning for now so that it is possible to experiment + with running this pass twice. In 3.6, we should either make this + an error, or use separate dump files. */ + if (flag_branch_target_load_optimize + && flag_branch_target_load_optimize2 + && !warned) + { + warning (0, "branch target register load optimization is not intended " + "to be run twice"); - update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, - PROP_DEATH_NOTES | PROP_REG_INFO); + warned = 1; } + + branch_target_load_optimize (epilogue_completed); + return 0; } + +struct tree_opt_pass pass_branch_target_load_optimize2 = +{ + "btl2", /* name */ + gate_handle_branch_target_load_optimize2, /* gate */ + rest_of_handle_branch_target_load_optimize2, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | + TODO_ggc_collect, /* todo_flags_finish */ + 'd' /* letter */ +}; +