2008-05-18 Vladimir Makarov <vmakarov@redhat.com>

	PR tree-optimization/26854

	* timevar.def (TV_RELOAD): New timer.

	* ira.c (ira): Use TV_IRA and TV_RELOAD.
	(pass_ira): Remove TV_IRA.

	* Makefile.in (ira-color.o): Add SPLAY_TREE_H.

	* ira-conflicts.c (DEF_VEC_P, DEF_ALLOCC_P): Move to ira-int.h.

	* ira-int.h (DEF_VEC_P, DEF_ALLOCC_P): Move from ira-conflicts.c and
	ira-color.c.
	(struct allocno): New bitfield splay_removed_p.
	(ALLOCNO_MAY_BE_SPILLED_P): New macro.

	* ira-color.c (splay-tree.h): Add the header.
	(allocno_spill_priority_compare, splay_tree_allocate,
	splay_tree_free): New functions.
	(DEF_VEC_P, DEF_ALLOCC_P): Move to ira-int.h.
	(sorted_allocnos_for_spilling): Rename to allocnos_for_spilling.
	(splay_tree_node_pool, removed_splay_allocno_vec,
	uncolorable_allocnos_num, uncolorable_allocnos_splay_tree): New
	global variables.
	(add_allocno_to_bucket, add_allocno_to_ordered_bucket,
	delete_allocno_from_bucket): Update uncolorable_allocnos_num.
	(USE_SPLAY_P): New macro.
	(push_allocno_to_stack): Remove allocno from the splay tree.
	(push_allocnos_to_stack): Use the splay trees.
	(do_coloring): Create and finish splay_tree_node_pool.
	Move allocation/deallocation of allocnos_for_spilling to here...
	(initiate_ira_assign, finish_ira_assign): Move
	allocnos_for_spilling from here...
	(ira_color): Allocate/deallocate removed_splay_allocno_vec.

	* ira-build.c (DEF_VEC_P, DEF_ALLOCC_P): Move to ira-int.h.
	(create_allocno): Initiate ALLOCNO_SPLAY_REMOVED_P.



git-svn-id: https://gcc.gnu.org/svn/gcc/branches/ira@135523 138bc75d-0d04-0410-961f-82ee72b054a4

8 files changed, 331 insertions, 98 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a1d181d70f9..08679e67f5f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,42 @@
+2008-05-18  Vladimir Makarov  <vmakarov@redhat.com>
+	PR tree-optimization/26854
+
+	* timevar.def (TV_RELOAD): New timer.
+
+	* ira.c (ira): Use TV_IRA and TV_RELOAD.
+	(pass_ira): Remove TV_IRA.
+
+	* Makefile.in (ira-color.o): Add SPLAY_TREE_H.
+
+	* ira-conflicts.c (DEF_VEC_P, DEF_ALLOCC_P): Move to ira-int.h.
+
+	* ira-int.h (DEF_VEC_P, DEF_ALLOCC_P): Move from ira-conflicts.c and
+	ira-color.c.
+	(struct allocno): New bitfield splay_removed_p.
+	(ALLOCNO_MAY_BE_SPILLED_P): New macro.
+
+	* ira-color.c (splay-tree.h): Add the header.
+	(allocno_spill_priority_compare, splay_tree_allocate,
+	splay_tree_free): New functions.
+	(DEF_VEC_P, DEF_ALLOCC_P): Move to ira-int.h.
+	(sorted_allocnos_for_spilling): Rename to allocnos_for_spilling.
+	(splay_tree_node_pool, removed_splay_allocno_vec,
+	uncolorable_allocnos_num, uncolorable_allocnos_splay_tree): New
+	global variables.
+	(add_allocno_to_bucket, add_allocno_to_ordered_bucket,
+	delete_allocno_from_bucket): Update uncolorable_allocnos_num.
+	(USE_SPLAY_P): New macro.
+	(push_allocno_to_stack): Remove allocno from the splay tree.
+	(push_allocnos_to_stack): Use the splay trees.
+	(do_coloring): Create and finish splay_tree_node_pool.
+	Move allocation/deallocation of allocnos_for_spilling to here...
+	(initiate_ira_assign, finish_ira_assign): Move
+	allocnos_for_spilling from here...
+	(ira_color): Allocate/deallocate removed_splay_allocno_vec.
+
+	* ira-build.c (DEF_VEC_P, DEF_ALLOCC_P): Move to ira-int.h.
+	(create_allocno): Initiate ALLOCNO_SPLAY_REMOVED_P.
+	
 2008-05-12  Vladimir Makarov  <vmakarov@redhat.com>
 
 	* Makefile.in (ira-build.o): Add sparseset.h.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 58b84c6db22..631e4c42ea9 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2803,7 +2803,7 @@ ira-conflicts.o: ira-conflicts.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
 ira-color.o: ira-color.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TARGET_H) $(RTL_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) \
    $(EXPR_H) $(BASIC_BLOCK_H) toplev.h $(TM_P_H) $(PARAMS_H) \
