Re: RFC: GC allocating everything with a type, part 1

[Steven Bosscher <stevenb at suse dot de>]

On Monday 19 January 2004 02:10, Geoff Keating wrote:
> Steven Bosscher <stevenb@suse.de> writes:
> > There are at least two types that need to be special-cased (perhaps more,
> > but I haven't found them yet -- but probably not many).  These are the
> > types that do not have a fixed size, such as our core types, the unions
> > rtx_def and tree_node.  The macros for these types accept an extra SIZE
> > argument as follows:
> >
> > #define ggc_alloc_tree_node(SIZE) \
> >   ggc_alloc_typed(gt_ggc_e_9tree_node, SIZE)
> >
> > and
> >
> > #define ggc_alloc_rtx_def(SIZE) \
> >   ggc_alloc_typed(gt_ggc_e_7rtx_def, SIZE)
> >
> > I want these defines to be generated automatically, and the only way I
> > could think of to tell gengtype about these special cases is by adding
> > an extra GTY parameter, "size_not_fixed".  That's a bit ugly, if people
> > have other suggestions then let me know please.
>
> My preferred solution is to have a parameter that gives the size of
> the object; if the parameter is not provided, it defaults to sizeof().
> You couldn't use it in the macros, since you're going to need to read
> the object in the parameter, and you don't have one before you
> allocate it; but the presence of the parameter would indicate that the
> allocation macro can't just use sizeof().  (The actual conte
....?  :-)

