re PR c/10675 (Compile time increases quadratically with struct size)

        PR c/10675
        * c-decl.c: Include hashtab.h.
        (detect_field_duplicates): New.
        (finish_struct): Use it.
        * Makefile.in (c-decl.o): Update.
        * c-parse.in (structsp_attr): Nreverse component_decl_list results.
        (component_decl_list, component_decl_list2,
        components, components_notype): Build list in reverse order.
        (enumlist): Clarify docs.  Use TREE_CHAIN not chainon.
        * tree.c (chainon): Special case op2 null as well.
        Reorg for clarity.

From-SVN: r66710

5 files changed, 121 insertions, 59 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index cfdc861..b896526 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2003-05-11  Richard Henderson  <rth@redhat.com>
+
+	PR c/10675
+	* c-decl.c: Include hashtab.h.
+	(detect_field_duplicates): New.
+	(finish_struct): Use it.
+	* Makefile.in (c-decl.o): Update.
+	* c-parse.in (structsp_attr): Nreverse component_decl_list results.
+	(component_decl_list, component_decl_list2,
+	components, components_notype): Build list in reverse order.
+	(enumlist): Clarify docs.  Use TREE_CHAIN not chainon.
+
+	* tree.c (chainon): Special case op2 null as well. 
+	Reorg for clarity.
+
 2003-05-11  Roger Sayle  <roger@eyesopen.com>
 
 	* config/i386/i386.md (logsf2, logdf2, logxf2, logdf2): New patterns
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 3cf851b..38aa848 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1257,10 +1257,10 @@ $(parsedir)/c-parse.y: c-parse.in
 c-incpath.o: c-incpath.c c-incpath.h $(CONFIG_H) $(SYSTEM_H) $(CPPLIB_H) \
 		intl.h prefix.h coretypes.h $(TM_H) cppdefault.h
 
-c-decl.o : c-decl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(RTL_H) \
-    $(C_TREE_H) $(GGC_H) $(TARGET_H) flags.h function.h output.h $(EXPR_H) \
-    debug.h toplev.h intl.h $(TM_P_H) tree-inline.h $(TIMEVAR_H) c-pragma.h \
-    gt-c-decl.h cgraph.h
+c-decl.o : c-decl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
+    $(RTL_H) $(C_TREE_H) $(GGC_H) $(TARGET_H) flags.h function.h output.h \
+    $(EXPR_H) debug.h toplev.h intl.h $(TM_P_H) tree-inline.h $(TIMEVAR_H) \
+    c-pragma.h gt-c-decl.h cgraph.h $(HASHTAB_H)
 c-typeck.o : c-typeck.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
     $(TARGET_H) flags.h intl.h output.h $(EXPR_H) $(RTL_H) toplev.h $(TM_P_H)
 c-lang.o : c-lang.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(C_TREE_H) \
diff --git a/gcc/c-decl.c b/gcc/c-decl.c
index 7ac4739..b27ca06 100644
--- a/gcc/c-decl.c
+++ b/gcc/c-decl.c
@@ -49,6 +49,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "c-common.h"
 #include "c-pragma.h"
 #include "cgraph.h"
+#include "hashtab.h"
 
 /* In grokdeclarator, distinguish syntactic contexts of declarators.  */
 enum decl_context
@@ -4883,6 +4884,63 @@ grokfield (filename, line, declarator, declspecs, width)
   return value;
 }
 
