/* IRA allocation based on graph coloring.
- Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012
- 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 "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;
allocno_hard_regs_node_t parent, first, prev, next;
};
+/* Info about changing hard reg costs of an allocno. */
+struct update_cost_record
+{
+ /* Hard regno for which we changed the cost. */
+ int hard_regno;
+ /* Divisor used when we changed the cost of HARD_REGNO. */
+ int divisor;
+ /* Next record for given allocno. */
+ struct update_cost_record *next;
+};
+
/* To decrease footprint of ira_allocno structure we store all data
needed only for coloring in the following structure. */
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. */
static ira_allocno_t *sorted_allocnos;
/* Vec representing the stack of allocnos used during coloring. */
-static VEC(ira_allocno_t,heap) *allocno_stack_vec;
+static vec<ira_allocno_t> allocno_stack_vec;
/* Helper for qsort comparison callbacks - return a positive integer if
X > Y, or a negative value otherwise. Use a conditional expression
\f
/* Definition of vector of allocno hard registers. */
-DEF_VEC_P(allocno_hard_regs_t);
-DEF_VEC_ALLOC_P(allocno_hard_regs_t, heap);
/* Vector of unique allocno hard registers. */
-static VEC(allocno_hard_regs_t, heap) *allocno_hard_regs_vec;
+static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
-/* Returns hash value for allocno hard registers V. */
-static hashval_t
-allocno_hard_regs_hash (const void *v)
+struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
{
- const struct allocno_hard_regs *hv = (const struct allocno_hard_regs *) v;
+ 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 allocno_hard_regs *hv)
+{
return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
}
/* Compares allocno hard registers V1 and V2. */
-static int
-allocno_hard_regs_eq (const void *v1, const void *v2)
+inline bool
+allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
+ const allocno_hard_regs *hv2)
{
- const struct allocno_hard_regs *hv1 = (const struct allocno_hard_regs *) v1;
- const struct allocno_hard_regs *hv2 = (const struct allocno_hard_regs *) v2;
-
return hard_reg_set_equal_p (hv1->set, hv2->set);
}
/* Hash table of unique allocno hard registers. */
-static htab_t 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_t) htab_find (allocno_hard_regs_htab, 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)
{
- PTR *slot = htab_find_slot (allocno_hard_regs_htab, hv, INSERT);
+ allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
if (*slot == NULL)
*slot = hv;
- return (allocno_hard_regs_t) *slot;
+ return *slot;
}
/* Initialize data concerning allocno hard registers. */
static void
init_allocno_hard_regs (void)
{
- allocno_hard_regs_vec = VEC_alloc (allocno_hard_regs_t, heap, 200);
+ allocno_hard_regs_vec.create (200);
allocno_hard_regs_htab
- = htab_create (200, allocno_hard_regs_hash, allocno_hard_regs_eq, NULL);
+ = 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;
ira_allocate (sizeof (struct allocno_hard_regs)));
COPY_HARD_REG_SET (hv->set, set);
hv->cost = cost;
- VEC_safe_push (allocno_hard_regs_t, heap, allocno_hard_regs_vec, hv);
+ allocno_hard_regs_vec.safe_push (hv);
insert_hard_regs (hv);
}
return hv;
allocno_hard_regs_t hv;
for (i = 0;
- VEC_iterate (allocno_hard_regs_t, allocno_hard_regs_vec, i, hv);
+ allocno_hard_regs_vec.iterate (i, &hv);
i++)
ira_free (hv);
- htab_delete (allocno_hard_regs_htab);
- VEC_free (allocno_hard_regs_t, heap, allocno_hard_regs_vec);
+ delete allocno_hard_regs_htab;
+ allocno_hard_regs_htab = NULL;
+ allocno_hard_regs_vec.release ();
}
/* Sort hard regs according to their frequency of usage. */
static allocno_hard_regs_node_t hard_regs_roots;
/* Definition of vector of allocno hard register nodes. */
-DEF_VEC_P(allocno_hard_regs_node_t);
-DEF_VEC_ALLOC_P(allocno_hard_regs_node_t, heap);
/* Vector used to create the forest. */
-static VEC(allocno_hard_regs_node_t, heap) *hard_regs_node_vec;
+static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
/* Create and return allocno hard registers node containing allocno
hard registers HV. */
HARD_REG_SET temp_set;
allocno_hard_regs_t hv2;
- start = VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec);
+ start = hard_regs_node_vec.length ();
for (node = *roots; node != NULL; node = node->next)
{
if (hard_reg_set_equal_p (hv->set, node->hard_regs->set))
return;
}
if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
- VEC_safe_push (allocno_hard_regs_node_t, heap,
- hard_regs_node_vec, node);
+ hard_regs_node_vec.safe_push (node);
else if (hard_reg_set_intersect_p (hv->set, node->hard_regs->set))
{
COPY_HARD_REG_SET (temp_set, hv->set);
add_allocno_hard_regs_to_forest (&node->first, hv2);
}
}
- if (VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec)
+ if (hard_regs_node_vec.length ()
> start + 1)
{
/* Create a new node which contains nodes in hard_regs_node_vec. */
CLEAR_HARD_REG_SET (temp_set);
for (i = start;
- i < VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec);
+ i < hard_regs_node_vec.length ();
i++)
{
- node = VEC_index (allocno_hard_regs_node_t, hard_regs_node_vec, i);
+ node = hard_regs_node_vec[i];
IOR_HARD_REG_SET (temp_set, node->hard_regs->set);
}
hv = add_allocno_hard_regs (temp_set, hv->cost);
new_node = create_new_allocno_hard_regs_node (hv);
prev = NULL;
for (i = start;
- i < VEC_length (allocno_hard_regs_node_t, hard_regs_node_vec);
+ i < hard_regs_node_vec.length ();
i++)
{
- node = VEC_index (allocno_hard_regs_node_t, hard_regs_node_vec, i);
+ node = hard_regs_node_vec[i];
if (node->prev == NULL)
*roots = node->next;
else
}
add_new_allocno_hard_regs_node_to_forest (roots, new_node);
}
- VEC_truncate (allocno_hard_regs_node_t, hard_regs_node_vec, start);
+ hard_regs_node_vec.truncate (start);
}
/* Add allocno hard registers nodes starting with the forest level
ira_assert (first != NULL);
for (node = first; node != NULL; node = node->next)
if (hard_reg_set_subset_p (node->hard_regs->set, set))
- VEC_safe_push (allocno_hard_regs_node_t, heap, hard_regs_node_vec,
- node);
+ hard_regs_node_vec.safe_push (node);
else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
collect_allocno_hard_regs_cover (node->first, set);
}
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);
}
}
node_check_tick = 0;
init_allocno_hard_regs ();
hard_regs_roots = NULL;
- hard_regs_node_vec = VEC_alloc (allocno_hard_regs_node_t, heap, 100);
+ hard_regs_node_vec.create (100);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
{
node = create_new_allocno_hard_regs_node (hv);
add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
}
- start = VEC_length (allocno_hard_regs_t, allocno_hard_regs_vec);
+ start = allocno_hard_regs_vec.length ();
EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
a = ira_allocnos[i];
SET_HARD_REG_SET (temp);
AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
add_allocno_hard_regs (temp, 0);
- qsort (VEC_address (allocno_hard_regs_t, allocno_hard_regs_vec) + start,
- VEC_length (allocno_hard_regs_t, allocno_hard_regs_vec) - start,
+ qsort (allocno_hard_regs_vec.address () + start,
+ allocno_hard_regs_vec.length () - start,
sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
for (i = start;
- VEC_iterate (allocno_hard_regs_t, allocno_hard_regs_vec, i, hv);
+ allocno_hard_regs_vec.iterate (i, &hv);
i++)
{
add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
- ira_assert (VEC_length (allocno_hard_regs_node_t,
- hard_regs_node_vec) == 0);
+ ira_assert (hard_regs_node_vec.length () == 0);
}
/* We need to set up parent fields for right work of
first_common_ancestor_node. */
allocno_data = ALLOCNO_COLOR_DATA (a);
if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
continue;
- VEC_truncate (allocno_hard_regs_node_t, hard_regs_node_vec, 0);
+ hard_regs_node_vec.truncate (0);
collect_allocno_hard_regs_cover (hard_regs_roots,
allocno_data->profitable_hard_regs);
allocno_hard_regs_node = NULL;
- for (j = 0;
- VEC_iterate (allocno_hard_regs_node_t, hard_regs_node_vec,
- j, node);
- j++)
+ for (j = 0; hard_regs_node_vec.iterate (j, &node); j++)
allocno_hard_regs_node
= (j == 0
? node
allocno_hard_regs_subnodes
= ((allocno_hard_regs_subnode_t)
ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
- VEC_free (allocno_hard_regs_node_t, heap, hard_regs_node_vec);
+ hard_regs_node_vec.release ();
}
/* Free tree of allocno hard registers nodes given by its ROOT. */
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
{
+ mode = ALLOCNO_MODE (a);
COPY_HARD_REG_SET (data->profitable_hard_regs,
- reg_class_contents[aclass]);
- AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
- ira_no_alloc_regs);
+ ira_useful_class_mode_regs[aclass][mode]);
nobj = ALLOCNO_NUM_OBJECTS (a);
for (k = 0; k < nobj; k++)
{
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;
/* This page contains functions used to choose hard registers for
allocnos. */
+/* Pool for update cost records. */
+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 *
+get_update_cost_record (int hard_regno, int divisor,
+ struct update_cost_record *next)
+{
+ struct update_cost_record *record;
+
+ record = update_cost_record_pool.allocate ();
+ record->hard_regno = hard_regno;
+ record->divisor = divisor;
+ record->next = next;
+ return record;
+}
+
+/* Free memory for all records in LIST. */
+static void
+free_update_cost_record_list (struct update_cost_record *list)
+{
+ struct update_cost_record *next;
+
+ while (list != NULL)
+ {
+ next = list->next;
+ update_cost_record_pool.remove (list);
+ list = next;
+ }
+}
+
+/* Free memory allocated for all update cost records. */
+static void
+finish_update_cost_records (void)
+{
+ update_cost_record_pool.release ();
+}
+
/* Array whose element value is TRUE if the corresponding hard
register was already allocated for an allocno. */
static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
connecting this allocno to the one being allocated. */
int divisor;
+ /* 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;
+
/* The next allocno in the queue, or null if this is the last element. */
ira_allocno_t next;
};
Elements are indexed by ALLOCNO_NUM. */
static struct update_cost_queue_elem *update_cost_queue_elems;
-/* The current value of update_copy_cost call count. */
+/* The current value of update_costs_from_copies call count. */
static int update_cost_check;
/* Allocate and initialize data necessary for function
- update_copy_costs. */
+ update_costs_from_copies. */
static void
initiate_cost_update (void)
{
update_cost_check = 0;
}
-/* Deallocate data used by function update_copy_costs. */
+/* Deallocate data used by function update_costs_from_copies. */
static void
finish_cost_update (void)
{
ira_free (update_cost_queue_elems);
+ finish_update_cost_records ();
}
/* When we traverse allocnos to update hard register costs, the cost
update_cost_queue = NULL;
}
-/* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue, unless
+/* Add (ALLOCNO, 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, int divisor)
+queue_update_cost (ira_allocno_t allocno, ira_allocno_t from, int divisor)
{
struct update_cost_queue_elem *elem;
&& ALLOCNO_CLASS (allocno) != NO_REGS)
{
elem->check = update_cost_check;
+ elem->from = from;
elem->divisor = divisor;
elem->next = NULL;
if (update_cost_queue == NULL)
}
}
-/* Try to remove the first element from update_cost_queue. Return false
- if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
- the removed element. */
+/* 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. */
static inline bool
-get_next_update_cost (ira_allocno_t *allocno, int *divisor)
+get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *from, int *divisor)
{
struct update_cost_queue_elem *elem;
*allocno = update_cost_queue;
elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
+ *from = elem->from;
*divisor = elem->divisor;
update_cost_queue = elem->next;
return true;
}
-/* Update the cost of allocnos to increase chances to remove some
- copies as the result of subsequent assignment. */
+/* Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return
+ true if we really modified the cost. */
+static bool
+update_allocno_cost (ira_allocno_t allocno, int hard_regno, int update_cost)
+{
+ int i;
+ enum reg_class aclass = ALLOCNO_CLASS (allocno);
+
+ i = ira_class_hard_reg_index[aclass][hard_regno];
+ if (i < 0)
+ return false;
+ ira_allocate_and_set_or_copy_costs
+ (&ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
+ ALLOCNO_UPDATED_CLASS_COST (allocno),
+ ALLOCNO_HARD_REG_COSTS (allocno));
+ ira_allocate_and_set_or_copy_costs
+ (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
+ aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
+ ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
+ ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_cost;
+ return true;
+}
+
+/* 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. */
static void
-update_copy_costs (ira_allocno_t allocno, bool decr_p)
+update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
+ int divisor, bool decr_p, bool record_p)
{
- int i, cost, update_cost, hard_regno, divisor;
- enum machine_mode mode;
+ int cost, update_cost;
+ machine_mode mode;
enum reg_class rclass, aclass;
- ira_allocno_t another_allocno;
+ ira_allocno_t another_allocno, from = NULL;
ira_copy_t cp, next_cp;
- hard_regno = ALLOCNO_HARD_REGNO (allocno);
- ira_assert (hard_regno >= 0);
-
- aclass = ALLOCNO_CLASS (allocno);
- if (aclass == NO_REGS)
- return;
- i = ira_class_hard_reg_index[aclass][hard_regno];
- ira_assert (i >= 0);
rclass = REGNO_REG_CLASS (hard_regno);
-
- start_update_cost ();
- divisor = 1;
do
{
mode = ALLOCNO_MODE (allocno);
else
gcc_unreachable ();
+ if (another_allocno == from)
+ continue;
+
aclass = ALLOCNO_CLASS (another_allocno);
if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
hard_regno)
if (update_cost == 0)
continue;
- ira_allocate_and_set_or_copy_costs
- (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), aclass,
- ALLOCNO_UPDATED_CLASS_COST (another_allocno),
- ALLOCNO_HARD_REG_COSTS (another_allocno));
- ira_allocate_and_set_or_copy_costs
- (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
- aclass, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
- i = ira_class_hard_reg_index[aclass][hard_regno];
- if (i < 0)
+ if (! update_allocno_cost (another_allocno, hard_regno, update_cost))
continue;
- ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
- ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
- += update_cost;
-
- queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
+ queue_update_cost (another_allocno, 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,
+ ALLOCNO_COLOR_DATA (another_allocno)
+ ->update_cost_records);
}
}
- while (get_next_update_cost (&allocno, &divisor));
+ while (get_next_update_cost (&allocno, &from, &divisor));
+}
+
+/* Decrease preferred ALLOCNO hard register costs and costs of
+ allocnos connected to ALLOCNO through copy. */
+static void
+update_costs_from_prefs (ira_allocno_t allocno)
+{
+ ira_pref_t pref;
+
+ 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);
+}
+
+/* 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. Record cost updates if RECORD_P is true. */
+static void
+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, record_p);
+}
+
+/* Restore costs of allocnos connected to ALLOCNO by copies as it was
+ before updating costs of these allocnos from given allocno. This
+ is a wise thing to do as if given allocno did not get an expected
+ hard reg, using smaller cost of the hard reg for allocnos connected
+ by copies to given allocno becomes actually misleading. Free all
+ update cost records for ALLOCNO as we don't need them anymore. */
+static void
+restore_costs_from_copies (ira_allocno_t allocno)
+{
+ struct update_cost_record *records, *curr;
+
+ if (ALLOCNO_COLOR_DATA (allocno) == NULL)
+ return;
+ records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
+ start_update_cost ();
+ for (curr = records; curr != NULL; curr = curr->next)
+ update_costs_from_allocno (allocno, curr->hard_regno,
+ curr->divisor, true, false);
+ free_update_cost_record_list (records);
+ ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
}
/* This function updates COSTS (decrease if DECR_P) for hard_registers
int *conflict_costs;
bool cont_p;
enum reg_class another_aclass;
- ira_allocno_t allocno, another_allocno;
+ ira_allocno_t allocno, another_allocno, from;
ira_copy_t cp, next_cp;
- while (get_next_update_cost (&allocno, &divisor))
+ while (get_next_update_cost (&allocno, &from, &divisor))
for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
{
if (cp->first == allocno)
}
else
gcc_unreachable ();
+
+ if (another_allocno == from)
+ continue;
+
another_aclass = ALLOCNO_CLASS (another_allocno);
if (! ira_reg_classes_intersect_p[aclass][another_aclass]
|| ALLOCNO_ASSIGNED_P (another_allocno)
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;
* COST_HOP_DIVISOR
* COST_HOP_DIVISOR
* COST_HOP_DIVISOR))
- queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
+ queue_update_cost (another_allocno, allocno, divisor * COST_HOP_DIVISOR);
}
}
{
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];
}
- queue_update_cost (conflict_a, COST_HOP_DIVISOR);
+ queue_update_cost (conflict_a, NULL, COST_HOP_DIVISOR);
+
}
}
}
if (! retry_p)
{
start_update_cost ();
- queue_update_cost (a, COST_HOP_DIVISOR);
+ queue_update_cost (a, NULL, COST_HOP_DIVISOR);
update_conflict_hard_regno_costs (full_costs, aclass, false);
}
min_cost = min_full_cost = INT_MAX;
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;
}
+ 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_copy_costs (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)
data = ALLOCNO_COLOR_DATA (a);
data->in_graph_p = false;
- VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
+ allocno_stack_vec.safe_push (a);
aclass = ALLOCNO_CLASS (a);
if (aclass == NO_REGS)
return;
{
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);
int freq, i;
edge_iterator ei;
edge e;
- VEC (edge, heap) *edges;
+ vec<edge> edges;
ira_assert (current_loops != NULL && loop_node->loop != NULL
&& (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
if (e->src != loop_node->loop->latch
&& (regno < 0
- || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
- && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
+ || (bitmap_bit_p (df_get_live_out (e->src), regno)
+ && bitmap_bit_p (df_get_live_in (e->dest), regno))))
freq += EDGE_FREQUENCY (e);
}
else
{
edges = get_loop_exit_edges (loop_node->loop);
- FOR_EACH_VEC_ELT (edge, edges, i, e)
+ FOR_EACH_VEC_ELT (edges, i, e)
if (regno < 0
- || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
- && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
+ || (bitmap_bit_p (df_get_live_out (e->src), regno)
+ && bitmap_bit_p (df_get_live_in (e->dest), regno)))
freq += EDGE_FREQUENCY (e);
- VEC_free (edge, heap, edges);
+ edges.release ();
}
return REG_FREQ_FROM_EDGE_FREQ (freq);
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))
ira_allocno_t allocno;
enum reg_class aclass;
- for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
+ for (;allocno_stack_vec.length () != 0;)
{
- allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
+ allocno = allocno_stack_vec.pop ();
aclass = ALLOCNO_CLASS (allocno);
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
{
else if (ALLOCNO_ASSIGNED_P (allocno))
{
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
- fprintf (ira_dump_file, "spill\n");
+ fprintf (ira_dump_file, "spill%s\n",
+ ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
+ ? "" : "!");
}
ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
}
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)
}
}
-/* Sort allocnos according to their priorities which are calculated
- analogous to ones in file `global.c'. */
+/* Sort allocnos according to their priorities. */
static int
allocno_priority_compare_func (const void *v1p, const void *v2p)
{
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)
ira_allocno_t a;
setup_profitable_hard_regs ();
+ EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
+ {
+ int l, nr;
+ HARD_REG_SET conflict_hard_regs;
+ allocno_color_data_t data;
+ ira_pref_t pref, next_pref;
+
+ a = ira_allocnos[i];
+ 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));
+ }
+ data = ALLOCNO_COLOR_DATA (a);
+ for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
+ {
+ next_pref = pref->next_pref;
+ if (! ira_hard_reg_in_set_p (pref->hard_regno,
+ ALLOCNO_MODE (a),
+ data->profitable_hard_regs))
+ ira_remove_pref (pref);
+ }
+ }
if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
{
n = 0;
{
a = ira_allocnos[i];
if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
- ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
+ {
+ ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
+ update_costs_from_prefs (a);
+ }
else
{
ALLOCNO_HARD_REGNO (a) = -1;
\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. */
pclass = ira_pressure_class_translate[rclass];
if (flag_ira_region == IRA_REGION_MIXED
&& (loop_tree_node->reg_pressure[pclass]
- <= ira_available_class_regs[pclass]))
+ <= ira_class_hard_regs_num[pclass]))
{
mode = ALLOCNO_MODE (a);
hard_regno = ALLOCNO_HARD_REGNO (a);
ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
if (hard_regno >= 0)
- update_copy_costs (subloop_allocno, true);
- /* We don't need updated costs anymore: */
+ 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_available_class_regs[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_copy_costs (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;
exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
ira_assert (regno < ira_reg_equiv_len);
- if (ira_reg_equiv_invariant_p[regno]
- || ira_reg_equiv_const[regno] != NULL_RTX)
+ if (ira_equiv_no_lvalue_p (regno))
{
if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
{
ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
if (hard_regno >= 0)
- update_copy_costs (subloop_allocno, true);
- /* We don't need updated costs anymore: */
+ 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;
copies and the reload pass can spill the allocno set
by copy although the allocno will not get memory
slot. */
- || (regno < ira_reg_equiv_len
- && (ira_reg_equiv_invariant_p[regno]
- || ira_reg_equiv_const[regno] != NULL_RTX))
- || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
+ || ira_equiv_no_lvalue_p (regno)
+ || !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)
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])))
+ || ira_equiv_no_lvalue_p (regno))
continue;
for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
{
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)))
+ && ! ira_equiv_no_lvalue_p (regno))
sorted_copies[cp_num++] = cp;
}
else if (cp->second == a)
}
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),
allocno = spilled_coalesced_allocnos[i];
if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
|| bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
- || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
- && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
- || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
+ || ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
continue;
for (j = 0; j < i; j++)
{
n = ALLOCNO_COALESCE_DATA (a)->temp;
if (ALLOCNO_COALESCE_DATA (a)->first == 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))
+ && ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
&& ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
break;
}
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 = spilled_coalesced_allocnos[i];
if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
|| ALLOCNO_HARD_REGNO (allocno) >= 0
- || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
- && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
- || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
+ || ira_equiv_no_lvalue_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_CLASS_COST (a)
: ALLOCNO_HARD_REG_COSTS (a)
[ira_class_hard_reg_index[aclass][old_hard_regno]]);
- update_copy_costs (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_copy_costs (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
static void
color (void)
{
- allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
+ allocno_stack_vec.create (ira_allocnos_num);
memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
ira_initiate_assign ();
do_coloring ();
ira_finish_assign ();
- VEC_free (ira_allocno_t, heap, allocno_stack_vec);
+ allocno_stack_vec.release ();
move_spill_restore ();
}
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;