/* IRA allocation based on graph coloring.
- Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
- 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 object_hard_regs *object_hard_regs_t;
+typedef struct allocno_hard_regs *allocno_hard_regs_t;
/* The structure contains information about hard registers can be
- assigned to objects. Usually it is allocno profitable hard
+ assigned to allocnos. Usually it is allocno profitable hard
registers but in some cases this set can be a bit different. Major
reason of the difference is a requirement to use hard register sets
that form a tree or a forest (set of trees), i.e. hard register set
of a node should contain hard register sets of its subnodes. */
-struct object_hard_regs
+struct allocno_hard_regs
{
/* Hard registers can be assigned to an allocno. */
HARD_REG_SET set;
/* Overall (spilling) cost of all allocnos with given register
set. */
- long long int cost;
+ int64_t cost;
};
-typedef struct object_hard_regs_node *object_hard_regs_node_t;
+typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
-/* A node representing object hard registers. Such nodes form a
+/* A node representing allocno hard registers. Such nodes form a
forest (set of trees). Each subnode of given node in the forest
- refers for hard register set (usually object profitable hard
+ refers for hard register set (usually allocno profitable hard
register set) which is a subset of one referred from given
node. */
-struct object_hard_regs_node
+struct allocno_hard_regs_node
{
/* Set up number of the node in preorder traversing of the forest. */
int preorder_num;
allocno. */
int check;
/* Used for calculation of conflict size of an allocno. The
- conflict size of the allocno is maximal number of given object
+ conflict size of the allocno is maximal number of given allocno
hard registers needed for allocation of the conflicting allocnos.
Given allocno is trivially colored if this number plus the number
of hard registers needed for given allocno is not greater than
/* The following member is used to form the final forest. */
bool used_p;
/* Pointer to the corresponding profitable hard registers. */
- object_hard_regs_t hard_regs;
+ allocno_hard_regs_t hard_regs;
/* Parent, first subnode, previous and next node with the same
parent in the forest. */
- object_hard_regs_node_t parent, first, prev, next;
+ 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
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. */
unsigned int may_be_spilled_p : 1;
- /* TRUE if the object is trivially colorable. */
+ /* TRUE if the allocno is trivially colorable. */
unsigned int colorable_p : 1;
/* Number of hard registers of the allocno class really
available for the allocno allocation. It is number of the
ira_allocno_t prev_bucket_allocno;
/* Used for temporary purposes. */
int temp;
-};
-
-/* See above. */
-typedef struct allocno_color_data *allocno_color_data_t;
-
-/* Container for storing allocno data concerning coloring. */
-static allocno_color_data_t allocno_color_data;
-
-/* Macro to access the data concerning coloring. */
-#define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
-
-/* To decrease footprint of ira_object structure we store all data
- needed only for coloring in the following structure. */
-struct object_color_data
-{
+ /* Used to exclude repeated processing. */
+ int last_process;
/* Profitable hard regs available for this pseudo allocation. It
means that the set excludes unavailable hard regs and hard regs
conflicting with given pseudo. They should be of the allocno
class. */
HARD_REG_SET profitable_hard_regs;
- /* The object hard registers node. */
- object_hard_regs_node_t hard_regs_node;
- /* Array of structures object_hard_regs_subnode representing
- given object hard registers node (the 1st element in the array)
- and all its subnodes in the tree (forest) of object hard
+ /* The allocno hard registers node. */
+ allocno_hard_regs_node_t hard_regs_node;
+ /* Array of structures allocno_hard_regs_subnode representing
+ given allocno hard registers node (the 1st element in the array)
+ 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. */
-typedef struct object_color_data *object_color_data_t;
+typedef struct allocno_color_data *allocno_color_data_t;
-/* Container for storing object data concerning coloring. */
-static object_color_data_t object_color_data;
+/* Container for storing allocno data concerning coloring. */
+static allocno_color_data_t allocno_color_data;
/* Macro to access the data concerning coloring. */
-#define OBJECT_COLOR_DATA(o) ((object_color_data_t) OBJECT_ADD_DATA (o))
+#define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
+
+/* Used for finding allocno colorability to exclude repeated allocno
+ processing and for updating preferencing to exclude repeated
+ allocno processing during assignment. */
+static int curr_allocno_process;
/* This file contains code for regional graph coloring, spill/restore
code placement optimization, and code helping the reload pass to do
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 object hard registers. */
-DEF_VEC_P(object_hard_regs_t);
-DEF_VEC_ALLOC_P(object_hard_regs_t, heap);
+/* Definition of vector of allocno hard registers. */
-/* Vector of unique object hard registers. */
-static VEC(object_hard_regs_t, heap) *object_hard_regs_vec;
+/* Vector of unique allocno hard registers. */
+static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
-/* Returns hash value for object hard registers V. */
-static hashval_t
-object_hard_regs_hash (const void *v)
+struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
{
- const struct object_hard_regs *hv = (const struct object_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 object hard registers V1 and V2. */
-static int
-object_hard_regs_eq (const void *v1, const void *v2)
+/* Compares allocno hard registers V1 and V2. */
+inline bool
+allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
+ const allocno_hard_regs *hv2)
{
- const struct object_hard_regs *hv1 = (const struct object_hard_regs *) v1;
- const struct object_hard_regs *hv2 = (const struct object_hard_regs *) v2;
-
return hard_reg_set_equal_p (hv1->set, hv2->set);
}
-/* Hash table of unique object hard registers. */
-static htab_t object_hard_regs_htab;
+/* Hash table of unique allocno hard registers. */
+static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
-/* Return object hard registers in the hash table equal to HV. */
-static object_hard_regs_t
-find_hard_regs (object_hard_regs_t hv)
+/* 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 (object_hard_regs_t) htab_find (object_hard_regs_htab, hv);
+ return allocno_hard_regs_htab->find (hv);
}
/* Insert allocno hard registers HV in the hash table (if it is not
there yet) and return the value which in the table. */
-static object_hard_regs_t
-insert_hard_regs (object_hard_regs_t hv)
+static allocno_hard_regs_t
+insert_hard_regs (allocno_hard_regs_t hv)
{
- PTR *slot = htab_find_slot (object_hard_regs_htab, hv, INSERT);
+ allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (hv, INSERT);
if (*slot == NULL)
*slot = hv;
- return (object_hard_regs_t) *slot;
+ return *slot;
}
-/* Initialize data concerning object hard registers. */
+/* Initialize data concerning allocno hard registers. */
static void
-init_object_hard_regs (void)
+init_allocno_hard_regs (void)
{
- object_hard_regs_vec = VEC_alloc (object_hard_regs_t, heap, 200);
- object_hard_regs_htab
- = htab_create (200, object_hard_regs_hash, object_hard_regs_eq, NULL);
+ allocno_hard_regs_vec.create (200);
+ allocno_hard_regs_htab
+ = new hash_table<allocno_hard_regs_hasher> (200);
}
-/* Add (or update info about) object hard registers with SET and
+/* Add (or update info about) allocno hard registers with SET and
COST. */
-static object_hard_regs_t
-add_object_hard_regs (HARD_REG_SET set, long long int cost)
+static allocno_hard_regs_t
+add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
{
- struct object_hard_regs temp;
- object_hard_regs_t hv;
+ struct allocno_hard_regs temp;
+ allocno_hard_regs_t hv;
gcc_assert (! hard_reg_set_empty_p (set));
COPY_HARD_REG_SET (temp.set, set);
hv->cost += cost;
else
{
- hv = ((struct object_hard_regs *)
- ira_allocate (sizeof (struct object_hard_regs)));
+ hv = ((struct allocno_hard_regs *)
+ ira_allocate (sizeof (struct allocno_hard_regs)));
COPY_HARD_REG_SET (hv->set, set);
hv->cost = cost;
- VEC_safe_push (object_hard_regs_t, heap, object_hard_regs_vec, hv);
+ allocno_hard_regs_vec.safe_push (hv);
insert_hard_regs (hv);
}
return hv;
/* Finalize data concerning allocno hard registers. */
static void
-finish_object_hard_regs (void)
+finish_allocno_hard_regs (void)
{
int i;
- object_hard_regs_t hv;
+ allocno_hard_regs_t hv;
for (i = 0;
- VEC_iterate (object_hard_regs_t, object_hard_regs_vec, i, hv);
+ allocno_hard_regs_vec.iterate (i, &hv);
i++)
ira_free (hv);
- htab_delete (object_hard_regs_htab);
- VEC_free (object_hard_regs_t, heap, object_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 int
-object_hard_regs_compare (const void *v1p, const void *v2p)
+allocno_hard_regs_compare (const void *v1p, const void *v2p)
{
- object_hard_regs_t hv1 = *(const object_hard_regs_t *) v1p;
- object_hard_regs_t hv2 = *(const object_hard_regs_t *) v2p;
+ allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
+ allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
if (hv2->cost > hv1->cost)
return 1;
static int node_check_tick;
/* Roots of the forest containing hard register sets can be assigned
- to objects. */
-static object_hard_regs_node_t hard_regs_roots;
+ to allocnos. */
+static allocno_hard_regs_node_t hard_regs_roots;
-/* Definition of vector of object hard register nodes. */
-DEF_VEC_P(object_hard_regs_node_t);
-DEF_VEC_ALLOC_P(object_hard_regs_node_t, heap);
+/* Definition of vector of allocno hard register nodes. */
/* Vector used to create the forest. */
-static VEC(object_hard_regs_node_t, heap) *hard_regs_node_vec;
+static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
-/* Create and return object hard registers node containing object
+/* Create and return allocno hard registers node containing allocno
hard registers HV. */
-static object_hard_regs_node_t
-create_new_object_hard_regs_node (object_hard_regs_t hv)
+static allocno_hard_regs_node_t
+create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
{
- object_hard_regs_node_t new_node;
+ allocno_hard_regs_node_t new_node;
- new_node = ((struct object_hard_regs_node *)
- ira_allocate (sizeof (struct object_hard_regs_node)));
+ new_node = ((struct allocno_hard_regs_node *)
+ ira_allocate (sizeof (struct allocno_hard_regs_node)));
new_node->check = 0;
new_node->hard_regs = hv;
new_node->hard_regs_num = hard_reg_set_size (hv->set);
return new_node;
}
-/* Add object hard registers node NEW_NODE to the forest on its level
+/* Add allocno hard registers node NEW_NODE to the forest on its level
given by ROOTS. */
static void
-add_new_object_hard_regs_node_to_forest (object_hard_regs_node_t *roots,
- object_hard_regs_node_t new_node)
+add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
+ allocno_hard_regs_node_t new_node)
{
new_node->next = *roots;
if (new_node->next != NULL)
*roots = new_node;
}
-/* Add object hard registers HV (or its best approximation if it is
+/* Add allocno hard registers HV (or its best approximation if it is
not possible) to the forest on its level given by ROOTS. */
static void
-add_object_hard_regs_to_forest (object_hard_regs_node_t *roots,
- object_hard_regs_t hv)
+add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
+ allocno_hard_regs_t hv)
{
unsigned int i, start;
- object_hard_regs_node_t node, prev, new_node;
+ allocno_hard_regs_node_t node, prev, new_node;
HARD_REG_SET temp_set;
- object_hard_regs_t hv2;
+ allocno_hard_regs_t hv2;
- start = VEC_length (object_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 (hv->set, node->hard_regs->set))
{
- add_object_hard_regs_to_forest (&node->first, hv);
+ add_allocno_hard_regs_to_forest (&node->first, hv);
return;
}
if (hard_reg_set_subset_p (node->hard_regs->set, hv->set))
- VEC_safe_push (object_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);
AND_HARD_REG_SET (temp_set, node->hard_regs->set);
- hv2 = add_object_hard_regs (temp_set, hv->cost);
- add_object_hard_regs_to_forest (&node->first, hv2);
+ hv2 = add_allocno_hard_regs (temp_set, hv->cost);
+ add_allocno_hard_regs_to_forest (&node->first, hv2);
}
}
- if (VEC_length (object_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 (object_hard_regs_node_t, hard_regs_node_vec);
+ i < hard_regs_node_vec.length ();
i++)
{
- node = VEC_index (object_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_object_hard_regs (temp_set, hv->cost);
- new_node = create_new_object_hard_regs_node (hv);
+ 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 (object_hard_regs_node_t, hard_regs_node_vec);
+ i < hard_regs_node_vec.length ();
i++)
{
- node = VEC_index (object_hard_regs_node_t, hard_regs_node_vec, i);
+ node = hard_regs_node_vec[i];
if (node->prev == NULL)
*roots = node->next;
else
node->next = NULL;
prev = node;
}
- add_new_object_hard_regs_node_to_forest (roots, new_node);
+ add_new_allocno_hard_regs_node_to_forest (roots, new_node);
}
- VEC_truncate (object_hard_regs_node_t, hard_regs_node_vec, start);
+ hard_regs_node_vec.truncate (start);
}
-/* Add object hard registers nodes starting with the forest level
+/* Add allocno hard registers nodes starting with the forest level
given by FIRST which contains biggest set inside SET. */
static void
-collect_object_hard_regs_cover (object_hard_regs_node_t first,
+collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
HARD_REG_SET set)
{
- object_hard_regs_node_t node;
+ allocno_hard_regs_node_t node;
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 (object_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_object_hard_regs_cover (node->first, set);
+ collect_allocno_hard_regs_cover (node->first, set);
}
-/* Set up field parent as PARENT in all object hard registers nodes
+/* Set up field parent as PARENT in all allocno hard registers nodes
in forest given by FIRST. */
static void
-setup_object_hard_regs_nodes_parent (object_hard_regs_node_t first,
- object_hard_regs_node_t parent)
+setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
+ allocno_hard_regs_node_t parent)
{
- object_hard_regs_node_t node;
+ allocno_hard_regs_node_t node;
for (node = first; node != NULL; node = node->next)
{
node->parent = parent;
- setup_object_hard_regs_nodes_parent (node->first, node);
+ setup_allocno_hard_regs_nodes_parent (node->first, node);
}
}
-/* Return object hard registers node which is a first common ancestor
+/* Return allocno hard registers node which is a first common ancestor
node of FIRST and SECOND in the forest. */
-static object_hard_regs_node_t
-first_common_ancestor_node (object_hard_regs_node_t first,
- object_hard_regs_node_t second)
+static allocno_hard_regs_node_t
+first_common_ancestor_node (allocno_hard_regs_node_t first,
+ allocno_hard_regs_node_t second)
{
- object_hard_regs_node_t node;
+ allocno_hard_regs_node_t node;
node_check_tick++;
for (node = first; node != NULL; node = node->parent)
fprintf (f, "\n");
}
-/* Print object hard register subforest given by ROOTS and its LEVEL
+/* Print allocno hard register subforest given by ROOTS and its LEVEL
to F. */
static void
-print_hard_regs_subforest (FILE *f, object_hard_regs_node_t roots,
+print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
int level)
{
int i;
- object_hard_regs_node_t node;
+ allocno_hard_regs_node_t node;
for (node = roots; node != NULL; node = node->next)
{
fprintf (f, " ");
fprintf (f, "%d:(", node->preorder_num);
print_hard_reg_set (f, node->hard_regs->set, false);
- fprintf (f, ")@%lld\n", node->hard_regs->cost);
+ fprintf (f, ")@%" PRId64"\n", node->hard_regs->cost);
print_hard_regs_subforest (f, node->first, level + 1);
}
}
-/* Print the object hard register forest to F. */
+/* Print the allocno hard register forest to F. */
static void
print_hard_regs_forest (FILE *f)
{
print_hard_regs_subforest (f, hard_regs_roots, 1);
}
-/* Print the object hard register forest to stderr. */
+/* Print the allocno hard register forest to stderr. */
void
ira_debug_hard_regs_forest (void)
{
print_hard_regs_forest (stderr);
}
-/* Remove unused object hard registers nodes from forest given by its
+/* Remove unused allocno hard registers nodes from forest given by its
*ROOTS. */
static void
-remove_unused_object_hard_regs_nodes (object_hard_regs_node_t *roots)
+remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
{
- object_hard_regs_node_t node, prev, next, last;
+ allocno_hard_regs_node_t node, prev, next, last;
for (prev = NULL, node = *roots; node != NULL; node = next)
{
next = node->next;
if (node->used_p)
{
- remove_unused_object_hard_regs_nodes (&node->first);
+ remove_unused_allocno_hard_regs_nodes (&node->first);
prev = node;
}
else
}
}
-/* Set up fields preorder_num starting with START_NUM in all object
+/* Set up fields preorder_num starting with START_NUM in all allocno
hard registers nodes in forest given by FIRST. Return biggest set
PREORDER_NUM increased by 1. */
static int
-enumerate_object_hard_regs_nodes (object_hard_regs_node_t first,
- object_hard_regs_node_t parent,
- int start_num)
+enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
+ allocno_hard_regs_node_t parent,
+ int start_num)
{
- object_hard_regs_node_t node;
+ allocno_hard_regs_node_t node;
for (node = first; node != NULL; node = node->next)
{
node->preorder_num = start_num++;
node->parent = parent;
- start_num = enumerate_object_hard_regs_nodes (node->first, node,
- start_num);
+ start_num = enumerate_allocno_hard_regs_nodes (node->first, node,
+ start_num);
}
return start_num;
}
-/* Number of object hard registers nodes in the forest. */
-static int object_hard_regs_nodes_num;
+/* Number of allocno hard registers nodes in the forest. */
+static int allocno_hard_regs_nodes_num;
-/* Table preorder number of object hard registers node in the forest
- -> the object hard registers node. */
-static object_hard_regs_node_t *object_hard_regs_nodes;
+/* Table preorder number of allocno hard registers node in the forest
+ -> the allocno hard registers node. */
+static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
/* See below. */
-typedef struct object_hard_regs_subnode *object_hard_regs_subnode_t;
+typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
/* The structure is used to describes all subnodes (not only immediate
- ones) in the mentioned above tree for given object hard register
+ ones) in the mentioned above tree for given allocno hard register
node. The usage of such data accelerates calculation of
colorability of given allocno. */
-struct object_hard_regs_subnode
+struct allocno_hard_regs_subnode
{
/* The conflict size of conflicting allocnos whose hard register
sets are equal sets (plus supersets if given node is given
- object hard registers node) of one in the given node. */
+ allocno hard registers node) of one in the given node. */
int left_conflict_size;
/* The summary conflict size of conflicting allocnos whose hard
register sets are strict subsets of one in the given node.
short max_node_impact;
};
-/* Container for hard regs subnodes of all objects. */
-static object_hard_regs_subnode_t object_hard_regs_subnodes;
+/* Container for hard regs subnodes of all allocnos. */
+static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
-/* Table (preorder number of object hard registers node in the
- forest, preorder number of object hard registers subnode) -> index
+/* Table (preorder number of allocno hard registers node in the
+ forest, preorder number of allocno hard registers subnode) -> index
of the subnode relative to the node. -1 if it is not a
subnode. */
-static int *object_hard_regs_subnode_index;
+static int *allocno_hard_regs_subnode_index;
-/* Setup arrays OBJECT_HARD_REGS_NODES and
- OBJECT_HARD_REGS_SUBNODE_INDEX. */
+/* Setup arrays ALLOCNO_HARD_REGS_NODES and
+ ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
static void
-setup_object_hard_regs_subnode_index (object_hard_regs_node_t first)
+setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
{
- object_hard_regs_node_t node, parent;
+ allocno_hard_regs_node_t node, parent;
int index;
for (node = first; node != NULL; node = node->next)
{
- object_hard_regs_nodes[node->preorder_num] = node;
+ allocno_hard_regs_nodes[node->preorder_num] = node;
for (parent = node; parent != NULL; parent = parent->parent)
{
- index = parent->preorder_num * object_hard_regs_nodes_num;
- object_hard_regs_subnode_index[index + node->preorder_num]
+ index = parent->preorder_num * allocno_hard_regs_nodes_num;
+ allocno_hard_regs_subnode_index[index + node->preorder_num]
= node->preorder_num - parent->preorder_num;
}
- setup_object_hard_regs_subnode_index (node->first);
+ setup_allocno_hard_regs_subnode_index (node->first);
}
}
-/* Count all object hard registers nodes in tree ROOT. */
+/* Count all allocno hard registers nodes in tree ROOT. */
static int
-get_object_hard_regs_subnodes_num (object_hard_regs_node_t root)
+get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
{
int len = 1;
for (root = root->first; root != NULL; root = root->next)
- len += get_object_hard_regs_subnodes_num (root);
+ len += get_allocno_hard_regs_subnodes_num (root);
return len;
}
-/* Build the forest of object hard registers nodes and assign each
+/* Build the forest of allocno hard registers nodes and assign each
allocno a node from the forest. */
static void
-form_object_hard_regs_nodes_forest (void)
+form_allocno_hard_regs_nodes_forest (void)
{
unsigned int i, j, size, len;
- int start, k;
+ int start;
ira_allocno_t a;
- object_hard_regs_t hv;
+ allocno_hard_regs_t hv;
bitmap_iterator bi;
HARD_REG_SET temp;
- object_hard_regs_node_t node, object_hard_regs_node;
+ allocno_hard_regs_node_t node, allocno_hard_regs_node;
+ allocno_color_data_t allocno_data;
node_check_tick = 0;
- init_object_hard_regs ();
+ init_allocno_hard_regs ();
hard_regs_roots = NULL;
- hard_regs_node_vec = VEC_alloc (object_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))
{
CLEAR_HARD_REG_SET (temp);
SET_HARD_REG_BIT (temp, i);
- hv = add_object_hard_regs (temp, 0);
- node = create_new_object_hard_regs_node (hv);
- add_new_object_hard_regs_node_to_forest (&hard_regs_roots, node);
+ hv = add_allocno_hard_regs (temp, 0);
+ node = create_new_allocno_hard_regs_node (hv);
+ add_new_allocno_hard_regs_node_to_forest (&hard_regs_roots, node);
}
- start = VEC_length (object_hard_regs_t, object_hard_regs_vec);
+ start = allocno_hard_regs_vec.length ();
EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
a = ira_allocnos[i];
- for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
- continue;
- hv = (add_object_hard_regs
- (obj_data->profitable_hard_regs,
- ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
- }
+ allocno_data = ALLOCNO_COLOR_DATA (a);
+
+ if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
+ continue;
+ hv = (add_allocno_hard_regs
+ (allocno_data->profitable_hard_regs,
+ ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
}
SET_HARD_REG_SET (temp);
AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
- add_object_hard_regs (temp, 0);
- qsort (VEC_address (object_hard_regs_t, object_hard_regs_vec) + start,
- VEC_length (object_hard_regs_t, object_hard_regs_vec) - start,
- sizeof (object_hard_regs_t), object_hard_regs_compare);
+ add_allocno_hard_regs (temp, 0);
+ 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 (object_hard_regs_t, object_hard_regs_vec, i, hv);
+ allocno_hard_regs_vec.iterate (i, &hv);
i++)
{
- add_object_hard_regs_to_forest (&hard_regs_roots, hv);
- ira_assert (VEC_length (object_hard_regs_node_t,
- hard_regs_node_vec) == 0);
+ add_allocno_hard_regs_to_forest (&hard_regs_roots, hv);
+ ira_assert (hard_regs_node_vec.length () == 0);
}
/* We need to set up parent fields for right work of
first_common_ancestor_node. */
- setup_object_hard_regs_nodes_parent (hard_regs_roots, NULL);
+ setup_allocno_hard_regs_nodes_parent (hard_regs_roots, NULL);
EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
a = ira_allocnos[i];
- for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
- continue;
- VEC_truncate (object_hard_regs_node_t, hard_regs_node_vec, 0);
- collect_object_hard_regs_cover (hard_regs_roots,
- obj_data->profitable_hard_regs);
- object_hard_regs_node = NULL;
- for (j = 0;
- VEC_iterate (object_hard_regs_node_t, hard_regs_node_vec,
- j, node);
- j++)
- object_hard_regs_node
- = (j == 0
- ? node
- : first_common_ancestor_node (node, object_hard_regs_node));
- /* That is a temporary storage. */
- object_hard_regs_node->used_p = true;
- obj_data->hard_regs_node = object_hard_regs_node;
- }
+ allocno_data = ALLOCNO_COLOR_DATA (a);
+ if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
+ continue;
+ 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; hard_regs_node_vec.iterate (j, &node); j++)
+ allocno_hard_regs_node
+ = (j == 0
+ ? node
+ : first_common_ancestor_node (node, allocno_hard_regs_node));
+ /* That is a temporary storage. */
+ allocno_hard_regs_node->used_p = true;
+ allocno_data->hard_regs_node = allocno_hard_regs_node;
}
ira_assert (hard_regs_roots->next == NULL);
hard_regs_roots->used_p = true;
- remove_unused_object_hard_regs_nodes (&hard_regs_roots);
- object_hard_regs_nodes_num
- = enumerate_object_hard_regs_nodes (hard_regs_roots, NULL, 0);
- object_hard_regs_nodes
- = ((object_hard_regs_node_t *)
- ira_allocate (object_hard_regs_nodes_num
- * sizeof (object_hard_regs_node_t)));
- size = object_hard_regs_nodes_num * object_hard_regs_nodes_num;
- object_hard_regs_subnode_index
+ remove_unused_allocno_hard_regs_nodes (&hard_regs_roots);
+ allocno_hard_regs_nodes_num
+ = enumerate_allocno_hard_regs_nodes (hard_regs_roots, NULL, 0);
+ allocno_hard_regs_nodes
+ = ((allocno_hard_regs_node_t *)
+ ira_allocate (allocno_hard_regs_nodes_num
+ * sizeof (allocno_hard_regs_node_t)));
+ size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
+ allocno_hard_regs_subnode_index
= (int *) ira_allocate (size * sizeof (int));
for (i = 0; i < size; i++)
- object_hard_regs_subnode_index[i] = -1;
- setup_object_hard_regs_subnode_index (hard_regs_roots);
+ allocno_hard_regs_subnode_index[i] = -1;
+ setup_allocno_hard_regs_subnode_index (hard_regs_roots);
start = 0;
EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
a = ira_allocnos[i];
- for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
- continue;
- len = get_object_hard_regs_subnodes_num (obj_data->hard_regs_node);
- obj_data->hard_regs_subnodes_start = start;
- obj_data->hard_regs_subnodes_num = len;
- start += len;
- }
+ allocno_data = ALLOCNO_COLOR_DATA (a);
+ if (hard_reg_set_empty_p (allocno_data->profitable_hard_regs))
+ continue;
+ len = get_allocno_hard_regs_subnodes_num (allocno_data->hard_regs_node);
+ allocno_data->hard_regs_subnodes_start = start;
+ allocno_data->hard_regs_subnodes_num = len;
+ start += len;
}
- object_hard_regs_subnodes
- = ((object_hard_regs_subnode_t)
- ira_allocate (sizeof (struct object_hard_regs_subnode) * start));
- VEC_free (object_hard_regs_node_t, heap, hard_regs_node_vec);
+ allocno_hard_regs_subnodes
+ = ((allocno_hard_regs_subnode_t)
+ ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
+ hard_regs_node_vec.release ();
}
-/* Free tree of object hard registers nodes given by its ROOT. */
+/* Free tree of allocno hard registers nodes given by its ROOT. */
static void
-finish_object_hard_regs_nodes_tree (object_hard_regs_node_t root)
+finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
{
- object_hard_regs_node_t child, next;
+ allocno_hard_regs_node_t child, next;
for (child = root->first; child != NULL; child = next)
{
next = child->next;
- finish_object_hard_regs_nodes_tree (child);
+ finish_allocno_hard_regs_nodes_tree (child);
}
ira_free (root);
}
-/* Finish work with the forest of object hard registers nodes. */
+/* Finish work with the forest of allocno hard registers nodes. */
static void
-finish_object_hard_regs_nodes_forest (void)
+finish_allocno_hard_regs_nodes_forest (void)
{
- object_hard_regs_node_t node, next;
+ allocno_hard_regs_node_t node, next;
- ira_free (object_hard_regs_subnodes);
+ ira_free (allocno_hard_regs_subnodes);
for (node = hard_regs_roots; node != NULL; node = next)
{
next = node->next;
- finish_object_hard_regs_nodes_tree (node);
+ finish_allocno_hard_regs_nodes_tree (node);
}
- ira_free (object_hard_regs_nodes);
- ira_free (object_hard_regs_subnode_index);
- finish_object_hard_regs ();
+ ira_free (allocno_hard_regs_nodes);
+ ira_free (allocno_hard_regs_subnode_index);
+ finish_allocno_hard_regs ();
}
/* Set up left conflict sizes and left conflict subnodes sizes of hard
static bool
setup_left_conflict_sizes_p (ira_allocno_t a)
{
- int k, nobj, conflict_size;
+ int i, k, nobj, start;
+ int conflict_size, left_conflict_subnodes_size, node_preorder_num;
allocno_color_data_t data;
+ HARD_REG_SET profitable_hard_regs;
+ allocno_hard_regs_subnode_t subnodes;
+ allocno_hard_regs_node_t node;
+ 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);
+ node = data->hard_regs_node;
+ node_preorder_num = node->preorder_num;
+ COPY_HARD_REG_SET (node_set, node->hard_regs->set);
+ node_check_tick++;
for (k = 0; k < nobj; k++)
{
- int i, node_preorder_num, start, left_conflict_subnodes_size;
- HARD_REG_SET profitable_hard_regs;
- object_hard_regs_subnode_t subnodes;
- object_hard_regs_node_t node;
- HARD_REG_SET node_set;
ira_object_t obj = ALLOCNO_OBJECT (a, k);
ira_object_t conflict_obj;
ira_object_conflict_iterator oci;
- object_color_data_t obj_data;
- node_check_tick++;
- obj_data = OBJECT_COLOR_DATA (obj);
- subnodes = object_hard_regs_subnodes + obj_data->hard_regs_subnodes_start;
- COPY_HARD_REG_SET (profitable_hard_regs, obj_data->profitable_hard_regs);
- node = obj_data->hard_regs_node;
- node_preorder_num = node->preorder_num;
- COPY_HARD_REG_SET (node_set, node->hard_regs->set);
FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
{
int size;
ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
- object_hard_regs_node_t conflict_node, temp_node;
+ allocno_hard_regs_node_t conflict_node, temp_node;
HARD_REG_SET conflict_node_set;
- object_color_data_t conflict_obj_data;
+ allocno_color_data_t conflict_data;
- conflict_obj_data = OBJECT_COLOR_DATA (conflict_obj);
+ conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
|| ! hard_reg_set_intersect_p (profitable_hard_regs,
- conflict_obj_data
+ conflict_data
->profitable_hard_regs))
continue;
- conflict_node = conflict_obj_data->hard_regs_node;
+ conflict_node = conflict_data->hard_regs_node;
COPY_HARD_REG_SET (conflict_node_set, conflict_node->hard_regs->set);
if (hard_reg_set_subset_p (node_set, conflict_node_set))
temp_node = node;
size = 1;
temp_node->conflict_size += size;
}
- for (i = 0; i < obj_data->hard_regs_subnodes_num; i++)
+ }
+ for (i = 0; i < data->hard_regs_subnodes_num; i++)
+ {
+ allocno_hard_regs_node_t temp_node;
+
+ temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
+ ira_assert (temp_node->preorder_num == i + node_preorder_num);
+ subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
+ ? 0 : temp_node->conflict_size);
+ if (hard_reg_set_subset_p (temp_node->hard_regs->set,
+ profitable_hard_regs))
+ subnodes[i].max_node_impact = temp_node->hard_regs_num;
+ else
{
- object_hard_regs_node_t temp_node;
-
- temp_node = object_hard_regs_nodes[i + node_preorder_num];
- ira_assert (temp_node->preorder_num == i + node_preorder_num);
- subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
- ? 0 : temp_node->conflict_size);
- if (hard_reg_set_subset_p (temp_node->hard_regs->set,
- profitable_hard_regs))
- subnodes[i].max_node_impact = temp_node->hard_regs_num;
- else
+ HARD_REG_SET temp_set;
+ int j, n, hard_regno;
+ enum reg_class aclass;
+
+ COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
+ AND_HARD_REG_SET (temp_set, profitable_hard_regs);
+ aclass = ALLOCNO_CLASS (a);
+ for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
{
- HARD_REG_SET temp_set;
- int j, n;
- enum reg_class aclass;
-
- COPY_HARD_REG_SET (temp_set, temp_node->hard_regs->set);
- AND_HARD_REG_SET (temp_set, profitable_hard_regs);
- aclass = ALLOCNO_CLASS (a);
- for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
- if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[aclass][j]))
- n++;
- subnodes[i].max_node_impact = n;
+ hard_regno = ira_class_hard_regs[aclass][j];
+ if (TEST_HARD_REG_BIT (temp_set, hard_regno))
+ n++;
}
- subnodes[i].left_conflict_subnodes_size = 0;
+ subnodes[i].max_node_impact = n;
}
- start = node_preorder_num * object_hard_regs_nodes_num;
- for (i = obj_data->hard_regs_subnodes_num - 1; i >= 0; i--)
- {
- int size, parent_i;
- object_hard_regs_node_t parent;
-
- size = (subnodes[i].left_conflict_subnodes_size
- + MIN (subnodes[i].max_node_impact
- - subnodes[i].left_conflict_subnodes_size,
- subnodes[i].left_conflict_size));
- parent = object_hard_regs_nodes[i + node_preorder_num]->parent;
- if (parent == NULL)
- continue;
- parent_i
- = object_hard_regs_subnode_index[start + parent->preorder_num];
- if (parent_i < 0)
- continue;
- 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));
+ 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--)
+ {
+ int size, parent_i;
+ allocno_hard_regs_node_t parent;
+
+ size = (subnodes[i].left_conflict_subnodes_size
+ + MIN (subnodes[i].max_node_impact
+ - subnodes[i].left_conflict_subnodes_size,
+ subnodes[i].left_conflict_size));
+ parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
+ gcc_checking_assert(parent);
+ parent_i
+ = allocno_hard_regs_subnode_index[start + parent->preorder_num];
+ 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));
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;
}
/* Update left conflict sizes of hard registers subnodes of allocno A
- after removing allocno containing object REMOVED_OBJ with SIZE from
- the conflict graph. Return TRUE if A is trivially colorable. */
+ after removing allocno REMOVED_A with SIZE from the conflict graph.
+ Return TRUE if A is trivially colorable. */
static bool
update_left_conflict_sizes_p (ira_allocno_t a,
- ira_object_t removed_obj, int size)
+ ira_allocno_t removed_a, int size)
{
- int i, k, conflict_size, before_conflict_size, diff, start;
+ int i, conflict_size, before_conflict_size, diff, start;
int node_preorder_num, parent_i;
- object_hard_regs_node_t node, removed_node, parent;
- object_hard_regs_subnode_t subnodes;
+ allocno_hard_regs_node_t node, removed_node, parent;
+ allocno_hard_regs_subnode_t subnodes;
allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
- bool colorable_p = true;
ira_assert (! data->colorable_p);
- for (k = 0; k < ALLOCNO_NUM_OBJECTS (a); k++)
+ node = data->hard_regs_node;
+ node_preorder_num = node->preorder_num;
+ removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
+ ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
+ node->hard_regs->set)
+ || hard_reg_set_subset_p (node->hard_regs->set,
+ removed_node->hard_regs->set));
+ start = node_preorder_num * allocno_hard_regs_nodes_num;
+ i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
+ if (i < 0)
+ i = 0;
+ subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
+ before_conflict_size
+ = (subnodes[i].left_conflict_subnodes_size
+ + MIN (subnodes[i].max_node_impact
+ - subnodes[i].left_conflict_subnodes_size,
+ subnodes[i].left_conflict_size));
+ subnodes[i].left_conflict_size -= size;
+ for (;;)
{
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- node = obj_data->hard_regs_node;
- node_preorder_num = node->preorder_num;
- removed_node = OBJECT_COLOR_DATA (removed_obj)->hard_regs_node;
- if (! hard_reg_set_subset_p (removed_node->hard_regs->set,
- node->hard_regs->set)
- && ! hard_reg_set_subset_p (node->hard_regs->set,
- removed_node->hard_regs->set))
- /* It is a rare case which can happen for conflicting
- multi-object allocnos where only one pair of objects might
- conflict. */
- continue;
- start = node_preorder_num * object_hard_regs_nodes_num;
- i = object_hard_regs_subnode_index[start + removed_node->preorder_num];
- if (i < 0)
- i = 0;
- subnodes = object_hard_regs_subnodes + obj_data->hard_regs_subnodes_start;
+ conflict_size
+ = (subnodes[i].left_conflict_subnodes_size
+ + MIN (subnodes[i].max_node_impact
+ - subnodes[i].left_conflict_subnodes_size,
+ subnodes[i].left_conflict_size));
+ if ((diff = before_conflict_size - conflict_size) == 0)
+ break;
+ ira_assert (conflict_size < before_conflict_size);
+ parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
+ if (parent == NULL)
+ break;
+ parent_i
+ = allocno_hard_regs_subnode_index[start + parent->preorder_num];
+ if (parent_i < 0)
+ break;
+ i = parent_i;
before_conflict_size
= (subnodes[i].left_conflict_subnodes_size
+ MIN (subnodes[i].max_node_impact
- subnodes[i].left_conflict_subnodes_size,
subnodes[i].left_conflict_size));
- subnodes[i].left_conflict_size -= size;
- for (;;)
- {
- conflict_size
- = (subnodes[i].left_conflict_subnodes_size
- + MIN (subnodes[i].max_node_impact
- - subnodes[i].left_conflict_subnodes_size,
- subnodes[i].left_conflict_size));
- if ((diff = before_conflict_size - conflict_size) == 0)
- break;
- ira_assert (conflict_size < before_conflict_size);
- parent = object_hard_regs_nodes[i + node_preorder_num]->parent;
- if (parent == NULL)
- break;
- parent_i
- = object_hard_regs_subnode_index[start + parent->preorder_num];
- if (parent_i < 0)
- break;
- i = parent_i;
- before_conflict_size
- = (subnodes[i].left_conflict_subnodes_size
- + MIN (subnodes[i].max_node_impact
- - subnodes[i].left_conflict_subnodes_size,
- subnodes[i].left_conflict_size));
- subnodes[i].left_conflict_subnodes_size -= diff;
- }
- if (i != 0
- || (conflict_size
- + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
- > data->available_regs_num))
- {
- colorable_p = false;
- break;
- }
- }
- if (colorable_p)
- {
- data->colorable_p = true;
- return true;
+ subnodes[i].left_conflict_subnodes_size -= diff;
}
- return false;
+ if (i != 0
+ || (conflict_size
+ + ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
+ > data->available_regs_num))
+ return false;
+ data->colorable_p = true;
+ return true;
}
-/* Return true if allocno A has an object with empty profitable hard
- regs. */
+/* Return true if allocno A has empty profitable hard regs. */
static bool
empty_profitable_hard_regs (ira_allocno_t a)
{
- int k, nobj;
-
- nobj = ALLOCNO_NUM_OBJECTS (a);
- for (k = 0; k < nobj; k++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
+ allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
- if (hard_reg_set_empty_p (obj_data->profitable_hard_regs))
- return true;
- }
- return false;
+ return hard_reg_set_empty_p (data->profitable_hard_regs);
}
/* Set up profitable hard registers for each allocno being
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
hard regs. */
a = ira_allocnos[i];
if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
continue;
- mode = ALLOCNO_MODE (a);
- nobj = ALLOCNO_NUM_OBJECTS (a);
- for (k = 0; k < nobj; k++)
+ data = ALLOCNO_COLOR_DATA (a);
+ if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
+ && 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
{
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
- && ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a))
- CLEAR_HARD_REG_SET (obj_data->profitable_hard_regs);
- else
+ mode = ALLOCNO_MODE (a);
+ COPY_HARD_REG_SET (data->profitable_hard_regs,
+ ira_useful_class_mode_regs[aclass][mode]);
+ nobj = ALLOCNO_NUM_OBJECTS (a);
+ for (k = 0; k < nobj; k++)
{
- COPY_HARD_REG_SET (obj_data->profitable_hard_regs,
- reg_class_contents[aclass]);
- AND_COMPL_HARD_REG_SET (obj_data->profitable_hard_regs,
- ira_no_alloc_regs);
- AND_COMPL_HARD_REG_SET (obj_data->profitable_hard_regs,
+ ira_object_t obj = ALLOCNO_OBJECT (a, k);
+
+ AND_COMPL_HARD_REG_SET (data->profitable_hard_regs,
OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
}
}
FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
{
+ ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
+
+ /* We can process the conflict allocno repeatedly with
+ the same result. */
if (nregs == nobj && nregs > 1)
{
int num = OBJECT_SUBWORD (conflict_obj);
- if (WORDS_BIG_ENDIAN)
+ if (REG_WORDS_BIG_ENDIAN)
CLEAR_HARD_REG_BIT
- (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
+ (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
hard_regno + nobj - num - 1);
else
CLEAR_HARD_REG_BIT
- (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
+ (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
hard_regno + num);
}
else
AND_COMPL_HARD_REG_SET
- (OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs,
+ (ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
ira_reg_mode_hard_regset[hard_regno][mode]);
}
}
if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
|| empty_profitable_hard_regs (a))
continue;
+ data = ALLOCNO_COLOR_DATA (a);
mode = ALLOCNO_MODE (a);
- nobj = ALLOCNO_NUM_OBJECTS (a);
- for (k = 0; k < nobj; k++)
+ if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
+ || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
{
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
- || (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
+ class_size = ira_class_hard_regs_num[aclass];
+ for (j = 0; j < class_size; j++)
{
- class_size = ira_class_hard_regs_num[aclass];
- for (j = 0; j < class_size; j++)
- {
- hard_regno = ira_class_hard_regs[aclass][j];
- nregs = hard_regno_nregs[hard_regno][mode];
- if (nregs == nobj && nregs > 1)
- {
- int num = OBJECT_SUBWORD (obj);
-
- if (WORDS_BIG_ENDIAN)
- hard_regno += nobj - num - 1;
- else
- hard_regno += num;
- }
- if (! TEST_HARD_REG_BIT (obj_data->profitable_hard_regs,
- hard_regno))
- continue;
- if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j])
- CLEAR_HARD_REG_BIT (obj_data->profitable_hard_regs,
- hard_regno);
- else if (min_cost > costs[j])
- min_cost = costs[j];
- }
+ hard_regno = ira_class_hard_regs[aclass][j];
+ if (! TEST_HARD_REG_BIT (data->profitable_hard_regs,
+ hard_regno))
+ continue;
+ 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])
+ min_cost = costs[j];
}
- else if (ALLOCNO_UPDATED_MEMORY_COST (a)
- < ALLOCNO_UPDATED_CLASS_COST (a))
- CLEAR_HARD_REG_SET (obj_data->profitable_hard_regs);
}
+ else if (ALLOCNO_UPDATED_MEMORY_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);
}
}
-/* Set up conflicting and profitable regs (through CONFLICT_REGS and
- PROFITABLE_REGS) for each object of allocno A. Remember that the
- profitable regs exclude hard regs which can not hold value of mode
- of allocno A. */
+/* Set up conflicting (through CONFLICT_REGS) for each object of
+ allocno A and the start allocno profitable regs (through
+ START_PROFITABLE_REGS). Remember that the start profitable regs
+ exclude hard regs which can not hold value of mode of allocno A.
+ This covers mostly cases when multi-register value should be
+ aligned. */
static inline void
-get_conflict_profitable_regs (ira_allocno_t a, bool retry_p,
- HARD_REG_SET *conflict_regs,
- HARD_REG_SET *profitable_regs)
+get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
+ HARD_REG_SET *conflict_regs,
+ HARD_REG_SET *start_profitable_regs)
{
int i, nwords;
ira_object_t obj;
obj = ALLOCNO_OBJECT (a, i);
COPY_HARD_REG_SET (conflict_regs[i],
OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
- if (retry_p)
- {
- COPY_HARD_REG_SET (profitable_regs[i],
- reg_class_contents[ALLOCNO_CLASS (a)]);
- AND_COMPL_HARD_REG_SET (profitable_regs[i],
- ira_prohibited_class_mode_regs
- [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
- }
- else
- COPY_HARD_REG_SET (profitable_regs[i],
- OBJECT_COLOR_DATA (obj)->profitable_hard_regs);
}
+ if (retry_p)
+ {
+ COPY_HARD_REG_SET (*start_profitable_regs,
+ reg_class_contents[ALLOCNO_CLASS (a)]);
+ AND_COMPL_HARD_REG_SET (*start_profitable_regs,
+ ira_prohibited_class_mode_regs
+ [ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
+ }
+ else
+ COPY_HARD_REG_SET (*start_profitable_regs,
+ ALLOCNO_COLOR_DATA (a)->profitable_hard_regs);
}
-/* Return true if HARD_REGNO is ok for assigning to allocno A whose
- objects have corresponding CONFLICT_REGS and PROFITABLE_REGS. */
+/* Return true if HARD_REGNO is ok for assigning to allocno A with
+ PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
static inline bool
check_hard_reg_p (ira_allocno_t a, int hard_regno,
- HARD_REG_SET *conflict_regs, HARD_REG_SET *profitable_regs)
+ HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
{
int j, nwords, nregs;
enum reg_class aclass;
- enum machine_mode mode;
+ machine_mode mode;
aclass = ALLOCNO_CLASS (a);
mode = ALLOCNO_MODE (a);
if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
hard_regno))
return false;
+ /* Checking only profitable hard regs. */
+ if (! TEST_HARD_REG_BIT (profitable_regs, hard_regno))
+ return false;
nregs = hard_regno_nregs[hard_regno][mode];
nwords = ALLOCNO_NUM_OBJECTS (a);
for (j = 0; j < nregs; j++)
if (nregs == nwords)
{
- if (WORDS_BIG_ENDIAN)
+ if (REG_WORDS_BIG_ENDIAN)
set_to_test_start = nwords - j - 1;
else
set_to_test_start = j;
set_to_test_end = set_to_test_start + 1;
}
for (k = set_to_test_start; k < set_to_test_end; k++)
- /* Checking only profitable hard regs. */
- if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j)
- || ! TEST_HARD_REG_BIT (profitable_regs[k], hard_regno + j))
+ if (TEST_HARD_REG_BIT (conflict_regs[k], hard_regno + j))
break;
if (k != set_to_test_end)
break;
return j == nregs;
}
+/* 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, machine_mode mode)
+{
+ int i;
+ int nregs = 0;
+
+ ira_assert (hard_regno >= 0);
+ for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--)
+ if (!allocated_hardreg_p[hard_regno + i]
+ && !TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + i)
+ && !LOCAL_REGNO (hard_regno + i))
+ nregs++;
+ return nregs;
+}
+
/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
that the function called from function
`ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
static bool
assign_hard_reg (ira_allocno_t a, bool retry_p)
{
- HARD_REG_SET conflicting_regs[2], profitable_hard_regs[2];
+ HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
int i, j, hard_regno, best_hard_regno, class_size;
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_assert (! ALLOCNO_ASSIGNED_P (a));
- get_conflict_profitable_regs (a, retry_p,
- conflicting_regs, profitable_hard_regs);
+ get_conflict_and_start_profitable_regs (a, retry_p,
+ conflicting_regs,
+ &profitable_hard_regs);
aclass = ALLOCNO_CLASS (a);
class_size = ira_class_hard_regs_num[aclass];
best_hard_regno = -1;
full_costs[i] += cost;
}
nwords = ALLOCNO_NUM_OBJECTS (a);
+ curr_allocno_process++;
for (word = 0; word < nwords; word++)
{
ira_object_t conflict_obj;
{
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[word],
- OBJECT_COLOR_DATA
- (conflict_obj)->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]);
{
int num = OBJECT_SUBWORD (conflict_obj);
- if (WORDS_BIG_ENDIAN)
+ if (REG_WORDS_BIG_ENDIAN)
SET_HARD_REG_BIT (conflicting_regs[word],
hard_regno + n_objects - num - 1);
else
IOR_HARD_REG_SET
(conflicting_regs[word],
ira_reg_mode_hard_regset[hard_regno][mode]);
- if (hard_reg_set_subset_p (profitable_hard_regs[word],
+ if (hard_reg_set_subset_p (profitable_hard_regs,
conflicting_regs[word]))
goto fail;
}
}
else if (! retry_p
- && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p)
+ && ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
+ /* Don't process the conflict allocno twice. */
+ && (ALLOCNO_COLOR_DATA (conflict_a)->last_process
+ != curr_allocno_process))
{
int k, *conflict_costs;
+ ALLOCNO_COLOR_DATA (conflict_a)->last_process
+ = curr_allocno_process;
ira_allocate_and_copy_costs
(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
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;
-
/* We don't care about giving callee saved registers to allocnos no
living through calls because call clobbered registers are
allocated first (it is usual practice to put them first in
continue;
cost = costs[i];
full_cost = full_costs[i];
-#ifndef HONOR_REG_ALLOC_ORDER
- if (! allocated_hardreg_p[hard_regno]
- && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set)
- && !LOCAL_REGNO (hard_regno))
- /* We need to save/restore the hard register in
- epilogue/prologue. Therefore we increase the cost. */
+ if (!HONOR_REG_ALLOC_ORDER)
{
- /* ??? If only part is call clobbered. */
- rclass = REGNO_REG_CLASS (hard_regno);
- add_cost = (ira_memory_move_cost[mode][rclass][0]
- + ira_memory_move_cost[mode][rclass][1] - 1);
- cost += add_cost;
- full_cost += add_cost;
+ if ((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) ",
}
fail:
if (best_hard_regno >= 0)
- allocated_hardreg_p[best_hard_regno] = true;
+ {
+ 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;
- if ((diff = (int) ALLOCNO_CLASS (a2) - ALLOCNO_CLASS (a1)) != 0)
+ /* 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
+ which the pseudos requiring more hard registers can not fit. */
+ 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;
|| ! conflict_data->in_graph_p
|| ALLOCNO_ASSIGNED_P (conflict_a)
|| !(hard_reg_set_intersect_p
- (OBJECT_COLOR_DATA (obj)->profitable_hard_regs,
- OBJECT_COLOR_DATA (conflict_obj)->profitable_hard_regs)))
+ (ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
+ conflict_data->profitable_hard_regs)))
continue;
ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
ALLOCNO_NUM (conflict_a)));
- if (update_left_conflict_sizes_p (conflict_a, obj, size))
+ if (update_left_conflict_sizes_p (conflict_a, a, size))
{
delete_allocno_from_bucket
- (conflict_a, &uncolorable_allocno_bucket);
- add_allocno_to_ordered_bucket
- (conflict_a, &colorable_allocno_bucket);
+ (conflict_a, &uncolorable_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 (loop_node->loop != NULL
+ ira_assert (current_loops != NULL && loop_node->loop != NULL
&& (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
freq = 0;
if (! exit_p)
FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
if (e->src != loop_node->loop->latch
&& (regno < 0
- || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
- && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
+ || (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;
}
static void
setup_allocno_available_regs_num (ira_allocno_t a)
{
- int i, j, n, hard_regno, hard_regs_num, nwords, nregs;
+ int i, n, hard_regno, hard_regs_num, nwords;
enum reg_class aclass;
- enum machine_mode mode;
allocno_color_data_t data;
aclass = ALLOCNO_CLASS (a);
if (aclass == NO_REGS)
return;
hard_regs_num = ira_class_hard_regs_num[aclass];
- mode = ALLOCNO_MODE (a);
nwords = ALLOCNO_NUM_OBJECTS (a);
for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
{
hard_regno = ira_class_hard_regs[aclass][i];
- nregs = hard_regno_nregs[hard_regno][mode];
- for (j = 0; j < nregs; j++)
- {
- int k;
- int set_to_test_start = 0, set_to_test_end = nwords;
-
- if (nregs == nwords)
- {
- if (WORDS_BIG_ENDIAN)
- set_to_test_start = nwords - j - 1;
- else
- set_to_test_start = j;
- set_to_test_end = set_to_test_start + 1;
- }
- for (k = set_to_test_start; k < set_to_test_end; k++)
- {
- ira_object_t obj = ALLOCNO_OBJECT (a, k);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
-
- /* Checking only profitable hard regs which exclude
- object's conflict hard regs. */
- if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
- hard_regno + j)
- || ! TEST_HARD_REG_BIT (obj_data->profitable_hard_regs,
- hard_regno + j))
- break;
- }
- if (k != set_to_test_end)
- break;
- }
- if (j == nregs)
+ /* Checking only profitable hard regs. */
+ if (TEST_HARD_REG_BIT (data->profitable_hard_regs, hard_regno))
n++;
}
data->available_regs_num = n;
return;
fprintf
(ira_dump_file,
- " Allocno a%dr%d of %s(%d) has %d avail. regs",
+ " Allocno a%dr%d of %s(%d) has %d avail. regs ",
ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
+ print_hard_reg_set (ira_dump_file, data->profitable_hard_regs, false);
+ fprintf (ira_dump_file, ", %snode: ",
+ hard_reg_set_equal_p (data->profitable_hard_regs,
+ data->hard_regs_node->hard_regs->set)
+ ? "" : "^");
+ print_hard_reg_set (ira_dump_file,
+ data->hard_regs_node->hard_regs->set, false);
for (i = 0; i < nwords; i++)
{
ira_object_t obj = ALLOCNO_OBJECT (a, i);
- object_color_data_t obj_data = OBJECT_COLOR_DATA (obj);
if (nwords != 1)
{
fprintf (ira_dump_file, ", ");
fprintf (ira_dump_file, " obj %d", i);
}
- print_hard_reg_set (ira_dump_file, obj_data->profitable_hard_regs, false);
fprintf (ira_dump_file, " (confl regs = ");
print_hard_reg_set (ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
false);
- fprintf (ira_dump_file, " ) %snode: ",
- hard_reg_set_equal_p (obj_data->profitable_hard_regs,
- obj_data->hard_regs_node->hard_regs->set)
- ? "" : "^");
- print_hard_reg_set (ira_dump_file,
- obj_data->hard_regs_node->hard_regs->set, false);
-
+ fprintf (ira_dump_file, ")");
}
fprintf (ira_dump_file, "\n");
}
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[2];
+ 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)
else
base_cost = allocno_costs[ira_class_hard_reg_index[aclass][hregno]];
try_p = false;
- get_conflict_profitable_regs (a, false,
- conflicting_regs, profitable_hard_regs);
+ get_conflict_and_start_profitable_regs (a, false,
+ conflicting_regs,
+ &profitable_hard_regs);
class_size = ira_class_hard_regs_num[aclass];
/* Set up cost improvement for usage of each profitable hard
register for allocno A. */
}
}
-/* 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;
}
else
{
- form_object_hard_regs_nodes_forest ();
+ form_allocno_hard_regs_nodes_forest ();
if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
print_hard_regs_forest (ira_dump_file);
EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
{
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;
}
push_allocnos_to_stack ();
pop_allocnos_from_stack ();
- finish_object_hard_regs_nodes_forest ();
+ finish_allocno_hard_regs_nodes_forest ();
}
improve_allocation ();
}
\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)
{
edge e;
edge_iterator ei;
- ira_assert (loop_tree_node->loop != NULL);
- fprintf (ira_dump_file,
- "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
- loop_tree_node->loop->num,
- (loop_tree_node->parent == NULL
- ? -1 : loop_tree_node->parent->loop->num),
- loop_tree_node->loop->header->index,
- loop_depth (loop_tree_node->loop));
+ if (loop_tree_node->parent == NULL)
+ fprintf (ira_dump_file,
+ "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
+ NUM_FIXED_BLOCKS);
+ else
+ {
+ ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
+ fprintf (ira_dump_file,
+ "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
+ loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
+ loop_tree_node->loop->header->index,
+ loop_depth (loop_tree_node->loop));
+ }
for (subloop_node = loop_tree_node->children;
subloop_node != NULL;
subloop_node = subloop_node->next)
{
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)",
- e->dest->index, dest_loop_node->loop->num);
+ e->dest->index, dest_loop_node->loop_num);
}
fprintf (ira_dump_file, "\n all:");
EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
static void
color_pass (ira_loop_tree_node_t loop_tree_node)
{
- int i, regno, hard_regno, index = -1, n, nobj;
+ int regno, hard_regno, index = -1, n;
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;
bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
- n = nobj = 0;
+ n = 0;
EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
{
a = ira_allocnos[j];
n++;
- nobj += ALLOCNO_NUM_OBJECTS (a);
if (! ALLOCNO_ASSIGNED_P (a))
continue;
bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
= (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
* n);
memset (allocno_color_data, 0, sizeof (struct allocno_color_data) * n);
- object_color_data
- = (object_color_data_t) ira_allocate (sizeof (struct object_color_data)
- * nobj);
- memset (object_color_data, 0, sizeof (struct object_color_data) * nobj);
- n = nobj = 0;
+ curr_allocno_process = 0;
+ n = 0;
EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
{
a = ira_allocnos[j];
ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
n++;
- for (i = 0; i < ALLOCNO_NUM_OBJECTS (a); i++)
- {
- OBJECT_ADD_DATA (ALLOCNO_OBJECT (a, i)) = object_color_data + nobj;
- nobj++;
- }
}
+ 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 (object_color_data);
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;
- for (i = 0; i < ALLOCNO_NUM_OBJECTS (a); i++)
- OBJECT_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. */
- || 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);
fprintf
(ira_dump_file,
" Moving spill/restore for a%dr%d up from loop %d",
- ALLOCNO_NUM (a), regno, loop_node->loop->num);
+ ALLOCNO_NUM (a), regno, loop_node->loop_num);
fprintf (ira_dump_file, " - profit %d\n", -cost);
}
changed_p = true;
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. */
: ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
[aclass][hard_regno]]));
if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
- && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
- call_used_reg_set))
+ && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
+ call_used_reg_set))
{
ira_assert (flag_caller_saves);
caller_save_needed = 1;
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;
&& hard_regno <= LAST_STACK_REG)
continue;
#endif
- if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
+ if (ira_hard_reg_set_intersection_p (hard_regno, mode, conflict_hard_regs)
|| (TEST_HARD_REG_BIT
(ira_prohibited_class_mode_regs[aclass][mode], hard_regno)))
continue;
projects / gcc.git / blobdiff