From patchwork Fri Aug 13 20:56:27 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: resubmitting IRA improvements: patch 1/4 Date: Fri, 13 Aug 2010 10:56:27 -0000 From: Vladimir Makarov X-Patchwork-Id: 61710 Message-Id: <4C65B17B.8040205@redhat.com> To: GCC Patches Cc: Jeff Law 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 * 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. 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; } @@ -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