/* IRA allocation based on graph coloring.
- Copyright (C) 2006-2013 Free Software Foundation, Inc.
+ Copyright (C) 2006-2015 Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "predict.h"
+#include "tree.h"
#include "rtl.h"
+#include "df.h"
#include "tm_p.h"
#include "target.h"
#include "regs.h"
#include "flags.h"
-#include "sbitmap.h"
-#include "bitmap.h"
-#include "hash-table.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
+#include "alias.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "diagnostic-core.h"
#include "reload.h"
#include "params.h"
-#include "df.h"
+#include "cfgloop.h"
+#include "ira.h"
+#include "alloc-pool.h"
#include "ira-int.h"
typedef struct allocno_hard_regs *allocno_hard_regs_t;
HARD_REG_SET set;
/* Overall (spilling) cost of all allocnos with given register
set. */
- HOST_WIDEST_INT cost;
+ int64_t cost;
};
typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
struct allocno_color_data
{
/* TRUE value means that the allocno was not removed yet from the
- conflicting graph during colouring. */
+ conflicting graph during coloring. */
unsigned int in_graph_p : 1;
/* TRUE if it is put on the stack to make other allocnos
colorable. */
and all its subnodes in the tree (forest) of allocno hard
register nodes (see comments above). */
int hard_regs_subnodes_start;
- /* The length of the previous array. */
+ /* The length of the previous array. */
int hard_regs_subnodes_num;
/* Records about updating allocno hard reg costs from copies. If
the allocno did not get expected hard register, these records are
used to restore original hard reg costs of allocnos connected to
this allocno by copies. */
struct update_cost_record *update_cost_records;
+ /* Threads. We collect allocnos connected by copies into threads
+ and try to assign hard regs to allocnos by threads. */
+ /* Allocno representing all thread. */
+ ira_allocno_t first_thread_allocno;
+ /* Allocnos in thread forms a cycle list through the following
+ member. */
+ ira_allocno_t next_thread_allocno;
+ /* All thread frequency. Defined only for first thread allocno. */
+ int thread_freq;
};
/* See above. */
/* Vector of unique allocno hard registers. */
static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
-struct allocno_hard_regs_hasher :
typed_noop_remove <allocno_hard_regs>
+struct allocno_hard_regs_hasher :
nofree_ptr_hash <allocno_hard_regs>
{
- typedef allocno_hard_regs value_type;
- typedef allocno_hard_regs compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const allocno_hard_regs *);
+ static inline bool equal (const allocno_hard_regs *,
+ const allocno_hard_regs *);
};
/* Returns hash value for allocno hard registers V. */
inline hashval_t
-allocno_hard_regs_hasher::hash (const value_type *hv)
+allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
{
return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
}
/* Compares allocno hard registers V1 and V2. */
inline bool
-allocno_hard_regs_hasher::equal (const value_type *hv1, const compare_type *hv2)
+allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
+ const allocno_hard_regs *hv2)
{
return hard_reg_set_equal_p (hv1->set, hv2->set);
}
/* Hash table of unique allocno hard registers. */
-static hash_table <allocno_hard_regs_hasher> allocno_hard_regs_htab;
+static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
/* Return allocno hard registers in the hash table equal to HV. */
static allocno_hard_regs_t
find_hard_regs (allocno_hard_regs_t hv)
{
- return allocno_hard_regs_htab.find (hv);
+ return allocno_hard_regs_htab->find (hv);
}
/* Insert allocno hard registers HV in the hash table (if it is not
static allocno_hard_regs_t
insert_hard_regs (allocno_hard_regs_t hv)
{
- allocno_hard_regs **slot = allocno_hard_regs_htab.find_slot (hv, INSERT);
+ allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
if (*slot == NULL)
*slot = hv;
init_allocno_hard_regs (void)
{
allocno_hard_regs_vec.create (200);
- allocno_hard_regs_htab.create (200);
+ allocno_hard_regs_htab
+ = new hash_table<allocno_hard_regs_hasher> (200);
}
/* Add (or update info about) allocno hard registers with SET and
COST. */
static allocno_hard_regs_t
-add_allocno_hard_regs (HARD_REG_SET set, HOST_WIDEST_INT cost)
+add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
{
struct allocno_hard_regs temp;
allocno_hard_regs_t hv;
allocno_hard_regs_vec.iterate (i, &hv);
i++)
ira_free (hv);
- allocno_hard_regs_htab.dispose ();
+ delete allocno_hard_regs_htab;
+ allocno_hard_regs_htab = NULL;
allocno_hard_regs_vec.release ();
}
fprintf (f, " ");
fprintf (f, "%d:(", node->preorder_num);
print_hard_reg_set (f, node->hard_regs->set, false);
- fprintf (f, ")@" HOST_WIDEST_INT_PRINT_DEC "\n", node->hard_regs->cost);
+ fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
print_hard_regs_subforest (f, node->first, level + 1);
}
}
HARD_REG_SET node_set;
nobj = ALLOCNO_NUM_OBJECTS (a);
- conflict_size = 0;
data = ALLOCNO_COLOR_DATA (a);
subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
COPY_HARD_REG_SET (profitable_hard_regs, data->profitable_hard_regs);
subnodes[i].left_conflict_subnodes_size = 0;
}
start = node_preorder_num * allocno_hard_regs_nodes_num;
- for (i = data->hard_regs_subnodes_num - 1; i >= 0; i--)
+ for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
{
int size, parent_i;
allocno_hard_regs_node_t parent;
- subnodes[i].left_conflict_subnodes_size,
subnodes[i].left_conflict_size));
parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
- if (parent == NULL)
- continue;
+ gcc_checking_assert(parent);
parent_i
= allocno_hard_regs_subnode_index[start + parent->preorder_num];
- if (parent_i < 0)
- continue;
+ gcc_checking_assert(parent_i >= 0);
subnodes[parent_i].left_conflict_subnodes_size += size;
}
left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
conflict_size
- += (left_conflict_subnodes_size
- + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
- subnodes[0].left_conflict_size));
+ = (left_conflict_subnodes_size
+ + MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
+ subnodes[0].left_conflict_size));
conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
data->colorable_p = conflict_size <= data->available_regs_num;
return data->colorable_p;
ira_allocno_t a;
bitmap_iterator bi;
enum reg_class aclass;
- enum machine_mode mode;
+ machine_mode mode;
allocno_color_data_t data;
/* Initial set up from allocno classes and explicitly conflicting
continue;
data = ALLOCNO_COLOR_DATA (a);
if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
- && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
+ && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
+ /* Do not empty profitable regs for static chain pointer
+ pseudo when non-local goto is used. */
+ && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
CLEAR_HARD_REG_SET (data->profitable_hard_regs);
else
{
if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
hard_regno))
continue;
- if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
+ if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
+ /* Do not remove HARD_REGNO for static chain pointer
+ pseudo when non-local goto is used. */
+ && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
CLEAR_HARD_REG_BIT (data->profitable_hard_regs,
hard_regno);
else if (min_cost > costs[j])
}
}
else if (ALLOCNO_UPDATED_MEMORY_COST (a)
- < ALLOCNO_UPDATED_CLASS_COST (a))
+ < ALLOCNO_UPDATED_CLASS_COST (a)
+ /* Do not empty profitable regs for static chain
+ pointer pseudo when non-local goto is used. */
+ && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
CLEAR_HARD_REG_SET (data->profitable_hard_regs);
if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
allocnos. */
/* Pool for update cost records. */
-static alloc_pool update_cost_record_pool;
-
-/* Initiate update cost records. */
-static void
-init_update_cost_records (void)
-{
- update_cost_record_pool
- = create_alloc_pool ("update cost records",
- sizeof (struct update_cost_record), 100);
-}
+static object_allocator<update_cost_record> update_cost_record_pool
+ ("update cost records", 100);
/* Return new update cost record with given params. */
static struct update_cost_record *
{
struct update_cost_record *record;
- record = (struct update_cost_record *) pool_alloc (update_cost_record_pool);
+ record = update_cost_record_pool.allocate ();
record->hard_regno = hard_regno;
record->divisor = divisor;
record->next = next;
while (list != NULL)
{
next = list->next;
- pool_free (update_cost_record_pool, list);
+ update_cost_record_pool.remove (list);
list = next;
}
}
static void
finish_update_cost_records (void)
{
- free_alloc_pool (update_cost_record_pool);
+ update_cost_record_pool.release ();
}
/* Array whose element value is TRUE if the corresponding hard
connecting this allocno to the one being allocated. */
int divisor;
- /* Allocno from which we are chaning costs of connected allocnos.
+ /* Allocno from which we are chaining costs of connected allocnos.
It is used not go back in graph of allocnos connected by
copies. */
ira_allocno_t from;
static int update_cost_check;
/* Allocate and initialize data necessary for function
- update_costs_from_copiess. */
+ update_costs_from_copies. */
static void
initiate_cost_update (void)
{
= (struct update_cost_queue_elem *) ira_allocate (size);
memset (update_cost_queue_elems, 0, size);
update_cost_check = 0;
- init_update_cost_records ();
}
/* Deallocate data used by function update_costs_from_copies. */
int divisor, bool decr_p, bool record_p)
{
int cost, update_cost;
- enum machine_mode mode;
+ machine_mode mode;
enum reg_class rclass, aclass;
ira_allocno_t another_allocno, from = NULL;
ira_copy_t cp, next_cp;
/* Update (decrease if DECR_P) the cost of allocnos connected to
ALLOCNO through copies to increase chances to remove some copies as
the result of subsequent assignment. ALLOCNO was just assigned to
- a hard register. */
+ a hard register. Record cost updates if RECORD_P is true. */
static void
-update_costs_from_copies (ira_allocno_t allocno, bool decr_p)
+update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
{
int hard_regno;
hard_regno = ALLOCNO_HARD_REGNO (allocno);
ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
start_update_cost ();
- update_costs_from_allocno (allocno, hard_regno, 1, decr_p, true);
+ update_costs_from_allocno (allocno, hard_regno, 1, decr_p, record_p);
}
/* Restore costs of allocnos connected to ALLOCNO by copies as it was
index = ira_class_hard_reg_index[aclass][hard_regno];
if (index < 0)
continue;
- cost = conflict_costs [i] * mult / div;
+ cost = (int) ((unsigned) conflict_costs [i] * mult) / div;
if (cost == 0)
continue;
cont_p = true;
{
int j, nwords, nregs;
enum reg_class aclass;
- enum machine_mode mode;
+ machine_mode mode;
aclass = ALLOCNO_CLASS (a);
mode = ALLOCNO_MODE (a);
}
return j == nregs;
}
-#ifndef HONOR_REG_ALLOC_ORDER
/* Return number of registers needed to be saved and restored at
function prologue/epilogue if we allocate HARD_REGNO to hold value
of MODE. */
static int
-calculate_saved_nregs (int hard_regno, enum machine_mode mode)
+calculate_saved_nregs (int hard_regno, machine_mode mode)
{
int i;
int nregs = 0;
nregs++;
return nregs;
}
-#endif
/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
that the function called from function
int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
int *a_costs;
enum reg_class aclass;
- enum machine_mode mode;
+ machine_mode mode;
static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
-#ifndef HONOR_REG_ALLOC_ORDER
int saved_nregs;
enum reg_class rclass;
int add_cost;
-#endif
#ifdef STACK_REGS
bool no_stack_reg_p;
#endif
{
ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
enum reg_class conflict_aclass;
+ allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
/* 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))
- || ((!ALLOCNO_ASSIGNED_P (conflict_a)
- || ALLOCNO_HARD_REGNO (conflict_a) < 0)
- && !(hard_reg_set_intersect_p
- (profitable_hard_regs,
- ALLOCNO_COLOR_DATA
- (conflict_a)->profitable_hard_regs)))))
- continue;
+ && ((!ALLOCNO_ASSIGNED_P (conflict_a)
+ || ALLOCNO_HARD_REGNO (conflict_a) < 0)
+ && !(hard_reg_set_intersect_p
+ (profitable_hard_regs,
+ ALLOCNO_COLOR_DATA
+ (conflict_a)->profitable_hard_regs))))
+ {
+ /* All conflict allocnos are in consideration bitmap
+ when retry_p is false. It might change in future and
+ if it happens the assert will be broken. It means
+ the code should be modified for the new
+ assumptions. */
+ ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
+ ALLOCNO_NUM (conflict_a)));
+ continue;
+ }
conflict_aclass = ALLOCNO_CLASS (conflict_a);
ira_assert (ira_reg_classes_intersect_p
[aclass][conflict_aclass]);
hard_regno = ira_class_hard_regs[aclass][j];
ira_assert (hard_regno >= 0);
k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
- if (k < 0)
+ if (k < 0
+ /* If HARD_REGNO is not available for CONFLICT_A,
+ the conflict would be ignored, since HARD_REGNO
+ will never be assigned to CONFLICT_A. */
+ || !TEST_HARD_REG_BIT (data->profitable_hard_regs,
+ hard_regno))
continue;
full_costs[j] -= conflict_costs[k];
}
continue;
cost = costs[i];
full_cost = full_costs[i];
-#ifndef HONOR_REG_ALLOC_ORDER
- if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
- /* We need to save/restore the hard register in
- epilogue/prologue. Therefore we increase the cost. */
+ if (!HONOR_REG_ALLOC_ORDER)
{
- rclass = REGNO_REG_CLASS (hard_regno);
- add_cost = ((ira_memory_move_cost[mode][rclass][0]
- + ira_memory_move_cost[mode][rclass][1])
- * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1);
- cost += add_cost;
- full_cost += add_cost;
+ if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
+ /* We need to save/restore the hard register in
+ epilogue/prologue. Therefore we increase the cost. */
+ {
+ rclass = REGNO_REG_CLASS (hard_regno);
+ add_cost = ((ira_memory_move_cost[mode][rclass][0]
+ + ira_memory_move_cost[mode][rclass][1])
+ * saved_nregs / hard_regno_nregs[hard_regno][mode] - 1);
+ cost += add_cost;
+ full_cost += add_cost;
+ }
}
-#endif
if (min_cost > cost)
min_cost = cost;
if (min_full_cost > full_cost)
ira_assert (hard_regno >= 0);
}
}
- if (min_full_cost > mem_cost)
+ if (min_full_cost > mem_cost
+ /* Do not spill static chain pointer pseudo when non-local goto
+ is used. */
+ && ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
{
if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
for (i = hard_regno_nregs[best_hard_regno][mode] - 1; i >= 0; i--)
allocated_hardreg_p[best_hard_regno + i] = true;
}
- restore_costs_from_copies (a);
+ if (! retry_p)
+ restore_costs_from_copies (a);
ALLOCNO_HARD_REGNO (a) = best_hard_regno;
ALLOCNO_ASSIGNED_P (a) = true;
if (best_hard_regno >= 0)
- update_costs_from_copies (a, true);
+ update_costs_from_copies (a, true, ! retry_p);
ira_assert (ALLOCNO_CLASS (a) == aclass);
- /* We don't need updated costs anymore: */
+ /* We don't need updated costs anymore. */
ira_free_allocno_updated_costs (a);
return best_hard_regno >= 0;
}
\f
+/* An array used to sort copies. */
+static ira_copy_t *sorted_copies;
+
+/* 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 allocno classes. */
+static bool
+allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
+{
+ rtx reg1, reg2;
+ int i, j;
+ int n1 = ALLOCNO_NUM_OBJECTS (a1);
+ int n2 = ALLOCNO_NUM_OBJECTS (a2);
+
+ if (a1 == a2)
+ return false;
+ reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
+ reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
+ if (reg1 != NULL && reg2 != NULL
+ && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
+ 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;
+}
+
+/* The function is used to sort copies 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 frequencies are equal, sort by copies, so that the results of
+ qsort leave nothing to chance. */
+ return cp1->num - cp2->num;
+}
+
+\f
+
+/* Return true if any allocno from thread of A1 conflicts with any
+ allocno from thread A2. */
+static bool
+allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
+{
+ ira_allocno_t a, conflict_a;
+
+ for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
+ a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
+ {
+ for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
+ conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
+ {
+ if (allocnos_conflict_by_live_ranges_p (a, conflict_a))
+ return true;
+ if (conflict_a == a1)
+ break;
+ }
+ if (a == a2)
+ break;
+ }
+ return false;
+}
+
+/* Merge two threads given correspondingly by their first allocnos T1
+ and T2 (more accurately merging T2 into T1). */
+static void
+merge_threads (ira_allocno_t t1, ira_allocno_t t2)
+{
+ ira_allocno_t a, next, last;
+
+ gcc_assert (t1 != t2
+ && ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
+ && ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
+ for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
+ a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
+ {
+ ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
+ if (a == t2)
+ break;
+ last = a;
+ }
+ next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
+ ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
+ ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
+ ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
+}
+
+/* Create threads by processing CP_NUM copies from sorted copies. We
+ process the most expensive copies first. */
+static void
+form_threads_from_copies (int cp_num)
+{
+ ira_allocno_t a, thread1, thread2;
+ ira_copy_t cp;
+ int i, n;
+
+ qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
+ /* Form threads processing copies, most frequently executed
+ first. */
+ for (; cp_num != 0;)
+ {
+ for (i = 0; i < cp_num; i++)
+ {
+ cp = sorted_copies[i];
+ thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
+ thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
+ if (thread1 == thread2)
+ continue;
+ if (! allocno_thread_conflict_p (thread1, thread2))
+ {
+ 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",
+ cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
+ ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
+ cp->freq);
+ merge_threads (thread1, thread2);
+ 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)",
+ ALLOCNO_COLOR_DATA (thread1)->thread_freq,
+ ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
+ ALLOCNO_FREQ (thread1));
+ for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
+ a != thread1;
+ a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
+ fprintf (ira_dump_file, " a%dr%d(%d)",
+ ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
+ ALLOCNO_FREQ (a));
+ fprintf (ira_dump_file, "\n");
+ }
+ i++;
+ break;
+ }
+ }
+ /* Collect the rest of copies. */
+ for (n = 0; i < cp_num; i++)
+ {
+ cp = sorted_copies[i];
+ if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
+ != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
+ sorted_copies[n++] = cp;
+ }
+ cp_num = n;
+ }
+}
+
+/* Create threads by processing copies of all alocnos from BUCKET. We
+ process the most expensive copies first. */
+static void
+form_threads_from_bucket (ira_allocno_t bucket)
+{
+ ira_allocno_t a;
+ ira_copy_t cp, next_cp;
+ int cp_num = 0;
+
+ for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
+ {
+ for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
+ {
+ if (cp->first == a)
+ {
+ next_cp = cp->next_first_allocno_copy;
+ sorted_copies[cp_num++] = cp;
+ }
+ else if (cp->second == a)
+ next_cp = cp->next_second_allocno_copy;
+ else
+ gcc_unreachable ();
+ }
+ }
+ form_threads_from_copies (cp_num);
+}
+
+/* Create threads by processing copies of colorable allocno A. We
+ process most expensive copies first. */
+static void
+form_threads_from_colorable_allocno (ira_allocno_t a)
+{
+ ira_allocno_t another_a;
+ ira_copy_t cp, next_cp;
+ int cp_num = 0;
+
+ for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
+ {
+ if (cp->first == a)
+ {
+ next_cp = cp->next_first_allocno_copy;
+ another_a = cp->second;
+ }
+ else if (cp->second == a)
+ {
+ next_cp = cp->next_second_allocno_copy;
+ another_a = cp->first;
+ }
+ else
+ gcc_unreachable ();
+ if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
+ && !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
+ || ALLOCNO_COLOR_DATA (another_a)->colorable_p)
+ sorted_copies[cp_num++] = cp;
+ }
+ form_threads_from_copies (cp_num);
+}
+
+/* Form initial threads which contain only one allocno. */
+static void
+init_allocno_threads (void)
+{
+ ira_allocno_t a;
+ unsigned int j;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
+ {
+ a = ira_allocnos[j];
+ /* Set up initial thread data: */
+ ALLOCNO_COLOR_DATA (a)->first_thread_allocno
+ = ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
+ ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
+ }
+}
+
+\f
+
/* This page contains the allocator based on the Chaitin-Briggs algorithm. */
/* Bucket of allocnos that can colored currently without spilling. */
{
ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
- int diff, a1_freq, a2_freq, a1_num, a2_num;
+ int diff, freq1, freq2, a1_num, a2_num;
+ ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
+ ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
+ freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
+ freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
+ if ((diff = freq1 - freq2) != 0)
+ return diff;
+
+ if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
+ return diff;
+
/* Push pseudos requiring less hard registers first. It means that
we will assign pseudos requiring more hard registers first
avoiding creation small holes in free hard register file into
if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
- ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
return diff;
- a1_freq = ALLOCNO_FREQ (a1);
- a2_freq = ALLOCNO_FREQ (a2);
- if ((diff = a1_freq - a2_freq) != 0)
+
+ freq1 = ALLOCNO_FREQ (a1);
+ freq2 = ALLOCNO_FREQ (a2);
+ if ((diff = freq1 - freq2) != 0)
return diff;
+
a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
if ((diff = a2_num - a1_num) != 0)
*bucket_ptr = head;
}
-/* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
+/* Add ALLOCNO to colorable bucket maintaining the order according
their priority. ALLOCNO should be not in a bucket before the
call. */
static void
-add_allocno_to_ordered_bucket (ira_allocno_t allocno,
- ira_allocno_t *bucket_ptr)
+add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
{
ira_allocno_t before, after;
- if (bucket_ptr == &uncolorable_allocno_bucket
- && ALLOCNO_CLASS (allocno) != NO_REGS)
- {
- uncolorable_allocnos_num++;
- ira_assert (uncolorable_allocnos_num > 0);
- }
- for (before = *bucket_ptr, after = NULL;
+ form_threads_from_colorable_allocno (allocno);
+ for (before = colorable_allocno_bucket, after = NULL;
before != NULL;
after = before,
before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
if (after == NULL)
- *bucket_ptr = allocno;
+ colorable_allocno_bucket = allocno;
else
ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
if (before != NULL)
{
delete_allocno_from_bucket
(conflict_a, &uncolorable_allocno_bucket);
- add_allocno_to_ordered_bucket
- (conflict_a, &colorable_allocno_bucket);
+ add_allocno_to_ordered_colorable_bucket (conflict_a);
if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
{
fprintf (ira_dump_file, " Making");
static void
push_only_colorable (void)
{
+ form_threads_from_bucket (colorable_allocno_bucket);
sort_bucket (&colorable_allocno_bucket, bucket_allocno_compare_func);
for (;colorable_allocno_bucket != NULL;)
remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
calculate_allocno_spill_cost (ira_allocno_t a)
{
int regno, cost;
- enum machine_mode mode;
+ machine_mode mode;
enum reg_class rclass;
ira_allocno_t parent_allocno;
ira_loop_tree_node_t parent_node, loop_node;
{
int pri1, pri2, diff;
+ /* Avoid spilling static chain pointer pseudo when non-local goto is
+ used. */
+ if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
+ return 1;
+ else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
+ return -1;
if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
return 1;
if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
bool try_p;
enum reg_class aclass;
- enum machine_mode mode;
+ machine_mode mode;
int *allocno_costs;
int costs[FIRST_PSEUDO_REGISTER];
HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
ira_allocno_t a;
bitmap_iterator bi;
+ /* Don't bother to optimize the code with static chain pointer and
+ non-local goto in order not to spill the chain pointer
+ pseudo. */
+ if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
+ return;
/* Clear counts used to process conflicting allocnos only once for
each allocno. */
EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
int pri1, pri2;
+ /* Assign hard reg to static chain pointer pseudo first when
+ non-local goto is used. */
+ if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
+ return 1;
+ else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
+ return -1;
pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
if (pri2 != pri1)
\f
-/* Output information about the loop given by its LOOP_TREE_NODE. */
+/* Output information about the loop given by its LOOP_TREE_NODE. */
static void
print_loop_title (ira_loop_tree_node_t loop_tree_node)
{
{
fprintf (ira_dump_file, " %d", subloop_node->bb->index);
FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
- if (e->dest != EXIT_BLOCK_PTR
+ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
&& ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
!= loop_tree_node))
fprintf (ira_dump_file, "(->%d:l%d)",
int cost, exit_freq, enter_freq;
unsigned int j;
bitmap_iterator bi;
- enum machine_mode mode;
+ machine_mode mode;
enum reg_class rclass, aclass, pclass;
ira_allocno_t a, subloop_allocno;
ira_loop_tree_node_t subloop_node;
ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
n++;
}
+ init_allocno_threads ();
/* Color all mentioned allocnos including transparent ones. */
color_allocnos ();
/* Process caps. They are processed just once. */
ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
if (hard_regno >= 0)
- update_costs_from_copies (subloop_allocno, true);
- /* We don't need updated costs anymore: */
+ update_costs_from_copies (subloop_allocno, true, true);
+ /* We don't need updated costs anymore. */
ira_free_allocno_updated_costs (subloop_allocno);
}
}
ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
ALLOCNO_NUM (subloop_allocno)));
- if ((flag_ira_region == IRA_REGION_MIXED)
- && (loop_tree_node->reg_pressure[pclass]
- <= ira_class_hard_regs_num[pclass]))
+ if ((flag_ira_region == IRA_REGION_MIXED
+ && (loop_tree_node->reg_pressure[pclass]
+ <= ira_class_hard_regs_num[pclass]))
+ || (pic_offset_table_rtx != NULL
+ && regno == (int) REGNO (pic_offset_table_rtx))
+ /* Avoid overlapped multi-registers. Moves between them
+ might result in wrong code generation. */
+ || (hard_regno >= 0
+ && ira_reg_class_max_nregs[pclass][mode] > 1))
{
if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
{
ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
if (hard_regno >= 0)
- update_costs_from_copies (subloop_allocno, true);
- /* We don't need updated costs anymore: */
+ update_costs_from_copies (subloop_allocno, true, true);
+ /* We don't need updated costs anymore. */
ira_free_allocno_updated_costs (subloop_allocno);
}
continue;
ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
if (hard_regno >= 0)
- update_costs_from_copies (subloop_allocno, true);
- /* We don't need updated costs anymore: */
+ update_costs_from_copies (subloop_allocno, true, true);
+ /* We don't need updated costs anymore. */
ira_free_allocno_updated_costs (subloop_allocno);
}
}
}
}
ira_free (allocno_color_data);
- EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
+ EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
{
a = ira_allocnos[j];
ALLOCNO_ADD_DATA (a) = NULL;
int cost, regno, hard_regno, hard_regno2, index;
bool changed_p;
int enter_freq, exit_freq;
- enum machine_mode mode;
+ machine_mode mode;
enum reg_class rclass;
ira_allocno_t a, parent_allocno, subloop_allocno;
ira_loop_tree_node_t parent, loop_node, subloop_node;
by copy although the allocno will not get memory
slot. */
|| ira_equiv_no_lvalue_p (regno)
- || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
+ || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
+ /* Do not spill static chain pointer pseudo when
+ non-local goto is used. */
+ || non_spilled_static_chain_regno_p (regno))
continue;
mode = ALLOCNO_MODE (a);
rclass = ALLOCNO_CLASS (a);
update_curr_costs (ira_allocno_t a)
{
int i, hard_regno, cost;
- enum machine_mode mode;
+ machine_mode mode;
enum reg_class aclass, rclass;
ira_allocno_t another_a;
ira_copy_t cp, next_cp;
/* 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 allocno classes. */
-static bool
-allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
-{
- rtx reg1, reg2;
- int i, j;
- int n1 = ALLOCNO_NUM_OBJECTS (a1);
- int n2 = ALLOCNO_NUM_OBJECTS (a2);
-
- if (a1 == a2)
- return false;
- reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
- reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
- if (reg1 != NULL && reg2 != NULL
- && ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
- 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
ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
&& regno2 >= FIRST_PSEUDO_REGISTER);
- /* Reg info caclulated by dataflow infrastructure can be different
+ /* Reg info calculated 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)
/* Macro to access the data concerning coalescing. */
#define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
-/* 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). */
coalesce_allocnos (void)
{
ira_allocno_t a;
- ira_copy_t cp, next_cp, *sorted_copies;
+ ira_copy_t cp, next_cp;
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)
}
cp_num = n;
}
- ira_free (sorted_copies);
}
/* Usage cost and order number of coalesced allocno set to which
It is used for sorting pseudo registers. */
static unsigned int *regno_max_ref_width;
-/* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
-#ifdef STACK_GROWS_DOWNWARD
-# undef STACK_GROWS_DOWNWARD
-# define STACK_GROWS_DOWNWARD 1
-#else
-# define STACK_GROWS_DOWNWARD 0
-#endif
-
/* Sort pseudos according their slot numbers (putting ones with
smaller numbers first, or last when the frame pointer is not
needed). */
slot_num2 = -ALLOCNO_HARD_REGNO (a2);
if ((diff = slot_num1 - slot_num2) != 0)
return (frame_pointer_needed
- || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
+ || (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1),
regno_max_ref_width[regno1]);
total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2),
ira_allocno_iterator ai;
ira_allocno_t *spilled_coalesced_allocnos;
+ ira_assert (! ira_use_lra_p);
+
/* Set up allocnos can be coalesced. */
coloring_allocno_bitmap = ira_allocate_bitmap ();
for (i = 0; i < n; i++)
? ALLOCNO_CLASS_COST (a)
: ALLOCNO_HARD_REG_COSTS (a)
[ira_class_hard_reg_index[aclass][old_hard_regno]]);
- update_costs_from_copies (a, false);
+ update_costs_from_copies (a, false, false);
}
ira_overall_cost -= cost;
ALLOCNO_HARD_REGNO (a) = hard_regno;
? ALLOCNO_CLASS_COST (a)
: ALLOCNO_HARD_REG_COSTS (a)
[ira_class_hard_reg_index[aclass][hard_regno]]);
- update_costs_from_copies (a, true);
+ update_costs_from_copies (a, true, false);
}
else
/* Reload changed class of the allocno. */
bitmap_iterator bi;
struct ira_spilled_reg_stack_slot *slot = NULL;
+ ira_assert (! ira_use_lra_p);
+
ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
&& inherent_size <= total_size
&& ALLOCNO_HARD_REGNO (allocno) < 0);
int slot_num;
ira_allocno_t allocno;
+ ira_assert (! ira_use_lra_p);
+
ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
allocno = ira_regno_allocno_map[regno];
slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
CALL_USED_COUNT), and the first hard regno occupied by the
pseudo-registers (through FIRST_HARD_REGNO). */
static int
-calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
+calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
int *excess_pressure_live_length,
int *nrefs, int *call_used_count, int *first_hard_regno)
{
decisions. */
bool
ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
- rtx in, rtx out, rtx insn)
+ rtx in, rtx out, rtx_insn *insn)
{
int cost, other_cost;
int length, other_length;
consideration_allocno_bitmap = ira_allocate_bitmap ();
initiate_cost_update ();
allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
+ sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
+ * sizeof (ira_copy_t));
}
/* Deallocate data used by assign_hard_reg. */
ira_free_bitmap (consideration_allocno_bitmap);
finish_cost_update ();
ira_free (allocno_priorities);
+ ira_free (sorted_copies);
}
\f
bool no_stack_reg_p;
#endif
enum reg_class aclass;
- enum machine_mode mode;
+ machine_mode mode;
ira_allocno_t a;
ira_allocno_iterator ai;
live_range_t r;
projects / gcc.git / blobdiff