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
