2008-08-1 Vladimir Makarov <vmakarov@redhat.com>

	* ira-conflicts.c (process_regs_for_copy): Don't add copy for
	conflicting allocnos.
	(propagate_allocno_copy_info, propagate_copy_info): Remove.
	(propagate_copies): New.
	(collected_conflict_allocnos): New.
	(remove_conflict_allocno_copies): Remove.
	(build_allocno_conflicts): Add parameter.  Build conflicts only
	for one allocno. Check cap too.  Don't free conflict table row.
	(build_conflicts): New.
	(ira_build_conflicts): Build conflicts before adding copies.  Free
	conflict bit table rows.

	* ira-color.c (color_pass): Check cap.  Process caps only once.
	Remove propagation code.
	(move_spill_restore): Check caps and border allocnos.

	* ira-lives.c (propagate_new_allocno_info, propagate_new_info):
	Remove.
	(ira_create_allocno_live_ranges): Don't propagate info of new
	allocnos.

	* ira-emit.c (not_modified_p, update_costs): Check caps.

	* ira-build.c (allocnos_bitmap): Remove.
	(create_cap_allocno): Set up all cap attributes.
	(propagate_info_to_cap): Remove.
	(create_loop_allocnos): Create allocnos in parent for border
	allocnos if there is no one.
	(propagate_allocno_info): New.
	(create_allocnos): Don't propagate allocno info.
	(remove_unnecessary_allocnos): Accumulate all allocno info.
	(setup_min_max_allocno_live_range_point): Set up min/max for caps
	too.
	(create_loop_tree_node_caps): Remove.
	(create_caps): New.
	(propagate_info_to_loop_tree_node_caps): Remove.
	(ira_flattening): Check cap.  Stop decrease call info after
	reaching allocno which is destination of removed store.  Check
	allocno nrefs and freq.
	(calculate_high_pressure_loops): Remove.
	(check_allocno_creation): New.
	(ira_build): Call propagate_allocno_info, call_caps, and
	check_allocno_creation.  Move
	ira_tune_allocno_costs_and_cover_classes before
	setup_min_max_allocno_live_range_point.

	* ira.c: Update comments about IRA.
	(ira_print_disposition): Add comment.

	* ira-costs.c (total_costs): Rename to allocno_costs.
	(total_costs): New.
	(print_costs): Print accumulated costs too.
	(find_allocno_class_costs): Check border allocnos for propagation
	costs.  Setup non-accumulated costs for allocnos.
	(process_bb_node_for_hard_reg_moves): Don't propagate costs.
	(ira_costs): Add allocation/freeing allocno_costs.

	* common.opt (fira-propagate-cost): Remove.

	* doc/invoke.texi (-fira-propagate-cost): Remove.



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

10 files changed, 487 insertions, 603 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4a294ce85c6..12dfa43d25a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,66 @@
+2008-08-1  Vladimir Makarov  <vmakarov@redhat.com>
+
+	* ira-conflicts.c (process_regs_for_copy): Don't add copy for
+	conflicting allocnos.
+	(propagate_allocno_copy_info, propagate_copy_info): Remove.
+	(propagate_copies): New.
+	(collected_conflict_allocnos): New.
+	(remove_conflict_allocno_copies): Remove.
+	(build_allocno_conflicts): Add parameter.  Build conflicts only
+	for one allocno. Check cap too.  Don't free conflict table row.
+	(build_conflicts): New.
+	(ira_build_conflicts): Build conflicts before adding copies.  Free
+	conflict bit table rows.
+
+	* ira-color.c (color_pass): Check cap.  Process caps only once.
+	Remove propagation code.
+	(move_spill_restore): Check caps and border allocnos.
+
+	* ira-lives.c (propagate_new_allocno_info, propagate_new_info):
+	Remove.
+	(ira_create_allocno_live_ranges): Don't propagate info of new
+	allocnos.
+
+	* ira-emit.c (not_modified_p, update_costs): Check caps.
+
+	* ira-build.c (allocnos_bitmap): Remove.
+	(create_cap_allocno): Set up all cap attributes.
+	(propagate_info_to_cap): Remove.
+	(create_loop_allocnos): Create allocnos in parent for border
+	allocnos if there is no one.
+	(propagate_allocno_info): New.
+	(create_allocnos): Don't propagate allocno info.
+	(remove_unnecessary_allocnos): Accumulate all allocno info.
+	(setup_min_max_allocno_live_range_point): Set up min/max for caps
+	too.
+	(create_loop_tree_node_caps): Remove.
+	(create_caps): New.
+	(propagate_info_to_loop_tree_node_caps): Remove.
+	(ira_flattening): Check cap.  Stop decrease call info after
+	reaching allocno which is destination of removed store.  Check
+	allocno nrefs and freq.
+	(calculate_high_pressure_loops): Remove.
+	(check_allocno_creation): New.
+	(ira_build): Call propagate_allocno_info, call_caps, and
+	check_allocno_creation.  Move
+	ira_tune_allocno_costs_and_cover_classes before
+	setup_min_max_allocno_live_range_point.
+
+	* ira.c: Update comments about IRA.
+	(ira_print_disposition): Add comment.
+
+	* ira-costs.c (total_costs): Rename to allocno_costs.
+	(total_costs): New.
+	(print_costs): Print accumulated costs too.
+	(find_allocno_class_costs): Check border allocnos for propagation
+	costs.  Setup non-accumulated costs for allocnos.
+	(process_bb_node_for_hard_reg_moves): Don't propagate costs.
+	(ira_costs): Add allocation/freeing allocno_costs.
+
+	* common.opt (fira-propagate-cost): Remove.
+
+	* doc/invoke.texi (-fira-propagate-cost): Remove.
+	
 2008-08-04  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR middle-end/36450
diff --git a/gcc/common.opt b/gcc/common.opt
index 9bed0adc6ec..dc532440afa 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -661,10 +661,6 @@ fira-coalesce
 Common Report Var(flag_ira_coalesce) Init(0)
 Do optimistic coalescing.
 
-fira-propagate-cost
-Common Report Var(flag_ira_propagate_cost) Init(0)
-Propagate hard reg costs down for regional or mixed ira allocation algorithm.
-
 fira-share-save-slots
 Common Report Var(flag_ira_share_save_slots) Init(1)
 Share slots for saving different hard registers.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index e2a1f1e531f..3f106cc8b10 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -334,8 +334,7 @@ Objective-C and Objective-C++ Dialects}.
 -finline-small-functions -fipa-cp -fipa-marix-reorg -fipa-pta @gol 
 -fipa-pure-const -fipa-reference -fipa-struct-reorg @gol
 -fipa-type-escape -fira -fira-algorithm=@var{algorithm} @gol
--fira-coalesce @gol
--fira-propagate-cost -fno-ira-share-save-slots @gol
+-fira-coalesce -fno-ira-share-save-slots @gol
 -fno-ira-share-spill-slots -fira-verbose=@var{n} @gol
 -fivopts -fkeep-inline-functions -fkeep-static-consts @gol
 -fmerge-all-constants -fmerge-constants -fmodulo-sched @gol
@@ -5704,11 +5703,6 @@ results in most cases and for most architectures.
 Do optimistic register coalescing.  This option might be profitable for
 architectures with big regular register files.
 
-@item -fira-propagate-cost
-@opindex -fira-propagate-cost
-This is an experimental option used to propagate hard reg costs down
-to nested regions for regional or mixed ira allocation algorithm.
-
 @item -fno-ira-share-save-slots
 @opindex fno-ira-share-save-slots
 Switch off sharing stack slots used for saving call used hard
diff --git a/gcc/ira-build.c b/gcc/ira-build.c
index 651810b6e5b..979a3c86685 100644
--- a/gcc/ira-build.c
+++ b/gcc/ira-build.c
@@ -82,9 +82,6 @@ ira_copy_t *ira_copies;
 /* Size of the previous array.  */
 int ira_copies_num;
 
