+/* Return TRUE if NODE is inside PARENT. */
+static bool
+loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
+{
+ for (node = node->parent; node != NULL; node = node->parent)
+ if (node == parent)
+ return true;
+ return false;
+}
+
+/* Sort allocnos according to their order in regno allocno list. */
+static int
+regno_allocno_order_compare_func (const void *v1p, const void *v2p)
+{
+ ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
+ ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
+ ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
+ ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
+
+ if (loop_is_inside_p (n1, n2))
+ return -1;
+ else if (loop_is_inside_p (n2, n1))
+ return 1;
+ /* If allocnos are equally good, sort by allocno numbers, so that
+ the results of qsort leave nothing to chance. We put allocnos
+ with higher number first in the list because it is the original
+ order for allocnos from loops on the same levels. */
+ return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
+}
+
+/* This array is used to sort allocnos to restore allocno order in
+ the regno allocno list. */
+static ira_allocno_t *regno_allocnos;
+
+/* Restore allocno order for REGNO in the regno allocno list. */
+static void
+ira_rebuild_regno_allocno_list (int regno)
+{
+ int i, n;
+ ira_allocno_t a;
+
+ for (n = 0, a = ira_regno_allocno_map[regno];
+ a != NULL;
+ a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
+ regno_allocnos[n++] = a;
+ ira_assert (n > 0);
+ qsort (regno_allocnos, n, sizeof (ira_allocno_t),
+ regno_allocno_order_compare_func);
+ for (i = 1; i < n; i++)
+ ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
+ ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
+ ira_regno_allocno_map[regno] = regno_allocnos[0];
+ if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
+}
+