On Mon, 2013-08-05 at 06:59 -1000, Richard Henderson wrote: > On 08/05/2013 05:18 AM, David Malcolm wrote: > > So I *think* the most efficient traversal is to do this first (with a > > suitable comment): > > > > for (int i = passes_by_id_size ; i > 0; ) > > ::gt_ggc_mx (passes_by_id[--i]); > > > > That ought to visit all of the passes without triggering recursion > > (unless someone does something weird to the pass structure in a plugin). > > Reasonable. > > > I'm nervous about omitting the traversal for other pointers the class > > has (though I *think* the passes by id array captures it all) so for > > completeness I'd prefer to then to also do it for all of: > > > > ::gt_ggc_mx (all_passes); > > ::gt_ggc_mx (all_small_ipa_passes); > > ::gt_ggc_mx (all_lowering_passes); > > ::gt_ggc_mx (all_regular_ipa_passes); > > ::gt_ggc_mx (all_lto_gen_passes); > > ::gt_ggc_mx (all_late_ipa_passes); > > > > #define INSERT_PASSES_AFTER(PASS) > > #define PUSH_INSERT_PASSES_WITHIN(PASS) > > #define POP_INSERT_PASSES() > > #define NEXT_PASS(PASS, NUM) ::gt_ggc_mx (PASS ## _ ## NUM); > > #define TERMINATE_PASS_LIST() > > > > #include "pass-instances.def" > > > > #undef INSERT_PASSES_AFTER > > #undef PUSH_INSERT_PASSES_WITHIN > > #undef POP_INSERT_PASSES > > #undef NEXT_PASS > > #undef TERMINATE_PASS_LIST > > > > Is it standard in handwritten GC code to omit traversals based on this > > higher-level knowledge? Presumably it warrants a source comment? > > (having spent too much time lately debugging PCH issues I'm nervous > > about trying to optimize this). > > It's something that we should think about when doing any kind of GC. > The deep recursion has bitten us before, and lead to the chain_next > and chain_prev annotations for GTY. > > > AIUI we could do similar optimizations in the PCH object-noting hook, > > but can't do similar optimizations in the PCH *op* hook, since every > > field needs to reconstructed when reading the data back from disk. > > Correct.
Sorry about the delay in following up on this. I'm attaching an implementation of patch which incorporates the ideas for optimizing the GC traversal. It turned out that the passes_by_id array only contains *most* of the passes, not all of them: it only contains passes that had register_one_dump_file called on them, thus omitting those that have a "*" at the front of their names (or a NULL name, but I don't think there are any of these). So the pass_manager traversal hooks need to do some extra work after the backwards traversal of the passes_by_id array to ensure that we visit everything. I also tweaked the traversal hooks for opt_pass to emulate "chain_next", since this is where the really deep callchains could otherwise occur. See the patch for details (given the subtleties I opted to put big comments in the relevant routines). (I also fixed the typo "overide" to "override" as noted by Bernhard) Successfully bootstrapped and tested on x86_64-unknown-linux-gnu, on top of the other patches (Note that the gengtype fix I committed just now as r201791 is also needed [1]). OK for trunk? [1] http://gcc.gnu.org/ml/gcc-patches/2013-08/msg00882.html
commit 5deba6060b8d9991b6298af2d1122310e0415043 Author: David Malcolm <dmalc...@redhat.com> Date: Fri Aug 2 15:58:46 2013 -0400 Make opt_pass and gcc::pass_manager be GC-managed This patch makes gcc::pass_manager and opt_pass instances be allocated within the GC-heap, and adds traversal hooks for GC/PCH, so that passes can own refs to other GC-allocated objects. It also adds templates to ggc.h, to create boilerplate for GTY((user)) types that gengtype can't handle. gcc/ Make opt_pass and gcc::pass_manager be GC-managed, so that pass instances can own GC refs. * Makefile.in (GTFILES): Add pass_manager.h and tree-pass.h. * context.c (gcc::context::gt_ggc_mx): Traverse passes_. (gcc::context::gt_pch_nx): Likewise. (gcc::context::gt_pch_nx): Likewise. * ggc.h (gt_ggc_mx <T>): New. (gt_pch_nx_with_op <T>): New. (gt_pch_nx <T>): New. * passes.c (opt_pass::gt_ggc_mx): New. (opt_pass::gt_pch_nx): New. (opt_pass::gt_pch_nx_with_op): New. (pass_manager::gt_ggc_mx): New. (pass_manager::gt_pch_nx): New. (pass_manager::gt_pch_nx_with_op): New. (pass_manager::operator new): Use ggc_internal_cleared_alloc_stat rather than xcalloc. * pass_manager.h (class pass_manager): Add GTY((user)) marking. (pass_manager::gt_ggc_mx): New. (pass_manager::gt_pch_nx): New. (pass_manager::gt_pch_nx_with_op): New. * tree-pass.h (class opt_pass): Add GTY((user)) marking. (opt_pass::operator new): New. (opt_pass::gt_ggc_mx): New. (opt_pass::gt_pch_nx): New. (opt_pass::gt_pch_nx_with_op): New. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b874a6b..9917aec 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -3828,6 +3828,8 @@ GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/asan.c \ $(srcdir)/tsan.c \ $(srcdir)/context.h \ + $(srcdir)/pass_manager.h \ + $(srcdir)/tree-pass.h \ @all_gtfiles@ # Compute the list of GT header files from the corresponding C sources, diff --git a/gcc/context.c b/gcc/context.c index ba6f335..698cc57 100644 --- a/gcc/context.c +++ b/gcc/context.c @@ -42,18 +42,18 @@ gcc::context::context() void gcc::context::gt_ggc_mx () { - /* Currently a no-op. */ + ::gt_ggc_mx (passes_); } void gcc::context::gt_pch_nx () { - /* Currently a no-op. */ + ::gt_pch_nx (passes_); } void gcc::context::gt_pch_nx (gt_pointer_operator op ATTRIBUTE_UNUSED, void *cookie ATTRIBUTE_UNUSED) { - /* Currently a no-op. */ + op (&passes_, cookie); } diff --git a/gcc/ggc.h b/gcc/ggc.h index b31bc80..e2a1aaf 100644 --- a/gcc/ggc.h +++ b/gcc/ggc.h @@ -276,4 +276,50 @@ ggc_alloc_cleared_gimple_statement_d_stat (size_t s MEM_STAT_DECL) ggc_internal_cleared_alloc_stat (s PASS_MEM_STAT); } +/* gengtype will autogenerate traversal functions (in gtype-desc.c) for + all GTY-marked types that it sees are referenced by a GTY marker. + + Unfortunately, it will not generate traveral functions for types that + are only referenced by GTY((user)) types. + + The following templates are a substitute, providing equivalent + traversal functions for such types. They are instantiated for + types whose objects that are traversed during GC/PCH, and are + called *every time* that an instance of type T is traversed during + GC/PCH. + + They require the presence of the following member functions + + void gt_ggc_mx (); + void gt_pch_nx (); + void gt_pch_nx_with_op (gt_pointer_operator op, void *cookie); + + within class T, which are called *once* per object - the first + time the object is visited during the traversal. */ + +template<class T> +inline void gt_ggc_mx (T *p) +{ + if (ggc_test_and_set_mark (p)) + p->gt_ggc_mx (); +} + +template<class T> +void gt_pch_nx_with_op (void *this_obj, void *p, + gt_pointer_operator op, void *cookie) +{ + if (p == this_obj) + { + T *t = static_cast<T *>(p); + t->gt_pch_nx_with_op (op, cookie); + } +} + +template<class T> +inline void gt_pch_nx (T *p) +{ + if (gt_pch_note_object (p, p, gt_pch_nx_with_op<T>)) + p->gt_pch_nx (); +} + #endif diff --git a/gcc/pass_manager.h b/gcc/pass_manager.h index 41d2c76..a442bf1 100644 --- a/gcc/pass_manager.h +++ b/gcc/pass_manager.h @@ -44,13 +44,19 @@ namespace gcc { class context; -class pass_manager +class GTY((user)) pass_manager { public: + /* Ensure that instances are allocated in the GC-managed heap. */ void *operator new (size_t sz); pass_manager(context *ctxt); + /* GTY((user)) methods. */ + void gt_ggc_mx (); + void gt_pch_nx (); + void gt_pch_nx_with_op (gt_pointer_operator op, void *cookie); + void register_pass (struct register_pass_info *pass_info); void register_one_dump_file (struct opt_pass *pass); @@ -134,4 +140,3 @@ private: } // namespace gcc #endif /* ! GCC_PASS_MANAGER_H */ - diff --git a/gcc/passes.c b/gcc/passes.c index e3a7212..3fa4393 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -82,6 +82,58 @@ struct opt_pass *current_pass; static void register_pass_name (struct opt_pass *, const char *); +void* +opt_pass::operator new (size_t sz) +{ + return ggc_internal_cleared_alloc_stat (sz MEM_STAT_INFO); +} + +void opt_pass::gt_ggc_mx () +{ + ::gt_ggc_mx (ctxt_); + ::gt_ggc_mx (sub); + + /* Avoid deep stack usage by iteratively walking the chain of "next" + passes, rather than recursing (analogous to the chain_next/chain_prev + GTY options). */ + + /* "this" has already been marked. + Mark a chain of as-yet-unmarked passes. */ + opt_pass *limit = this->next; + while (ggc_test_and_set_mark (limit)) + limit = limit->next; + + /* "limit" is the first in the chain that wasn't just marked, either + because it is NULL, or because it was already marked. + Hence all of the passes in the half-open interval: + [this->next...limit) + have just been marked: visit them. */ + for (opt_pass *iter = this->next; iter != limit; iter = iter->next) + iter->gt_ggc_mx (); +} + +void opt_pass::gt_pch_nx () +{ + ::gt_pch_nx (ctxt_); + ::gt_pch_nx (sub); + + /* Analogous to opt_pass::gt_ggc_mx. */ + opt_pass *limit = this->next; + while (gt_pch_note_object (limit, limit, ::gt_pch_nx_with_op<opt_pass>)) + limit = limit->next; + + for (opt_pass *iter = this->next; iter != limit; iter = iter->next) + iter->gt_pch_nx (); + +} + +void opt_pass::gt_pch_nx_with_op (gt_pointer_operator op, void *cookie) +{ + op (&(ctxt_), cookie); + op (&(sub), cookie); + op (&(next), cookie); +} + /* Most passes are single-instance (within their context) and thus don't need to implement cloning, but passes that support multiple instances *must* provide their own implementation of the clone method. @@ -116,6 +168,92 @@ opt_pass::opt_pass(const pass_data &data, context *ctxt) { } +void +pass_manager::gt_ggc_mx () +{ + /* We want to efficiently visit all pass objects without incurring deep + call chains that could blow the stack. + + Although there are multiple fields referencing passes within the + pass_manager, *almost* all of the underlying pass instances are + referenced by the passes_by_id array. + + Specifically, passes are in the passes_by_id array if they have + register_one_dump_file called on them, which requires them to have + a name, and for that name to *not* begin with "*". Currently + there are 25 passes with a "*" prefix and thus not in the array. + + Each pass holds references to its sub and next, so visiting a pass + will potentially trigger a recursive traversal through these + neighbours - if these passes haven't been visited yet. + + By walking the passes_by_id array *backwards*, in the common case + this leads to us walking the pass tree from the leaf passes first, + eventually reaching the trunk passes, and hence none of the calls + should recurse, given that at each point in the iteration pass->sub + and pass->next will already have been marked. + + Having walked the array, we then walk the higher-level fields, + again in bottom-up order, which will ensure that we visit all + remaining passes. Most of the passes will have already been + visited, which should minimize further recursion. */ + for (int i = passes_by_id_size ; i > 0; ) + ::gt_ggc_mx (passes_by_id[--i]); + + ::gt_ggc_mx (all_late_ipa_passes); + ::gt_ggc_mx (all_lto_gen_passes); + ::gt_ggc_mx (all_regular_ipa_passes); + ::gt_ggc_mx (all_lowering_passes); + ::gt_ggc_mx (all_small_ipa_passes); + ::gt_ggc_mx (all_passes); +} + +void +pass_manager::gt_pch_nx () +{ + /* Analogous to pass_manager::gt_ggc_mx */ + for (int i = passes_by_id_size ; i > 0; ) + ::gt_pch_nx (passes_by_id[--i]); + + ::gt_pch_nx (all_late_ipa_passes); + ::gt_pch_nx (all_lto_gen_passes); + ::gt_pch_nx (all_regular_ipa_passes); + ::gt_pch_nx (all_lowering_passes); + ::gt_pch_nx (all_small_ipa_passes); + ::gt_pch_nx (all_passes); +} + +void +pass_manager::gt_pch_nx_with_op (gt_pointer_operator op, void *cookie) +{ + /* Unlike the _mx and _nx hooks, we must visit *every* field, since + they must each be reconstructed when reading the data back from + disk. */ + op (&(all_passes), cookie); + op (&(all_small_ipa_passes), cookie); + op (&(all_lowering_passes), cookie); + op (&(all_regular_ipa_passes), cookie); + op (&(all_lto_gen_passes), cookie); + op (&(all_late_ipa_passes), cookie); + + for (int i = 0; i < passes_by_id_size; i++) + op (&(passes_by_id[i]), cookie); + +#define INSERT_PASSES_AFTER(PASS) +#define PUSH_INSERT_PASSES_WITHIN(PASS) +#define POP_INSERT_PASSES() +#define NEXT_PASS(PASS, NUM) op (&(PASS ## _ ## NUM), cookie); +#define TERMINATE_PASS_LIST() + +#include "pass-instances.def" + +#undef INSERT_PASSES_AFTER +#undef PUSH_INSERT_PASSES_WITHIN +#undef POP_INSERT_PASSES +#undef NEXT_PASS +#undef TERMINATE_PASS_LIST + +} void pass_manager::execute_early_local_passes () @@ -1464,7 +1602,7 @@ void * pass_manager::operator new (size_t sz) { /* Ensure that all fields of the pass manager are zero-initialized. */ - return xcalloc (1, sz); + return ggc_internal_cleared_alloc_stat (sz MEM_STAT_INFO); } pass_manager::pass_manager (context *ctxt) diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 787a49b..b2182c5 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -76,11 +76,22 @@ namespace gcc /* An instance of a pass. This is also "pass_data" to minimize the changes in existing code. */ -class opt_pass : public pass_data +class GTY((user)) opt_pass : public pass_data { public: + /* Ensure that instances are allocated in the GC-managed heap. */ + void *operator new (size_t sz); + virtual ~opt_pass () { } + /* GTY((user)) methods, to be called once per traversal. + opt_pass subclasses with additional GC-managed data should override + these, chain up to the base class implementation, then walk their + extra fields. */ + virtual void gt_ggc_mx (); + virtual void gt_pch_nx (); + virtual void gt_pch_nx_with_op (gt_pointer_operator op, void *cookie); + /* Create a copy of this pass. Passes that can have multiple instances must provide their own