-/* Bitmap of allocnos used for different purposes.  */
-static bitmap allocnos_bitmap;
-
 
 
 /* LAST_BASIC_BLOCK before generating additional insns because of live
@@ -757,13 +754,15 @@ create_cap_allocno (ira_allocno_t a)
 {
   ira_allocno_t cap;
   ira_loop_tree_node_t parent;
+  enum reg_class cover_class;
 
   ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
 	      && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
   parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
   cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
   ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
-  ira_set_allocno_cover_class (cap, ALLOCNO_COVER_CLASS (a));
+  cover_class = ALLOCNO_COVER_CLASS (a);
+  ira_set_allocno_cover_class (cap, cover_class);
   ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
   ALLOCNO_CAP_MEMBER (cap) = a;
   bitmap_set_bit (parent->mentioned_allocnos, ALLOCNO_NUM (cap));
@@ -771,35 +770,6 @@ create_cap_allocno (ira_allocno_t a)
   ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
   ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
   ALLOCNO_UPDATED_MEMORY_COST (cap) = ALLOCNO_UPDATED_MEMORY_COST (a);
-  if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
-    {
-      fprintf (ira_dump_file, "    Creating cap ");
-      ira_print_expanded_allocno (cap);
-      fprintf (ira_dump_file, "\n");
-    }
-  return cap;
-}
-
-/* Propagates info to the CAP from its member.  We must propagate info
-   which is not available at the cap creation time.  */
-static void
-propagate_info_to_cap (ira_allocno_t cap)
-{
-  int regno, conflicts_num;
-  enum reg_class cover_class;
-  ira_allocno_t a, conflict_allocno, conflict_parent_allocno;
-  ira_allocno_t another_a, parent_a;
-  ira_loop_tree_node_t parent;
-  ira_copy_t cp, next_cp;
-  ira_allocno_conflict_iterator aci;
-
-  ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (cap) == cap
-	      && ALLOCNO_NEXT_COALESCED_ALLOCNO (cap) == cap
-	      && ALLOCNO_CONFLICT_ALLOCNO_ARRAY (cap) == NULL
-	      && ALLOCNO_CALLS_CROSSED_NUM (cap) == 0);
-  a = ALLOCNO_CAP_MEMBER (cap);
-  parent = ALLOCNO_LOOP_TREE_NODE (cap);
-  cover_class = ALLOCNO_COVER_CLASS (cap);
   ira_allocate_and_copy_costs
     (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
   ira_allocate_and_copy_costs
@@ -817,74 +787,15 @@ propagate_info_to_cap (ira_allocno_t cap)
   ALLOCNO_NO_STACK_REG_P (cap) = ALLOCNO_NO_STACK_REG_P (a);
   ALLOCNO_TOTAL_NO_STACK_REG_P (cap) = ALLOCNO_TOTAL_NO_STACK_REG_P (a);
 #endif
-  /* Add copies to the cap.  */
-  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 ();
-      parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (another_a)];
-      if (parent_a == NULL)
-	parent_a = ALLOCNO_CAP (another_a);
-      if (parent_a != NULL
-	  && find_allocno_copy (cap, parent_a,
-				cp->insn, cp->loop_tree_node) == NULL)
-	/* Upper level allocno might be not existing because it is not
-	   mentioned or lived on the region border.  It is just living
-	   on BB start of the loop.  */
-	ira_add_allocno_copy (cap, parent_a, cp->freq, cp->insn,
-			      cp->loop_tree_node);
-    }
-  if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
-    {
-      conflicts_num = 0;
-      FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
-	conflicts_num++;
-      ira_allocate_allocno_conflicts (cap, conflicts_num);
-      FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
-	{
-	  regno = ALLOCNO_REGNO (conflict_allocno);
-	  conflict_parent_allocno = parent->regno_allocno_map[regno];
-	  if (conflict_parent_allocno == NULL)
-	    conflict_parent_allocno = ALLOCNO_CAP (conflict_allocno);
-	  if (conflict_parent_allocno != NULL
-	      && (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (conflict_parent_allocno)
-		  != NULL))
-	    ira_add_allocno_conflict (cap, conflict_parent_allocno);
-	}
-    }
   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
     {
-      fprintf (ira_dump_file, "    Propagate info to cap ");
+      fprintf (ira_dump_file, "    Creating cap ");
       ira_print_expanded_allocno (cap);
-      if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (cap) != NULL)
-	{
-	  fprintf (ira_dump_file, "\n      Conflicts:");
-	  FOR_EACH_ALLOCNO_CONFLICT (cap, conflict_allocno, aci)
-	    {
-	      fprintf (ira_dump_file, " a%d(r%d,",
-		       ALLOCNO_NUM (conflict_allocno),
-		       ALLOCNO_REGNO (conflict_allocno));
-	      ira_assert
-		(ALLOCNO_LOOP_TREE_NODE (conflict_allocno)->bb == NULL);
-	      fprintf (ira_dump_file, "l%d)",
-		       ALLOCNO_LOOP_TREE_NODE (conflict_allocno)->loop->num);
-	    }
-	}
       fprintf (ira_dump_file, "\n");
     }
+  return cap;
 }
 
-
 /* Create and return allocno live range with given attributes.  */
 allocno_live_range_t
 ira_create_allocno_live_range (ira_allocno_t a, int start, int finish,
@@ -1453,6 +1364,7 @@ create_loop_allocnos (edge e)
   unsigned int i;
   bitmap live_in_regs, border_allocnos;
   bitmap_iterator bi;
+  ira_loop_tree_node_t parent;
 
   live_in_regs = DF_LR_IN (e->dest);
   border_allocnos = ira_curr_loop_tree_node->border_allocnos;
@@ -1461,7 +1373,14 @@ create_loop_allocnos (edge e)
     if (bitmap_bit_p (live_in_regs, i))
       {
 	if (ira_curr_regno_allocno_map[i] == NULL)
-	  ira_create_allocno (i, false, ira_curr_loop_tree_node);
+	  {
+	    /* The order of creations is important for right
+	       ira_regno_allocno_map.  */
+	    if ((parent = ira_curr_loop_tree_node->parent) != NULL
+		&& parent->regno_allocno_map[i] == NULL)
+	      ira_create_allocno (i, false, parent);
+	    ira_create_allocno (i, false, ira_curr_loop_tree_node);
+	  }
 	bitmap_set_bit (border_allocnos,
 			ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
       }
@@ -1505,39 +1424,78 @@ propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
 		   loop_tree_node->modified_regnos);
 }
 
-/* Create allocnos corresponding to pseudo-registers in the current
-   function.  Traverse the loop tree for this.  */
+/* Propagate new info about allocno A (see comments about accumulated
+   info in allocno definition) to the corresponding allocno on upper
+   loop tree level.  So allocnos on upper levels accumulate
+   information about the corresponding allocnos in nested regions.
+   The new info means allocno info finally calculated in this
+   file.  */
 static void
-create_allocnos (void)
+propagate_allocno_info (void)
 {
   int i;
   ira_allocno_t a, parent_a;
   ira_loop_tree_node_t parent;
+  enum reg_class cover_class;
 
-  /* We need to process BB first to correctly link allocnos by member
-     next_regno_allocno.  */
-  ira_traverse_loop_tree (true, ira_loop_tree_root,
-			  create_loop_tree_node_allocnos, NULL);
-  if (optimize)
-    ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
-			    propagate_modified_regnos);
   if (flag_ira_algorithm != IRA_ALGORITHM_REGIONAL
       && flag_ira_algorithm != IRA_ALGORITHM_MIXED)
     return;
-  /* Propagate number of references and frequencies for regional
-     register allocation.  */
   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
     for (a = ira_regno_allocno_map[i];
 	 a != NULL;
 	 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
       if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
-	  && (parent_a = parent->regno_allocno_map[i]) != NULL)
+	  && (parent_a = parent->regno_allocno_map[i]) != NULL
+	  /* There are no caps yet at this point.  So use
+	     border_allocnos to find allocnos for the propagation.  */
+	  && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
+			   ALLOCNO_NUM (a)))
 	{
 	  ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
 	  ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
+	  ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
+#ifdef STACK_REGS
+	  if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
+	    ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
+#endif
+	  IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
+			    ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
+	  ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+	    += ALLOCNO_CALLS_CROSSED_NUM (a);
+	  ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+	    += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+	  cover_class = ALLOCNO_COVER_CLASS (a);
+	  ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
+	  ira_allocate_and_accumulate_costs
+	    (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
+	     ALLOCNO_HARD_REG_COSTS (a));
+	  ira_allocate_and_accumulate_costs
+	    (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
+	     cover_class,
+	     ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
+	  ALLOCNO_COVER_CLASS_COST (parent_a)
+	    += ALLOCNO_COVER_CLASS_COST (a);
+	  ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
+	  ALLOCNO_UPDATED_MEMORY_COST (parent_a)
+	    += ALLOCNO_UPDATED_MEMORY_COST (a);
 	}
 }
 
