[ira] patch to choose a better spill reg in reload for IRA

[Vladimir Makarov <vmakarov at redhat dot com>]

------------------------ Common header -----------------------------
 I've broken reload changes for IRA in several patches as Bernd
Schmidt asked me to do for their review.  The order patches is
important if you try to apply them.  Patches starting with smaller
numbers should be applied first (more probably if you start with the
current branch state, you should apply patches starting with bigger
numbers using -R).

 Although I am waiting only for review of the reload parts of the
patches, I've added IRA parts too for better understanding.
--------------------------------------------------------------------

The patch implements better choice of spill register.  The reload
call IRA better_spill_reload_regno_p in reload1.c:find_reg to find
pseudo to spill for reloads.  Besides old heuristic based on spill
costs, IRA uses secondary heuristic based on length of the pseudo live
range where the register pressure is too high.


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

   * ira-color.c (calculate_spill_cost,
   ira_better_spill_reload_regno_p): New functions.

   * ira.h (ira_better_spill_reload_regno_p): New prototype.

   * reload1.c (hard_regno_to_pseudo_regno): New variable.
   (count_psuedo) Set hard_regno_to_pseudo_regno up.
   (order_regs_for_reload, count_spilled_pseudo): Clear
   hard_regno_to_pseudo_regno.
   (find_reg): Call IRA to find a better spill register.

--- ira-color.c	2008-07-17 17:38:32.000000000 -0400
+++ ../4/ira-color.c	2008-07-17 16:39:08.000000000 -0400
@@ -2700,6 +2700,111 @@ ira_mark_new_stack_slot (rtx x, int regn
 	     regno, REG_FREQ (regno), slot_num);
 }
 
+
+/* Return spill cost for pseudo-registers whose numbers are in array
+   REGNOS (with a negative number as an end marker) for reload with
+   given IN and OUT for INSN.  Return also number points (through
+   EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
+   the register pressure is high, number of references of the
+   pseudo-registers (through NREFS), number of callee-clobbered
+   hard-registers occupied by the pseudo-registers (through
+   CALL_USED_COUNT), and the first hard regno occupied by the
+   pseudo-registers (through FIRST_HARD_REGNO).  */
+static int
+calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
+		      int *excess_pressure_live_length,
+		      int *nrefs, int *call_used_count, int *first_hard_regno)
+{
+  int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
+  bool in_p, out_p;
+  int length;
+  ira_allocno_t a;
+
+  *nrefs = 0;
+  for (length = count = cost = i = 0;; i++)
+    {
+      regno = regnos[i];
+      if (regno < 0)
+	break;
+      *nrefs += REG_N_REFS (regno);
+      hard_regno = reg_renumber[regno];
+      ira_assert (hard_regno >= 0);
+      a = ira_regno_allocno_map[regno];
+      length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
+      cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
+      nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
+      for (j = 0; j < nregs; j++)
+	if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
+	  break;
+      if (j == nregs)
+	count++;
+      in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
+      out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
+      if ((in_p || out_p)
+	  && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
+	{
+	  saved_cost = 0;
+	  if (in_p)
+	    saved_cost += ira_memory_move_cost
+	                  [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
+	  if (out_p)
+	    saved_cost
+	      += ira_memory_move_cost
+	         [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
+	  cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
+	}
+    }
+  *excess_pressure_live_length = length;
+  *call_used_count = count;
+  hard_regno = -1;
+  if (regnos[0] >= 0)
+    {
+      hard_regno = reg_renumber[regnos[0]];
+    }
+  *first_hard_regno = hard_regno;
+  return cost;
+}
+
+/* Return TRUE if spilling pseudo-registers whose numbers are in array
+   REGNOS is better than spilling pseudo-registers with numbers in
+   OTHER_REGNOS for reload with given IN and OUT for INSN.  The
+   function used by the reload pass to make better register spilling
+   decisions.  */
+bool
+ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
+				 rtx in, rtx out, rtx insn)
+{
+  int cost, other_cost;
+  int length, other_length;
+  int nrefs, other_nrefs;
+  int call_used_count, other_call_used_count;
+  int hard_regno, other_hard_regno;
+
+  cost = calculate_spill_cost (regnos, in, out, insn, 
+			       &length, &nrefs, &call_used_count, &hard_regno);
+  other_cost = calculate_spill_cost (other_regnos, in, out, insn,
+				     &other_length, &other_nrefs,
+				     &other_call_used_count,
+				     &other_hard_regno);
+  if (nrefs == 0 && other_nrefs != 0)
+    return true;
+  if (nrefs != 0 && other_nrefs == 0)
+    return false;
+  if (cost != other_cost)
+    return cost < other_cost;
+  if (length != other_length)
+    return length > other_length;
+#ifdef REG_ALLOC_ORDER
+  if (hard_regno >= 0 && other_hard_regno >= 0)
+    return (inv_reg_alloc_order[hard_regno]
+	    < inv_reg_alloc_order[other_hard_regno]);
+#else
+  if (call_used_count != other_call_used_count)
+    return call_used_count > other_call_used_count;
+#endif
+  return false;
+}
+
 
 
 /* Allocate and initialize data necessary for assign_hard_reg.  */
--- ira.h	2008-07-17 17:38:33.000000000 -0400
+++ ../4/ira.h	2008-07-17 16:39:07.000000000 -0400
@@ -31,4 +31,5 @@ extern bool ira_reassign_pseudos (int *,
 				  HARD_REG_SET *, bitmap);
 extern rtx ira_reuse_stack_slot (int, unsigned int, unsigned int);
 extern void ira_mark_new_stack_slot (rtx, int, unsigned int);
+extern bool ira_better_spill_reload_regno_p (int *, int *, rtx, rtx, rtx);
 
--- reload1.c	2008-07-17 17:40:01.000000000 -0400
+++ ../4/reload1.c	2008-07-17 16:37:04.000000000 -0400
@@ -1692,6 +1692,10 @@ static int spill_cost[FIRST_PSEUDO_REGIS
    only the first hard reg for a multi-reg pseudo.  */
 static int spill_add_cost[FIRST_PSEUDO_REGISTER];
 
+/* Map of hard regno to pseudo regno currently occupying the hard
+   reg.  */
+static int hard_regno_to_pseudo_regno[FIRST_PSEUDO_REGISTER];
+
 /* Update the spill cost arrays, considering that pseudo REG is live.  */
 
 static void
@@ -1715,7 +1719,10 @@ count_pseudo (int reg)
   spill_add_cost[r] += freq;
   nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)];
   while (nregs-- > 0)
-    spill_cost[r + nregs] += freq;
+    {
+      hard_regno_to_pseudo_regno[r + nregs] = reg;
+      spill_cost[r + nregs] += freq;
+    }
 }
 
 /* Calculate the SPILL_COST and SPILL_ADD_COST arrays and determine the
@@ -1733,6 +1740,8 @@ order_regs_for_reload (struct insn_chain
 
   memset (spill_cost, 0, sizeof spill_cost);
   memset (spill_add_cost, 0, sizeof spill_add_cost);
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    hard_regno_to_pseudo_regno[i] = -1;
 
   /* Count number of uses of each hard reg by pseudo regs allocated to it
      and then order them by decreasing use.  First exclude hard registers
@@ -1775,6 +1784,7 @@ static HARD_REG_SET used_spill_regs_loca
 static void
 count_spilled_pseudo (int spilled, int spilled_nregs, int reg)
 {
+  int freq = REG_FREQ (reg);
   int r = reg_renumber[reg];
   int nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)];
 
@@ -1787,9 +1797,12 @@ count_spilled_pseudo (int spilled, int s
 
   SET_REGNO_REG_SET (&spilled_pseudos, reg);
 
-  spill_add_cost[r] -= REG_FREQ (reg);
+  spill_add_cost[r] -= freq;
   while (nregs-- > 0)
-    spill_cost[r + nregs] -= REG_FREQ (reg);
+    {
+      hard_regno_to_pseudo_regno[r + nregs] = -1;
+      spill_cost[r + nregs] -= freq;
+    }
 }
 
 /* Find reload register to use for reload number ORDER.  */
