+ It is also used to figure out allocno colorability as a mark that
+ we already reset value of member 'conflict_size' for the forest
+ node corresponding to the processed allocno. */
+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;
+
+/* 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);
+
+/* Vector used to create the forest. */
+static VEC(object_hard_regs_node_t, heap) *hard_regs_node_vec;
+
+/* Create and return object hard registers node containing object
+ hard registers HV. */
+static object_hard_regs_node_t
+create_new_object_hard_regs_node (object_hard_regs_t hv)
+{
+ object_hard_regs_node_t new_node;
+
+ new_node = ((struct object_hard_regs_node *)
+ ira_allocate (sizeof (struct object_hard_regs_node)));
+ new_node->check = 0;
+ new_node->hard_regs = hv;
+ new_node->hard_regs_num = hard_reg_set_size (hv->set);
+ new_node->first = NULL;
+ new_node->used_p = false;
+ return new_node;
+}
+
+/* Add object 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)
+{
+ new_node->next = *roots;
+ if (new_node->next != NULL)
+ new_node->next->prev = new_node;
+ new_node->prev = NULL;
+ *roots = new_node;
+}
+
+/* Add object 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)
+{
+ unsigned int i, start;
+ object_hard_regs_node_t node, prev, new_node;
+ HARD_REG_SET temp_set;
+ object_hard_regs_t hv2;
+
+ start = VEC_length (object_hard_regs_node_t, hard_regs_node_vec);
+ 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);
+ 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);
+ 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);
+ }
+ }
+ if (VEC_length (object_hard_regs_node_t, hard_regs_node_vec)
+ > 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++)
+ {
+ node = VEC_index (object_hard_regs_node_t, 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);
+ prev = NULL;
+ for (i = start;
+ i < VEC_length (object_hard_regs_node_t, hard_regs_node_vec);
+ i++)
+ {
+ node = VEC_index (object_hard_regs_node_t, hard_regs_node_vec, i);
+ if (node->prev == NULL)
+ *roots = node->next;
+ else
+ node->prev->next = node->next;
+ if (node->next != NULL)
+ node->next->prev = node->prev;
+ if (prev == NULL)
+ new_node->first = node;
+ else
+ prev->next = node;
+ node->prev = prev;
+ node->next = NULL;
+ prev = node;
+ }
+ add_new_object_hard_regs_node_to_forest (roots, new_node);
+ }
+ VEC_truncate (object_hard_regs_node_t, hard_regs_node_vec, start);
+}
+
+/* Add object 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,
+ HARD_REG_SET set)
+{
+ object_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);
+ else if (hard_reg_set_intersect_p (set, node->hard_regs->set))
+ collect_object_hard_regs_cover (node->first, set);
+}
+
+/* Set up field parent as PARENT in all object 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)
+{
+ object_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);
+ }
+}
+
+/* Return object 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)
+{
+ object_hard_regs_node_t node;
+
+ node_check_tick++;
+ for (node = first; node != NULL; node = node->parent)
+ node->check = node_check_tick;
+ for (node = second; node != NULL; node = node->parent)
+ if (node->check == node_check_tick)
+ return node;
+ return first_common_ancestor_node (second, first);
+}
+
+/* Print hard reg set SET to F. */
+static void
+print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
+{
+ int i, start;
+
+ for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ {
+ if (TEST_HARD_REG_BIT (set, i))
+ {
+ if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
+ start = i;
+ }
+ if (start >= 0
+ && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
+ {
+ if (start == i - 1)
+ fprintf (f, " %d", start);
+ else if (start == i - 2)
+ fprintf (f, " %d %d", start, start + 1);
+ else
+ fprintf (f, " %d-%d", start, i - 1);
+ start = -1;
+ }
+ }
+ if (new_line_p)
+ fprintf (f, "\n");
+}
+
+/* Print object 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,
+ int level)
+{
+ int i;
+ object_hard_regs_node_t node;
+
+ for (node = roots; node != NULL; node = node->next)
+ {
+ fprintf (f, " ");
+ for (i = 0; i < level * 2; i++)
+ 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);
+ print_hard_regs_subforest (f, node->first, level + 1);
+ }
+}
+
+/* Print the object hard register forest to F. */
+static void
+print_hard_regs_forest (FILE *f)
+{
+ fprintf (f, " Hard reg set forest:\n");
+ print_hard_regs_subforest (f, hard_regs_roots, 1);
+}
+
+/* Print the object 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
+ *ROOTS. */
+static void
+remove_unused_object_hard_regs_nodes (object_hard_regs_node_t *roots)
+{
+ object_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);
+ prev = node;
+ }
+ else
+ {
+ for (last = node->first;
+ last != NULL && last->next != NULL;
+ last = last->next)
+ ;
+ if (last != NULL)
+ {
+ if (prev == NULL)
+ *roots = node->first;
+ else
+ prev->next = node->first;
+ if (next != NULL)
+ next->prev = last;
+ last->next = next;
+ next = node->first;
+ }
+ else
+ {
+ if (prev == NULL)
+ *roots = next;
+ else
+ prev->next = next;
+ if (next != NULL)
+ next->prev = prev;
+ }
+ ira_free (node);
+ }
+ }
+}
+
+/* Set up fields preorder_num starting with START_NUM in all object
+ 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)
+{
+ object_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);
+ }
+ return start_num;
+}
+
+/* Number of object hard registers nodes in the forest. */
+static int object_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;
+
+/* See below. */
+typedef struct object_hard_regs_subnode *object_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
+ node. The usage of such data accelerates calculation of
+ colorability of given allocno. */
+struct object_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. */
+ int left_conflict_size;
+ /* The summary conflict size of conflicting allocnos whose hard
+ register sets are strict subsets of one in the given node.
+ Overall conflict size is
+ left_conflict_subnodes_size
+ + MIN (max_node_impact - left_conflict_subnodes_size,
+ left_conflict_size)
+ */
+ short left_conflict_subnodes_size;
+ short max_node_impact;
+};
+
+/* Container for hard regs subnodes of all objects. */
+static object_hard_regs_subnode_t object_hard_regs_subnodes;
+
+/* Table (preorder number of object hard registers node in the
+ forest, preorder number of object 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;
+
+/* Setup arrays OBJECT_HARD_REGS_NODES and
+ OBJECT_HARD_REGS_SUBNODE_INDEX. */
+static void
+setup_object_hard_regs_subnode_index (object_hard_regs_node_t first)
+{
+ object_hard_regs_node_t node, parent;
+ int index;
+
+ for (node = first; node != NULL; node = node->next)
+ {
+ object_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]
+ = node->preorder_num - parent->preorder_num;
+ }
+ setup_object_hard_regs_subnode_index (node->first);
+ }
+}
+
+/* Count all object hard registers nodes in tree ROOT. */
+static int
+get_object_hard_regs_subnodes_num (object_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);
+ return len;
+}
+
+/* Build the forest of object hard registers nodes and assign each
+ allocno a node from the forest. */
+static void
+form_object_hard_regs_nodes_forest (void)
+{
+ unsigned int i, j, size, len;
+ int start, k;
+ ira_allocno_t a;
+ object_hard_regs_t hv;
+ bitmap_iterator bi;
+ HARD_REG_SET temp;
+ object_hard_regs_node_t node, object_hard_regs_node;
+
+ node_check_tick = 0;
+ init_object_hard_regs ();
+ hard_regs_roots = NULL;
+ hard_regs_node_vec = VEC_alloc (object_hard_regs_node_t, heap, 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);
+ }
+ start = VEC_length (object_hard_regs_t, object_hard_regs_vec);
+ 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)));
+ }
+ }
+ 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);
+ for (i = start;
+ VEC_iterate (object_hard_regs_t, object_hard_regs_vec, 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);
+ }
+ /* 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);
+ 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;
+ }
+ }
+ 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
+ = (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);
+ 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;
+ }
+ }
+ 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);
+}
+
+/* Free tree of object hard registers nodes given by its ROOT. */
+static void
+finish_object_hard_regs_nodes_tree (object_hard_regs_node_t root)
+{
+ object_hard_regs_node_t child, next;
+
+ for (child = root->first; child != NULL; child = next)
+ {
+ next = child->next;
+ finish_object_hard_regs_nodes_tree (child);
+ }
+ ira_free (root);
+}
+
+/* Finish work with the forest of object hard registers nodes. */
+static void
+finish_object_hard_regs_nodes_forest (void)
+{
+ object_hard_regs_node_t node, next;
+
+ ira_free (object_hard_regs_subnodes);
+ for (node = hard_regs_roots; node != NULL; node = next)
+ {
+ next = node->next;
+ finish_object_hard_regs_nodes_tree (node);
+ }
+ ira_free (object_hard_regs_nodes);
+ ira_free (object_hard_regs_subnode_index);
+ finish_object_hard_regs ();
+}
+
+/* Set up left conflict sizes and left conflict subnodes sizes of hard
+ registers subnodes of allocno A. Return TRUE if allocno A is
+ trivially colorable. */