+/* Create allocnos corresponding to pseudo-registers in the current
+   function.  Traverse the loop tree for this.  */
+static void
+create_allocnos (void)
+{
+  /* We need to process BB first to correctly link allocnos by member
+     next_regno_allocno.  */
+  ira_traverse_loop_tree (true, ira_loop_tree_root,
+			  create_loop_tree_node_allocnos, NULL);
+  if (optimize)
+    ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
+			    propagate_modified_regnos);
+}
+
 
 
 /* The page contains function to remove some regions from a separate
@@ -1725,9 +1683,7 @@ remove_unnecessary_allocnos (void)
   ira_allocno_t a, prev_a, next_a, parent_a;
   ira_loop_tree_node_t a_node, parent;
   allocno_live_range_t r;
-  bitmap local_allocno_bitmap;
 
-  local_allocno_bitmap = ira_allocate_bitmap ();
   merged_p = false;
   for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
     for (prev_a = NULL, a = ira_regno_allocno_map[regno];
@@ -1753,7 +1709,6 @@ remove_unnecessary_allocnos (void)
 		prev_a = a;
 		ALLOCNO_LOOP_TREE_NODE (a) = parent;
 		parent->regno_allocno_map[regno] = a;
-		bitmap_set_bit (local_allocno_bitmap, ALLOCNO_NUM (a));
 		bitmap_set_bit (parent->mentioned_allocnos, ALLOCNO_NUM (a));
 	      }
 	    else
@@ -1776,54 +1731,40 @@ remove_unnecessary_allocnos (void)
 		if (ALLOCNO_NO_STACK_REG_P (a))
 		  ALLOCNO_NO_STACK_REG_P (parent_a) = true;
 #endif
-		/* We already have an accumulated info for the
-		   corresponding allocno in the parent region.  But
-		   this info is not accumulated in two cases:
-		   o there is not corresponding allocno in the parent
-  		     region but there is an allocno in the
-  		     grand-(grand-...)parent region.
-		   o the allocno in upper region was moved from a
-		     lower level region.
-		     So accumulate the info in the both cases. */
-		if (parent != a_node->parent
-		    || bitmap_bit_p (local_allocno_bitmap, ALLOCNO_NUM (a)))
-		  {
-		    cover_class = ALLOCNO_COVER_CLASS (a);
-		    ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
-		    ira_allocate_and_accumulate_costs
-		      (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
-		       ALLOCNO_HARD_REG_COSTS (a));
-		    ira_allocate_and_accumulate_costs
-		      (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
-		       cover_class,
-		       ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
-		    ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
-		    ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
-		    ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
-		    IOR_HARD_REG_SET
-		      (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
-		       ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
-		    ALLOCNO_CALLS_CROSSED_NUM (parent_a)
-		      += ALLOCNO_CALLS_CROSSED_NUM (a);
+		ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
+		ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
+		ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
+		IOR_HARD_REG_SET
+		  (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
+		   ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
+		ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+		  += ALLOCNO_CALLS_CROSSED_NUM (a);
+		ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+		  += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
 #ifdef STACK_REGS
-		    if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
-		      ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
+		if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
+		  ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
 #endif
-		    ALLOCNO_COVER_CLASS_COST (parent_a)
-		      += ALLOCNO_COVER_CLASS_COST (a);
-		    ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
-		    ALLOCNO_UPDATED_MEMORY_COST (parent_a)
-		      += ALLOCNO_UPDATED_MEMORY_COST (a);
-		    ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
-		      += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
-		  }
+		cover_class = ALLOCNO_COVER_CLASS (a);
+		ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
+		ira_allocate_and_accumulate_costs
+		  (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
+		   ALLOCNO_HARD_REG_COSTS (a));
+		ira_allocate_and_accumulate_costs
+		  (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
+		   cover_class,
+		   ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
+		ALLOCNO_COVER_CLASS_COST (parent_a)
+		  += ALLOCNO_COVER_CLASS_COST (a);
+		ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
+		ALLOCNO_UPDATED_MEMORY_COST (parent_a)
+		  += ALLOCNO_UPDATED_MEMORY_COST (a);
 		finish_allocno (a);
 	      }
 	  }
       }
   if (merged_p)
     ira_rebuild_start_finish_chains ();
-  ira_free_bitmap (local_allocno_bitmap);
 }
 
 /* Remove loops from consideration.  We remove loops for which a
@@ -1879,8 +1820,7 @@ setup_min_max_allocno_live_range_point (void)
 	  continue;
 	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
 	/* Accumulation of range info.  */
-	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
-	    || (parent_a = parent->regno_allocno_map[i]) == NULL)
+	if (ALLOCNO_CAP (a) != NULL)
 	  {
 	    for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
 	      {
@@ -1891,6 +1831,9 @@ setup_min_max_allocno_live_range_point (void)
 	      }
 	    continue;
 	  }
+	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
+	  continue;
+	parent_a = parent->regno_allocno_map[i];
 	if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
 	  ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
 	if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
@@ -2032,41 +1975,25 @@ setup_min_max_conflict_allocno_ids (void)
 
 
 
-/* Create caps representing allocnos living only inside the loop given
-   by LOOP_NODE on higher loop level.  */
 static void
-create_loop_tree_node_caps (ira_loop_tree_node_t loop_node)
+create_caps (void)
 {
-  unsigned int i;
-  bitmap_iterator bi;
-  ira_loop_tree_node_t parent;
-
-  if (loop_node == ira_loop_tree_root)
-    return;
-  ira_assert (loop_node->bb == NULL);
-  bitmap_and_compl (allocnos_bitmap, loop_node->mentioned_allocnos,
-		    loop_node->border_allocnos);
-  parent = loop_node->parent;
-  EXECUTE_IF_SET_IN_BITMAP (allocnos_bitmap, 0, i, bi)
-    if (parent->regno_allocno_map[ALLOCNO_REGNO (ira_allocnos[i])] == NULL)
-      create_cap_allocno (ira_allocnos[i]);
-}
-
-/* Propagate info (not available at the cap creation time) to caps
-   mentioned in LOOP_NODE.  */
-static void
-propagate_info_to_loop_tree_node_caps (ira_loop_tree_node_t loop_node)
-{
-  unsigned int i;
-  bitmap_iterator bi;
   ira_allocno_t a;
+  ira_allocno_iterator ai;
+  ira_loop_tree_node_t loop_tree_node;
 
-  ira_assert (loop_node->bb == NULL);
-  EXECUTE_IF_SET_IN_BITMAP (loop_node->mentioned_allocnos, 0, i, bi)
+  FOR_EACH_ALLOCNO (a, ai)
     {
-      a = ira_allocnos[i];
+      if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
+	continue;
       if (ALLOCNO_CAP_MEMBER (a) != NULL)
-	propagate_info_to_cap (a);
+	create_cap_allocno (a);
+      else if (ALLOCNO_CAP (a) == NULL)
+	{
+	  loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
+	  if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
+	    create_cap_allocno (a);
+	}
     }
 }
 