@@ -1801,11 +1814,13 @@ find_reg (struct insn_chain *chain, int 
   struct reload *rl = rld + rnum;
   int best_cost = INT_MAX;
   int best_reg = -1;
-  unsigned int i, j;
+  unsigned int i, j, n;
   int k;
   HARD_REG_SET not_usable;
   HARD_REG_SET used_by_other_reload;
   reg_set_iterator rsi;
+  static int regno_pseudo_regs[FIRST_PSEUDO_REGISTER];
+  static int best_regno_pseudo_regs[FIRST_PSEUDO_REGISTER];
 
   COPY_HARD_REG_SET (not_usable, bad_spill_regs);
   IOR_HARD_REG_SET (not_usable, bad_spill_regs_global);
@@ -1823,7 +1838,11 @@ find_reg (struct insn_chain *chain, int 
 
   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
     {
+#ifdef REG_ALLOC_ORDER
+      unsigned int regno = reg_alloc_order[i];
+#else
       unsigned int regno = i;
+#endif
 
       if (! TEST_HARD_REG_BIT (not_usable, regno)
 	  && ! TEST_HARD_REG_BIT (used_by_other_reload, regno)
@@ -1842,6 +1861,38 @@ find_reg (struct insn_chain *chain, int 
 	    }
 	  if (! ok)
 	    continue;
+
+	  if (flag_ira && optimize)
+	    {
+	      /* Ask IRA to find a better pseudo-register for
+		 spilling.  */
+	      for (n = j = 0; j < this_nregs; j++)
+		{
+		  int r = hard_regno_to_pseudo_regno[regno + j];
+
+		  if (r < 0)
+		    continue;
+		  if (n == 0 || regno_pseudo_regs[n - 1] != r)
+		    regno_pseudo_regs[n++] = r;
+		}
+	      regno_pseudo_regs[n++] = -1;
+	      if (best_reg < 0
+		  || ira_better_spill_reload_regno_p (regno_pseudo_regs,
+						      best_regno_pseudo_regs,
+						      rl->in, rl->out,
+						      chain->insn))
+		{
+		  best_reg = regno;
+		  for (j = 0;; j++)
+		    {
+		      best_regno_pseudo_regs[j] = regno_pseudo_regs[j];
+		      if (regno_pseudo_regs[j] < 0)
+			break;
+		    }
+		}
+	      continue;
+	    }
+
 	  if (rl->in && REG_P (rl->in) && REGNO (rl->in) == regno)
 	    this_cost--;
 	  if (rl->out && REG_P (rl->out) && REGNO (rl->out) == regno)
@@ -1889,6 +1940,7 @@ find_reg (struct insn_chain *chain, int 
     {
       gcc_assert (spill_cost[best_reg + i] == 0);
       gcc_assert (spill_add_cost[best_reg + i] == 0);
+      gcc_assert (hard_regno_to_pseudo_regno[best_reg + i] == -1);
       SET_HARD_REG_BIT (used_spill_regs_local, best_reg + i);
     }
   return 1;