[RFC] Make regclass optimistic about union register classes

[Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>]

This is a patch based on an old proposal by Jan Hubicka, which can be 
found at http://www.x86-64.org/lists/patches/msg00271.html.

This patch removes the need for all the '#' constraints in i386.md and 
possibly other MDs too.  When presented with an union class (e.g. 
FLOAT_INT_CLASS), regclass sees an alternative accepting FLOAT_CLASS and 
one accepting GENERAL_CLASS; in both cases he adds move cost for moving 
from SSE_FLOAT_CLASS to each of them: this is large because it is 
computed conservativly in case the pseudo ends up outside the 
destination class.  Then it decides randomly for one of the classes 
depending on the REGISTER_MOVE_COST differences. Thus we need to fake 
those superclass alternatives by always using r#fx or f#xr.

The patch fixes this by making regclass optimistic and not adding the 
cost when the alternate class is a superset of the preferred class.  It 
also fixes the cost computation to take into account properly 
may_move_in_cost or may_move_out_cost as in other parts of regclass.  is 
ommision in my regclass patches two years ago.

When originally submitted, rth did not approve the patch because it 
gives strange results in the lreg dump:

  main()
  {
      float b,c;
      asm volatile ("# %0 %1":"=&f,&r"(c):"f,r"(b));
      asm volatile ("# %0"::"f,r"(c));
  }

gives

  Register 58: GENERAL_REGS:0 FLOAT_REGS:0 FLOAT_INT_REGS:20000 MEM:6000
  Register 59: GENERAL_REGS:0 FLOAT_REGS:0 FLOAT_INT_REGS:10000 MEM:3000

  Register 58 pref FLOAT_INT_REGS or none
  Register 59 pref FLOAT_INT_REGS or none

It sure looks like GCC chooses the most expensive class, but actually 
FLOAT_INT_REGS is picked as the *union of the two classes with the 
minimum cost*, GENERAL_REGS and FLOAT_REGS.  I have then modified 
regclass to dump it like this:

  Register 58
   pref FLOAT_REGS + GENERAL_REGS = FLOAT_INT_REGS
   or none
  Register 59
   pref FLOAT_REGS + GENERAL_REGS = FLOAT_INT_REGS
   or none

I'll let a maintainer decide if this would be ok for stage3, so I post 
this as an RFC before bootstrapping and regtesting.  It does allow a 
significant cleanup of the # constraints in the fp templates, which also 
fixes some pessimizations with -mfpmath=sse.

Richard (Guenther), you may want test tramp3ds+libsse2 with this patch 
and something like http://www.x86-64.org/lists/patches/msg00272.html 
(the i386 constraint cleanup)?

Paolo
2005-07-13  Paolo Bonzini  <bonzini@gnu.org>

	* regclass.c (move_cost_for_alternate_class, dump_class_formation):
	New.
	(regclass): Use dump_class_formation.
	(record_reg_classes): Use move_cost_for_alternate_class to be more
	optimistic.

Index: regclass.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/regclass.c,v
retrieving revision 1.206
diff -u -p -r1.206 regclass.c
--- regclass.c	25 Jun 2005 02:00:52 -0000	1.206
+++ regclass.c	13 Jul 2005 13:49:02 -0000
@@ -607,6 +607,26 @@ init_fake_stack_mems (void)
 #endif
 }
 