@@ -2139,11 +2066,11 @@ ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 	   a != NULL;
 	   a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
 	{
-	  if (ALLOCNO_CAP_MEMBER (a) != NULL)
-	    continue;
+	  ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
 	  if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
 	    new_pseudos_p = true;
-	  if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
+	  if (ALLOCNO_CAP (a) != NULL
+	      || (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
 	      || ((parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
 		  == NULL))
 	    {
@@ -2195,6 +2122,7 @@ ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 	  new_pseudos_p = true;
 	  propagate_p = true;
 	  first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a;
+	  stop_p = false;
 	  for (;;)
 	    {
 	      if (first == NULL
@@ -2202,10 +2130,20 @@ ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 		first = parent_a;
 	      ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
 	      ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
-	      ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
-	      ALLOCNO_CALLS_CROSSED_NUM (parent_a)
-		-= ALLOCNO_CALLS_CROSSED_NUM (a);
-	      ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0);
+	      if (first != NULL
+		  && ALLOCNO_MEM_OPTIMIZED_DEST (first) == parent_a)
+		stop_p = true;
+	      else if (!stop_p)
+		{
+		  ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
+		  ALLOCNO_CALLS_CROSSED_NUM (parent_a)
+		    -= ALLOCNO_CALLS_CROSSED_NUM (a);
+		  ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
+		    -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+		}
+	      ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
+			  && ALLOCNO_NREFS (parent_a) >= 0
+			  && ALLOCNO_FREQ (parent_a) >= 0);
 	      cover_class = ALLOCNO_COVER_CLASS (parent_a);
 	      hard_regs_num = ira_class_hard_regs_num[cover_class];
 	      if (ALLOCNO_HARD_REG_COSTS (a) != NULL
@@ -2221,9 +2159,9 @@ ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 	      ALLOCNO_COVER_CLASS_COST (parent_a)
 		-= ALLOCNO_COVER_CLASS_COST (a);
 	      ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
-	      ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
-		-= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
-	      if ((parent = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
+	      if (ALLOCNO_CAP (parent_a) != NULL
+		  || (parent
+		      = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
 		  || (parent_a = (parent->regno_allocno_map
 				  [ALLOCNO_REGNO (parent_a)])) == NULL)
 		break;
@@ -2408,37 +2346,32 @@ ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
 
 
 
-#if 0
-
-static int all_loops = 0, high_pressure_loops = 0;
-    
+#ifdef ENABLE_IRA_CHECKING
+/* Check creation of all allocnos.  Allocnos on lower levels should
+   have allocnos or caps on all upper levels.  */
 static void
-calculate_high_pressure_loops (ira_loop_tree_node_t loop_node,
-			       int *all_loops, int *high_pressure_loops)
+check_allocno_creation (void)
 {
-  ira_loop_tree_node_t subloop_node;
-  int i;
-  enum reg_class class;
+  ira_allocno_t a;
+  ira_allocno_iterator ai;
+  ira_loop_tree_node_t loop_tree_node;
 
-  (*all_loops)++;
-  for (i = 0; i < ira_reg_class_cover_size; i++)
-    {
-      class = ira_reg_class_cover[i];
-      if (loop_node->reg_pressure[class] > ira_available_class_regs[class]
-	  || (loop_node->parent != NULL
-	      && (loop_node->parent->reg_pressure[class]
-		  > ira_available_class_regs[class])))
-	break;
-    }
-  if (i < ira_reg_class_cover_size)
-    (*high_pressure_loops)++;
-  for (subloop_node = loop_node->subloops;
-       subloop_node != NULL;
-       subloop_node = subloop_node->subloop_next)
+  FOR_EACH_ALLOCNO (a, ai)
     {
-      ira_assert (subloop_node->bb == NULL);
-      calculate_high_pressure_loops (subloop_node,
-				     all_loops, high_pressure_loops);
+      if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
+	continue;
+      if (ALLOCNO_CAP_MEMBER (a) != NULL)
+	{
+	  ira_assert (ALLOCNO_CAP (a) != NULL);
+	}
+      else if (ALLOCNO_CAP (a) == NULL)
+	{
+	  loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
+	  ira_assert (loop_tree_node->parent
+		      ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
+		      && bitmap_bit_p (loop_tree_node->border_allocnos,
+				       ALLOCNO_NUM (a)));
+	}
     }
 }
 #endif
@@ -2457,7 +2390,6 @@ ira_build (bool loops_p)
 {
   df_analyze ();
 
-  allocnos_bitmap = ira_allocate_bitmap ();
   initiate_cost_vectors ();
   initiate_allocnos ();
   initiate_copies ();
@@ -2470,10 +2402,13 @@ ira_build (bool loops_p)
   loops_p = more_one_region_p ();
   if (loops_p)
     {
-      bitmap_clear (allocnos_bitmap);
-      ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
-			      create_loop_tree_node_caps);
+      propagate_allocno_info ();
+      create_caps ();
     }
+  ira_tune_allocno_costs_and_cover_classes ();
+#ifdef ENABLE_IRA_CHECKING
+  check_allocno_creation ();
+#endif
   setup_min_max_allocno_live_range_point ();
   sort_conflict_id_allocno_map ();
   setup_min_max_conflict_allocno_ids ();
@@ -2499,10 +2434,6 @@ ira_build (bool loops_p)
 	       "    allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
 	       ira_allocnos_num, ira_copies_num, n, nr);
     }
-  if (loops_p)
-    ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
-			    propagate_info_to_loop_tree_node_caps);
-  ira_tune_allocno_costs_and_cover_classes ();
   return loops_p;
 }
 
@@ -2515,5 +2446,4 @@ ira_destroy (void)
   finish_allocnos ();
   finish_cost_vectors ();
   ira_finish_allocno_live_ranges ();
-  ira_free_bitmap (allocnos_bitmap);
 }
diff --git a/gcc/ira-color.c b/gcc/ira-color.c
index 7f79c2f4417..458e23a3519 100644
--- a/gcc/ira-color.c
+++ b/gcc/ira-color.c
@@ -1593,7 +1593,42 @@ color_pass (ira_loop_tree_node_t loop_tree_node)
     }
   /* Color all mentioned allocnos including transparent ones.  */
   color_allocnos ();
-  /* Update costs of the corresponding allocnos in the subloops.  */
+  /* Process caps.  They are processed just once.  */
+  if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
+      || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL)
+    EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi)
+      {
+	a = ira_allocnos[j];
+	if (ALLOCNO_CAP_MEMBER (a) == NULL)
+	  continue;
+	/* Remove from processing in the next loop.  */
+	bitmap_clear_bit (consideration_allocno_bitmap, j);
+	class = ALLOCNO_COVER_CLASS (a);
+	if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
+	     && loop_tree_node->reg_pressure[class]
+	     <= ira_available_class_regs[class]))
+	  {
+	    mode = ALLOCNO_MODE (a);
+	    hard_regno = ALLOCNO_HARD_REGNO (a);
+	    if (hard_regno >= 0)
+	      {
+		index = ira_class_hard_reg_index[class][hard_regno];
+		ira_assert (index >= 0);
+	      }
+	    regno = ALLOCNO_REGNO (a);
+	    subloop_allocno = ALLOCNO_CAP_MEMBER (a);
+	    subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
+	    ira_assert (!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: */
+	    ira_free_allocno_updated_costs (subloop_allocno);
+	  }
+      }
+  /* Update costs of the corresponding allocnos (not caps) in the
+     subloops.  */
   for (subloop_node = loop_tree_node->subloops;
        subloop_node != NULL;
        subloop_node = subloop_node->subloop_next)
@@ -1602,6 +1637,7 @@ color_pass (ira_loop_tree_node_t loop_tree_node)
       EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
         {
 	  a = ira_allocnos[j];
+	  ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
 	  mode = ALLOCNO_MODE (a);
 	  class = ALLOCNO_COVER_CLASS (a);
 	  hard_regno = ALLOCNO_HARD_REGNO (a);
@@ -1612,120 +1648,71 @@ color_pass (ira_loop_tree_node_t loop_tree_node)
 	    }
 	  regno = ALLOCNO_REGNO (a);
 	  /* ??? conflict costs */
