[PATCH] cselib_invalidate_regno performance

[David S. Miller]

Ok, here is another try at this, based upon Bernd's analysis.
(although oddly he commented on this patch rather than the one
 I actually sought input from him on, the approx_reg_cost stuff
 since he is the one who added that :-)

I do the same thing that regrename.c does to handle this situation
during kill_value().  Every time a hard register is added to the
REG_VALUES table, we see if it's size is larger than any other hard
register value we've added to the table already.

This is then used in cse_invalidate_regno to determine exactly
which hard registers need to be scanned.

Comments?

2002-05-20  David S. Miller  <davem@redhat.com>

	* cselib.c (max_value_regs): New.
	(cselib_lookup, cselib_invalidate_regno): Initialize it when
	adding new entries to the REG_VALUES table and we are dealing with
	a hard register.
	(clear_table): Initialize it.
	(cselib_invalidate_regno): Use it to determine which hard
	registers to scan when mode is not VOIDmode.

--- cselib.c.~1~	Mon May 20 18:20:19 2002
+++ cselib.c	Mon May 20 18:21:28 2002
@@ -104,6 +104,10 @@ static int n_useless_values;
 static varray_type reg_values;
 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
 
+/* The largest number of hard regs used by any entry added to the
+   REG_VALUES table.  Cleared on each clear_table() invocation.   */
+static unsigned int max_value_regs;
+
 /* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used
    in clear_table() for fast emptying.  */
 static varray_type used_regs;
@@ -227,6 +231,8 @@ clear_table (clear_all)
     for (i = 0; i < VARRAY_ACTIVE_SIZE (used_regs); i++)
       REG_VALUES (VARRAY_UINT (used_regs, i)) = 0;
 
+  max_value_regs = 0;
+
   VARRAY_POP_ALL (used_regs);
 
   htab_empty (hash_table);
@@ -897,6 +903,14 @@ cselib_lookup (x, mode, create)
       if (! create)
 	return 0;
 
+      if (i < FIRST_PSEUDO_REGISTER)
+	{
+	  unsigned int n = HARD_REGNO_NREGS (i, mode);
+
+	  if (n > max_value_regs)
+	    max_value_regs = n;
+	}
+
       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
       e->locs = new_elt_loc_list (e->locs, x);
       if (REG_VALUES (i) == 0)
@@ -957,11 +971,22 @@ cselib_invalidate_regno (regno, mode)
      pseudos, only REGNO is affected.  For hard regs, we must take MODE
      into account, and we must also invalidate lower register numbers
      if they contain values that overlap REGNO.  */
-  endregno = regno + 1;
   if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode) 
-    endregno = regno + HARD_REGNO_NREGS (regno, mode);
+    {
+      if (regno < max_value_regs)
+	i = 0;
+      else
+	i = regno - max_value_regs;
 
-  for (i = 0; i < endregno; i++)
+      endregno = regno + HARD_REGNO_NREGS (regno, mode);
+    }
+  else
+    {
+      i = regno;
+      endregno = regno + 1;
+    }
+
+  for (; i < endregno; i++)
     {
       struct elt_list **l = &REG_VALUES (i);
 
@@ -1170,6 +1195,14 @@ cselib_record_set (dest, src_elt, dest_a
     {
       if (REG_VALUES (dreg) == 0)
         VARRAY_PUSH_UINT (used_regs, dreg);
+
+      if (dreg < FIRST_PSEUDO_REGISTER)
+	{
+	  unsigned int n = HARD_REGNO_NREGS (dreg, GET_MODE (dest));
+
+	  if (n > max_value_regs)
+	    max_value_regs = n;
+	}
 
       REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
       if (src_elt->locs == 0)