+/* Return the cost of moving a register from the PREFERRED class to the
+   ALTERNATE or vice versa (depending on MOVE_IN), in the mode MODE.
+
+   Return 0 if the alternate class is a superset of preferred, hoping that
+   the preferred class will be used anyway.  */
+static int
+move_cost_for_alternate_class (enum reg_class preferred,
+			       enum reg_class alternate,
+			       enum machine_mode mode,
+			       bool move_in_alternate)
+{
+  if (reg_class_subset_p (preferred, alternate))
+    return 0;
+
+  if (move_in_alternate)
+    return may_move_in_cost[mode][(int) preferred][(int) alternate];
+  else
+    return may_move_out_cost[mode][(int) alternate][(int) preferred];
+}
+
 #ifdef HAVE_SECONDARY_RELOADS
 
 /* Compute extra cost of moving registers to/from memory due to reloads.
@@ -953,6 +973,32 @@ dump_regclass (FILE *dump)
 	}
     }
 }
+
+/* The register class, CLASS, is the union of all the classes whose cost
+   is COST.  Dump how it was built.  */
+static void
+dump_class_formation (FILE *dump, int *costs, int cost, enum reg_class best)
+{
+  int n;
+  enum reg_class class, cur_best = NO_REGS;
+  for (n = 0, class = (int) ALL_REGS - 1; class > 0; class--)
+    if (costs[class] == cost)
+      {
+	enum reg_class new_best = reg_class_subunion[(int) cur_best][class];
+	if (cur_best == new_best)
+	  continue;
+
+	cur_best = new_best;
+	fprintf (dump, "%s %s", (n ? " +" : ""), reg_class_names[class]);
+	n++;
+      }
+
+  gcc_assert (cur_best == best);
+  if (n > 1)
+    fprintf (dump, " = %s\n", reg_class_names[(int) best]);
+  else
+    fprintf (dump, "\n");
+}
 
 
 /* Calculate the costs of insn operands.  */
@@ -1347,19 +1393,14 @@ regclass (rtx f, int nregs, FILE *dump)
 	  if (alt == best)
 	    alt = NO_REGS;
 
-	  if (dump
-	      && (reg_pref[i].prefclass != (int) best
-		  || reg_pref[i].altclass != (int) alt))
+	  if (dump)
 	    {
-	      fprintf (dump, "  Register %i", i);
-	      if (alt == ALL_REGS || best == ALL_REGS)
-		fprintf (dump, " pref %s\n", reg_class_names[(int) best]);
-	      else if (alt == NO_REGS)
-		fprintf (dump, " pref %s or none\n", reg_class_names[(int) best]);
-	      else
-		fprintf (dump, " pref %s, else %s\n",
-			 reg_class_names[(int) best],
-			 reg_class_names[(int) alt]);
+	      fprintf (dump, "  Register %i\n   pref", i);
+	      dump_class_formation (dump, p->cost, best_cost, best);
+	      if (alt == NO_REGS && best != ALL_REGS)
+		fprintf (dump, "   or none\n");
+	      else if (alt != ALL_REGS && best != ALL_REGS)
+		fprintf (dump, "   else %s\n", reg_class_names[(int) alt]);
 	    }
 
 	  /* We cast to (int) because (char) hits bugs in some compilers.  */
@@ -1529,10 +1570,10 @@ record_reg_classes (int n_alts, int n_op
 		     appropriate class.  */
 
 		  if (reg_pref)
-		    alt_cost
-		      += (may_move_in_cost[mode]
-			  [(unsigned char) reg_pref[REGNO (op)].prefclass]
-			  [(int) classes[i]]);
+		    alt_cost +=
+		      move_cost_for_alternate_class (
+			reg_pref[REGNO (op)].prefclass, classes[i], mode,
+		        recog_data.operand_type[i] == OP_OUT);
 
 		  if (REGNO (ops[i]) != REGNO (ops[j])
 		      && ! find_reg_note (insn, REG_DEAD, op))
@@ -1755,10 +1796,10 @@ record_reg_classes (int n_alts, int n_op
 		     appropriate class.  */
 
 		  if (reg_pref)
-		    alt_cost
-		      += (may_move_in_cost[mode]
-			  [(unsigned char) reg_pref[REGNO (op)].prefclass]
-			  [(int) classes[i]]);
+		    alt_cost +=
+		      move_cost_for_alternate_class (
+			reg_pref[REGNO (op)].prefclass, classes[i], mode,
+		        recog_data.operand_type[i] == OP_OUT);
 		}
 	    }