* resubmitting IRA improvements: patch 1/4
@ 2010-08-13 20:58 Vladimir N. Makarov
2010-08-17 0:13 ` Bernd Schmidt
0 siblings, 1 reply; 2+ messages in thread
From: Vladimir N. Makarov @ 2010-08-13 20:58 UTC (permalink / raw)
To: GCC Patches; +Cc: Jeff Law
[-- Attachment #1: Type: text/plain, Size: 1923 bytes --]
I've resolved the conflicts on the ira-improv with latest big changes in
IRA (Bernd's and Richard Sandiford patches). I also take all proposals
I got into account. Here is the first patch which removes explicit
coalescing. It was a part of patch removing cover classes.
Ok to commit into the trunk.
2010-08-11 Vladimir Makarov <vmakarov@redhat.com>
* common.opt (fira-coalesce): Remove.
* doc/invoke.texi (flag_ira_coalesce): Remove.
* ira-color.c (allocno_coalesced_p): Move before
copy_freq_compare_func.
processed_coalesced_allocno_bitmap): Ditto.
(update_conflict_hard_regno_costs): Don't use
ALLOCNO_FIRST_COALESCED_ALLOCNO.
(allocno_cost_compare_func, print_coalesced_allocno): Remove.
(assign_hard_reg): Assume no coalesced allocnos.
(get_coalesced_allocnos_attributes): Remove.
(bucket_allocno_compare_func): Assume no coalesced allocnos.
(push_allocno_to_stack): Ditto.
(remove_allocno_from_bucket_and_push): Use
ira_print_expanded_allocno instead of print_coalesced_allocno.
(push_allocnos_to_stack): Assume uncoalesced allocnos.
(all_conflicting_hard_regs_coalesced): Ditto. Rename to
all_conflicting_hard_regs.
(setup_allocno_available_regs_num): Assume uncoalesced allocnos.
(setup_allocno_left_conflicts_size): Ditto.
(put_allocno_into_bucket): Ditto.
(copy_freq_compare_func): Remove.
(copy_freq_compare_func, merge_allocnos): Move before
coalesced_pseudo_reg_freq_compare.
coalesced_allocno_conflict_p): Ditto.
(coalesced_allocno_conflict_p, coalesce_allocnos): Ditto. Remove
parameter. Assume it true.
(color_allocnos): Assume uncoalesced allocnos. Use
ira_print_expanded_allocno instead of print_coalesced_allocno.
(ira_sort_regnos_for_alter_reg): Call coalesce_allocnos without
parameter.
* ira.c: Remove comment about coalescing.
[-- Attachment #2: remove-coalescing.patch --]
[-- Type: text/plain, Size: 48428 bytes --]
Index: doc/invoke.texi
===================================================================
--- doc/invoke.texi (revision 163079)
+++ doc/invoke.texi (working copy)
@@ -348,7 +348,7 @@ Objective-C and Objective-C++ Dialects}.
-finline-small-functions -fipa-cp -fipa-cp-clone -fipa-matrix-reorg -fipa-pta @gol
-fipa-profile -fipa-pure-const -fipa-reference -fipa-struct-reorg @gol
-fira-algorithm=@var{algorithm} @gol
--fira-region=@var{region} -fira-coalesce @gol
+-fira-region=@var{region} @gol
-fira-loop-pressure -fno-ira-share-save-slots @gol
-fno-ira-share-spill-slots -fira-verbose=@var{n} @gol
-fivopts -fkeep-inline-functions -fkeep-static-consts @gol
@@ -6408,11 +6408,6 @@ irregular register set, the third one re
decent code and the smallest size code, and the default value usually
give the best results in most cases and for most architectures.
-@item -fira-coalesce
-@opindex fira-coalesce
-Do optimistic register coalescing. This option might be profitable for
-architectures with big regular register files.
-
@item -fira-loop-pressure
@opindex fira-loop-pressure
Use IRA to evaluate register pressure in loops for decision to move
Index: ira-color.c
===================================================================
--- ira-color.c (revision 163079)
+++ ira-color.c (working copy)
@@ -54,15 +54,6 @@ static bitmap coloring_allocno_bitmap;
allocnos. */
static bitmap consideration_allocno_bitmap;
-/* TRUE if we coalesced some allocnos. In other words, if we got
- loops formed by members first_coalesced_allocno and
- next_coalesced_allocno containing more one allocno. */
-static bool allocno_coalesced_p;
-
-/* Bitmap used to prevent a repeated allocno processing because of
- coalescing. */
-static bitmap processed_coalesced_allocno_bitmap;
-
/* All allocnos sorted according their priorities. */
static ira_allocno_t *sorted_allocnos;
@@ -364,8 +355,7 @@ update_conflict_hard_regno_costs (int *c
another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
|| ALLOCNO_ASSIGNED_P (another_allocno)
- || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
- (another_allocno)))
+ || ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
continue;
class_size = ira_class_hard_regs_num[another_cover_class];
ira_allocate_and_copy_costs
@@ -410,58 +400,18 @@ update_conflict_hard_regno_costs (int *c
}
}
-/* Sort allocnos according to the profit of usage of a hard register
- instead of memory for them. */
-static int
-allocno_cost_compare_func (const void *v1p, const void *v2p)
-{
- ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
- ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
- int c1, c2;
-
- c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
- c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
- if (c1 - c2)
- return c1 - c2;
-
- /* If regs are equally good, sort by allocno numbers, so that the
- results of qsort leave nothing to chance. */
- return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
-}
-
-/* Print all allocnos coalesced with ALLOCNO. */
-static void
-print_coalesced_allocno (ira_allocno_t allocno)
-{
- ira_allocno_t a;
-
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- ira_print_expanded_allocno (a);
- if (a == allocno)
- break;
- fprintf (ira_dump_file, "+");
- }
-}
-
-/* Choose a hard register for ALLOCNO (or for all coalesced allocnos
- represented by ALLOCNO). If RETRY_P is TRUE, it means that the
- function called from function `ira_reassign_conflict_allocnos' and
- `allocno_reload_assign'. This function implements the optimistic
- coalescing too: if we failed to assign a hard register to set of
- the coalesced allocnos, we put them onto the coloring stack for
- subsequent separate assigning. */
+/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
+ that the function called from function
+ `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. */
static bool
-assign_hard_reg (ira_allocno_t allocno, bool retry_p)
+assign_hard_reg (ira_allocno_t a, bool retry_p)
{
HARD_REG_SET conflicting_regs[2];
int i, j, hard_regno, nregs, best_hard_regno, class_size;
- int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords;
+ int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
int *a_costs;
enum reg_class cover_class;
enum machine_mode mode;
- ira_allocno_t a;
static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
#ifndef HONOR_REG_ALLOC_ORDER
enum reg_class rclass;
@@ -471,133 +421,118 @@ assign_hard_reg (ira_allocno_t allocno,
bool no_stack_reg_p;
#endif
- nwords = ALLOCNO_NUM_OBJECTS (allocno);
- ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
- cover_class = ALLOCNO_COVER_CLASS (allocno);
+ nwords = ALLOCNO_NUM_OBJECTS (a);
+ ira_assert (! ALLOCNO_ASSIGNED_P (a));
+ cover_class = ALLOCNO_COVER_CLASS (a);
class_size = ira_class_hard_regs_num[cover_class];
- mode = ALLOCNO_MODE (allocno);
+ mode = ALLOCNO_MODE (a);
for (i = 0; i < nwords; i++)
CLEAR_HARD_REG_SET (conflicting_regs[i]);
best_hard_regno = -1;
memset (full_costs, 0, sizeof (int) * class_size);
mem_cost = 0;
- if (allocno_coalesced_p)
- bitmap_clear (processed_coalesced_allocno_bitmap);
memset (costs, 0, sizeof (int) * class_size);
memset (full_costs, 0, sizeof (int) * class_size);
#ifdef STACK_REGS
no_stack_reg_p = false;
#endif
start_update_cost ();
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- int word;
- mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
-
- ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
- cover_class, ALLOCNO_HARD_REG_COSTS (a));
- a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
+ mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
+
+ ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
+ cover_class, ALLOCNO_HARD_REG_COSTS (a));
+ a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
#ifdef STACK_REGS
- no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
+ no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
#endif
- cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a);
- for (i = 0; i < class_size; i++)
- if (a_costs != NULL)
- {
- costs[i] += a_costs[i];
- full_costs[i] += a_costs[i];
- }
- else
- {
- costs[i] += cost;
- full_costs[i] += cost;
- }
- for (word = 0; word < nwords; word++)
- {
- ira_object_t conflict_obj;
- ira_object_t obj = ALLOCNO_OBJECT (allocno, word);
- ira_object_conflict_iterator oci;
-
- IOR_HARD_REG_SET (conflicting_regs[word],
- OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
- /* Take preferences of conflicting allocnos into account. */
- FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
- {
- ira_allocno_t conflict_allocno = OBJECT_ALLOCNO (conflict_obj);
- enum reg_class conflict_cover_class;
- /* Reload can give another class so we need to check all
- allocnos. */
- if (!retry_p && !bitmap_bit_p (consideration_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
- conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno);
- ira_assert (ira_reg_classes_intersect_p
- [cover_class][conflict_cover_class]);
- if (ALLOCNO_ASSIGNED_P (conflict_allocno))
- {
- hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno);
- if (hard_regno >= 0
- && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
+ cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a);
+ for (i = 0; i < class_size; i++)
+ if (a_costs != NULL)
+ {
+ costs[i] += a_costs[i];
+ full_costs[i] += a_costs[i];
+ }
+ else
+ {
+ costs[i] += cost;
+ full_costs[i] += cost;
+ }
+ for (word = 0; word < nwords; word++)
+ {
+ ira_object_t conflict_obj;
+ ira_object_t obj = ALLOCNO_OBJECT (a, word);
+ ira_object_conflict_iterator oci;
+
+ IOR_HARD_REG_SET (conflicting_regs[word],
+ OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
+ /* Take preferences of conflicting allocnos into account. */
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+ enum reg_class conflict_cover_class;
+
+ /* Reload can give another class so we need to check all
+ allocnos. */
+ if (!retry_p && !bitmap_bit_p (consideration_allocno_bitmap,
+ ALLOCNO_NUM (conflict_a)))
+ continue;
+ conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_a);
+ ira_assert (ira_reg_classes_intersect_p
+ [cover_class][conflict_cover_class]);
+ if (ALLOCNO_ASSIGNED_P (conflict_a))
+ {
+ hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
+ if (hard_regno >= 0
+ && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
+ {
+ enum machine_mode mode = ALLOCNO_MODE (conflict_a);
+ int conflict_nregs = hard_regno_nregs[hard_regno][mode];
+ int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
+
+ if (conflict_nregs == n_objects && conflict_nregs > 1)
{
- enum machine_mode mode = ALLOCNO_MODE (conflict_allocno);
- int conflict_nregs = hard_regno_nregs[hard_regno][mode];
- int n_objects = ALLOCNO_NUM_OBJECTS (conflict_allocno);
- if (conflict_nregs == n_objects && conflict_nregs > 1)
- {
- int num = OBJECT_SUBWORD (conflict_obj);
- if (WORDS_BIG_ENDIAN)
- SET_HARD_REG_BIT (conflicting_regs[word],
- hard_regno + n_objects - num - 1);
- else
- SET_HARD_REG_BIT (conflicting_regs[word],
- hard_regno + num);
- }
- else
- IOR_HARD_REG_SET (conflicting_regs[word],
- ira_reg_mode_hard_regset[hard_regno][mode]);
- if (hard_reg_set_subset_p (reg_class_contents[cover_class],
- conflicting_regs[word]))
- goto fail;
- }
- }
- else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
- (conflict_allocno)))
- {
- int k, *conflict_costs;
+ int num = OBJECT_SUBWORD (conflict_obj);
- if (allocno_coalesced_p)
- {
- if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno));
+ if (WORDS_BIG_ENDIAN)
+ SET_HARD_REG_BIT (conflicting_regs[word],
+ hard_regno + n_objects - num - 1);
+ else
+ SET_HARD_REG_BIT (conflicting_regs[word],
+ hard_regno + num);
}
-
- ira_allocate_and_copy_costs
- (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
- conflict_cover_class,
- ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
- conflict_costs
- = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
- if (conflict_costs != NULL)
- for (j = class_size - 1; j >= 0; j--)
- {
- hard_regno = ira_class_hard_regs[cover_class][j];
- ira_assert (hard_regno >= 0);
- k = (ira_class_hard_reg_index
- [conflict_cover_class][hard_regno]);
- if (k < 0)
- continue;
- full_costs[j] -= conflict_costs[k];
- }
- queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
- }
+ else
+ IOR_HARD_REG_SET
+ (conflicting_regs[word],
+ ira_reg_mode_hard_regset[hard_regno][mode]);
+ if (hard_reg_set_subset_p (reg_class_contents[cover_class],
+ conflicting_regs[word]))
+ goto fail;
+ }
+ }
+ else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_a))
+ {
+ int k, *conflict_costs;
+
+ ira_allocate_and_copy_costs
+ (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
+ conflict_cover_class,
+ ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
+ conflict_costs
+ = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
+ if (conflict_costs != NULL)
+ for (j = class_size - 1; j >= 0; j--)
+ {
+ hard_regno = ira_class_hard_regs[cover_class][j];
+ ira_assert (hard_regno >= 0);
+ k = (ira_class_hard_reg_index
+ [conflict_cover_class][hard_regno]);
+ if (k < 0)
+ continue;
+ full_costs[j] -= conflict_costs[k];
+ }
+ queue_update_cost (conflict_a, COST_HOP_DIVISOR);
}
}
- if (a == allocno)
- break;
}
/* Take into account preferences of allocnos connected by copies to
the conflict allocnos. */
@@ -606,13 +541,7 @@ assign_hard_reg (ira_allocno_t allocno,
/* Take preferences of allocnos connected by copies into
account. */
start_update_cost ();
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- queue_update_cost (a, COST_HOP_DIVISOR);
- if (a == allocno)
- break;
- }
+ queue_update_cost (a, COST_HOP_DIVISOR);
update_conflict_hard_regno_costs (full_costs, cover_class, false);
min_cost = min_full_cost = INT_MAX;
@@ -623,7 +552,7 @@ assign_hard_reg (ira_allocno_t allocno,
for (i = 0; i < class_size; i++)
{
hard_regno = ira_class_hard_regs[cover_class][i];
- nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (allocno)];
+ nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
#ifdef STACK_REGS
if (no_stack_reg_p
&& FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
@@ -685,50 +614,14 @@ assign_hard_reg (ira_allocno_t allocno,
best_hard_regno = -1;
}
fail:
- if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
- && best_hard_regno < 0
- && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
- {
- for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- ira_assert (! ALLOCNO_IN_GRAPH_P (a));
- sorted_allocnos[j++] = a;
- if (a == allocno)
- break;
- }
- qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
- allocno_cost_compare_func);
- for (i = 0; i < j; i++)
- {
- a = sorted_allocnos[i];
- ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
- ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
- VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
- if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
- {
- fprintf (ira_dump_file, " Pushing");
- print_coalesced_allocno (a);
- fprintf (ira_dump_file, "\n");
- }
- }
- return false;
- }
if (best_hard_regno >= 0)
allocated_hardreg_p[best_hard_regno] = true;
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- ALLOCNO_HARD_REGNO (a) = best_hard_regno;
- ALLOCNO_ASSIGNED_P (a) = true;
- if (best_hard_regno >= 0)
- update_copy_costs (a, true);
- ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
- /* We don't need updated costs anymore: */
- ira_free_allocno_updated_costs (a);
- if (a == allocno)
- break;
- }
+ ALLOCNO_HARD_REGNO (a) = best_hard_regno;
+ ALLOCNO_ASSIGNED_P (a) = true;
+ if (best_hard_regno >= 0)
+ update_copy_costs (a, true);
+ /* We don't need updated costs anymore: */
+ ira_free_allocno_updated_costs (a);
return best_hard_regno >= 0;
}
@@ -780,25 +673,6 @@ add_allocno_to_bucket (ira_allocno_t all
*bucket_ptr = allocno;
}
-/* The function returns frequency and number of available hard
- registers for allocnos coalesced with ALLOCNO. */
-static void
-get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
-{
- ira_allocno_t a;
-
- *freq = 0;
- *num = 0;
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- *freq += ALLOCNO_FREQ (a);
- *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
- if (a == allocno)
- break;
- }
-}
-
/* Compare two allocnos to define which allocno should be pushed first
into the coloring stack. If the return is a negative number, the
allocno given by the first parameter will be pushed first. In this
@@ -815,8 +689,10 @@ bucket_allocno_compare_func (const void
if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
return diff;
- get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
- get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
+ a1_freq = ALLOCNO_FREQ (a1);
+ a1_num = ALLOCNO_AVAILABLE_REGS_NUM (a1);
+ a2_freq = ALLOCNO_FREQ (a2);
+ a2_num = ALLOCNO_AVAILABLE_REGS_NUM (a2);
if ((diff = a2_num - a1_num) != 0)
return diff;
else if ((diff = a1_freq - a2_freq) != 0)
@@ -924,112 +800,91 @@ static splay_tree uncolorable_allocnos_s
into account. */
#define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
-/* Put ALLOCNO onto the coloring stack without removing it from its
+/* Put allocno A onto the coloring stack without removing it from its
bucket. Pushing allocno to the coloring stack can result in moving
conflicting allocnos from the uncolorable bucket to the colorable
one. */
static void
-push_allocno_to_stack (ira_allocno_t allocno)
+push_allocno_to_stack (ira_allocno_t a)
{
int size;
- ira_allocno_t a;
enum reg_class cover_class;
+ int i, n = ALLOCNO_NUM_OBJECTS (a);
- ALLOCNO_IN_GRAPH_P (allocno) = false;
- VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
- cover_class = ALLOCNO_COVER_CLASS (allocno);
+ ALLOCNO_IN_GRAPH_P (a) = false;
+ VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
+ cover_class = ALLOCNO_COVER_CLASS (a);
if (cover_class == NO_REGS)
return;
- size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
- if (ALLOCNO_NUM_OBJECTS (allocno) > 1)
+ size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (a)];
+ if (ALLOCNO_NUM_OBJECTS (a) > 1)
{
/* We will deal with the subwords individually. */
- gcc_assert (size == ALLOCNO_NUM_OBJECTS (allocno));
+ gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
size = 1;
}
- if (allocno_coalesced_p)
- bitmap_clear (processed_coalesced_allocno_bitmap);
-
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ for (i = 0; i < n; i++)
{
- int i, n = ALLOCNO_NUM_OBJECTS (a);
- for (i = 0; i < n; i++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, i);
- int conflict_size;
- ira_object_t conflict_obj;
- ira_object_conflict_iterator oci;
-
- FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ int conflict_size;
+ ira_object_t conflict_obj;
+ ira_object_conflict_iterator oci;
+
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+ int left_conflicts_size;
+
+ conflict_a = conflict_a;
+ if (!bitmap_bit_p (coloring_allocno_bitmap,
+ ALLOCNO_NUM (conflict_a)))
+ continue;
+
+ ira_assert (cover_class
+ == ALLOCNO_COVER_CLASS (conflict_a));
+ if (!ALLOCNO_IN_GRAPH_P (conflict_a)
+ || ALLOCNO_ASSIGNED_P (conflict_a))
+ continue;
+
+ left_conflicts_size = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_a);
+ conflict_size
+ = (ira_reg_class_nregs
+ [cover_class][ALLOCNO_MODE (conflict_a)]);
+ ira_assert (left_conflicts_size >= size);
+ if (left_conflicts_size + conflict_size
+ <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_a))
{
- ira_allocno_t conflict_allocno = OBJECT_ALLOCNO (conflict_obj);
- int left_conflicts_size;
-
- conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
- if (!bitmap_bit_p (coloring_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
-
- ira_assert (cover_class
- == ALLOCNO_COVER_CLASS (conflict_allocno));
- if (allocno_coalesced_p)
- {
- conflict_obj = ALLOCNO_OBJECT (conflict_allocno,
- OBJECT_SUBWORD (conflict_obj));
- if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
- OBJECT_CONFLICT_ID (conflict_obj)))
- continue;
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- OBJECT_CONFLICT_ID (conflict_obj));
- }
-
- if (!ALLOCNO_IN_GRAPH_P (conflict_allocno)
- || ALLOCNO_ASSIGNED_P (conflict_allocno))
- continue;
-
- left_conflicts_size = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno);
- conflict_size
- = (ira_reg_class_nregs
- [cover_class][ALLOCNO_MODE (conflict_allocno)]);
- ira_assert (left_conflicts_size >= size);
- if (left_conflicts_size + conflict_size
- <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
- {
- ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) -= size;
- continue;
- }
- left_conflicts_size -= size;
- if (uncolorable_allocnos_splay_tree[cover_class] != NULL
- && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
- && USE_SPLAY_P (cover_class))
- {
- ira_assert
- (splay_tree_lookup
- (uncolorable_allocnos_splay_tree[cover_class],
- (splay_tree_key) conflict_allocno) != NULL);
- splay_tree_remove
- (uncolorable_allocnos_splay_tree[cover_class],
- (splay_tree_key) conflict_allocno);
- ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
- VEC_safe_push (ira_allocno_t, heap,
- removed_splay_allocno_vec,
- conflict_allocno);
- }
- 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
- (conflict_allocno, &uncolorable_allocno_bucket);
- add_allocno_to_ordered_bucket
- (conflict_allocno, &colorable_allocno_bucket);
- }
+ ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_a) -= size;
+ continue;
+ }
+ left_conflicts_size -= size;
+ if (uncolorable_allocnos_splay_tree[cover_class] != NULL
+ && !ALLOCNO_SPLAY_REMOVED_P (conflict_a)
+ && USE_SPLAY_P (cover_class))
+ {
+ ira_assert
+ (splay_tree_lookup
+ (uncolorable_allocnos_splay_tree[cover_class],
+ (splay_tree_key) conflict_a) != NULL);
+ splay_tree_remove
+ (uncolorable_allocnos_splay_tree[cover_class],
+ (splay_tree_key) conflict_a);
+ ALLOCNO_SPLAY_REMOVED_P (conflict_a) = true;
+ VEC_safe_push (ira_allocno_t, heap,
+ removed_splay_allocno_vec,
+ conflict_a);
+ }
+ ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_a)
+ = left_conflicts_size;
+ if (left_conflicts_size + conflict_size
+ <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_a))
+ {
+ delete_allocno_from_bucket
+ (conflict_a, &uncolorable_allocno_bucket);
+ add_allocno_to_ordered_bucket
+ (conflict_a, &colorable_allocno_bucket);
}
}
- if (a == allocno)
- break;
}
}
@@ -1047,7 +902,7 @@ remove_allocno_from_bucket_and_push (ira
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Pushing");
- print_coalesced_allocno (allocno);
+ ira_print_expanded_allocno (allocno);
if (colorable_p)
fprintf (ira_dump_file, "\n");
else
@@ -1225,7 +1080,7 @@ splay_tree_free (void *node, void *data
static void
push_allocnos_to_stack (void)
{
- ira_allocno_t allocno, a, i_allocno, *allocno_vec;
+ ira_allocno_t allocno, i_allocno, *allocno_vec;
enum reg_class cover_class, rclass;
int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
@@ -1248,16 +1103,7 @@ push_allocnos_to_stack (void)
if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
{
cover_class_allocnos_num[cover_class]++;
- cost = 0;
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- cost += calculate_allocno_spill_cost (a);
- if (a == allocno)
- break;
- }
- /* ??? Remove cost of copies between the coalesced
- allocnos. */
+ cost = calculate_allocno_spill_cost (allocno);
ALLOCNO_TEMP (allocno) = cost;
}
/* Define place where to put uncolorable allocnos of the same cover
@@ -1410,7 +1256,7 @@ pop_allocnos_from_stack (void)
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Popping");
- print_coalesced_allocno (allocno);
+ ira_print_expanded_allocno (allocno);
fprintf (ira_dump_file, " -- ");
}
if (cover_class == NO_REGS)
@@ -1438,47 +1284,41 @@ pop_allocnos_from_stack (void)
}
}
-/* Loop over all coalesced allocnos of ALLOCNO and their subobjects, collecting
- total hard register conflicts in PSET (which the caller must initialize). */
+/* Loop over all subobjects of allocno A, collecting total hard
+ register conflicts in PSET (which the caller must initialize). */
static void
-all_conflicting_hard_regs_coalesced (ira_allocno_t allocno, HARD_REG_SET *pset)
+all_conflicting_hard_regs (ira_allocno_t a, HARD_REG_SET *pset)
{
- ira_allocno_t a;
-
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ int i;
+ int n = ALLOCNO_NUM_OBJECTS (a);
+
+ for (i = 0; i < n; i++)
{
- int i;
- int n = ALLOCNO_NUM_OBJECTS (a);
- for (i = 0; i < n; i++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, i);
- IOR_HARD_REG_SET (*pset, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
- }
- if (a == allocno)
- break;
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+
+ IOR_HARD_REG_SET (*pset, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
}
}
-/* Set up number of available hard registers for ALLOCNO. */
+/* Set up number of available hard registers for allocno A. */
static void
-setup_allocno_available_regs_num (ira_allocno_t allocno)
+setup_allocno_available_regs_num (ira_allocno_t a)
{
int i, n, hard_regs_num, hard_regno;
enum machine_mode mode;
enum reg_class cover_class;
HARD_REG_SET temp_set;
- cover_class = ALLOCNO_COVER_CLASS (allocno);
- ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
+ cover_class = ALLOCNO_COVER_CLASS (a);
+ ALLOCNO_AVAILABLE_REGS_NUM (a) = ira_available_class_regs[cover_class];
if (cover_class == NO_REGS)
return;
CLEAR_HARD_REG_SET (temp_set);
- ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
+ ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
hard_regs_num = ira_class_hard_regs_num[cover_class];
- all_conflicting_hard_regs_coalesced (allocno, &temp_set);
+ all_conflicting_hard_regs (a, &temp_set);
- mode = ALLOCNO_MODE (allocno);
+ mode = ALLOCNO_MODE (a);
for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
{
hard_regno = ira_class_hard_regs[cover_class][i];
@@ -1489,24 +1329,23 @@ setup_allocno_available_regs_num (ira_al
}
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;
+ ALLOCNO_REGNO (a), reg_class_names[cover_class], n);
+ ALLOCNO_AVAILABLE_REGS_NUM (a) -= n;
}
-/* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */
+/* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for allocno A. */
static void
-setup_allocno_left_conflicts_size (ira_allocno_t allocno)
+setup_allocno_left_conflicts_size (ira_allocno_t a)
{
int i, hard_regs_num, hard_regno, conflict_allocnos_size;
- ira_allocno_t a;
enum reg_class cover_class;
HARD_REG_SET temp_set;
- cover_class = ALLOCNO_COVER_CLASS (allocno);
+ cover_class = ALLOCNO_COVER_CLASS (a);
hard_regs_num = ira_class_hard_regs_num[cover_class];
CLEAR_HARD_REG_SET (temp_set);
- ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
- all_conflicting_hard_regs_coalesced (allocno, &temp_set);
+ ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
+ all_conflicting_hard_regs (a, &temp_set);
AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
@@ -1525,67 +1364,47 @@ setup_allocno_left_conflicts_size (ira_a
}
}
CLEAR_HARD_REG_SET (temp_set);
- if (allocno_coalesced_p)
- bitmap_clear (processed_coalesced_allocno_bitmap);
if (cover_class != NO_REGS)
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- int n = ALLOCNO_NUM_OBJECTS (a);
- for (i = 0; i < n; i++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, i);
- ira_object_t conflict_obj;
- ira_object_conflict_iterator oci;
-
- FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
- {
- ira_allocno_t conflict_allocno = OBJECT_ALLOCNO (conflict_obj);
-
- conflict_allocno
- = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
- if (!bitmap_bit_p (consideration_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
-
- ira_assert (cover_class
- == ALLOCNO_COVER_CLASS (conflict_allocno));
- if (allocno_coalesced_p)
- {
- if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno));
- }
+ {
+ int n = ALLOCNO_NUM_OBJECTS (a);
- if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
- conflict_allocnos_size
- += (ira_reg_class_nregs
- [cover_class][ALLOCNO_MODE (conflict_allocno)]);
- else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
- >= 0)
- {
- 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))
- {
- conflict_allocnos_size++;
- SET_HARD_REG_BIT (temp_set, hard_regno);
- }
- hard_regno++;
- }
- }
- }
- }
- if (a == allocno)
- break;
- }
- ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) = conflict_allocnos_size;
+ for (i = 0; i < n; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ ira_object_t conflict_obj;
+ ira_object_conflict_iterator oci;
+
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+
+ ira_assert (cover_class
+ == ALLOCNO_COVER_CLASS (conflict_a));
+ if (! ALLOCNO_ASSIGNED_P (conflict_a))
+ conflict_allocnos_size
+ += (ira_reg_class_nregs
+ [cover_class][ALLOCNO_MODE (conflict_a)]);
+ else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_a))
+ >= 0)
+ {
+ int last = (hard_regno
+ + hard_regno_nregs
+ [hard_regno][ALLOCNO_MODE (conflict_a)]);
+
+ while (hard_regno < last)
+ {
+ if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
+ {
+ conflict_allocnos_size++;
+ SET_HARD_REG_BIT (temp_set, hard_regno);
+ }
+ hard_regno++;
+ }
+ }
+ }
+ }
+ }
+ ALLOCNO_LEFT_CONFLICTS_SIZE (a) = conflict_allocnos_size;
}
/* Put ALLOCNO in a bucket corresponding to its number and size of its
@@ -1596,8 +1415,6 @@ put_allocno_into_bucket (ira_allocno_t a
enum reg_class cover_class;
cover_class = ALLOCNO_COVER_CLASS (allocno);
- if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
- return;
ALLOCNO_IN_GRAPH_P (allocno) = true;
setup_allocno_left_conflicts_size (allocno);
setup_allocno_available_regs_num (allocno);
@@ -1609,220 +1426,19 @@ put_allocno_into_bucket (ira_allocno_t a
add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
}
-/* The function is used to sort allocnos according to their execution
- frequencies. */
-static int
-copy_freq_compare_func (const void *v1p, const void *v2p)
-{
- ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
- int pri1, pri2;
-
- pri1 = cp1->freq;
- pri2 = cp2->freq;
- if (pri2 - pri1)
- return pri2 - pri1;
-
- /* If freqencies are equal, sort by copies, so that the results of
- qsort leave nothing to chance. */
- return cp1->num - cp2->num;
-}
+/* Map: allocno number -> allocno priority. */
+static int *allocno_priorities;
-/* Merge two sets of coalesced allocnos given correspondingly by
- allocnos A1 and A2 (more accurately merging A2 set into A1
- set). */
+/* Set up priorities for N allocnos in array
+ CONSIDERATION_ALLOCNOS. */
static void
-merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
+setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
{
- ira_allocno_t a, first, last, next;
+ int i, length, nrefs, priority, max_priority, mult;
+ ira_allocno_t a;
- first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
- if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
- return;
- for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
- if (a == a2)
- break;
- last = a;
- }
- next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
- ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
- ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
-}
-
-/* Given two sets of coalesced sets of allocnos, A1 and A2, this
- function determines if any conflicts exist between the two sets.
- If RELOAD_P is TRUE, we use live ranges to find conflicts because
- conflicts are represented only for allocnos of the same cover class
- and during the reload pass we coalesce allocnos for sharing stack
- memory slots. */
-static bool
-coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
- bool reload_p)
-{
- ira_allocno_t a, conflict_allocno;
-
- /* When testing for conflicts, it is sufficient to examine only the
- subobjects of order 0, due to the canonicalization of conflicts
- we do in record_object_conflict. */
-
- bitmap_clear (processed_coalesced_allocno_bitmap);
- if (allocno_coalesced_p)
- {
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (a, 0)));
- if (a == a1)
- break;
- }
- }
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- if (reload_p)
- {
- for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
- conflict_allocno
- = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
- {
- if (allocnos_have_intersected_live_ranges_p (a,
- conflict_allocno))
- return true;
- if (conflict_allocno == a1)
- break;
- }
- }
- else
- {
- ira_object_t a_obj = ALLOCNO_OBJECT (a, 0);
- ira_object_t conflict_obj;
- ira_object_conflict_iterator oci;
- FOR_EACH_OBJECT_CONFLICT (a_obj, conflict_obj, oci)
- if (conflict_obj == ALLOCNO_OBJECT (a1, 0)
- || (allocno_coalesced_p
- && bitmap_bit_p (processed_coalesced_allocno_bitmap,
- OBJECT_CONFLICT_ID (conflict_obj))))
- return true;
- }
-
- if (a == a2)
- break;
- }
- return false;
-}
-
-/* The major function for aggressive allocno coalescing. For the
- reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
- allocnos have been coalesced, we set up flag
- allocno_coalesced_p. */
-static void
-coalesce_allocnos (bool reload_p)
-{
- ira_allocno_t a;
- ira_copy_t cp, next_cp, *sorted_copies;
- enum reg_class cover_class;
- enum machine_mode mode;
- unsigned int j;
- int i, n, cp_num, regno;
- bitmap_iterator bi;
-
- sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
- * sizeof (ira_copy_t));
- cp_num = 0;
- /* Collect copies. */
- EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
- {
- a = ira_allocnos[j];
- regno = ALLOCNO_REGNO (a);
- if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
- || (reload_p
- && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
- || (regno < ira_reg_equiv_len
- && (ira_reg_equiv_const[regno] != NULL_RTX
- || ira_reg_equiv_invariant_p[regno])))))
- continue;
- cover_class = ALLOCNO_COVER_CLASS (a);
- mode = ALLOCNO_MODE (a);
- for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
- {
- if (cp->first == a)
- {
- next_cp = cp->next_first_allocno_copy;
- regno = ALLOCNO_REGNO (cp->second);
- /* For priority coloring we coalesce allocnos only with
- the same cover class not with intersected cover
- classes as it were possible. It is done for
- simplicity. */
- if ((reload_p
- || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
- && ALLOCNO_MODE (cp->second) == mode))
- && (cp->insn != NULL || cp->constraint_p)
- && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
- || (reload_p
- && ALLOCNO_ASSIGNED_P (cp->second)
- && ALLOCNO_HARD_REGNO (cp->second) < 0
- && (regno >= ira_reg_equiv_len
- || (! ira_reg_equiv_invariant_p[regno]
- && ira_reg_equiv_const[regno] == NULL_RTX)))))
- sorted_copies[cp_num++] = cp;
- }
- else if (cp->second == a)
- next_cp = cp->next_second_allocno_copy;
- else
- gcc_unreachable ();
- }
- }
- qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
- /* Coalesced copies, most frequently executed first. */
- for (; cp_num != 0;)
- {
- for (i = 0; i < cp_num; i++)
- {
- cp = sorted_copies[i];
- if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
- {
- allocno_coalesced_p = true;
- if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
- fprintf
- (ira_dump_file,
- " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
- cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
- ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
- cp->freq);
- merge_allocnos (cp->first, cp->second);
- i++;
- break;
- }
- }
- /* Collect the rest of copies. */
- for (n = 0; i < cp_num; i++)
- {
- cp = sorted_copies[i];
- if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
- != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
- sorted_copies[n++] = cp;
- }
- cp_num = n;
- }
- ira_free (sorted_copies);
-}
-
-/* Map: allocno number -> allocno priority. */
-static int *allocno_priorities;
-
-/* Set up priorities for N allocnos in array
- CONSIDERATION_ALLOCNOS. */
-static void
-setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
-{
- int i, length, nrefs, priority, max_priority, mult;
- ira_allocno_t a;
-
- max_priority = 0;
- for (i = 0; i < n; i++)
+ max_priority = 0;
+ for (i = 0; i < n; i++)
{
a = consideration_allocnos[i];
nrefs = ALLOCNO_NREFS (a);
@@ -1881,10 +1497,6 @@ color_allocnos (void)
bitmap_iterator bi;
ira_allocno_t a;
- allocno_coalesced_p = false;
- processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
- if (flag_ira_coalesce)
- coalesce_allocnos (false);
if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
{
n = 0;
@@ -1900,7 +1512,7 @@ color_allocnos (void)
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Spill");
- print_coalesced_allocno (a);
+ ira_print_expanded_allocno (a);
fprintf (ira_dump_file, "\n");
}
continue;
@@ -1918,7 +1530,7 @@ color_allocnos (void)
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " ");
- print_coalesced_allocno (a);
+ ira_print_expanded_allocno (a);
fprintf (ira_dump_file, " -- ");
}
if (assign_hard_reg (a, false))
@@ -1952,7 +1564,7 @@ color_allocnos (void)
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Spill");
- print_coalesced_allocno (a);
+ ira_print_expanded_allocno (a);
fprintf (ira_dump_file, "\n");
}
continue;
@@ -1962,16 +1574,6 @@ color_allocnos (void)
push_allocnos_to_stack ();
pop_allocnos_from_stack ();
}
- if (flag_ira_coalesce)
- /* We don't need coalesced allocnos for ira_reassign_pseudos. */
- EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
- {
- a = ira_allocnos[i];
- ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
- ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
- }
- ira_free_bitmap (processed_coalesced_allocno_bitmap);
- allocno_coalesced_p = false;
}
\f
@@ -2479,6 +2081,183 @@ ira_reassign_conflict_allocnos (int star
On the other hand, it can worsen insn scheduling after the RA but
in practice it is less important than smaller stack frames. */
+/* TRUE if we coalesced some allocnos. In other words, if we got
+ loops formed by members first_coalesced_allocno and
+ next_coalesced_allocno containing more one allocno. */
+static bool allocno_coalesced_p;
+
+/* Bitmap used to prevent a repeated allocno processing because of
+ coalescing. */
+static bitmap processed_coalesced_allocno_bitmap;
+
+/* The function is used to sort allocnos according to their execution
+ frequencies. */
+static int
+copy_freq_compare_func (const void *v1p, const void *v2p)
+{
+ ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
+ int pri1, pri2;
+
+ pri1 = cp1->freq;
+ pri2 = cp2->freq;
+ if (pri2 - pri1)
+ return pri2 - pri1;
+
+ /* If freqencies are equal, sort by copies, so that the results of
+ qsort leave nothing to chance. */
+ return cp1->num - cp2->num;
+}
+
+/* Merge two sets of coalesced allocnos given correspondingly by
+ allocnos A1 and A2 (more accurately merging A2 set into A1
+ set). */
+static void
+merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
+{
+ ira_allocno_t a, first, last, next;
+
+ first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
+ if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
+ return;
+ for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
+ if (a == a2)
+ break;
+ last = a;
+ }
+ next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
+ ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
+ ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
+}
+
+/* Given two sets of coalesced sets of allocnos, A1 and A2, this
+ function determines if any conflicts exist between the two sets.
+ We use live ranges to find conflicts because conflicts are
+ represented only for allocnos of the same cover class and during
+ the reload pass we coalesce allocnos for sharing stack memory
+ slots. */
+static bool
+coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
+{
+ ira_allocno_t a, conflict_allocno;
+
+ bitmap_clear (processed_coalesced_allocno_bitmap);
+ if (allocno_coalesced_p)
+ {
+ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ bitmap_set_bit (processed_coalesced_allocno_bitmap,
+ OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (a, 0)));
+ if (a == a1)
+ break;
+ }
+ }
+ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
+ conflict_allocno
+ = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
+ {
+ if (allocnos_have_intersected_live_ranges_p (a, conflict_allocno))
+ return true;
+ if (conflict_allocno == a1)
+ break;
+ }
+
+ if (a == a2)
+ break;
+ }
+ return false;
+}
+
+/* The major function for aggressive allocno coalescing. We coalesce
+ only spilled allocnos. If some allocnos have been coalesced, we
+ set up flag allocno_coalesced_p. */
+static void
+coalesce_allocnos (void)
+{
+ ira_allocno_t a;
+ ira_copy_t cp, next_cp, *sorted_copies;
+ unsigned int j;
+ int i, n, cp_num, regno;
+ bitmap_iterator bi;
+
+ sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
+ * sizeof (ira_copy_t));
+ cp_num = 0;
+ /* Collect copies. */
+ EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
+ {
+ a = ira_allocnos[j];
+ regno = ALLOCNO_REGNO (a);
+ if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
+ || (regno < ira_reg_equiv_len
+ && (ira_reg_equiv_const[regno] != NULL_RTX
+ || ira_reg_equiv_invariant_p[regno])))
+ continue;
+ for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
+ {
+ if (cp->first == a)
+ {
+ next_cp = cp->next_first_allocno_copy;
+ regno = ALLOCNO_REGNO (cp->second);
+ /* For priority coloring we coalesce allocnos only with
+ the same cover class not with intersected cover
+ classes as it were possible. It is done for
+ simplicity. */
+ if ((cp->insn != NULL || cp->constraint_p)
+ && ALLOCNO_ASSIGNED_P (cp->second)
+ && ALLOCNO_HARD_REGNO (cp->second) < 0
+ && (regno >= ira_reg_equiv_len
+ || (! ira_reg_equiv_invariant_p[regno]
+ && ira_reg_equiv_const[regno] == NULL_RTX)))
+ sorted_copies[cp_num++] = cp;
+ }
+ else if (cp->second == a)
+ next_cp = cp->next_second_allocno_copy;
+ else
+ gcc_unreachable ();
+ }
+ }
+ qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
+ /* Coalesced copies, most frequently executed first. */
+ for (; cp_num != 0;)
+ {
+ for (i = 0; i < cp_num; i++)
+ {
+ cp = sorted_copies[i];
+ if (! coalesced_allocno_conflict_p (cp->first, cp->second))
+ {
+ allocno_coalesced_p = true;
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ fprintf
+ (ira_dump_file,
+ " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
+ cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
+ ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
+ cp->freq);
+ merge_allocnos (cp->first, cp->second);
+ i++;
+ break;
+ }
+ }
+ /* Collect the rest of copies. */
+ for (n = 0; i < cp_num; i++)
+ {
+ cp = sorted_copies[i];
+ if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
+ != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
+ sorted_copies[n++] = cp;
+ }
+ cp_num = n;
+ }
+ ira_free (sorted_copies);
+}
+
/* Usage cost and order number of coalesced allocno set to which
given pseudo register belongs to. */
static int *regno_coalesced_allocno_cost;
@@ -2754,7 +2533,6 @@ ira_sort_regnos_for_alter_reg (int *pseu
ira_allocno_iterator ai;
ira_allocno_t *spilled_coalesced_allocnos;
- processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
/* Set up allocnos can be coalesced. */
coloring_allocno_bitmap = ira_allocate_bitmap ();
for (i = 0; i < n; i++)
@@ -2766,7 +2544,8 @@ ira_sort_regnos_for_alter_reg (int *pseu
ALLOCNO_NUM (allocno));
}
allocno_coalesced_p = false;
- coalesce_allocnos (true);
+ processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
+ coalesce_allocnos ();
ira_free_bitmap (coloring_allocno_bitmap);
regno_coalesced_allocno_cost
= (int *) ira_allocate (max_regno * sizeof (int));
Index: common.opt
===================================================================
--- common.opt (revision 163079)
+++ common.opt (working copy)
@@ -751,10 +751,6 @@ fira-region=
Common Joined RejectNegative
-fira-region=[one|all|mixed] Set regions for IRA
-fira-coalesce
-Common Report Var(flag_ira_coalesce) Init(0)
-Do optimistic coalescing.
-
fira-loop-pressure
Common Report Var(flag_ira_loop_pressure)
Use IRA based register pressure calculation
Index: ira.c
===================================================================
--- ira.c (revision 163079)
+++ ira.c (working copy)
@@ -168,8 +168,6 @@ along with GCC; see the file COPYING3.
process. It is done in each region on top-down traverse of the
region tree (file ira-color.c). There are following subpasses:
- * Optional aggressive coalescing of allocnos in the region.
-
* Putting allocnos onto the coloring stack. IRA uses Briggs
optimistic coloring which is a major improvement over
Chaitin's coloring. Therefore IRA does not spill allocnos at
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: resubmitting IRA improvements: patch 1/4
2010-08-13 20:58 resubmitting IRA improvements: patch 1/4 Vladimir N. Makarov
@ 2010-08-17 0:13 ` Bernd Schmidt
0 siblings, 0 replies; 2+ messages in thread
From: Bernd Schmidt @ 2010-08-17 0:13 UTC (permalink / raw)
To: Vladimir N. Makarov; +Cc: GCC Patches, Jeff Law
On 08/13/2010 10:56 PM, Vladimir N. Makarov wrote:
> I've resolved the conflicts on the ira-improv with latest big changes in
> IRA (Bernd's and Richard Sandiford patches). I also take all proposals
> I got into account. Here is the first patch which removes explicit
> coalescing. It was a part of patch removing cover classes.
>
> Ok to commit into the trunk.
I haven't reviewed most of it in detail since it's hard to read with the
indentation level changes, but I'm assuming it's mostly mechanical. Ok.
Bernd
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2010-08-17 0:05 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-08-13 20:58 resubmitting IRA improvements: patch 1/4 Vladimir N. Makarov
2010-08-17 0:13 ` Bernd Schmidt
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).