diff options
author | bstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4> | 2008-09-04 13:11:52 +0000 |
---|---|---|
committer | bstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4> | 2008-09-04 13:11:52 +0000 |
commit | ed1d171006e8f6c4403232e075b3e8455a19299a (patch) | |
tree | 883e632907dd1f7e877229c0ea962daf81725fa6 /gcc/ira-color.c | |
parent | 2ca603eacebf3a9902742389a1fe68c6a6bb6c0e (diff) | |
download | gcc-ed1d171006e8f6c4403232e075b3e8455a19299a.tar.gz |
2008-09-04 Basile Starynkevitch <basile@starynkevitch.net>
MELT branch merged with trunk r139983
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@139985 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'gcc/ira-color.c')
-rw-r--r-- | gcc/ira-color.c | 156 |
1 files changed, 114 insertions, 42 deletions
diff --git a/gcc/ira-color.c b/gcc/ira-color.c index a9a64b96ac6..8afc01078ee 100644 --- a/gcc/ira-color.c +++ b/gcc/ira-color.c @@ -68,6 +68,9 @@ static ira_allocno_t *sorted_allocnos; /* Vec representing the stack of allocnos used during coloring. */ static VEC(ira_allocno_t,heap) *allocno_stack_vec; +/* Vec representing conflict allocnos used during assigning. */ +static VEC(ira_allocno_t,heap) *conflict_allocno_vec; + /* Array used to choose an allocno for spilling. */ static ira_allocno_t *allocnos_for_spilling; @@ -116,6 +119,11 @@ finish_cost_update (void) ira_free (allocno_update_cost_check); } +/* When we traverse allocnos to update hard register costs, the cost + divisor will be multiplied by the following macro value for each + hop from given allocno to directly connected allocnos. */ +#define COST_HOP_DIVISOR 4 + /* This recursive function updates costs (decrease if DECR_P) of the unassigned allocnos connected by copies with ALLOCNO. This update increases chances to remove some copies. Copy cost is proportional @@ -180,7 +188,7 @@ update_copy_costs_1 (ira_allocno_t allocno, int hard_regno, += update_cost; if (update_cost != 0) update_copy_costs_1 (another_allocno, hard_regno, - decr_p, divisor * 4); + decr_p, divisor * COST_HOP_DIVISOR); } } @@ -193,6 +201,84 @@ update_copy_costs (ira_allocno_t allocno, bool decr_p) update_copy_costs_1 (allocno, ALLOCNO_HARD_REGNO (allocno), decr_p, 1); } +/* This recursive function updates COSTS (decrease if DECR_P) by + conflict costs of the unassigned allocnos connected by copies with + ALLOCNO. This update increases chances to remove some copies. + Copy cost is proportional to the copy frequency divided by + DIVISOR. */ +static void +update_conflict_hard_regno_costs (int *costs, ira_allocno_t allocno, + int divisor, bool decr_p) +{ + int i, cost, class_size, mult, div; + int *conflict_costs; + bool cont_p; + enum machine_mode mode; + enum reg_class cover_class; + ira_allocno_t another_allocno; + ira_copy_t cp, next_cp; + + cover_class = ALLOCNO_COVER_CLASS (allocno); + /* Probably 5 hops will be enough. */ + if (divisor > (COST_HOP_DIVISOR * COST_HOP_DIVISOR + * COST_HOP_DIVISOR * COST_HOP_DIVISOR * COST_HOP_DIVISOR)) + return; + if (cover_class == NO_REGS) + return; + /* Check that it was already visited. */ + if (allocno_update_cost_check[ALLOCNO_NUM (allocno)] == update_cost_check) + return; + allocno_update_cost_check[ALLOCNO_NUM (allocno)] = update_cost_check; + mode = ALLOCNO_MODE (allocno); + class_size = ira_class_hard_regs_num[cover_class]; + for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) + { + if (cp->first == allocno) + { + next_cp = cp->next_first_allocno_copy; + another_allocno = cp->second; + } + else if (cp->second == allocno) + { + next_cp = cp->next_second_allocno_copy; + another_allocno = cp->first; + } + else + gcc_unreachable (); + if (cover_class != ALLOCNO_COVER_CLASS (another_allocno) + || ALLOCNO_ASSIGNED_P (another_allocno) + || ALLOCNO_MAY_BE_SPILLED_P (another_allocno)) + continue; + ira_allocate_and_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), + cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); + conflict_costs + = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); + if (conflict_costs == NULL) + cont_p = true; + else + { + ira_assert (ALLOCNO_FREQ (another_allocno) != 0); + mult = cp->freq; + div = ALLOCNO_FREQ (another_allocno) * divisor; + cont_p = false; + for (i = class_size - 1; i >= 0; i--) + { + cost = conflict_costs [i] * mult / div; + if (cost == 0) + continue; + cont_p = true; + if (decr_p) + cost = -cost; + costs[i] += cost; + } + } + if (cont_p) + update_conflict_hard_regno_costs (costs, another_allocno, + divisor * COST_HOP_DIVISOR, decr_p); + } +} + /* Sort allocnos according to the profit of usage of a hard register instead of memory for them. */ static int @@ -246,9 +332,7 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p) enum reg_class cover_class, rclass; enum machine_mode mode; ira_allocno_t a, conflict_allocno; - ira_allocno_t another_allocno; ira_allocno_conflict_iterator aci; - ira_copy_t cp, next_cp; static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER]; #ifdef STACK_REGS bool no_stack_reg_p; @@ -333,42 +417,30 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p) if (conflict_costs != NULL) for (j = class_size - 1; j >= 0; j--) full_costs[j] -= conflict_costs[j]; + VEC_safe_push (ira_allocno_t, heap, conflict_allocno_vec, + conflict_allocno); } } if (a == allocno) break; } - /* Take copies into account. */ + /* Take into account preferences of allocnos connected by copies to + the conflict allocnos. */ + update_cost_check++; + while (VEC_length (ira_allocno_t, conflict_allocno_vec) != 0) + { + conflict_allocno = VEC_pop (ira_allocno_t, conflict_allocno_vec); + update_conflict_hard_regno_costs (full_costs, conflict_allocno, + COST_HOP_DIVISOR, true); + } + update_cost_check++; + /* Take preferences of allocnos connected by copies into + account. */ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) { - for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) - { - if (cp->first == a) - { - next_cp = cp->next_first_allocno_copy; - another_allocno = cp->second; - } - else if (cp->second == a) - { - next_cp = cp->next_second_allocno_copy; - another_allocno = cp->first; - } - else - gcc_unreachable (); - if (cover_class != ALLOCNO_COVER_CLASS (another_allocno) - || ALLOCNO_ASSIGNED_P (another_allocno)) - continue; - ira_allocate_and_copy_costs - (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), - cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); - conflict_costs - = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); - if (conflict_costs != NULL - && ! ALLOCNO_MAY_BE_SPILLED_P (another_allocno)) - for (j = class_size - 1; j >= 0; j--) - full_costs[j] += conflict_costs[j]; - } + update_conflict_hard_regno_costs (full_costs, a, + COST_HOP_DIVISOR, false); if (a == allocno) break; } @@ -1534,13 +1606,13 @@ print_loop_title (ira_loop_tree_node_t loop_tree_node) ira_assert (loop_tree_node->loop != NULL); fprintf (ira_dump_file, - "\n Loop %d (parent %d, header bb%d, depth %d)\n ref:", + "\n Loop %d (parent %d, header bb%d, depth %d)\n all:", loop_tree_node->loop->num, (loop_tree_node->parent == NULL ? -1 : loop_tree_node->parent->loop->num), loop_tree_node->loop->header->index, loop_depth (loop_tree_node->loop)); - EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi) + EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi) fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j])); fprintf (ira_dump_file, "\n modified regnos:"); EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi) @@ -1582,8 +1654,7 @@ color_pass (ira_loop_tree_node_t loop_tree_node) if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) print_loop_title (loop_tree_node); - bitmap_copy (coloring_allocno_bitmap, loop_tree_node->mentioned_allocnos); - bitmap_ior_into (coloring_allocno_bitmap, loop_tree_node->border_allocnos); + bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos); bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap); EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) { @@ -1597,7 +1668,7 @@ color_pass (ira_loop_tree_node_t loop_tree_node) /* Process caps. They are processed just once. */ if (flag_ira_algorithm == IRA_ALGORITHM_MIXED || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL) - EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi) + EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi) { a = ira_allocnos[j]; if (ALLOCNO_CAP_MEMBER (a) == NULL) @@ -1653,12 +1724,11 @@ color_pass (ira_loop_tree_node_t loop_tree_node) if (subloop_allocno == NULL || ALLOCNO_CAP (subloop_allocno) != NULL) continue; - if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED - && (loop_tree_node->reg_pressure[rclass] - <= ira_available_class_regs[rclass])) - || (hard_regno < 0 - && ! bitmap_bit_p (subloop_node->mentioned_allocnos, - ALLOCNO_NUM (subloop_allocno)))) + ira_assert (bitmap_bit_p (subloop_node->all_allocnos, + ALLOCNO_NUM (subloop_allocno))); + if (flag_ira_algorithm == IRA_ALGORITHM_MIXED + && (loop_tree_node->reg_pressure[rclass] + <= ira_available_class_regs[rclass])) { if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) { @@ -2853,6 +2923,7 @@ void ira_color (void) { allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num); + conflict_allocno_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num); removed_splay_allocno_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num); memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p)); @@ -2860,6 +2931,7 @@ ira_color (void) do_coloring (); ira_finish_assign (); VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec); + VEC_free (ira_allocno_t, heap, conflict_allocno_vec); VEC_free (ira_allocno_t, heap, allocno_stack_vec); move_spill_restore (); } |