-	  if (ALLOCNO_CAP_MEMBER (a) == NULL)
+	  subloop_allocno = subloop_node->regno_allocno_map[regno];
+	  if (subloop_allocno == NULL
+	      || ALLOCNO_CAP (subloop_allocno) != NULL)
+	    continue;
+	  if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
+	       && (loop_tree_node->reg_pressure[class]
+		   <= ira_available_class_regs[class]))
+	      || (hard_regno < 0
+		  && ! bitmap_bit_p (subloop_node->mentioned_allocnos,
+				     ALLOCNO_NUM (subloop_allocno))))
 	    {
-	      subloop_allocno = subloop_node->regno_allocno_map[regno];
-	      if (subloop_allocno == NULL)
-		continue;
-	      if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
-		   && (loop_tree_node->reg_pressure[class]
-		       <= ira_available_class_regs[class]))
-		  || (hard_regno < 0
-		      && ! bitmap_bit_p (subloop_node->mentioned_allocnos,
-					 ALLOCNO_NUM (subloop_allocno))))
-		{
-		  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: */
-		      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 (! ALLOCNO_ASSIGNED_P (subloop_allocno))
 		{
-		  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: */
-		      ira_free_allocno_updated_costs (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: */
+		  ira_free_allocno_updated_costs (subloop_allocno);
 		}
-	      else if (hard_regno < 0)
-		{
-		  ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
-		    -= ((ira_memory_move_cost[mode][class][1] * enter_freq)
-			+ (ira_memory_move_cost[mode][class][0] * exit_freq));
-		}
-	      else
+	      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 (! ALLOCNO_ASSIGNED_P (subloop_allocno))
 		{
-		  cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
-		  ira_allocate_and_set_costs
-		    (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
-		     ALLOCNO_COVER_CLASS_COST (subloop_allocno));
-		  ira_allocate_and_set_costs
-		    (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
-		     cover_class, 0);
-		  cost = (ira_register_move_cost[mode][class][class] 
-			  * (exit_freq + enter_freq));
-		  ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
-		  ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
-		    -= cost;
-		  ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
-		    += (ira_memory_move_cost[mode][class][0] * enter_freq
-			+ ira_memory_move_cost[mode][class][1] * exit_freq);
-		  if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
-		      > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
-		    ALLOCNO_COVER_CLASS_COST (subloop_allocno)
-		      = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
+		  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: */
+		  ira_free_allocno_updated_costs (subloop_allocno);
 		}
 	    }
+	  else if (hard_regno < 0)
+	    {
+	      ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
+		-= ((ira_memory_move_cost[mode][class][1] * enter_freq)
+		    + (ira_memory_move_cost[mode][class][0] * exit_freq));
+	    }
 	  else
 	    {
-	      subloop_allocno = ALLOCNO_CAP_MEMBER (a);
-	      if (ALLOCNO_LOOP_TREE_NODE (subloop_allocno) != subloop_node)
-		continue;
-	      if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
-		   && loop_tree_node->reg_pressure[class]
-		      <= ira_available_class_regs[class])
-		  || (hard_regno < 0
-		      && ! bitmap_bit_p (subloop_node->mentioned_allocnos,
-					 ALLOCNO_NUM (subloop_allocno))))
-		{
-		  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: */
-		      ira_free_allocno_updated_costs (subloop_allocno);
-		    }
-		}
-	      else if (flag_ira_propagate_cost && hard_regno >= 0)
-		{
-		  exit_freq = ira_loop_edge_freq (subloop_node, -1, true);
-		  enter_freq = ira_loop_edge_freq (subloop_node, -1, false);
-		  cost = (ira_register_move_cost[mode][class][class] 
-			  * (exit_freq + enter_freq));
-		  cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
-		  ira_allocate_and_set_costs
-		    (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
-		     ALLOCNO_COVER_CLASS_COST (subloop_allocno));
-		  ira_allocate_and_set_costs
-		    (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
-		     cover_class, 0);
-		  ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
-		  ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
-		    -= cost;
-		  ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
-		    += (ira_memory_move_cost[mode][class][0] * enter_freq
-			+ ira_memory_move_cost[mode][class][1] * exit_freq);
-		  if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
-		      > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
-		    ALLOCNO_COVER_CLASS_COST (subloop_allocno)
-		      = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
-		}
+	      cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
+	      ira_allocate_and_set_costs
+		(&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
+		 ALLOCNO_COVER_CLASS_COST (subloop_allocno));
+	      ira_allocate_and_set_costs
+		(&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
+		 cover_class, 0);
+	      cost = (ira_register_move_cost[mode][class][class] 
+		      * (exit_freq + enter_freq));
+	      ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
+	      ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
+		-= cost;
+	      ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
+		+= (ira_memory_move_cost[mode][class][0] * enter_freq
+		    + ira_memory_move_cost[mode][class][1] * exit_freq);
+	      if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
+		  > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
+		ALLOCNO_COVER_CLASS_COST (subloop_allocno)
+		  = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
 	    }
 	}
     }
@@ -1785,6 +1772,7 @@ move_spill_restore (void)
 	  regno = ALLOCNO_REGNO (a);
 	  loop_node = ALLOCNO_LOOP_TREE_NODE (a);
 	  if (ALLOCNO_CAP_MEMBER (a) != NULL
+	      || ALLOCNO_CAP (a) != NULL
 	      || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
 	      || loop_node->children == NULL
 	      /* don't do the optimization because it can create
@@ -1792,7 +1780,8 @@ move_spill_restore (void)
 		 by copy although the allocno will not get memory
 		 slot.  */
 	      || ira_reg_equiv_invariant_p[regno]
-	      || ira_reg_equiv_const[regno] != NULL_RTX)
+	      || ira_reg_equiv_const[regno] != NULL_RTX
+	      || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
 	    continue;
 	  mode = ALLOCNO_MODE (a);
 	  class = ALLOCNO_COVER_CLASS (a);
diff --git a/gcc/ira-conflicts.c b/gcc/ira-conflicts.c
index 7a3d8ae8fd1..5f2fa2aa64a 100644
--- a/gcc/ira-conflicts.c
+++ b/gcc/ira-conflicts.c
@@ -325,7 +325,8 @@ process_regs_for_copy (rtx reg1, rtx reg2, rtx insn, int freq)
       hard_regno = REGNO (reg2);
       a = ira_curr_regno_allocno_map[REGNO (reg1)];
     }
-  else
+  else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
+				ira_curr_regno_allocno_map[REGNO (reg2)]))
     {
       cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
 				 ira_curr_regno_allocno_map[REGNO (reg2)],
@@ -333,6 +334,8 @@ process_regs_for_copy (rtx reg1, rtx reg2, rtx insn, int freq)
       bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num); 
       return true;
     }
+  else
+    return false;
   class = REGNO_REG_CLASS (hard_regno);
   mode = ALLOCNO_MODE (a);
   cover_class = ALLOCNO_COVER_CLASS (a);
@@ -446,58 +449,35 @@ add_copies (ira_loop_tree_node_t loop_tree_node)
       add_insn_allocno_copies (insn);
 }
 
-/* Propagate copy info for allocno A to the corresponding allocno on
-   upper loop tree level.  So allocnos on upper levels accumulate
-   information about the corresponding allocnos in nested regions.  */
+/* Propagate copies the corresponding allocnos on upper loop tree
+   level.  */
 static void
-propagate_allocno_copy_info (ira_allocno_t a)
+propagate_copies (void)
 {
-  int regno;
-  ira_allocno_t parent_a, another_a, another_parent_a;
+  ira_copy_t cp;
+  ira_copy_iterator ci;
+  ira_allocno_t a1, a2, parent_a1, parent_a2;
   ira_loop_tree_node_t parent;
-  ira_copy_t cp, next_cp;
 
-  regno = ALLOCNO_REGNO (a);
-  if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
-      && (parent_a = parent->regno_allocno_map[regno]) != NULL)
+  FOR_EACH_COPY (cp, ci)
     {
-      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 ((another_parent_a = (parent->regno_allocno_map
-				   [ALLOCNO_REGNO (another_a)])) != NULL)
-	    ira_add_allocno_copy (parent_a, another_parent_a, cp->freq,
-				  cp->insn, cp->loop_tree_node);
-	}
+      a1 = cp->first;
+      a2 = cp->second;
+      if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
+	continue;
+      ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
+      parent = ALLOCNO_LOOP_TREE_NODE (a1)->parent;
+      if ((parent_a1 = ALLOCNO_CAP (a1)) == NULL)
+	parent_a1 = parent->regno_allocno_map[ALLOCNO_REGNO (a1)];
+      if ((parent_a2 = ALLOCNO_CAP (a2)) == NULL)
+	parent_a2 = parent->regno_allocno_map[ALLOCNO_REGNO (a2)];
+      ira_assert (parent_a1 != NULL && parent_a2 != NULL);
+      if (! CONFLICT_ALLOCNO_P (parent_a1, parent_a2))
+	ira_add_allocno_copy (parent_a1, parent_a1, cp->freq,
+			      cp->insn, cp->loop_tree_node);
     }
 }
 
