X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fira-color.c;fp=gcc%2Fira-color.c;h=3f706ef5fbcaf9218030d3fbf087f43b94d2dddf;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/ira-color.c b/gcc/ira-color.c new file mode 100644 index 00000000..3f706ef5 --- /dev/null +++ b/gcc/ira-color.c @@ -0,0 +1,3340 @@ +/* IRA allocation based on graph coloring. + Copyright (C) 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. + Contributed by Vladimir Makarov . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "rtl.h" +#include "tm_p.h" +#include "target.h" +#include "regs.h" +#include "flags.h" +#include "sbitmap.h" +#include "bitmap.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "expr.h" +#include "toplev.h" +#include "reload.h" +#include "params.h" +#include "df.h" +#include "splay-tree.h" +#include "ira-int.h" + +/* This file contains code for regional graph coloring, spill/restore + code placement optimization, and code helping the reload pass to do + a better job. */ + +/* Bitmap of allocnos which should be colored. */ +static bitmap coloring_allocno_bitmap; + +/* Bitmap of allocnos which should be taken into account during + coloring. In general case it contains allocnos from + coloring_allocno_bitmap plus other already colored conflicting + 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; + +/* Array used to choose an allocno for spilling. */ +static ira_allocno_t *allocnos_for_spilling; + +/* Pool for splay tree nodes. */ +static alloc_pool splay_tree_node_pool; + +/* When an allocno is removed from the splay tree, it is put in the + following vector for subsequent inserting it into the splay tree + after putting all colorable allocnos onto the stack. The allocno + could be removed from and inserted to the splay tree every time + when its spilling priority is changed but such solution would be + more costly although simpler. */ +static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec; + + + +/* 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) +{ + 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; + return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1), + ALLOCNO_LIVE_RANGES (a2)); +} + +#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 + allocnos. */ + +/* Array whose element value is TRUE if the corresponding hard + register was already allocated for an allocno. */ +static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]; + +/* 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; + +/* Allocate and initialize data necessary for function + update_copy_costs. */ +static void +initiate_cost_update (void) +{ + 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; +} + +/* Deallocate data used by function update_copy_costs. */ +static void +finish_cost_update (void) +{ + ira_free (update_cost_queue_elems); +} + +/* When we traverse allocnos to update hard register costs, the cost + divisor will be multiplied by the following macro value for each + hop from given allocno to directly connected allocnos. */ +#define COST_HOP_DIVISOR 4 + +/* Start a new cost-updating pass. */ +static void +start_update_cost (void) +{ + update_cost_check++; + update_cost_queue = NULL; +} + +/* 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) + { + elem->check = update_cost_check; + elem->divisor = divisor; + elem->next = NULL; + if (update_cost_queue == NULL) + update_cost_queue = allocno; + else + update_cost_queue_tail->next = allocno; + update_cost_queue_tail = elem; + } +} + +/* 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) +{ + 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; +} + +/* 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) +{ + int i, cost, update_cost, hard_regno, divisor; + enum machine_mode mode; + 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); + if (cover_class == NO_REGS) + return; + 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 + { + mode = ALLOCNO_MODE (allocno); + 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 (); + + cover_class = ALLOCNO_COVER_CLASS (another_allocno); + if (! ira_reg_classes_intersect_p[rclass][cover_class] + || ALLOCNO_ASSIGNED_P (another_allocno)) + continue; + + 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; + + 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)); +} + +/* 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 +update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class, + bool decr_p) +{ + 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; + + 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 (ALLOCNO_FIRST_COALESCED_ALLOCNO + (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); + } +} + +/* Sort allocnos according to the profit of usage of a hard register + instead of memory for them. */ +static int +allocno_cost_compare_func (const void *v1p, const void *v2p) +{ + ira_allocno_t p1 = *(const ira_allocno_t *) v1p; + ira_allocno_t p2 = *(const ira_allocno_t *) v2p; + int c1, c2; + + c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1); + c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2); + if (c1 - c2) + return c1 - c2; + + /* If regs are equally good, sort by allocno numbers, so that the + results of qsort leave nothing to chance. */ + return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2); +} + +/* Print all allocnos coalesced with ALLOCNO. */ +static void +print_coalesced_allocno (ira_allocno_t allocno) +{ + ira_allocno_t a; + + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + ira_print_expanded_allocno (a); + if (a == allocno) + break; + fprintf (ira_dump_file, "+"); + } +} + +/* Choose a hard register for ALLOCNO (or for all coalesced allocnos + represented by ALLOCNO). If RETRY_P is TRUE, it means that the + function called from function `ira_reassign_conflict_allocnos' and + `allocno_reload_assign'. This function implements the optimistic + coalescing too: if we failed to assign a hard register to set of + the coalesced allocnos, we put them onto the coloring stack for + subsequent separate assigning. */ +static bool +assign_hard_reg (ira_allocno_t allocno, bool retry_p) +{ + HARD_REG_SET conflicting_regs; + int i, j, k, hard_regno, best_hard_regno, class_size; + int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost; + int *a_costs; + int *conflict_costs; + enum reg_class cover_class, rclass, conflict_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]; +#ifdef STACK_REGS + bool no_stack_reg_p; +#endif + + ira_assert (! ALLOCNO_ASSIGNED_P (allocno)); + cover_class = ALLOCNO_COVER_CLASS (allocno); + class_size = ira_class_hard_regs_num[cover_class]; + mode = ALLOCNO_MODE (allocno); + CLEAR_HARD_REG_SET (conflicting_regs); + best_hard_regno = -1; + memset (full_costs, 0, sizeof (int) * class_size); + mem_cost = 0; + if (allocno_coalesced_p) + bitmap_clear (processed_coalesced_allocno_bitmap); + memset (costs, 0, sizeof (int) * class_size); + memset (full_costs, 0, sizeof (int) * class_size); +#ifdef STACK_REGS + no_stack_reg_p = false; +#endif + start_update_cost (); + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + 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); +#ifdef STACK_REGS + no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a); +#endif + for (cost = ALLOCNO_UPDATED_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; + } + /* 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))) + { + conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno); + ira_assert (ira_reg_classes_intersect_p + [cover_class][conflict_cover_class]); + 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 + && ira_class_hard_reg_index[cover_class][hard_regno] >= 0) + { + 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; + } + } + else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO + (conflict_allocno))) + { + ira_allocate_and_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno), + conflict_cover_class, + ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno)); + conflict_costs + = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno); + if (conflict_costs != NULL) + for (j = class_size - 1; j >= 0; j--) + { + hard_regno = ira_class_hard_regs[cover_class][j]; + ira_assert (hard_regno >= 0); + k = (ira_class_hard_reg_index + [conflict_cover_class][hard_regno]); + if (k < 0) + continue; + full_costs[j] -= conflict_costs[k]; + } + queue_update_cost (conflict_allocno, COST_HOP_DIVISOR); + } + } + if (a == allocno) + break; + } + /* Take into account preferences of allocnos connected by copies to + the conflict allocnos. */ + update_conflict_hard_regno_costs (full_costs, cover_class, true); + + /* Take preferences of allocnos connected by copies into + account. */ + start_update_cost (); + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + queue_update_cost (a, COST_HOP_DIVISOR); + if (a == allocno) + break; + } + 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 + REG_ALLOC_ORDER). */ + for (i = 0; i < class_size; i++) + { + hard_regno = ira_class_hard_regs[cover_class][i]; +#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)) + continue; + cost = costs[i]; + full_cost = full_costs[i]; + 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 + epilogue/prologue. Therefore we increase the cost. */ + { + /* ??? If only part is call clobbered. */ + rclass = REGNO_REG_CLASS (hard_regno); + add_cost = (ira_memory_move_cost[mode][rclass][0] + + ira_memory_move_cost[mode][rclass][1] - 1); + cost += add_cost; + full_cost += add_cost; + } + if (min_cost > cost) + min_cost = cost; + if (min_full_cost > full_cost) + { + min_full_cost = full_cost; + best_hard_regno = hard_regno; + ira_assert (hard_regno >= 0); + } + } + if (min_full_cost > mem_cost) + { + if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ", + mem_cost, min_full_cost); + best_hard_regno = -1; + } + fail: + if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY + && best_hard_regno < 0 + && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno) + { + for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + ira_assert (! ALLOCNO_IN_GRAPH_P (a)); + sorted_allocnos[j++] = a; + if (a == allocno) + break; + } + qsort (sorted_allocnos, j, sizeof (ira_allocno_t), + allocno_cost_compare_func); + for (i = 0; i < j; i++) + { + a = sorted_allocnos[i]; + ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a; + ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a; + VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " Pushing"); + print_coalesced_allocno (a); + fprintf (ira_dump_file, "\n"); + } + } + return false; + } + if (best_hard_regno >= 0) + allocated_hardreg_p[best_hard_regno] = true; + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + ALLOCNO_HARD_REGNO (a) = best_hard_regno; + ALLOCNO_ASSIGNED_P (a) = true; + if (best_hard_regno >= 0) + update_copy_costs (a, true); + ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class); + /* We don't need updated costs anymore: */ + ira_free_allocno_updated_costs (a); + if (a == allocno) + break; + } + return best_hard_regno >= 0; +} + + + +/* This page contains the allocator based on the Chaitin-Briggs algorithm. */ + +/* Bucket of allocnos that can colored currently without spilling. */ +static ira_allocno_t colorable_allocno_bucket; + +/* Bucket of allocnos that might be not colored currently without + spilling. */ +static ira_allocno_t uncolorable_allocno_bucket; + +/* Each element of the array contains the current number of allocnos + 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_NUM (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_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) +{ + ira_allocno_t first_allocno; + enum reg_class cover_class; + + if (bucket_ptr == &uncolorable_allocno_bucket + && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS) + { + uncolorable_allocnos_num[cover_class]++; + ira_assert (uncolorable_allocnos_num[cover_class] > 0); + } + first_allocno = *bucket_ptr; + ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno; + ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL; + if (first_allocno != NULL) + ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno; + *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 + case such allocno has less priority than the second one and the + hard register will be assigned to it after assignment to the second + one. As the result of such assignment order, the second allocno + has a better chance to get the best hard register. */ +static int +bucket_allocno_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; + int diff, a1_freq, a2_freq, a1_num, a2_num; + + 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); + if ((diff = a2_num - a1_num) != 0) + return diff; + else if ((diff = a1_freq - a2_freq) != 0) + return diff; + return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1); +} + +/* Sort bucket *BUCKET_PTR and return the result through + BUCKET_PTR. */ +static void +sort_bucket (ira_allocno_t *bucket_ptr) +{ + ira_allocno_t a, head; + int n; + + for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a)) + sorted_allocnos[n++] = a; + if (n <= 1) + return; + qsort (sorted_allocnos, n, sizeof (ira_allocno_t), + bucket_allocno_compare_func); + head = NULL; + for (n--; n >= 0; n--) + { + a = sorted_allocnos[n]; + ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head; + ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL; + if (head != NULL) + ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a; + head = a; + } + *bucket_ptr = head; +} + +/* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according + their priority. ALLOCNO should be not in a bucket before the + call. */ +static void +add_allocno_to_ordered_bucket (ira_allocno_t allocno, + ira_allocno_t *bucket_ptr) +{ + ira_allocno_t before, after; + enum reg_class cover_class; + + if (bucket_ptr == &uncolorable_allocno_bucket + && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS) + { + uncolorable_allocnos_num[cover_class]++; + ira_assert (uncolorable_allocnos_num[cover_class] > 0); + } + for (before = *bucket_ptr, after = NULL; + before != NULL; + after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before)) + if (bucket_allocno_compare_func (&allocno, &before) < 0) + break; + ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before; + ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after; + if (after == NULL) + *bucket_ptr = allocno; + else + ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno; + if (before != NULL) + ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno; +} + +/* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before + the call. */ +static void +delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr) +{ + ira_allocno_t prev_allocno, next_allocno; + enum reg_class cover_class; + + if (bucket_ptr == &uncolorable_allocno_bucket + && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS) + { + uncolorable_allocnos_num[cover_class]--; + ira_assert (uncolorable_allocnos_num[cover_class] >= 0); + } + prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno); + next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno); + if (prev_allocno != NULL) + ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno; + else + { + ira_assert (*bucket_ptr == allocno); + *bucket_ptr = next_allocno; + } + if (next_allocno != NULL) + ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno; +} + +/* Splay tree for each cover class. The trees are indexed by the + corresponding cover classes. Splay trees contain uncolorable + allocnos. */ +static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES]; + +/* If the following macro is TRUE, splay tree is used to choose an + allocno of the corresponding cover class for spilling. When the + number uncolorable allocnos of given cover class decreases to some + threshold, linear array search is used to find the best allocno for + spilling. This threshold is actually pretty big because, although + splay trees asymptotically is much faster, each splay tree + operation is sufficiently costly especially taking cache locality + into account. */ +#define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000) + +/* Put ALLOCNO onto the coloring stack without removing it from its + bucket. Pushing allocno to the coloring stack can result in moving + conflicting allocnos from the uncolorable bucket to the colorable + one. */ +static void +push_allocno_to_stack (ira_allocno_t allocno) +{ + int conflicts_num, conflict_size, size; + ira_allocno_t a, conflict_allocno; + 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); + 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)) + { + FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci) + { + conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno); + 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_allocno_to_ordered_bucket + (conflict_allocno, &colorable_allocno_bucket); + } + } + } + } + if (a == allocno) + break; + } +} + +/* Put ALLOCNO onto the coloring stack and remove it from its bucket. + The allocno is in the colorable bucket if COLORABLE_P is TRUE. */ +static void +remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p) +{ + enum reg_class cover_class; + + if (colorable_p) + delete_allocno_from_bucket (allocno, &colorable_allocno_bucket); + else + delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " Pushing"); + print_coalesced_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) + + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] + <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))) + || (! colorable_p + && (ALLOCNO_LEFT_CONFLICTS_NUM (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_allocno_to_stack (allocno); +} + +/* Put all allocnos from colorable bucket onto the coloring stack. */ +static void +push_only_colorable (void) +{ + sort_bucket (&colorable_allocno_bucket); + for (;colorable_allocno_bucket != NULL;) + remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true); +} + +/* Puts ALLOCNO chosen for potential spilling onto the coloring + stack. */ +static void +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) (spill for NO_REGS)\n", + ALLOCNO_NUM (allocno), ALLOCNO_REGNO (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. */ +int +ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p) +{ + int freq, i; + edge_iterator ei; + edge e; + VEC (edge, heap) *edges; + + ira_assert (loop_node->loop != NULL + && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER)); + freq = 0; + if (! exit_p) + { + FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds) + if (e->src != loop_node->loop->latch + && (regno < 0 + || (bitmap_bit_p (DF_LR_OUT (e->src), regno) + && bitmap_bit_p (DF_LR_IN (e->dest), regno)))) + freq += EDGE_FREQUENCY (e); + } + else + { + edges = get_loop_exit_edges (loop_node->loop); + for (i = 0; VEC_iterate (edge, edges, i, e); i++) + if (regno < 0 + || (bitmap_bit_p (DF_LR_OUT (e->src), regno) + && bitmap_bit_p (DF_LR_IN (e->dest), regno))) + freq += EDGE_FREQUENCY (e); + VEC_free (edge, heap, edges); + } + + return REG_FREQ_FROM_EDGE_FREQ (freq); +} + +/* Calculate and return the cost of putting allocno A into memory. */ +static int +calculate_allocno_spill_cost (ira_allocno_t a) +{ + int regno, cost; + enum machine_mode mode; + enum reg_class rclass; + ira_allocno_t parent_allocno; + ira_loop_tree_node_t parent_node, loop_node; + + regno = ALLOCNO_REGNO (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); + if ((parent_node = loop_node->parent) == NULL) + return cost; + if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL) + return cost; + mode = ALLOCNO_MODE (a); + rclass = ALLOCNO_COVER_CLASS (a); + if (ALLOCNO_HARD_REGNO (parent_allocno) < 0) + cost -= (ira_memory_move_cost[mode][rclass][0] + * ira_loop_edge_freq (loop_node, regno, true) + + ira_memory_move_cost[mode][rclass][1] + * ira_loop_edge_freq (loop_node, regno, false)); + else + cost += ((ira_memory_move_cost[mode][rclass][1] + * ira_loop_edge_freq (loop_node, regno, true) + + ira_memory_move_cost[mode][rclass][0] + * ira_loop_edge_freq (loop_node, regno, false)) + - (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; +} + +/* Compare keys in the splay tree used to choose best allocno for + spilling. The best allocno has the minimal key. */ +static int +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 = (ALLOCNO_TEMP (a1) + / (ALLOCNO_LEFT_CONFLICTS_NUM (a1) + * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)] + + 1)); + pri2 = (ALLOCNO_TEMP (a2) + / (ALLOCNO_LEFT_CONFLICTS_NUM (a2) + * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)] + + 1)); + if ((diff = pri1 - pri2) != 0) + return diff; + if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0) + return diff; + return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); +} + +/* Allocate data of SIZE for the splay trees. We allocate only spay + tree roots or splay tree nodes. If you change this, please rewrite + the function. */ +static void * +splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED) +{ + if (size != sizeof (struct splay_tree_node_s)) + return ira_allocate (size); + return pool_alloc (splay_tree_node_pool); +} + +/* Free data NODE for the splay trees. We allocate and free only spay + tree roots or splay tree nodes. If you change this, please rewrite + the function. */ +static void +splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED) +{ + int i; + enum reg_class cover_class; + + for (i = 0; i < ira_reg_class_cover_size; i++) + { + cover_class = ira_reg_class_cover[i]; + if (node == uncolorable_allocnos_splay_tree[cover_class]) + { + ira_free (node); + return; + } + } + pool_free (splay_tree_node_pool, node); +} + +/* Push allocnos to the coloring stack. The order of allocnos in the + stack defines the order for the subsequent coloring. */ +static void +push_allocnos_to_stack (void) +{ + ira_allocno_t allocno, a, 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]; + ira_allocno_t *cover_class_allocnos[N_REG_CLASSES]; + int cost; + + /* Initialize. */ + VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0); + for (i = 0; i < ira_reg_class_cover_size; i++) + { + cover_class = ira_reg_class_cover[i]; + cover_class_allocnos_num[cover_class] = 0; + cover_class_allocnos[cover_class] = NULL; + uncolorable_allocnos_splay_tree[cover_class] = NULL; + } + /* Calculate uncolorable allocno spill costs. */ + for (allocno = uncolorable_allocno_bucket; + allocno != NULL; + allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno)) + 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. */ + ALLOCNO_TEMP (allocno) = cost; + } + /* Define place where to put uncolorable allocnos of the same cover + class. */ + for (num = i = 0; i < ira_reg_class_cover_size; i++) + { + cover_class = ira_reg_class_cover[i]; + ira_assert (cover_class_allocnos_num[cover_class] + == uncolorable_allocnos_num[cover_class]); + if (cover_class_allocnos_num[cover_class] != 0) + { + cover_class_allocnos[cover_class] = allocnos_for_spilling + num; + num += cover_class_allocnos_num[cover_class]; + cover_class_allocnos_num[cover_class] = 0; + } + if (USE_SPLAY_P (cover_class)) + uncolorable_allocnos_splay_tree[cover_class] + = splay_tree_new_with_allocator (allocno_spill_priority_compare, + NULL, NULL, splay_tree_allocate, + splay_tree_free, NULL); + } + ira_assert (num <= ira_allocnos_num); + /* Collect uncolorable allocnos of each cover class. */ + for (allocno = uncolorable_allocno_bucket; + allocno != NULL; + allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno)) + if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS) + { + cover_class_allocnos + [cover_class][cover_class_allocnos_num[cover_class]++] = allocno; + if (uncolorable_allocnos_splay_tree[cover_class] != NULL) + splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class], + (splay_tree_key) allocno, + (splay_tree_value) allocno); + } + for (;;) + { + push_only_colorable (); + allocno = uncolorable_allocno_bucket; + if (allocno == NULL) + break; + cover_class = ALLOCNO_COVER_CLASS (allocno); + if (cover_class == NO_REGS) + { + push_allocno_to_spill (allocno); + continue; + } + /* Potential spilling. */ + ira_assert + (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0); + if (USE_SPLAY_P (cover_class)) + { + for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;) + { + 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) + + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)] + > ALLOCNO_AVAILABLE_REGS_NUM (allocno)) + splay_tree_insert + (uncolorable_allocnos_splay_tree[rclass], + (splay_tree_key) allocno, (splay_tree_value) allocno); + } + allocno = ((ira_allocno_t) + splay_tree_min + (uncolorable_allocnos_splay_tree[cover_class])->key); + splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class], + (splay_tree_key) allocno); + } + else + { + num = cover_class_allocnos_num[cover_class]; + ira_assert (num > 0); + allocno_vec = cover_class_allocnos[cover_class]; + allocno = NULL; + allocno_pri = allocno_cost = 0; + /* Sort uncolorable allocno to find the one with the lowest + spill cost. */ + for (i = 0, j = num - 1; i <= j;) + { + i_allocno = allocno_vec[i]; + if (! ALLOCNO_IN_GRAPH_P (i_allocno) + && ALLOCNO_IN_GRAPH_P (allocno_vec[j])) + { + i_allocno = allocno_vec[j]; + allocno_vec[j] = allocno_vec[i]; + allocno_vec[i] = i_allocno; + } + if (ALLOCNO_IN_GRAPH_P (i_allocno)) + { + i++; + 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; + allocno_pri = i_allocno_pri; + } + } + if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j])) + j--; + } + ira_assert (allocno != NULL && j >= 0); + cover_class_allocnos_num[cover_class] = j + 1; + } + ira_assert (ALLOCNO_IN_GRAPH_P (allocno) + && ALLOCNO_COVER_CLASS (allocno) == cover_class + && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + + ira_reg_class_nregs[cover_class][ALLOCNO_MODE + (allocno)] + > ALLOCNO_AVAILABLE_REGS_NUM (allocno))); + remove_allocno_from_bucket_and_push (allocno, false); + } + ira_assert (colorable_allocno_bucket == NULL + && uncolorable_allocno_bucket == NULL); + for (i = 0; i < ira_reg_class_cover_size; i++) + { + cover_class = ira_reg_class_cover[i]; + ira_assert (uncolorable_allocnos_num[cover_class] == 0); + if (uncolorable_allocnos_splay_tree[cover_class] != NULL) + splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]); + } +} + +/* Pop the coloring stack and assign hard registers to the popped + allocnos. */ +static void +pop_allocnos_from_stack (void) +{ + ira_allocno_t allocno; + enum reg_class cover_class; + + for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;) + { + allocno = VEC_pop (ira_allocno_t, allocno_stack_vec); + cover_class = ALLOCNO_COVER_CLASS (allocno); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " Popping"); + print_coalesced_allocno (allocno); + fprintf (ira_dump_file, " -- "); + } + if (cover_class == NO_REGS) + { + ALLOCNO_HARD_REGNO (allocno) = -1; + ALLOCNO_ASSIGNED_P (allocno) = true; + ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL); + ira_assert + (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "assign memory\n"); + } + else if (assign_hard_reg (allocno, false)) + { + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "assign reg %d\n", + ALLOCNO_HARD_REGNO (allocno)); + } + else if (ALLOCNO_ASSIGNED_P (allocno)) + { + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "spill\n"); + } + ALLOCNO_IN_GRAPH_P (allocno) = true; + } +} + +/* Set up number of available hard registers for ALLOCNO. */ +static void +setup_allocno_available_regs_num (ira_allocno_t allocno) +{ + int i, n, hard_regs_num; + 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]; + if (cover_class == NO_REGS) + return; + CLEAR_HARD_REG_SET (temp_set); + ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno); + hard_regs_num = ira_class_hard_regs_num[cover_class]; + 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; + } + 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; +} + +/* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */ +static void +setup_allocno_left_conflicts_num (ira_allocno_t allocno) +{ + 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); + 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; + } + 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++) + { + hard_regno = ira_class_hard_regs[cover_class][i]; + if (TEST_HARD_REG_BIT (temp_set, hard_regno)) + { + conflict_allocnos_size++; + CLEAR_HARD_REG_BIT (temp_set, hard_regno); + if (hard_reg_set_empty_p (temp_set)) + break; + } + } + 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) + { + conflict_allocno + = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno); + if (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)) + conflict_allocnos_size + += (ira_reg_class_nregs + [cover_class][ALLOCNO_MODE (conflict_allocno)]); + else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) + >= 0) + { + int last = (hard_regno + + hard_regno_nregs + [hard_regno][ALLOCNO_MODE (conflict_allocno)]); + + while (hard_regno < last) + { + if (! TEST_HARD_REG_BIT (temp_set, hard_regno)) + { + conflict_allocnos_size++; + SET_HARD_REG_BIT (temp_set, hard_regno); + } + hard_regno++; + } + } + } + } + if (a == allocno) + break; + } + ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size; +} + +/* Put ALLOCNO in a bucket corresponding to its number and size of its + conflicting allocnos and hard registers. */ +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_available_regs_num (allocno); + if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno) + + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] + <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)) + add_allocno_to_bucket (allocno, &colorable_allocno_bucket); + else + 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; +} + +/* 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; +} + +/* 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) +{ + ira_allocno_t a, conflict_allocno; + ira_allocno_conflict_iterator aci; + + 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 (allocnos_have_intersected_live_ranges_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; +} + +/* The major function for aggressive allocno coalescing. For the + reload pass (RELOAD_P) we coalesce only spilled allocnos. If some + allocnos have been coalesced, we set up flag + allocno_coalesced_p. */ +static void +coalesce_allocnos (bool reload_p) +{ + ira_allocno_t a; + ira_copy_t cp, next_cp, *sorted_copies; + enum reg_class cover_class; + enum machine_mode mode; + unsigned int j; + int i, n, cp_num, regno; + bitmap_iterator bi; + + sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num + * sizeof (ira_copy_t)); + cp_num = 0; + /* Collect copies. */ + EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi) + { + a = ira_allocnos[j]; + regno = ALLOCNO_REGNO (a); + if ((! reload_p && ALLOCNO_ASSIGNED_P (a)) + || (reload_p + && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0 + || (regno < ira_reg_equiv_len + && (ira_reg_equiv_const[regno] != NULL_RTX + || ira_reg_equiv_invariant_p[regno]))))) + continue; + cover_class = ALLOCNO_COVER_CLASS (a); + mode = ALLOCNO_MODE (a); + for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) + { + if (cp->first == a) + { + next_cp = cp->next_first_allocno_copy; + regno = ALLOCNO_REGNO (cp->second); + /* For priority coloring we coalesce allocnos only with + the same cover class not with intersected cover + classes as it were possible. It is done for + simplicity. */ + if ((reload_p + || (ALLOCNO_COVER_CLASS (cp->second) == cover_class + && ALLOCNO_MODE (cp->second) == mode)) + && (cp->insn != NULL || cp->constraint_p) + && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second)) + || (reload_p + && ALLOCNO_ASSIGNED_P (cp->second) + && ALLOCNO_HARD_REGNO (cp->second) < 0 + && (regno >= ira_reg_equiv_len + || (! ira_reg_equiv_invariant_p[regno] + && ira_reg_equiv_const[regno] == NULL_RTX))))) + sorted_copies[cp_num++] = cp; + } + else if (cp->second == a) + next_cp = cp->next_second_allocno_copy; + else + gcc_unreachable (); + } + } + qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func); + /* Coalesced copies, most frequently executed first. */ + for (; cp_num != 0;) + { + for (i = 0; i < cp_num; i++) + { + cp = sorted_copies[i]; + if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p)) + { + allocno_coalesced_p = true; + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf + (ira_dump_file, + " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n", + cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first), + ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), + cp->freq); + merge_allocnos (cp->first, cp->second); + i++; + break; + } + } + /* Collect the rest of copies. */ + for (n = 0; i < cp_num; i++) + { + cp = sorted_copies[i]; + if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first) + != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second)) + sorted_copies[n++] = cp; + } + cp_num = n; + } + ira_free (sorted_copies); +} + +/* Map: allocno number -> allocno priority. */ +static int *allocno_priorities; + +/* Set up priorities for N allocnos in array + CONSIDERATION_ALLOCNOS. */ +static void +setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n) +{ + int i, length, nrefs, priority, max_priority, mult; + ira_allocno_t a; + + max_priority = 0; + for (i = 0; i < n; i++) + { + 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 (length <= 0) + length = 1; + allocno_priorities[ALLOCNO_NUM (a)] + = allocno_priorities[ALLOCNO_NUM (a)] * mult / length; + } +} + +/* 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 a1 = *(const ira_allocno_t *) v1p; + ira_allocno_t a2 = *(const ira_allocno_t *) v2p; + int pri1, pri2; + + pri1 = allocno_priorities[ALLOCNO_NUM (a1)]; + pri2 = allocno_priorities[ALLOCNO_NUM (a2)]; + 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); +} + +/* 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, n; + bitmap_iterator bi; + ira_allocno_t a; + + allocno_coalesced_p = false; + processed_coalesced_allocno_bitmap = ira_allocate_bitmap (); + if (flag_ira_coalesce) + coalesce_allocnos (false); + if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY) + { + n = 0; + EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) + { + a = ira_allocnos[i]; + if (ALLOCNO_COVER_CLASS (a) == NO_REGS) + { + 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"); + print_coalesced_allocno (a); + fprintf (ira_dump_file, "\n"); + } + continue; + } + sorted_allocnos[n++] = a; + } + if (n != 0) + { + setup_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]; + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " "); + print_coalesced_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"); + } + } + } + } + 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) + { + a = ira_allocnos[i]; + if (ALLOCNO_COVER_CLASS (a) == NO_REGS) + { + 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"); + print_coalesced_allocno (a); + fprintf (ira_dump_file, "\n"); + } + continue; + } + put_allocno_into_bucket (a); + } + 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; +} + + + +/* Output information about the loop given by its LOOP_TREE_NODE. */ +static void +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 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:"); + EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi) + fprintf (ira_dump_file, " %d", j); + fprintf (ira_dump_file, "\n border:"); + EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi) + fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j])); + fprintf (ira_dump_file, "\n Pressure:"); + 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; + fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class], + loop_tree_node->reg_pressure[cover_class]); + } + fprintf (ira_dump_file, "\n"); +} + +/* Color the allocnos inside loop (in the extreme case it can be all + of the function) given the corresponding LOOP_TREE_NODE. The + function is called for each loop during top-down traverse of the + loop tree. */ +static void +color_pass (ira_loop_tree_node_t loop_tree_node) +{ + int regno, hard_regno, index = -1; + int cost, exit_freq, enter_freq; + unsigned int j; + bitmap_iterator bi; + enum machine_mode mode; + enum reg_class rclass, cover_class; + ira_allocno_t a, subloop_allocno; + ira_loop_tree_node_t subloop_node; + + ira_assert (loop_tree_node->bb == NULL); + if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) + print_loop_title (loop_tree_node); + + bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos); + bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap); + EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) + { + a = ira_allocnos[j]; + if (! ALLOCNO_ASSIGNED_P (a)) + continue; + 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_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]; + if (ALLOCNO_CAP_MEMBER (a) == NULL) + continue; + /* Remove from processing in the next loop. */ + bitmap_clear_bit (consideration_allocno_bitmap, j); + rclass = ALLOCNO_COVER_CLASS (a); + 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); + if (hard_regno >= 0) + { + index = ira_class_hard_reg_index[rclass][hard_regno]; + ira_assert (index >= 0); + } + regno = ALLOCNO_REGNO (a); + subloop_allocno = ALLOCNO_CAP_MEMBER (a); + subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno); + ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno)); + ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; + ALLOCNO_ASSIGNED_P (subloop_allocno) = true; + if (hard_regno >= 0) + update_copy_costs (subloop_allocno, true); + /* We don't need updated costs anymore: */ + ira_free_allocno_updated_costs (subloop_allocno); + } + } + /* Update costs of the corresponding allocnos (not caps) in the + subloops. */ + for (subloop_node = loop_tree_node->subloops; + subloop_node != NULL; + subloop_node = subloop_node->subloop_next) + { + ira_assert (subloop_node->bb == NULL); + EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi) + { + a = ira_allocnos[j]; + ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); + 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]; + ira_assert (index >= 0); + } + regno = ALLOCNO_REGNO (a); + /* ??? conflict costs */ + subloop_allocno = subloop_node->regno_allocno_map[regno]; + 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_region == IRA_REGION_MIXED) + && (loop_tree_node->reg_pressure[rclass] + <= ira_available_class_regs[rclass])) + { + if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) + { + ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; + ALLOCNO_ASSIGNED_P (subloop_allocno) = true; + if (hard_regno >= 0) + update_copy_costs (subloop_allocno, true); + /* We don't need updated costs anymore: */ + ira_free_allocno_updated_costs (subloop_allocno); + } + continue; + } + exit_freq = ira_loop_edge_freq (subloop_node, regno, true); + enter_freq = ira_loop_edge_freq (subloop_node, regno, false); + ira_assert (regno < ira_reg_equiv_len); + if (ira_reg_equiv_invariant_p[regno] + || ira_reg_equiv_const[regno] != NULL_RTX) + { + if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) + { + ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; + ALLOCNO_ASSIGNED_P (subloop_allocno) = true; + if (hard_regno >= 0) + update_copy_costs (subloop_allocno, true); + /* We don't need updated costs anymore: */ + ira_free_allocno_updated_costs (subloop_allocno); + } + } + else if (hard_regno < 0) + { + ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno) + -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq) + + (ira_memory_move_cost[mode][rclass][0] * exit_freq)); + } + else + { + cover_class = ALLOCNO_COVER_CLASS (subloop_allocno); + cost = (ira_get_register_move_cost (mode, rclass, rclass) + * (exit_freq + enter_freq)); + 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); + } + } + } +} + +/* Initialize the common data for coloring and calls functions to do + Chaitin-Briggs and regional coloring. */ +static void +do_coloring (void) +{ + coloring_allocno_bitmap = ira_allocate_bitmap (); + allocnos_for_spilling + = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) + * ira_allocnos_num); + splay_tree_node_pool = create_alloc_pool ("splay tree nodes", + sizeof (struct splay_tree_node_s), + 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) + ira_print_disposition (ira_dump_file); + + free_alloc_pool (splay_tree_node_pool); + ira_free_bitmap (coloring_allocno_bitmap); + ira_free (allocnos_for_spilling); +} + + + +/* Move spill/restore code, which are to be generated in ira-emit.c, + to less frequent points (if it is profitable) by reassigning some + allocnos (in loop with subloops containing in another loop) to + memory which results in longer live-range where the corresponding + pseudo-registers will be in memory. */ +static void +move_spill_restore (void) +{ + int cost, regno, hard_regno, hard_regno2, index; + bool changed_p; + int enter_freq, exit_freq; + enum machine_mode mode; + enum reg_class rclass; + ira_allocno_t a, parent_allocno, subloop_allocno; + ira_loop_tree_node_t parent, loop_node, subloop_node; + ira_allocno_iterator ai; + + for (;;) + { + changed_p = false; + if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) + fprintf (ira_dump_file, "New iteration of spill/restore move\n"); + FOR_EACH_ALLOCNO (a, ai) + { + regno = ALLOCNO_REGNO (a); + loop_node = ALLOCNO_LOOP_TREE_NODE (a); + if (ALLOCNO_CAP_MEMBER (a) != NULL + || ALLOCNO_CAP (a) != NULL + || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0 + || loop_node->children == NULL + /* don't do the optimization because it can create + copies and the reload pass can spill the allocno set + by copy although the allocno will not get memory + slot. */ + || ira_reg_equiv_invariant_p[regno] + || ira_reg_equiv_const[regno] != NULL_RTX + || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))) + continue; + mode = ALLOCNO_MODE (a); + rclass = ALLOCNO_COVER_CLASS (a); + index = ira_class_hard_reg_index[rclass][hard_regno]; + ira_assert (index >= 0); + cost = (ALLOCNO_MEMORY_COST (a) + - (ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a)[index])); + for (subloop_node = loop_node->subloops; + subloop_node != NULL; + subloop_node = subloop_node->subloop_next) + { + ira_assert (subloop_node->bb == NULL); + 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. */ + cost -= (ALLOCNO_MEMORY_COST (subloop_allocno) + - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL + ? ALLOCNO_COVER_CLASS_COST (subloop_allocno) + : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])); + exit_freq = ira_loop_edge_freq (subloop_node, regno, true); + enter_freq = ira_loop_edge_freq (subloop_node, regno, false); + if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0) + cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq + + ira_memory_move_cost[mode][rclass][1] * enter_freq); + else + { + cost + += (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_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) + cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq + + ira_memory_move_cost[mode][rclass][1] * enter_freq); + else + { + cost + += (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_get_register_move_cost (mode, rclass, rclass) + * (exit_freq + enter_freq)); + } + } + if (cost < 0) + { + ALLOCNO_HARD_REGNO (a) = -1; + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf + (ira_dump_file, + " Moving spill/restore for a%dr%d up from loop %d", + ALLOCNO_NUM (a), regno, loop_node->loop->num); + fprintf (ira_dump_file, " - profit %d\n", -cost); + } + changed_p = true; + } + } + if (! changed_p) + break; + } +} + + + +/* Update current hard reg costs and current conflict hard reg costs + for allocno A. It is done by processing its copies containing + other allocnos already assigned. */ +static void +update_curr_costs (ira_allocno_t a) +{ + int i, hard_regno, cost; + enum machine_mode mode; + enum reg_class cover_class, rclass; + ira_allocno_t another_a; + ira_copy_t cp, next_cp; + + ira_assert (! ALLOCNO_ASSIGNED_P (a)); + cover_class = ALLOCNO_COVER_CLASS (a); + if (cover_class == NO_REGS) + return; + mode = ALLOCNO_MODE (a); + for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) + { + if (cp->first == a) + { + next_cp = cp->next_first_allocno_copy; + another_a = cp->second; + } + else if (cp->second == a) + { + next_cp = cp->next_second_allocno_copy; + another_a = cp->first; + } + else + gcc_unreachable (); + 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]; + if (i < 0) + continue; + cost = (cp->first == a + ? 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), + ALLOCNO_HARD_REG_COSTS (a)); + ira_allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), + cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); + ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost; + ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost; + } +} + +/* 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, 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; + + allocnos_to_color = ira_allocate_bitmap (); + allocnos_to_color_num = 0; + FOR_EACH_ALLOCNO (a, ai) + { + if (! ALLOCNO_ASSIGNED_P (a) + && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a))) + { + 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_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci) + { + ira_assert (ira_reg_classes_intersect_p + [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; + } + } + 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; + 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++) + { + 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)); + } + } +} + + + +/* 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; +static int *regno_coalesced_allocno_num; + +/* Sort pseudos according frequencies of coalesced allocno sets they + belong to (putting most frequently ones first), and according to + coalesced allocno set order numbers. */ +static int +coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p) +{ + const int regno1 = *(const int *) v1p; + const int regno2 = *(const int *) v2p; + int diff; + + if ((diff = (regno_coalesced_allocno_cost[regno2] + - regno_coalesced_allocno_cost[regno1])) != 0) + return diff; + if ((diff = (regno_coalesced_allocno_num[regno1] + - regno_coalesced_allocno_num[regno2])) != 0) + return diff; + return regno1 - regno2; +} + +/* Widest width in which each pseudo reg is referred to (via subreg). + It is used for sorting pseudo registers. */ +static unsigned int *regno_max_ref_width; + +/* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */ +#ifdef STACK_GROWS_DOWNWARD +# undef STACK_GROWS_DOWNWARD +# define STACK_GROWS_DOWNWARD 1 +#else +# define STACK_GROWS_DOWNWARD 0 +#endif + +/* Sort pseudos according their slot numbers (putting ones with + smaller numbers first, or last when the frame pointer is not + needed). */ +static int +coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p) +{ + const int regno1 = *(const int *) v1p; + const int regno2 = *(const int *) v2p; + ira_allocno_t a1 = ira_regno_allocno_map[regno1]; + ira_allocno_t a2 = ira_regno_allocno_map[regno2]; + int diff, slot_num1, slot_num2; + int total_size1, total_size2; + + if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0) + { + if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0) + return regno1 - regno2; + return 1; + } + else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0) + return -1; + slot_num1 = -ALLOCNO_HARD_REGNO (a1); + slot_num2 = -ALLOCNO_HARD_REGNO (a2); + if ((diff = slot_num1 - slot_num2) != 0) + return (frame_pointer_needed + || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff); + total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]); + total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]); + if ((diff = total_size2 - total_size1) != 0) + return diff; + return regno1 - regno2; +} + +/* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM + for coalesced allocno sets containing allocnos with their regnos + given in array PSEUDO_REGNOS of length N. */ +static void +setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n) +{ + int i, num, regno, cost; + ira_allocno_t allocno, a; + + for (num = i = 0; i < n; i++) + { + regno = pseudo_regnos[i]; + allocno = ira_regno_allocno_map[regno]; + if (allocno == NULL) + { + regno_coalesced_allocno_cost[regno] = 0; + regno_coalesced_allocno_num[regno] = ++num; + continue; + } + if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno) + continue; + num++; + for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + cost += ALLOCNO_FREQ (a); + if (a == allocno) + break; + } + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num; + regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost; + if (a == allocno) + break; + } + } +} + +/* Collect spilled allocnos representing coalesced allocno sets (the + first coalesced allocno). The collected allocnos are returned + through array SPILLED_COALESCED_ALLOCNOS. The function returns the + number of the collected allocnos. The allocnos are given by their + regnos in array PSEUDO_REGNOS of length N. */ +static int +collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n, + ira_allocno_t *spilled_coalesced_allocnos) +{ + int i, num, regno; + ira_allocno_t allocno; + + for (num = i = 0; i < n; i++) + { + regno = pseudo_regnos[i]; + allocno = ira_regno_allocno_map[regno]; + if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0 + || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno) + continue; + spilled_coalesced_allocnos[num++] = allocno; + } + 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 allocno_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)) + { + if (ira_allocno_live_ranges_intersect_p + (slot_coalesced_allocnos_live_ranges[n], ALLOCNO_LIVE_RANGES (a))) + 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 n; + ira_allocno_t a; + allocno_live_range_t r; + + n = ALLOCNO_TEMP (allocno); + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a)); + slot_coalesced_allocnos_live_ranges[n] + = ira_merge_allocno_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 + in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if + some allocnos were coalesced in the function. */ +static bool +coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num) +{ + 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 + = (allocno_live_range_t *) ira_allocate (sizeof (allocno_live_range_t) + * ira_allocnos_num); + memset (slot_coalesced_allocnos_live_ranges, 0, + sizeof (allocno_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_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]; + 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) + fprintf (ira_dump_file, + " 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_allocno_live_range_list + (slot_coalesced_allocnos_live_ranges[i]); + ira_free (slot_coalesced_allocnos_live_ranges); + return merged_p; +} + +/* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for + subsequent assigning stack slots to them in the reload pass. To do + this we coalesce spilled allocnos first to decrease the number of + memory-memory move insns. This function is called by the + reload. */ +void +ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, + unsigned int *reg_max_ref_width) +{ + int max_regno = max_reg_num (); + int i, regno, num, slot_num; + ira_allocno_t allocno, a; + 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++) + { + regno = pseudo_regnos[i]; + allocno = ira_regno_allocno_map[regno]; + if (allocno != NULL) + bitmap_set_bit (coloring_allocno_bitmap, + ALLOCNO_NUM (allocno)); + } + allocno_coalesced_p = false; + coalesce_allocnos (true); + ira_free_bitmap (coloring_allocno_bitmap); + regno_coalesced_allocno_cost + = (int *) ira_allocate (max_regno * sizeof (int)); + regno_coalesced_allocno_num + = (int *) ira_allocate (max_regno * sizeof (int)); + memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int)); + setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n); + /* Sort regnos according frequencies of the corresponding coalesced + allocno sets. */ + qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare); + spilled_coalesced_allocnos + = (ira_allocno_t *) ira_allocate (ira_allocnos_num + * sizeof (ira_allocno_t)); + /* Collect allocnos representing the spilled coalesced allocno + sets. */ + num = collect_spilled_coalesced_allocnos (pseudo_regnos, n, + spilled_coalesced_allocnos); + if (flag_ira_share_spill_slots + && coalesce_spill_slots (spilled_coalesced_allocnos, num)) + { + setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n); + qsort (pseudo_regnos, n, sizeof (int), + coalesced_pseudo_reg_freq_compare); + num = collect_spilled_coalesced_allocnos (pseudo_regnos, n, + spilled_coalesced_allocnos); + } + ira_free_bitmap (processed_coalesced_allocno_bitmap); + allocno_coalesced_p = false; + /* Assign stack slot numbers to spilled allocno sets, use smaller + numbers for most frequently used coalesced allocnos. -1 is + reserved for dynamic search of stack slots for pseudos spilled by + the reload. */ + slot_num = 1; + for (i = 0; i < num; i++) + { + allocno = spilled_coalesced_allocnos[i]; + if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno + || ALLOCNO_HARD_REGNO (allocno) >= 0 + || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len + && (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); + slot_num++; + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + ira_assert (ALLOCNO_HARD_REGNO (a) < 0); + ALLOCNO_HARD_REGNO (a) = -slot_num; + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, " a%dr%d(%d,%d)", + 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; + } + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "\n"); + } + ira_spilled_reg_stack_slots_num = slot_num - 1; + ira_free (spilled_coalesced_allocnos); + /* Sort regnos according the slot numbers. */ + regno_max_ref_width = reg_max_ref_width; + qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare); + /* Uncoalesce allocnos which is necessary for (re)assigning during + the reload pass. */ + FOR_EACH_ALLOCNO (a, ai) + { + ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a; + ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a; + } + ira_free (regno_coalesced_allocno_num); + ira_free (regno_coalesced_allocno_cost); +} + + + +/* This page contains code used by the reload pass to improve the + final code. */ + +/* The function is called from reload to mark changes in the + allocation of REGNO made by the reload. Remember that reg_renumber + reflects the change result. */ +void +ira_mark_allocation_change (int regno) +{ + ira_allocno_t a = ira_regno_allocno_map[regno]; + int old_hard_regno, hard_regno, cost; + enum reg_class cover_class = ALLOCNO_COVER_CLASS (a); + + ira_assert (a != NULL); + hard_regno = reg_renumber[regno]; + if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno) + return; + if (old_hard_regno < 0) + cost = -ALLOCNO_MEMORY_COST (a); + else + { + ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0); + cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) + [ira_class_hard_reg_index[cover_class][old_hard_regno]]); + update_copy_costs (a, false); + } + ira_overall_cost -= cost; + ALLOCNO_HARD_REGNO (a) = hard_regno; + if (hard_regno < 0) + { + ALLOCNO_HARD_REGNO (a) = -1; + cost += ALLOCNO_MEMORY_COST (a); + } + else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0) + { + cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) + [ira_class_hard_reg_index[cover_class][hard_regno]]); + update_copy_costs (a, true); + } + else + /* Reload changed class of the allocno. */ + cost = 0; + ira_overall_cost += cost; +} + +/* This function is called when reload deletes memory-memory move. In + this case we marks that the allocation of the corresponding + allocnos should be not changed in future. Otherwise we risk to get + a wrong code. */ +void +ira_mark_memory_move_deletion (int dst_regno, int src_regno) +{ + ira_allocno_t dst = ira_regno_allocno_map[dst_regno]; + ira_allocno_t src = ira_regno_allocno_map[src_regno]; + + ira_assert (dst != NULL && src != NULL + && ALLOCNO_HARD_REGNO (dst) < 0 + && ALLOCNO_HARD_REGNO (src) < 0); + ALLOCNO_DONT_REASSIGN_P (dst) = true; + ALLOCNO_DONT_REASSIGN_P (src) = true; +} + +/* Try to assign a hard register (except for FORBIDDEN_REGS) to + 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); + + 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); + 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); + hard_regno = ALLOCNO_HARD_REGNO (a); + reg_renumber[regno] = hard_regno; + if (hard_regno < 0) + ALLOCNO_HARD_REGNO (a) = -1; + else + { + ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0); + ira_overall_cost -= (ALLOCNO_MEMORY_COST (a) + - (ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) + [ira_class_hard_reg_index + [cover_class][hard_regno]])); + if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0 + && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a), + call_used_reg_set)) + { + ira_assert (flag_caller_saves); + caller_save_needed = 1; + } + } + + /* If we found a hard register, modify the RTL for the pseudo + register to show the hard register, and mark the pseudo register + live. */ + if (reg_renumber[regno] >= 0) + { + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]); + SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]); + mark_home_live (regno); + } + else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, "\n"); + + return reg_renumber[regno] >= 0; +} + +/* Sort pseudos according their usage frequencies (putting most + frequently ones first). */ +static int +pseudo_reg_compare (const void *v1p, const void *v2p) +{ + int regno1 = *(const int *) v1p; + int regno2 = *(const int *) v2p; + int diff; + + if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0) + return diff; + return regno1 - regno2; +} + +/* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are + NUM of them) or spilled pseudos conflicting with pseudos in + SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the + allocation has been changed. The function doesn't use + BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and + PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function + is called by the reload pass at the end of each reload + iteration. */ +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) +{ + int i, m, n, regno; + bool changed_p; + ira_allocno_t a, conflict_a; + HARD_REG_SET forbidden_regs; + ira_allocno_conflict_iterator aci; + + 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++) + { + regno = spilled_pseudo_regs[i]; + 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]); + gcc_assert (reg_renumber[regno] < 0); + a = ira_regno_allocno_map[regno]; + ira_mark_allocation_change (regno); + 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), + ALLOCNO_MEMORY_COST (a) + - ALLOCNO_COVER_CLASS_COST (a)); + allocno_reload_assign (a, forbidden_regs); + if (reg_renumber[regno] >= 0) + { + 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) + { + setup_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); + } + } + } + return changed_p; +} + +/* The function is called by reload and returns already allocated + stack slot (if any) for REGNO with given INHERENT_SIZE and + TOTAL_SIZE. In the case of failure to find a slot which can be + used for REGNO, the function returns NULL. */ +rtx +ira_reuse_stack_slot (int regno, unsigned int inherent_size, + unsigned int total_size) +{ + unsigned int i; + int slot_num, best_slot_num; + int cost, best_cost; + ira_copy_t cp, next_cp; + ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno]; + rtx x; + bitmap_iterator bi; + struct ira_spilled_reg_stack_slot *slot = NULL; + + ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno) + && inherent_size <= total_size + && ALLOCNO_HARD_REGNO (allocno) < 0); + if (! flag_ira_share_spill_slots) + return NULL_RTX; + slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2; + if (slot_num != -1) + { + slot = &ira_spilled_reg_stack_slots[slot_num]; + x = slot->mem; + } + else + { + best_cost = best_slot_num = -1; + x = NULL_RTX; + /* It means that the pseudo was spilled in the reload pass, try + to reuse a slot. */ + for (slot_num = 0; + slot_num < ira_spilled_reg_stack_slots_num; + slot_num++) + { + slot = &ira_spilled_reg_stack_slots[slot_num]; + if (slot->mem == NULL_RTX) + continue; + 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 (allocnos_have_intersected_live_ranges_p (allocno, + another_allocno)) + goto cont; + } + for (cost = 0, cp = ALLOCNO_COPIES (allocno); + cp != NULL; + cp = next_cp) + { + if (cp->first == allocno) + { + next_cp = cp->next_first_allocno_copy; + another_allocno = cp->second; + } + else if (cp->second == allocno) + { + next_cp = cp->next_second_allocno_copy; + another_allocno = cp->first; + } + else + gcc_unreachable (); + if (cp->insn == NULL_RTX) + continue; + if (bitmap_bit_p (&slot->spilled_regs, + ALLOCNO_REGNO (another_allocno))) + cost += cp->freq; + } + if (cost > best_cost) + { + best_cost = cost; + best_slot_num = slot_num; + } + cont: + ; + } + if (best_cost >= 0) + { + slot_num = best_slot_num; + slot = &ira_spilled_reg_stack_slots[slot_num]; + SET_REGNO_REG_SET (&slot->spilled_regs, regno); + x = slot->mem; + ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2; + } + } + 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 (! 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) + { + fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of", + regno, REG_FREQ (regno), slot_num); + EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs, + FIRST_PSEUDO_REGISTER, i, bi) + { + if ((unsigned) regno != i) + fprintf (ira_dump_file, " %d", i); + } + fprintf (ira_dump_file, "\n"); + } + } + return x; +} + +/* This is called by reload every time a new stack slot X with + TOTAL_SIZE was allocated for REGNO. We store this info for + subsequent ira_reuse_stack_slot calls. */ +void +ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size) +{ + struct ira_spilled_reg_stack_slot *slot; + int slot_num; + ira_allocno_t allocno; + + 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) + { + slot_num = ira_spilled_reg_stack_slots_num++; + ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2; + } + slot = &ira_spilled_reg_stack_slots[slot_num]; + INIT_REG_SET (&slot->spilled_regs); + SET_REGNO_REG_SET (&slot->spilled_regs, regno); + slot->mem = x; + slot->width = total_size; + if (internal_flag_ira_verbose > 3 && ira_dump_file) + fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n", + regno, REG_FREQ (regno), slot_num); +} + + +/* Return spill cost for pseudo-registers whose numbers are in array + REGNOS (with a negative number as an end marker) for reload with + given IN and OUT for INSN. Return also number points (through + EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and + the register pressure is high, number of references of the + pseudo-registers (through NREFS), number of callee-clobbered + hard-registers occupied by the pseudo-registers (through + CALL_USED_COUNT), and the first hard regno occupied by the + pseudo-registers (through FIRST_HARD_REGNO). */ +static int +calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn, + int *excess_pressure_live_length, + int *nrefs, int *call_used_count, int *first_hard_regno) +{ + int i, cost, regno, hard_regno, j, count, saved_cost, nregs; + bool in_p, out_p; + int length; + ira_allocno_t a; + + *nrefs = 0; + for (length = count = cost = i = 0;; i++) + { + regno = regnos[i]; + if (regno < 0) + break; + *nrefs += REG_N_REFS (regno); + hard_regno = reg_renumber[regno]; + ira_assert (hard_regno >= 0); + a = ira_regno_allocno_map[regno]; + length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (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++) + if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j)) + break; + if (j == nregs) + count++; + in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno; + out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno; + if ((in_p || out_p) + && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX) + { + saved_cost = 0; + if (in_p) + saved_cost += ira_memory_move_cost + [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1]; + if (out_p) + saved_cost + += ira_memory_move_cost + [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0]; + cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost; + } + } + *excess_pressure_live_length = length; + *call_used_count = count; + hard_regno = -1; + if (regnos[0] >= 0) + { + hard_regno = reg_renumber[regnos[0]]; + } + *first_hard_regno = hard_regno; + return cost; +} + +/* Return TRUE if spilling pseudo-registers whose numbers are in array + REGNOS is better than spilling pseudo-registers with numbers in + OTHER_REGNOS for reload with given IN and OUT for INSN. The + function used by the reload pass to make better register spilling + decisions. */ +bool +ira_better_spill_reload_regno_p (int *regnos, int *other_regnos, + rtx in, rtx out, rtx insn) +{ + int cost, other_cost; + int length, other_length; + int nrefs, other_nrefs; + int call_used_count, other_call_used_count; + int hard_regno, other_hard_regno; + + 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, + &other_call_used_count, + &other_hard_regno); + if (nrefs == 0 && other_nrefs != 0) + return true; + if (nrefs != 0 && other_nrefs == 0) + return false; + if (cost != other_cost) + return cost < other_cost; + if (length != other_length) + return length > other_length; +#ifdef REG_ALLOC_ORDER + if (hard_regno >= 0 && other_hard_regno >= 0) + return (inv_reg_alloc_order[hard_regno] + < inv_reg_alloc_order[other_hard_regno]); +#else + if (call_used_count != other_call_used_count) + return call_used_count > other_call_used_count; +#endif + return false; +} + + + +/* Allocate and initialize data necessary for assign_hard_reg. */ +void +ira_initiate_assign (void) +{ + sorted_allocnos + = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) + * ira_allocnos_num); + consideration_allocno_bitmap = ira_allocate_bitmap (); + initiate_cost_update (); + allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num); +} + +/* Deallocate data used by assign_hard_reg. */ +void +ira_finish_assign (void) +{ + ira_free (sorted_allocnos); + ira_free_bitmap (consideration_allocno_bitmap); + finish_cost_update (); + ira_free (allocno_priorities); +} + + + +/* Entry function doing color-based register allocation. */ +static void +color (void) +{ + allocno_stack_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)); + ira_initiate_assign (); + do_coloring (); + ira_finish_assign (); + VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec); + VEC_free (ira_allocno_t, heap, allocno_stack_vec); + move_spill_restore (); +} + + + +/* This page contains a simple register allocator without usage of + allocno conflicts. This is used for fast allocation for -O0. */ + +/* Do register allocation by not using allocno conflicts. It uses + only allocno live ranges. The algorithm is close to Chow's + priority coloring. */ +static void +fast_allocation (void) +{ + int i, j, k, num, class_size, hard_regno; +#ifdef STACK_REGS + bool no_stack_reg_p; +#endif + enum reg_class cover_class; + enum machine_mode mode; + ira_allocno_t a; + ira_allocno_iterator ai; + allocno_live_range_t r; + HARD_REG_SET conflict_hard_regs, *used_hard_regs; + + 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; + 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++) + { + 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]); + cover_class = ALLOCNO_COVER_CLASS (a); + ALLOCNO_ASSIGNED_P (a) = true; + ALLOCNO_HARD_REGNO (a) = -1; + if (hard_reg_set_subset_p (reg_class_contents[cover_class], + conflict_hard_regs)) + continue; + mode = ALLOCNO_MODE (a); +#ifdef STACK_REGS + no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a); +#endif + class_size = ira_class_hard_regs_num[cover_class]; + for (j = 0; j < class_size; j++) + { + hard_regno = ira_class_hard_regs[cover_class][j]; +#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, conflict_hard_regs) + || (TEST_HARD_REG_BIT + (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]); + break; + } + } + ira_free (sorted_allocnos); + ira_free (used_hard_regs); + ira_free (allocno_priorities); + 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 (); +}