+/* Generate an error for any duplicate field names in FIELDLIST.  Munge
+   the list such that this does not present a problem later.  */
+
+static void
+detect_field_duplicates (tree fieldlist)
+{
+  tree x, y;
+  int timeout = 10;
+
+  /* First, see if there are more than "a few" fields.
+     This is trivially true if there are zero or one fields.  */
+  if (!fieldlist)
+    return;
+  x = TREE_CHAIN (fieldlist);
+  if (!x)
+    return;
+  do {
+    timeout--;
+    x = TREE_CHAIN (x);
+  } while (timeout > 0 && x);
+
+  /* If there were "few" fields, avoid the overhead of allocating
+     a hash table.  Instead just do the nested traversal thing.  */
+  if (timeout > 0)
+    {
+      for (x = TREE_CHAIN (fieldlist); x ; x = TREE_CHAIN (x))
+	if (DECL_NAME (x))
+	  {
+	    for (y = fieldlist; y != x; y = TREE_CHAIN (y))
+	      if (DECL_NAME (y) == DECL_NAME (x))
+		{
+		  error_with_decl (x, "duplicate member `%s'");
+		  DECL_NAME (x) = NULL_TREE;
+		}
+	  }
+    }
+  else
+    {
+      htab_t htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+      void **slot;
+
+      for (x = fieldlist; x ; x = TREE_CHAIN (x))
+	if ((y = DECL_NAME (x)) != 0)
+	  {
+	    slot = htab_find_slot (htab, y, INSERT);
+	    if (*slot)
+	      {
+		error_with_decl (x, "duplicate member `%s'");
+		DECL_NAME (x) = NULL_TREE;
+	      }
+	    *slot = y;
+	  }
+
+      htab_delete (htab);
+    }
+}
+
 /* Fill in the fields of a RECORD_TYPE or UNION_TYPE node, T.
    FIELDLIST is a chain of FIELD_DECL nodes for the fields.
    ATTRIBUTES are attributes to be applied to the structure.  */
@@ -5062,31 +5120,7 @@ finish_struct (t, fieldlist, attributes)
 	saw_named_field = 1;
     }
 
-  /* Delete all duplicate fields from the fieldlist */
-  for (x = fieldlist; x && TREE_CHAIN (x);)
-    /* Anonymous fields aren't duplicates.  */
-    if (DECL_NAME (TREE_CHAIN (x)) == 0)
-      x = TREE_CHAIN (x);
-    else
-      {
-	tree y = fieldlist;
-
-	while (1)
-	  {
-	    if (DECL_NAME (y) == DECL_NAME (TREE_CHAIN (x)))
-	      break;
-	    if (y == x)
-	      break;
-	    y = TREE_CHAIN (y);
-	  }
-	if (DECL_NAME (y) == DECL_NAME (TREE_CHAIN (x)))
-	  {
-	    error_with_decl (TREE_CHAIN (x), "duplicate member `%s'");
-	    TREE_CHAIN (x) = TREE_CHAIN (TREE_CHAIN (x));
-	  }
-	else
-	  x = TREE_CHAIN (x);
-      }
+  detect_field_duplicates (fieldlist);
 
   /* Now we have the nearly final fieldlist.  Record it,
      then lay out the structure or union (including the fields).  */
diff --git a/gcc/c-parse.in b/gcc/c-parse.in
index f9d3656..a9400b3 100644
--- a/gcc/c-parse.in
+++ b/gcc/c-parse.in
@@ -1,4 +1,4 @@
- /* YACC parser for C syntax and for Objective C.  -*-c-*-
+/* YACC parser for C syntax and for Objective C.  -*-c-*-
    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996,
    1997, 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
 
@@ -1759,18 +1759,20 @@ structsp_attr:
 		  /* Start scope of tag before parsing components.  */
 		}
 	  component_decl_list '}' maybe_attribute
-		{ $$ = finish_struct ($<ttype>4, $5, chainon ($1, $7)); }
+		{ $$ = finish_struct ($<ttype>4, nreverse ($5),
+				      chainon ($1, $7)); }
 	| struct_head '{' component_decl_list '}' maybe_attribute
 		{ $$ = finish_struct (start_struct (RECORD_TYPE, NULL_TREE),
-				      $3, chainon ($1, $5));
+				      nreverse ($3), chainon ($1, $5));
 		}
 	| union_head identifier '{'
 		{ $$ = start_struct (UNION_TYPE, $2); }
 	  component_decl_list '}' maybe_attribute
-		{ $$ = finish_struct ($<ttype>4, $5, chainon ($1, $7)); }
+		{ $$ = finish_struct ($<ttype>4, nreverse ($5),
+				      chainon ($1, $7)); }
 	| union_head '{' component_decl_list '}' maybe_attribute
 		{ $$ = finish_struct (start_struct (UNION_TYPE, NULL_TREE),
-				      $3, chainon ($1, $5));
+				      nreverse ($3), chainon ($1, $5));
 		}
 	| enum_head identifier '{'
 		{ $$ = start_enum ($2); }
