Speeding up ggc-simple on stage1

[Alexandre Oliva <oliva at lsd dot ic dot unicamp dot br>]

stage1 is usually built without optimization (couldn't this change, at
least when the bootstrap compiler is gcc?).  Unfortunately, I've got a
slow powerpc running AIX 4.1 (it won't run GNU/Linux :-(, that takes
ages to build stage2 and, it seems that, whenever I attach gdb to cc1,
it's within running garbage collection code :-(

I believe reducing stack usage for garbage collection could help it
some, so I've tried to rewrite some (all?) of the recursive functions
in ggc-simple to try to avoid recursion as much as possible.  I can't
say that know it's fast, but it seems to have improved a bit.

I believe gcc would notice it could tail-recurse with optimization (I
haven't checked), but, with this patch, we'd get tail recursion even
with -O0.

Is this ok to install?

Index: gcc/ggc-simple.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ggc-simple.c,v
retrieving revision 1.28
diff -u -p -r1.28 ggc-simple.c
--- gcc/ggc-simple.c	1999/12/26 23:06:54	1.28
+++ gcc/ggc-simple.c	2000/01/08 20:48:04
@@ -1,5 +1,5 @@
 /* Simple garbage collection for the GNU compiler.
-   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
 
    This file is part of GNU CC.
 
@@ -277,11 +277,20 @@ static void
 clear_marks (x)
      struct ggc_mem *x;
 {
-  x->mark = 0;
-  if (x->sub[0])
-    clear_marks (x->sub[0]);
-  if (x->sub[1])
-    clear_marks (x->sub[1]);
+  for (;;) {
+    x->mark = 0;
+    if (x->sub[1] && x->sub[0])
+      {
+	clear_marks (x->sub[0]);
+	x = x->sub[1];
+      }
+    else if (x->sub[1])
+      x = x->sub[1];
+    else if (x->sub[0])
+      x = x->sub[0];
+    else
+      break;
+  }
 }
 
 /* Free all objects in the current context that are not marked.  */
@@ -420,12 +429,21 @@ ggc_pop_context_1 (x, c)
      struct ggc_mem *x;
      int c;
 {
-  if (x->context > c)
-    x->context = c;
-  if (x->sub[0])
-    ggc_pop_context_1 (x->sub[0], c);
-  if (x->sub[1])
-    ggc_pop_context_1 (x->sub[1], c);
+  for (;;) {
+    if (x->context > c)
+      x->context = c;
+    if (x->sub[1] && x->sub[0])
+      {
+	ggc_pop_context_1 (x->sub[0], c);
+	x = x->sub[1];
+      }
+    else if (x->sub[1])
+      x = x->sub[1];
+    else if (x->sub[0])
+      x = x->sub[0];
+    else
+      break;
+  }
 }
 
 /* Dump a tree.  */
@@ -482,17 +500,29 @@ tally_leaves (x, depth, nleaf, sumdepth)
      size_t *nleaf;
      size_t *sumdepth;
 {
-  if (! x->sub[0] && !x->sub[1])
-    {
-      *nleaf += 1;
-      *sumdepth += depth;
-    }
-  else
-    {
-      if (x->sub[0])
-	tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
-      if (x->sub[1])
-	tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
+  for (;;) {
+    if (! x->sub[0] && !x->sub[1])
+      {
+	*nleaf += 1;
+	*sumdepth += depth;
+	break;
+      }
+    else
+      {
+	depth++;
+	if (x->sub[1] && x->sub[0])
+	  {
+	    tally_leaves (x->sub[0], depth, nleaf, sumdepth);
+	    x = x->sub[1];
+	  }
+	else if (x->sub[1])
+	  x = x->sub[1];
+	else /* if (x->sub[0]) */
+	  x = x->sub[0];
+	/*
+	else
+	  break;
+	*/
     }
 }
 #endif


-- 
Alexandre Oliva http://www.ic.unicamp.br/~oliva IC-Unicamp, Bra[sz]il
oliva@{lsd.ic.unicamp.br,guarana.{org,com}} aoliva@{acm,computer}.org
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
** I may forward mail about projects to mailing lists; please use them