-/* Propagate copy info to the corresponding allocnos on upper loop
-   tree level.  */
-static void
-propagate_copy_info (void)
-{
-  int i;
-  ira_allocno_t a;
-
-  for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
-    for (a = ira_regno_allocno_map[i];
-	 a != NULL;
-	 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
-      propagate_allocno_copy_info (a);
-}
-
 /* 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 cover classes.  */
@@ -544,120 +524,103 @@ ira_pseudo_live_ranges_intersect_p (int regno1, int regno2)
   return ira_allocno_live_ranges_intersect_p (a1, a2);
 }
 
-/* Remove copies involving conflicting allocnos.  We can not do this
-   at the copy creation time because there are no conflicts at that
-   time yet.  */
+/* Array used to collect all conflict allocnos for given allocno.  */
+static ira_allocno_t *collected_conflict_allocnos;
+
+/* Build conflict vectors or bit conflict vectors (whatever is more
+   profitable) for allocno A from the conflict table and propagate the
+   conflicts to upper level allocno.  */
 static void
-remove_conflict_allocno_copies (void)
+build_allocno_conflicts (ira_allocno_t a)
 {
-  int i;
-  ira_allocno_t a;
-  ira_allocno_iterator ai;
-  ira_copy_t cp, next_cp;
-  VEC(ira_copy_t,heap) *conflict_allocno_copy_vec;
+  int i, px, parent_num;
+  int conflict_bit_vec_words_num;
+  ira_loop_tree_node_t parent;
+  ira_allocno_t parent_a, another_a, another_parent_a;
+  ira_allocno_t *vec;
+  IRA_INT_TYPE *allocno_conflicts;
+  ira_allocno_set_iterator asi;
 
-  conflict_allocno_copy_vec = VEC_alloc (ira_copy_t, heap, get_max_uid ());
-  FOR_EACH_ALLOCNO (a, ai)
+  allocno_conflicts = conflicts[ALLOCNO_NUM (a)];
+  px = 0;
+  FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
+			   ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
     {
-      for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
-	if (cp->first == a)
-	  next_cp = cp->next_first_allocno_copy;
-	else
-	  {
-	    next_cp = cp->next_second_allocno_copy;
-	    VEC_safe_push (ira_copy_t, heap, conflict_allocno_copy_vec, cp);
-	  }
+      another_a = ira_conflict_id_allocno_map[i];
+      ira_assert (ALLOCNO_COVER_CLASS (a)
+		  == ALLOCNO_COVER_CLASS (another_a));
+      collected_conflict_allocnos[px++] = another_a;
+    }
+  if (ira_conflict_vector_profitable_p (a, px))
+    {
+      ira_allocate_allocno_conflict_vec (a, px);
+      vec = (ira_allocno_t*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
+      memcpy (vec, collected_conflict_allocnos, sizeof (ira_allocno_t) * px);
+      vec[px] = NULL;
+      ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = px;
+    }
+  else
+    {
+      ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = conflicts[ALLOCNO_NUM (a)];
+      if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
+	conflict_bit_vec_words_num = 0;
+      else
+	conflict_bit_vec_words_num
+	  = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
+	     / IRA_INT_BITS);
+      ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a)
+	= conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
+    }
+  parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
+  if ((parent_a = ALLOCNO_CAP (a)) == NULL
+      && (parent == NULL
+	  || (parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
+	  == NULL))
+    return;
+  ira_assert (parent != NULL);
+  ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
+  parent_num = ALLOCNO_NUM (parent_a);
+  FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
+			   ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
+    {
+      another_a = ira_conflict_id_allocno_map[i];
+      ira_assert (ALLOCNO_COVER_CLASS (a)
+		  == ALLOCNO_COVER_CLASS (another_a));
+      if ((another_parent_a = ALLOCNO_CAP (another_a)) == NULL
+	  && (another_parent_a = (parent->regno_allocno_map
+				  [ALLOCNO_REGNO (another_a)])) == NULL)
+	continue;
+      ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
+      ira_assert (ALLOCNO_COVER_CLASS (another_a)
+		  == ALLOCNO_COVER_CLASS (another_parent_a));
+      SET_ALLOCNO_SET_BIT (conflicts[parent_num],
+			   ALLOCNO_CONFLICT_ID (another_parent_a),
+			   ALLOCNO_MIN (parent_a),
+			   ALLOCNO_MAX (parent_a));
     }
-  for (i = 0; VEC_iterate (ira_copy_t, conflict_allocno_copy_vec, i, cp); i++)
-    if (CONFLICT_ALLOCNO_P (cp->first, cp->second))
-      ira_remove_allocno_copy_from_list (cp);
-  VEC_free (ira_copy_t, heap, conflict_allocno_copy_vec);
 }
 
 /* Build conflict vectors or bit conflict vectors (whatever is more
    profitable) of all allocnos from the conflict table.  */
 static void
-build_allocno_conflicts (void)
+build_conflicts (void)
 {
-  int i, j, px, parent_num;
-  bool free_p;
-  int conflict_bit_vec_words_num;
-  ira_loop_tree_node_t parent;
-  ira_allocno_t a, parent_a, another_a, another_parent_a;
-  ira_allocno_t *conflict_allocnos, *vec;
-  IRA_INT_TYPE *allocno_conflicts;
-  ira_allocno_set_iterator asi;
+  int i;
+  ira_allocno_t a, cap;
 
-  conflict_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
-						      * ira_allocnos_num);
+  collected_conflict_allocnos
+    = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
+				      * ira_allocnos_num);
   for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
     for (a = ira_regno_allocno_map[i];
 	 a != NULL;
 	 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
       {
-	allocno_conflicts = conflicts[ALLOCNO_NUM (a)];
-	px = 0;
-	FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
-				 ALLOCNO_MIN (a), ALLOCNO_MAX (a), j, asi)
-	  {
-	    another_a = ira_conflict_id_allocno_map[j];
-	    ira_assert (ALLOCNO_COVER_CLASS (a)
-			== ALLOCNO_COVER_CLASS (another_a));
-	    conflict_allocnos[px++] = another_a;
-	  }
-	if (ira_conflict_vector_profitable_p (a, px))
-	  {
-	    free_p = true;
-	    ira_allocate_allocno_conflict_vec (a, px);
-	    vec = (ira_allocno_t*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
-	    memcpy (vec, conflict_allocnos, sizeof (ira_allocno_t) * px);
-	    vec[px] = NULL;
-	    ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = px;
-	  }
-	else
-	  {
-	    free_p = false;
-	    ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = conflicts[ALLOCNO_NUM (a)];
-	    if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
-	      conflict_bit_vec_words_num = 0;
-	    else
-	      conflict_bit_vec_words_num
-		= ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
-		   / IRA_INT_BITS);
-	    ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a)
-	      = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
-	  }
-	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
-	    || (parent_a = parent->regno_allocno_map[i]) == NULL)
-	  {
-	    if (free_p)
-	      ira_free (conflicts[ALLOCNO_NUM (a)]);
-	    continue;
-	  }
-	ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
-	parent_num = ALLOCNO_NUM (parent_a);
-	FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
-				 ALLOCNO_MIN (a), ALLOCNO_MAX (a), j, asi)
-	  {
-	    another_a = ira_conflict_id_allocno_map[j];
-	    ira_assert (ALLOCNO_COVER_CLASS (a)
-			== ALLOCNO_COVER_CLASS (another_a));
-	    if ((another_parent_a = (parent->regno_allocno_map
-				     [ALLOCNO_REGNO (another_a)])) == NULL)
-	      continue;
-	    ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
-	    ira_assert (ALLOCNO_COVER_CLASS (another_a)
-			== ALLOCNO_COVER_CLASS (another_parent_a));
-	    SET_ALLOCNO_SET_BIT (conflicts[parent_num],
-				 ALLOCNO_CONFLICT_ID (another_parent_a),
-				 ALLOCNO_MIN (parent_a),
-				 ALLOCNO_MAX (parent_a));
-	  }
-	if (free_p)
-	  ira_free (conflicts[ALLOCNO_NUM (a)]);
+	build_allocno_conflicts (a);
+	for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
+	  build_allocno_conflicts (cap);
       }
-  ira_free (conflict_allocnos);
-  ira_free (conflicts);
+  ira_free (collected_conflict_allocnos);
 }
 
 