-   $(DF_H) $(IRA_INT_H)
+   $(DF_H) $(SPLAY_TREE_H) $(IRA_INT_H)
 ira-emit.o: ira-emit.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TARGET_H) $(RTL_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) \
    $(EXPR_H) $(BASIC_BLOCK_H) toplev.h $(TM_P_H) $(PARAMS_H) \
diff --git a/gcc/ira-build.c b/gcc/ira-build.c
index 6d19f0ec369..cbc379f9e46 100644
--- a/gcc/ira-build.c
+++ b/gcc/ira-build.c
@@ -505,10 +505,6 @@ finish_calls (void)
 /* Pools for allocnos and allocno live ranges.  */
 static alloc_pool allocno_pool, allocno_live_range_pool;
 
-/* Definition of vector of allocnos.  */
-DEF_VEC_P(allocno_t);
-DEF_VEC_ALLOC_P(allocno_t, heap);
-
 /* Vec containing references to all created allocnos.  It is a
    container of array allocnos.  */
 static VEC(allocno_t,heap) *allocno_vec;
@@ -581,6 +577,7 @@ create_allocno (int regno, int cap_p, loop_tree_node_t loop_tree_node)
   ALLOCNO_IN_GRAPH_P (a) = FALSE;
   ALLOCNO_ASSIGNED_P (a) = FALSE;
   ALLOCNO_MAY_BE_SPILLED_P (a) = FALSE;
+  ALLOCNO_SPLAY_REMOVED_P (a) = FALSE;
   ALLOCNO_CONFLICT_VEC_P (a) = FALSE;
   ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
   ALLOCNO_COPIES (a) = NULL;
@@ -1114,10 +1111,6 @@ finish_allocnos (void)
 /* Pools for copies.  */
 static alloc_pool copy_pool;
 
-/* Definition of vector of copies.  */
-DEF_VEC_P(copy_t);
-DEF_VEC_ALLOC_P(copy_t, heap);
-
 /* Vec containing references to all created copies.  It is a
    container of array copies.  */
 static VEC(copy_t,heap) *copy_vec;
diff --git a/gcc/ira-color.c b/gcc/ira-color.c
index 18be6acfa26..edbe4c0127b 100644
--- a/gcc/ira-color.c
+++ b/gcc/ira-color.c
@@ -37,6 +37,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "reload.h"
 #include "params.h"
 #include "df.h"
+#include "splay-tree.h"
 #include "ira-int.h"
 
 /* This file contains code for regional graph coloring, spill/restore
@@ -62,6 +63,9 @@ static void remove_allocno_from_bucket_and_push (allocno_t, int);
 static void push_only_colorable (void);
 static void push_allocno_to_spill (allocno_t);
 static int calculate_allocno_spill_cost (allocno_t);
+static int allocno_spill_priority_compare (splay_tree_key, splay_tree_key);
+static void *splay_tree_allocate (int, void *);
+static void splay_tree_free (void *, void *);
 static void push_allocnos_to_stack (void);
 static void pop_allocnos_from_stack (void);
 static void setup_allocno_available_regs_num (allocno_t);
@@ -116,16 +120,23 @@ static bitmap processed_coalesced_allocno_bitmap;
 /* All allocnos sorted according their priorities.  */
 static allocno_t *sorted_allocnos;
 
