re PR middle-end/37243 (IRA causes wrong code generation)

2008-09-03  Vladimir Makarov  <vmakarov@redhat.com>

	PR rtl-opt/37243
	
	* ira-conflicts.c (REG_SUBREG_P, go_through_subreg): New.
	(process_regs_for_copy): Process subregs.  Refine check when cost
	is taken into account in ira-costs.c.
	(process_reg_shuffles): Use REG_SUBREG_P.
	(add_insn_allocno_copies): Ditto.  Ignore modes.

	* ira-color.c (conflict_allocno_vec): New.
	(COST_HOP_DIVISOR): New macro.
	(update_copy_costs_1): Use it.
	(update_conflict_hard_regno_costs): New function.
	(assign_hard_reg): Use it.
	(ira_color): Allocate and free conflict_allocno_vec.

From-SVN: r139949

3 files changed, 172 insertions, 45 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d624181..87e5fcc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,22 @@
 2008-09-03  Vladimir Makarov  <vmakarov@redhat.com>
 
+	PR rtl-opt/37243
+	
+	* ira-conflicts.c (REG_SUBREG_P, go_through_subreg): New.
+	(process_regs_for_copy): Process subregs.  Refine check when cost
+	is taken into account in ira-costs.c.
+	(process_reg_shuffles): Use REG_SUBREG_P.
+	(add_insn_allocno_copies): Ditto.  Ignore modes.
+
+	* ira-color.c (conflict_allocno_vec): New.
+	(COST_HOP_DIVISOR): New macro.
+	(update_copy_costs_1): Use it.
+	(update_conflict_hard_regno_costs): New function.
+	(assign_hard_reg): Use it.
+	(ira_color): Allocate and free conflict_allocno_vec.
+ 
+2008-09-03  Vladimir Makarov  <vmakarov@redhat.com>
+
 	PR rtl-opt/37296
 
 	* ira-int.h (ira_sort_insn_chain): Remove.
diff --git a/gcc/ira-color.c b/gcc/ira-color.c
index a9a64b9..71e3f68 100644
--- a/gcc/ira-color.c
+++ b/gcc/ira-color.c
@@ -68,6 +68,9 @@ static ira_allocno_t *sorted_allocnos;
 /* Vec representing the stack of allocnos used during coloring.  */
 static VEC(ira_allocno_t,heap) *allocno_stack_vec;
 
+/* Vec representing conflict allocnos used during assigning.  */
+static VEC(ira_allocno_t,heap) *conflict_allocno_vec;
+
 /* Array used to choose an allocno for spilling.  */
 static ira_allocno_t *allocnos_for_spilling;
 
@@ -116,6 +119,11 @@ finish_cost_update (void)
   ira_free (allocno_update_cost_check);
 }
 
