summaryrefslogtreecommitdiff
path: root/gcc/ira-color.c
diff options
context:
space:
mode:
authorbstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4>2008-09-04 13:11:52 +0000
committerbstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4>2008-09-04 13:11:52 +0000
commited1d171006e8f6c4403232e075b3e8455a19299a (patch)
tree883e632907dd1f7e877229c0ea962daf81725fa6 /gcc/ira-color.c
parent2ca603eacebf3a9902742389a1fe68c6a6bb6c0e (diff)
downloadgcc-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.c156
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 ();
}
View Lorry Controller Status