/* IRA allocation based on graph coloring.
- Copyright (C) 2006-2020 Free Software Foundation, Inc.
+ Copyright (C) 2006-2021 Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
This file is part of GCC.
ira_allocno_t next_thread_allocno;
/* All thread frequency. Defined only for first thread allocno. */
int thread_freq;
+ /* Sum of frequencies of hard register preferences of the allocno. */
+ int hard_reg_prefs;
};
/* See above. */
static void
print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
{
- int i, start;
+ int i, start, end;
- for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
{
- if (TEST_HARD_REG_BIT (set, i))
+ bool reg_included = TEST_HARD_REG_BIT (set, i);
+
+ if (reg_included)
{
- if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
+ if (start == -1)
start = i;
+ end = i;
}
- if (start >= 0
- && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
+ if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
{
- if (start == i - 1)
+ if (start == end)
fprintf (f, " %d", start);
- else if (start == i - 2)
- fprintf (f, " %d %d", start, start + 1);
+ else if (start == end + 1)
+ fprintf (f, " %d %d", start, end);
else
- fprintf (f, " %d-%d", start, i - 1);
+ fprintf (f, " %d-%d", start, end);
start = -1;
}
}
connecting this allocno to the one being allocated. */
int divisor;
+ /* Allocno from which we started chaining costs of connected
+ allocnos. */
+ ira_allocno_t start;
+
/* Allocno from which we are chaining costs of connected allocnos.
It is used not go back in graph of allocnos connected by
copies. */
update_cost_queue = NULL;
}
-/* Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
+/* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless
ALLOCNO is already in the queue, or has NO_REGS class. */
static inline void
-queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
+queue_update_cost (ira_allocno_t allocno, ira_allocno_t start,
+ ira_allocno_t from, int divisor)
{
struct update_cost_queue_elem *elem;
&& ALLOCNO_CLASS (allocno) != NO_REGS)
{
elem->check = update_cost_check;
+ elem->start = start;
elem->from = from;
elem->divisor = divisor;
elem->next = NULL;
}
/* Try to remove the first element from update_cost_queue. Return
- false if the queue was empty, otherwise make (*ALLOCNO, *FROM,
- *DIVISOR) describe the removed element. */
+ false if the queue was empty, otherwise make (*ALLOCNO, *START,
+ *FROM, *DIVISOR) describe the removed element. */
static inline bool
-get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
+get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start,
+ ira_allocno_t *from, int *divisor)
{
struct update_cost_queue_elem *elem;
*allocno = update_cost_queue;
elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
+ *start = elem->start;
*from = elem->from;
*divisor = elem->divisor;
update_cost_queue = elem->next;
return true;
}
+/* Return TRUE if allocnos A1 and A2 conflicts. Here we are
+ interesting only in conflicts of allocnos with intersected allocno
+ classes. */
+static bool
+allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
+{
+ ira_object_t obj, conflict_obj;
+ ira_object_conflict_iterator oci;
+ int word, nwords = ALLOCNO_NUM_OBJECTS (a1);
+
+ for (word = 0; word < nwords; word++)
+ {
+ obj = ALLOCNO_OBJECT (a1, word);
+ /* Take preferences of conflicting allocnos into account. */
+ FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+ if (OBJECT_ALLOCNO (conflict_obj) == a2)
+ return true;
+ }
+ return false;
+}
+
/* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
by copies to ALLOCNO to increase chances to remove some copies as
- the result of subsequent assignment. Record cost updates if
- RECORD_P is true. */
+ the result of subsequent assignment. Update conflict costs.
+ Record cost updates if RECORD_P is true. */
static void
update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
int divisor, bool decr_p, bool record_p)
int cost, update_cost, update_conflict_cost;
machine_mode mode;
enum reg_class rclass, aclass;
- ira_allocno_t another_allocno, from = NULL;
+ ira_allocno_t another_allocno, start = allocno, from = NULL;
ira_copy_t cp, next_cp;
rclass = REGNO_REG_CLASS (hard_regno);
else
gcc_unreachable ();
- if (another_allocno == from)
+ if (another_allocno == from
+ || (ALLOCNO_COLOR_DATA (another_allocno) != NULL
+ && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
+ != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno)))
continue;
aclass = ALLOCNO_CLASS (another_allocno);
register classes bigger modes might be invalid,
e.g. DImode for AREG on x86. For such cases the
register move cost will be maximal. */
- mode = narrower_subreg_mode (mode, ALLOCNO_MODE (cp->second));
+ mode = narrower_subreg_mode (ALLOCNO_MODE (cp->first),
+ ALLOCNO_MODE (cp->second));
+
ira_init_register_move_cost_if_necessary (mode);
-
+
cost = (cp->second == allocno
? ira_register_move_cost[mode][rclass][aclass]
: ira_register_move_cost[mode][aclass][rclass]);
if (decr_p)
cost = -cost;
- update_conflict_cost = update_cost = cp->freq * cost / divisor;
-
- if (ALLOCNO_COLOR_DATA (another_allocno) != NULL
- && (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
- != ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno))
- /* Decrease conflict cost of ANOTHER_ALLOCNO if it is not
- in the same allocation thread. */
- update_conflict_cost /= COST_HOP_DIVISOR;
+ update_cost = cp->freq * cost / divisor;
+ update_conflict_cost = update_cost;
+ if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
+ fprintf (ira_dump_file,
+ " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
+ ALLOCNO_NUM (another_allocno), ALLOCNO_REGNO (another_allocno),
+ hard_regno, update_cost, update_conflict_cost);
if (update_cost == 0)
continue;
if (! update_allocno_cost (another_allocno, hard_regno,
update_cost, update_conflict_cost))
continue;
- queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
+ queue_update_cost (another_allocno, start, allocno,
+ divisor * COST_HOP_DIVISOR);
if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
= get_update_cost_record (hard_regno, divisor,
->update_cost_records);
}
}
- while (get_next_update_cost (&allocno, &from, &divisor));
+ while (get_next_update_cost (&allocno, &start, &from, &divisor));
}
/* Decrease preferred ALLOCNO hard register costs and costs of
start_update_cost ();
for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
- update_costs_from_allocno (allocno, pref->hard_regno,
- COST_HOP_DIVISOR, true, true);
+ {
+ if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Start updating from pref of hr%d for a%dr%d:\n",
+ pref->hard_regno, ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
+ update_costs_from_allocno (allocno, pref->hard_regno,
+ COST_HOP_DIVISOR, true, true);
+ }
}
/* Update (decrease if DECR_P) the cost of allocnos connected to
hard_regno = ALLOCNO_HARD_REGNO (allocno);
ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
start_update_cost ();
+ if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Start updating from a%dr%d by copies:\n",
+ ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
}
return;
records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
start_update_cost ();
+ if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Start restoring from a%dr%d:\n",
+ ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
for (curr = records; curr != NULL; curr = curr->next)
update_costs_from_allocno (allocno, curr->hard_regno,
curr->divisor, true, false);
int *conflict_costs;
bool cont_p;
enum reg_class another_aclass;
- ira_allocno_t allocno, another_allocno, from;
+ ira_allocno_t allocno, another_allocno, start, from;
ira_copy_t cp, next_cp;
- while (get_next_update_cost (&allocno, &from, &divisor))
+ while (get_next_update_cost (&allocno, &start, &from, &divisor))
for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
{
if (cp->first == allocno)
else
gcc_unreachable ();
- if (another_allocno == from)
+ if (another_allocno == from
+ || allocnos_conflict_p (another_allocno, start))
continue;
another_aclass = ALLOCNO_CLASS (another_allocno);
* COST_HOP_DIVISOR
* COST_HOP_DIVISOR
* COST_HOP_DIVISOR))
- queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
+ queue_update_cost (another_allocno, start, from, divisor * COST_HOP_DIVISOR);
}
}
continue;
full_costs[j] -= conflict_costs[k];
}
- queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
-
+ queue_update_cost (conflict_a, conflict_a, NULL, COST_HOP_DIVISOR);
}
}
}
if (! retry_p)
{
start_update_cost ();
- queue_update_cost (a, NULL, COST_HOP_DIVISOR);
+ queue_update_cost (a, a, NULL, COST_HOP_DIVISOR);
update_conflict_hard_regno_costs (full_costs, aclass, false);
}
min_cost = min_full_cost = INT_MAX;
best_hard_regno = hard_regno;
ira_assert (hard_regno >= 0);
}
+ if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, "(%d=%d,%d) ", hard_regno, cost, full_cost);
}
+ if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, "\n");
if (min_full_cost > mem_cost
/* Do not spill static chain pointer pseudo when non-local goto
is used. */
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
fprintf
(ira_dump_file,
- " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
+ " Forming thread by 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);
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
- fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
+ fprintf (ira_dump_file, " Result (freq=%d): a%dr%d(%d)",
ALLOCNO_COLOR_DATA (thread1)->thread_freq,
ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
ALLOCNO_FREQ (thread1));
ira_copy_t cp, next_cp;
int cp_num = 0;
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Forming thread from allocno a%dr%d:\n",
+ ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
{
if (cp->first == a)
ira_allocno_t a;
unsigned int j;
bitmap_iterator bi;
+ ira_pref_t pref;
EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
{
ALLOCNO_COLOR_DATA (a)->first_thread_allocno
= ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
+ ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0;
+ for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
+ ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq;
}
}
ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
- /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
- pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
- pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
- if ((diff = pref1 - pref2) != 0)
- return diff;
freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
if ((diff = freq1 - freq2) != 0)
a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
if ((diff = a2_num - a1_num) != 0)
return diff;
+ /* Push allocnos with minimal conflict_allocno_hard_prefs first. */
+ pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
+ pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
+ if ((diff = pref1 - pref2) != 0)
+ return diff;
return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
}
static void
push_only_colorable (void)
{
+ if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Forming thread from colorable bucket:\n");
form_threads_from_bucket (colorable_allocno_bucket);
+ for (ira_allocno_t a = colorable_allocno_bucket;
+ a != NULL;
+ a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
+ update_costs_from_prefs (a);
sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
for (;colorable_allocno_bucket != NULL;)
remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
int freq, i;
edge_iterator ei;
edge e;
- vec<edge> edges;
ira_assert (current_loops != NULL && loop_node->loop != NULL
&& (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
}
else
{
- edges = get_loop_exit_edges (loop_node->loop);
+ auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
FOR_EACH_VEC_ELT (edges, i, e)
if (regno < 0
|| (bitmap_bit_p (df_get_live_out (e->src), regno)
&& bitmap_bit_p (df_get_live_in (e->dest), regno)))
freq += EDGE_FREQUENCY (e);
- edges.release ();
}
return REG_FREQ_FROM_EDGE_FREQ (freq);
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",
+ fprintf (ira_dump_file, " assign reg %d\n",
ALLOCNO_HARD_REGNO (allocno));
}
else if (ALLOCNO_ASSIGNED_P (allocno))
if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
{
ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
- update_costs_from_prefs (a);
update_conflict_allocno_hard_prefs (a);
}
else
projects / thirdparty / gcc.git / blobdiff