Re: Problems with the way we calculate costs

[Bernd Schmidt <bernds at redhat dot co dot uk>]

On Mon, 11 Sep 2000, Geoff Keating wrote:

> > Date: Mon, 11 Sep 2000 10:15:25 +0100 (BST)
> > From: Bernd Schmidt <bernds@redhat.co.uk>
> > cc: gcc-patches@gcc.gnu.org
> > 
> > On Mon, 11 Sep 2000, Geoff Keating wrote:
> > 
> > > It'd probably be better if it worked like the original code; that is,
> > > the cost of a non-fixed hard register is 2, compared to 1 for a
> > > pseudo.  This ensures a pseudo gets preference, which would be the
> > > usual case because such hard registers should be copied into pseudos
> > > immediately after they appear.
> > 
> > The original code mixed up these register pressure considerations with
> > the calculation of the cost of an operation.  I still think this is a
> > bad idea.  It also won't reliably prevent lifetimes of hard registers
> > from being lenghtened (think of computing the cost of a shift of a
> > hardreg as opposed to multiplication of a pseudo).
> 
> I don't mind hard register lifetimes being lengthened if it really
> makes the program faster; what I was complaining about is when a
> hardreg and a pseudo are equivalent and the hardreg gets preference.

Hmm.  OK.  How about the patch below?  I incorporated a few suggestions
from other people as well (moved COSTS_N_INSNS into rtl.h and added a new
macro MAX_COST).  I've also changed COSTS_N_INSNS to (4 * N) to restore
some of the old cost relationships we use to have in the compiler.

> Probably the macro to consider is SMALL_REGISTER_CLASSES.

With the patch, we'll either consider hard regs having a cost of 2 (for
non-SRC machines), or forcing a return value of MAX_COST (for SRC).

Bernd

	* cse.c (approx_reg_cost): If SMALL_REGISTER_CLASSES, return INT_MAX
	if a reference to non-fixed hardreg is seen.  Otherwise, count hard
	regs with a higher cost.
	(preferrable): Deal with cases where either cost or regcost is
	MAX_COST.
	(cse_insn): Use MAX_COST rather than 10000.  Always initialize
	regcost values.
	(COSTS_N_INSNS): Move definition...
	* rtl.h: ...here.
	(MAX_COST): New macro.
	* loop.c (init_loop): Use COSTS_N_INSNS macro instead of hardcoded
	constant.

Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.282
diff -u -p -r1.282 loop.c
--- loop.c	2000/09/09 23:02:15	1.282
+++ loop.c	2000/09/11 14:55:55
@@ -328,7 +328,7 @@ init_loop ()
 
   reg_address_cost = address_cost (reg, SImode);
 
-  copy_cost = 2;
+  copy_cost = COSTS_N_INSNS (1);
 
   /* Free the objects we just allocated.  */
   obfree (free_point);
Index: cse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cse.c,v
retrieving revision 1.156
diff -u -p -r1.156 cse.c
--- cse.c	2000/09/06 09:20:37	1.156
+++ cse.c	2000/09/11 14:55:58
@@ -730,7 +730,7 @@ approx_reg_cost_1 (xp, data)
 /* Return an estimate of the cost of the registers used in an rtx.
    This is mostly the number of different REG expressions in the rtx;
    however for some excecptions like fixed registers we use a cost of
-   0.  */
+   0.  If any other hard register reference occurs, return INT_MAX.  */
 
 static int
 approx_reg_cost (x)
@@ -739,6 +739,7 @@ approx_reg_cost (x)
   regset_head set;
   int i;
   int cost = 0;
+  int hardregs = 0;
 
   INIT_REG_SET (&set);
   for_each_rtx (&x, approx_reg_cost_1, (void *)&set);
@@ -747,11 +748,16 @@ approx_reg_cost (x)
     (&set, 0, i,
      {
        if (! CHEAP_REGNO (i))
-	 cost++;
+	 {
+	   if (i < FIRST_PSEUDO_REGISTER)
+	     hardregs++;
+
+	   cost += i < FIRST_PSEUDO_REGISTER ? 2 : 1;
+	 }
      });
 
   CLEAR_REG_SET (&set);
-  return cost;
+  return hardregs && SMALL_REGISTER_CLASSES ? INT_MAX : cost;
 }
 
 /* Return a negative value if an rtx A, whose costs are given by COST_A
@@ -762,8 +768,29 @@ static int
 preferrable (cost_a, regcost_a, cost_b, regcost_b)
      int cost_a, regcost_a, cost_b, regcost_b;
 {
+  /* First, get rid of a cases involving expressions that are entirely
+     unwanted.  */
   if (cost_a != cost_b)
+    {
+      if (cost_a == INT_MAX)
+	return 1;
+      if (cost_b == INT_MAX)
+	return -1;
+    }
+
+  /* Avoid extending lifetimes of hardregs.  */
+  if (regcost_a != regcost_b)
+    {
+      if (regcost_a == INT_MAX)
+	return 1;
+      if (regcost_b == INT_MAX)
+	return -1;
+    }
+
+  /* Normal operation costs take precedence.  */
+  if (cost_a != cost_b)
     return cost_a - cost_b;
+  /* Only if these are identical consider effects on register pressure.  */
   if (regcost_a != regcost_b)
     return regcost_a - regcost_b;
   return 0;
@@ -789,12 +816,6 @@ notreg_cost (x)
 	  : rtx_cost (x, SET) * 2);
 }
 
