From 66ea6f4ccef91a1d6b86f7feaf524df51a15e36c Mon Sep 17 00:00:00 2001 From: Richard Henderson Date: Sun, 11 May 2003 20:25:38 -0700 Subject: [PATCH] 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 --- gcc/ChangeLog | 15 +++++++++++ gcc/Makefile.in | 8 +++--- gcc/c-decl.c | 84 ++++++++++++++++++++++++++++++++++++++++----------------- gcc/c-parse.in | 40 +++++++++++++++++---------- gcc/tree.c | 33 ++++++++++++----------- 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 + + 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 * 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 ($4, $5, chainon ($1, $7)); } + { $$ = finish_struct ($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 ($4, $5, chainon ($1, $7)); } + { $$ = finish_struct ($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). */ -- 2.7.4