/* Building internal representation for IRA.
- Copyright (C) 2006, 2007, 2008
+ Copyright (C) 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
array. */
ira_loop_tree_node_t ira_loop_nodes;
-/* Map regno -> allocnos with given regno (see comments for
+/* Map regno -> allocnos with given regno (see comments for
allocno member `next_regno_allocno'). */
ira_allocno_t *ira_regno_allocno_map;
ira_loop_nodes[i].children = NULL;
ira_loop_nodes[i].subloops = NULL;
}
- FOR_EACH_BB_REVERSE (bb)
+ FOR_EACH_BB (bb)
{
bb_node = &ira_bb_nodes[bb->index];
bb_node->bb = bb;
COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
ALLOCNO_NREFS (a) = 0;
- ALLOCNO_FREQ (a) = 1;
+ ALLOCNO_FREQ (a) = 0;
ALLOCNO_HARD_REGNO (a) = -1;
ALLOCNO_CALL_FREQ (a) = 0;
ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
ALLOCNO_CHILD_RENAMED_P (a) = false;
ALLOCNO_DONT_REASSIGN_P (a) = false;
+ ALLOCNO_BAD_SPILL_P (a) = false;
ALLOCNO_IN_GRAPH_P (a) = false;
ALLOCNO_ASSIGNED_P (a) = false;
ALLOCNO_MAY_BE_SPILLED_P (a) = false;
ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
- ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
+ ALLOCNO_LEFT_CONFLICTS_SIZE (a) = -1;
ALLOCNO_COVER_CLASS (a) = NO_REGS;
+ ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0;
ALLOCNO_COVER_CLASS_COST (a) = 0;
ALLOCNO_MEMORY_COST (a) = 0;
ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
ALLOCNO_CAP (a) = cap;
ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
- ALLOCNO_UPDATED_MEMORY_COST (cap) = ALLOCNO_UPDATED_MEMORY_COST (a);
ira_allocate_and_copy_costs
(&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
ira_allocate_and_copy_costs
(&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), cover_class,
ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
+ ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
/* Copy allocno live range list given by its head R and return the
result. */
-static allocno_live_range_t
-copy_allocno_live_range_list (allocno_live_range_t r)
+allocno_live_range_t
+ira_copy_allocno_live_range_list (allocno_live_range_t r)
{
allocno_live_range_t p, first, last;
return first;
}
+/* Merge ranges R1 and R2 and returns the result. The function
+ maintains the order of ranges and tries to minimize number of the
+ result ranges. */
+allocno_live_range_t
+ira_merge_allocno_live_ranges (allocno_live_range_t r1,
+ allocno_live_range_t r2)
+{
+ allocno_live_range_t first, last, temp;
+
+ if (r1 == NULL)
+ return r2;
+ if (r2 == NULL)
+ return r1;
+ for (first = last = NULL; r1 != NULL && r2 != NULL;)
+ {
+ if (r1->start < r2->start)
+ {
+ temp = r1;
+ r1 = r2;
+ r2 = temp;
+ }
+ if (r1->start <= r2->finish + 1)
+ {
+ /* Intersected ranges: merge r1 and r2 into r1. */
+ r1->start = r2->start;
+ if (r1->finish < r2->finish)
+ r1->finish = r2->finish;
+ temp = r2;
+ r2 = r2->next;
+ ira_finish_allocno_live_range (temp);
+ if (r2 == NULL)
+ {
+ /* To try to merge with subsequent ranges in r1. */
+ r2 = r1->next;
+ r1->next = NULL;
+ }
+ }
+ else
+ {
+ /* Add r1 to the result. */
+ if (first == NULL)
+ first = last = r1;
+ else
+ {
+ last->next = r1;
+ last = r1;
+ }
+ r1 = r1->next;
+ if (r1 == NULL)
+ {
+ /* To try to merge with subsequent ranges in r2. */
+ r1 = r2->next;
+ r2->next = NULL;
+ }
+ }
+ }
+ if (r1 != NULL)
+ {
+ if (first == NULL)
+ first = r1;
+ else
+ last->next = r1;
+ ira_assert (r1->next == NULL);
+ }
+ else if (r2 != NULL)
+ {
+ if (first == NULL)
+ first = r2;
+ else
+ last->next = r2;
+ ira_assert (r2->next == NULL);
+ }
+ else
+ {
+ ira_assert (last->next == NULL);
+ }
+ return first;
+}
+
+/* Return TRUE if live ranges R1 and R2 intersect. */
+bool
+ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1,
+ allocno_live_range_t r2)
+{
+ /* Remember the live ranges are always kept ordered. */
+ while (r1 != NULL && r2 != NULL)
+ {
+ if (r1->start > r2->finish)
+ r1 = r1->next;
+ else if (r2->start > r1->finish)
+ r2 = r2->next;
+ else
+ return true;
+ }
+ return false;
+}
+
/* Free allocno live range R. */
void
ira_finish_allocno_live_range (allocno_live_range_t r)
pool_free (allocno_live_range_pool, r);
}
+/* Free list of allocno live ranges starting with R. */
+void
+ira_finish_allocno_live_range_list (allocno_live_range_t r)
+{
+ allocno_live_range_t next_r;
+
+ for (; r != NULL; r = next_r)
+ {
+ next_r = r->next;
+ ira_finish_allocno_live_range (r);
+ }
+}
+
/* Free updated register costs of allocno A. */
void
ira_free_allocno_updated_costs (ira_allocno_t a)
static void
finish_allocno (ira_allocno_t a)
{
- allocno_live_range_t r, next_r;
enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
ira_allocnos[ALLOCNO_NUM (a)] = NULL;
if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
cover_class);
- for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = next_r)
- {
- next_r = r->next;
- ira_finish_allocno_live_range (r);
- }
+ ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
pool_free (allocno_pool, a);
}
}
/* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
- SECOND, FREQ, and INSN. */
+ SECOND, FREQ, CONSTRAINT_P, and INSN. */
ira_copy_t
-ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq, rtx insn,
+ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
+ bool constraint_p, rtx insn,
ira_loop_tree_node_t loop_tree_node)
{
ira_copy_t cp;
cp->first = first;
cp->second = second;
cp->freq = freq;
+ cp->constraint_p = constraint_p;
cp->insn = insn;
cp->loop_tree_node = loop_tree_node;
VEC_safe_push (ira_copy_t, heap, copy_vec, cp);
LOOP_TREE_NODE. */
ira_copy_t
ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
- rtx insn, ira_loop_tree_node_t loop_tree_node)
+ bool constraint_p, rtx insn,
+ ira_loop_tree_node_t loop_tree_node)
{
ira_copy_t cp;
cp->freq += freq;
return cp;
}
- cp = ira_create_copy (first, second, freq, insn, loop_tree_node);
+ cp = ira_create_copy (first, second, freq, constraint_p, insn,
+ loop_tree_node);
ira_assert (first != NULL && second != NULL);
ira_add_allocno_copy_to_list (cp);
ira_swap_allocno_copy_ends_if_necessary (cp);
return cp;
}
+/* Print info about copy CP into file F. */
+static void
+print_copy (FILE *f, ira_copy_t cp)
+{
+ fprintf (f, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
+ ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
+ ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
+ cp->insn != NULL
+ ? "move" : cp->constraint_p ? "constraint" : "shuffle");
+}
+
+/* Print info about copy CP into stderr. */
+void
+ira_debug_copy (ira_copy_t cp)
+{
+ print_copy (stderr, cp);
+}
+
+/* Print info about all copies into file F. */
+static void
+print_copies (FILE *f)
+{
+ ira_copy_t cp;
+ ira_copy_iterator ci;
+
+ FOR_EACH_COPY (cp, ci)
+ print_copy (f, cp);
+}
+
+/* Print info about all copies into stderr. */
+void
+ira_debug_copies (void)
+{
+ print_copies (stderr);
+}
+
/* Print info about copies involving allocno A into file F. */
static void
print_allocno_copies (FILE *f, ira_allocno_t a)
if (preorder_func != NULL)
(*preorder_func) (loop_node);
-
+
if (bb_p)
for (subloop_node = loop_node->children;
subloop_node != NULL;
{
if (preorder_func != NULL)
(*preorder_func) (subloop_node);
-
+
if (postorder_func != NULL)
(*postorder_func) (subloop_node);
}
-
+
for (subloop_node = loop_node->subloops;
subloop_node != NULL;
subloop_node = subloop_node->subloop_next)
if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
-
+
ALLOCNO_NREFS (a)++;
ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
if (output_p)
create_insn_allocnos (XEXP (x, 0), false);
return;
}
- else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
+ else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
{
create_insn_allocnos (XEXP (x, 0), true);
curr_bb = bb = bb_node->bb;
ira_assert (bb != NULL);
- FOR_BB_INSNS (bb, insn)
- if (INSN_P (insn))
+ FOR_BB_INSNS_REVERSE (bb, insn)
+ if (NONDEBUG_INSN_P (insn))
create_insn_allocnos (PATTERN (insn), false);
/* It might be a allocno living through from one subloop to
another. */
FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
if (e->src != loop_node->loop->latch)
create_loop_allocnos (e);
-
+
edges = get_loop_exit_edges (loop_node->loop);
for (i = 0; VEC_iterate (edge, edges, i, e); i++)
create_loop_allocnos (e);
ira_loop_tree_node_t parent;
enum reg_class cover_class;
- if (flag_ira_algorithm != IRA_ALGORITHM_REGIONAL
- && flag_ira_algorithm != IRA_ALGORITHM_MIXED)
+ if (flag_ira_region != IRA_REGION_ALL
+ && flag_ira_region != IRA_REGION_MIXED)
return;
for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
for (a = ira_regno_allocno_map[i];
&& bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
ALLOCNO_NUM (a)))
{
+ if (! ALLOCNO_BAD_SPILL_P (a))
+ ALLOCNO_BAD_SPILL_P (parent_a) = false;
ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
ALLOCNO_COVER_CLASS_COST (parent_a)
+= ALLOCNO_COVER_CLASS_COST (a);
ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
- ALLOCNO_UPDATED_MEMORY_COST (parent_a)
- += ALLOCNO_UPDATED_MEMORY_COST (a);
}
}
will hardly improve the result. As a result we speed up regional
register allocation. */
-/* Merge ranges R1 and R2 and returns the result. The function
- maintains the order of ranges and tries to minimize number of the
- result ranges. */
-static allocno_live_range_t
-merge_ranges (allocno_live_range_t r1, allocno_live_range_t r2)
-{
- allocno_live_range_t first, last, temp;
-
- if (r1 == NULL)
- return r2;
- if (r2 == NULL)
- return r1;
- for (first = last = NULL; r1 != NULL && r2 != NULL;)
- {
- if (r1->start < r2->start)
- {
- temp = r1;
- r1 = r2;
- r2 = temp;
- }
- if (r1->start <= r2->finish + 1)
- {
- /* Intersected ranges: merge r1 and r2 into r1. */
- r1->start = r2->start;
- if (r1->finish < r2->finish)
- r1->finish = r2->finish;
- temp = r2;
- r2 = r2->next;
- ira_finish_allocno_live_range (temp);
- if (r2 == NULL)
- {
- /* To try to merge with subsequent ranges in r1. */
- r2 = r1->next;
- r1->next = NULL;
- }
- }
- else
- {
- /* Add r1 to the result. */
- if (first == NULL)
- first = last = r1;
- else
- {
- last->next = r1;
- last = r1;
- }
- r1 = r1->next;
- if (r1 == NULL)
- {
- /* To try to merge with subsequent ranges in r2. */
- r1 = r2->next;
- r2->next = NULL;
- }
- }
- }
- if (r1 != NULL)
- {
- if (first == NULL)
- first = r1;
- else
- last->next = r1;
- ira_assert (r1->next == NULL);
- }
- else if (r2 != NULL)
- {
- if (first == NULL)
- first = r2;
- else
- last->next = r2;
- ira_assert (r2->next == NULL);
- }
- else
- {
- ira_assert (last->next == NULL);
- }
- return first;
-}
-
/* The function changes allocno in range list given by R onto A. */
static void
change_allocno_in_range_list (allocno_live_range_t r, ira_allocno_t a)
{
int i;
enum reg_class cover_class;
-
+
if (node->bb != NULL)
return false;
-
+
for (i = 0; i < ira_reg_class_cover_size; i++)
{
cover_class = ira_reg_class_cover[i];
return true;
}
-/* Return TRUE if NODE represents a loop with should be removed from
- regional allocation. We remove a loop with low register pressure
- inside another loop with register pressure. In this case a
- separate allocation of the loop hardly helps (for irregular
- register file architecture it could help by choosing a better hard
- register in the loop but we prefer faster allocation even in this
- case). */
-static bool
-loop_node_to_be_removed_p (ira_loop_tree_node_t node)
+/* Sort loops for marking them for removal. We put already marked
+ loops first, then less frequent loops next, and then outer loops
+ next. */
+static int
+loop_compare_func (const void *v1p, const void *v2p)
+{
+ int diff;
+ ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
+ ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
+
+ ira_assert (l1->parent != NULL && l2->parent != NULL);
+ if (l1->to_remove_p && ! l2->to_remove_p)
+ return -1;
+ if (! l1->to_remove_p && l2->to_remove_p)
+ return 1;
+ if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
+ return diff;
+ if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
+ return diff;
+ /* Make sorting stable. */
+ return l1->loop->num - l2->loop->num;
+}
+
+
+/* Mark loops which should be removed from regional allocation. We
+ remove a loop with low register pressure inside another loop with
+ register pressure. In this case a separate allocation of the loop
+ hardly helps (for irregular register file architecture it could
+ help by choosing a better hard register in the loop but we prefer
+ faster allocation even in this case). We also remove cheap loops
+ if there are more than IRA_MAX_LOOPS_NUM of them. */
+static void
+mark_loops_for_removal (void)
{
- return (node->parent != NULL && low_pressure_loop_node_p (node->parent)
- && low_pressure_loop_node_p (node));
+ int i, n;
+ ira_loop_tree_node_t *sorted_loops;
+ loop_p loop;
+
+ sorted_loops
+ = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
+ * VEC_length (loop_p,
+ ira_loops.larray));
+ for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
+ if (ira_loop_nodes[i].regno_allocno_map != NULL)
+ {
+ if (ira_loop_nodes[i].parent == NULL)
+ {
+ /* Don't remove the root. */
+ ira_loop_nodes[i].to_remove_p = false;
+ continue;
+ }
+ sorted_loops[n++] = &ira_loop_nodes[i];
+ ira_loop_nodes[i].to_remove_p
+ = (low_pressure_loop_node_p (ira_loop_nodes[i].parent)
+ && low_pressure_loop_node_p (&ira_loop_nodes[i]));
+ }
+ qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
+ for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
+ {
+ sorted_loops[i]->to_remove_p = true;
+ if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
+ fprintf
+ (ira_dump_file,
+ " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
+ sorted_loops[i]->loop->num, sorted_loops[i]->loop->header->index,
+ sorted_loops[i]->loop->header->frequency,
+ loop_depth (sorted_loops[i]->loop),
+ low_pressure_loop_node_p (sorted_loops[i]->parent)
+ && low_pressure_loop_node_p (sorted_loops[i])
+ ? "low pressure" : "cheap loop");
+ }
+ ira_free (sorted_loops);
+}
+
+/* Mark all loops but root for removing. */
+static void
+mark_all_loops_for_removal (void)
+{
+ int i;
+ loop_p loop;
+
+ for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
+ if (ira_loop_nodes[i].regno_allocno_map != NULL)
+ {
+ if (ira_loop_nodes[i].parent == NULL)
+ {
+ /* Don't remove the root. */
+ ira_loop_nodes[i].to_remove_p = false;
+ continue;
+ }
+ ira_loop_nodes[i].to_remove_p = true;
+ if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
+ fprintf
+ (ira_dump_file,
+ " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
+ ira_loop_nodes[i].loop->num,
+ ira_loop_nodes[i].loop->header->index,
+ ira_loop_nodes[i].loop->header->frequency,
+ loop_depth (ira_loop_nodes[i].loop));
+ }
}
/* Definition of vector of loop tree nodes. */
bool remove_p;
ira_loop_tree_node_t subnode;
- remove_p = loop_node_to_be_removed_p (node);
+ remove_p = node->to_remove_p;
if (! remove_p)
VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
start = VEC_length (ira_loop_tree_node_t, children_vec);
}
}
+/* Return TRUE if NODE is inside PARENT. */
+static bool
+loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
+{
+ for (node = node->parent; node != NULL; node = node->parent)
+ if (node == parent)
+ return true;
+ return false;
+}
+
+/* Sort allocnos according to their order in regno allocno list. */
+static int
+regno_allocno_order_compare_func (const void *v1p, const void *v2p)
+{
+ ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
+ ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
+ ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
+ ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
+
+ if (loop_is_inside_p (n1, n2))
+ return -1;
+ else if (loop_is_inside_p (n2, n1))
+ return 1;
+ /* If allocnos are equally good, sort by allocno numbers, so that
+ the results of qsort leave nothing to chance. We put allocnos
+ with higher number first in the list because it is the original
+ order for allocnos from loops on the same levels. */
+ return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
+}
+
+/* This array is used to sort allocnos to restore allocno order in
+ the regno allocno list. */
+static ira_allocno_t *regno_allocnos;
+
+/* Restore allocno order for REGNO in the regno allocno list. */
+static void
+ira_rebuild_regno_allocno_list (int regno)
+{
+ int i, n;
+ ira_allocno_t a;
+
+ for (n = 0, a = ira_regno_allocno_map[regno];
+ a != NULL;
+ a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
+ regno_allocnos[n++] = a;
+ ira_assert (n > 0);
+ qsort (regno_allocnos, n, sizeof (ira_allocno_t),
+ regno_allocno_order_compare_func);
+ for (i = 1; i < n; i++)
+ ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
+ ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
+ ira_regno_allocno_map[regno] = regno_allocnos[0];
+ if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
+}
+
+/* Propagate info from allocno FROM_A to allocno A. */
+static void
+propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
+{
+ enum reg_class cover_class;
+
+ IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
+ ALLOCNO_CONFLICT_HARD_REGS (from_a));
+#ifdef STACK_REGS
+ if (ALLOCNO_NO_STACK_REG_P (from_a))
+ ALLOCNO_NO_STACK_REG_P (a) = true;
+#endif
+ ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
+ ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
+ ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
+ IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
+ ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from_a));
+ ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
+ ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
+ += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
+ if (! ALLOCNO_BAD_SPILL_P (from_a))
+ ALLOCNO_BAD_SPILL_P (a) = false;
+#ifdef STACK_REGS
+ if (ALLOCNO_TOTAL_NO_STACK_REG_P (from_a))
+ ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
+#endif
+ cover_class = ALLOCNO_COVER_CLASS (from_a);
+ ira_assert (cover_class == ALLOCNO_COVER_CLASS (a));
+ ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
+ ALLOCNO_HARD_REG_COSTS (from_a));
+ ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
+ cover_class,
+ ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
+ ALLOCNO_COVER_CLASS_COST (a) += ALLOCNO_COVER_CLASS_COST (from_a);
+ ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
+}
+
/* Remove allocnos from loops removed from the allocation
consideration. */
static void
remove_unnecessary_allocnos (void)
{
int regno;
- bool merged_p;
- enum reg_class cover_class;
+ bool merged_p, rebuild_p;
ira_allocno_t a, prev_a, next_a, parent_a;
ira_loop_tree_node_t a_node, parent;
allocno_live_range_t r;
merged_p = false;
+ regno_allocnos = NULL;
for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
- for (prev_a = NULL, a = ira_regno_allocno_map[regno];
- a != NULL;
- a = next_a)
- {
- next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
- a_node = ALLOCNO_LOOP_TREE_NODE (a);
- if (! loop_node_to_be_removed_p (a_node))
- prev_a = a;
- else
- {
- for (parent = a_node->parent;
- (parent_a = parent->regno_allocno_map[regno]) == NULL
- && loop_node_to_be_removed_p (parent);
- parent = parent->parent)
- ;
- if (parent_a == NULL)
- {
- /* There are no allocnos with the same regno in upper
- region -- just move the allocno to the upper
- region. */
- prev_a = a;
- ALLOCNO_LOOP_TREE_NODE (a) = parent;
- parent->regno_allocno_map[regno] = a;
- bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
- }
- else
- {
- /* Remove the allocno and update info of allocno in
- the upper region. */
- if (prev_a == NULL)
- ira_regno_allocno_map[regno] = next_a;
- else
- ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
- r = ALLOCNO_LIVE_RANGES (a);
- change_allocno_in_range_list (r, parent_a);
- ALLOCNO_LIVE_RANGES (parent_a)
- = merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
- merged_p = true;
- ALLOCNO_LIVE_RANGES (a) = NULL;
- IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a),
- ALLOCNO_CONFLICT_HARD_REGS (a));
-#ifdef STACK_REGS
- if (ALLOCNO_NO_STACK_REG_P (a))
- ALLOCNO_NO_STACK_REG_P (parent_a) = true;
-#endif
- ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
- ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
- ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
- IOR_HARD_REG_SET
- (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
- ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
- ALLOCNO_CALLS_CROSSED_NUM (parent_a)
- += ALLOCNO_CALLS_CROSSED_NUM (a);
- ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
- += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+ {
+ rebuild_p = false;
+ for (prev_a = NULL, a = ira_regno_allocno_map[regno];
+ a != NULL;
+ a = next_a)
+ {
+ next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
+ a_node = ALLOCNO_LOOP_TREE_NODE (a);
+ if (! a_node->to_remove_p)
+ prev_a = a;
+ else
+ {
+ for (parent = a_node->parent;
+ (parent_a = parent->regno_allocno_map[regno]) == NULL
+ && parent->to_remove_p;
+ parent = parent->parent)
+ ;
+ if (parent_a == NULL)
+ {
+ /* There are no allocnos with the same regno in
+ upper region -- just move the allocno to the
+ upper region. */
+ prev_a = a;
+ ALLOCNO_LOOP_TREE_NODE (a) = parent;
+ parent->regno_allocno_map[regno] = a;
+ bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
+ rebuild_p = true;
+ }
+ else
+ {
+ /* Remove the allocno and update info of allocno in
+ the upper region. */
+ if (prev_a == NULL)
+ ira_regno_allocno_map[regno] = next_a;
+ else
+ ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
+ r = ALLOCNO_LIVE_RANGES (a);
+ change_allocno_in_range_list (r, parent_a);
+ ALLOCNO_LIVE_RANGES (parent_a)
+ = ira_merge_allocno_live_ranges
+ (r, ALLOCNO_LIVE_RANGES (parent_a));
+ merged_p = true;
+ ALLOCNO_LIVE_RANGES (a) = NULL;
+ propagate_some_info_from_allocno (parent_a, a);
+ /* Remove it from the corresponding regno allocno
+ map to avoid info propagation of subsequent
+ allocno into this already removed allocno. */
+ a_node->regno_allocno_map[regno] = NULL;
+ finish_allocno (a);
+ }
+ }
+ }
+ if (rebuild_p)
+ /* We need to restore the order in regno allocno list. */
+ {
+ if (regno_allocnos == NULL)
+ regno_allocnos
+ = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
+ * ira_allocnos_num);
+ ira_rebuild_regno_allocno_list (regno);
+ }
+ }
+ if (merged_p)
+ ira_rebuild_start_finish_chains ();
+ if (regno_allocnos != NULL)
+ ira_free (regno_allocnos);
+}
+
+/* Remove allocnos from all loops but the root. */
+static void
+remove_low_level_allocnos (void)
+{
+ int regno;
+ bool merged_p, propagate_p;
+ ira_allocno_t a, top_a;
+ ira_loop_tree_node_t a_node, parent;
+ allocno_live_range_t r;
+ ira_allocno_iterator ai;
+
+ merged_p = false;
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ a_node = ALLOCNO_LOOP_TREE_NODE (a);
+ if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
+ continue;
+ regno = ALLOCNO_REGNO (a);
+ if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
+ {
+ ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
+ ira_loop_tree_root->regno_allocno_map[regno] = a;
+ continue;
+ }
+ propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
+ /* Remove the allocno and update info of allocno in the upper
+ region. */
+ r = ALLOCNO_LIVE_RANGES (a);
+ change_allocno_in_range_list (r, top_a);
+ ALLOCNO_LIVE_RANGES (top_a)
+ = ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (top_a));
+ merged_p = true;
+ ALLOCNO_LIVE_RANGES (a) = NULL;
+ if (propagate_p)
+ propagate_some_info_from_allocno (top_a, a);
+ }
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ a_node = ALLOCNO_LOOP_TREE_NODE (a);
+ if (a_node == ira_loop_tree_root)
+ continue;
+ parent = a_node->parent;
+ regno = ALLOCNO_REGNO (a);
+ if (ALLOCNO_CAP_MEMBER (a) != NULL)
+ ira_assert (ALLOCNO_CAP (a) != NULL);
+ else if (ALLOCNO_CAP (a) == NULL)
+ ira_assert (parent->regno_allocno_map[regno] != NULL);
+ }
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ regno = ALLOCNO_REGNO (a);
+ if (ira_loop_tree_root->regno_allocno_map[regno] == a)
+ {
+ ira_regno_allocno_map[regno] = a;
+ ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
+ ALLOCNO_CAP_MEMBER (a) = NULL;
+ COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
+ ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
#ifdef STACK_REGS
- if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
- ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
+ if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
+ ALLOCNO_NO_STACK_REG_P (a) = true;
#endif
- cover_class = ALLOCNO_COVER_CLASS (a);
- ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
- ira_allocate_and_accumulate_costs
- (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
- ALLOCNO_HARD_REG_COSTS (a));
- ira_allocate_and_accumulate_costs
- (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
- cover_class,
- ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
- ALLOCNO_COVER_CLASS_COST (parent_a)
- += ALLOCNO_COVER_CLASS_COST (a);
- ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
- ALLOCNO_UPDATED_MEMORY_COST (parent_a)
- += ALLOCNO_UPDATED_MEMORY_COST (a);
- finish_allocno (a);
- }
- }
- }
+ }
+ else
+ finish_allocno (a);
+ }
if (merged_p)
ira_rebuild_start_finish_chains ();
}
-/* Remove loops from consideration. We remove loops for which a
- separate allocation will not improve the result. We have to do
- this after allocno creation and their costs and cover class
- evaluation because only after that the register pressure can be
- known and is calculated. */
+/* Remove loops from consideration. We remove all loops except for
+ root if ALL_P or loops for which a separate allocation will not
+ improve the result. We have to do this after allocno creation and
+ their costs and cover class evaluation because only after that the
+ register pressure can be known and is calculated. */
static void
-remove_unnecessary_regions (void)
+remove_unnecessary_regions (bool all_p)
{
+ if (all_p)
+ mark_all_loops_for_removal ();
+ else
+ mark_loops_for_removal ();
children_vec
= VEC_alloc (ira_loop_tree_node_t, heap,
last_basic_block + VEC_length (loop_p, ira_loops.larray));
last_basic_block + VEC_length (loop_p, ira_loops.larray));
remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
VEC_free (ira_loop_tree_node_t, heap, children_vec);
- remove_unnecessary_allocnos ();
+ if (all_p)
+ remove_low_level_allocnos ();
+ else
+ remove_unnecessary_allocnos ();
while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
\f
+/* At this point true value of allocno attribute bad_spill_p means
+ that there is an insn where allocno occurs and where the allocno
+ can not be used as memory. The function updates the attribute, now
+ it can be true only for allocnos which can not be used as memory in
+ an insn and in whose live ranges there is other allocno deaths.
+ Spilling allocnos with true value will not improve the code because
+ it will not make other allocnos colorable and additional reloads
+ for the corresponding pseudo will be generated in reload pass for
+ each insn it occurs.
+
+ This is a trick mentioned in one classic article of Chaitin etc
+ which is frequently omitted in other implementations of RA based on
+ graph coloring. */
+static void
+update_bad_spill_attribute (void)
+{
+ int i;
+ ira_allocno_t a;
+ ira_allocno_iterator ai;
+ allocno_live_range_t r;
+ enum reg_class cover_class;
+ bitmap_head dead_points[N_REG_CLASSES];
+
+ for (i = 0; i < ira_reg_class_cover_size; i++)
+ {
+ cover_class = ira_reg_class_cover[i];
+ bitmap_initialize (&dead_points[cover_class], ®_obstack);
+ }
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ cover_class = ALLOCNO_COVER_CLASS (a);
+ if (cover_class == NO_REGS)
+ continue;
+ for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
+ bitmap_set_bit (&dead_points[cover_class], r->finish);
+ }
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ cover_class = ALLOCNO_COVER_CLASS (a);
+ if (cover_class == NO_REGS)
+ continue;
+ if (! ALLOCNO_BAD_SPILL_P (a))
+ continue;
+ for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
+ {
+ for (i = r->start + 1; i < r->finish; i++)
+ if (bitmap_bit_p (&dead_points[cover_class], i))
+ break;
+ if (i < r->finish)
+ break;
+ }
+ if (r != NULL)
+ ALLOCNO_BAD_SPILL_P (a) = false;
+ }
+ for (i = 0; i < ira_reg_class_cover_size; i++)
+ {
+ cover_class = ira_reg_class_cover[i];
+ bitmap_clear (&dead_points[cover_class]);
+ }
+}
+
+\f
+
/* Set up minimal and maximal live range points for allocnos. */
static void
setup_min_max_allocno_live_range_point (void)
}
/* Sort allocnos according to their live ranges. Allocnos with
- smaller cover class are put first. Allocnos with the same cove
- class are ordered according their start (min). Allocnos with the
- same start are ordered according their finish (max). */
+ smaller cover class are put first unless we use priority coloring.
+ Allocnos with the same cove class are ordered according their start
+ (min). Allocnos with the same start are ordered according their
+ finish (max). */
static int
allocno_range_compare_func (const void *v1p, const void *v2p)
{
ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
- if ((diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
+ if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
+ && (diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
return diff;
if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
return diff;
static void
setup_min_max_conflict_allocno_ids (void)
{
- enum reg_class cover_class;
+ int cover_class;
int i, j, min, max, start, finish, first_not_finished, filled_area_start;
int *live_range_min, *last_lived;
ira_allocno_t a;
a = ira_conflict_id_allocno_map[i];
if (a == NULL)
continue;
- if (cover_class != ALLOCNO_COVER_CLASS (a))
+ if (cover_class < 0
+ || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
+ && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
{
cover_class = ALLOCNO_COVER_CLASS (a);
min = i;
[first_not_finished]))
first_not_finished++;
min = first_not_finished;
- }
+ }
if (min == i)
/* We could increase min further in this case but it is good
enough. */
a = ira_conflict_id_allocno_map[i];
if (a == NULL)
continue;
- if (cover_class != ALLOCNO_COVER_CLASS (a))
+ if (cover_class < 0
+ || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
+ && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
{
cover_class = ALLOCNO_COVER_CLASS (a);
for (j = 0; j < ira_max_point; j++)
the IR for one region but we don't do it because it takes a lot of
time. */
-/* This recursive function returns immediate common dominator of two
- loop tree nodes N1 and N2. */
-static ira_loop_tree_node_t
-common_loop_tree_node_dominator (ira_loop_tree_node_t n1,
- ira_loop_tree_node_t n2)
-{
- ira_assert (n1 != NULL && n2 != NULL);
- if (n1 == n2)
- return n1;
- if (n1->level < n2->level)
- return common_loop_tree_node_dominator (n1, n2->parent);
- else if (n1->level > n2->level)
- return common_loop_tree_node_dominator (n1->parent, n2);
- else
- return common_loop_tree_node_dominator (n1->parent, n2->parent);
+/* Map: regno -> allocnos which will finally represent the regno for
+ IR with one region. */
+static ira_allocno_t *regno_top_level_allocno_map;
+
+/* Process all allocnos originated from pseudo REGNO and copy live
+ ranges, hard reg conflicts, and allocno stack reg attributes from
+ low level allocnos to final allocnos which are destinations of
+ removed stores at a loop exit. Return true if we copied live
+ ranges. */
+static bool
+copy_info_to_removed_store_destinations (int regno)
+{
+ ira_allocno_t a;
+ ira_allocno_t parent_a = NULL;
+ ira_loop_tree_node_t parent;
+ allocno_live_range_t r;
+ bool merged_p;
+
+ merged_p = false;
+ for (a = ira_regno_allocno_map[regno];
+ a != NULL;
+ a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
+ {
+ if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))])
+ /* This allocno will be removed. */
+ continue;
+ /* Caps will be removed. */
+ ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
+ for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
+ parent != NULL;
+ parent = parent->parent)
+ if ((parent_a = parent->regno_allocno_map[regno]) == NULL
+ || (parent_a == regno_top_level_allocno_map[REGNO (ALLOCNO_REG
+ (parent_a))]
+ && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)))
+ break;
+ if (parent == NULL || parent_a == NULL)
+ continue;
+ if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
+ {
+ fprintf
+ (ira_dump_file,
+ " Coping ranges of a%dr%d to a%dr%d: ",
+ ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
+ ALLOCNO_NUM (parent_a), REGNO (ALLOCNO_REG (parent_a)));
+ ira_print_live_range_list (ira_dump_file,
+ ALLOCNO_LIVE_RANGES (a));
+ }
+ r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
+ change_allocno_in_range_list (r, parent_a);
+ ALLOCNO_LIVE_RANGES (parent_a)
+ = ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
+ IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
+ ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
+#ifdef STACK_REGS
+ if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
+ ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
+#endif
+ ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
+ ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+ += ALLOCNO_CALLS_CROSSED_NUM (a);
+ ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+ += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+ merged_p = true;
+ }
+ return merged_p;
}
/* Flatten the IR. In other words, this function transforms IR as if
ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
{
int i, j, num;
- bool propagate_p, stop_p, keep_p;
+ bool keep_p;
int hard_regs_num;
- bool new_pseudos_p, merged_p;
+ bool new_pseudos_p, merged_p, mem_dest_p;
unsigned int n;
enum reg_class cover_class;
ira_allocno_t a, parent_a, first, second, node_first, node_second;
- ira_allocno_t dominator_a;
ira_copy_t cp;
- ira_loop_tree_node_t parent, node, dominator;
+ ira_loop_tree_node_t parent, node;
allocno_live_range_t r;
ira_allocno_iterator ai;
ira_copy_iterator ci;
sparseset allocnos_live;
- /* Map: regno -> allocnos which will finally represent the regno for
- IR with one region. */
- ira_allocno_t *regno_top_level_allocno_map;
- bool *allocno_propagated_p;
regno_top_level_allocno_map
= (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
memset (regno_top_level_allocno_map, 0,
max_reg_num () * sizeof (ira_allocno_t));
- allocno_propagated_p
- = (bool *) ira_allocate (ira_allocnos_num * sizeof (bool));
- memset (allocno_propagated_p, 0, ira_allocnos_num * sizeof (bool));
new_pseudos_p = merged_p = false;
+ FOR_EACH_ALLOCNO (a, ai)
+ {
+ if (ALLOCNO_CAP_MEMBER (a) != NULL)
+ /* Caps are not in the regno allocno maps and they are never
+ will be transformed into allocnos existing after IR
+ flattening. */
+ continue;
+ COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
+ ALLOCNO_CONFLICT_HARD_REGS (a));
+#ifdef STACK_REGS
+ ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
+#endif
+ }
/* Fix final allocno attributes. */
for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
{
- propagate_p = false;
+ mem_dest_p = false;
for (a = ira_regno_allocno_map[i];
a != NULL;
a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
continue;
}
ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
- if (propagate_p)
+
+ if (ALLOCNO_MEM_OPTIMIZED_DEST (a) != NULL)
+ mem_dest_p = true;
+ if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
{
- if (!allocno_propagated_p [ALLOCNO_NUM (parent_a)])
- COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
- ALLOCNO_CONFLICT_HARD_REGS (parent_a));
IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
#ifdef STACK_REGS
- if (!allocno_propagated_p [ALLOCNO_NUM (parent_a)])
- ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
- = ALLOCNO_NO_STACK_REG_P (parent_a);
- ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
- = (ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
- || ALLOCNO_TOTAL_NO_STACK_REG_P (a));
+ if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
+ ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
#endif
- allocno_propagated_p [ALLOCNO_NUM (parent_a)] = true;
- }
- if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
- {
if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
{
fprintf (ira_dump_file,
}
change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
ALLOCNO_LIVE_RANGES (parent_a)
- = merge_ranges (ALLOCNO_LIVE_RANGES (a),
- ALLOCNO_LIVE_RANGES (parent_a));
+ = ira_merge_allocno_live_ranges
+ (ALLOCNO_LIVE_RANGES (a), ALLOCNO_LIVE_RANGES (parent_a));
merged_p = true;
ALLOCNO_LIVE_RANGES (a) = NULL;
ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
continue;
}
new_pseudos_p = true;
- propagate_p = true;
- first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a;
- stop_p = false;
for (;;)
{
- if (first == NULL
- && ALLOCNO_MEM_OPTIMIZED_DEST (parent_a) != NULL)
- first = parent_a;
ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
- if (first != NULL
- && ALLOCNO_MEM_OPTIMIZED_DEST (first) == parent_a)
- stop_p = true;
- else if (!stop_p)
- {
- ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
- ALLOCNO_CALLS_CROSSED_NUM (parent_a)
- -= ALLOCNO_CALLS_CROSSED_NUM (a);
- ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
- -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
- }
+ ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
+ ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+ -= ALLOCNO_CALLS_CROSSED_NUM (a);
+ ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+ -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
&& ALLOCNO_NREFS (parent_a) >= 0
&& ALLOCNO_FREQ (parent_a) >= 0);
[ALLOCNO_REGNO (parent_a)])) == NULL)
break;
}
- if (first != NULL)
- {
- parent_a = ALLOCNO_MEM_OPTIMIZED_DEST (first);
- dominator = common_loop_tree_node_dominator
- (ALLOCNO_LOOP_TREE_NODE (parent_a),
- ALLOCNO_LOOP_TREE_NODE (first));
- dominator_a = dominator->regno_allocno_map[ALLOCNO_REGNO (a)];
- ira_assert (parent_a != NULL);
- stop_p = first != a;
- /* Remember that exit can be to a grandparent (not only
- to a parent) or a child of the grandparent. */
- for (first = a;;)
- {
- if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
- {
- fprintf
- (ira_dump_file,
- " Coping ranges of a%dr%d to a%dr%d: ",
- ALLOCNO_NUM (first), REGNO (ALLOCNO_REG (first)),
- ALLOCNO_NUM (parent_a),
- REGNO (ALLOCNO_REG (parent_a)));
- ira_print_live_range_list (ira_dump_file,
- ALLOCNO_LIVE_RANGES (first));
- }
- r = copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES
- (first));
- change_allocno_in_range_list (r, parent_a);
- ALLOCNO_LIVE_RANGES (parent_a)
- = merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
- merged_p = true;
- if (stop_p)
- break;
- parent = ALLOCNO_LOOP_TREE_NODE (first)->parent;
- ira_assert (parent != NULL);
- first = parent->regno_allocno_map[ALLOCNO_REGNO (a)];
- ira_assert (first != NULL);
- if (first == dominator_a)
- break;
- }
- }
ALLOCNO_COPIES (a) = NULL;
regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
}
+ if (mem_dest_p && copy_info_to_removed_store_destinations (i))
+ merged_p = true;
}
- ira_free (allocno_propagated_p);
ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
if (merged_p || ira_max_point_before_emit != ira_max_point)
ira_rebuild_start_finish_chains ();
{
ira_allocno_t live_a = ira_allocnos[n];
- if (cover_class == ALLOCNO_COVER_CLASS (live_a)
+ if (ira_reg_classes_intersect_p
+ [cover_class][ALLOCNO_COVER_CLASS (live_a)]
/* Don't set up conflict for the allocno with itself. */
&& num != (int) n)
ira_add_allocno_conflict (a, live_a);
}
}
-
+
for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
}
ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
ALLOCNO_CAP (a) = NULL;
+ /* Restore updated costs for assignments from reload. */
ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
+ ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
if (! ALLOCNO_ASSIGNED_P (a))
ira_free_allocno_updated_costs (a);
ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
ira_swap_allocno_copy_ends_if_necessary (cp);
}
rebuild_regno_allocno_maps ();
+ if (ira_max_point != ira_max_point_before_emit)
+ ira_compress_allocno_live_ranges ();
ira_free (regno_top_level_allocno_map);
}
create_allocnos ();
ira_costs ();
ira_create_allocno_live_ranges ();
- remove_unnecessary_regions ();
+ remove_unnecessary_regions (false);
+ ira_compress_allocno_live_ranges ();
+ update_bad_spill_attribute ();
loops_p = more_one_region_p ();
if (loops_p)
{
sort_conflict_id_allocno_map ();
setup_min_max_conflict_allocno_ids ();
ira_build_conflicts ();
+ if (! ira_conflicts_p)
+ {
+ ira_allocno_t a;
+ ira_allocno_iterator ai;
+
+ /* Remove all regions but root one. */
+ if (loops_p)
+ {
+ remove_unnecessary_regions (true);
+ loops_p = false;
+ }
+ /* We don't save hard registers around calls for fast allocation
+ -- add caller clobbered registers as conflicting ones to
+ allocno crossing calls. */
+ FOR_EACH_ALLOCNO (a, ai)
+ if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
+ {
+ IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
+ call_used_reg_set);
+ IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
+ call_used_reg_set);
+ }
+ }
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ print_copies (ira_dump_file);
if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
{
int n, nr;