This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Greatly speed up finish_struct
- From: Stan Shebs <shebs at apple dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 31 May 2002 06:24:13 -0700
- Subject: [PATCH] Greatly speed up finish_struct
- Organization: Apple Computer, Inc.
In c-decl.c, pushdecl and finish_struct use a count of incomplete
decls to decide whether to go back and look for other decls that can
be completed once a struct is completed. However, the current
algorithm scans all(!) decls in the current binding level, which is
spectacularly slow if you have so much as a "typedef struct foo bar"
followed by lots of regular struct definitions. In the case of
Mac headers, there are some incompletes, about a thousand structs,
and many thousands of declarations, and finish_struct would actually
appear at the top of the profile.
Over a year ago, Turly posted a patch to use a list of incompletes
instead (http://gcc.gnu.org/ml/gcc-patches/2001-03/msg00916.html),
but it appears not to have been noticed at the time. I've updated
the patch and retested its effect on performance; using SPU (src
repository, utils/spu) with --structs 1000 and a manually-added
incomplete struct typedef, compilation time is cut nearly in half
by this patch. It also seems to speed up bootstrapping on GNU/Linux
very slightly (1/2%), but this is probably within the bounds of
measurement error.
OK for mainline and 3.1 branch? (Technically not a regression,
but a very safe speed win - in use at Apple for a year, plus
bootstrapped on powerpc-apple-darwin and i686-pc-linux-gnu).
Stan
2002-05-31 Stan Shebs <shebs@apple.com>
Turly O'Connor <turly@apple.com>
* c-decl.c (struct binding_level): Change int field n_incomplete
to tree list incomplete_list.
(clear_binding_level): Init field with NULL.
(pushdecl): Add incomplete type to list.
(mark_binding_level): Mark the incomplete list.
(finish_struct): Scan the incomplete list for types instead
of all decls in the current binding level.
Index: c-decl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-decl.c,v
retrieving revision 1.329
diff -p -r1.329 c-decl.c
*** c-decl.c 25 May 2002 22:01:41 -0000 1.329
--- c-decl.c 31 May 2002 12:35:25 -0000
*************** struct binding_level
*** 215,223 ****
/* Nonzero means make a BLOCK if this level has any subblocks. */
char keep_if_subblocks;
! /* Number of decls in `names' that have incomplete
! structure or union types. */
! int n_incomplete;
/* A list of decls giving the (reversed) specified order of parms,
not including any forward-decls in the parmlist.
--- 215,223 ----
/* Nonzero means make a BLOCK if this level has any subblocks. */
char keep_if_subblocks;
! /* List of decls in `names' that have incomplete structure or
! union types. */
! tree incomplete_list;
/* A list of decls giving the (reversed) specified order of parms,
not including any forward-decls in the parmlist.
*************** static struct binding_level *global_bind
*** 244,250 ****
/* Binding level structures are initialized by copying this one. */
static struct binding_level clear_binding_level
! = {NULL, NULL, NULL, NULL, NULL, NULL_BINDING_LEVEL, 0, 0, 0, 0, 0, 0,
NULL};
/* Nonzero means unconditionally make a BLOCK for the next level pushed. */
--- 244,250 ----
/* Binding level structures are initialized by copying this one. */
static struct binding_level clear_binding_level
! = {NULL, NULL, NULL, NULL, NULL, NULL_BINDING_LEVEL, 0, 0, 0, 0, 0, NULL,
NULL};
/* Nonzero means unconditionally make a BLOCK for the next level pushed. */
*************** pushdecl (x)
*** 2392,2398 ****
b->shadowed = tree_cons (name, oldlocal, b->shadowed);
}
! /* Keep count of variables in this level with incomplete type.
If the input is erroneous, we can have error_mark in the type
slot (e.g. "f(void a, ...)") - that doesn't count as an
incomplete type. */
--- 2392,2398 ----
b->shadowed = tree_cons (name, oldlocal, b->shadowed);
}
! /* Keep list of variables in this level with incomplete type.
If the input is erroneous, we can have error_mark in the type
slot (e.g. "f(void a, ...)") - that doesn't count as an
incomplete type. */
*************** pushdecl (x)
*** 2405,2411 ****
element = TREE_TYPE (element);
if (TREE_CODE (element) == RECORD_TYPE
|| TREE_CODE (element) == UNION_TYPE)
! ++b->n_incomplete;
}
}
--- 2405,2411 ----
element = TREE_TYPE (element);
if (TREE_CODE (element) == RECORD_TYPE
|| TREE_CODE (element) == UNION_TYPE)
! b->incomplete_list = tree_cons (NULL_TREE, x, b->incomplete_list);
}
}
*************** mark_binding_level (arg)
*** 2880,2885 ****
--- 2880,2886 ----
ggc_mark_tree (level->blocks);
ggc_mark_tree (level->this_block);
ggc_mark_tree (level->parm_order);
+ ggc_mark_tree (level->incomplete_list);
}
}
*************** finish_struct (t, fieldlist, attributes)
*** 5691,5701 ****
/* If this structure or union completes the type of any previous
variable declaration, lay it out and output its rtl. */
! if (current_binding_level->n_incomplete != 0)
{
! tree decl;
! for (decl = current_binding_level->names; decl; decl = TREE_CHAIN (decl))
! {
if (TYPE_MAIN_VARIANT (TREE_TYPE (decl)) == TYPE_MAIN_VARIANT (t)
&& TREE_CODE (decl) != TYPE_DECL)
{
--- 5692,5705 ----
/* If this structure or union completes the type of any previous
variable declaration, lay it out and output its rtl. */
! if (current_binding_level->incomplete_list != NULL_TREE)
{
! tree prev = NULL_TREE;
!
! for (x = current_binding_level->incomplete_list; x; x = TREE_CHAIN (x))
! {
! tree decl = TREE_VALUE (x);
!
if (TYPE_MAIN_VARIANT (TREE_TYPE (decl)) == TYPE_MAIN_VARIANT (t)
&& TREE_CODE (decl) != TYPE_DECL)
{
*************** finish_struct (t, fieldlist, attributes)
*** 5705,5712 ****
rest_of_decl_compilation (decl, NULL, toplevel, 0);
if (! toplevel)
expand_decl (decl);
! if (--current_binding_level->n_incomplete == 0)
! break;
}
else if (!COMPLETE_TYPE_P (TREE_TYPE (decl))
&& TREE_CODE (TREE_TYPE (decl)) == ARRAY_TYPE)
--- 5709,5719 ----
rest_of_decl_compilation (decl, NULL, toplevel, 0);
if (! toplevel)
expand_decl (decl);
! /* Unlink X from the incomplete list. */
! if (prev)
! TREE_CHAIN (prev) = TREE_CHAIN (x);
! else
! current_binding_level->incomplete_list = TREE_CHAIN (x);
}
else if (!COMPLETE_TYPE_P (TREE_TYPE (decl))
&& TREE_CODE (TREE_TYPE (decl)) == ARRAY_TYPE)
*************** finish_struct (t, fieldlist, attributes)
*** 5725,5732 ****
if (! toplevel)
expand_decl (decl);
}
! if (--current_binding_level->n_incomplete == 0)
! break;
}
}
}
--- 5732,5742 ----
if (! toplevel)
expand_decl (decl);
}
! /* Unlink X from the incomplete list. */
! if (prev)
! TREE_CHAIN (prev) = TREE_CHAIN (x);
! else
! current_binding_level->incomplete_list = TREE_CHAIN (x);
}
}
}