+/* When we traverse allocnos to update hard register costs, the cost
+   divisor will be multiplied by the following macro value for each
+   hop from given allocno to directly connected allocnos.  */
+#define COST_HOP_DIVISOR 4
+
 /* This recursive function updates costs (decrease if DECR_P) of the
    unassigned allocnos connected by copies with ALLOCNO.  This update
    increases chances to remove some copies.  Copy cost is proportional
@@ -180,7 +188,7 @@ update_copy_costs_1 (ira_allocno_t allocno, int hard_regno,
 	+= update_cost;
       if (update_cost != 0)
 	update_copy_costs_1 (another_allocno, hard_regno,
-			     decr_p, divisor * 4);
+			     decr_p, divisor * COST_HOP_DIVISOR);
     }
 }
 
@@ -193,6 +201,84 @@ update_copy_costs (ira_allocno_t allocno, bool decr_p)
   update_copy_costs_1 (allocno, ALLOCNO_HARD_REGNO (allocno), decr_p, 1);
 }
 
+/* This recursive function updates COSTS (decrease if DECR_P) by
+   conflict costs of the unassigned allocnos connected by copies with
+   ALLOCNO.  This update increases chances to remove some copies.
+   Copy cost is proportional to the copy frequency divided by
+   DIVISOR.  */
+static void
+update_conflict_hard_regno_costs (int *costs, ira_allocno_t allocno,
+				  int divisor, bool decr_p)
+{
+  int i, cost, class_size, mult, div;
+  int *conflict_costs;
+  bool cont_p;
+  enum machine_mode mode;
+  enum reg_class cover_class;
+  ira_allocno_t another_allocno;
+  ira_copy_t cp, next_cp;
+
+  cover_class = ALLOCNO_COVER_CLASS (allocno);
+  /* Probably 5 hops will be enough.  */
+  if (divisor > (COST_HOP_DIVISOR * COST_HOP_DIVISOR
+		 * COST_HOP_DIVISOR * COST_HOP_DIVISOR * COST_HOP_DIVISOR))
+    return;
+  if (cover_class == NO_REGS)
+    return;
+  /* Check that it was already visited.  */
+  if (allocno_update_cost_check[ALLOCNO_NUM (allocno)] == update_cost_check)
+    return;
+  allocno_update_cost_check[ALLOCNO_NUM (allocno)] = update_cost_check;
+  mode = ALLOCNO_MODE (allocno);
+  class_size = ira_class_hard_regs_num[cover_class];
+  for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
+    {
+      if (cp->first == allocno)
+	{
+	  next_cp = cp->next_first_allocno_copy;
+	  another_allocno = cp->second;
+	}
+      else if (cp->second == allocno)
+	{
+	  next_cp = cp->next_second_allocno_copy;
+	  another_allocno = cp->first;
+	}
+      else
+	gcc_unreachable ();
+      if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
+	  || ALLOCNO_ASSIGNED_P (another_allocno)
+	  || ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
+	continue;
+      ira_allocate_and_copy_costs
+	(&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
+	 cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
+      conflict_costs
+	= ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
+      if (conflict_costs == NULL)
+	cont_p = true;
+      else
+	{
+	  ira_assert (ALLOCNO_FREQ (another_allocno) != 0);
+	  mult = cp->freq;
+	  div = ALLOCNO_FREQ (another_allocno) * divisor;
+	  cont_p = false;
+	  for (i = class_size - 1; i >= 0; i--)
+	    {
+	      cost = conflict_costs [i] * mult / div;
+	      if (cost == 0)
+		continue;
+	      cont_p = true;
+	      if (decr_p)
+		cost = -cost;
+	      costs[i] += cost;
+	    }
+	}
+      if (cont_p)
+	update_conflict_hard_regno_costs (costs, another_allocno,
+					  divisor * COST_HOP_DIVISOR, decr_p);
+    }
+}
+
 /* Sort allocnos according to the profit of usage of a hard register
    instead of memory for them. */
 static int
@@ -246,9 +332,7 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p)
   enum reg_class cover_class, rclass;
   enum machine_mode mode;
   ira_allocno_t a, conflict_allocno;
-  ira_allocno_t another_allocno;
   ira_allocno_conflict_iterator aci;
-  ira_copy_t cp, next_cp;
   static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
 #ifdef STACK_REGS
   bool no_stack_reg_p;
@@ -333,42 +417,30 @@ assign_hard_reg (ira_allocno_t allocno, bool retry_p)
 		if (conflict_costs != NULL)
 		  for (j = class_size - 1; j >= 0; j--)
 		    full_costs[j] -= conflict_costs[j];
+		VEC_safe_push (ira_allocno_t, heap, conflict_allocno_vec,
+			       conflict_allocno);
 	      }
 	  }
       if (a == allocno)
 	break;
     }
