Message ID | 1375490907.4994.87.camel@surprise |
---|---|
State | New |
Headers | show |
On 08/02/2013 02:48 PM, David Malcolm wrote: > +pass_manager::gt_ggc_mx () > +{ > + ::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); > + > + for (int i = 0; i < passes_by_id_size; i++) > + ::gt_ggc_mx (passes_by_id[i]); > + > +#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 > + > +} You're marking all passes, and also walking through the chain of sub/next within the passes themselves? That seems unnecessary. Either the passes are reachable via sub/next or they aren't. Alternately, don't walk the sub/next fields and instead only walk all of the passes explicitly, here. That avoids some of the recursion in the opt_pass marking, and keeps the call chain flatter. r~
On Sat, 2013-08-03 at 08:39 -1000, Richard Henderson wrote: > On 08/02/2013 02:48 PM, David Malcolm wrote: > > +pass_manager::gt_ggc_mx () > > +{ > > + ::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); > > + > > + for (int i = 0; i < passes_by_id_size; i++) > > + ::gt_ggc_mx (passes_by_id[i]); > > + > > +#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 > > + > > +} > > You're marking all passes, and also walking through the chain of sub/next > within the passes themselves? That seems unnecessary. Either the passes > are reachable via sub/next or they aren't. > > Alternately, don't walk the sub/next fields and instead only walk all of > the passes explicitly, here. That avoids some of the recursion in the > opt_pass marking, and keeps the call chain flatter. Each _mx call is implemented like this: if (ggc_test_and_set_mark (p)) p->gt_ggc_mx (); i.e. each pass only recurses the first time it is seen. So if the goal is to avoid a deep traversal of the call chain, then walking the passes_by_id array *backwards* ought to walk 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 been marked. 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). 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). 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. Thanks Dave
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. r~
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. Note to self: the chain_next and chain_prev options are documented at: http://gcc.gnu.org/onlinedocs/gccint/GTY-Options.html BTW, this issue seems very reminiscent to me of an implementation detail within the CPython interpreter called the "trashcan". CPython uses reference-counting, and if you have a deep chain of references e.g.: # make a very deep chain of list-of-lists: foo = [] for i in range(depth): foo = [foo] # at this point we have # foo = [[[[[[[[[[[[[[[[[[[[[[[[[[[[ \ # ]]]]]]]]]]]]]]]]]]]]]]]]]]]] for some depth # try to overflow the stack during deallocation: del foo ...you would have a deeply nested chain of decrefs, each triggering deleting of the object, and hence a potential stack overflow. The way CPython avoids such deep reference chains from killing the process with a stack overflow is a pair of macros used in the deallocator for container types, which track the depth of the traversal, and when it reaches a certain threshold, start appending objects to a singly-linked list of deferred deallocations (using a spare pointer in the objects that's safe to use during finalization). Hence the recursion becomes an iteration when a certain stack depth is reached, and diabolical reference graphs can't blow the stack (modulo bugs in 3rd-party container code, of course). The equivalent for GC would be for mx routines to change from: if (ggc_test_and_set_mark (p)) gt_ggc_mx (p); to: if (ggc_test_and_set_mark (p)) add_to_worklist (p, marking_cb); I suspect that this technique can't be used in GGC since it would require (a) having a spare pointer per-object and (b) tracking the type of the marking callback, which would be a jump through a function ptr where there wasn't one before, and thus unacceptable in the general case. > > 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. I'll update the patch with the optimizations you suggest (and the reverse-order marking I mentioned above). Thanks Dave
From 2e3002e597eb7cfdbfb274ede7c02c0510e35e70 Mon Sep 17 00:00:00 2001 From: David Malcolm <dmalcolm@redhat.com> Date: Fri, 2 Aug 2013 15:58:46 -0400 Subject: [PATCH 12/15] 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. --- gcc/Makefile.in | 2 + gcc/context.c | 6 +-- gcc/ggc.h | 46 +++++++++++++++++++++ gcc/pass_manager.h | 9 ++++- gcc/passes.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++- gcc/tree-pass.h | 13 +++++- 6 files changed, 184 insertions(+), 8 deletions(-) diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 61a4d7c..df24bdc 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -3820,6 +3820,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 00f0b1c..c861893 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); @@ -125,4 +131,3 @@ private: } // namespace gcc #endif /* ! GCC_PASS_MANAGER_H */ - diff --git a/gcc/passes.c b/gcc/passes.c index aa273fb..db6fc3b 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -82,6 +82,33 @@ 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); + ::gt_ggc_mx (next); +} + +void opt_pass::gt_pch_nx () +{ + ::gt_pch_nx (ctxt_); + ::gt_pch_nx (sub); + ::gt_pch_nx (next); +} + +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 +143,92 @@ opt_pass::opt_pass(const pass_data &data, context *ctxt) { } +void +pass_manager::gt_ggc_mx () +{ + ::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); + + for (int i = 0; i < passes_by_id_size; i++) + ::gt_ggc_mx (passes_by_id[i]); + +#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 + +} + +void +pass_manager::gt_pch_nx () +{ + ::gt_pch_nx (all_passes); + ::gt_pch_nx (all_small_ipa_passes); + ::gt_pch_nx (all_lowering_passes); + ::gt_pch_nx (all_regular_ipa_passes); + ::gt_pch_nx (all_lto_gen_passes); + ::gt_pch_nx (all_late_ipa_passes); + + for (int i = 0; i < passes_by_id_size; i++) + ::gt_pch_nx (passes_by_id[i]); + +#define INSERT_PASSES_AFTER(PASS) +#define PUSH_INSERT_PASSES_WITHIN(PASS) +#define POP_INSERT_PASSES() +#define NEXT_PASS(PASS, NUM) ::gt_pch_nx (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 + +} + +void +pass_manager::gt_pch_nx_with_op (gt_pointer_operator op, void *cookie) +{ + 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 () @@ -129,7 +242,6 @@ pass_manager::execute_pass_mode_switching () return pass_mode_switching_1->execute (); } - /* Call from anywhere to find out what pass this is. Useful for printing out debugging information deep inside an service routine. */ @@ -1464,7 +1576,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 41d5d92..063b166 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 overide + 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 -- 1.7.11.7