re PR middle-end/37790 (limits-fnargs.c takes very long time to compile at -O2)

2008-11-15  Vladimir Makarov  <vmakarov@redhat.com>

	PR bootstrap/37790
	* ira-int.h (ira_copy_allocno_live_range_list,
	ira_merge_allocno_live_ranges,
	ira_allocno_live_ranges_intersect_p,
	ira_finish_allocno_live_range_list): New prototypes.
	(ira_allocno_live_ranges_intersect_p,
	ira_pseudo_live_ranges_intersect_p): Remove.
	
	* ira-conflicts.c (ira_allocno_live_ranges_intersect_p,
	ira_pseudo_live_ranges_intersect_p): Rename to
	allocnos_have_intersected_live_ranges_p and
	pseudos_have_intersected_live_ranges_p.  Move them from here to
	...

	* ira-color.c: ... here
	(coalesced_allocno_conflict_p): Use
	allocnos_have_intersected_live_ranges_p.
	(coalesced_allocnos_living_at_program_points,
	coalesced_allocnos_live_at_points_p,
	set_coalesced_allocnos_live_points): Remove.
	(slot_coalesced_allocnos_live_ranges,
	slot_coalesced_allocno_live_ranges_intersect_p,
	setup_slot_coalesced_allocno_live_ranges): New.
	(coalesce_spill_slots): Use ranges of coalesced allocnos.
	(ira_sort_regnos_for_alter_reg): Use
	allocnos_have_intersected_live_ranges_p.
	(ira_reuse_stack_slot): Use
	pseudos_have_intersected_live_ranges_p.

	* global.c (pseudo_for_reload_consideration_p): Check
	flag_ira_share_spill_slots too.

	* ira-build.c (copy_allocno_live_range_list): Rename to
	ira_copy_allocno_live_range_list.  Make it external.
	(merge_ranges): Rename to ira_merge_allocno_live_ranges.  Make it
	external.
	(ira_allocno_live_ranges_intersect_p): New.
	(ira_finish_allocno_live_range_list): New.
	(finish_allocno): Use it.
	(remove_unnecessary_allocnos): Use ira_merge_allocno_live_ranges.
	(copy_info_to_removed_store_destinations): Ditto.  Use
	ira_copy_allocno_live_range_list.
	(ira_flattening): Use ira_merge_allocno_live_ranges.
	
	* ira.c (too_high_register_pressure_p): New function.
	(ira): Switch off sharing spill slots if the pressure is too high.

From-SVN: r142017

1 files changed, 119 insertions, 91 deletions

diff --git a/gcc/ira-build.c b/gcc/ira-build.c
index 110da63..af1d174 100644
--- a/gcc/ira-build.c
+++ b/gcc/ira-build.c
@@ -826,8 +826,8 @@ copy_allocno_live_range (allocno_live_range_t r)
 
 /* Copy allocno live range list given by its head R and return the
    result.  */
-static allocno_live_range_t
-copy_allocno_live_range_list (allocno_live_range_t r)
+allocno_live_range_t
+ira_copy_allocno_live_range_list (allocno_live_range_t r)
 {
   allocno_live_range_t p, first, last;
 
@@ -845,6 +845,103 @@ copy_allocno_live_range_list (allocno_live_range_t r)
   return first;
 }
 
+/* Merge ranges R1 and R2 and returns the result.  The function
+   maintains the order of ranges and tries to minimize number of the
+   result ranges.  */
+allocno_live_range_t 
+ira_merge_allocno_live_ranges (allocno_live_range_t r1,
+			       allocno_live_range_t r2)
+{
+  allocno_live_range_t first, last, temp;
+
+  if (r1 == NULL)
+    return r2;
+  if (r2 == NULL)
+    return r1;
+  for (first = last = NULL; r1 != NULL && r2 != NULL;)
+    {
+      if (r1->start < r2->start)
+	{
+	  temp = r1;
+	  r1 = r2;
+	  r2 = temp;
+	}
+      if (r1->start <= r2->finish + 1)
+	{
+	  /* Intersected ranges: merge r1 and r2 into r1.  */
+	  r1->start = r2->start;
+	  if (r1->finish < r2->finish)
+	    r1->finish = r2->finish;
+	  temp = r2;
+	  r2 = r2->next;
+	  ira_finish_allocno_live_range (temp);
+	  if (r2 == NULL)
+	    {
+	      /* To try to merge with subsequent ranges in r1.  */
+	      r2 = r1->next;
+	      r1->next = NULL;
+	    }
+	}
+      else
+	{
+	  /* Add r1 to the result.  */
+	  if (first == NULL)
+	    first = last = r1;
+	  else
+	    {
+	      last->next = r1;
+	      last = r1;
+	    }
+	  r1 = r1->next;
+	  if (r1 == NULL)
+	    {
+	      /* To try to merge with subsequent ranges in r2.  */
+	      r1 = r2->next;
+	      r2->next = NULL;
+	    }
+	}
+    }
+  if (r1 != NULL)
+    {
+      if (first == NULL)
+	first = r1;
+      else
+	last->next = r1;
+      ira_assert (r1->next == NULL);
+    }
+  else if (r2 != NULL)
+    {
+      if (first == NULL)
+	first = r2;
+      else
+	last->next = r2;
+      ira_assert (r2->next == NULL);
+    }
+  else
+    {
+      ira_assert (last->next == NULL);
+    }
+  return first;
+}
+
+/* Return TRUE if live ranges R1 and R2 intersect.  */
+bool
+ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1,
+				     allocno_live_range_t r2)
+{
+  /* Remember the live ranges are always kept ordered.  */
+  while (r1 != NULL && r2 != NULL)
+    {
+      if (r1->start > r2->finish)
+	r1 = r1->next;
+      else if (r2->start > r1->finish)
+	r2 = r2->next;
+      else
+	return true;
+    }
+  return false;
+}
+
 /* Free allocno live range R.  */
 void
 ira_finish_allocno_live_range (allocno_live_range_t r)