@@ -1809,18 +1811,30 @@ maybecomma_warn:
 		    pedwarn ("comma at end of enumerator list"); }
 	;
 
+/* We chain the components in reverse order.  They are put in forward
+   order in structsp_attr.
+
+   Note that component_declarator returns single decls, so components
+   and components_notype can use TREE_CHAIN directly, wheras components
+   and components_notype return lists (of comma separated decls), so
+   component_decl_list and component_decl_list2 must use chainon.
+
+   The theory behind all this is that there will be more semicolon
+   separated fields than comma separated fields, and so we'll be
+   minimizing the number of node traversals required by chainon.  */
+
 component_decl_list:
 	  component_decl_list2
 		{ $$ = $1; }
 	| component_decl_list2 component_decl
-		{ $$ = chainon ($1, $2);
+		{ $$ = chainon ($2, $1);
 		  pedwarn ("no semicolon at end of struct or union"); }
 	;
 
 component_decl_list2:	/* empty */
 		{ $$ = NULL_TREE; }
 	| component_decl_list2 component_decl ';'
-		{ $$ = chainon ($1, $2); }
+		{ $$ = chainon ($2, $1); }
 	| component_decl_list2 ';'
 		{ if (pedantic)
 		    pedwarn ("extra semicolon in struct or union specified"); }
@@ -1831,7 +1845,7 @@ ifobjc
 		  tree interface = lookup_interface ($3);
 
 		  if (interface)
-		    $$ = get_class_ivars (interface);
+		    $$ = nreverse (get_class_ivars (interface));
 		  else
 		    {
 		      error ("cannot find interface declaration for `%s'",
@@ -1874,13 +1888,13 @@ component_decl:
 components:
 	  component_declarator
 	| components ',' maybe_resetattrs component_declarator
-		{ $$ = chainon ($1, $4); }
+		{ TREE_CHAIN ($4) = $1; $$ = $4; }
 	;
 
 components_notype:
 	  component_notype_declarator
 	| components_notype ',' maybe_resetattrs component_notype_declarator
-		{ $$ = chainon ($1, $4); }
+		{ TREE_CHAIN ($4) = $1; $$ = $4; }
 	;
 
 component_declarator:
@@ -1910,9 +1924,7 @@ component_notype_declarator:
 	;
 
 /* We chain the enumerators in reverse order.
-   They are put in forward order where enumlist is used.
-   (The order used to be significant, but no longer is so.
-   However, we still maintain the order, just to be clean.)  */
+   They are put in forward order in structsp_attr.  */
 
 enumlist:
 	  enumerator
@@ -1920,7 +1932,7 @@ enumlist:
 		{ if ($1 == error_mark_node)
 		    $$ = $1;
 		  else
-		    $$ = chainon ($3, $1); }
+		    TREE_CHAIN ($3) = $1, $$ = $3; }
 	| error
 		{ $$ = error_mark_node; }
 	;
diff --git a/gcc/tree.c b/gcc/tree.c
index 8cff4ce..64b605a 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -1031,26 +1031,27 @@ tree
 chainon (op1, op2)
      tree op1, op2;
 {
+  tree t1;
 
-  if (op1)
-    {
-      tree t1;
-#ifdef ENABLE_TREE_CHECKING
-      tree t2;
-#endif
+  if (!op1)
+    return op2;
+  if (!op2)
+    return op1;
+
+  for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
+    continue;
+  TREE_CHAIN (t1) = op2;
 
-      for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
-	;
-      TREE_CHAIN (t1) = op2;
 #ifdef ENABLE_TREE_CHECKING
-      for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
-	if (t2 == t1)
-	  abort ();  /* Circularity created.  */
+  {
+    tree t2;
+    for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
+      if (t2 == t1)
+	abort ();  /* Circularity created.  */
+  }
 #endif
-      return op1;
-    }
-  else
-    return op2;
+
+  return op1;
 }
 
 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */