RFC: GC allocating everything with a type, part 1

[Steven Bosscher <stevenb at suse dot de>]

Hello,

To fully exploit the possibilities of the zone based garbage collector,
we need to know the type that is stored in each piece of GC allocated
memory.  For each allocated object, we have an "alloc_chunk" with a
"typecode" field.  If we know the type for each hunk, then we can call
the proper marker routine for that hunk without walking from the GC
roots.  As everyone knows by now i guess, we spend lots of time in the
marking phase of our garbage collectors.  If we get type codes for each
chunk, we can start thinking about more sophisticated (and faster) GC
techniques.

(The type codes are defined in "enum gt_types_enum" which is in the
 machine generated file gtype-desc.h in the build dir.)

Right now we don't use the typecode field for anything.  The attached
patch is a first step to change that.  It makes gengtype write out a
#define for each type to gtype-desc.h, eg. for bitmap_head you get the
following define:

#define ggc_alloc_bitmap_head_def() \
  ggc_alloc_typed(gt_ggc_e_15bitmap_head_def, sizeof (struct bitmap_head_def))

(I choose to write all defines to gtype-desc.h because it is included in
ggc.h, so everything that uses GC gets all the defines.  It also means
that there are lots of redundant defines to allocate types defined in .c
files, ie. not visible to all files.  I don't think this is a problem.)

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.

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.

(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.  For the
others it probably means passing around the type codes.)

The next steps from here would be:
 o  Figure out how to deal with the GTY param_is attribute.
 o  Replace all ggc_alloc calls with a use of the proper define,
    so that we know the type code for everything we allocate with
    the GC alloctors.
 o  Hack gengtype some more to write out an array of marker
    functions that can be called by typecode index.
 o  Implement better GC strategies?

This was bootstrapped just to make sure it works.  Before going on to
the next step,  I'd like to hear from people what they think of this
approach.

Gr.
Steven

Index: gengtype.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gengtype.c,v
retrieving revision 1.43
diff -c -3 -p -r1.43 gengtype.c
*** gengtype.c	16 Jan 2004 01:44:06 -0000	1.43
--- gengtype.c	17 Jan 2004 17:08:04 -0000
*************** walk_type (type_p t, struct walk_type_da
*** 1509,1514 ****
--- 1509,1516 ----
        use_param_num = oo->name[9] == '\0' ? 0 : oo->name[9] - '0';
      else if (strcmp (oo->name, "use_params") == 0)
        use_params_p = 1;
+     else if (strcmp (oo->name, "size_not_fixed") == 0)
+       ;
      else if (strcmp (oo->name, "desc") == 0)
        desc = (const char *)oo->info;
      else if (strcmp (oo->name, "dot") == 0)
*************** write_local (type_p structures, type_p p
*** 2306,2316 ****
  /* Write out the 'enum' definition for gt_types_enum.  */
  
  static void
! write_enum_defn  (type_p structures, type_p param_structs)
  {
    type_p s;
  
!   oprintf (header_file, "\n/* Enumeration of types known.  */\n");
    oprintf (header_file, "enum gt_types_enum {\n");
    for (s = structures; s; s = s->next)
      if (s->gc_used == GC_POINTED_TO
--- 2308,2318 ----
  /* Write out the 'enum' definition for gt_types_enum.  */
  
  static void
! write_enum_defn  (type_p structures, type_p param_structs ATTRIBUTE_UNUSED)
  {
    type_p s;
  
!   oprintf (header_file, "\n/* Enumeration of known types.  */\n");
    oprintf (header_file, "enum gt_types_enum {\n");
    for (s = structures; s; s = s->next)
      if (s->gc_used == GC_POINTED_TO
*************** write_enum_defn  (type_p structures, typ
*** 2324,2329 ****
--- 2326,2335 ----
  	output_mangled_typename (header_file, s);
  	oprintf (header_file, ", \n");
        }
+ 
+ #if 0
+   /* ??? These param_struct elements in the enum set contribute no relevant
+ 	 information AFAICT.  Let's just not write them.  */
    for (s = param_structs; s; s = s->next)
      if (s->gc_used == GC_POINTED_TO)
        {
*************** write_enum_defn  (type_p structures, typ
*** 2331,2340 ****
--- 2337,2413 ----
  	output_mangled_typename (header_file, s);
  	oprintf (header_file, ", \n");
        }
+ #endif
+ 
    oprintf (header_file, " gt_types_enum_last\n");
    oprintf (header_file, "};\n");
  }
  
+ /* Write out a macro for typed allocations for each known struct or union.  */
+ 
+ static void
+ write_typed_alloc_defns (type_p structures)
+ {
+   type_p s;
+   pair_p p;
+ 
+   oprintf (header_file,
+ 	   "\n/* Typed allocation for known structs and unions.  */\n");
+   for (s = structures; s; s = s->next)
+     if (s->gc_used == GC_POINTED_TO
+ 	|| (s->gc_used == GC_MAYBE_POINTED_TO && s->u.s.line.file != NULL))
+       {
+ 	options_p o;
+ 	int have_size = 0;
+ 	const char *type_kind;
+ 
+ 	for (o = s->u.s.opt; o; o = o->next)
+ 	  if (strcmp (o->name, "size_not_fixed") == 0)
+ 	    have_size = 1;
+  
+ 	if (s->kind == TYPE_STRUCT)
+ 	  type_kind = "struct ";
+ 	else if (s->kind == TYPE_UNION)
+ 	  type_kind = "union ";
+ 	else
+ 	  type_kind = "";
+ 
+ 	oprintf (header_file, "#define ggc_alloc_%s(%s) \\\n",
+ 		 s->u.s.tag, (have_size ? "SIZE" : ""));
+ 	oprintf (header_file, "  ggc_alloc_typed(gt_ggc_e_");
+ 	output_mangled_typename (header_file, s);
+ 	if (have_size)
+ 	  oprintf (header_file, ", SIZE)\n");
+ 	else
+ 	  oprintf (header_file, ", sizeof (%s%s))\n",
+ 		   type_kind, s->u.s.tag);
+       }
+ 
+   oprintf (header_file,
+            "\n/* Typed allocation for known typedefs.  */\n");
+   for (p = typedefs; p != NULL; p = p->next)
+     {
+       s = p->type;
+       if (strcmp (p->name, s->u.s.tag) == 0)
+ 	continue;
+ 
+       if (s->gc_used == GC_POINTED_TO
+ 	  || (s->gc_used == GC_MAYBE_POINTED_TO && s->u.s.line.file != NULL))
+ 	{
+ 	  if (s->kind != TYPE_STRUCT
+ 	      && s->kind != TYPE_UNION)
+ 	    continue;
+ 
+ 	  oprintf (header_file, "#define ggc_alloc_%s(%s) \\\n",
+ 		   p->name, s->kind == TYPE_STRUCT ? "" : "__SIZE");
+ 	  oprintf (header_file, "  ggc_alloc_typed(gt_ggc_e_");
+ 	  output_mangled_typename (header_file, s);
+ 	  oprintf (header_file, ", sizeof (%s%s))\n",
+ 		   s->kind == TYPE_STRUCT ? "struct " : "", s->u.s.tag);
+ 	}
+     }
+ }
+ 
  /* Might T contain any non-pointer elements?  */
  
  static int
*************** main(int argc ATTRIBUTE_UNUSED, char **a
*** 2945,2950 ****
--- 3018,3024 ----
  
    open_base_files ();
    write_enum_defn (structures, param_structs);
+   write_typed_alloc_defns (structures);
    write_types (structures, param_structs, &ggc_wtd);
    write_types (structures, param_structs, &pch_wtd);
    write_local (structures, param_structs);
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.448
diff -c -3 -p -r1.448 rtl.h
*** rtl.h	12 Jan 2004 18:37:40 -0000	1.448
--- rtl.h	17 Jan 2004 17:08:09 -0000
*************** typedef union rtunion_def rtunion;
*** 137,143 ****
  /* RTL expression ("rtx").  */
  
  struct rtx_def GTY((chain_next ("RTX_NEXT (&%h)"),
! 		    chain_prev ("RTX_PREV (&%h)")))
  {
    /* The kind of expression this is.  */
    ENUM_BITFIELD(rtx_code) code: 16;
--- 137,144 ----
  /* RTL expression ("rtx").  */
  
  struct rtx_def GTY((chain_next ("RTX_NEXT (&%h)"),
! 		    chain_prev ("RTX_PREV (&%h)"),
! 		    size_not_fixed ("")))
  {
    /* The kind of expression this is.  */
    ENUM_BITFIELD(rtx_code) code: 16;
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.458
diff -c -3 -p -r1.458 tree.h
*** tree.h	16 Jan 2004 07:20:29 -0000	1.458
--- tree.h	17 Jan 2004 17:08:17 -0000
*************** enum tree_node_structure_enum {
*** 1770,1776 ****
     for various types of node.  */
  
  union tree_node GTY ((ptr_alias (union lang_tree_node),
! 		      desc ("tree_node_structure (&%h)")))
  {
    struct tree_common GTY ((tag ("TS_COMMON"))) common;
    struct tree_int_cst GTY ((tag ("TS_INT_CST"))) int_cst;
--- 1770,1777 ----
     for various types of node.  */
  
  union tree_node GTY ((ptr_alias (union lang_tree_node),
! 		      desc ("tree_node_structure (&%h)"),
! 		      size_not_fixed ("")))
  {
    struct tree_common GTY ((tag ("TS_COMMON"))) common;
    struct tree_int_cst GTY ((tag ("TS_INT_CST"))) int_cst;