X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fira-color.c;h=6a6a3304a510c3d9169ddd1492964ad8b43ac040;hb=e7a960245cbc9ed81b426a79876e0a84a59bcea1;hp=645d7dc3e536f52ab74940cea04cc98a9d8aa03a;hpb=441554ef16f1d6d223b43a6e7e528b1d831d134e;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/ira-color.c b/gcc/ira-color.c index 645d7dc3e53..6a6a3304a51 100644 --- a/gcc/ira-color.c +++ b/gcc/ira-color.c @@ -1,5 +1,5 @@ /* IRA allocation based on graph coloring. - Copyright (C) 2006, 2007, 2008 + Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. Contributed by Vladimir Makarov . @@ -33,6 +33,7 @@ along with GCC; see the file COPYING3. If not see #include "hard-reg-set.h" #include "basic-block.h" #include "expr.h" +#include "diagnostic-core.h" #include "toplev.h" #include "reload.h" #include "params.h" @@ -53,24 +54,12 @@ 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; /* Vec representing the stack of allocnos used during coloring. */ static VEC(ira_allocno_t,heap) *allocno_stack_vec; -/* Vec representing conflict allocnos used during assigning. */ -static VEC(ira_allocno_t,heap) *conflict_allocno_vec; - /* Array used to choose an allocno for spilling. */ static ira_allocno_t *allocnos_for_spilling; @@ -85,6 +74,70 @@ static alloc_pool splay_tree_node_pool; more costly although simpler. */ static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec; +/* Helper for qsort comparison callbacks - return a positive integer if + X > Y, or a negative value otherwise. Use a conditional expression + instead of a difference computation to insulate from possible overflow + issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */ +#define SORTGT(x,y) (((x) > (y)) ? 1 : -1) + + + +/* This page contains functions used to find conflicts using allocno + live ranges. */ + +/* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is + used to find a conflict for new allocnos or allocnos with the + different cover classes. */ +static bool +allocnos_have_intersected_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2) +{ + int i, j; + int n1 = ALLOCNO_NUM_OBJECTS (a1); + int n2 = ALLOCNO_NUM_OBJECTS (a2); + + if (a1 == a2) + return false; + if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL + && (ORIGINAL_REGNO (ALLOCNO_REG (a1)) + == ORIGINAL_REGNO (ALLOCNO_REG (a2)))) + return false; + + for (i = 0; i < n1; i++) + { + ira_object_t c1 = ALLOCNO_OBJECT (a1, i); + for (j = 0; j < n2; j++) + { + ira_object_t c2 = ALLOCNO_OBJECT (a2, j); + if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1), + OBJECT_LIVE_RANGES (c2))) + return true; + } + } + return false; +} + +#ifdef ENABLE_IRA_CHECKING + +/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2 + intersect. This should be used when there is only one region. + Currently this is used during reload. */ +static bool +pseudos_have_intersected_live_ranges_p (int regno1, int regno2) +{ + ira_allocno_t a1, a2; + + ira_assert (regno1 >= FIRST_PSEUDO_REGISTER + && regno2 >= FIRST_PSEUDO_REGISTER); + /* Reg info caclulated by dataflow infrastructure can be different + from one calculated by regclass. */ + if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL + || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL) + return false; + return allocnos_have_intersected_live_ranges_p (a1, a2); +} + +#endif + /* This page contains functions used to choose hard registers for @@ -94,9 +147,32 @@ static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec; register was already allocated for an allocno. */ static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]; -/* Array used to check already processed allocnos during the current - update_copy_costs call. */ -static int *allocno_update_cost_check; +/* Describes one element in a queue of allocnos whose costs need to be + updated. Each allocno in the queue is known to have a cover class. */ +struct update_cost_queue_elem +{ + /* This element is in the queue iff CHECK == update_cost_check. */ + int check; + + /* COST_HOP_DIVISOR**N, where N is the length of the shortest path + connecting this allocno to the one being allocated. */ + int divisor; + + /* The next allocno in the queue, or null if this is the last element. */ + ira_allocno_t next; +}; + +/* The first element in a queue of allocnos whose copy costs need to be + updated. Null if the queue is empty. */ +static ira_allocno_t update_cost_queue; + +/* The last element in the queue described by update_cost_queue. + Not valid if update_cost_queue is null. */ +static struct update_cost_queue_elem *update_cost_queue_tail; + +/* A pool of elements in the queue described by update_cost_queue. + Elements are indexed by ALLOCNO_NUM. */ +static struct update_cost_queue_elem *update_cost_queue_elems; /* The current value of update_copy_cost call count. */ static int update_cost_check; @@ -106,9 +182,12 @@ static int update_cost_check; static void initiate_cost_update (void) { - allocno_update_cost_check - = (int *) ira_allocate (ira_allocnos_num * sizeof (int)); - memset (allocno_update_cost_check, 0, ira_allocnos_num * sizeof (int)); + size_t size; + + size = ira_allocnos_num * sizeof (struct update_cost_queue_elem); + update_cost_queue_elems + = (struct update_cost_queue_elem *) ira_allocate (size); + memset (update_cost_queue_elems, 0, size); update_cost_check = 0; } @@ -116,7 +195,7 @@ initiate_cost_update (void) static void finish_cost_update (void) { - ira_free (allocno_update_cost_check); + ira_free (update_cost_queue_elems); } /* When we traverse allocnos to update hard register costs, the cost @@ -124,329 +203,354 @@ finish_cost_update (void) hop from given allocno to directly connected allocnos. */ #define COST_HOP_DIVISOR 4 -/* This recursive function updates costs (decrease if DECR_P) of the - unassigned allocnos connected by copies with ALLOCNO. This update - increases chances to remove some copies. Copy cost is proportional - the copy frequency divided by DIVISOR. */ +/* Start a new cost-updating pass. */ static void -update_copy_costs_1 (ira_allocno_t allocno, int hard_regno, - bool decr_p, int divisor) +start_update_cost (void) { - int i, cost, update_cost; - enum machine_mode mode; - enum reg_class rclass, cover_class; - ira_allocno_t another_allocno; - ira_copy_t cp, next_cp; + update_cost_check++; + update_cost_queue = NULL; +} - cover_class = ALLOCNO_COVER_CLASS (allocno); - if (cover_class == NO_REGS) - return; - if (allocno_update_cost_check[ALLOCNO_NUM (allocno)] == update_cost_check) - return; - allocno_update_cost_check[ALLOCNO_NUM (allocno)] = update_cost_check; - ira_assert (hard_regno >= 0); - i = ira_class_hard_reg_index[cover_class][hard_regno]; - ira_assert (i >= 0); - rclass = REGNO_REG_CLASS (hard_regno); - mode = ALLOCNO_MODE (allocno); - for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) +/* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue, + unless ALLOCNO is already in the queue, or has no cover class. */ +static inline void +queue_update_cost (ira_allocno_t allocno, int divisor) +{ + struct update_cost_queue_elem *elem; + + elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)]; + if (elem->check != update_cost_check + && ALLOCNO_COVER_CLASS (allocno) != NO_REGS) { - if (cp->first == allocno) - { - next_cp = cp->next_first_allocno_copy; - another_allocno = cp->second; - } - else if (cp->second == allocno) - { - next_cp = cp->next_second_allocno_copy; - another_allocno = cp->first; - } + elem->check = update_cost_check; + elem->divisor = divisor; + elem->next = NULL; + if (update_cost_queue == NULL) + update_cost_queue = allocno; else - gcc_unreachable (); - if (cover_class - != ALLOCNO_COVER_CLASS (another_allocno) - || ALLOCNO_ASSIGNED_P (another_allocno)) - continue; - cost = (cp->second == allocno - ? ira_register_move_cost[mode][rclass] - [ALLOCNO_COVER_CLASS (another_allocno)] - : ira_register_move_cost[mode] - [ALLOCNO_COVER_CLASS (another_allocno)][rclass]); - if (decr_p) - cost = -cost; - ira_allocate_and_set_or_copy_costs - (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class, - ALLOCNO_COVER_CLASS_COST (another_allocno), - ALLOCNO_HARD_REG_COSTS (another_allocno)); - ira_allocate_and_set_or_copy_costs - (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), - cover_class, 0, - ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); - update_cost = cp->freq * cost / divisor; - ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost; - ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i] - += update_cost; - if (update_cost != 0) - update_copy_costs_1 (another_allocno, hard_regno, - decr_p, divisor * COST_HOP_DIVISOR); + update_cost_queue_tail->next = allocno; + update_cost_queue_tail = elem; } } -/* Update the cost of allocnos to increase chances to remove some - copies as the result of subsequent assignment. */ -static void -update_copy_costs (ira_allocno_t allocno, bool decr_p) +/* Try to remove the first element from update_cost_queue. Return false + if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe + the removed element. */ +static inline bool +get_next_update_cost (ira_allocno_t *allocno, int *divisor) { - update_cost_check++; - update_copy_costs_1 (allocno, ALLOCNO_HARD_REGNO (allocno), decr_p, 1); + struct update_cost_queue_elem *elem; + + if (update_cost_queue == NULL) + return false; + + *allocno = update_cost_queue; + elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)]; + *divisor = elem->divisor; + update_cost_queue = elem->next; + return true; } -/* This recursive function updates COSTS (decrease if DECR_P) by - conflict costs of the unassigned allocnos connected by copies with - ALLOCNO. This update increases chances to remove some copies. - Copy cost is proportional to the copy frequency divided by - DIVISOR. */ +/* Update the cost of allocnos to increase chances to remove some + copies as the result of subsequent assignment. */ static void -update_conflict_hard_regno_costs (int *costs, ira_allocno_t allocno, - int divisor, bool decr_p) +update_copy_costs (ira_allocno_t allocno, bool decr_p) { - int i, cost, class_size, freq, mult, div; - int *conflict_costs; - bool cont_p; + int i, cost, update_cost, hard_regno, divisor; enum machine_mode mode; - enum reg_class cover_class; + enum reg_class rclass, cover_class; ira_allocno_t another_allocno; ira_copy_t cp, next_cp; + hard_regno = ALLOCNO_HARD_REGNO (allocno); + ira_assert (hard_regno >= 0); + cover_class = ALLOCNO_COVER_CLASS (allocno); - /* Probably 5 hops will be enough. */ - if (divisor > (COST_HOP_DIVISOR * COST_HOP_DIVISOR - * COST_HOP_DIVISOR * COST_HOP_DIVISOR * COST_HOP_DIVISOR)) - return; if (cover_class == NO_REGS) return; - /* Check that it was already visited. */ - if (allocno_update_cost_check[ALLOCNO_NUM (allocno)] == update_cost_check) - return; - allocno_update_cost_check[ALLOCNO_NUM (allocno)] = update_cost_check; - mode = ALLOCNO_MODE (allocno); - class_size = ira_class_hard_regs_num[cover_class]; - for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) + i = ira_class_hard_reg_index[cover_class][hard_regno]; + ira_assert (i >= 0); + rclass = REGNO_REG_CLASS (hard_regno); + + start_update_cost (); + divisor = 1; + do { - if (cp->first == allocno) - { - next_cp = cp->next_first_allocno_copy; - another_allocno = cp->second; - } - else if (cp->second == allocno) + mode = ALLOCNO_MODE (allocno); + for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) { - next_cp = cp->next_second_allocno_copy; - another_allocno = cp->first; - } - else - gcc_unreachable (); - if (cover_class != ALLOCNO_COVER_CLASS (another_allocno) - || ALLOCNO_ASSIGNED_P (another_allocno) - || ALLOCNO_MAY_BE_SPILLED_P (another_allocno)) - continue; - ira_allocate_and_copy_costs - (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), - cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); - conflict_costs - = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); - if (conflict_costs == NULL) - cont_p = true; - else - { - mult = cp->freq; - freq = ALLOCNO_FREQ (another_allocno); - if (freq == 0) - freq = 1; - div = freq * divisor; - cont_p = false; - for (i = class_size - 1; i >= 0; i--) + if (cp->first == allocno) { - cost = conflict_costs [i] * mult / div; - if (cost == 0) - continue; - cont_p = true; - if (decr_p) - cost = -cost; - costs[i] += cost; + next_cp = cp->next_first_allocno_copy; + another_allocno = cp->second; } - } - if (cont_p) - update_conflict_hard_regno_costs (costs, another_allocno, - divisor * COST_HOP_DIVISOR, decr_p); - } -} + else if (cp->second == allocno) + { + next_cp = cp->next_second_allocno_copy; + another_allocno = cp->first; + } + else + gcc_unreachable (); -/* 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; + cover_class = ALLOCNO_COVER_CLASS (another_allocno); + if (! ira_reg_classes_intersect_p[rclass][cover_class] + || ALLOCNO_ASSIGNED_P (another_allocno)) + continue; - c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1); - c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2); - if (c1 - c2) - return c1 - c2; + cost = (cp->second == allocno + ? ira_get_register_move_cost (mode, rclass, cover_class) + : ira_get_register_move_cost (mode, cover_class, rclass)); + if (decr_p) + cost = -cost; - /* 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); + update_cost = cp->freq * cost / divisor; + if (update_cost == 0) + continue; + + ira_allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class, + ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno), + ALLOCNO_HARD_REG_COSTS (another_allocno)); + ira_allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), + cover_class, 0, + ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); + i = ira_class_hard_reg_index[cover_class][hard_regno]; + ira_assert (i >= 0); + ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost; + ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i] + += update_cost; + + queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR); + } + } + while (get_next_update_cost (&allocno, &divisor)); } -/* Print all allocnos coalesced with ALLOCNO. */ +/* This function updates COSTS (decrease if DECR_P) for hard_registers + of COVER_CLASS by conflict costs of the unassigned allocnos + connected by copies with allocnos in update_cost_queue. This + update increases chances to remove some copies. */ static void -print_coalesced_allocno (ira_allocno_t allocno) +update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class, + bool decr_p) { - ira_allocno_t a; + int i, cost, class_size, freq, mult, div, divisor; + int index, hard_regno; + int *conflict_costs; + bool cont_p; + enum reg_class another_cover_class; + ira_allocno_t allocno, another_allocno; + ira_copy_t cp, next_cp; - 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, "+"); - } + while (get_next_update_cost (&allocno, &divisor)) + for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp) + { + if (cp->first == allocno) + { + next_cp = cp->next_first_allocno_copy; + another_allocno = cp->second; + } + else if (cp->second == allocno) + { + next_cp = cp->next_second_allocno_copy; + another_allocno = cp->first; + } + else + gcc_unreachable (); + 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 (another_allocno)) + continue; + class_size = ira_class_hard_regs_num[another_cover_class]; + ira_allocate_and_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), + another_cover_class, + ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); + conflict_costs + = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); + if (conflict_costs == NULL) + cont_p = true; + else + { + mult = cp->freq; + freq = ALLOCNO_FREQ (another_allocno); + if (freq == 0) + freq = 1; + div = freq * divisor; + cont_p = false; + for (i = class_size - 1; i >= 0; i--) + { + hard_regno = ira_class_hard_regs[another_cover_class][i]; + ira_assert (hard_regno >= 0); + index = ira_class_hard_reg_index[cover_class][hard_regno]; + if (index < 0) + continue; + cost = conflict_costs [i] * mult / div; + if (cost == 0) + continue; + cont_p = true; + if (decr_p) + cost = -cost; + costs[index] += cost; + } + } + /* Probably 5 hops will be enough. */ + if (cont_p + && divisor <= (COST_HOP_DIVISOR + * COST_HOP_DIVISOR + * COST_HOP_DIVISOR + * COST_HOP_DIVISOR)) + queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR); + } } -/* 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; - int i, j, hard_regno, best_hard_regno, class_size; - int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost; + 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, word; int *a_costs; - int *conflict_costs; - enum reg_class cover_class, rclass; + enum reg_class cover_class; enum machine_mode mode; - ira_allocno_t a, conflict_allocno; - ira_allocno_conflict_iterator aci; static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER]; +#ifndef HONOR_REG_ALLOC_ORDER + enum reg_class rclass; + int add_cost; +#endif #ifdef STACK_REGS bool no_stack_reg_p; #endif - 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); - CLEAR_HARD_REG_SET (conflicting_regs); + 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 - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) - { - mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a); - IOR_HARD_REG_SET (conflicting_regs, - ALLOCNO_TOTAL_CONFLICT_HARD_REGS (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); + start_update_cost (); + 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 - for (cost = ALLOCNO_COVER_CLASS_COST (a), 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; - } + 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_ALLOCNO_CONFLICT (a, conflict_allocno, aci) - /* 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))) - { - 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)); - } - if (ALLOCNO_ASSIGNED_P (conflict_allocno)) - { - if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0) - { + 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) + { + 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, - ira_reg_mode_hard_regset - [hard_regno][ALLOCNO_MODE (conflict_allocno)]); - if (hard_reg_set_subset_p (reg_class_contents[cover_class], - conflicting_regs)) - goto fail; + (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]; } - continue; - } - else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno)) - { - ira_allocate_and_copy_costs - (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno), - 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--) - full_costs[j] -= conflict_costs[j]; - VEC_safe_push (ira_allocno_t, heap, conflict_allocno_vec, - conflict_allocno); - } - } - if (a == allocno) - break; + queue_update_cost (conflict_a, COST_HOP_DIVISOR); + } + } } /* Take into account preferences of allocnos connected by copies to the conflict allocnos. */ - update_cost_check++; - while (VEC_length (ira_allocno_t, conflict_allocno_vec) != 0) - { - conflict_allocno = VEC_pop (ira_allocno_t, conflict_allocno_vec); - update_conflict_hard_regno_costs (full_costs, conflict_allocno, - COST_HOP_DIVISOR, true); - } - update_cost_check++; + update_conflict_hard_regno_costs (full_costs, cover_class, true); + /* Take preferences of allocnos connected by copies into account. */ - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) - { - update_conflict_hard_regno_costs (full_costs, a, - COST_HOP_DIVISOR, false); - if (a == allocno) - break; - } + start_update_cost (); + queue_update_cost (a, COST_HOP_DIVISOR); + update_conflict_hard_regno_costs (full_costs, cover_class, false); min_cost = min_full_cost = INT_MAX; + /* We don't care about giving callee saved registers to allocnos no living through calls because call clobbered registers are allocated first (it is usual practice to put them first in @@ -454,17 +558,38 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p) for (i = 0; i < class_size; i++) { hard_regno = ira_class_hard_regs[cover_class][i]; + 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) continue; #endif - if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs) - || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode], - hard_regno)) + if (TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode], + hard_regno)) + continue; + for (j = 0; j < nregs; j++) + { + int k; + int set_to_test_start = 0, set_to_test_end = nwords; + if (nregs == nwords) + { + if (WORDS_BIG_ENDIAN) + set_to_test_start = nwords - j - 1; + else + set_to_test_start = j; + set_to_test_end = set_to_test_start + 1; + } + for (k = set_to_test_start; k < set_to_test_end; k++) + if (TEST_HARD_REG_BIT (conflicting_regs[k], hard_regno + j)) + break; + if (k != set_to_test_end) + break; + } + if (j != nregs) continue; cost = costs[i]; full_cost = full_costs[i]; +#ifndef HONOR_REG_ALLOC_ORDER if (! allocated_hardreg_p[hard_regno] && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set)) /* We need to save/restore the hard register in @@ -477,6 +602,7 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p) cost += add_cost; full_cost += add_cost; } +#endif if (min_cost > cost) min_cost = cost; if (min_full_cost > full_cost) @@ -494,48 +620,14 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p) best_hard_regno = -1; } fail: - if (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)) - { - 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; } @@ -554,10 +646,21 @@ static ira_allocno_t uncolorable_allocno_bucket; of given *cover* class in the uncolorable_bucket. */ static int uncolorable_allocnos_num[N_REG_CLASSES]; +/* Return the current spill priority of allocno A. The less the + number, the more preferable the allocno for spilling. */ +static int +allocno_spill_priority (ira_allocno_t a) +{ + return (ALLOCNO_TEMP (a) + / (ALLOCNO_LEFT_CONFLICTS_SIZE (a) + * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)] + + 1)); +} + /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket before the call. */ static void -add_ira_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) +add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) { ira_allocno_t first_allocno; enum reg_class cover_class; @@ -576,25 +679,6 @@ add_ira_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) *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 @@ -611,8 +695,10 @@ bucket_allocno_compare_func (const void *v1p, const void *v2p) 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) @@ -651,8 +737,8 @@ sort_bucket (ira_allocno_t *bucket_ptr) their priority. ALLOCNO should be not in a bucket before the call. */ static void -add_ira_allocno_to_ordered_bucket (ira_allocno_t allocno, - ira_allocno_t *bucket_ptr) +add_allocno_to_ordered_bucket (ira_allocno_t allocno, + ira_allocno_t *bucket_ptr) { ira_allocno_t before, after; enum reg_class cover_class; @@ -720,88 +806,91 @@ static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES]; 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_ira_allocno_to_stack (ira_allocno_t allocno) +push_allocno_to_stack (ira_allocno_t a) { - int conflicts_num, conflict_size, size; - ira_allocno_t a, conflict_allocno; + int size; enum reg_class cover_class; - ira_allocno_conflict_iterator aci; - - ALLOCNO_IN_GRAPH_P (allocno) = false; - VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno); - cover_class = ALLOCNO_COVER_CLASS (allocno); + int i, n = ALLOCNO_NUM_OBJECTS (a); + + 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_coalesced_p) - bitmap_clear (processed_coalesced_allocno_bitmap); - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (a)]; + if (ALLOCNO_NUM_OBJECTS (a) > 1) { - FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci) - if (bitmap_bit_p (coloring_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno))) - { - 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)); - } - if (ALLOCNO_IN_GRAPH_P (conflict_allocno) - && ! ALLOCNO_ASSIGNED_P (conflict_allocno)) - { - conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno); - conflict_size - = (ira_reg_class_nregs - [cover_class][ALLOCNO_MODE (conflict_allocno)]); - ira_assert - (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size); - if (conflicts_num + conflict_size - <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno)) - { - ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size; - continue; - } - conflicts_num - = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - 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_NUM (conflict_allocno) = conflicts_num; - if (conflicts_num + conflict_size - <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno)) - { - delete_allocno_from_bucket (conflict_allocno, - &uncolorable_allocno_bucket); - add_ira_allocno_to_ordered_bucket (conflict_allocno, - &colorable_allocno_bucket); - } - } - } - if (a == allocno) - break; + /* We will deal with the subwords individually. */ + gcc_assert (size == ALLOCNO_NUM_OBJECTS (a)); + size = 1; + } + 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_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)) + { + 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); + } + } } } @@ -819,22 +908,27 @@ remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p) if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) { fprintf (ira_dump_file, " Pushing"); - print_coalesced_allocno (allocno); - fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)"); + ira_print_expanded_allocno (allocno); + if (colorable_p) + fprintf (ira_dump_file, "\n"); + else + fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n", + ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "", + allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno)); } cover_class = ALLOCNO_COVER_CLASS (allocno); ira_assert ((colorable_p - && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))) || (! colorable_p - && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > ALLOCNO_AVAILABLE_REGS_NUM (allocno)))); if (! colorable_p) ALLOCNO_MAY_BE_SPILLED_P (allocno) = true; - push_ira_allocno_to_stack (allocno); + push_allocno_to_stack (allocno); } /* Put all allocnos from colorable bucket onto the coloring stack. */ @@ -849,18 +943,18 @@ push_only_colorable (void) /* Puts ALLOCNO chosen for potential spilling onto the coloring stack. */ static void -push_ira_allocno_to_spill (ira_allocno_t allocno) +push_allocno_to_spill (ira_allocno_t allocno) { delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket); ALLOCNO_MAY_BE_SPILLED_P (allocno) = true; if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf (ira_dump_file, " Pushing p%d(%d) (potential spill)\n", + fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n", ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno)); - push_ira_allocno_to_stack (allocno); + push_allocno_to_stack (allocno); } /* Return the frequency of exit edges (if EXIT_P) or entry from/to the - loop given by its LOOP_NODE. */ + loop given by its LOOP_NODE. */ int ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) { @@ -884,7 +978,7 @@ ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) else { edges = get_loop_exit_edges (loop_node->loop); - for (i = 0; VEC_iterate (edge, edges, i, e); i++) + FOR_EACH_VEC_ELT (edge, edges, i, e) if (regno < 0 || (bitmap_bit_p (DF_LR_OUT (e->src), regno) && bitmap_bit_p (DF_LR_IN (e->dest), regno))) @@ -906,7 +1000,7 @@ calculate_allocno_spill_cost (ira_allocno_t a) ira_loop_tree_node_t parent_node, loop_node; regno = ALLOCNO_REGNO (a); - cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a); + cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a); if (ALLOCNO_CAP (a) != NULL) return cost; loop_node = ALLOCNO_LOOP_TREE_NODE (a); @@ -926,7 +1020,7 @@ calculate_allocno_spill_cost (ira_allocno_t a) * ira_loop_edge_freq (loop_node, regno, true) + ira_memory_move_cost[mode][rclass][0] * ira_loop_edge_freq (loop_node, regno, false)) - - (ira_register_move_cost[mode][rclass][rclass] + - (ira_get_register_move_cost (mode, rclass, rclass) * (ira_loop_edge_freq (loop_node, regno, false) + ira_loop_edge_freq (loop_node, regno, true)))); return cost; @@ -939,18 +1033,18 @@ allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2) { int pri1, pri2, diff; ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2; - - pri1 = (IRA_ALLOCNO_TEMP (a1) - / (ALLOCNO_LEFT_CONFLICTS_NUM (a1) + + pri1 = (ALLOCNO_TEMP (a1) + / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1) * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)] + 1)); - pri2 = (IRA_ALLOCNO_TEMP (a2) - / (ALLOCNO_LEFT_CONFLICTS_NUM (a2) + pri2 = (ALLOCNO_TEMP (a2) + / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2) * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)] + 1)); if ((diff = pri1 - pri2) != 0) return diff; - if ((diff = IRA_ALLOCNO_TEMP (a1) - IRA_ALLOCNO_TEMP (a2)) != 0) + if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0) return diff; return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); } @@ -992,7 +1086,7 @@ splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED) 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]; @@ -1015,17 +1109,8 @@ 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. */ - IRA_ALLOCNO_TEMP (allocno) = cost; + cost = calculate_allocno_spill_cost (allocno); + ALLOCNO_TEMP (allocno) = cost; } /* Define place where to put uncolorable allocnos of the same cover class. */ @@ -1069,7 +1154,7 @@ push_allocnos_to_stack (void) cover_class = ALLOCNO_COVER_CLASS (allocno); if (cover_class == NO_REGS) { - push_ira_allocno_to_spill (allocno); + push_allocno_to_spill (allocno); continue; } /* Potential spilling. */ @@ -1082,7 +1167,7 @@ push_allocnos_to_stack (void) allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec); ALLOCNO_SPLAY_REMOVED_P (allocno) = false; rclass = ALLOCNO_COVER_CLASS (allocno); - if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)] > ALLOCNO_AVAILABLE_REGS_NUM (allocno)) splay_tree_insert @@ -1117,35 +1202,20 @@ push_allocnos_to_stack (void) if (ALLOCNO_IN_GRAPH_P (i_allocno)) { i++; - if (IRA_ALLOCNO_TEMP (i_allocno) == INT_MAX) - { - ira_allocno_t a; - int cost = 0; - - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) - { - cost += calculate_allocno_spill_cost (i_allocno); - if (a == i_allocno) - break; - } - /* ??? Remove cost of copies between the coalesced - allocnos. */ - IRA_ALLOCNO_TEMP (i_allocno) = cost; - } - i_allocno_cost = IRA_ALLOCNO_TEMP (i_allocno); - i_allocno_pri - = (i_allocno_cost - / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno) - * ira_reg_class_nregs[ALLOCNO_COVER_CLASS - (i_allocno)] - [ALLOCNO_MODE (i_allocno)] + 1)); - if (allocno == NULL || allocno_pri > i_allocno_pri - || (allocno_pri == i_allocno_pri - && (allocno_cost > i_allocno_cost - || (allocno_cost == i_allocno_cost - && (ALLOCNO_NUM (allocno) - > ALLOCNO_NUM (i_allocno)))))) + ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX); + i_allocno_cost = ALLOCNO_TEMP (i_allocno); + i_allocno_pri = allocno_spill_priority (i_allocno); + if (allocno == NULL + || (! ALLOCNO_BAD_SPILL_P (i_allocno) + && ALLOCNO_BAD_SPILL_P (allocno)) + || (! (ALLOCNO_BAD_SPILL_P (i_allocno) + && ! ALLOCNO_BAD_SPILL_P (allocno)) + && (allocno_pri > i_allocno_pri + || (allocno_pri == i_allocno_pri + && (allocno_cost > i_allocno_cost + || (allocno_cost == i_allocno_cost + && (ALLOCNO_NUM (allocno) + > ALLOCNO_NUM (i_allocno)))))))) { allocno = i_allocno; allocno_cost = i_allocno_cost; @@ -1160,7 +1230,7 @@ push_allocnos_to_stack (void) } ira_assert (ALLOCNO_IN_GRAPH_P (allocno) && ALLOCNO_COVER_CLASS (allocno) == cover_class - && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > ALLOCNO_AVAILABLE_REGS_NUM (allocno))); @@ -1192,7 +1262,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) @@ -1220,61 +1290,72 @@ pop_allocnos_from_stack (void) } } -/* Set up number of available hard registers for ALLOCNO. */ +/* Loop over all subobjects of allocno A, collecting total hard + register conflicts in PSET (which the caller must initialize). */ static void -setup_allocno_available_regs_num (ira_allocno_t allocno) +all_conflicting_hard_regs (ira_allocno_t a, HARD_REG_SET *pset) { - int i, n, hard_regs_num; + 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)); + } +} + +/* Set up number of available hard registers for allocno A. */ +static void +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; - ira_allocno_t a; 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]; - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + all_conflicting_hard_regs (a, &temp_set); + + mode = ALLOCNO_MODE (a); + for (n = 0, i = hard_regs_num - 1; i >= 0; i--) { - IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a)); - if (a == allocno) - break; + hard_regno = ira_class_hard_regs[cover_class][i]; + if (TEST_HARD_REG_BIT (temp_set, hard_regno) + || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode], + hard_regno)) + n++; } - for (n = 0, i = hard_regs_num - 1; i >= 0; i--) - if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i])) - n++; 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_NUM for ALLOCNO. */ +/* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for allocno A. */ static void -setup_allocno_left_conflicts_num (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, conflict_allocno; enum reg_class cover_class; HARD_REG_SET temp_set; - ira_allocno_conflict_iterator aci; - 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); - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) - { - IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a)); - if (a == allocno) - break; - } + 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); + conflict_allocnos_size = 0; if (! hard_reg_set_empty_p (temp_set)) for (i = 0; i < (int) hard_regs_num; i++) @@ -1289,36 +1370,32 @@ setup_allocno_left_conflicts_num (ira_allocno_t allocno) } } 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)) - { - FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci) - if (bitmap_bit_p (consideration_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno))) + { + 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_a = OBJECT_ALLOCNO (conflict_obj); + 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)); - } - if (! ALLOCNO_ASSIGNED_P (conflict_allocno)) + == ALLOCNO_COVER_CLASS (conflict_a)); + if (! ALLOCNO_ASSIGNED_P (conflict_a)) conflict_allocnos_size += (ira_reg_class_nregs - [cover_class][ALLOCNO_MODE (conflict_allocno)]); - else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) + [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_allocno)]); + [hard_regno][ALLOCNO_MODE (conflict_a)]); while (hard_regno < last) { @@ -1331,10 +1408,9 @@ setup_allocno_left_conflicts_num (ira_allocno_t allocno) } } } - if (a == allocno) - break; - } - ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size; + } + } + ALLOCNO_LEFT_CONFLICTS_SIZE (a) = conflict_allocnos_size; } /* Put ALLOCNO in a bucket corresponding to its number and size of its @@ -1342,259 +1418,168 @@ setup_allocno_left_conflicts_num (ira_allocno_t allocno) static void put_allocno_into_bucket (ira_allocno_t allocno) { - int hard_regs_num; enum reg_class cover_class; cover_class = ALLOCNO_COVER_CLASS (allocno); - hard_regs_num = ira_class_hard_regs_num[cover_class]; - if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno) - return; ALLOCNO_IN_GRAPH_P (allocno) = true; - setup_allocno_left_conflicts_num (allocno); + setup_allocno_left_conflicts_size (allocno); setup_allocno_available_regs_num (allocno); - if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)) - add_ira_allocno_to_bucket (allocno, &colorable_allocno_bucket); + add_allocno_to_bucket (allocno, &colorable_allocno_bucket); else - add_ira_allocno_to_bucket (allocno, &uncolorable_allocno_bucket); + 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)) + max_priority = 0; + for (i = 0; i < n; i++) { - ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first; - if (a == a2) - break; - last = a; + a = consideration_allocnos[i]; + nrefs = ALLOCNO_NREFS (a); + ira_assert (nrefs >= 0); + mult = floor_log2 (ALLOCNO_NREFS (a)) + 1; + ira_assert (mult >= 0); + allocno_priorities[ALLOCNO_NUM (a)] + = priority + = (mult + * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a)) + * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]); + if (priority < 0) + priority = -priority; + if (max_priority < priority) + max_priority = priority; + } + mult = max_priority == 0 ? 1 : INT_MAX / max_priority; + for (i = 0; i < n; i++) + { + a = consideration_allocnos[i]; + length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); + if (ALLOCNO_NUM_OBJECTS (a) > 1) + length /= ALLOCNO_NUM_OBJECTS (a); + if (length <= 0) + length = 1; + allocno_priorities[ALLOCNO_NUM (a)] + = allocno_priorities[ALLOCNO_NUM (a)] * mult / length; } - next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first); - ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2; - ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next; } -/* Return TRUE if there are conflicting allocnos from two sets of - coalesced allocnos given correspondingly by allocnos A1 and A2. 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) +/* Sort allocnos according to their priorities which are calculated + analogous to ones in file `global.c'. */ +static int +allocno_priority_compare_func (const void *v1p, const void *v2p) { - ira_allocno_t a, conflict_allocno; - ira_allocno_conflict_iterator aci; + ira_allocno_t a1 = *(const ira_allocno_t *) v1p; + ira_allocno_t a2 = *(const ira_allocno_t *) v2p; + int pri1, pri2; - if (allocno_coalesced_p) - { - bitmap_clear (processed_coalesced_allocno_bitmap); - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) - { - bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a)); - 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 (ira_allocno_live_ranges_intersect_p (a, conflict_allocno)) - return true; - if (conflict_allocno == a1) - break; - } - } - else - { - FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci) - if (conflict_allocno == a1 - || (allocno_coalesced_p - && bitmap_bit_p (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno)))) - return true; - } - if (a == a2) - break; - } - return false; + pri1 = allocno_priorities[ALLOCNO_NUM (a1)]; + pri2 = allocno_priorities[ALLOCNO_NUM (a2)]; + if (pri2 != pri1) + return SORTGT (pri2, pri1); + + /* If regs are equally good, sort by allocnos, so that the results of + qsort leave nothing to chance. */ + return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); } -/* 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. */ +/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP + taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */ static void -coalesce_allocnos (bool reload_p) +color_allocnos (void) { - 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; + unsigned int i, n; bitmap_iterator bi; + ira_allocno_t a; - 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) + if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY) { - 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) + n = 0; + EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) { - if (cp->first == a) + a = ira_allocnos[i]; + if (ALLOCNO_COVER_CLASS (a) == NO_REGS) { - next_cp = cp->next_first_allocno_copy; - regno = ALLOCNO_REGNO (cp->second); - if ((reload_p - || (ALLOCNO_COVER_CLASS (cp->second) == cover_class - && ALLOCNO_MODE (cp->second) == mode)) - && cp->insn != NULL - && ((! 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; + ALLOCNO_HARD_REGNO (a) = -1; + ALLOCNO_ASSIGNED_P (a) = true; + ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); + ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " Spill"); + ira_print_expanded_allocno (a); + fprintf (ira_dump_file, "\n"); + } + continue; } - else if (cp->second == a) - next_cp = cp->next_second_allocno_copy; - else - gcc_unreachable (); + sorted_allocnos[n++] = a; } - } - 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++) + if (n != 0) { - cp = sorted_copies[i]; - if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p)) + setup_allocno_priorities (sorted_allocnos, n); + qsort (sorted_allocnos, n, sizeof (ira_allocno_t), + allocno_priority_compare_func); + for (i = 0; i < n; i++) { - allocno_coalesced_p = true; + a = sorted_allocnos[i]; 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; + { + fprintf (ira_dump_file, " "); + ira_print_expanded_allocno (a); + fprintf (ira_dump_file, " -- "); + } + if (assign_hard_reg (a, false)) + { + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "assign hard reg %d\n", + ALLOCNO_HARD_REGNO (a)); + } + else + { + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "assign memory\n"); + } } } - /* 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); -} - -/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP - taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */ -static void -color_allocnos (void) -{ - unsigned int i; - 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); - /* Put the allocnos into the corresponding buckets. */ - colorable_allocno_bucket = NULL; - uncolorable_allocno_bucket = NULL; - EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) - { - a = ira_allocnos[i]; - if (ALLOCNO_COVER_CLASS (a) == NO_REGS) + else + { + /* Put the allocnos into the corresponding buckets. */ + colorable_allocno_bucket = NULL; + uncolorable_allocno_bucket = NULL; + EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) { - ALLOCNO_HARD_REGNO (a) = -1; - ALLOCNO_ASSIGNED_P (a) = true; - ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); - ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + a = ira_allocnos[i]; + if (ALLOCNO_COVER_CLASS (a) == NO_REGS) { - fprintf (ira_dump_file, " Spill"); - print_coalesced_allocno (a); - fprintf (ira_dump_file, "\n"); + ALLOCNO_HARD_REGNO (a) = -1; + ALLOCNO_ASSIGNED_P (a) = true; + ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); + ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " Spill"); + ira_print_expanded_allocno (a); + fprintf (ira_dump_file, "\n"); + } + continue; } - continue; + put_allocno_into_bucket (a); } - put_allocno_into_bucket (a); + push_allocnos_to_stack (); + pop_allocnos_from_stack (); } - 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; } @@ -1605,15 +1590,32 @@ print_loop_title (ira_loop_tree_node_t loop_tree_node) { unsigned int j; bitmap_iterator bi; + ira_loop_tree_node_t subloop_node, dest_loop_node; + edge e; + edge_iterator ei; ira_assert (loop_tree_node->loop != NULL); fprintf (ira_dump_file, - "\n Loop %d (parent %d, header bb%d, depth %d)\n all:", + "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:", loop_tree_node->loop->num, (loop_tree_node->parent == NULL ? -1 : loop_tree_node->parent->loop->num), loop_tree_node->loop->header->index, loop_depth (loop_tree_node->loop)); + for (subloop_node = loop_tree_node->children; + subloop_node != NULL; + subloop_node = subloop_node->next) + if (subloop_node->bb != NULL) + { + fprintf (ira_dump_file, " %d", subloop_node->bb->index); + FOR_EACH_EDGE (e, ei, subloop_node->bb->succs) + if (e->dest != EXIT_BLOCK_PTR + && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent) + != loop_tree_node)) + fprintf (ira_dump_file, "(->%d:l%d)", + e->dest->index, dest_loop_node->loop->num); + } + fprintf (ira_dump_file, "\n all:"); EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi) fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j])); fprintf (ira_dump_file, "\n modified regnos:"); @@ -1626,7 +1628,7 @@ print_loop_title (ira_loop_tree_node_t loop_tree_node) for (j = 0; (int) j < ira_reg_class_cover_size; j++) { enum reg_class cover_class; - + cover_class = ira_reg_class_cover[j]; if (loop_tree_node->reg_pressure[cover_class] == 0) continue; @@ -1661,15 +1663,14 @@ color_pass (ira_loop_tree_node_t loop_tree_node) EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) { a = ira_allocnos[j]; - if (! ALLOCNO_ASSIGNED_P (a)) - continue; - bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a)); + if (ALLOCNO_ASSIGNED_P (a)) + bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a)); } /* Color all mentioned allocnos including transparent ones. */ color_allocnos (); /* Process caps. They are processed just once. */ - if (flag_ira_algorithm == IRA_ALGORITHM_MIXED - || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL) + if (flag_ira_region == IRA_REGION_MIXED + || flag_ira_region == IRA_REGION_ALL) EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi) { a = ira_allocnos[j]; @@ -1678,9 +1679,9 @@ color_pass (ira_loop_tree_node_t loop_tree_node) /* Remove from processing in the next loop. */ bitmap_clear_bit (consideration_allocno_bitmap, j); rclass = ALLOCNO_COVER_CLASS (a); - if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED - && loop_tree_node->reg_pressure[rclass] - <= ira_available_class_regs[rclass])) + if (flag_ira_region == IRA_REGION_MIXED + && (loop_tree_node->reg_pressure[rclass] + <= ira_available_class_regs[rclass])) { mode = ALLOCNO_MODE (a); hard_regno = ALLOCNO_HARD_REGNO (a); @@ -1715,6 +1716,7 @@ color_pass (ira_loop_tree_node_t loop_tree_node) mode = ALLOCNO_MODE (a); rclass = ALLOCNO_COVER_CLASS (a); hard_regno = ALLOCNO_HARD_REGNO (a); + /* Use hard register class here. ??? */ if (hard_regno >= 0) { index = ira_class_hard_reg_index[rclass][hard_regno]; @@ -1726,9 +1728,10 @@ color_pass (ira_loop_tree_node_t loop_tree_node) if (subloop_allocno == NULL || ALLOCNO_CAP (subloop_allocno) != NULL) continue; + ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass); ira_assert (bitmap_bit_p (subloop_node->all_allocnos, ALLOCNO_NUM (subloop_allocno))); - if (flag_ira_algorithm == IRA_ALGORITHM_MIXED + if ((flag_ira_region == IRA_REGION_MIXED) && (loop_tree_node->reg_pressure[rclass] <= ira_available_class_regs[rclass])) { @@ -1768,24 +1771,26 @@ color_pass (ira_loop_tree_node_t loop_tree_node) else { cover_class = ALLOCNO_COVER_CLASS (subloop_allocno); - ira_allocate_and_set_costs - (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class, - ALLOCNO_COVER_CLASS_COST (subloop_allocno)); - ira_allocate_and_set_costs - (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno), - cover_class, 0); - cost = (ira_register_move_cost[mode][rclass][rclass] + cost = (ira_get_register_move_cost (mode, rclass, rclass) * (exit_freq + enter_freq)); - ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost; - ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index] + ira_allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class, + ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno), + ALLOCNO_HARD_REG_COSTS (subloop_allocno)); + ira_allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno), + cover_class, 0, + ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)); + ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost; + ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index] -= cost; + if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno) + > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index]) + ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno) + = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index]; ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno) += (ira_memory_move_cost[mode][rclass][0] * enter_freq + ira_memory_move_cost[mode][rclass][1] * exit_freq); - if (ALLOCNO_COVER_CLASS_COST (subloop_allocno) - > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]) - ALLOCNO_COVER_CLASS_COST (subloop_allocno) - = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]; } } } @@ -1805,7 +1810,7 @@ do_coloring (void) 100); if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n"); - + ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL); if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) @@ -1872,6 +1877,7 @@ move_spill_restore (void) subloop_allocno = subloop_node->regno_allocno_map[regno]; if (subloop_allocno == NULL) continue; + ira_assert (rclass == ALLOCNO_COVER_CLASS (subloop_allocno)); /* We have accumulated cost. To get the real cost of allocno usage in the loop we should subtract costs of the subloop allocnos. */ @@ -1890,13 +1896,14 @@ move_spill_restore (void) += (ira_memory_move_cost[mode][rclass][0] * exit_freq + ira_memory_move_cost[mode][rclass][1] * enter_freq); if (hard_regno2 != hard_regno) - cost -= (ira_register_move_cost[mode][rclass][rclass] + cost -= (ira_get_register_move_cost (mode, rclass, rclass) * (exit_freq + enter_freq)); } } if ((parent = loop_node->parent) != NULL && (parent_allocno = parent->regno_allocno_map[regno]) != NULL) { + ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno)); exit_freq = ira_loop_edge_freq (loop_node, regno, true); enter_freq = ira_loop_edge_freq (loop_node, regno, false); if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0) @@ -1908,7 +1915,7 @@ move_spill_restore (void) += (ira_memory_move_cost[mode][rclass][1] * exit_freq + ira_memory_move_cost[mode][rclass][0] * enter_freq); if (hard_regno2 != hard_regno) - cost -= (ira_register_move_cost[mode][rclass][rclass] + cost -= (ira_get_register_move_cost (mode, rclass, rclass) * (exit_freq + enter_freq)); } } @@ -1945,6 +1952,7 @@ update_curr_costs (ira_allocno_t a) ira_allocno_t another_a; ira_copy_t cp, next_cp; + ira_free_allocno_updated_costs (a); ira_assert (! ALLOCNO_ASSIGNED_P (a)); cover_class = ALLOCNO_COVER_CLASS (a); if (cover_class == NO_REGS) @@ -1964,16 +1972,18 @@ update_curr_costs (ira_allocno_t a) } else gcc_unreachable (); - if (cover_class != ALLOCNO_COVER_CLASS (another_a) + if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS + (another_a)] || ! ALLOCNO_ASSIGNED_P (another_a) || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0) continue; rclass = REGNO_REG_CLASS (hard_regno); i = ira_class_hard_reg_index[cover_class][hard_regno]; - ira_assert (i >= 0); + if (i < 0) + continue; cost = (cp->first == a - ? ira_register_move_cost[mode][rclass][cover_class] - : ira_register_move_cost[mode][cover_class][rclass]); + ? ira_get_register_move_cost (mode, rclass, cover_class) + : ira_get_register_move_cost (mode, cover_class, rclass)); ira_allocate_and_set_or_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class, ALLOCNO_COVER_CLASS_COST (a), @@ -1986,139 +1996,273 @@ update_curr_costs (ira_allocno_t a) } } -/* Map: allocno number -> allocno priority. */ -static int *allocno_priorities; - -/* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in - array CONSIDERATION_ALLOCNOS. */ -static void -start_allocno_priorities (ira_allocno_t *consideration_allocnos, int n) +/* Try to assign hard registers to the unassigned allocnos and + allocnos conflicting with them or conflicting with allocnos whose + regno >= START_REGNO. The function is called after ira_flattening, + so more allocnos (including ones created in ira-emit.c) will have a + chance to get a hard register. We use simple assignment algorithm + based on priorities. */ +void +ira_reassign_conflict_allocnos (int start_regno) { - int i, length; + int i, allocnos_to_color_num; ira_allocno_t a; - allocno_live_range_t r; + enum reg_class cover_class; + bitmap allocnos_to_color; + ira_allocno_iterator ai; - for (i = 0; i < n; i++) + allocnos_to_color = ira_allocate_bitmap (); + allocnos_to_color_num = 0; + FOR_EACH_ALLOCNO (a, ai) { - a = consideration_allocnos[i]; - for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next) - length += r->finish - r->start + 1; - if (length == 0) + int n = ALLOCNO_NUM_OBJECTS (a); + + if (! ALLOCNO_ASSIGNED_P (a) + && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a))) { - allocno_priorities[ALLOCNO_NUM (a)] = 0; - continue; + if (ALLOCNO_COVER_CLASS (a) != NO_REGS) + sorted_allocnos[allocnos_to_color_num++] = a; + else + { + ALLOCNO_ASSIGNED_P (a) = true; + ALLOCNO_HARD_REGNO (a) = -1; + ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); + ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); + } + bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a)); + } + if (ALLOCNO_REGNO (a) < start_regno + || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS) + continue; + 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 (ira_reg_classes_intersect_p + [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]); + if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a))) + continue; + sorted_allocnos[allocnos_to_color_num++] = conflict_a; + } + } + } + ira_free_bitmap (allocnos_to_color); + if (allocnos_to_color_num > 1) + { + setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num); + qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t), + allocno_priority_compare_func); + } + for (i = 0; i < allocnos_to_color_num; i++) + { + a = sorted_allocnos[i]; + ALLOCNO_ASSIGNED_P (a) = false; + update_curr_costs (a); + } + for (i = 0; i < allocnos_to_color_num; i++) + { + a = sorted_allocnos[i]; + if (assign_hard_reg (a, true)) + { + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf + (ira_dump_file, + " Secondary allocation: assign hard reg %d to reg %d\n", + ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a)); } - ira_assert (length > 0 && ALLOCNO_NREFS (a) >= 0); - allocno_priorities[ALLOCNO_NUM (a)] - = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a)) - / length) - * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a))); } } -/* Sort allocnos according to their priorities which are calculated - analogous to ones in file `global.c'. */ + + +/* This page contains code to coalesce memory stack slots used by + spilled allocnos. This results in smaller stack frame, better data + locality, and in smaller code for some architectures like + x86/x86_64 where insn size depends on address displacement value. + 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 -allocno_priority_compare_func (const void *v1p, const void *v2p) +copy_freq_compare_func (const void *v1p, const void *v2p) { - ira_allocno_t a1 = *(const ira_allocno_t *) v1p; - ira_allocno_t a2 = *(const ira_allocno_t *) v2p; + ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p; int pri1, pri2; - pri1 = allocno_priorities[ALLOCNO_NUM (a1)]; - pri2 = allocno_priorities[ALLOCNO_NUM (a2)]; + pri1 = cp1->freq; + pri2 = cp2->freq; if (pri2 - pri1) return pri2 - pri1; - /* If regs are equally good, sort by allocnos, so that the results of - qsort leave nothing to chance. */ - return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); + /* 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; } -/* Try to assign hard registers to the unassigned allocnos and - allocnos conflicting with them or conflicting with allocnos whose - regno >= START_REGNO. The function is called after ira_flattening, - so more allocnos (including ones created in ira-emit.c) will have a - chance to get a hard register. We use simple assignment algorithm - based on priorities. */ -void -ira_reassign_conflict_allocnos (int start_regno) +/* 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) { - int i, allocnos_to_color_num; - ira_allocno_t a, conflict_a; - ira_allocno_conflict_iterator aci; - enum reg_class cover_class; - bitmap allocnos_to_color; - ira_allocno_iterator ai; + ira_allocno_t a; + ira_copy_t cp, next_cp, *sorted_copies; + unsigned int j; + int i, n, cp_num, regno; + bitmap_iterator bi; - allocnos_to_color = ira_allocate_bitmap (); - allocnos_to_color_num = 0; - FOR_EACH_ALLOCNO (a, ai) + 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) { - if (! ALLOCNO_ASSIGNED_P (a) - && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a))) + 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 (ALLOCNO_COVER_CLASS (a) != NO_REGS) - sorted_allocnos[allocnos_to_color_num++] = a; - else + if (cp->first == a) { - ALLOCNO_ASSIGNED_P (a) = true; - ALLOCNO_HARD_REGNO (a) = -1; - ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); - ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); + 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; } - bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a)); - } - if (ALLOCNO_REGNO (a) < start_regno - || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS) - continue; - FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci) - { - ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a)); - if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a))) - continue; - bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)); - sorted_allocnos[allocnos_to_color_num++] = conflict_a; + else if (cp->second == a) + next_cp = cp->next_second_allocno_copy; + else + gcc_unreachable (); } } - ira_free_bitmap (allocnos_to_color); - if (allocnos_to_color_num > 1) - { - start_allocno_priorities (sorted_allocnos, allocnos_to_color_num); - qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t), - allocno_priority_compare_func); - } - for (i = 0; i < allocnos_to_color_num; i++) - { - a = sorted_allocnos[i]; - ALLOCNO_ASSIGNED_P (a) = false; - ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); - ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); - update_curr_costs (a); - } - for (i = 0; i < allocnos_to_color_num; i++) + qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func); + /* Coalesced copies, most frequently executed first. */ + for (; cp_num != 0;) { - a = sorted_allocnos[i]; - if (assign_hard_reg (a, true)) + for (i = 0; i < cp_num; i++) { - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf - (ira_dump_file, - " Secondary allocation: assign hard reg %d to reg %d\n", - ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a)); + 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); } - - -/* This page contains code to coalesce memory stack slots used by - spilled allocnos. This results in smaller stack frame, better data - locality, and in smaller code for some architectures like - x86/x86_64 where insn size depends on address displacement value. - On the other hand, it can worsen insn scheduling after the RA but - in practice it is less important than smaller stack frames. */ - /* Usage cost and order number of coalesced allocno set to which given pseudo register belongs to. */ static int *regno_coalesced_allocno_cost; @@ -2252,6 +2396,64 @@ collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n, return num; } +/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for + given slot contains live ranges of coalesced allocnos assigned to + given slot. */ +static live_range_t *slot_coalesced_allocnos_live_ranges; + +/* Return TRUE if coalesced allocnos represented by ALLOCNO has live + ranges intersected with live ranges of coalesced allocnos assigned + to slot with number N. */ +static bool +slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n) +{ + ira_allocno_t a; + + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + int i; + int nr = ALLOCNO_NUM_OBJECTS (a); + for (i = 0; i < nr; i++) + { + ira_object_t obj = ALLOCNO_OBJECT (a, i); + if (ira_live_ranges_intersect_p (slot_coalesced_allocnos_live_ranges[n], + OBJECT_LIVE_RANGES (obj))) + return true; + } + if (a == allocno) + break; + } + return false; +} + +/* Update live ranges of slot to which coalesced allocnos represented + by ALLOCNO were assigned. */ +static void +setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno) +{ + int i, n; + ira_allocno_t a; + live_range_t r; + + n = ALLOCNO_TEMP (allocno); + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + int nr = ALLOCNO_NUM_OBJECTS (a); + for (i = 0; i < nr; i++) + { + ira_object_t obj = ALLOCNO_OBJECT (a, i); + r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj)); + slot_coalesced_allocnos_live_ranges[n] + = ira_merge_live_ranges + (slot_coalesced_allocnos_live_ranges[n], r); + } + if (a == allocno) + break; + } +} + /* We have coalesced allocnos involving in copies. Coalesce allocnos further in order to share the same memory stack slot. Allocnos representing sets of allocnos coalesced before the call are given @@ -2260,29 +2462,48 @@ collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n, static bool coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num) { - int i, j; + int i, j, n, last_coalesced_allocno_num; ira_allocno_t allocno, a; bool merged_p = false; + bitmap set_jump_crosses = regstat_get_setjmp_crosses (); + slot_coalesced_allocnos_live_ranges + = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num); + memset (slot_coalesced_allocnos_live_ranges, 0, + sizeof (live_range_t) * ira_allocnos_num); + last_coalesced_allocno_num = 0; /* Coalesce non-conflicting spilled allocnos preferring most frequently used. */ for (i = 0; i < num; i++) { allocno = spilled_coalesced_allocnos[i]; if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno + || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno)) || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len - && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)] - || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX))) + && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX + || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]))) continue; for (j = 0; j < i; j++) { a = spilled_coalesced_allocnos[j]; - if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a - || (ALLOCNO_REGNO (a) < ira_reg_equiv_len - && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)] - || ira_reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX)) - || coalesced_allocno_conflict_p (allocno, a, true)) - continue; + n = ALLOCNO_TEMP (a); + if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a + && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a)) + && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len + || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)] + && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX)) + && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n)) + break; + } + if (j >= i) + { + /* No coalescing: set up number for coalesced allocnos + represented by ALLOCNO. */ + ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++; + setup_slot_coalesced_allocno_live_ranges (allocno); + } + else + { allocno_coalesced_p = true; merged_p = true; if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) @@ -2290,10 +2511,15 @@ coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num) " Coalescing spilled allocnos a%dr%d->a%dr%d\n", ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno), ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); + ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a); + setup_slot_coalesced_allocno_live_ranges (allocno); merge_allocnos (a, allocno); ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a); } } + for (i = 0; i < ira_allocnos_num; i++) + ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]); + ira_free (slot_coalesced_allocnos_live_ranges); return merged_p; } @@ -2312,7 +2538,6 @@ ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, 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++) @@ -2324,7 +2549,8 @@ ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, 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)); @@ -2364,8 +2590,8 @@ ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno || ALLOCNO_HARD_REGNO (allocno) >= 0 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len - && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)] - || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX))) + && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX + || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]))) continue; if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num); @@ -2380,7 +2606,7 @@ ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a), MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)), reg_max_ref_width[ALLOCNO_REGNO (a)])); - + if (a == allocno) break; } @@ -2472,21 +2698,27 @@ ira_mark_memory_move_deletion (int dst_regno, int src_regno) } /* Try to assign a hard register (except for FORBIDDEN_REGS) to - allocno A and return TRUE in the case of success. That is an - analog of retry_global_alloc for IRA. */ + allocno A and return TRUE in the case of success. */ static bool allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs) { int hard_regno; enum reg_class cover_class; int regno = ALLOCNO_REGNO (a); + HARD_REG_SET saved[2]; + int i, n; - IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs); - if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) - IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set); + n = ALLOCNO_NUM_OBJECTS (a); + for (i = 0; i < n; i++) + { + ira_object_t obj = ALLOCNO_OBJECT (a, i); + COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); + IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs); + if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) + IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), + call_used_reg_set); + } ALLOCNO_ASSIGNED_P (a) = false; - ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); - ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); cover_class = ALLOCNO_COVER_CLASS (a); update_curr_costs (a); assign_hard_reg (a, true); @@ -2524,7 +2756,11 @@ allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs) } else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) fprintf (ira_dump_file, "\n"); - + for (i = 0; i < n; i++) + { + ira_object_t obj = ALLOCNO_OBJECT (a, i); + COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]); + } return reg_renumber[regno] >= 0; } @@ -2554,20 +2790,58 @@ bool ira_reassign_pseudos (int *spilled_pseudo_regs, int num, HARD_REG_SET bad_spill_regs, HARD_REG_SET *pseudo_forbidden_regs, - HARD_REG_SET *pseudo_previous_regs, bitmap spilled) + HARD_REG_SET *pseudo_previous_regs, + bitmap spilled) { - int i, m, n, regno; + int i, n, regno; bool changed_p; - ira_allocno_t a, conflict_a; + ira_allocno_t a; HARD_REG_SET forbidden_regs; - ira_allocno_conflict_iterator aci; + bitmap temp = BITMAP_ALLOC (NULL); + + /* Add pseudos which conflict with pseudos already in + SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable + to allocating in two steps as some of the conflicts might have + a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */ + for (i = 0; i < num; i++) + bitmap_set_bit (temp, spilled_pseudo_regs[i]); + + for (i = 0, n = num; i < n; i++) + { + int nr, j; + int regno = spilled_pseudo_regs[i]; + bitmap_set_bit (temp, regno); + + a = ira_regno_allocno_map[regno]; + nr = ALLOCNO_NUM_OBJECTS (a); + for (j = 0; j < nr; j++) + { + ira_object_t conflict_obj; + ira_object_t obj = ALLOCNO_OBJECT (a, j); + ira_object_conflict_iterator oci; + + FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) + { + ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); + if (ALLOCNO_HARD_REGNO (conflict_a) < 0 + && ! ALLOCNO_DONT_REASSIGN_P (conflict_a) + && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a))) + { + spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a); + /* ?!? This seems wrong. */ + bitmap_set_bit (consideration_allocno_bitmap, + ALLOCNO_NUM (conflict_a)); + } + } + } + } if (num > 1) qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare); changed_p = false; /* Try to assign hard registers to pseudos from SPILLED_PSEUDO_REGS. */ - for (m = i = 0; i < num; i++) + for (i = 0; i < num; i++) { regno = spilled_pseudo_regs[i]; COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs); @@ -2579,7 +2853,7 @@ ira_reassign_pseudos (int *spilled_pseudo_regs, int num, ira_assert (reg_renumber[regno] < 0); if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) fprintf (ira_dump_file, - " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), + " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a)); allocno_reload_assign (a, forbidden_regs); @@ -2588,60 +2862,8 @@ ira_reassign_pseudos (int *spilled_pseudo_regs, int num, CLEAR_REGNO_REG_SET (spilled, regno); changed_p = true; } - else - spilled_pseudo_regs[m++] = regno; - } - if (m == 0) - return changed_p; - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - { - fprintf (ira_dump_file, " Spilled regs"); - for (i = 0; i < m; i++) - fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]); - fprintf (ira_dump_file, "\n"); - } - /* Try to assign hard registers to pseudos conflicting with ones - from SPILLED_PSEUDO_REGS. */ - for (i = n = 0; i < m; i++) - { - regno = spilled_pseudo_regs[i]; - a = ira_regno_allocno_map[regno]; - FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci) - if (ALLOCNO_HARD_REGNO (conflict_a) < 0 - && ! ALLOCNO_DONT_REASSIGN_P (conflict_a) - && ! bitmap_bit_p (consideration_allocno_bitmap, - ALLOCNO_NUM (conflict_a))) - { - sorted_allocnos[n++] = conflict_a; - bitmap_set_bit (consideration_allocno_bitmap, - ALLOCNO_NUM (conflict_a)); - } - } - if (n != 0) - { - start_allocno_priorities (sorted_allocnos, n); - qsort (sorted_allocnos, n, sizeof (ira_allocno_t), - allocno_priority_compare_func); - for (i = 0; i < n; i++) - { - a = sorted_allocnos[i]; - regno = ALLOCNO_REGNO (a); - COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs); - IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]); - IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]); - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf (ira_dump_file, - " Try assign %d(a%d), cost=%d", - regno, ALLOCNO_NUM (a), - ALLOCNO_MEMORY_COST (a) - - ALLOCNO_COVER_CLASS_COST (a)); - if (allocno_reload_assign (a, forbidden_regs)) - { - changed_p = true; - bitmap_clear_bit (spilled, regno); - } - } } + BITMAP_FREE (temp); return changed_p; } @@ -2662,7 +2884,7 @@ ira_reuse_stack_slot (int regno, unsigned int inherent_size, bitmap_iterator bi; struct ira_spilled_reg_stack_slot *slot = NULL; - ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno) + ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno) && inherent_size <= total_size && ALLOCNO_HARD_REGNO (allocno) < 0); if (! flag_ira_share_spill_slots) @@ -2689,13 +2911,13 @@ ira_reuse_stack_slot (int regno, unsigned int inherent_size, if (slot->width < total_size || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size) continue; - + EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, FIRST_PSEUDO_REGISTER, i, bi) { another_allocno = ira_regno_allocno_map[i]; - if (ira_allocno_live_ranges_intersect_p (allocno, - another_allocno)) + if (allocnos_have_intersected_live_ranges_p (allocno, + another_allocno)) goto cont; } for (cost = 0, cp = ALLOCNO_COPIES (allocno); @@ -2740,11 +2962,13 @@ ira_reuse_stack_slot (int regno, unsigned int inherent_size, if (x != NULL_RTX) { ira_assert (slot->width >= total_size); +#ifdef ENABLE_IRA_CHECKING EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, FIRST_PSEUDO_REGISTER, i, bi) { - ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i)); + ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i)); } +#endif SET_REGNO_REG_SET (&slot->spilled_regs, regno); if (internal_flag_ira_verbose > 3 && ira_dump_file) { @@ -2772,7 +2996,7 @@ ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size) int slot_num; ira_allocno_t allocno; - ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size); + ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size); allocno = ira_regno_allocno_map[regno]; slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2; if (slot_num == -1) @@ -2820,7 +3044,7 @@ calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn, hard_regno = reg_renumber[regno]; ira_assert (hard_regno >= 0); a = ira_regno_allocno_map[regno]; - length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); + length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a); cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a); nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)]; for (j = 0; j < nregs; j++) @@ -2870,7 +3094,7 @@ ira_better_spill_reload_regno_p (int *regnos, int *other_regnos, int call_used_count, other_call_used_count; int hard_regno, other_hard_regno; - cost = calculate_spill_cost (regnos, in, out, insn, + cost = calculate_spill_cost (regnos, in, out, insn, &length, &nrefs, &call_used_count, &hard_regno); other_cost = calculate_spill_cost (other_regnos, in, out, insn, &other_length, &other_nrefs, @@ -2922,11 +3146,10 @@ ira_finish_assign (void) /* Entry function doing color-based register allocation. */ -void -ira_color (void) +static void +color (void) { allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num); - conflict_allocno_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num); removed_splay_allocno_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num); memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p)); @@ -2934,7 +3157,6 @@ ira_color (void) do_coloring (); ira_finish_assign (); VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec); - VEC_free (ira_allocno_t, heap, conflict_allocno_vec); VEC_free (ira_allocno_t, heap, allocno_stack_vec); move_spill_restore (); } @@ -2947,10 +3169,10 @@ ira_color (void) /* Do register allocation by not using allocno conflicts. It uses only allocno live ranges. The algorithm is close to Chow's priority coloring. */ -void -ira_fast_allocation (void) +static void +fast_allocation (void) { - int i, j, k, l, num, class_size, hard_regno; + int i, j, k, num, class_size, hard_regno; #ifdef STACK_REGS bool no_stack_reg_p; #endif @@ -2958,40 +3180,38 @@ ira_fast_allocation (void) enum machine_mode mode; ira_allocno_t a; ira_allocno_iterator ai; - allocno_live_range_t r; + live_range_t r; HARD_REG_SET conflict_hard_regs, *used_hard_regs; - allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num); - FOR_EACH_ALLOCNO (a, ai) - { - l = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); - if (l <= 0) - l = 1; - allocno_priorities[ALLOCNO_NUM (a)] - = (((double) (floor_log2 (ALLOCNO_NREFS (a)) - * (ALLOCNO_MEMORY_COST (a) - - ALLOCNO_COVER_CLASS_COST (a))) / l) - * (10000 / REG_FREQ_MAX) - * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]); - } - used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET) - * ira_max_point); - for (i = 0; i < ira_max_point; i++) - CLEAR_HARD_REG_SET (used_hard_regs[i]); sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * ira_allocnos_num); num = 0; FOR_EACH_ALLOCNO (a, ai) sorted_allocnos[num++] = a; - qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t), + allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num); + setup_allocno_priorities (sorted_allocnos, num); + used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET) + * ira_max_point); + for (i = 0; i < ira_max_point; i++) + CLEAR_HARD_REG_SET (used_hard_regs[i]); + qsort (sorted_allocnos, num, sizeof (ira_allocno_t), allocno_priority_compare_func); for (i = 0; i < num; i++) { + int nr, l; + a = sorted_allocnos[i]; - COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a)); - for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next) - for (j = r->start; j <= r->finish; j++) - IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]); + nr = ALLOCNO_NUM_OBJECTS (a); + CLEAR_HARD_REG_SET (conflict_hard_regs); + for (l = 0; l < nr; l++) + { + ira_object_t obj = ALLOCNO_OBJECT (a, l); + IOR_HARD_REG_SET (conflict_hard_regs, + OBJECT_CONFLICT_HARD_REGS (obj)); + for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) + for (j = r->start; j <= r->finish; j++) + IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]); + } cover_class = ALLOCNO_COVER_CLASS (a); ALLOCNO_ASSIGNED_P (a) = true; ALLOCNO_HARD_REGNO (a) = -1; @@ -3016,10 +3236,14 @@ ira_fast_allocation (void) (prohibited_class_mode_regs[cover_class][mode], hard_regno))) continue; ALLOCNO_HARD_REGNO (a) = hard_regno; - for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next) - for (k = r->start; k <= r->finish; k++) - IOR_HARD_REG_SET (used_hard_regs[k], - ira_reg_mode_hard_regset[hard_regno][mode]); + for (l = 0; l < nr; l++) + { + ira_object_t obj = ALLOCNO_OBJECT (a, l); + for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) + for (k = r->start; k <= r->finish; k++) + IOR_HARD_REG_SET (used_hard_regs[k], + ira_reg_mode_hard_regset[hard_regno][mode]); + } break; } } @@ -3029,3 +3253,24 @@ ira_fast_allocation (void) if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) ira_print_disposition (ira_dump_file); } + + + +/* Entry function doing coloring. */ +void +ira_color (void) +{ + ira_allocno_t a; + ira_allocno_iterator ai; + + /* Setup updated costs. */ + FOR_EACH_ALLOCNO (a, ai) + { + ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a); + ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a); + } + if (ira_conflicts_p) + color (); + else + fast_allocation (); +}