@@ -852,6 +949,19 @@ ira_finish_allocno_live_range (allocno_live_range_t r)
   pool_free (allocno_live_range_pool, r);
 }
 
+/* Free list of allocno live ranges starting with R.  */
+void
+ira_finish_allocno_live_range_list (allocno_live_range_t r)
+{
+  allocno_live_range_t next_r;
+
+  for (; r != NULL; r = next_r)
+    {
+      next_r = r->next;
+      ira_finish_allocno_live_range (r);
+    }
+}
+
 /* Free updated register costs of allocno A.  */
 void
 ira_free_allocno_updated_costs (ira_allocno_t a)
@@ -872,7 +982,6 @@ ira_free_allocno_updated_costs (ira_allocno_t a)
 static void
 finish_allocno (ira_allocno_t a)
 {
-  allocno_live_range_t r, next_r;
   enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
 
   ira_allocnos[ALLOCNO_NUM (a)] = NULL;
@@ -888,11 +997,7 @@ finish_allocno (ira_allocno_t a)
   if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
     ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
 			  cover_class);
-  for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = next_r)
-    {
-      next_r = r->next;
-      ira_finish_allocno_live_range (r);
-    }
+  ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
   pool_free (allocno_pool, a);
 }
 
@@ -1543,84 +1648,6 @@ create_allocnos (void)
    will hardly improve the result.  As a result we speed up regional
    register allocation.  */
 
-/* Merge ranges R1 and R2 and returns the result.  The function
-   maintains the order of ranges and tries to minimize number of the
-   result ranges.  */
-static allocno_live_range_t 
-merge_ranges (allocno_live_range_t r1, allocno_live_range_t r2)
-{
-  allocno_live_range_t first, last, temp;
-
-  if (r1 == NULL)
-    return r2;
-  if (r2 == NULL)
-    return r1;
-  for (first = last = NULL; r1 != NULL && r2 != NULL;)
-    {
-      if (r1->start < r2->start)
-	{
-	  temp = r1;
-	  r1 = r2;
-	  r2 = temp;
-	}
-      if (r1->start <= r2->finish + 1)
-	{
-	  /* Intersected ranges: merge r1 and r2 into r1.  */
-	  r1->start = r2->start;
-	  if (r1->finish < r2->finish)
-	    r1->finish = r2->finish;
-	  temp = r2;
-	  r2 = r2->next;
-	  ira_finish_allocno_live_range (temp);
-	  if (r2 == NULL)
-	    {
-	      /* To try to merge with subsequent ranges in r1.  */
-	      r2 = r1->next;
-	      r1->next = NULL;
-	    }
-	}
-      else
-	{
-	  /* Add r1 to the result.  */
-	  if (first == NULL)
-	    first = last = r1;
-	  else
-	    {
-	      last->next = r1;
-	      last = r1;
-	    }
-	  r1 = r1->next;
-	  if (r1 == NULL)
-	    {
-	      /* To try to merge with subsequent ranges in r2.  */
-	      r1 = r2->next;
-	      r2->next = NULL;
-	    }
-	}
-    }
-  if (r1 != NULL)
-    {
-      if (first == NULL)
-	first = r1;
-      else
-	last->next = r1;
-      ira_assert (r1->next == NULL);
-    }
-  else if (r2 != NULL)
-    {
-      if (first == NULL)
-	first = r2;
-      else
-	last->next = r2;
-      ira_assert (r2->next == NULL);
-    }
-  else
-    {
-      ira_assert (last->next == NULL);
-    }
-  return first;
-}
-
 /* The function changes allocno in range list given by R onto A.  */
 static void
 change_allocno_in_range_list (allocno_live_range_t r, ira_allocno_t a)
@@ -1762,7 +1789,8 @@ remove_unnecessary_allocnos (void)
 		r = ALLOCNO_LIVE_RANGES (a);
 		change_allocno_in_range_list (r, parent_a);
 		ALLOCNO_LIVE_RANGES (parent_a)
-		  = merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
+		  = ira_merge_allocno_live_ranges
+		    (r, ALLOCNO_LIVE_RANGES (parent_a));
 		merged_p = true;
 		ALLOCNO_LIVE_RANGES (a) = NULL;
 		IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a),
@@ -2155,10 +2183,10 @@ copy_info_to_removed_store_destinations (int regno)
 	  ira_print_live_range_list (ira_dump_file,
 				     ALLOCNO_LIVE_RANGES (a));
 	}
-      r = copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
+      r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
       change_allocno_in_range_list (r, parent_a);
       ALLOCNO_LIVE_RANGES (parent_a)
-	= merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
+	= ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
       IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
 			ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
 #ifdef STACK_REGS
@@ -2255,8 +2283,8 @@ ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 		}
 	      change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
 	      ALLOCNO_LIVE_RANGES (parent_a)
-		= merge_ranges (ALLOCNO_LIVE_RANGES (a),
-				ALLOCNO_LIVE_RANGES (parent_a));
+		= ira_merge_allocno_live_ranges
+		  (ALLOCNO_LIVE_RANGES (a), ALLOCNO_LIVE_RANGES (parent_a));
 	      merged_p = true;
 	      ALLOCNO_LIVE_RANGES (a) = NULL;
 	      ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)