/* IRA allocation based on graph coloring.
- Copyright (C) 2006, 2007, 2008
+ Copyright (C) 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
#include "hard-reg-set.h"
#include "basic-block.h"
#include "expr.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "reload.h"
#include "params.h"
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;
more costly although simpler. */
static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec;
+/* Helper for qsort comparison callbacks - return a positive integer if
+ X > Y, or a negative value otherwise. Use a conditional expression
+ instead of a difference computation to insulate from possible overflow
+ issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
+#define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
+
+\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)
+{
+ int i, j;
+ int n1 = ALLOCNO_NUM_OBJECTS (a1);
+ int n2 = ALLOCNO_NUM_OBJECTS (a2);
+
+ if (a1 == a2)
+ return false;
+ if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
+ && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
+ == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
+ return false;
+
+ for (i = 0; i < n1; i++)
+ {
+ ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
+ for (j = 0; j < n2; j++)
+ {
+ ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
+ if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
+ OBJECT_LIVE_RANGES (c2)))
+ return true;
+ }
+ }
+ return false;
+}
+
+#ifdef ENABLE_IRA_CHECKING
+
+/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
+ intersect. This should be used when there is only one region.
+ Currently this is used during reload. */
+static bool
+pseudos_have_intersected_live_ranges_p (int regno1, int regno2)
+{
+ ira_allocno_t a1, a2;
+
+ ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
+ && regno2 >= FIRST_PSEUDO_REGISTER);
+ /* Reg info caclulated by dataflow infrastructure can be different
+ from one calculated by regclass. */
+ if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
+ || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
+ return false;
+ return allocnos_have_intersected_live_ranges_p (a1, a2);
+}
+
+#endif
+
\f
/* This page contains functions used to choose hard registers for
else
gcc_unreachable ();
- if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
+ 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_register_move_cost[mode][rclass][cover_class]
- : ira_register_move_cost[mode][cover_class][rclass]);
+ ? ira_get_register_move_cost (mode, rclass, cover_class)
+ : ira_get_register_move_cost (mode, cover_class, rclass));
if (decr_p)
cost = -cost;
(&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;
while (get_next_update_cost (&allocno, &divisor));
}
-/* This function updates COSTS (decrease if DECR_P) by conflict costs
- of the unassigned allocnos connected by copies with allocnos in
- update_cost_queue. This update increases chances to remove some
- copies. */
+/* 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, bool decr_p)
+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 cover_class;
+ enum reg_class another_cover_class;
ira_allocno_t allocno, another_allocno;
ira_copy_t cp, next_cp;
}
else
gcc_unreachable ();
- cover_class = ALLOCNO_COVER_CLASS (allocno);
- if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
+ another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
+ if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
|| ALLOCNO_ASSIGNED_P (another_allocno)
|| ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
continue;
- class_size = ira_class_hard_regs_num[cover_class];
+ class_size = ira_class_hard_regs_num[another_cover_class];
ira_allocate_and_copy_costs
(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
- cover_class, ALLOCNO_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 = 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[i] += cost;
+ costs[index] += cost;
}
}
/* Probably 5 hops will be enough. */
}
}
-/* Sort allocnos according to the profit of usage of a hard register
- instead of memory for them. */
-static int
-allocno_cost_compare_func (const void *v1p, const void *v2p)
-{
- ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
- ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
- int c1, c2;
-
- c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
- c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
- if (c1 - c2)
- return c1 - c2;
-
- /* If regs are equally good, sort by allocno numbers, so that the
- results of qsort leave nothing to chance. */
- return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
-}
-
-/* Print all allocnos coalesced with ALLOCNO. */
-static void
-print_coalesced_allocno (ira_allocno_t allocno)
-{
- ira_allocno_t a;
-
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- ira_print_expanded_allocno (a);
- if (a == allocno)
- break;
- fprintf (ira_dump_file, "+");
- }
-}
-
-/* Choose a hard register for ALLOCNO (or for all coalesced allocnos
- represented by ALLOCNO). If RETRY_P is TRUE, it means that the
- function called from function `ira_reassign_conflict_allocnos' and
- `allocno_reload_assign'. This function implements the optimistic
- coalescing too: if we failed to assign a hard register to set of
- the coalesced allocnos, we put them onto the coloring stack for
- subsequent separate assigning. */
+/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
+ that the function called from function
+ `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. */
static bool
-assign_hard_reg (ira_allocno_t allocno, bool retry_p)
+assign_hard_reg (ira_allocno_t a, bool retry_p)
{
- HARD_REG_SET conflicting_regs;
- int i, j, hard_regno, best_hard_regno, class_size;
- int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
+ HARD_REG_SET conflicting_regs[2];
+ int i, j, hard_regno, nregs, best_hard_regno, class_size;
+ int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
int *a_costs;
- int *conflict_costs;
- enum reg_class cover_class, rclass;
+ enum reg_class cover_class;
enum machine_mode mode;
- ira_allocno_t a, conflict_allocno;
- ira_allocno_conflict_iterator aci;
static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
+#ifndef HONOR_REG_ALLOC_ORDER
+ enum reg_class rclass;
+ int add_cost;
+#endif
#ifdef STACK_REGS
bool no_stack_reg_p;
#endif
- ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
- cover_class = ALLOCNO_COVER_CLASS (allocno);
+ nwords = ALLOCNO_NUM_OBJECTS (a);
+ ira_assert (! ALLOCNO_ASSIGNED_P (a));
+ cover_class = ALLOCNO_COVER_CLASS (a);
class_size = ira_class_hard_regs_num[cover_class];
- mode = ALLOCNO_MODE (allocno);
- CLEAR_HARD_REG_SET (conflicting_regs);
+ mode = ALLOCNO_MODE (a);
+ for (i = 0; i < nwords; i++)
+ CLEAR_HARD_REG_SET (conflicting_regs[i]);
best_hard_regno = -1;
memset (full_costs, 0, sizeof (int) * class_size);
mem_cost = 0;
- if (allocno_coalesced_p)
- bitmap_clear (processed_coalesced_allocno_bitmap);
memset (costs, 0, sizeof (int) * class_size);
memset (full_costs, 0, sizeof (int) * class_size);
#ifdef STACK_REGS
no_stack_reg_p = false;
#endif
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);
+ mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
+
+ ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
+ cover_class, ALLOCNO_HARD_REG_COSTS (a));
+ a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
#ifdef STACK_REGS
- no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
+ no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
#endif
- for (cost = ALLOCNO_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;
- }
+ cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a);
+ for (i = 0; i < class_size; i++)
+ if (a_costs != NULL)
+ {
+ costs[i] += a_costs[i];
+ full_costs[i] += a_costs[i];
+ }
+ else
+ {
+ costs[i] += cost;
+ full_costs[i] += cost;
+ }
+ for (word = 0; word < nwords; word++)
+ {
+ ira_object_t conflict_obj;
+ ira_object_t obj = ALLOCNO_OBJECT (a, word);
+ ira_object_conflict_iterator oci;
+
+ IOR_HARD_REG_SET (conflicting_regs[word],
+ OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
/* Take preferences of conflicting allocnos into account. */
- FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
- /* Reload can give another class so we need to check all
- allocnos. */
- if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- {
- ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
- if (allocno_coalesced_p)
- {
- if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno));
- }
- if (ALLOCNO_ASSIGNED_P (conflict_allocno))
- {
- if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0)
- {
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+ enum reg_class conflict_cover_class;
+
+ /* Reload can give another class so we need to check all
+ allocnos. */
+ if (!retry_p && !bitmap_bit_p (consideration_allocno_bitmap,
+ ALLOCNO_NUM (conflict_a)))
+ continue;
+ conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_a);
+ ira_assert (ira_reg_classes_intersect_p
+ [cover_class][conflict_cover_class]);
+ if (ALLOCNO_ASSIGNED_P (conflict_a))
+ {
+ hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
+ if (hard_regno >= 0
+ && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
+ {
+ enum machine_mode mode = ALLOCNO_MODE (conflict_a);
+ int conflict_nregs = hard_regno_nregs[hard_regno][mode];
+ int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
+
+ if (conflict_nregs == n_objects && conflict_nregs > 1)
+ {
+ int num = OBJECT_SUBWORD (conflict_obj);
+
+ if (WORDS_BIG_ENDIAN)
+ SET_HARD_REG_BIT (conflicting_regs[word],
+ hard_regno + n_objects - num - 1);
+ else
+ SET_HARD_REG_BIT (conflicting_regs[word],
+ hard_regno + num);
+ }
+ else
IOR_HARD_REG_SET
- (conflicting_regs,
- ira_reg_mode_hard_regset
- [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
- if (hard_reg_set_subset_p (reg_class_contents[cover_class],
- conflicting_regs))
- goto fail;
+ (conflicting_regs[word],
+ ira_reg_mode_hard_regset[hard_regno][mode]);
+ if (hard_reg_set_subset_p (reg_class_contents[cover_class],
+ conflicting_regs[word]))
+ goto fail;
+ }
+ }
+ else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_a))
+ {
+ int k, *conflict_costs;
+
+ ira_allocate_and_copy_costs
+ (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
+ conflict_cover_class,
+ ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
+ conflict_costs
+ = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
+ if (conflict_costs != NULL)
+ for (j = class_size - 1; j >= 0; j--)
+ {
+ hard_regno = ira_class_hard_regs[cover_class][j];
+ ira_assert (hard_regno >= 0);
+ k = (ira_class_hard_reg_index
+ [conflict_cover_class][hard_regno]);
+ if (k < 0)
+ continue;
+ full_costs[j] -= conflict_costs[k];
}
- continue;
- }
- else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno))
- {
- ira_allocate_and_copy_costs
- (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
- cover_class,
- ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
- conflict_costs
- = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
- if (conflict_costs != NULL)
- for (j = class_size - 1; j >= 0; j--)
- full_costs[j] -= conflict_costs[j];
- queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
- }
- }
- if (a == allocno)
- break;
+ queue_update_cost (conflict_a, COST_HOP_DIVISOR);
+ }
+ }
}
/* Take into account preferences of allocnos connected by copies to
the conflict allocnos. */
- update_conflict_hard_regno_costs (full_costs, true);
+ 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, false);
+ queue_update_cost (a, COST_HOP_DIVISOR);
+ update_conflict_hard_regno_costs (full_costs, cover_class, false);
min_cost = min_full_cost = INT_MAX;
+
/* We don't care about giving callee saved registers to allocnos no
living through calls because call clobbered registers are
allocated first (it is usual practice to put them first in
for (i = 0; i < class_size; i++)
{
hard_regno = ira_class_hard_regs[cover_class][i];
+ nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
#ifdef STACK_REGS
if (no_stack_reg_p
&& FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
continue;
#endif
- if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
- || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
- hard_regno))
+ if (TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
+ hard_regno))
+ continue;
+ for (j = 0; j < nregs; j++)
+ {
+ int k;
+ int set_to_test_start = 0, set_to_test_end = nwords;
+ if (nregs == nwords)
+ {
+ if (WORDS_BIG_ENDIAN)
+ set_to_test_start = nwords - j - 1;
+ else
+ set_to_test_start = j;
+ set_to_test_end = set_to_test_start + 1;
+ }
+ for (k = set_to_test_start; k < set_to_test_end; k++)
+ if (TEST_HARD_REG_BIT (conflicting_regs[k], hard_regno + j))
+ break;
+ if (k != set_to_test_end)
+ break;
+ }
+ if (j != nregs)
continue;
cost = costs[i];
full_cost = full_costs[i];
+#ifndef HONOR_REG_ALLOC_ORDER
if (! allocated_hardreg_p[hard_regno]
&& ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
/* We need to save/restore the hard register in
cost += add_cost;
full_cost += add_cost;
}
+#endif
if (min_cost > cost)
min_cost = cost;
if (min_full_cost > full_cost)
best_hard_regno = -1;
}
fail:
- if (best_hard_regno < 0
- && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
- {
- for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- sorted_allocnos[j++] = a;
- if (a == allocno)
- break;
- }
- qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
- allocno_cost_compare_func);
- for (i = 0; i < j; i++)
- {
- a = sorted_allocnos[i];
- ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
- ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
- VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
- if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
- {
- fprintf (ira_dump_file, " Pushing");
- print_coalesced_allocno (a);
- fprintf (ira_dump_file, "\n");
- }
- }
- return false;
- }
if (best_hard_regno >= 0)
allocated_hardreg_p[best_hard_regno] = true;
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- ALLOCNO_HARD_REGNO (a) = best_hard_regno;
- ALLOCNO_ASSIGNED_P (a) = true;
- if (best_hard_regno >= 0)
- update_copy_costs (a, true);
- ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
- /* We don't need updated costs anymore: */
- ira_free_allocno_updated_costs (a);
- if (a == allocno)
- break;
- }
+ ALLOCNO_HARD_REGNO (a) = best_hard_regno;
+ ALLOCNO_ASSIGNED_P (a) = true;
+ if (best_hard_regno >= 0)
+ update_copy_costs (a, true);
+ /* We don't need updated costs anymore: */
+ ira_free_allocno_updated_costs (a);
return best_hard_regno >= 0;
}
of given *cover* class in the uncolorable_bucket. */
static int uncolorable_allocnos_num[N_REG_CLASSES];
+/* Return the current spill priority of allocno A. The less the
+ number, the more preferable the allocno for spilling. */
+static int
+allocno_spill_priority (ira_allocno_t a)
+{
+ return (ALLOCNO_TEMP (a)
+ / (ALLOCNO_LEFT_CONFLICTS_SIZE (a)
+ * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]
+ + 1));
+}
+
/* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
before the call. */
static void
-add_ira_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
+add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
{
ira_allocno_t first_allocno;
enum reg_class cover_class;
*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
if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
return diff;
- get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
- get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
+ a1_freq = ALLOCNO_FREQ (a1);
+ a1_num = ALLOCNO_AVAILABLE_REGS_NUM (a1);
+ a2_freq = ALLOCNO_FREQ (a2);
+ a2_num = ALLOCNO_AVAILABLE_REGS_NUM (a2);
if ((diff = a2_num - a1_num) != 0)
return diff;
else if ((diff = a1_freq - a2_freq) != 0)
their priority. ALLOCNO should be not in a bucket before the
call. */
static void
-add_ira_allocno_to_ordered_bucket (ira_allocno_t allocno,
- ira_allocno_t *bucket_ptr)
+add_allocno_to_ordered_bucket (ira_allocno_t allocno,
+ ira_allocno_t *bucket_ptr)
{
ira_allocno_t before, after;
enum reg_class cover_class;
into account. */
#define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
-/* Put ALLOCNO onto the coloring stack without removing it from its
+/* Put allocno A onto the coloring stack without removing it from its
bucket. Pushing allocno to the coloring stack can result in moving
conflicting allocnos from the uncolorable bucket to the colorable
one. */
static void
-push_ira_allocno_to_stack (ira_allocno_t allocno)
+push_allocno_to_stack (ira_allocno_t a)
{
- int conflicts_num, conflict_size, size;
- ira_allocno_t a, conflict_allocno;
+ int size;
enum reg_class cover_class;
- ira_allocno_conflict_iterator aci;
-
- ALLOCNO_IN_GRAPH_P (allocno) = false;
- VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
- cover_class = ALLOCNO_COVER_CLASS (allocno);
+ int i, n = ALLOCNO_NUM_OBJECTS (a);
+
+ ALLOCNO_IN_GRAPH_P (a) = false;
+ VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
+ cover_class = ALLOCNO_COVER_CLASS (a);
if (cover_class == NO_REGS)
return;
- size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
- if (allocno_coalesced_p)
- bitmap_clear (processed_coalesced_allocno_bitmap);
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (a)];
+ if (ALLOCNO_NUM_OBJECTS (a) > 1)
{
- FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
- if (bitmap_bit_p (coloring_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- {
- ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
- if (allocno_coalesced_p)
- {
- if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno));
- }
- if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
- && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
- {
- conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
- conflict_size
- = (ira_reg_class_nregs
- [cover_class][ALLOCNO_MODE (conflict_allocno)]);
- ira_assert
- (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
- if (conflicts_num + conflict_size
- <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
- {
- ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
- continue;
- }
- conflicts_num
- = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
- if (uncolorable_allocnos_splay_tree[cover_class] != NULL
- && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
- && USE_SPLAY_P (cover_class))
- {
- ira_assert
- (splay_tree_lookup
- (uncolorable_allocnos_splay_tree[cover_class],
- (splay_tree_key) conflict_allocno) != NULL);
- splay_tree_remove
- (uncolorable_allocnos_splay_tree[cover_class],
- (splay_tree_key) conflict_allocno);
- ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
- VEC_safe_push (ira_allocno_t, heap,
- removed_splay_allocno_vec,
- conflict_allocno);
- }
- ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
- if (conflicts_num + conflict_size
- <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
- {
- delete_allocno_from_bucket (conflict_allocno,
- &uncolorable_allocno_bucket);
- add_ira_allocno_to_ordered_bucket (conflict_allocno,
- &colorable_allocno_bucket);
- }
- }
- }
- if (a == allocno)
- break;
+ /* We will deal with the subwords individually. */
+ gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
+ size = 1;
+ }
+ for (i = 0; i < n; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ int conflict_size;
+ ira_object_t conflict_obj;
+ ira_object_conflict_iterator oci;
+
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+ int left_conflicts_size;
+
+ conflict_a = conflict_a;
+ if (!bitmap_bit_p (coloring_allocno_bitmap,
+ ALLOCNO_NUM (conflict_a)))
+ continue;
+
+ ira_assert (cover_class
+ == ALLOCNO_COVER_CLASS (conflict_a));
+ if (!ALLOCNO_IN_GRAPH_P (conflict_a)
+ || ALLOCNO_ASSIGNED_P (conflict_a))
+ continue;
+
+ left_conflicts_size = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_a);
+ conflict_size
+ = (ira_reg_class_nregs
+ [cover_class][ALLOCNO_MODE (conflict_a)]);
+ ira_assert (left_conflicts_size >= size);
+ if (left_conflicts_size + conflict_size
+ <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_a))
+ {
+ ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_a) -= size;
+ continue;
+ }
+ left_conflicts_size -= size;
+ if (uncolorable_allocnos_splay_tree[cover_class] != NULL
+ && !ALLOCNO_SPLAY_REMOVED_P (conflict_a)
+ && USE_SPLAY_P (cover_class))
+ {
+ ira_assert
+ (splay_tree_lookup
+ (uncolorable_allocnos_splay_tree[cover_class],
+ (splay_tree_key) conflict_a) != NULL);
+ splay_tree_remove
+ (uncolorable_allocnos_splay_tree[cover_class],
+ (splay_tree_key) conflict_a);
+ ALLOCNO_SPLAY_REMOVED_P (conflict_a) = true;
+ VEC_safe_push (ira_allocno_t, heap,
+ removed_splay_allocno_vec,
+ conflict_a);
+ }
+ ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_a)
+ = left_conflicts_size;
+ if (left_conflicts_size + conflict_size
+ <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_a))
+ {
+ delete_allocno_from_bucket
+ (conflict_a, &uncolorable_allocno_bucket);
+ add_allocno_to_ordered_bucket
+ (conflict_a, &colorable_allocno_bucket);
+ }
+ }
}
}
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Pushing");
- print_coalesced_allocno (allocno);
- fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)");
+ ira_print_expanded_allocno (allocno);
+ if (colorable_p)
+ fprintf (ira_dump_file, "\n");
+ else
+ fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
+ ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
+ allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno));
}
cover_class = ALLOCNO_COVER_CLASS (allocno);
ira_assert ((colorable_p
- && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
+ && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
+ ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
<= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
|| (! colorable_p
- && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
+ && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
+ ira_reg_class_nregs[cover_class][ALLOCNO_MODE
(allocno)]
> ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
if (! colorable_p)
ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
- push_ira_allocno_to_stack (allocno);
+ push_allocno_to_stack (allocno);
}
/* Put all allocnos from colorable bucket onto the coloring stack. */
/* Puts ALLOCNO chosen for potential spilling onto the coloring
stack. */
static void
-push_ira_allocno_to_spill (ira_allocno_t allocno)
+push_allocno_to_spill (ira_allocno_t allocno)
{
delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
- fprintf (ira_dump_file, " Pushing p%d(%d) (potential spill)\n",
+ fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n",
ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
- push_ira_allocno_to_stack (allocno);
+ push_allocno_to_stack (allocno);
}
/* Return the frequency of exit edges (if EXIT_P) or entry from/to the
- loop given by its LOOP_NODE. */
+ loop given by its LOOP_NODE. */
int
ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
{
else
{
edges = get_loop_exit_edges (loop_node->loop);
- for (i = 0; VEC_iterate (edge, edges, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, edges, i, e)
if (regno < 0
|| (bitmap_bit_p (DF_LR_OUT (e->src), regno)
&& bitmap_bit_p (DF_LR_IN (e->dest), regno)))
* ira_loop_edge_freq (loop_node, regno, true)
+ ira_memory_move_cost[mode][rclass][0]
* ira_loop_edge_freq (loop_node, regno, false))
- - (ira_register_move_cost[mode][rclass][rclass]
+ - (ira_get_register_move_cost (mode, rclass, rclass)
* (ira_loop_edge_freq (loop_node, regno, false)
+ ira_loop_edge_freq (loop_node, regno, true))));
return cost;
{
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)
+ / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1)
* ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
+ 1));
pri2 = (ALLOCNO_TEMP (a2)
- / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
+ / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2)
* ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
+ 1));
if ((diff = pri1 - pri2) != 0)
static void
push_allocnos_to_stack (void)
{
- ira_allocno_t allocno, a, i_allocno, *allocno_vec;
+ ira_allocno_t allocno, i_allocno, *allocno_vec;
enum reg_class cover_class, rclass;
int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
{
cover_class_allocnos_num[cover_class]++;
- cost = 0;
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- cost += calculate_allocno_spill_cost (a);
- if (a == allocno)
- break;
- }
- /* ??? Remove cost of copies between the coalesced
- allocnos. */
+ cost = calculate_allocno_spill_cost (allocno);
ALLOCNO_TEMP (allocno) = cost;
}
/* Define place where to put uncolorable allocnos of the same cover
cover_class = ALLOCNO_COVER_CLASS (allocno);
if (cover_class == NO_REGS)
{
- push_ira_allocno_to_spill (allocno);
+ push_allocno_to_spill (allocno);
continue;
}
/* Potential spilling. */
allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
rclass = ALLOCNO_COVER_CLASS (allocno);
- if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
+ if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
+ ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
> ALLOCNO_AVAILABLE_REGS_NUM (allocno))
splay_tree_insert
if (ALLOCNO_IN_GRAPH_P (i_allocno))
{
i++;
- if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
- {
- ira_allocno_t a;
- int cost = 0;
-
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- cost += calculate_allocno_spill_cost (i_allocno);
- if (a == i_allocno)
- break;
- }
- /* ??? Remove cost of copies between the coalesced
- allocnos. */
- ALLOCNO_TEMP (i_allocno) = cost;
- }
+ ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX);
i_allocno_cost = ALLOCNO_TEMP (i_allocno);
- i_allocno_pri
- = (i_allocno_cost
- / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
- * ira_reg_class_nregs[ALLOCNO_COVER_CLASS
- (i_allocno)]
- [ALLOCNO_MODE (i_allocno)] + 1));
- if (allocno == NULL || allocno_pri > i_allocno_pri
- || (allocno_pri == i_allocno_pri
- && (allocno_cost > i_allocno_cost
- || (allocno_cost == i_allocno_cost
- && (ALLOCNO_NUM (allocno)
- > ALLOCNO_NUM (i_allocno))))))
+ 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;
}
ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
&& ALLOCNO_COVER_CLASS (allocno) == cover_class
- && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
+ && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
+ ira_reg_class_nregs[cover_class][ALLOCNO_MODE
(allocno)]
> ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Popping");
- print_coalesced_allocno (allocno);
+ ira_print_expanded_allocno (allocno);
fprintf (ira_dump_file, " -- ");
}
if (cover_class == NO_REGS)
}
}
-/* Set up number of available hard registers for ALLOCNO. */
+/* Loop over all subobjects of allocno A, collecting total hard
+ register conflicts in PSET (which the caller must initialize). */
+static void
+all_conflicting_hard_regs (ira_allocno_t a, HARD_REG_SET *pset)
+{
+ int i;
+ int n = ALLOCNO_NUM_OBJECTS (a);
+
+ for (i = 0; i < n; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+
+ IOR_HARD_REG_SET (*pset, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
+ }
+}
+
+/* Set up number of available hard registers for allocno A. */
static void
-setup_allocno_available_regs_num (ira_allocno_t allocno)
+setup_allocno_available_regs_num (ira_allocno_t a)
{
- int i, n, hard_regs_num;
+ int i, n, hard_regs_num, hard_regno;
+ enum machine_mode mode;
enum reg_class cover_class;
- ira_allocno_t a;
HARD_REG_SET temp_set;
- cover_class = ALLOCNO_COVER_CLASS (allocno);
- ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
+ cover_class = ALLOCNO_COVER_CLASS (a);
+ ALLOCNO_AVAILABLE_REGS_NUM (a) = ira_available_class_regs[cover_class];
if (cover_class == NO_REGS)
return;
CLEAR_HARD_REG_SET (temp_set);
- ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
+ ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
hard_regs_num = ira_class_hard_regs_num[cover_class];
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ all_conflicting_hard_regs (a, &temp_set);
+
+ mode = ALLOCNO_MODE (a);
+ for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
{
- IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
- if (a == allocno)
- break;
+ hard_regno = ira_class_hard_regs[cover_class][i];
+ if (TEST_HARD_REG_BIT (temp_set, hard_regno)
+ || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
+ hard_regno))
+ n++;
}
- for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
- if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
- n++;
if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
- ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
- ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
+ ALLOCNO_REGNO (a), reg_class_names[cover_class], n);
+ ALLOCNO_AVAILABLE_REGS_NUM (a) -= n;
}
-/* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
+/* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for allocno A. */
static void
-setup_allocno_left_conflicts_num (ira_allocno_t allocno)
+setup_allocno_left_conflicts_size (ira_allocno_t a)
{
int i, hard_regs_num, hard_regno, conflict_allocnos_size;
- ira_allocno_t a, conflict_allocno;
enum reg_class cover_class;
HARD_REG_SET temp_set;
- ira_allocno_conflict_iterator aci;
- cover_class = ALLOCNO_COVER_CLASS (allocno);
+ cover_class = ALLOCNO_COVER_CLASS (a);
hard_regs_num = ira_class_hard_regs_num[cover_class];
CLEAR_HARD_REG_SET (temp_set);
- ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
- if (a == allocno)
- break;
- }
+ ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
+ all_conflicting_hard_regs (a, &temp_set);
+
AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
+
conflict_allocnos_size = 0;
if (! hard_reg_set_empty_p (temp_set))
for (i = 0; i < (int) hard_regs_num; i++)
}
}
CLEAR_HARD_REG_SET (temp_set);
- if (allocno_coalesced_p)
- bitmap_clear (processed_coalesced_allocno_bitmap);
if (cover_class != NO_REGS)
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
- if (bitmap_bit_p (consideration_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
+ {
+ int n = ALLOCNO_NUM_OBJECTS (a);
+
+ for (i = 0; i < n; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ ira_object_t conflict_obj;
+ ira_object_conflict_iterator oci;
+
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
{
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+
ira_assert (cover_class
- == ALLOCNO_COVER_CLASS (conflict_allocno));
- if (allocno_coalesced_p)
- {
- if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno)))
- continue;
- bitmap_set_bit (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno));
- }
- if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
+ == ALLOCNO_COVER_CLASS (conflict_a));
+ if (! ALLOCNO_ASSIGNED_P (conflict_a))
conflict_allocnos_size
+= (ira_reg_class_nregs
- [cover_class][ALLOCNO_MODE (conflict_allocno)]);
- else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
+ [cover_class][ALLOCNO_MODE (conflict_a)]);
+ else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_a))
>= 0)
{
int last = (hard_regno
+ hard_regno_nregs
- [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
+ [hard_regno][ALLOCNO_MODE (conflict_a)]);
while (hard_regno < last)
{
}
}
}
- if (a == allocno)
- break;
- }
- ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
+ }
+ }
+ ALLOCNO_LEFT_CONFLICTS_SIZE (a) = conflict_allocnos_size;
}
/* Put ALLOCNO in a bucket corresponding to its number and size of its
static void
put_allocno_into_bucket (ira_allocno_t allocno)
{
- int hard_regs_num;
enum reg_class cover_class;
cover_class = ALLOCNO_COVER_CLASS (allocno);
- hard_regs_num = ira_class_hard_regs_num[cover_class];
- if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
- return;
ALLOCNO_IN_GRAPH_P (allocno) = true;
- setup_allocno_left_conflicts_num (allocno);
+ setup_allocno_left_conflicts_size (allocno);
setup_allocno_available_regs_num (allocno);
- if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
+ if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
+ ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
<= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
- add_ira_allocno_to_bucket (allocno, &colorable_allocno_bucket);
+ add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
else
- add_ira_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
+ add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
}
-/* The function is used to sort allocnos according to their execution
- frequencies. */
-static int
-copy_freq_compare_func (const void *v1p, const void *v2p)
-{
- ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
- int pri1, pri2;
-
- pri1 = cp1->freq;
- pri2 = cp2->freq;
- if (pri2 - pri1)
- return pri2 - pri1;
-
- /* If freqencies are equal, sort by copies, so that the results of
- qsort leave nothing to chance. */
- return cp1->num - cp2->num;
-}
+/* Map: allocno number -> allocno priority. */
+static int *allocno_priorities;
-/* Merge two sets of coalesced allocnos given correspondingly by
- allocnos A1 and A2 (more accurately merging A2 set into A1
- set). */
+/* Set up priorities for N allocnos in array
+ CONSIDERATION_ALLOCNOS. */
static void
-merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
+setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
{
- ira_allocno_t a, first, last, next;
+ int i, length, nrefs, priority, max_priority, mult;
+ ira_allocno_t a;
- first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
- if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
- return;
- for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ max_priority = 0;
+ for (i = 0; i < n; i++)
{
- ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
- if (a == a2)
- break;
- last = a;
+ a = consideration_allocnos[i];
+ nrefs = ALLOCNO_NREFS (a);
+ ira_assert (nrefs >= 0);
+ mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
+ ira_assert (mult >= 0);
+ allocno_priorities[ALLOCNO_NUM (a)]
+ = priority
+ = (mult
+ * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
+ * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
+ if (priority < 0)
+ priority = -priority;
+ if (max_priority < priority)
+ max_priority = priority;
+ }
+ mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
+ for (i = 0; i < n; i++)
+ {
+ a = consideration_allocnos[i];
+ length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+ if (ALLOCNO_NUM_OBJECTS (a) > 1)
+ length /= ALLOCNO_NUM_OBJECTS (a);
+ if (length <= 0)
+ length = 1;
+ allocno_priorities[ALLOCNO_NUM (a)]
+ = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
}
- next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
- ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
- ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
}
-/* Return TRUE if there are conflicting allocnos from two sets of
- coalesced allocnos given correspondingly by allocnos A1 and A2. If
- RELOAD_P is TRUE, we use live ranges to find conflicts because
- conflicts are represented only for allocnos of the same cover class
- and during the reload pass we coalesce allocnos for sharing stack
- memory slots. */
-static bool
-coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
- bool reload_p)
+/* Sort allocnos according to their priorities which are calculated
+ analogous to ones in file `global.c'. */
+static int
+allocno_priority_compare_func (const void *v1p, const void *v2p)
{
- ira_allocno_t a, conflict_allocno;
- ira_allocno_conflict_iterator aci;
+ ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
+ ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
+ int pri1, pri2;
- if (allocno_coalesced_p)
- {
- bitmap_clear (processed_coalesced_allocno_bitmap);
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
- if (a == a1)
- break;
- }
- }
- for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
- a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
- {
- if (reload_p)
- {
- for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
- conflict_allocno
- = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
- {
- if (ira_allocno_live_ranges_intersect_p (a, conflict_allocno))
- return true;
- if (conflict_allocno == a1)
- break;
- }
- }
- else
- {
- FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
- if (conflict_allocno == a1
- || (allocno_coalesced_p
- && bitmap_bit_p (processed_coalesced_allocno_bitmap,
- ALLOCNO_NUM (conflict_allocno))))
- return true;
- }
- if (a == a2)
- break;
- }
- return false;
+ pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
+ pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
+ if (pri2 != pri1)
+ return SORTGT (pri2, pri1);
+
+ /* If regs are equally good, sort by allocnos, so that the results of
+ qsort leave nothing to chance. */
+ return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
}
-/* The major function for aggressive allocno coalescing. For the
- reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
- allocnos have been coalesced, we set up flag
- allocno_coalesced_p. */
+/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
+ taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
static void
-coalesce_allocnos (bool reload_p)
+color_allocnos (void)
{
- ira_allocno_t a;
- ira_copy_t cp, next_cp, *sorted_copies;
- enum reg_class cover_class;
- enum machine_mode mode;
- unsigned int j;
- int i, n, cp_num, regno;
+ unsigned int i, n;
bitmap_iterator bi;
+ ira_allocno_t a;
- sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
- * sizeof (ira_copy_t));
- cp_num = 0;
- /* Collect copies. */
- EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
+ if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
{
- a = ira_allocnos[j];
- regno = ALLOCNO_REGNO (a);
- if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
- || (reload_p
- && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
- || (regno < ira_reg_equiv_len
- && (ira_reg_equiv_const[regno] != NULL_RTX
- || ira_reg_equiv_invariant_p[regno])))))
- continue;
- cover_class = ALLOCNO_COVER_CLASS (a);
- mode = ALLOCNO_MODE (a);
- for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
+ n = 0;
+ EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
- if (cp->first == a)
+ a = ira_allocnos[i];
+ if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
{
- next_cp = cp->next_first_allocno_copy;
- regno = ALLOCNO_REGNO (cp->second);
- if ((reload_p
- || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
- && ALLOCNO_MODE (cp->second) == mode))
- && cp->insn != NULL
- && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
- || (reload_p
- && ALLOCNO_ASSIGNED_P (cp->second)
- && ALLOCNO_HARD_REGNO (cp->second) < 0
- && (regno >= ira_reg_equiv_len
- || (! ira_reg_equiv_invariant_p[regno]
- && ira_reg_equiv_const[regno] == NULL_RTX)))))
- sorted_copies[cp_num++] = cp;
+ ALLOCNO_HARD_REGNO (a) = -1;
+ ALLOCNO_ASSIGNED_P (a) = true;
+ ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
+ ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ {
+ fprintf (ira_dump_file, " Spill");
+ ira_print_expanded_allocno (a);
+ fprintf (ira_dump_file, "\n");
+ }
+ continue;
}
- else if (cp->second == a)
- next_cp = cp->next_second_allocno_copy;
- else
- gcc_unreachable ();
+ sorted_allocnos[n++] = a;
}
- }
- qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
- /* Coalesced copies, most frequently executed first. */
- for (; cp_num != 0;)
- {
- for (i = 0; i < cp_num; i++)
+ if (n != 0)
{
- cp = sorted_copies[i];
- if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
+ setup_allocno_priorities (sorted_allocnos, n);
+ qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
+ allocno_priority_compare_func);
+ for (i = 0; i < n; i++)
{
- allocno_coalesced_p = true;
+ a = sorted_allocnos[i];
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
- fprintf
- (ira_dump_file,
- " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
- cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
- ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
- cp->freq);
- merge_allocnos (cp->first, cp->second);
- i++;
- break;
+ {
+ fprintf (ira_dump_file, " ");
+ ira_print_expanded_allocno (a);
+ fprintf (ira_dump_file, " -- ");
+ }
+ if (assign_hard_reg (a, false))
+ {
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, "assign hard reg %d\n",
+ ALLOCNO_HARD_REGNO (a));
+ }
+ else
+ {
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, "assign memory\n");
+ }
}
}
- /* Collect the rest of copies. */
- for (n = 0; i < cp_num; i++)
- {
- cp = sorted_copies[i];
- if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
- != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
- sorted_copies[n++] = cp;
- }
- cp_num = n;
}
- ira_free (sorted_copies);
-}
-
-/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
- taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
-static void
-color_allocnos (void)
-{
- unsigned int i;
- bitmap_iterator bi;
- ira_allocno_t a;
-
- allocno_coalesced_p = false;
- processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
- if (flag_ira_coalesce)
- coalesce_allocnos (false);
- /* Put the allocnos into the corresponding buckets. */
- colorable_allocno_bucket = NULL;
- uncolorable_allocno_bucket = NULL;
- EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
- {
- a = ira_allocnos[i];
- if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
+ else
+ {
+ /* Put the allocnos into the corresponding buckets. */
+ colorable_allocno_bucket = NULL;
+ uncolorable_allocno_bucket = NULL;
+ EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
- ALLOCNO_HARD_REGNO (a) = -1;
- ALLOCNO_ASSIGNED_P (a) = true;
- ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
- ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
- if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ a = ira_allocnos[i];
+ if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
{
- fprintf (ira_dump_file, " Spill");
- print_coalesced_allocno (a);
- fprintf (ira_dump_file, "\n");
+ ALLOCNO_HARD_REGNO (a) = -1;
+ ALLOCNO_ASSIGNED_P (a) = true;
+ ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
+ ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ {
+ fprintf (ira_dump_file, " Spill");
+ ira_print_expanded_allocno (a);
+ fprintf (ira_dump_file, "\n");
+ }
+ continue;
}
- continue;
+ put_allocno_into_bucket (a);
}
- put_allocno_into_bucket (a);
+ push_allocnos_to_stack ();
+ pop_allocnos_from_stack ();
}
- push_allocnos_to_stack ();
- pop_allocnos_from_stack ();
- if (flag_ira_coalesce)
- /* We don't need coalesced allocnos for ira_reassign_pseudos. */
- EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
- {
- a = ira_allocnos[i];
- ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
- ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
- }
- ira_free_bitmap (processed_coalesced_allocno_bitmap);
- allocno_coalesced_p = false;
}
\f
{
unsigned int j;
bitmap_iterator bi;
+ ira_loop_tree_node_t subloop_node, dest_loop_node;
+ edge e;
+ edge_iterator ei;
ira_assert (loop_tree_node->loop != NULL);
fprintf (ira_dump_file,
- "\n Loop %d (parent %d, header bb%d, depth %d)\n all:",
+ "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
loop_tree_node->loop->num,
(loop_tree_node->parent == NULL
? -1 : loop_tree_node->parent->loop->num),
loop_tree_node->loop->header->index,
loop_depth (loop_tree_node->loop));
+ for (subloop_node = loop_tree_node->children;
+ subloop_node != NULL;
+ subloop_node = subloop_node->next)
+ if (subloop_node->bb != NULL)
+ {
+ fprintf (ira_dump_file, " %d", subloop_node->bb->index);
+ FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
+ if (e->dest != EXIT_BLOCK_PTR
+ && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
+ != loop_tree_node))
+ fprintf (ira_dump_file, "(->%d:l%d)",
+ e->dest->index, dest_loop_node->loop->num);
+ }
+ fprintf (ira_dump_file, "\n all:");
EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
fprintf (ira_dump_file, "\n modified regnos:");
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;
EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
{
a = ira_allocnos[j];
- if (! ALLOCNO_ASSIGNED_P (a))
- continue;
- bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
+ if (ALLOCNO_ASSIGNED_P (a))
+ bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
}
/* Color all mentioned allocnos including transparent ones. */
color_allocnos ();
/* Process caps. They are processed just once. */
- if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
- || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL)
+ if (flag_ira_region == IRA_REGION_MIXED
+ || flag_ira_region == IRA_REGION_ALL)
EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
{
a = ira_allocnos[j];
/* Remove from processing in the next loop. */
bitmap_clear_bit (consideration_allocno_bitmap, j);
rclass = ALLOCNO_COVER_CLASS (a);
- if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
- && loop_tree_node->reg_pressure[rclass]
- <= ira_available_class_regs[rclass]))
+ if (flag_ira_region == IRA_REGION_MIXED
+ && (loop_tree_node->reg_pressure[rclass]
+ <= ira_available_class_regs[rclass]))
{
mode = ALLOCNO_MODE (a);
hard_regno = ALLOCNO_HARD_REGNO (a);
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];
if (subloop_allocno == NULL
|| ALLOCNO_CAP (subloop_allocno) != NULL)
continue;
+ ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass);
ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
ALLOCNO_NUM (subloop_allocno)));
- if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
+ if ((flag_ira_region == IRA_REGION_MIXED)
&& (loop_tree_node->reg_pressure[rclass]
<= ira_available_class_regs[rclass]))
{
else
{
cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
- cost = (ira_register_move_cost[mode][rclass][rclass]
+ 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,
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)
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. */
+= (ira_memory_move_cost[mode][rclass][0] * exit_freq
+ ira_memory_move_cost[mode][rclass][1] * enter_freq);
if (hard_regno2 != hard_regno)
- cost -= (ira_register_move_cost[mode][rclass][rclass]
+ cost -= (ira_get_register_move_cost (mode, rclass, rclass)
* (exit_freq + enter_freq));
}
}
if ((parent = loop_node->parent) != NULL
&& (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
{
+ ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno));
exit_freq = ira_loop_edge_freq (loop_node, regno, true);
enter_freq = ira_loop_edge_freq (loop_node, regno, false);
if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
+= (ira_memory_move_cost[mode][rclass][1] * exit_freq
+ ira_memory_move_cost[mode][rclass][0] * enter_freq);
if (hard_regno2 != hard_regno)
- cost -= (ira_register_move_cost[mode][rclass][rclass]
+ cost -= (ira_get_register_move_cost (mode, rclass, rclass)
* (exit_freq + enter_freq));
}
}
ira_allocno_t another_a;
ira_copy_t cp, next_cp;
+ ira_free_allocno_updated_costs (a);
ira_assert (! ALLOCNO_ASSIGNED_P (a));
cover_class = ALLOCNO_COVER_CLASS (a);
if (cover_class == NO_REGS)
}
else
gcc_unreachable ();
- if (cover_class != ALLOCNO_COVER_CLASS (another_a)
+ if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS
+ (another_a)]
|| ! ALLOCNO_ASSIGNED_P (another_a)
|| (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
continue;
rclass = REGNO_REG_CLASS (hard_regno);
i = ira_class_hard_reg_index[cover_class][hard_regno];
- ira_assert (i >= 0);
+ if (i < 0)
+ continue;
cost = (cp->first == a
- ? ira_register_move_cost[mode][rclass][cover_class]
- : ira_register_move_cost[mode][cover_class][rclass]);
+ ? ira_get_register_move_cost (mode, rclass, cover_class)
+ : ira_get_register_move_cost (mode, cover_class, rclass));
ira_allocate_and_set_or_copy_costs
(&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
cover_class, ALLOCNO_COVER_CLASS_COST (a),
}
}
-/* 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);
-}
-
/* 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,
ira_reassign_conflict_allocnos (int start_regno)
{
int i, allocnos_to_color_num;
- ira_allocno_t a, conflict_a;
- ira_allocno_conflict_iterator aci;
+ ira_allocno_t a;
enum reg_class cover_class;
bitmap allocnos_to_color;
ira_allocno_iterator ai;
allocnos_to_color_num = 0;
FOR_EACH_ALLOCNO (a, ai)
{
+ int n = ALLOCNO_NUM_OBJECTS (a);
+
if (! ALLOCNO_ASSIGNED_P (a)
&& ! bitmap_bit_p (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)
+ for (i = 0; i < n; i++)
{
- ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
- if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
- continue;
- bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
- sorted_allocnos[allocnos_to_color_num++] = conflict_a;
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ ira_object_t conflict_obj;
+ ira_object_conflict_iterator oci;
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+ ira_assert (ira_reg_classes_intersect_p
+ [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]);
+ if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
+ continue;
+ sorted_allocnos[allocnos_to_color_num++] = conflict_a;
+ }
}
}
ira_free_bitmap (allocnos_to_color);
{
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++)
On the other hand, it can worsen insn scheduling after the RA but
in practice it is less important than smaller stack frames. */
+/* TRUE if we coalesced some allocnos. In other words, if we got
+ loops formed by members first_coalesced_allocno and
+ next_coalesced_allocno containing more one allocno. */
+static bool allocno_coalesced_p;
+
+/* Bitmap used to prevent a repeated allocno processing because of
+ coalescing. */
+static bitmap processed_coalesced_allocno_bitmap;
+
+/* The function is used to sort allocnos according to their execution
+ frequencies. */
+static int
+copy_freq_compare_func (const void *v1p, const void *v2p)
+{
+ ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
+ int pri1, pri2;
+
+ pri1 = cp1->freq;
+ pri2 = cp2->freq;
+ if (pri2 - pri1)
+ return pri2 - pri1;
+
+ /* If freqencies are equal, sort by copies, so that the results of
+ qsort leave nothing to chance. */
+ return cp1->num - cp2->num;
+}
+
+/* Merge two sets of coalesced allocnos given correspondingly by
+ allocnos A1 and A2 (more accurately merging A2 set into A1
+ set). */
+static void
+merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
+{
+ ira_allocno_t a, first, last, next;
+
+ first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
+ if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
+ return;
+ for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
+ if (a == a2)
+ break;
+ last = a;
+ }
+ next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
+ ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
+ ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
+}
+
+/* Given two sets of coalesced sets of allocnos, A1 and A2, this
+ function determines if any conflicts exist between the two sets.
+ We use live ranges to find conflicts because conflicts are
+ represented only for allocnos of the same cover class and during
+ the reload pass we coalesce allocnos for sharing stack memory
+ slots. */
+static bool
+coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
+{
+ ira_allocno_t a, conflict_allocno;
+
+ bitmap_clear (processed_coalesced_allocno_bitmap);
+ if (allocno_coalesced_p)
+ {
+ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ bitmap_set_bit (processed_coalesced_allocno_bitmap,
+ OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (a, 0)));
+ if (a == a1)
+ break;
+ }
+ }
+ for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
+ a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+ {
+ for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
+ conflict_allocno
+ = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
+ {
+ if (allocnos_have_intersected_live_ranges_p (a, conflict_allocno))
+ return true;
+ if (conflict_allocno == a1)
+ break;
+ }
+
+ if (a == a2)
+ break;
+ }
+ return false;
+}
+
+/* The major function for aggressive allocno coalescing. We coalesce
+ only spilled allocnos. If some allocnos have been coalesced, we
+ set up flag allocno_coalesced_p. */
+static void
+coalesce_allocnos (void)
+{
+ ira_allocno_t a;
+ ira_copy_t cp, next_cp, *sorted_copies;
+ unsigned int j;
+ int i, n, cp_num, regno;
+ bitmap_iterator bi;
+
+ sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
+ * sizeof (ira_copy_t));
+ cp_num = 0;
+ /* Collect copies. */
+ EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
+ {
+ a = ira_allocnos[j];
+ regno = ALLOCNO_REGNO (a);
+ if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
+ || (regno < ira_reg_equiv_len
+ && (ira_reg_equiv_const[regno] != NULL_RTX
+ || ira_reg_equiv_invariant_p[regno])))
+ continue;
+ for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
+ {
+ if (cp->first == a)
+ {
+ next_cp = cp->next_first_allocno_copy;
+ regno = ALLOCNO_REGNO (cp->second);
+ /* For priority coloring we coalesce allocnos only with
+ the same cover class not with intersected cover
+ classes as it were possible. It is done for
+ simplicity. */
+ if ((cp->insn != NULL || cp->constraint_p)
+ && ALLOCNO_ASSIGNED_P (cp->second)
+ && ALLOCNO_HARD_REGNO (cp->second) < 0
+ && (regno >= ira_reg_equiv_len
+ || (! ira_reg_equiv_invariant_p[regno]
+ && ira_reg_equiv_const[regno] == NULL_RTX)))
+ sorted_copies[cp_num++] = cp;
+ }
+ else if (cp->second == a)
+ next_cp = cp->next_second_allocno_copy;
+ else
+ gcc_unreachable ();
+ }
+ }
+ qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
+ /* Coalesced copies, most frequently executed first. */
+ for (; cp_num != 0;)
+ {
+ for (i = 0; i < cp_num; i++)
+ {
+ cp = sorted_copies[i];
+ if (! coalesced_allocno_conflict_p (cp->first, cp->second))
+ {
+ allocno_coalesced_p = true;
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ fprintf
+ (ira_dump_file,
+ " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
+ cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
+ ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
+ cp->freq);
+ merge_allocnos (cp->first, cp->second);
+ i++;
+ break;
+ }
+ }
+ /* Collect the rest of copies. */
+ for (n = 0; i < cp_num; i++)
+ {
+ cp = sorted_copies[i];
+ if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
+ != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
+ sorted_copies[n++] = cp;
+ }
+ cp_num = n;
+ }
+ ira_free (sorted_copies);
+}
+
/* Usage cost and order number of coalesced allocno set to which
given pseudo register belongs to. */
static int *regno_coalesced_allocno_cost;
return num;
}
-/* Array of bitmaps of size IRA_MAX_POINT. Bitmap for given point
- contains numbers of coalesced allocnos living at this point. */
-static regset_head *coalesced_allocnos_living_at_program_points;
+/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
+ given slot contains live ranges of coalesced allocnos assigned to
+ given slot. */
+static live_range_t *slot_coalesced_allocnos_live_ranges;
-/* Return TRUE if coalesced allocnos represented by ALLOCNO live at
- program points of coalesced allocnos with number N. */
+/* 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
-coalesced_allocnos_live_at_points_p (ira_allocno_t allocno, int n)
+slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
{
- int i;
ira_allocno_t a;
- allocno_live_range_t r;
for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
{
- for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
- for (i = r->start; i <= r->finish; i++)
- if (bitmap_bit_p (&coalesced_allocnos_living_at_program_points[i], n))
- return true;
+ int i;
+ int nr = ALLOCNO_NUM_OBJECTS (a);
+ for (i = 0; i < nr; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ if (ira_live_ranges_intersect_p (slot_coalesced_allocnos_live_ranges[n],
+ OBJECT_LIVE_RANGES (obj)))
+ return true;
+ }
if (a == allocno)
break;
}
return false;
}
-/* Mark program points where coalesced allocnos represented by ALLOCNO
- live. */
+/* Update live ranges of slot to which coalesced allocnos represented
+ by ALLOCNO were assigned. */
static void
-set_coalesced_allocnos_live_points (ira_allocno_t allocno)
+setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
{
int i, n;
ira_allocno_t a;
- allocno_live_range_t r;
+ live_range_t r;
n = ALLOCNO_TEMP (allocno);
for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
{
- for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
- for (i = r->start; i <= r->finish; i++)
- bitmap_set_bit (&coalesced_allocnos_living_at_program_points[i], n);
+ int nr = ALLOCNO_NUM_OBJECTS (a);
+ for (i = 0; i < nr; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
+ slot_coalesced_allocnos_live_ranges[n]
+ = ira_merge_live_ranges
+ (slot_coalesced_allocnos_live_ranges[n], r);
+ }
if (a == allocno)
break;
}
static bool
coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
{
- int i, j, last_coalesced_allocno_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 ();
- coalesced_allocnos_living_at_program_points
- = (regset_head *) ira_allocate (sizeof (regset_head) * ira_max_point);
- for (i = 0; i < ira_max_point; i++)
- INIT_REG_SET (&coalesced_allocnos_living_at_program_points[i]);
+ slot_coalesced_allocnos_live_ranges
+ = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
+ memset (slot_coalesced_allocnos_live_ranges, 0,
+ sizeof (live_range_t) * ira_allocnos_num);
last_coalesced_allocno_num = 0;
/* Coalesce non-conflicting spilled allocnos preferring most
frequently used. */
{
allocno = spilled_coalesced_allocnos[i];
if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
+ || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
|| (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
- && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
- || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
+ && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
+ || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
continue;
for (j = 0; j < i; j++)
{
a = spilled_coalesced_allocnos[j];
+ 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))
- && ! coalesced_allocnos_live_at_points_p (allocno,
- ALLOCNO_TEMP (a)))
+ && ! 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++;
- set_coalesced_allocnos_live_points (allocno);
+ setup_slot_coalesced_allocno_live_ranges (allocno);
}
else
{
ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
- set_coalesced_allocnos_live_points (allocno);
+ setup_slot_coalesced_allocno_live_ranges (allocno);
merge_allocnos (a, allocno);
ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
}
}
- for (i = 0; i < ira_max_point; i++)
- CLEAR_REG_SET (&coalesced_allocnos_living_at_program_points[i]);
- ira_free (coalesced_allocnos_living_at_program_points);
+ for (i = 0; i < ira_allocnos_num; i++)
+ ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
+ ira_free (slot_coalesced_allocnos_live_ranges);
return merged_p;
}
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++)
ALLOCNO_NUM (allocno));
}
allocno_coalesced_p = false;
- coalesce_allocnos (true);
+ processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
+ coalesce_allocnos ();
ira_free_bitmap (coloring_allocno_bitmap);
regno_coalesced_allocno_cost
= (int *) ira_allocate (max_regno * sizeof (int));
if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
|| ALLOCNO_HARD_REGNO (allocno) >= 0
|| (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
- && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
- || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
+ && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
+ || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
continue;
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
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;
}
}
/* Try to assign a hard register (except for FORBIDDEN_REGS) to
- allocno A and return TRUE in the case of success. That is an
- analog of retry_global_alloc for IRA. */
+ allocno A and return TRUE in the case of success. */
static bool
allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
{
int hard_regno;
enum reg_class cover_class;
int regno = ALLOCNO_REGNO (a);
+ HARD_REG_SET saved[2];
+ int i, n;
- IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
- if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
- IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
+ n = ALLOCNO_NUM_OBJECTS (a);
+ for (i = 0; i < n; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ COPY_HARD_REG_SET (saved[i], OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
+ IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), forbidden_regs);
+ if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
+ IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
+ call_used_reg_set);
+ }
ALLOCNO_ASSIGNED_P (a) = false;
- ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
- ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
cover_class = ALLOCNO_COVER_CLASS (a);
update_curr_costs (a);
assign_hard_reg (a, true);
}
else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
fprintf (ira_dump_file, "\n");
-
+ for (i = 0; i < n; i++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), saved[i]);
+ }
return reg_renumber[regno] >= 0;
}
ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
HARD_REG_SET bad_spill_regs,
HARD_REG_SET *pseudo_forbidden_regs,
- HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
+ HARD_REG_SET *pseudo_previous_regs,
+ bitmap spilled)
{
- int i, m, n, regno;
+ int i, n, regno;
bool changed_p;
- ira_allocno_t a, conflict_a;
+ ira_allocno_t a;
HARD_REG_SET forbidden_regs;
- ira_allocno_conflict_iterator aci;
+ bitmap temp = BITMAP_ALLOC (NULL);
+
+ /* Add pseudos which conflict with pseudos already in
+ SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
+ to allocating in two steps as some of the conflicts might have
+ a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
+ for (i = 0; i < num; i++)
+ bitmap_set_bit (temp, spilled_pseudo_regs[i]);
+
+ for (i = 0, n = num; i < n; i++)
+ {
+ int nr, j;
+ int regno = spilled_pseudo_regs[i];
+ bitmap_set_bit (temp, regno);
+
+ a = ira_regno_allocno_map[regno];
+ nr = ALLOCNO_NUM_OBJECTS (a);
+ for (j = 0; j < nr; j++)
+ {
+ ira_object_t conflict_obj;
+ ira_object_t obj = ALLOCNO_OBJECT (a, j);
+ ira_object_conflict_iterator oci;
+
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ {
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+ if (ALLOCNO_HARD_REGNO (conflict_a) < 0
+ && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
+ && bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
+ {
+ spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
+ /* ?!? This seems wrong. */
+ bitmap_set_bit (consideration_allocno_bitmap,
+ ALLOCNO_NUM (conflict_a));
+ }
+ }
+ }
+ }
if (num > 1)
qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
changed_p = false;
/* Try to assign hard registers to pseudos from
SPILLED_PSEUDO_REGS. */
- for (m = i = 0; i < num; i++)
+ for (i = 0; i < num; i++)
{
regno = spilled_pseudo_regs[i];
COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
ira_assert (reg_renumber[regno] < 0);
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
fprintf (ira_dump_file,
- " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
+ " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
ALLOCNO_MEMORY_COST (a)
- ALLOCNO_COVER_CLASS_COST (a));
allocno_reload_assign (a, forbidden_regs);
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);
- }
- }
}
+ BITMAP_FREE (temp);
return changed_p;
}
bitmap_iterator bi;
struct ira_spilled_reg_stack_slot *slot = NULL;
- ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
+ ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
&& inherent_size <= total_size
&& ALLOCNO_HARD_REGNO (allocno) < 0);
if (! flag_ira_share_spill_slots)
if (slot->width < total_size
|| GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
continue;
-
+
EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
FIRST_PSEUDO_REGISTER, i, bi)
{
another_allocno = ira_regno_allocno_map[i];
- if (ira_allocno_live_ranges_intersect_p (allocno,
- another_allocno))
+ if (allocnos_have_intersected_live_ranges_p (allocno,
+ another_allocno))
goto cont;
}
for (cost = 0, cp = ALLOCNO_COPIES (allocno);
if (x != NULL_RTX)
{
ira_assert (slot->width >= total_size);
+#ifdef ENABLE_IRA_CHECKING
EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
FIRST_PSEUDO_REGISTER, i, bi)
{
- ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i));
+ ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i));
}
+#endif
SET_REGNO_REG_SET (&slot->spilled_regs, regno);
if (internal_flag_ira_verbose > 3 && ira_dump_file)
{
int slot_num;
ira_allocno_t allocno;
- ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
+ ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
allocno = ira_regno_allocno_map[regno];
slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
if (slot_num == -1)
hard_regno = reg_renumber[regno];
ira_assert (hard_regno >= 0);
a = ira_regno_allocno_map[regno];
- length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+ length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
for (j = 0; j < nregs; j++)
int call_used_count, other_call_used_count;
int hard_regno, other_hard_regno;
- cost = calculate_spill_cost (regnos, in, out, insn,
+ cost = calculate_spill_cost (regnos, in, out, insn,
&length, &nrefs, &call_used_count, &hard_regno);
other_cost = calculate_spill_cost (other_regnos, in, out, insn,
&other_length, &other_nrefs,
enum machine_mode mode;
ira_allocno_t a;
ira_allocno_iterator ai;
- allocno_live_range_t r;
+ live_range_t r;
HARD_REG_SET conflict_hard_regs, *used_hard_regs;
sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
* ira_max_point);
for (i = 0; i < ira_max_point; i++)
CLEAR_HARD_REG_SET (used_hard_regs[i]);
- qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t),
+ qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
allocno_priority_compare_func);
for (i = 0; i < num; i++)
{
+ int nr, l;
+
a = sorted_allocnos[i];
- COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
- for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
- for (j = r->start; j <= r->finish; j++)
- IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
+ nr = ALLOCNO_NUM_OBJECTS (a);
+ CLEAR_HARD_REG_SET (conflict_hard_regs);
+ for (l = 0; l < nr; l++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, l);
+ IOR_HARD_REG_SET (conflict_hard_regs,
+ OBJECT_CONFLICT_HARD_REGS (obj));
+ for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
+ for (j = r->start; j <= r->finish; j++)
+ IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
+ }
cover_class = ALLOCNO_COVER_CLASS (a);
ALLOCNO_ASSIGNED_P (a) = true;
ALLOCNO_HARD_REGNO (a) = -1;
(prohibited_class_mode_regs[cover_class][mode], hard_regno)))
continue;
ALLOCNO_HARD_REGNO (a) = hard_regno;
- for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
- for (k = r->start; k <= r->finish; k++)
- IOR_HARD_REG_SET (used_hard_regs[k],
- ira_reg_mode_hard_regset[hard_regno][mode]);
+ for (l = 0; l < nr; l++)
+ {
+ ira_object_t obj = ALLOCNO_OBJECT (a, l);
+ for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
+ for (k = r->start; k <= r->finish; k++)
+ IOR_HARD_REG_SET (used_hard_regs[k],
+ ira_reg_mode_hard_regset[hard_regno][mode]);
+ }
break;
}
}
ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
}
- if (optimize)
+ if (ira_conflicts_p)
color ();
else
fast_allocation ();