@@ -773,13 +736,20 @@ ira_build_conflicts (void)
   if (optimize)
     {
       build_conflict_bit_table ();
+      build_conflicts ();
       ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
+      /* We need finished conflict table for the subsequent call.  */
       if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
 	  || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
-	propagate_copy_info ();
-      /* We need finished conflict table for the subsequent call.  */
-      remove_conflict_allocno_copies ();
-      build_allocno_conflicts ();
+	propagate_copies ();
+      /* Now we can free memory for the conflict table (see function
+	 build_allocno_conflicts for details).  */
+      FOR_EACH_ALLOCNO (a, ai)
+	{
+	  if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != conflicts[ALLOCNO_NUM (a)])
+	    ira_free (conflicts[ALLOCNO_NUM (a)]);
+	}
+      ira_free (conflicts);
     }
   FOR_EACH_ALLOCNO (a, ai)
     {
diff --git a/gcc/ira-costs.c b/gcc/ira-costs.c
index bf111bb58a1..d1e1f2280fb 100644
--- a/gcc/ira-costs.c
+++ b/gcc/ira-costs.c
@@ -74,9 +74,8 @@ static struct costs *temp_costs;
 static struct costs *op_costs[MAX_RECOG_OPERANDS];
 static struct costs *this_op_costs[MAX_RECOG_OPERANDS];
 
-/* Record the initial and accumulated cost of each class for each
-   allocno.  */
-static struct costs *total_costs;
+/* Original and accumulated costs of each class for each allocno.  */
+static struct costs *allocno_costs, *total_costs;
 
 /* Classes used for cost calculation.  They may be different on
    different iterations of the cost calculations or in different
@@ -868,7 +867,7 @@ record_address_regs (enum machine_mode mode, rtx x, int context,
 	if (REGNO (x) < FIRST_PSEUDO_REGISTER)
 	  break;
 
-	pp = COSTS_OF_ALLOCNO (total_costs,
+	pp = COSTS_OF_ALLOCNO (allocno_costs,
 			       ALLOCNO_NUM (ira_curr_regno_allocno_map
 					    [REGNO (x)]));
 	pp->mem_cost += (ira_memory_move_cost[Pmode][class][1] * scale) / 2;
@@ -990,7 +989,7 @@ scan_one_insn (rtx insn)
       && (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL_RTX
       && MEM_P (XEXP (note, 0)))
     {
-      COSTS_OF_ALLOCNO (total_costs,
+      COSTS_OF_ALLOCNO (allocno_costs,
 			ALLOCNO_NUM (ira_curr_regno_allocno_map
 				     [REGNO (SET_DEST (set))]))->mem_cost
 	-= (ira_memory_move_cost[GET_MODE (SET_DEST (set))][GENERAL_REGS][1]
@@ -1009,7 +1008,7 @@ scan_one_insn (rtx insn)
       {
 	int regno = REGNO (recog_data.operand[i]);
 	struct costs *p
-	  = COSTS_OF_ALLOCNO (total_costs,
+	  = COSTS_OF_ALLOCNO (allocno_costs,
 			      ALLOCNO_NUM (ira_curr_regno_allocno_map[regno]));
 	struct costs *q = op_costs[i];
 
@@ -1057,10 +1056,15 @@ print_costs (FILE *f)
 					  PSEUDO_REGNO_MODE (regno))
 #endif
 	      )
-	    fprintf (f, " %s:%d", reg_class_names[class],
-		     COSTS_OF_ALLOCNO (total_costs, i)->cost[k]);
+	    {
+	      fprintf (f, " %s:%d", reg_class_names[class],
+		       COSTS_OF_ALLOCNO (allocno_costs, i)->cost[k]);
+	      if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
+		  || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
+		fprintf (f, ",%d", COSTS_OF_ALLOCNO (total_costs, i)->cost[k]);
+	    }
 	}
-      fprintf (f, " MEM:%i\n", COSTS_OF_ALLOCNO (total_costs, i)->mem_cost);
+      fprintf (f, " MEM:%i\n", COSTS_OF_ALLOCNO (allocno_costs, i)->mem_cost);
     }
 }
 
@@ -1095,7 +1099,6 @@ find_allocno_class_costs (void)
 #ifdef FORBIDDEN_INC_DEC_CLASSES
   in_inc_dec = ira_allocate (sizeof (bool) * ira_allocnos_num);
 #endif /* FORBIDDEN_INC_DEC_CLASSES */
-
   allocno_pref = NULL;
   /* Normally we scan the insns once and determine the best class to
      use for each allocno.  However, if -fexpensive-optimizations are
@@ -1122,7 +1125,7 @@ find_allocno_class_costs (void)
 	= sizeof (struct costs) + sizeof (int) * (cost_classes_num - 1);
       /* Zero out our accumulation of the cost of each class for each
 	 allocno.  */
-      memset (total_costs, 0, ira_allocnos_num * struct_costs_size);
+      memset (allocno_costs, 0, ira_allocnos_num * struct_costs_size);
 #ifdef FORBIDDEN_INC_DEC_CLASSES
       memset (in_inc_dec, 0, ira_allocnos_num * sizeof (bool));
 #endif
@@ -1132,6 +1135,8 @@ find_allocno_class_costs (void)
       ira_traverse_loop_tree (true, ira_loop_tree_root,
 			      process_bb_node_for_costs, NULL);
 
+      memcpy (total_costs, allocno_costs,
+	      max_struct_costs_size * ira_allocnos_num);
       if (pass == 0)
 	allocno_pref = allocno_pref_buffer;
 
@@ -1160,7 +1165,10 @@ find_allocno_class_costs (void)
 	      if ((flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
 		   || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
 		  && (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
-		  && (parent_a = parent->regno_allocno_map[i]) != NULL)
+		  && (parent_a = parent->regno_allocno_map[i]) != NULL
+		  /* There are no caps yet.  */
+		  && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
+				   ALLOCNO_NUM (a)))
 		{
 		  /* Propagate costs to upper levels in the region
 		     tree.  */
@@ -1173,9 +1181,9 @@ find_allocno_class_costs (void)
 		}
 	      for (k = 0; k < cost_classes_num; k++)
 		temp_costs->cost[k]
-		  += COSTS_OF_ALLOCNO (total_costs, a_num)->cost[k];
+		  += COSTS_OF_ALLOCNO (allocno_costs, a_num)->cost[k];
 	      temp_costs->mem_cost
-		+= COSTS_OF_ALLOCNO (total_costs, a_num)->mem_cost;
+		+= COSTS_OF_ALLOCNO (allocno_costs, a_num)->mem_cost;
 #ifdef FORBIDDEN_INC_DEC_CLASSES
 	      if (in_inc_dec[a_num])
 		inc_dec_p = true;
@@ -1299,7 +1307,6 @@ find_allocno_class_costs (void)
 	  fprintf (ira_dump_file,"\n");
 	}
     }
-
 #ifdef FORBIDDEN_INC_DEC_CLASSES
   ira_free (in_inc_dec);
 #endif
@@ -1318,7 +1325,7 @@ process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
   int i, freq, cost, src_regno, dst_regno, hard_regno;
   bool to_p;
   ira_allocno_t a;
-  enum reg_class class, cover_class, hard_reg_class;
+  enum reg_class class, hard_reg_class;
   enum machine_mode mode;
   basic_block bb;
   rtx insn, set, src, dst;
@@ -1376,33 +1383,6 @@ process_bb_node_for_hard_reg_moves (ira_loop_tree_node_t loop_tree_node)
       ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
       ALLOCNO_COVER_CLASS_COST (a) = MIN (ALLOCNO_COVER_CLASS_COST (a),
 					  ALLOCNO_HARD_REG_COSTS (a)[i]);
