Manual tail recursion for walk_tree()

[Alexandre Oliva <aoliva at redhat dot com>]

Mike Meissner ran into a proprietary piece of code that had a static
array in a function with an initializer list that was more than 200000
elements long.  Since we don't recognize the opportunity for
tail-recursing in WALK_SUBTREE, and we shouldn't rely on that since
GCC may well be compiled with dumber compilers at least for stage 1, I
went ahead and introduced tail recursion by hand.  Bootstrapped on
athlon-pc-linux-gnu.  Ok to install?

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>
	* tree-inline.c (WALK_SUBTREE_TAIL): New macro.
	(walk_tree): Use it for tail calls where appropriate.

2001-10-16  Alexandre Oliva  <aoliva@redhat.com>

Index: gcc/tree-inline.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/tree-inline.c,v
retrieving revision 1.6
diff -u -p -r1.6 tree-inline.c
--- gcc/tree-inline.c 2001/10/16 21:17:59 1.6
+++ gcc/tree-inline.c 2001/10/16 21:18:50
@@ -1088,6 +1088,15 @@ walk_tree (tp, func, data, htab_)
     }							\
   while (0)
 
+#define WALK_SUBTREE_TAIL(NODE)				\
+  do							\
+    {							\
+       tp = & (NODE);					\
+       goto tail_recurse;				\
+    }							\
+  while (0)
+
+ tail_recurse:
   /* Skip empty subtrees.  */
   if (!*tp)
     return NULL_TREE;
@@ -1122,7 +1131,7 @@ walk_tree (tp, func, data, htab_)
       if (statement_code_p (code) || code == TREE_LIST
 	  || (*lang_hooks.tree_inlining.tree_chain_matters_p) (*tp))
 	/* But we still need to check our siblings.  */
-	return walk_tree (&TREE_CHAIN (*tp), func, data, htab);
+	WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
       else
 	return NULL_TREE;
     }
@@ -1170,7 +1179,7 @@ walk_tree (tp, func, data, htab_)
 	    }
 
 	  /* This can be tail-recursion optimized if we write it this way.  */
-	  return walk_tree (&TREE_CHAIN (*tp), func, data, htab);
+	  WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
 	}
 
       /* We didn't find what we were looking for.  */
@@ -1178,10 +1187,7 @@ walk_tree (tp, func, data, htab_)
     }
   else if (TREE_CODE_CLASS (code) == 'd')
     {
-      WALK_SUBTREE (TREE_TYPE (*tp));
-
-      /* We didn't find what we were looking for.  */
-      return NULL_TREE;
+      WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
     }
 
   result = (*lang_hooks.tree_inlining.walk_subtrees) (tp, &walk_subtrees, func,
@@ -1213,30 +1219,35 @@ walk_tree (tp, func, data, htab_)
 
     case POINTER_TYPE:
     case REFERENCE_TYPE:
-      WALK_SUBTREE (TREE_TYPE (*tp));
+      WALK_SUBTREE_TAIL (TREE_TYPE (*tp));
       break;
 
     case TREE_LIST:
       WALK_SUBTREE (TREE_VALUE (*tp));
-      WALK_SUBTREE (TREE_CHAIN (*tp));
+      WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
       break;
 
     case TREE_VEC:
       {
 	int len = TREE_VEC_LENGTH (*tp);
-	while (len--)
+
+	if (len == 0)
+	  break;
+
+	/* Walk all elements but the first.  */
+	while (--len)
 	  WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
+
+	/* Now walk the first one as a tail call.  */
+	WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
       }
-      break;
 
     case COMPLEX_CST:
       WALK_SUBTREE (TREE_REALPART (*tp));
-      WALK_SUBTREE (TREE_IMAGPART (*tp));
-      break;
+      WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
 
     case CONSTRUCTOR:
-      WALK_SUBTREE (CONSTRUCTOR_ELTS (*tp));
-      break;
+      WALK_SUBTREE_TAIL (CONSTRUCTOR_ELTS (*tp));
 
     case METHOD_TYPE:
       WALK_SUBTREE (TYPE_METHOD_BASETYPE (*tp));
@@ -1255,18 +1266,15 @@ walk_tree (tp, func, data, htab_)
 
     case ARRAY_TYPE:
       WALK_SUBTREE (TREE_TYPE (*tp));
-      WALK_SUBTREE (TYPE_DOMAIN (*tp));
-      break;
+      WALK_SUBTREE_TAIL (TYPE_DOMAIN (*tp));
 
     case INTEGER_TYPE:
       WALK_SUBTREE (TYPE_MIN_VALUE (*tp));
-      WALK_SUBTREE (TYPE_MAX_VALUE (*tp));
-      break;
+      WALK_SUBTREE_TAIL (TYPE_MAX_VALUE (*tp));
 
     case OFFSET_TYPE:
       WALK_SUBTREE (TREE_TYPE (*tp));
-      WALK_SUBTREE (TYPE_OFFSET_BASETYPE (*tp));
-      break;
+      WALK_SUBTREE_TAIL (TYPE_OFFSET_BASETYPE (*tp));
 
     default:
       abort ();

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me