memory is not free

[Mike Stump <mrs at windriver dot com>]

Memory is not free...

Repeat after me, I won't test gcc on 256 meg machines, I will only
test on 4 meg machines...  I don't care how ugly the code is, 90%
reduction in stack space is way to valuable (why does my program seg
fault the compiler?) to pass up:

1999-11-30  Mike Stump  <mrs@wrs.com>

	* ggc-common.c (ggc_mark_rtx_children): Reduce stack consumption by
	90% by handling element 1 via tail recursion, and hand eliminate
	the tail recursion.  Saves about 7.2% of total memory requirements
	on random C++ code.

If you have never seen a 62000 deep call chain on a 255 line C++
program, oh boy, you're in for a treat, look fast before we fix it.  I
checked my testcase, and the center mass in the call chain all was
this exact case.  Why did it blow it out?  I am on a sparc, and I
noticed each recursion consumed a raw 32x the number of bytes needed.
This would be better to do it with a iterative breadth first search
with a memory efficient queue, but I leave that to the next person
that cares.  My scheme was the quick 5 line patch that nets a 90%
savings.  The better method will only net another 96% savings at most,
but it isn't very worthwhile as that stack space used post the below
patch is almost all the stack we already otherwise use.  The savings
with my patch are `real', this is the only routine that allocated and
used the stack space.

Doing diffs in ggc-common.c.~1~:
*** ggc-common.c.~1~	Mon Nov 29 13:14:09 1999
--- ggc-common.c	Tue Nov 30 13:46:28 1999
*************** ggc_mark_rtx_children (r)
*** 234,240 ****
  {
    const char *fmt;
    int i;
!   enum rtx_code code = GET_CODE (r);
  
    /* Collect statistics, if appropriate.  */
    if (ggc_stats)
--- 234,245 ----
  {
    const char *fmt;
    int i;
!   enum rtx_code code;
!   rtx tail_rtx;
! 
!  top:
!   tail_rtx = 0;
!   code = GET_CODE (r);
  
    /* Collect statistics, if appropriate.  */
    if (ggc_stats)
*************** ggc_mark_rtx_children (r)
*** 294,300 ****
        switch (*fmt)
  	{
  	case 'e': case 'u':
! 	  ggc_mark_rtx (XEXP (r, i));
  	  break;
  	case 'V': case 'E':
  	  ggc_mark_rtvec (XVEC (r, i));
--- 299,313 ----
        switch (*fmt)
  	{
  	case 'e': case 'u':
! 	  if (i==1
! 	      && XEXP (r, i) != 0
! 	      && ! ggc_set_mark (XEXP (r, i)))
! 	    {
! 	      /* Do element 1 via hand eliminated tail recursion.  */
! 	      tail_rtx = XEXP (r, i);
! 	    }
! 	  else
! 	    ggc_mark_rtx (XEXP (r, i));
  	  break;
  	case 'V': case 'E':
  	  ggc_mark_rtvec (XVEC (r, i));
*************** ggc_mark_rtx_children (r)
*** 303,308 ****
--- 316,327 ----
  	  ggc_mark_if_gcable (XSTR (r, i));
  	  break;
  	}
+     }
+ 
+   if (tail_rtx)
+     {
+       r = tail_rtx;
+       goto top;
      }
  }
  
--------------