-  /* Take copies into account.  */
+  /* Take into account preferences of allocnos connected by copies to
+     the conflict allocnos.  */
+  update_cost_check++;
+  while (VEC_length (ira_allocno_t, conflict_allocno_vec) != 0)
+    {
+      conflict_allocno = VEC_pop (ira_allocno_t, conflict_allocno_vec);
+      update_conflict_hard_regno_costs (full_costs, conflict_allocno,
+					COST_HOP_DIVISOR, true);
+    }
+  update_cost_check++;
+  /* Take preferences of allocnos connected by copies into
+     account.  */
   for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
        a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
     {
-      for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
-	{
-	  if (cp->first == a)
-	    {
-	      next_cp = cp->next_first_allocno_copy;
-	      another_allocno = cp->second;
-	    }
-	  else if (cp->second == a)
-	    {
-	      next_cp = cp->next_second_allocno_copy;
-	      another_allocno = cp->first;
-	    }
-	  else
-	    gcc_unreachable ();
-	  if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
-	      || ALLOCNO_ASSIGNED_P (another_allocno))
-	    continue;
-	  ira_allocate_and_copy_costs
-	    (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
-	     cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
-	  conflict_costs
-	    = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
-	  if (conflict_costs != NULL
-	      && ! ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
-	    for (j = class_size - 1; j >= 0; j--)
-	      full_costs[j] += conflict_costs[j];
-	}
+      update_conflict_hard_regno_costs (full_costs, a,
+					COST_HOP_DIVISOR, false);
       if (a == allocno)
 	break;
     }
@@ -2853,6 +2925,7 @@ void
 ira_color (void)
 {
   allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
+  conflict_allocno_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
   removed_splay_allocno_vec
     = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
   memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
@@ -2860,6 +2933,7 @@ ira_color (void)
   do_coloring ();
   ira_finish_assign ();
   VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
+  VEC_free (ira_allocno_t, heap, conflict_allocno_vec);
   VEC_free (ira_allocno_t, heap, allocno_stack_vec);
   move_spill_restore ();
 }
diff --git a/gcc/ira-conflicts.c b/gcc/ira-conflicts.c
index 04d3e42..97da7c5 100644
--- a/gcc/ira-conflicts.c
+++ b/gcc/ira-conflicts.c
@@ -181,7 +181,6 @@ get_dup_num (int op_num, bool use_commut_op_p)
   if (op_num < 0 || recog_data.n_alternatives == 0)
     return -1;
   op = recog_data.operand[op_num];
-  ira_assert (REG_P (op));
   commut_op_used_p = true;
   if (use_commut_op_p)
     {
@@ -295,6 +294,32 @@ get_dup (int op_num, bool use_commut_op_p)
     return recog_data.operand[n];
 }
 
+/* Check that X is REG or SUBREG of REG.  */
+#define REG_SUBREG_P(x)							\
+   (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
+
+/* Return X if X is a REG, otherwise it should be SUBREG of REG and
+   the function returns the reg in this case.  *OFFSET will be set to
+   0 in the first case or the regno offset in the first case.  */
+static rtx
+go_through_subreg (rtx x, int *offset)
+{
+  rtx reg;
+
+  *offset = 0;
+  if (REG_P (x))
+    return x;
+  ira_assert (GET_CODE (x) == SUBREG);
+  reg = SUBREG_REG (x);
+  ira_assert (REG_P (reg));
+  if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
+    *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
+				   SUBREG_BYTE (x), GET_MODE (x));
+  else
+    *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
+  return reg;
+}
+
 /* Process registers REG1 and REG2 in move INSN with execution
    frequency FREQ.  The function also processes the registers in a
    potential move insn (INSN == NULL in this case) with frequency
@@ -306,27 +331,32 @@ get_dup (int op_num, bool use_commut_op_p)
 static bool
 process_regs_for_copy (rtx reg1, rtx reg2, rtx insn, int freq)
 {
-  int hard_regno, cost, index;
+  int hard_regno, cost, index, offset1, offset2;
+  bool only_regs_p;
   ira_allocno_t a;
   enum reg_class rclass, cover_class;
   enum machine_mode mode;
   ira_copy_t cp;
 
-  gcc_assert (REG_P (reg1) && REG_P (reg2));
+  gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
+  only_regs_p = REG_P (reg1) && REG_P (reg2);
+  reg1 = go_through_subreg (reg1, &offset1);
+  reg2 = go_through_subreg (reg2, &offset2);
   if (HARD_REGISTER_P (reg1))
     {
       if (HARD_REGISTER_P (reg2))
 	return false;
-      hard_regno = REGNO (reg1);
+      hard_regno = REGNO (reg1) + offset1 - offset2;
       a = ira_curr_regno_allocno_map[REGNO (reg2)];
     }
   else if (HARD_REGISTER_P (reg2))
     {
-      hard_regno = REGNO (reg2);
+      hard_regno = REGNO (reg2) + offset2 - offset1;
       a = ira_curr_regno_allocno_map[REGNO (reg1)];
     }
   else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
-				ira_curr_regno_allocno_map[REGNO (reg2)]))
+				ira_curr_regno_allocno_map[REGNO (reg2)])
+	   && offset1 == offset2)
     {
       cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
 				 ira_curr_regno_allocno_map[REGNO (reg2)],
@@ -341,7 +371,8 @@ process_regs_for_copy (rtx reg1, rtx reg2, rtx insn, int freq)
   cover_class = ALLOCNO_COVER_CLASS (a);
   if (! ira_class_subset_p[rclass][cover_class])
     return false;
-  if (reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
+  if (reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode)
+      && only_regs_p)
     /* It is already taken into account in ira-costs.c.  */
     return false;
   index = ira_class_hard_reg_index[cover_class][hard_regno];
@@ -371,12 +402,12 @@ process_reg_shuffles (rtx reg, int op_num, int freq)
   int i;
   rtx another_reg;
 
-  gcc_assert (REG_P (reg));
+  gcc_assert (REG_SUBREG_P (reg));
   for (i = 0; i < recog_data.n_operands; i++)
     {
       another_reg = recog_data.operand[i];
       
-      if (!REG_P (another_reg) || op_num == i
+      if (!REG_SUBREG_P (another_reg) || op_num == i
 	  || recog_data.operand_type[i] != OP_OUT)
 	continue;
       
@@ -399,9 +430,12 @@ add_insn_allocno_copies (rtx insn)
   if (freq == 0)
     freq = 1;
   if ((set = single_set (insn)) != NULL_RTX
-      && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
+      && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
       && ! side_effects_p (set)
-      && find_reg_note (insn, REG_DEAD, SET_SRC (set)) != NULL_RTX)
+      && find_reg_note (insn, REG_DEAD,
+			REG_P (SET_SRC (set))
+			? SET_SRC (set)
+			: SUBREG_REG (SET_SRC (set))) != NULL_RTX)
     process_regs_for_copy (SET_DEST (set), SET_SRC (set), insn, freq);
   else
     {
@@ -409,8 +443,10 @@ add_insn_allocno_copies (rtx insn)
       for (i = 0; i < recog_data.n_operands; i++)
 	{
 	  operand = recog_data.operand[i];
-	  if (REG_P (operand)
-	      && find_reg_note (insn, REG_DEAD, operand) != NULL_RTX)
+	  if (REG_SUBREG_P (operand)
+	      && find_reg_note (insn, REG_DEAD,
+				REG_P (operand)
+				? operand : SUBREG_REG (operand)) != NULL_RTX)
 	    {
 	      str = recog_data.constraints[i];
 	      while (*str == ' ' && *str == '\t')
@@ -418,7 +454,7 @@ add_insn_allocno_copies (rtx insn)
 	      bound_p = false;
 	      for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
 		if ((dup = get_dup (i, commut_p)) != NULL_RTX
-		    && REG_P (dup) && GET_MODE (operand) == GET_MODE (dup)
+		    && REG_SUBREG_P (dup)
 		    && process_regs_for_copy (operand, dup, NULL_RTX, freq))
 		  bound_p = true;
 	      if (bound_p)