I agree that such an extra parameter would be more elegant, but in
practice it wouldn't work.  We have many places where we unleash some
really scarly black magic for some tree codes.  My favorites are on
the tree-ssa branch, like so (NB. phi is a `tree'):

  len = ideal_phi_node_len (len);
  size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
  phi = ggc_alloc (size);

To make this work with the extra parameter you'd have to make some
local functions global, or at least visible from the GC code, and you'd
have to rewrite/extend tree_size() to handle all tree codes and all
special cases like the one above.  I would rather not go there.


> This would also allow you to avoid the need for ggc_get_size.  I was
> originally going to implement this for PCH, but ggc_get_size was
> available, so that was easier.

Hmm I don't see how.  Note that for the zone collector we already don't
really need ggc_get_size(), there is a size field in each alloc chunk
so we don't have to look up page orders (there's no such thing in
ggc-zone.c) or similar.  For ggc-page, I don't know how you think we
could get rid of ggc_get_size, or why you want to.  All I'm trying to
do for now is add type codes to the alloc chunks in the zone collector.
(I hope we can improve ggc-zone enough that it can be the default on
systems with mmap and mprotect, and leave ggc-page for the remaining
targets.)


> > There also is some work to do for types that take the GTY param_is and
> > param[0-9]_is attributes.  Right now we use them for one varray (since
> > Geoff's patch from two days ago) which is easiliy fixed, a number of
> > hashtables, and two splay trees.  On other words, rare cases that we
> > just need to think up something special for.
>
> These cases aren't *that* rare.  There are 18 different parameterised
> types in my build.

I have a few more (tree-ssa branch):

cgraph.c:static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
cgraph.c:static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
cgraph.h:extern GTY((param_is (union tree_node))) htab_t cgraph_inline_hash;
config/rs6000/rs6000.c:static GTY ((param_is (struct toc_hash_struct))) htab_t toc_hash_table;
cp/mangle.c:static GTY ((param_is (union tree_node))) htab_t conv_type_names;
cp/decl.c:static GTY ((param_is (union tree_node))) htab_t typename_htab;
cp/tree.c:static GTY ((param_is (union tree_node))) htab_t list_hash_table;
cselib.c:static GTY((param_is (cselib_val))) htab_t hash_table;
dwarf2out.c:static GTY ((param_is (struct indirect_string_node))) htab_t debug_str_hash;
emit-rtl.c:static GTY ((if_marked ("ggc_marked_p"), param_is (struct rtx_def)))
emit-rtl.c:static GTY ((if_marked ("ggc_marked_p"), param_is (struct mem_attrs)))
emit-rtl.c:static GTY ((if_marked ("ggc_marked_p"), param_is (struct reg_attrs)))
emit-rtl.c:static GTY ((if_marked ("ggc_marked_p"), param_is (struct rtx_def)))
except.c:static GTY ((param_is (union tree_node)))
except.c:  htab_t GTY ((param_is (struct ehl_map_entry))) exception_handler_label_map;
fold-const.c:static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
java/java-tree.h:  htab_t GTY ((param_is (struct treetreehash_entry))) init_test_table;
java/java-tree.h:  htab_t GTY ((param_is (union tree_node))) ict;
tree-alias-common.c:static GTY((param_is (union alias_typevar_def))) varray_type alias_vars = NULL;
tree.c:static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
tree-eh.c:static GTY((param_is (struct throw_stmt_node))) htab_t throw_stmt_table;
tree-mudflap.c:static GTY ((param_is (union tree_node))) htab_t marked_trees = NULL;
tree-ssa-gvn.c:static GTY ((param_is (struct valnum_expr))) htab_t valid_table = NULL;
tree-ssa-gvn.c:static GTY ((param_is (struct valnum_expr))) htab_t optimistic_table = NULL;
varasm.c:static GTY((param_is (struct in_named_entry))) htab_t in_named_htab;
varasm.c:static GTY((param_is (struct constant_descriptor_tree)))

That's 26 of them.  Hmmm.
Also there are five places where we use param?_is, for splay trees.  And
you have just added one more to alias.c with the patch for PR13689 which
I was trying to avoid with my version of the patch ;-)


> > (Fortunately most hash tables are for trees, so we can hide all magic
> > in another #define we can put in by hand in ggc.h or something.
>
> I think your 'most' is wrong.  My quick survey says that 4 of 13 GCed
> hash tables in gcc contain just trees.

You are right, I was misguided here.  Oops :-)


> >  For the
> > others it probably means passing around the type codes.)
>
> The real problem is that these aren't allocated inside GCC, so
> #defines are irrelevant;

Yup.

> you'd have to write special allocator
> routines that can be passed to htab_create_alloc and
> splay_tree_new_with_allocator.

Or pass the type code for GC allocated data structs.  Or perhaps it's
not even necessary, I'm not sure yet.  The whole GC system is pretty
complex.


> I recommend you instead ignore the parameters, and treat all hash
> tables, splay trees, or whatever the same.  If you have the typecodes
> stored with each allocated object, you don't need to know in advance
> that this is a 'hash table of constant_descriptor_tree'; you just need
> to know it's a hash table, and if you need to know the type of a
> particular element, you can just go look.

Right.  All we have to do is follow the pointer to each entry.  But
my concern is that we also have parametrized types that don't contain
pointers to GC allocated memory.  Like this one:

dwarf2asm.c:static GTY((param1_is (char *), param2_is (tree))) splay_tree indirect_pool;
alias.c:  splay_tree GTY((param1_is (int), param2_is (int))) children;

The param arguments are not in GC memory, so there is no type code to
look at.


> However, there's another problem you've not noticed yet.  Consider
> struct emit_status in function.h.  It contains the following field:
>
>   rtx * GTY ((length ("%h.x_reg_rtx_no"))) x_regno_reg_rtx;
>
> What type are you going to give to the object that this field points
> to?  You need to mark it, it contains pointers to rtx; but you don't
> even know how many of them there are without looking at the containing
> structure.  So you'll need to keep a back pointer.

I don't think so.  This field is enclosed in a type, so it doesn't have
its own type code.  The marker for the containing type obviously knows
how to handle the length parameter.  The rtx'en pointed to by this field
each have the type code for an rtx, so we know which marker function to
use here, too.  We don't care about what points to some memory, just
about the type that is stored in that memory.

Gr.
Steven