public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* RFA: patch for accurate updating hard reg costs.
@ 2008-10-15  5:01 Vladimir Makarov
  2008-10-27 18:15 ` Jeff Law
  0 siblings, 1 reply; 2+ messages in thread
From: Vladimir Makarov @ 2008-10-15  5:01 UTC (permalink / raw)
  To: gcc-patches; +Cc: Jeff Law

[-- Attachment #1: Type: text/plain, Size: 1829 bytes --]

The following patch solves a problem reported for MIPS by Richard 
Sandiford in

http://gcc.gnu.org/ml/gcc/2008-09/msg00484.html

Richard reported that it solves some worst problems:

http://gcc.gnu.org/ml/gcc/2008-10/msg00268.html

The patch was successfully tested and bootstrapped on x86_64.

Is it ok to commit the patch to the trunk?

2008-10-14  Vladimir Makarov  <vmakarov@redhat.com>

   * ira-int.h (ira_allocno): Add member updated_cover_class_cost.
   (ALLOCNO_UPDATED_COVER_CLASS_COST): New.
   (ira_fast_allocation): Remove the prototype.
  
   * ira-color.c (update_copy_costs, allocno_cost_compare_func,
   assign_hard_reg, calculate_allocno_spill_cost): Use updated costs.
   (color_pass): Modify the updated costs.
   (ira_color): Rename to color.  Make it static.
   (ira_fast_allocation): Rename to fast_allocation.  Make it static.
   (ira_color): New function.
  
   * ira-conflicts.c (process_regs_for_copy): Propagate hard reg cost
   change.

   * ira-lives.c (last_call_num, allocno_saved_at_call): New
   variables.
   (set_allocno_live, clear_allocno_live, mark_ref_live,
   mark_ref_dead): Invalidate corresponding element of
   allocno_saved_at_call.
   (process_bb_node_lives): Increment last_call_num.  Setup
   allocno_saved_at_call.  Don't increase ALLOCNO_CALL_FREQ if the
   allocno was already saved.
   (ira_create_allocno_live_ranges): Initiate last_call_num and
   allocno_saved_at_call.

   * ira-build.c (ira_create_allocno): Initiate
   ALLOCNO_UPDATED_COVER_CLASS_COST.
   (create_cap_allocno, propagate_allocno_info,
   remove_unnecessary_allocnos): Remove setting updated costs.
   (ira_flattening): Set up ALLOCNO_UPDATED_COVER_CLASS_COST.

   * ira.c (ira):  Don't call ira_fast_allocation.

   * ira-costs.c (setup_allocno_cover_class_and_costs): Don't set up
   updated costs.
  

[-- Attachment #2: accurate-costs.patch --]
[-- Type: text/x-patch, Size: 15762 bytes --]

Index: ira-conflicts.c
===================================================================
--- ira-conflicts.c	(revision 140793)
+++ ira-conflicts.c	(working copy)
@@ -337,6 +337,7 @@ process_regs_for_copy (rtx reg1, rtx reg
   enum reg_class rclass, cover_class;
   enum machine_mode mode;
   ira_copy_t cp;
+  ira_loop_tree_node_t parent;
 
   gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
   only_regs_p = REG_P (reg1) && REG_P (reg2);
@@ -388,13 +389,23 @@ process_regs_for_copy (rtx reg1, rtx reg
     cost = ira_register_move_cost[mode][cover_class][rclass] * freq;
   else
     cost = ira_register_move_cost[mode][rclass][cover_class] * freq;
-  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)[index] -= cost;
-  ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
+  for (;;)
+    {
+      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)[index] -= cost;
+      ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
+      if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_COVER_CLASS_COST (a))
+	ALLOCNO_COVER_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
+      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;
+    }
   return true;
 }
 
Index: ira-int.h
===================================================================
--- ira-int.h	(revision 140793)
+++ ira-int.h	(working copy)
@@ -258,9 +258,9 @@ struct ira_allocno
   /* Register class which should be used for allocation for given
      allocno.  NO_REGS means that we should use memory.  */
   enum reg_class cover_class;
-  /* Minimal accumulated cost of usage register of the cover class for
-     the allocno.  */
-  int cover_class_cost;
+  /* Minimal accumulated and updated costs of usage register of the
+     cover class for the allocno.  */
+  int cover_class_cost, updated_cover_class_cost;
   /* Minimal accumulated, and updated costs of memory for the allocno.
      At the allocation start, the original and updated costs are
      equal.  The updated cost may be changed after finishing
@@ -451,6 +451,7 @@ struct ira_allocno
 #define ALLOCNO_LEFT_CONFLICTS_NUM(A) ((A)->left_conflicts_num)
 #define ALLOCNO_COVER_CLASS(A) ((A)->cover_class)
 #define ALLOCNO_COVER_CLASS_COST(A) ((A)->cover_class_cost)
+#define ALLOCNO_UPDATED_COVER_CLASS_COST(A) ((A)->updated_cover_class_cost)
 #define ALLOCNO_MEMORY_COST(A) ((A)->memory_cost)
 #define ALLOCNO_UPDATED_MEMORY_COST(A) ((A)->updated_memory_cost)
 #define ALLOCNO_EXCESS_PRESSURE_POINTS_NUM(A) ((A)->excess_pressure_points_num)
@@ -897,7 +898,6 @@ extern void ira_reassign_conflict_allocn
 extern void ira_initiate_assign (void);
 extern void ira_finish_assign (void);
 extern void ira_color (void);
-extern void ira_fast_allocation (void);
 
 /* ira-emit.c */
 extern void ira_emit (bool);
Index: ira-color.c
===================================================================
--- ira-color.c	(revision 140793)
+++ ira-color.c	(working copy)
@@ -252,7 +252,7 @@ update_copy_costs (ira_allocno_t allocno
 
 	  ira_allocate_and_set_or_copy_costs
 	    (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
-	     ALLOCNO_COVER_CLASS_COST (another_allocno),
+	     ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
 	     ALLOCNO_HARD_REG_COSTS (another_allocno));
 	  ira_allocate_and_set_or_copy_costs
 	    (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
@@ -348,8 +348,8 @@ allocno_cost_compare_func (const void *v
   ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
   int c1, c2;
 
-  c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1);
-  c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2);
+  c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
+  c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
   if (c1 - c2)
     return c1 - c2;
 
@@ -426,7 +426,9 @@ assign_hard_reg (ira_allocno_t allocno, 
 #ifdef STACK_REGS
       no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
 #endif
-      for (cost = ALLOCNO_COVER_CLASS_COST (a), i = 0; i < class_size; i++)
+      for (cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a), i = 0;
+	   i < class_size;
+	   i++)
 	if (a_costs != NULL)
 	  {
 	    costs[i] += a_costs[i];
@@ -959,7 +961,7 @@ calculate_allocno_spill_cost (ira_allocn
   ira_loop_tree_node_t parent_node, loop_node;
 
   regno = ALLOCNO_REGNO (a);
-  cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
+  cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
   if (ALLOCNO_CAP (a) != NULL)
     return cost;
   loop_node = ALLOCNO_LOOP_TREE_NODE (a);
@@ -1821,24 +1823,26 @@ color_pass (ira_loop_tree_node_t loop_tr
 	  else
 	    {
 	      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][rclass][rclass] 
 		      * (exit_freq + enter_freq));
-	      ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
-	      ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
+	      ira_allocate_and_set_or_copy_costs
+		(&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
+		 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
+		 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
+	      ira_allocate_and_set_or_copy_costs
+		(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
+		 cover_class, 0,
+		 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
+	      ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
+	      ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
 		-= cost;
+	      if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
+		  > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
+		ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
+		  = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
 	      ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
 		+= (ira_memory_move_cost[mode][rclass][0] * enter_freq
 		    + ira_memory_move_cost[mode][rclass][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];
 	    }
 	}
     }
@@ -3054,8 +3058,8 @@ ira_finish_assign (void)
 \f
 
 /* Entry function doing color-based register allocation.  */
-void
-ira_color (void)
+static void
+color (void)
 {
   allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
   removed_splay_allocno_vec
@@ -3077,8 +3081,8 @@ ira_color (void)
 /* Do register allocation by not using allocno conflicts.  It uses
    only allocno live ranges.  The algorithm is close to Chow's
    priority coloring.  */
-void
-ira_fast_allocation (void)
+static void
+fast_allocation (void)
 {
   int i, j, k, num, class_size, hard_regno;
 #ifdef STACK_REGS
@@ -3148,3 +3152,24 @@ ira_fast_allocation (void)
   if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
     ira_print_disposition (ira_dump_file);
 }
+
+\f
+
+/* Entry function doing coloring.  */
+void
+ira_color (void)
+{
+  ira_allocno_t a;
+  ira_allocno_iterator ai;
+
+  /* Setup updated costs.  */
+  FOR_EACH_ALLOCNO (a, ai)
+    {
+      ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
+      ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
+    }
+  if (optimize)
+    color ();
+  else
+    fast_allocation ();
+}
Index: ira-lives.c
===================================================================
--- ira-lives.c	(revision 140793)
+++ ira-lives.c	(working copy)
@@ -75,6 +75,11 @@ static HARD_REG_SET hard_regs_live;
 /* The loop tree node corresponding to the current basic block.  */
 static ira_loop_tree_node_t curr_bb_node;
 
+/* The number of the last processed call.  */
+static int last_call_num;
+/* The number of last call at which given allocno was saved.  */
+static int *allocno_saved_at_call;
+
 /* The function processing birth of register REGNO.  It updates living
    hard regs and conflict hard regs for living allocnos or starts a
    new live range for the allocno corresponding to REGNO if it is
@@ -163,6 +168,8 @@ set_allocno_live (ira_allocno_t a)
   int nregs;
   enum reg_class cover_class;
 
+  /* Invalidate because it is referenced.  */
+  allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
   if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
     return;
   sparseset_set_bit (allocnos_live, ALLOCNO_NUM (a));
@@ -189,6 +196,8 @@ clear_allocno_live (ira_allocno_t a)
   unsigned int i;
   enum reg_class cover_class;
 
+  /* Invalidate because it is referenced.  */
+  allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
   if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
     {
       cover_class = ALLOCNO_COVER_CLASS (a);
@@ -233,7 +242,11 @@ mark_ref_live (struct df_ref *ref)
       if (a != NULL)
 	{
 	  if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
-	    return;
+	    {
+	      /* Invalidate because it is referenced.  */
+	      allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
+	      return;
+	    }
 	  set_allocno_live (a);
 	}
       make_regno_born (regno);
@@ -305,7 +318,11 @@ mark_ref_dead (struct df_ref *def)
       if (a != NULL)
 	{
 	  if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
-	    return;
+	    {
+	      /* Invalidate because it is referenced.  */
+	      allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
+	      return;
+	    }
 	  clear_allocno_live (a);
 	}
       make_regno_dead (regno);
@@ -627,6 +644,9 @@ process_bb_node_lives (ira_loop_tree_nod
       if (freq == 0)
 	freq = 1;
 
+      /* Invalidate all allocno_saved_at_call entries.  */
+      last_call_num++;
+
       /* Scan the code of this basic block, noting which allocnos and
 	 hard regs are born or die.
 
@@ -707,12 +727,21 @@ process_bb_node_lives (ira_loop_tree_nod
 
 	  if (call_p)
 	    {
+	      last_call_num++;
 	      /* The current set of live allocnos are live across the call.  */
 	      EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
 	        {
 		  ira_allocno_t a = ira_allocnos[i];
 		  
-		  ALLOCNO_CALL_FREQ (a) += freq;
+		  if (allocno_saved_at_call[i] != last_call_num)
+		    /* Here we are mimicking caller-save.c behaviour
+		       which does not save hard register at a call if
+		       it was saved on previous call in the same basic
+		       block and the hard register was not mentioned
+		       between the two calls.  */
+		    ALLOCNO_CALL_FREQ (a) += freq;
+		  /* Mark it as saved at the next call.  */
+		  allocno_saved_at_call[i] = last_call_num + 1;
 		  ALLOCNO_CALLS_CROSSED_NUM (a)++;
 		  /* Don't allocate allocnos that cross setjmps or any
 		     call, if this function receives a nonlocal
@@ -946,6 +975,10 @@ ira_create_allocno_live_ranges (void)
 {
   allocnos_live = sparseset_alloc (ira_allocnos_num);
   curr_point = 0;
+  last_call_num = 0;
+  allocno_saved_at_call
+    = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
+  memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
   ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
 			  process_bb_node_lives);
   ira_max_point = curr_point;
@@ -953,6 +986,7 @@ ira_create_allocno_live_ranges (void)
   if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
     print_live_ranges (ira_dump_file);
   /* Clean up.  */
+  ira_free (allocno_saved_at_call);
   sparseset_free (allocnos_live);
 }
 
Index: ira-build.c
===================================================================
--- ira-build.c	(revision 140793)
+++ ira-build.c	(working copy)
@@ -469,6 +469,7 @@ ira_create_allocno (int regno, bool cap_
   ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
   ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
   ALLOCNO_COVER_CLASS (a) = NO_REGS;
+  ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0;
   ALLOCNO_COVER_CLASS_COST (a) = 0;
   ALLOCNO_MEMORY_COST (a) = 0;
   ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
@@ -769,7 +770,6 @@ create_cap_allocno (ira_allocno_t a)
   ALLOCNO_CAP (a) = cap;
   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);
   ira_allocate_and_copy_costs
     (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
   ira_allocate_and_copy_costs
@@ -1509,8 +1509,6 @@ propagate_allocno_info (void)
 	  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);
 	}
 }
 
@@ -1789,8 +1787,6 @@ remove_unnecessary_allocnos (void)
 		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);
 	      }
 	  }
@@ -2349,7 +2345,9 @@ ira_flattening (int max_regno_before_emi
       ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
       ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
       ALLOCNO_CAP (a) = NULL;
+      /* Restore updated costs for assignments from reload.  */
       ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
+      ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
       if (! ALLOCNO_ASSIGNED_P (a))
 	ira_free_allocno_updated_costs (a);
       ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
Index: ira.c
===================================================================
--- ira.c	(revision 140793)
+++ ira.c	(working copy)
@@ -1761,10 +1761,7 @@ ira (FILE *f)
   loops_p = ira_build (optimize
 		       && (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
 			   || flag_ira_algorithm == IRA_ALGORITHM_MIXED));
-  if (optimize)
-    ira_color ();
-  else
-    ira_fast_allocation ();
+  ira_color ();
       
   ira_max_point_before_emit = ira_max_point;
       
Index: ira-costs.c
===================================================================
--- ira-costs.c	(revision 140793)
+++ ira-costs.c	(working copy)
@@ -1405,15 +1405,13 @@ setup_allocno_cover_class_and_costs (voi
       mode = ALLOCNO_MODE (a);
       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 (allocno_costs, i)->mem_cost;
+      ALLOCNO_MEMORY_COST (a) = 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 (allocno_costs, i)
-	   ->cost[cost_class_nums[allocno_pref[i]]]);
+      ALLOCNO_COVER_CLASS_COST (a) = (COSTS_OF_ALLOCNO (allocno_costs, i)
+				      ->cost[cost_class_nums[allocno_pref[i]]]);
       if (optimize && ALLOCNO_COVER_CLASS (a) != allocno_pref[i])
 	{
 	  n = ira_class_hard_regs_num[cover_class];

^ permalink raw reply	[flat|nested] 2+ messages in thread
end of thread, other threads:[~2008-10-27 16:17 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-10-15  5:01 RFA: patch for accurate updating hard reg costs Vladimir Makarov
2008-10-27 18:15 ` Jeff Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).