This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR41254 Make free-lang-data not recurse so much
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Diego Novillo <dnovillo at google dot com>
- Date: Thu, 10 Sep 2009 10:51:40 +0200 (CEST)
- Subject: Re: [PATCH] Fix PR41254 Make free-lang-data not recurse so much
- References: <alpine.LNX.2.00.0909081637010.28140@zhemvz.fhfr.qr>
On Tue, 8 Sep 2009, Richard Guenther wrote:
>
> This rewrites free-lang-data to use (partly) a worklist to walk fields
> from types and decls. This avoids deep recursion that crashes
> build of Qt (and tramp3d).
>
> The result is even a bit faster on tramp3d (probably due to the extra
> early outs), and suprisingly collects some more garbage.
>
> Due to the latter effect I want to give it testing on the lto branch
> first, otherwise - bootstrapped and tested on x86_64-unknown-linux-gnu.
We need to properly handle TREE_BINFOs. The following is what I
applied to trunk after testing on the trunk and the branch.
Richard.
2009-09-10 Richard Guenther <rguenther@suse.de>
PR middle-end/41254
* tree.c (struct free_lang_data_d): Add worklist member.
(find_decls_types_r): Push onto the worklist instead of recursing.
Handle TREE_BINFOs properly.
(find_decls_types): New function wrapped around find_decls_types_r
to process the worklist.
(find_decls_types_in_eh_region): Use it.
(find_decls_types_in_node): Likewise.
(find_decls_types_in_var): Likewise.
(free_lang_data_in_cgraph): Likewise. Free the worklist.
* tree.h (RECORD_OR_UNION_TYPE_P): New.
(AGGREGATE_TYPE_P): Adjust.
Index: gcc/tree.c
===================================================================
*** gcc/tree.c.orig 2009-09-09 11:28:58.000000000 +0200
--- gcc/tree.c 2009-09-09 17:10:04.000000000 +0200
*************** free_lang_data_in_decl (tree decl)
*** 4447,4452 ****
--- 4447,4455 ----
struct free_lang_data_d
{
+ /* Worklist to avoid excessive recursion. */
+ VEC(tree,heap) *worklist;
+
/* Set of traversed objects. Used to avoid duplicate visits. */
struct pointer_set_t *pset;
*************** add_tree_to_fld_list (tree t, struct fre
*** 4508,4513 ****
--- 4511,4519 ----
gcc_unreachable ();
}
+ #define PUSH(t) \
+ if (t && !pointer_set_contains (fld->pset, t)) \
+ VEC_safe_push (tree, heap, fld->worklist, (t))
/* Operand callback helper for free_lang_data_in_node. *TP is the
subtree operand being considered. */
*************** find_decls_types_r (tree *tp, int *ws AT
*** 4518,4566 ****
tree t = *tp;
struct free_lang_data_d *fld = (struct free_lang_data_d *) data;
if (DECL_P (t))
{
/* Note that walk_tree does not traverse every possible field in
decls, so we have to do our own traversals here. */
add_tree_to_fld_list (t, fld);
! walk_tree (&DECL_NAME (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_CONTEXT (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_SIZE (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_SIZE_UNIT (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_INITIAL (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_ATTRIBUTES (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_ABSTRACT_ORIGIN (t), find_decls_types_r, fld, fld->pset);
if (TREE_CODE (t) == FUNCTION_DECL)
{
! walk_tree (&DECL_ARGUMENTS (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_RESULT (t), find_decls_types_r, fld, fld->pset);
}
else if (TREE_CODE (t) == TYPE_DECL)
{
! walk_tree (&DECL_ARGUMENT_FLD (t), find_decls_types_r, fld,
! fld->pset);
! walk_tree (&DECL_VINDEX (t), find_decls_types_r, fld, fld->pset);
}
else if (TREE_CODE (t) == FIELD_DECL)
{
! walk_tree (&DECL_FIELD_OFFSET (t), find_decls_types_r, fld,
! fld->pset);
! walk_tree (&DECL_BIT_FIELD_TYPE (t), find_decls_types_r, fld,
! fld->pset);
! walk_tree (&DECL_QUALIFIER (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&DECL_FIELD_BIT_OFFSET (t), find_decls_types_r, fld,
! fld->pset);
! walk_tree (&DECL_FCONTEXT (t), find_decls_types_r, fld, fld->pset);
}
else if (TREE_CODE (t) == VAR_DECL)
{
! walk_tree (&DECL_SECTION_NAME (t), find_decls_types_r, fld,
! fld->pset);
! walk_tree (&DECL_COMDAT_GROUP (t), find_decls_types_r, fld,
! fld->pset);
}
}
else if (TYPE_P (t))
{
--- 4524,4572 ----
tree t = *tp;
struct free_lang_data_d *fld = (struct free_lang_data_d *) data;
+ if (TREE_CODE (t) == TREE_LIST)
+ return NULL_TREE;
+
if (DECL_P (t))
{
/* Note that walk_tree does not traverse every possible field in
decls, so we have to do our own traversals here. */
add_tree_to_fld_list (t, fld);
! PUSH (DECL_NAME (t));
! PUSH (DECL_CONTEXT (t));
! PUSH (DECL_SIZE (t));
! PUSH (DECL_SIZE_UNIT (t));
! PUSH (DECL_INITIAL(t));
! PUSH (DECL_ATTRIBUTES (t));
! PUSH (DECL_ABSTRACT_ORIGIN (t));
if (TREE_CODE (t) == FUNCTION_DECL)
{
! PUSH (DECL_ARGUMENTS (t));
! PUSH (DECL_RESULT (t));
}
else if (TREE_CODE (t) == TYPE_DECL)
{
! PUSH (DECL_ARGUMENT_FLD (t));
! PUSH (DECL_VINDEX (t));
}
else if (TREE_CODE (t) == FIELD_DECL)
{
! PUSH (DECL_FIELD_OFFSET (t));
! PUSH (DECL_BIT_FIELD_TYPE (t));
! PUSH (DECL_QUALIFIER (t));
! PUSH (DECL_FIELD_BIT_OFFSET (t));
! PUSH (DECL_FCONTEXT (t));
}
else if (TREE_CODE (t) == VAR_DECL)
{
! PUSH (DECL_SECTION_NAME (t));
! PUSH (DECL_COMDAT_GROUP (t));
}
+
+ PUSH (TREE_CHAIN (t));
+ *ws = 0;
}
else if (TYPE_P (t))
{
*************** find_decls_types_r (tree *tp, int *ws AT
*** 4568,4603 ****
types, so we have to do our own traversals here. */
add_tree_to_fld_list (t, fld);
! walk_tree (&TYPE_CACHED_VALUES (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_SIZE (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_SIZE_UNIT (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_ATTRIBUTES (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_POINTER_TO (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_REFERENCE_TO (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_NAME (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_MINVAL (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_MAXVAL (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_NEXT_VARIANT (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_MAIN_VARIANT (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_CONTEXT (t), find_decls_types_r, fld, fld->pset);
! walk_tree (&TYPE_CANONICAL (t), find_decls_types_r, fld, fld->pset);
! }
! if (TREE_TYPE (t))
! walk_tree (&TREE_TYPE (t), find_decls_types_r, fld, fld->pset);
! /* Do not recurse into TREE_CHAIN to avoid blowing up the stack. */
! for (tp = &TREE_CHAIN (t); *tp; tp = &TREE_CHAIN (*tp))
! {
! tree saved_chain = TREE_CHAIN (*tp);
! TREE_CHAIN (*tp) = NULL_TREE;
! walk_tree (tp, find_decls_types_r, fld, fld->pset);
! TREE_CHAIN (*tp) = saved_chain;
}
return NULL_TREE;
}
/* Translate all the types in LIST with the corresponding runtime
types. */
--- 4574,4628 ----
types, so we have to do our own traversals here. */
add_tree_to_fld_list (t, fld);
! PUSH (TYPE_CACHED_VALUES (t));
! PUSH (TYPE_SIZE (t));
! PUSH (TYPE_SIZE_UNIT (t));
! PUSH (TYPE_ATTRIBUTES (t));
! PUSH (TYPE_POINTER_TO (t));
! PUSH (TYPE_REFERENCE_TO (t));
! PUSH (TYPE_NAME (t));
! PUSH (TYPE_MINVAL (t));
! PUSH (TYPE_MAXVAL (t));
! PUSH (TYPE_MAIN_VARIANT (t));
! PUSH (TYPE_NEXT_VARIANT (t));
! PUSH (TYPE_CONTEXT (t));
! PUSH (TYPE_CANONICAL (t));
! if (RECORD_OR_UNION_TYPE_P (t)
! && TYPE_BINFO (t))
! {
! unsigned i;
! tree tem;
! for (i = 0; VEC_iterate (tree, BINFO_BASE_BINFOS (TYPE_BINFO (t)),
! i, tem); ++i)
! PUSH (TREE_TYPE (tem));
! }
! PUSH (TREE_CHAIN (t));
! *ws = 0;
}
+ PUSH (TREE_TYPE (t));
+
return NULL_TREE;
}
+ #undef PUSH
+
+ /* Find decls and types in T. */
+
+ static void
+ find_decls_types (tree t, struct free_lang_data_d *fld)
+ {
+ while (1)
+ {
+ if (!pointer_set_contains (fld->pset, t))
+ walk_tree (&t, find_decls_types_r, fld, fld->pset);
+ if (VEC_empty (tree, fld->worklist))
+ break;
+ t = VEC_pop (tree, fld->worklist);
+ }
+ }
/* Translate all the types in LIST with the corresponding runtime
types. */
*************** find_decls_types_in_eh_region (eh_region
*** 4641,4653 ****
{
tree list = r->u.eh_catch.type_list;
r->u.eh_catch.type_list = get_eh_types_for_runtime (list);
! walk_tree (&r->u.eh_catch.type_list, find_decls_types_r, fld, fld->pset);
}
else if (r->type == ERT_ALLOWED_EXCEPTIONS)
{
tree list = r->u.allowed.type_list;
r->u.allowed.type_list = get_eh_types_for_runtime (list);
! walk_tree (&r->u.allowed.type_list, find_decls_types_r, fld, fld->pset);
}
}
--- 4666,4678 ----
{
tree list = r->u.eh_catch.type_list;
r->u.eh_catch.type_list = get_eh_types_for_runtime (list);
! find_decls_types (r->u.eh_catch.type_list, fld);
}
else if (r->type == ERT_ALLOWED_EXCEPTIONS)
{
tree list = r->u.allowed.type_list;
r->u.allowed.type_list = get_eh_types_for_runtime (list);
! find_decls_types (r->u.allowed.type_list, fld);
}
}
*************** find_decls_types_in_node (struct cgraph_
*** 4665,4671 ****
struct function *fn;
tree t;
! walk_tree (&n->decl, find_decls_types_r, fld, fld->pset);
if (!gimple_has_body_p (n->decl))
return;
--- 4690,4696 ----
struct function *fn;
tree t;
! find_decls_types (n->decl, fld);
if (!gimple_has_body_p (n->decl))
return;
*************** find_decls_types_in_node (struct cgraph_
*** 4676,4688 ****
/* Traverse locals. */
for (t = fn->local_decls; t; t = TREE_CHAIN (t))
! {
! tree *tp = &TREE_VALUE (t);
! tree saved_chain = TREE_CHAIN (*tp);
! TREE_CHAIN (*tp) = NULL_TREE;
! walk_tree (tp, find_decls_types_r, fld, fld->pset);
! TREE_CHAIN (*tp) = saved_chain;
! }
/* Traverse EH regions in FN. */
if (fn->eh->region_array)
--- 4701,4707 ----
/* Traverse locals. */
for (t = fn->local_decls; t; t = TREE_CHAIN (t))
! find_decls_types (TREE_VALUE (t), fld);
/* Traverse EH regions in FN. */
if (fn->eh->region_array)
*************** find_decls_types_in_node (struct cgraph_
*** 4707,4713 ****
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree *arg_p = gimple_phi_arg_def_ptr (phi, i);
! walk_tree (arg_p, find_decls_types_r, fld, fld->pset);
}
}
--- 4726,4732 ----
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree *arg_p = gimple_phi_arg_def_ptr (phi, i);
! find_decls_types (*arg_p, fld);
}
}
*************** find_decls_types_in_node (struct cgraph_
*** 4717,4724 ****
for (i = 0; i < gimple_num_ops (stmt); i++)
{
! tree *arg_p = gimple_op_ptr (stmt, i);
! walk_tree (arg_p, find_decls_types_r, fld, fld->pset);
}
}
}
--- 4736,4743 ----
for (i = 0; i < gimple_num_ops (stmt); i++)
{
! tree arg = gimple_op (stmt, i);
! find_decls_types (arg, fld);
}
}
}
*************** find_decls_types_in_node (struct cgraph_
*** 4734,4740 ****
static void
find_decls_types_in_var (struct varpool_node *v, struct free_lang_data_d *fld)
{
! walk_tree (&v->decl, find_decls_types_r, fld, fld->pset);
}
--- 4753,4759 ----
static void
find_decls_types_in_var (struct varpool_node *v, struct free_lang_data_d *fld)
{
! find_decls_types (v->decl, fld);
}
*************** free_lang_data_in_cgraph (void)
*** 4767,4772 ****
--- 4786,4792 ----
/* Initialize sets and arrays to store referenced decls and types. */
fld.pset = pointer_set_create ();
+ fld.worklist = NULL;
fld.decls = VEC_alloc (tree, heap, 100);
fld.types = VEC_alloc (tree, heap, 100);
*************** free_lang_data_in_cgraph (void)
*** 4775,4781 ****
find_decls_types_in_node (n, &fld);
for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); i++)
! walk_tree (&p->decl, find_decls_types_r, &fld, fld.pset);
/* Find decls and types in every varpool symbol. */
for (v = varpool_nodes_queue; v; v = v->next_needed)
--- 4795,4801 ----
find_decls_types_in_node (n, &fld);
for (i = 0; VEC_iterate (alias_pair, alias_pairs, i, p); i++)
! find_decls_types (p->decl, &fld);
/* Find decls and types in every varpool symbol. */
for (v = varpool_nodes_queue; v; v = v->next_needed)
*************** free_lang_data_in_cgraph (void)
*** 4815,4820 ****
--- 4835,4841 ----
free_lang_data_in_type (t);
pointer_set_destroy (fld.pset);
+ VEC_free (tree, heap, fld.worklist);
VEC_free (tree, heap, fld.decls);
VEC_free (tree, heap, fld.types);
}
Index: gcc/tree.h
===================================================================
*** gcc/tree.h.orig 2009-09-09 13:05:59.000000000 +0200
--- gcc/tree.h 2009-09-09 17:12:06.000000000 +0200
*************** extern void omp_clause_range_check_faile
*** 1065,1076 ****
(SCALAR_FLOAT_TYPE_P (TYPE) \
&& DECIMAL_FLOAT_MODE_P (TYPE_MODE (TYPE)))
/* Nonzero if TYPE represents an aggregate (multi-component) type.
Keep these checks in ascending code order. */
#define AGGREGATE_TYPE_P(TYPE) \
! (TREE_CODE (TYPE) == ARRAY_TYPE || TREE_CODE (TYPE) == RECORD_TYPE \
! || TREE_CODE (TYPE) == UNION_TYPE || TREE_CODE (TYPE) == QUAL_UNION_TYPE)
/* Nonzero if TYPE represents a pointer or reference type.
(It should be renamed to INDIRECT_TYPE_P.) Keep these checks in
--- 1065,1081 ----
(SCALAR_FLOAT_TYPE_P (TYPE) \
&& DECIMAL_FLOAT_MODE_P (TYPE_MODE (TYPE)))
+ /* Nonzero if TYPE is a record or union type. */
+ #define RECORD_OR_UNION_TYPE_P(TYPE) \
+ (TREE_CODE (TYPE) == RECORD_TYPE \
+ || TREE_CODE (TYPE) == UNION_TYPE \
+ || TREE_CODE (TYPE) == QUAL_UNION_TYPE)
+
/* Nonzero if TYPE represents an aggregate (multi-component) type.
Keep these checks in ascending code order. */
#define AGGREGATE_TYPE_P(TYPE) \
! (TREE_CODE (TYPE) == ARRAY_TYPE || RECORD_OR_UNION_TYPE_P (TYPE))
/* Nonzero if TYPE represents a pointer or reference type.
(It should be renamed to INDIRECT_TYPE_P.) Keep these checks in