X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fira-color.c;h=feeaa627f0dc148a12c8f54911fe0d6fc5733e48;hb=e8db6cc1a2530e9a8180b4df91215b112df262e0;hp=fcad642ae12ea4301c44d451172ed3ad49d390b2;hpb=cf709bf61c30958576df8b13df595dfcf242a10b;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/ira-color.c b/gcc/ira-color.c index fcad642ae12..feeaa627f0d 100644 --- a/gcc/ira-color.c +++ b/gcc/ira-color.c @@ -1,5 +1,5 @@ /* IRA allocation based on graph coloring. - Copyright (C) 2006, 2007, 2008 + Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. Contributed by Vladimir Makarov . @@ -285,8 +285,8 @@ update_copy_costs (ira_allocno_t allocno, bool decr_p) continue; cost = (cp->second == allocno - ? ira_register_move_cost[mode][rclass][cover_class] - : ira_register_move_cost[mode][cover_class][rclass]); + ? ira_get_register_move_cost (mode, rclass, cover_class) + : ira_get_register_move_cost (mode, cover_class, rclass)); if (decr_p) cost = -cost; @@ -627,7 +627,7 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p) if (a == allocno) break; } - qsort (sorted_allocnos, j, sizeof (ira_allocno_t), + qsort (sorted_allocnos, j, sizeof (ira_allocno_t), allocno_cost_compare_func); for (i = 0; i < j; i++) { @@ -683,7 +683,7 @@ static int allocno_spill_priority (ira_allocno_t a) { return (ALLOCNO_TEMP (a) - / (ALLOCNO_LEFT_CONFLICTS_NUM (a) + / (ALLOCNO_LEFT_CONFLICTS_SIZE (a) * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)] + 1)); } @@ -861,11 +861,11 @@ static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES]; static void push_allocno_to_stack (ira_allocno_t allocno) { - int conflicts_num, conflict_size, size; + int left_conflicts_size, conflict_size, size; ira_allocno_t a, conflict_allocno; enum reg_class cover_class; ira_allocno_conflict_iterator aci; - + ALLOCNO_IN_GRAPH_P (allocno) = false; VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno); cover_class = ALLOCNO_COVER_CLASS (allocno); @@ -896,20 +896,21 @@ push_allocno_to_stack (ira_allocno_t allocno) if (ALLOCNO_IN_GRAPH_P (conflict_allocno) && ! ALLOCNO_ASSIGNED_P (conflict_allocno)) { - conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno); + left_conflicts_size + = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno); conflict_size = (ira_reg_class_nregs [cover_class][ALLOCNO_MODE (conflict_allocno)]); ira_assert - (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size); - if (conflicts_num + conflict_size + (ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) >= size); + if (left_conflicts_size + conflict_size <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno)) { - ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size; + ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) -= size; continue; } - conflicts_num - = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size; + left_conflicts_size + = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) - size; if (uncolorable_allocnos_splay_tree[cover_class] != NULL && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) && USE_SPLAY_P (cover_class)) @@ -926,8 +927,9 @@ push_allocno_to_stack (ira_allocno_t allocno) removed_splay_allocno_vec, conflict_allocno); } - ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num; - if (conflicts_num + conflict_size + ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) + = left_conflicts_size; + if (left_conflicts_size + conflict_size <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno)) { delete_allocno_from_bucket @@ -967,11 +969,11 @@ remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p) } cover_class = ALLOCNO_COVER_CLASS (allocno); ira_assert ((colorable_p - && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))) || (! colorable_p - && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > ALLOCNO_AVAILABLE_REGS_NUM (allocno)))); @@ -1003,7 +1005,7 @@ push_allocno_to_spill (ira_allocno_t allocno) } /* Return the frequency of exit edges (if EXIT_P) or entry from/to the - loop given by its LOOP_NODE. */ + loop given by its LOOP_NODE. */ int ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) { @@ -1069,7 +1071,7 @@ calculate_allocno_spill_cost (ira_allocno_t a) * ira_loop_edge_freq (loop_node, regno, true) + ira_memory_move_cost[mode][rclass][0] * ira_loop_edge_freq (loop_node, regno, false)) - - (ira_register_move_cost[mode][rclass][rclass] + - (ira_get_register_move_cost (mode, rclass, rclass) * (ira_loop_edge_freq (loop_node, regno, false) + ira_loop_edge_freq (loop_node, regno, true)))); return cost; @@ -1082,13 +1084,13 @@ allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2) { int pri1, pri2, diff; ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2; - + pri1 = (ALLOCNO_TEMP (a1) - / (ALLOCNO_LEFT_CONFLICTS_NUM (a1) + / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1) * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)] + 1)); pri2 = (ALLOCNO_TEMP (a2) - / (ALLOCNO_LEFT_CONFLICTS_NUM (a2) + / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2) * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)] + 1)); if ((diff = pri1 - pri2) != 0) @@ -1225,7 +1227,7 @@ push_allocnos_to_stack (void) allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec); ALLOCNO_SPLAY_REMOVED_P (allocno) = false; rclass = ALLOCNO_COVER_CLASS (allocno); - if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)] > ALLOCNO_AVAILABLE_REGS_NUM (allocno)) splay_tree_insert @@ -1271,7 +1273,7 @@ push_allocnos_to_stack (void) && (allocno_pri > i_allocno_pri || (allocno_pri == i_allocno_pri && (allocno_cost > i_allocno_cost - || (allocno_cost == i_allocno_cost + || (allocno_cost == i_allocno_cost && (ALLOCNO_NUM (allocno) > ALLOCNO_NUM (i_allocno)))))))) { @@ -1288,7 +1290,7 @@ push_allocnos_to_stack (void) } ira_assert (ALLOCNO_IN_GRAPH_P (allocno) && ALLOCNO_COVER_CLASS (allocno) == cover_class - && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > ALLOCNO_AVAILABLE_REGS_NUM (allocno))); @@ -1352,7 +1354,8 @@ pop_allocnos_from_stack (void) static void setup_allocno_available_regs_num (ira_allocno_t allocno) { - int i, n, hard_regs_num; + int i, n, hard_regs_num, hard_regno; + enum machine_mode mode; enum reg_class cover_class; ira_allocno_t a; HARD_REG_SET temp_set; @@ -1371,18 +1374,24 @@ setup_allocno_available_regs_num (ira_allocno_t allocno) if (a == allocno) break; } + mode = ALLOCNO_MODE (allocno); for (n = 0, i = hard_regs_num - 1; i >= 0; i--) - if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i])) - n++; + { + hard_regno = ira_class_hard_regs[cover_class][i]; + if (TEST_HARD_REG_BIT (temp_set, hard_regno) + || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode], + hard_regno)) + n++; + } if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL) fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n", ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n); ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n; } -/* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */ +/* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */ static void -setup_allocno_left_conflicts_num (ira_allocno_t allocno) +setup_allocno_left_conflicts_size (ira_allocno_t allocno) { int i, hard_regs_num, hard_regno, conflict_allocnos_size; ira_allocno_t a, conflict_allocno; @@ -1450,7 +1459,7 @@ setup_allocno_left_conflicts_num (ira_allocno_t allocno) int last = (hard_regno + hard_regno_nregs [hard_regno][ALLOCNO_MODE (conflict_allocno)]); - + while (hard_regno < last) { if (! TEST_HARD_REG_BIT (temp_set, hard_regno)) @@ -1466,7 +1475,7 @@ setup_allocno_left_conflicts_num (ira_allocno_t allocno) if (a == allocno) break; } - ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size; + ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) = conflict_allocnos_size; } /* Put ALLOCNO in a bucket corresponding to its number and size of its @@ -1474,17 +1483,15 @@ setup_allocno_left_conflicts_num (ira_allocno_t allocno) static void put_allocno_into_bucket (ira_allocno_t allocno) { - int hard_regs_num; enum reg_class cover_class; cover_class = ALLOCNO_COVER_CLASS (allocno); - hard_regs_num = ira_class_hard_regs_num[cover_class]; if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno) return; ALLOCNO_IN_GRAPH_P (allocno) = true; - setup_allocno_left_conflicts_num (allocno); + setup_allocno_left_conflicts_size (allocno); setup_allocno_available_regs_num (allocno); - if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)) add_allocno_to_bucket (allocno, &colorable_allocno_bucket); @@ -1893,7 +1900,7 @@ print_loop_title (ira_loop_tree_node_t loop_tree_node) for (j = 0; (int) j < ira_reg_class_cover_size; j++) { enum reg_class cover_class; - + cover_class = ira_reg_class_cover[j]; if (loop_tree_node->reg_pressure[cover_class] == 0) continue; @@ -2037,7 +2044,7 @@ color_pass (ira_loop_tree_node_t loop_tree_node) else { cover_class = ALLOCNO_COVER_CLASS (subloop_allocno); - cost = (ira_register_move_cost[mode][rclass][rclass] + cost = (ira_get_register_move_cost (mode, rclass, rclass) * (exit_freq + enter_freq)); ira_allocate_and_set_or_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class, @@ -2076,7 +2083,7 @@ do_coloring (void) 100); if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n"); - + ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL); if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) @@ -2162,7 +2169,7 @@ move_spill_restore (void) += (ira_memory_move_cost[mode][rclass][0] * exit_freq + ira_memory_move_cost[mode][rclass][1] * enter_freq); if (hard_regno2 != hard_regno) - cost -= (ira_register_move_cost[mode][rclass][rclass] + cost -= (ira_get_register_move_cost (mode, rclass, rclass) * (exit_freq + enter_freq)); } } @@ -2181,7 +2188,7 @@ move_spill_restore (void) += (ira_memory_move_cost[mode][rclass][1] * exit_freq + ira_memory_move_cost[mode][rclass][0] * enter_freq); if (hard_regno2 != hard_regno) - cost -= (ira_register_move_cost[mode][rclass][rclass] + cost -= (ira_get_register_move_cost (mode, rclass, rclass) * (exit_freq + enter_freq)); } } @@ -2247,8 +2254,8 @@ update_curr_costs (ira_allocno_t a) if (i < 0) continue; cost = (cp->first == a - ? ira_register_move_cost[mode][rclass][cover_class] - : ira_register_move_cost[mode][cover_class][rclass]); + ? ira_get_register_move_cost (mode, rclass, cover_class) + : ira_get_register_move_cost (mode, cover_class, rclass)); ira_allocate_and_set_or_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class, ALLOCNO_COVER_CLASS_COST (a), @@ -2680,7 +2687,7 @@ ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a), MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)), reg_max_ref_width[ALLOCNO_REGNO (a)])); - + if (a == allocno) break; } @@ -2772,8 +2779,7 @@ ira_mark_memory_move_deletion (int dst_regno, int src_regno) } /* Try to assign a hard register (except for FORBIDDEN_REGS) to - allocno A and return TRUE in the case of success. That is an - analog of retry_global_alloc for IRA. */ + allocno A and return TRUE in the case of success. */ static bool allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs) { @@ -2854,13 +2860,41 @@ bool ira_reassign_pseudos (int *spilled_pseudo_regs, int num, HARD_REG_SET bad_spill_regs, HARD_REG_SET *pseudo_forbidden_regs, - HARD_REG_SET *pseudo_previous_regs, bitmap spilled) + HARD_REG_SET *pseudo_previous_regs, + bitmap spilled) { int i, m, n, regno; bool changed_p; ira_allocno_t a, conflict_a; HARD_REG_SET forbidden_regs; ira_allocno_conflict_iterator aci; + bitmap temp = BITMAP_ALLOC (NULL); + + /* Add pseudos which conflict with pseudos already in + SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable + to allocating in two steps as some of the conflicts might have + a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */ + for (i = 0; i < num; i++) + bitmap_set_bit (temp, spilled_pseudo_regs[i]); + + for (i = 0, n = num; i < n; i++) + { + int regno = spilled_pseudo_regs[i]; + bitmap_set_bit (temp, regno); + + a = ira_regno_allocno_map[regno]; + FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci) + if (ALLOCNO_HARD_REGNO (conflict_a) < 0 + && ! ALLOCNO_DONT_REASSIGN_P (conflict_a) + && ! bitmap_bit_p (temp, ALLOCNO_REGNO (conflict_a))) + { + spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a); + bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)); + /* ?!? This seems wrong. */ + bitmap_set_bit (consideration_allocno_bitmap, + ALLOCNO_NUM (conflict_a)); + } + } if (num > 1) qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare); @@ -2879,7 +2913,7 @@ ira_reassign_pseudos (int *spilled_pseudo_regs, int num, ira_assert (reg_renumber[regno] < 0); if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) fprintf (ira_dump_file, - " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), + " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a)); allocno_reload_assign (a, forbidden_regs); @@ -2888,60 +2922,8 @@ ira_reassign_pseudos (int *spilled_pseudo_regs, int num, CLEAR_REGNO_REG_SET (spilled, regno); changed_p = true; } - else - spilled_pseudo_regs[m++] = regno; - } - if (m == 0) - return changed_p; - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - { - fprintf (ira_dump_file, " Spilled regs"); - for (i = 0; i < m; i++) - fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]); - fprintf (ira_dump_file, "\n"); - } - /* Try to assign hard registers to pseudos conflicting with ones - from SPILLED_PSEUDO_REGS. */ - for (i = n = 0; i < m; i++) - { - regno = spilled_pseudo_regs[i]; - a = ira_regno_allocno_map[regno]; - FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci) - if (ALLOCNO_HARD_REGNO (conflict_a) < 0 - && ! ALLOCNO_DONT_REASSIGN_P (conflict_a) - && ! bitmap_bit_p (consideration_allocno_bitmap, - ALLOCNO_NUM (conflict_a))) - { - sorted_allocnos[n++] = conflict_a; - bitmap_set_bit (consideration_allocno_bitmap, - ALLOCNO_NUM (conflict_a)); - } - } - if (n != 0) - { - setup_allocno_priorities (sorted_allocnos, n); - qsort (sorted_allocnos, n, sizeof (ira_allocno_t), - allocno_priority_compare_func); - for (i = 0; i < n; i++) - { - a = sorted_allocnos[i]; - regno = ALLOCNO_REGNO (a); - COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs); - IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]); - IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]); - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf (ira_dump_file, - " Try assign %d(a%d), cost=%d", - regno, ALLOCNO_NUM (a), - ALLOCNO_MEMORY_COST (a) - - ALLOCNO_COVER_CLASS_COST (a)); - if (allocno_reload_assign (a, forbidden_regs)) - { - changed_p = true; - bitmap_clear_bit (spilled, regno); - } - } } + BITMAP_FREE (temp); return changed_p; } @@ -2989,7 +2971,7 @@ ira_reuse_stack_slot (int regno, unsigned int inherent_size, if (slot->width < total_size || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size) continue; - + EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, FIRST_PSEUDO_REGISTER, i, bi) { @@ -3172,7 +3154,7 @@ ira_better_spill_reload_regno_p (int *regnos, int *other_regnos, int call_used_count, other_call_used_count; int hard_regno, other_hard_regno; - cost = calculate_spill_cost (regnos, in, out, insn, + cost = calculate_spill_cost (regnos, in, out, insn, &length, &nrefs, &call_used_count, &hard_regno); other_cost = calculate_spill_cost (other_regnos, in, out, insn, &other_length, &other_nrefs,