--- /dev/null
+/* IRA allocation based on graph coloring.
+ Copyright (C) 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
+ Contributed by Vladimir Makarov <vmakarov@redhat.com>.
+
+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
+<http://www.gnu.org/licenses/>. */
+
+#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;
+
+\f
+
+/* 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
+
+\f
+
+/* 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;
+}
+
+\f
+
+/* 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;
+}
+
+\f
+
+/* 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);
+}
+
+\f
+
+/* 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;
+ }
+}
+
+\f
+
+/* 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));
+ }
+ }
+}
+
+\f
+
+/* 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);
+}
+
+\f
+
+/* 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;
+}
+
+\f
+
+/* 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);
+}
+
+\f
+
+/* 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 ();
+}
+
+\f
+
+/* 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);
+}
+
+\f
+
+/* 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 ();
+}
projects / msp430-gcc.git / blobdiff