-/* Array used to sort allocnos to choose an allocno for spilling.  */
-static allocno_t *sorted_allocnos_for_spilling;
-
-/* Definition of vector of allocnos.  */
-DEF_VEC_P(allocno_t);
-DEF_VEC_ALLOC_P(allocno_t, heap);
-
 /* Vec representing the stack of allocnos used during coloring.  */
 static VEC(allocno_t,heap) *allocno_stack_vec;
 
+/* Array used to choose an allocno for spilling.  */
+static allocno_t *allocnos_for_spilling;
+
+/* Pool for splay tree nodes.  */
+static alloc_pool splay_tree_node_pool;
+
+/* When an allocno is removed from the splay tree, it is put in the
+   following vector for subsequent inserting it into the splay tree
+   after putting all colorable allocnos onto the stack.  The allocno
+   could be removed from and inserted to the splay tree every time
+   when its spilling priority is changed but such solution would be
+   more costly although simpler.  */
+static VEC(allocno_t,heap) *removed_splay_allocno_vec;
+
 
 
 /* This page contains functions used to choose hard registers for
@@ -518,13 +529,24 @@ static allocno_t colorable_allocno_bucket;
    spilling.  */
 static allocno_t uncolorable_allocno_bucket;
 
+/* Each element of the array contains the current number of allocnos
+   of given *cover* class in the uncolorable_bucket.  */
+static int uncolorable_allocnos_num[N_REG_CLASSES];
+
 /* Add ALLOCNO to bucket *BUCKET_PTR.  ALLOCNO should be not in a bucket
    before the call.  */
 static void
 add_allocno_to_bucket (allocno_t allocno, allocno_t *bucket_ptr)
 {
   allocno_t first_allocno;
+  enum reg_class cover_class;
 
+  if (bucket_ptr == &uncolorable_allocno_bucket
+      && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
+    {
+      uncolorable_allocnos_num[cover_class]++;
+      ira_assert (uncolorable_allocnos_num[cover_class] > 0);
+    }
   first_allocno = *bucket_ptr;
   ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
   ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
@@ -610,7 +632,14 @@ static void
 add_allocno_to_ordered_bucket (allocno_t allocno, allocno_t *bucket_ptr)
 {
   allocno_t before, after;
+  enum reg_class cover_class;
 
+  if (bucket_ptr == &uncolorable_allocno_bucket
+      && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
+    {
+      uncolorable_allocnos_num[cover_class]++;
+      ira_assert (uncolorable_allocnos_num[cover_class] > 0);
+    }
   for (before = *bucket_ptr, after = NULL;
        before != NULL;
        after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
@@ -632,7 +661,14 @@ static void
 delete_allocno_from_bucket (allocno_t allocno, allocno_t *bucket_ptr)
 {
   allocno_t prev_allocno, next_allocno;
+  enum reg_class cover_class;
 
+  if (bucket_ptr == &uncolorable_allocno_bucket
+      && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
+    {
+      uncolorable_allocnos_num[cover_class]--;
+      ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
+    }
   prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
   next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
   if (prev_allocno != NULL)
@@ -646,6 +682,21 @@ delete_allocno_from_bucket (allocno_t allocno, allocno_t *bucket_ptr)
     ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
 }
 
+/* Splay tree for each cover class.  The trees are indexed by the
+   corresponding cover classes.  Splay trees contain uncolorable
+   allocnos.  */
+static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
+
+/* If the following macro is TRUE, splay tree is used to choose an
+   allocno of the corresponding cover class for spilling.  When the
+   number uncolorable allocnos of given cover class decreases to some
+   threshold, linear array search is used to find the best allocno for
+   spilling.  This threshold is actually pretty big because, although
+   splay trees asymptotically is much faster, each splay tree
+   operation is sufficiently costly especially taking cache locality
+   into account.  */
+#define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
+
 /* The function puts ALLOCNO onto the coloring stack without removing
    it from its bucket.  Pushing allocno to the coloring stack can
    result in moving conflicting allocnos from the uncolorable bucket
@@ -691,16 +742,35 @@ push_allocno_to_stack (allocno_t allocno)
 		     [cover_class][ALLOCNO_MODE (conflict_allocno)]);
 		ira_assert
 		  (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
-		ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
 		if (conflicts_num + conflict_size
 		    <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
-		  continue;
-		conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
+		  {
+		    ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
+		    continue;
+		  }
+		conflicts_num
+		  = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
+		if (uncolorable_allocnos_splay_tree[cover_class] != NULL
+		    && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
+		    && USE_SPLAY_P (cover_class))
+		  {
+		    ira_assert
+		      (splay_tree_lookup
+		       (uncolorable_allocnos_splay_tree[cover_class],
+			(splay_tree_key) conflict_allocno) != NULL);
+		    splay_tree_remove
+		      (uncolorable_allocnos_splay_tree[cover_class],
+		       (splay_tree_key) conflict_allocno);
+		    ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = TRUE;
+		    VEC_safe_push (allocno_t, heap, removed_splay_allocno_vec,
+				   conflict_allocno);
+		  }
+		ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
 		if (conflicts_num + conflict_size
 		    <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
 		  {
-		    delete_allocno_from_bucket
-		      (conflict_allocno, &uncolorable_allocno_bucket);
+		    delete_allocno_from_bucket (conflict_allocno,
+						&uncolorable_allocno_bucket);
 		    add_allocno_to_ordered_bucket (conflict_allocno,
 						   &colorable_allocno_bucket);
 		  }
@@ -718,11 +788,11 @@ static void
 remove_allocno_from_bucket_and_push (allocno_t allocno, int colorable_p)
 {
   enum reg_class cover_class;
-  allocno_t *bucket_ptr;
 
-  bucket_ptr = (colorable_p
-		? &colorable_allocno_bucket : &uncolorable_allocno_bucket);
-  delete_allocno_from_bucket (allocno, bucket_ptr);
+  if (colorable_p)
+    delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
+  else
+    delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
   if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
     {
       fprintf (ira_dump_file, "      Pushing");
@@ -840,19 +910,73 @@ calculate_allocno_spill_cost (allocno_t a)
   return cost;
 }
 
+/* The function is used to compare keys in the splay tree used to
+   choose best allocno for spilling.  The best allocno has the minimal
+   key.  */
+static int
+allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
+{
+  int pri1, pri2, diff;
+  allocno_t a1 = (allocno_t) k1, a2 = (allocno_t) k2;
+  
+  pri1 = (ALLOCNO_TEMP (a1)
+	  / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
+	     * reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
+	     + 1));
+  pri2 = (ALLOCNO_TEMP (a2)
+	  / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
+	     * reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
+	     + 1));
+  if ((diff = pri1 - pri2) != 0)
+    return diff;
+  if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
+    return diff;
+  return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
+}
+
+/* The function is used to allocate data of SIZE for the splay trees.
+   We allocate only spay tree roots or splay tree nodes.  If you
+   change this, please rewrite the function.  */
+static void *
+splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
+{
+  if (size != sizeof (struct splay_tree_node_s))
+    return ira_allocate (size);
+  return pool_alloc (splay_tree_node_pool);
+}
+
+/* The function is used to free data NODE for the splay trees.  We
+   allocate and free only spay tree roots or splay tree nodes.  If you
+   change this, please rewrite the function.  */
+static void
+splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
+{
+  int i;
+  enum reg_class cover_class;
+
+  for (i = 0; i < reg_class_cover_size; i++)
+    {
+      cover_class = reg_class_cover[i];
+      if (node == uncolorable_allocnos_splay_tree[cover_class])
+	{
+	  ira_free (node);
+	  return;
+	}
+    }
+  pool_free (splay_tree_node_pool, node);
+}
+
 /* Push allocnos to the coloring stack.  The order of allocnos in the
    stack defines the order for the subsequent coloring.  */
 static void
 push_allocnos_to_stack (void)
 {
-  int i, j;
-  int allocno_pri, i_allocno_pri;
-  int allocno_cost, i_allocno_cost;
-  allocno_t allocno, i_allocno;
-  allocno_t *allocno_vec;
-  enum reg_class cover_class;
-  int num, cover_class_allocnos_num[N_REG_CLASSES];
+  allocno_t allocno, a, i_allocno, *allocno_vec;
+  enum reg_class cover_class, class;
+  int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
+  int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
   allocno_t *cover_class_allocnos[N_REG_CLASSES];
+  int cost;
 
   /* Initialize.  */
   for (i = 0; i < reg_class_cover_size; i++)
@@ -860,37 +984,60 @@ push_allocnos_to_stack (void)
       cover_class = reg_class_cover[i];
       cover_class_allocnos_num[cover_class] = 0;
       cover_class_allocnos[cover_class] = NULL;
+      uncolorable_allocnos_splay_tree[cover_class] = NULL;
     }
-  /* Calculate uncolorable allocnos of each cover class.  */
+  /* Calculate uncolorable allocno spill costs.  */
   for (allocno = uncolorable_allocno_bucket;
        allocno != NULL;
        allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
     if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
       {
 	cover_class_allocnos_num[cover_class]++;
-	ALLOCNO_TEMP (allocno) = INT_MAX;
+	cost = 0;
+	for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
+	     a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+	  {
+	    cost += calculate_allocno_spill_cost (a);
+	    if (a == allocno)
+	      break;
+	  }
+	/* ??? Remove cost of copies between the coalesced
+	   allocnos.  */
+	ALLOCNO_TEMP (allocno) = cost;
       }
   /* Define place where to put uncolorable allocnos of the same cover
      class.  */
   for (num = i = 0; i < reg_class_cover_size; i++)
     {
       cover_class = reg_class_cover[i];
+      ira_assert (cover_class_allocnos_num[cover_class]
+		  == uncolorable_allocnos_num[cover_class]);
       if (cover_class_allocnos_num[cover_class] != 0)
-	{
-	  cover_class_allocnos[cover_class]
-	    = sorted_allocnos_for_spilling + num;
+ 	{
+	  cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
 	  num += cover_class_allocnos_num[cover_class];
 	  cover_class_allocnos_num[cover_class] = 0;
 	}
+      if (USE_SPLAY_P (cover_class))
+	uncolorable_allocnos_splay_tree[cover_class]
+	  = splay_tree_new_with_allocator (allocno_spill_priority_compare,
+					   NULL, NULL, splay_tree_allocate,
+					   splay_tree_free, NULL);
     }
   ira_assert (num <= allocnos_num);
-  /* Put uncolorable allocnos of the same cover class together.  */
+  /* Collect uncolorable allocnos of each cover class.  */
   for (allocno = uncolorable_allocno_bucket;
        allocno != NULL;
        allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
     if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
-      cover_class_allocnos
-	[cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
+      {
+	cover_class_allocnos
+	  [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
+	if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
+	  splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
+			     (splay_tree_key) allocno,
+			     (splay_tree_value) allocno);
+      }
   for (;;)
     {
       push_only_colorable ();
@@ -905,65 +1052,88 @@ push_allocnos_to_stack (void)
 	}
       /* Potential spilling.  */
       ira_assert (reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
-      num = cover_class_allocnos_num[cover_class];
-      ira_assert (num > 0);
-      allocno_vec = cover_class_allocnos[cover_class];
-      allocno = NULL;
-      allocno_pri = allocno_cost = 0;
-      /* Sort uncolorable allocno to find the one with the lowest spill
-	 cost.  */
-      for (i = 0, j = num - 1; i <= j;)
+      if (USE_SPLAY_P (cover_class))
 	{
-	  i_allocno = allocno_vec[i];
-	  if (! ALLOCNO_IN_GRAPH_P (i_allocno)
-	      && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
+	  for (;VEC_length (allocno_t, removed_splay_allocno_vec) != 0;)
 	    {
-	      i_allocno = allocno_vec[j];
-	      allocno_vec[j] = allocno_vec[i];
-	      allocno_vec[i] = i_allocno;
+	      allocno = VEC_pop (allocno_t, removed_splay_allocno_vec);
+	      ALLOCNO_SPLAY_REMOVED_P (allocno) = FALSE;
+	      class = ALLOCNO_COVER_CLASS (allocno);
+	      if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
+		  + reg_class_nregs [class][ALLOCNO_MODE (allocno)]
+		  > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
+		splay_tree_insert
+		  (uncolorable_allocnos_splay_tree[class],
+		   (splay_tree_key) allocno, (splay_tree_value) allocno);
 	    }
-	  if (ALLOCNO_IN_GRAPH_P (i_allocno))
+	  allocno = ((allocno_t)
+		     splay_tree_min
+		     (uncolorable_allocnos_splay_tree[cover_class])->key);
+	  splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
+			     (splay_tree_key) allocno);
+	}
+      else
+	{
+	  num = cover_class_allocnos_num[cover_class];
+	  ira_assert (num > 0);
+	  allocno_vec = cover_class_allocnos[cover_class];
+	  allocno = NULL;
+	  allocno_pri = allocno_cost = 0;
+	  /* Sort uncolorable allocno to find the one with the lowest
+	     spill cost.  */
+	  for (i = 0, j = num - 1; i <= j;)
 	    {
-	      i++;
-	      if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
+	      i_allocno = allocno_vec[i];
+	      if (! ALLOCNO_IN_GRAPH_P (i_allocno)
+		  && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
 		{
-		  allocno_t a;
-		  int cost = 0;
-
-		  for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
-		       a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
-		    {
-		      cost += calculate_allocno_spill_cost (i_allocno);
-		      if (a == i_allocno)
-			break;
-		    }
-		  /* ??? Remove cost of copies between the coalesced
-		     allocnos.  */
-		  ALLOCNO_TEMP (i_allocno) = cost;
+		  i_allocno = allocno_vec[j];
+		  allocno_vec[j] = allocno_vec[i];
+		  allocno_vec[i] = i_allocno;
 		}
-	      i_allocno_cost = ALLOCNO_TEMP (i_allocno);
-	      i_allocno_pri
-		= (i_allocno_cost
-		   / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
-		      * reg_class_nregs[ALLOCNO_COVER_CLASS (i_allocno)]
-		                       [ALLOCNO_MODE (i_allocno)] + 1));
-	      if (allocno == NULL || allocno_pri > i_allocno_pri
-		  || (allocno_pri == i_allocno_pri
-		      && (allocno_cost > i_allocno_cost
-			  || (allocno_cost == i_allocno_cost 
-			      && (ALLOCNO_NUM (allocno)
-				  > ALLOCNO_NUM (i_allocno))))))
+	      if (ALLOCNO_IN_GRAPH_P (i_allocno))
 		{
-		  allocno = i_allocno;
-		  allocno_cost = i_allocno_cost;
-		  allocno_pri = i_allocno_pri;
+		  i++;
+		  if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
+		    {
+		      allocno_t a;
+		      int cost = 0;
+		      
+		      for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
+			   a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
+			{
+			  cost += calculate_allocno_spill_cost (i_allocno);
+			  if (a == i_allocno)
+			    break;
+			}
+		      /* ??? Remove cost of copies between the coalesced
+			 allocnos.  */
+		      ALLOCNO_TEMP (i_allocno) = cost;
+		    }
+		  i_allocno_cost = ALLOCNO_TEMP (i_allocno);
+		  i_allocno_pri
+		    = (i_allocno_cost
+		       / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
+			  * reg_class_nregs[ALLOCNO_COVER_CLASS (i_allocno)]
+			  [ALLOCNO_MODE (i_allocno)] + 1));
+		  if (allocno == NULL || allocno_pri > i_allocno_pri
+		      || (allocno_pri == i_allocno_pri
+			  && (allocno_cost > i_allocno_cost
+			      || (allocno_cost == i_allocno_cost 
+				  && (ALLOCNO_NUM (allocno)
+				      > ALLOCNO_NUM (i_allocno))))))
+		    {
+		      allocno = i_allocno;
+		      allocno_cost = i_allocno_cost;
+		      allocno_pri = i_allocno_pri;
+		    }
 		}
+	      if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
+		j--;
 	    }
-	  if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
-	    j--;
+	  ira_assert (allocno != NULL && j >= 0);
+	  cover_class_allocnos_num[cover_class] = j + 1;
 	}
-      ira_assert (allocno != NULL && j >= 0);
-      cover_class_allocnos_num[cover_class] = j + 1;
       ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
 		  && ALLOCNO_COVER_CLASS (allocno) == cover_class
 		  && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
@@ -971,6 +1141,15 @@ push_allocnos_to_stack (void)
 		      > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
       remove_allocno_from_bucket_and_push (allocno, FALSE);
     }
+  ira_assert (colorable_allocno_bucket == NULL
+	      && uncolorable_allocno_bucket == NULL);
+  for (i = 0; i < reg_class_cover_size; i++)
+    {
+      cover_class = reg_class_cover[i];
+      ira_assert (uncolorable_allocnos_num[cover_class] == 0);
+      if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
+	splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
+    }
 }
 
 /* Pop the coloring stack and assign hard registers to the popped
@@ -1608,7 +1787,10 @@ static void
 do_coloring (void)
 {
   coloring_allocno_bitmap = ira_allocate_bitmap ();
-
+  allocnos_for_spilling = ira_allocate (sizeof (allocno_t) * allocnos_num);
+  splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
+					    sizeof (struct splay_tree_node_s),
+					    100);
   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
     fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
   
@@ -1617,7 +1799,9 @@ do_coloring (void)
   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
     print_disposition (ira_dump_file);
 
+  free_alloc_pool (splay_tree_node_pool);
   ira_free_bitmap (coloring_allocno_bitmap);
+  ira_free (allocnos_for_spilling);
 }
 
 
@@ -2705,8 +2889,6 @@ void
 initiate_ira_assign (void)
 {
   sorted_allocnos = ira_allocate (sizeof (allocno_t) * allocnos_num);
-  sorted_allocnos_for_spilling
-    = ira_allocate (sizeof (allocno_t) * allocnos_num);
   consideration_allocno_bitmap = ira_allocate_bitmap ();
   initiate_cost_update ();
   allocno_priorities = ira_allocate (sizeof (int) * allocnos_num);
@@ -2716,7 +2898,6 @@ initiate_ira_assign (void)
 void
 finish_ira_assign (void)
 {
-  ira_free (sorted_allocnos_for_spilling);
   ira_free (sorted_allocnos);
   ira_free_bitmap (consideration_allocno_bitmap);
   finish_cost_update ();
@@ -2730,10 +2911,12 @@ void
 ira_color (void)
 {
   allocno_stack_vec = VEC_alloc (allocno_t, heap, allocnos_num);
+  removed_splay_allocno_vec = VEC_alloc (allocno_t, heap, allocnos_num);
   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
   initiate_ira_assign ();
   do_coloring ();
   finish_ira_assign ();
+  VEC_free (allocno_t, heap, removed_splay_allocno_vec);
   VEC_free (allocno_t, heap, allocno_stack_vec);
   move_spill_restore ();
 }
diff --git a/gcc/ira-conflicts.c b/gcc/ira-conflicts.c
index 46856f59d15..b56d389abc0 100644
--- a/gcc/ira-conflicts.c
+++ b/gcc/ira-conflicts.c
@@ -684,10 +684,6 @@ pseudo_live_ranges_intersect_p (int regno1, int regno2)
   return allocno_live_ranges_intersect_p (a1, a2);
 }
 
-/* Definition of vector of copies.  */
-DEF_VEC_P(copy_t);
-DEF_VEC_ALLOC_P(copy_t, heap);
-
 /* Remove copies involving conflicting allocnos.  We can not do this
    at the copy creation time because there are no conflicts at that
    time yet.  */
diff --git a/gcc/ira-int.h b/gcc/ira-int.h
index b60d913959e..794eb2e6266 100644
--- a/gcc/ira-int.h
+++ b/gcc/ira-int.h
@@ -58,6 +58,12 @@ typedef struct allocno_live_range *allocno_live_range_t;
 typedef struct allocno *allocno_t;
 typedef struct allocno_copy *copy_t;
 
+/* Definition of vector of allocnos and copies.  */
+DEF_VEC_P(allocno_t);
+DEF_VEC_ALLOC_P(allocno_t, heap);
+DEF_VEC_P(copy_t);
+DEF_VEC_ALLOC_P(copy_t, heap);
+
 /* Typedef for pointer to the subsequent structure.  */
 typedef struct loop_tree_node *loop_tree_node_t;
 
@@ -351,6 +357,9 @@ struct allocno
   /* TRUE if it is put on the stack to make other allocnos
      colorable.  */
   unsigned int may_be_spilled_p : 1;
+  /* TRUE if the allocno was removed from the splay tree used to
+     choose allocn for spilling (see ira-color.c::.  */
+  unsigned int splay_removed_p : 1;
   /* TRUE if conflicts for given allocno are represented by vector of
      pointers to the conflicting allocnos.  Otherwise, we use a bit
      vector where a bit with given index represents allocno with the
@@ -427,6 +436,7 @@ struct allocno
 #define ALLOCNO_IN_GRAPH_P(A) ((A)->in_graph_p)
 #define ALLOCNO_ASSIGNED_P(A) ((A)->assigned_p)
 #define ALLOCNO_MAY_BE_SPILLED_P(A) ((A)->may_be_spilled_p)
+#define ALLOCNO_SPLAY_REMOVED_P(A) ((A)->splay_removed_p)
 #define ALLOCNO_CONFLICT_VEC_P(A) ((A)->conflict_vec_p)
 #define ALLOCNO_MODE(A) ((A)->mode)
 #define ALLOCNO_COPIES(A) ((A)->allocno_copies)
diff --git a/gcc/ira.c b/gcc/ira.c
index 03f29a99352..0da26062943 100644
--- a/gcc/ira.c
+++ b/gcc/ira.c
@@ -1764,6 +1764,8 @@ ira (FILE *f)
   int rebuild_p, saved_flag_ira_algorithm;
   basic_block bb;
 
+  timevar_push (TV_IRA);
+
   if (flag_ira_verbose < 10)
     {
       internal_flag_ira_verbose = flag_ira_verbose;
@@ -1933,6 +1935,9 @@ ira (FILE *f)
 	      max_regno * sizeof (struct spilled_reg_stack_slot));
     }
   
+  timevar_pop (TV_IRA);
+
+  timevar_push (TV_RELOAD);
   df_set_flags (DF_NO_INSN_RESCAN);
   build_insn_chain ();
 
@@ -1941,6 +1946,10 @@ ira (FILE *f)
 
   reload_completed = !reload (get_insns (), optimize > 0);
 
+  timevar_pop (TV_RELOAD);
+
+  timevar_push (TV_IRA);
+
   if (optimize)
     {
       ira_free (spilled_reg_stack_slots);
@@ -1989,6 +1998,8 @@ ira (FILE *f)
 
   if (optimize)
     df_analyze ();
+
+  timevar_pop (TV_IRA);
 }
 
 
@@ -2017,7 +2028,7 @@ struct rtl_opt_pass pass_ira =
   NULL,                                 /* sub */
   NULL,                                 /* next */
   0,                                    /* static_pass_number */
-  TV_IRA,	                        /* tv_id */
+  0,		                        /* tv_id */
   0,                                    /* properties_required */
   0,                                    /* properties_provided */
   0,                                    /* properties_destroyed */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 893ce79897a..101cfe882bb 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -177,6 +177,7 @@ DEFTIMEVAR (TV_SCHED                 , "scheduling")
 DEFTIMEVAR (TV_LOCAL_ALLOC           , "local alloc")
 DEFTIMEVAR (TV_GLOBAL_ALLOC          , "global alloc")
 DEFTIMEVAR (TV_IRA	   	     , "integrated RA")
+DEFTIMEVAR (TV_RELOAD	   	     , "reload")
 DEFTIMEVAR (TV_RELOAD_CSE_REGS       , "reload CSE regs")
 DEFTIMEVAR (TV_SEQABSTR              , "sequence abstraction")
 DEFTIMEVAR (TV_GCSE_AFTER_RELOAD      , "load CSE after reload")