-/* Return the right cost to give to an operation
-   to make the cost of the corresponding register-to-register instruction
-   N times that of a fast register-to-register instruction.  */
-
-#define COSTS_N_INSNS(N) ((N) * 2)
-
 /* Return an estimate of the cost of computing rtx X.
    One use is in cse, to decide which expression to keep in the hash table.
    Another is in rtl generation, to pick the cheapest way to multiply.
@@ -4874,8 +4895,8 @@ cse_insn (insn, libcall_insn)
       rtx src_const = 0;
       rtx src_related = 0;
       struct table_elt *src_const_elt = 0;
-      int src_cost = 10000, src_eqv_cost = 10000, src_folded_cost = 10000;
-      int src_related_cost = 10000, src_elt_cost = 10000;
+      int src_cost = MAX_COST, src_eqv_cost = MAX_COST, src_folded_cost = MAX_COST;
+      int src_related_cost = MAX_COST, src_elt_cost = MAX_COST;
       int src_regcost, src_eqv_regcost, src_folded_regcost;
       int src_related_regcost, src_elt_regcost;
       /* Set non-zero if we need to call force_const_mem on with the
@@ -5284,7 +5305,7 @@ cse_insn (insn, libcall_insn)
       if (src)
 	{
 	  if (rtx_equal_p (src, dest))
-	    src_cost = -1;
+	    src_cost = src_regcost = -1;
 	  else
 	    {
 	      src_cost = COST (src);
@@ -5295,7 +5316,7 @@ cse_insn (insn, libcall_insn)
       if (src_eqv_here)
 	{
 	  if (rtx_equal_p (src_eqv_here, dest))
-	    src_eqv_cost = -1;
+	    src_eqv_cost = src_eqv_regcost = -1;
 	  else
 	    {
 	      src_eqv_cost = COST (src_eqv_here);
@@ -5306,7 +5327,7 @@ cse_insn (insn, libcall_insn)
       if (src_folded)
 	{
 	  if (rtx_equal_p (src_folded, dest))
-	    src_folded_cost = -1;
+	    src_folded_cost = src_folded_regcost = -1;
 	  else
 	    {
 	      src_folded_cost = COST (src_folded);
@@ -5317,7 +5338,7 @@ cse_insn (insn, libcall_insn)
       if (src_related)
 	{
 	  if (rtx_equal_p (src_related, dest))
-	    src_related_cost = -1;
+	    src_related_cost = src_related_regcost = -1;
 	  else
 	    {
 	      src_related_cost = COST (src_related);
@@ -5328,7 +5349,7 @@ cse_insn (insn, libcall_insn)
       /* If this was an indirect jump insn, a known label will really be
 	 cheaper even though it looks more expensive.  */
       if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
-	src_folded = src_const, src_folded_cost = -1;
+	src_folded = src_const, src_folded_cost = src_folded_regcost -1;
 
       /* Terminate loop when replacement made.  This must terminate since
          the current contents will be tested and will always be valid.  */
@@ -5378,7 +5399,7 @@ cse_insn (insn, libcall_insn)
 	      && preferrable (src_folded_cost, src_folded_regcost,
 			      src_elt_cost, src_elt_regcost) <= 0)
 	    {
-	      trial = src_folded, src_folded_cost = 10000;
+	      trial = src_folded, src_folded_cost = MAX_COST;
 	      if (src_folded_force_flag)
 		trial = force_const_mem (mode, trial);
 	    }
@@ -5388,20 +5409,20 @@ cse_insn (insn, libcall_insn)
 				   src_related_cost, src_related_regcost) <= 0
 		   && preferrable (src_cost, src_regcost,
 				   src_elt_cost, src_elt_regcost) <= 0)
-	    trial = src, src_cost = 10000;
+	    trial = src, src_cost = MAX_COST;
 	  else if (preferrable (src_eqv_cost, src_eqv_regcost,
 				src_related_cost, src_related_regcost) <= 0
 		   && preferrable (src_eqv_cost, src_eqv_regcost,
 				   src_elt_cost, src_elt_regcost) <= 0)
-	    trial = copy_rtx (src_eqv_here), src_eqv_cost = 10000;
+	    trial = copy_rtx (src_eqv_here), src_eqv_cost = MAX_COST;
 	  else if (preferrable (src_related_cost, src_related_regcost,
 				src_elt_cost, src_elt_regcost) <= 0)
-  	    trial = copy_rtx (src_related), src_related_cost = 10000;
+  	    trial = copy_rtx (src_related), src_related_cost = MAX_COST;
 	  else
 	    {
 	      trial = copy_rtx (elt->exp);
 	      elt = elt->next_same_value;
-	      src_elt_cost = 10000;
+	      src_elt_cost = MAX_COST;
 	    }
 
 	  /* We don't normally have an insn matching (set (pc) (pc)), so
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/rtl.h,v
retrieving revision 1.221
diff -u -p -r1.221 rtl.h
--- rtl.h	2000/09/02 02:54:54	1.221
+++ rtl.h	2000/09/11 14:55:58
@@ -1633,6 +1633,16 @@ extern void push_obstacks		PARAMS ((stru
 						struct obstack *));
 /* In cse.c */
 struct cse_basic_block_data;
+
+/* Return the right cost to give to an operation
+   to make the cost of the corresponding register-to-register instruction
+   N times that of a fast register-to-register instruction.  */
+#define COSTS_N_INSNS(N) ((N) * 4)
+
+/* Maximum cost of a rtl expression.  This value has the special meaning
+   not to use an rtx with this cost under any circumstances.  */
+#define MAX_COST INT_MAX
+
 extern int rtx_cost			PARAMS ((rtx, enum rtx_code));
 extern int address_cost			PARAMS ((rtx, enum machine_mode));
 extern void delete_trivially_dead_insns	PARAMS ((rtx, int));