[PATCH] Fix sched-ebb.c bug (was Re: [3.3 branch] IA64 bootstrap failure)

[Jakub Jelinek <jakub at redhat dot com>]

On Wed, Jul 09, 2003 at 10:35:02PM -0700, Jim Wilson wrote:
> On Wed, 2003-07-09 at 16:35, Jakub Jelinek wrote: 
> > Maybe add a flag to cselib, such that remove_useless_values is never called
> > from cselib_process_insn if called from sched-deps.c.
> I haven't looked at cselib before, so I don't know too much about how it
> works. 
> 
> It does look like there is a modularity violation here.  The value RTL
> was originally designed to be local to the cselib module.  Then later a
> cselib_subst_to_values call was added into sched-deps, and now there are
> value RTL objects outside cselib that aren't being tracked.  These turn
> into dangling pointers when cselib frees up unused values, and then we
> get problems when we dereference the dangling pointers. 
> 
> Since we have to call cselib_init before using cselib_subst_to_values,
> we could perhaps pass an extra argument to cselib_init to solve the
> problem.  Telling it not to free apparently unused value objects would
> be easy, but will increase memory usage by an unknown amount. 

I gathered some statistics (though just from full IA-64 gcc-3_3-rhl-branch
bootstrap (all langs)). In the worst case, there were
6063 cselib_val, 11334 elt_list and 14762 elt_loc_list structs which would
GCC put onto emtpy_vals/empty_elt_lists/empty_elt_loc_lists chains during
a single extended basic block processing, which is around 900KB.
The second worst case would be around 450KB and then quickly go to
uninteresting values (just about 20 compilations would use more than 50KB).
Attached is the simplest patch (ie. postpone remove_useless_values if
cselib_subst_to_values is called until cselib_finish, which during
sched-ebb.c is at the end of each extended basic block).
I'm still bootstrapping the patch, so don't know if it works as it should,
but IMHO this should be the starting point, so that others can try
if they see the same problem as I was seeing.

Now, are those memory consumptions unacceptable (for 3.3, or for mainline)?
If yes, is it ok if we get rid of them just on 64-bit hosts (sched-ebb.c
is by default used AFAIK on IA-64 target, so that would save memory during
IA-64 native compilations)?
Also, do we want to refcount the cselib_subst_to_values'ed cselib_val's
(which would mean tracking where we release last references to them),
or just flag them as never useless when cselib_subst_to_values is called
and only free them at cselib_finish time?
For 64-bit we could add either flag or refcount into the spare 32-bit pad
in cselib_val.
For 32-bit hosts if we just want to flag and not refcount,
we could maybe chain some magic struct elt_list at the end of addr_list
chain which would be shared by all marked cselib_val structs.
For refcounting on 32-bit hosts I'm afraid we'd have to grow cselib_val.

2003-07-15  Jakub Jelinek  <jakub@redhat.com>

	* cselib.c (cselib_subst_to_values_1): Renamed from
	cselib_subst_to_values.
	(cselib_subst_to_values): Set max_useless_values to INT_MAX,
	call cselib_subst_to_values_1.
	(max_useless_values): New variable.
	(cselib_lookup): Call cselib_subst_to_values_1.
	(cselib_process_insn): Change MAX_USELESS_VALUES into
	max_useless_values.
	(cselib_init): Initialize max_useless_values to MAX_USELESS_VALUES.
	(cselib_finish): Call remove_useless_values.

--- gcc/cselib.c.jj	2003-06-10 18:29:24.000000000 -0400
+++ gcc/cselib.c	2003-07-15 16:39:19.000000000 -0400
@@ -67,6 +67,8 @@ static void cselib_invalidate_rtx	PARAMS
 static void cselib_record_set		PARAMS ((rtx, cselib_val *,
 						 cselib_val *));
 static void cselib_record_sets		PARAMS ((rtx));
+static rtx cselib_subst_to_values_1	PARAMS ((rtx));
+
 
 /* There are three ways in which cselib can look up an rtx:
    - for a REG, the reg_values table (which is indexed by regno) is used
@@ -98,6 +100,8 @@ static int n_useless_values;
 /* Number of useless values before we remove them from the hash table.  */
 #define MAX_USELESS_VALUES 32
 
+static int max_useless_values;
+
 /* This table maps from register number to values.  It does not contain
    pointers to cselib_val structures, but rather elt_lists.  The purpose is
    to be able to refer to the same register in different modes.  */
@@ -775,8 +779,8 @@ cselib_lookup_mem (x, create)
    X isn't actually modified; if modifications are needed, new rtl is
    allocated.  However, the return value can share rtl with X.  */
 
-rtx
-cselib_subst_to_values (x)
+static rtx
+cselib_subst_to_values_1 (x)
      rtx x;
 {
   enum rtx_code code = GET_CODE (x);
@@ -827,7 +831,7 @@ cselib_subst_to_values (x)
     {
       if (fmt[i] == 'e')
 	{
-	  rtx t = cselib_subst_to_values (XEXP (x, i));
+	  rtx t = cselib_subst_to_values_1 (XEXP (x, i));
 
 	  if (t != XEXP (x, i) && x == copy)
 	    copy = shallow_copy_rtx (x);
@@ -840,7 +844,7 @@ cselib_subst_to_values (x)
 
 	  for (j = 0; j < XVECLEN (x, i); j++)
 	    {
-	      rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
+	      rtx t = cselib_subst_to_values_1 (XVECEXP (x, i, j));
 
 	      if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
 		{
@@ -860,6 +864,20 @@ cselib_subst_to_values (x)
   return copy;
 }
 
+/* Walk rtx X and replace all occurrences of REG and MEM subexpressions
+   with VALUE expressions.  This way, it becomes independent of changes
+   to registers and memory.
+   X isn't actually modified; if modifications are needed, new rtl is
+   allocated.  However, the return value can share rtl with X.  */
+
+rtx
+cselib_subst_to_values (x)
+     rtx x;
+{
+  max_useless_values = INT_MAX;
+  return cselib_subst_to_values_1 (x);
+}
+
 /* Look up the rtl expression X in our tables and return the value it has.
    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
    we create a new one if possible, using mode MODE if X doesn't have a mode
@@ -934,7 +952,7 @@ cselib_lookup (x, mode, create)
      the hash table is inconsistent until we do so, and
      cselib_subst_to_values will need to do lookups.  */
   *slot = (void *) e;
-  e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
+  e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values_1 (x));
   return e;
 }
 
@@ -1370,7 +1388,7 @@ cselib_process_insn (insn)
 
   cselib_current_insn = 0;
 
-  if (n_useless_values > MAX_USELESS_VALUES)
+  if (n_useless_values > max_useless_values)
     remove_useless_values ();
 }
 
@@ -1400,6 +1418,8 @@ cselib_init ()
   if (! callmem)
     callmem = gen_rtx_MEM (BLKmode, const0_rtx);
 
+  max_useless_values = MAX_USELESS_VALUES;
+
   cselib_nregs = max_reg_num ();
   if (reg_values_old != NULL && VARRAY_SIZE (reg_values_old) >= cselib_nregs)
     {
@@ -1424,6 +1444,10 @@ cselib_init ()
 void
 cselib_finish ()
 {
+  if (n_useless_values > MAX_USELESS_VALUES
+      && max_useless_values == INT_MAX)
+    remove_useless_values ();
+
   reg_values_old = reg_values;
   reg_values = 0;
   used_regs_old = used_regs;


	Jakub