-      if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
-	  || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
-	{
-	  /* Propagate changes to the upper levels in the region
-	     tree.  */
-	  ira_loop_tree_node_t parent;
-	  int regno = ALLOCNO_REGNO (a);
-	  
-	  for (;;)
-	    {
-	      if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
-	        break;
-	      if ((a = parent->regno_allocno_map[regno]) == NULL)
-		break;
-	      cover_class = ALLOCNO_COVER_CLASS (a);
-	      ira_allocate_and_set_costs
-		(&ALLOCNO_HARD_REG_COSTS (a), cover_class,
-		 ALLOCNO_COVER_CLASS_COST (a));
-	      ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
-					  cover_class, 0);
-	      ALLOCNO_HARD_REG_COSTS (a)[i] -= cost;
-	      ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[i] -= cost;
-	      ALLOCNO_COVER_CLASS_COST (a)
-		= MIN (ALLOCNO_COVER_CLASS_COST (a),
-		       ALLOCNO_HARD_REG_COSTS (a)[i]);
-	    }
-	}
     }
 }
 
@@ -1426,13 +1406,13 @@ setup_allocno_cover_class_and_costs (void)
       cover_class = ira_class_translate[allocno_pref[i]];
       ira_assert (allocno_pref[i] == NO_REGS || cover_class != NO_REGS);
       ALLOCNO_MEMORY_COST (a) = ALLOCNO_UPDATED_MEMORY_COST (a)
-	= COSTS_OF_ALLOCNO (total_costs, i)->mem_cost;
+	= COSTS_OF_ALLOCNO (allocno_costs, i)->mem_cost;
       ira_set_allocno_cover_class (a, cover_class);
       if (cover_class == NO_REGS)
 	continue;
       ALLOCNO_AVAILABLE_REGS_NUM (a) = ira_available_class_regs[cover_class];
       ALLOCNO_COVER_CLASS_COST (a)
-	= (COSTS_OF_ALLOCNO (total_costs, i)
+	= (COSTS_OF_ALLOCNO (allocno_costs, i)
 	   ->cost[cost_class_nums[allocno_pref[i]]]);
       if (optimize && ALLOCNO_COVER_CLASS (a) != allocno_pref[i])
 	{
@@ -1443,7 +1423,7 @@ setup_allocno_cover_class_and_costs (void)
 	    {
 	      regno = ira_class_hard_regs[cover_class][j];
 	      class = REGNO_REG_CLASS (regno);
-	      reg_costs[j] = (COSTS_OF_ALLOCNO (total_costs, i)
+	      reg_costs[j] = (COSTS_OF_ALLOCNO (allocno_costs, i)
 			       ->cost[cost_class_nums[class]]);
 	    }
 	}
@@ -1538,6 +1518,8 @@ ira_costs (void)
   ira_allocno_t a;
   ira_allocno_iterator ai;
 
+  allocno_costs = (struct costs *) ira_allocate (max_struct_costs_size
+					       * ira_allocnos_num);
   total_costs = (struct costs *) ira_allocate (max_struct_costs_size
 					       * ira_allocnos_num);
   allocno_pref_buffer
@@ -1553,6 +1535,7 @@ ira_costs (void)
       ira_init_register_move_cost (ALLOCNO_MODE (a));
   ira_free (allocno_pref_buffer);
   ira_free (total_costs);
+  ira_free (allocno_costs);
 }
 
 
diff --git a/gcc/ira-emit.c b/gcc/ira-emit.c
index db5049f3403..d18be8021ab 100644
--- a/gcc/ira-emit.c
+++ b/gcc/ira-emit.c
@@ -267,6 +267,8 @@ not_modified_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
   ira_allocno_t a;
   ira_loop_tree_node_t node;
 
+  ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
+	      && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
   orig_regno = ALLOCNO_REGNO (src_allocno);
   regno = REGNO (ALLOCNO_REG (dest_allocno));
   for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
@@ -800,8 +802,10 @@ update_costs (ira_allocno_t a, bool read_p, int freq)
       ALLOCNO_MEMORY_COST (a)
 	+= (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
 	    [read_p ? 1 : 0] * freq);
-      if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
-	  || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
+      if (ALLOCNO_CAP (a) != NULL)
+	a = ALLOCNO_CAP (a);
+      else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
+	       || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
 	break;
     }
 }
diff --git a/gcc/ira-lives.c b/gcc/ira-lives.c
index b9a62fd53db..7d6b29fedf1 100644
--- a/gcc/ira-lives.c
+++ b/gcc/ira-lives.c
@@ -937,51 +937,6 @@ ira_debug_live_ranges (void)
   print_live_ranges (stderr);
 }
 
-/* Propagate new info about allocno A (see comments about accumulated
-   info in allocno definition) to the corresponding allocno on upper
-   loop tree level.  So allocnos on upper levels accumulate
-   information about the corresponding allocnos in nested regions.
-   The new info means allocno info finally calculated in this
-   file.  */
-static void
-propagate_new_allocno_info (ira_allocno_t a)
-{
-  int regno;
-  ira_allocno_t parent_a;
-  ira_loop_tree_node_t parent;
-
-  regno = ALLOCNO_REGNO (a);
-  if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
-      && (parent_a = parent->regno_allocno_map[regno]) != NULL)
-    {
-      ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
-#ifdef STACK_REGS
-      if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
-	ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
-#endif
-      IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
-			ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
-      ALLOCNO_CALLS_CROSSED_NUM (parent_a) += ALLOCNO_CALLS_CROSSED_NUM (a);
-      ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
-	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
-    }
-}
-
-/* Propagate new info about allocnos to the corresponding allocnos on
-   upper loop tree level.  */
-static void
-propagate_new_info (void)
-{
-  int i;
-  ira_allocno_t a;
-
-  for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
-    for (a = ira_regno_allocno_map[i];
-	 a != NULL;
-	 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
-      propagate_new_allocno_info (a);
-}
-
 /* The main entry function creates live ranges, set up
    CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
    calculate register pressure info.  */
@@ -999,7 +954,6 @@ ira_create_allocno_live_ranges (void)
   create_start_finish_chains ();
   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
     print_live_ranges (ira_dump_file);
-  propagate_new_info ();
   /* Clean up.  */
   sparseset_free (allocnos_live);
 }
diff --git a/gcc/ira.c b/gcc/ira.c
index 0d41859023b..ada50341032 100644
--- a/gcc/ira.c
+++ b/gcc/ira.c
@@ -140,28 +140,29 @@ along with GCC; see the file COPYING3.  If not see
          ira-build.c) and initializes most of their attributes.
 
        * Then IRA finds a cover class for each allocno and calculates
-         its initial cost of memory and each hard-register of its
-         cover class (file ira-cost.c).
-
-       * IRA creates all caps (file ira-build.c).
+         its initial (non-accumulated) cost of memory and each
+         hard-register of its cover class (file ira-cost.c).
 
        * IRA creates live ranges of each allocno, calulates register
          pressure for each cover class in each region, sets up
-         conflict hard registers for each allocno and call insns the
-         allocno lives through (file ira-lives.c).
+         conflict hard registers for each allocno and info about calls
+         the allocno lives through (file ira-lives.c).
+
+       * IRA removes low register pressure loops from the regions
+         mostly to speed IRA up (file ira-build.c).
+
+       * IRA propagates accumulated allocno info from lower region
+         allocnos to corresponding upper region allocnos (file
+         ira-build.c).
+
+       * IRA creates all caps (file ira-build.c).
 
        * Having live-ranges of allocnos and their cover classes, IRA
          creates conflicting allocnos of the same cover class for each
          allocno.  Conflicting allocnos are stored as a bit vector or
-         array of pointers to the conflicting allocnos whatever is more
-         profitable (file ira-conflicts.c).  At this point IRA creates
-         allocno copies and after that accumulates allocno info
-         (conflicts, copies, call insns lived through) in upper level
-         allocnos from lower levels ones.
-
-       * Having all conflicts and other info for regular allocnos, IRA
-         propagates this info to caps (file ira-build.c) and modifies
-         costs of callee-clobbered hard-registers (file ira-costs.c).
+         array of pointers to the conflicting allocnos whatever is
+         more profitable (file ira-conflicts.c).  At this point IRA
+         creates allocno copies.
 
      o Coloring.  Now IRA has all necessary info to start graph coloring
        process.  It is done in each region on top-down traverse of the
@@ -604,8 +605,8 @@ ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
 
 
 
-/* Output information about allocation of all allocnos
-   into file F.  */
+/* Output information about allocation of all allocnos (except for
+   caps) into file F.  */
 void
 ira_print_disposition (FILE *f)
 {