This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[WIP] Copying garbage collection
- From: Daniel Jacobowitz <drow at false dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 13 Mar 2005 00:21:43 -0500
- Subject: [WIP] Copying garbage collection
This patch implements a minimal copying collector for ggc-zone. It's based
on my revamped zone collector, which I haven't committed yet, but it has
been approved - I'll take care of that tomorrow. The patch isn't finished;
it's just to play around with.
It's just a proof of concept. It only calls the copying collector once
during the course of compilation, at the beginning of cgraph_optimize; it
bypasses the usual GC heuristics and forces a copying collection at that
point. Bootstrap time appears to be mostly unchanged, but I didn't measure
with particularly good granularity. cc1-i-files (which includes some ii
files) shows a consistent 3% improvement. I like 3%! When Dan Berlin
originally implemented a copying collector he reported about 10%; his was
called more frequently, and had dirt-simple heap management, while this uses
ggc-zone's more flexible heap management. That probably accounts for the
difference. Who knows - we might be able to pick up most of that by finding
a few more good spots to collect.
Known issues:
- It won't build without --with-gc=zone. Trivial.
- A copying collection requires a lot of RAM: current heap size +
a second copy of all live data. There are various ways to cut
down this overhead but presumably most of them will slow us down.
- We can't use the copying collector just anywhere. For instance,
the very first ggc_collect encountered in a C compilation is
in the C parser. "parser" is a local variable in that function
which points to the GC allocated "the_parser"; when we move it,
the compiler crashes.
I didn't investigate the effects of calling it anywhere else.
- I haven't profiled it. There may be some obvious performance
gotchas.
- I am not 100% sure on the validity of some of the casts in the
new gengtype machinery. I hate C aliasing. I only know for sure
that I got all the ones GCC warns about.
- I have a bit of cut-and-paste to clean up in ggc-zone.
- I completely bugger the detailed memory stats when I run a copying
collection.
It bootstraps on i686-linux (currently finishing libjava). I'll have
testsuite results tomorrow.
Currently, just like with the zone collector it's based on, we have to mark
all objects in memory to do this. That doesn't scale. I have an algorithm
based on the copy collector to segregate functions into separate zones, but
(A) I haven't tried it yet to see if pointers are adequately
compartmentalized for it to work; (B) we have no way to do future
allocations into the right zone. But if folks are interested in working on
(B), I can try to implement it and check (A). If we could do that, we could
collect between optimization passes on a single function, or after
processing each function. I suspect that would get us another couple of
percent.
And, as usual, we need to diet our IL...
Any comments?
--
Daniel Jacobowitz
CodeSourcery, LLC
Index: gcc-copying/gcc/cgraphunit.c
===================================================================
--- gcc-copying.orig/gcc/cgraphunit.c 2005-03-12 19:27:53.000000000 -0500
+++ gcc-copying/gcc/cgraphunit.c 2005-03-12 19:40:24.000000000 -0500
@@ -1758,6 +1758,8 @@ cgraph_optimize (void)
if (!flag_unit_at_a_time)
return;
+ggc_copy_collect ();
+
process_pending_assemble_externals ();
timevar_push (TV_CGRAPHOPT);
Index: gcc-copying/gcc/rtl.h
===================================================================
--- gcc-copying.orig/gcc/rtl.h 2005-03-04 06:10:30.000000000 -0500
+++ gcc-copying/gcc/rtl.h 2005-03-12 15:03:25.000000000 -0500
@@ -178,7 +178,9 @@ typedef union rtunion_def rtunion;
/* RTL expression ("rtx"). */
struct rtx_def GTY((chain_next ("RTX_NEXT (&%h)"),
- chain_prev ("RTX_PREV (&%h)")))
+ chain_prev ("RTX_PREV (&%h)"),
+ chain_next_ptr ("RTX_NEXT_PTR (&%h)"),
+ chain_prev_ptr ("RTX_PREV_PTR (&%h)")))
{
/* The kind of expression this is. */
ENUM_BITFIELD(rtx_code) code: 16;
@@ -277,6 +279,20 @@ struct rtx_def GTY((chain_next ("RTX_NEX
&& NEXT_INSN (PREV_INSN (X)) == X \
? PREV_INSN (X) : NULL)
+/* Parallel macros for the copying collector, returning NULL or an
+ rtx *. */
+
+#define RTX_NEXT_PTR(X) (rtx_next[GET_CODE (X)] == 0 ? NULL \
+ : (rtx *)(((char *)X) + rtx_next[GET_CODE (X)]))
+
+#define RTX_PREV_PTR(X) ((INSN_P (X) \
+ || NOTE_P (X) \
+ || BARRIER_P (X) \
+ || LABEL_P (X)) \
+ && PREV_INSN (X) != NULL \
+ && NEXT_INSN (PREV_INSN (X)) == X \
+ ? &PREV_INSN (X) : NULL)
+
/* Define macros to access the `code' field of the rtx. */
#define GET_CODE(RTX) ((enum rtx_code) (RTX)->code)
Index: gcc-copying/gcc/stringpool.c
===================================================================
--- gcc-copying.orig/gcc/stringpool.c 2005-03-12 00:42:17.000000000 -0500
+++ gcc-copying/gcc/stringpool.c 2005-03-12 20:00:04.000000000 -0500
@@ -173,6 +173,29 @@ ggc_mark_stringpool (void)
ht_forall (ident_hash, mark_ident, NULL);
}
+/* Mark an identifier for GC copying. We do not actually copy
+ identifiers, because there's no benefit - none are ever collected. */
+
+static int
+mark_copy_ident (struct cpp_reader *pfile ATTRIBUTE_UNUSED, hashnode h,
+ const void *v ATTRIBUTE_UNUSED)
+{
+ tree ident = HT_IDENT_TO_GCC_IDENT (h);
+ gt_ggc_c_9tree_node (&ident);
+ gcc_assert (HT_IDENT_TO_GCC_IDENT (h) == ident);
+ return 1;
+}
+
+/* Mark the trees hanging off the identifier node for GGC. These are
+ handled specially (not using gengtype) because of the special
+ treatment for strings. */
+
+void
+ggc_copy_mark_stringpool (void)
+{
+ ht_forall (ident_hash, mark_copy_ident, NULL);
+}
+
/* Strings are _not_ GCed, but this routine exists so that a separate
roots table isn't needed for the few global variables that refer
to strings. */
@@ -200,6 +223,13 @@ gt_pch_n_S (const void *x)
gt_pch_note_object ((void *)x, (void *)x, >_pch_p_S,
gt_types_enum_last);
}
+
+/* Copying marker function for strings. */
+
+void
+gt_ggc_c_S (void *x ATTRIBUTE_UNUSED)
+{
+}
/* Handle saving and restoring the string pool for PCH. */
Index: gcc-copying/gcc/cp/cp-tree.h
===================================================================
--- gcc-copying.orig/gcc/cp/cp-tree.h 2005-03-01 04:57:38.000000000 -0500
+++ gcc-copying/gcc/cp/cp-tree.h 2005-03-12 15:47:49.000000000 -0500
@@ -435,7 +435,7 @@ enum cp_tree_node_structure_enum {
/* The resulting tree type. */
union lang_tree_node GTY((desc ("cp_tree_node_structure (&%h)"),
- chain_next ("(union lang_tree_node *)TREE_CHAIN (&%h.generic)")))
+ chain_next ("*(union lang_tree_node **)&TREE_CHAIN (&%h.generic)")))
{
union tree_node GTY ((tag ("TS_CP_GENERIC"),
desc ("tree_node_structure (&%h)"))) generic;
Index: gcc-copying/gcc/gengtype.c
===================================================================
--- gcc-copying.orig/gcc/gengtype.c 2005-03-12 00:42:17.000000000 -0500
+++ gcc-copying/gcc/gengtype.c 2005-03-12 21:08:35.000000000 -0500
@@ -1353,6 +1353,7 @@ struct write_types_data
const char *subfield_marker_routine;
const char *marker_routine;
const char *reorder_note_routine;
+ const int pass_addresses;
const char *comment;
};
@@ -1545,6 +1546,10 @@ walk_type (type_p t, struct walk_type_da
;
else if (strcmp (oo->name, "chain_prev") == 0)
;
+ else if (strcmp (oo->name, "chain_next_ptr") == 0)
+ ;
+ else if (strcmp (oo->name, "chain_prev_ptr") == 0)
+ ;
else if (strcmp (oo->name, "reorder") == 0)
;
else
@@ -1916,8 +1921,9 @@ write_types_process_field (type_p f, con
switch (f->kind)
{
case TYPE_POINTER:
- oprintf (d->of, "%*s%s (%s%s", d->indent, "",
- wtd->subfield_marker_routine, cast, d->val);
+ oprintf (d->of, "%*s%s (%s%s%s", d->indent, "",
+ wtd->subfield_marker_routine, cast,
+ wtd->pass_addresses ? "&" : "", d->val);
if (wtd->param_prefix)
{
oprintf (d->of, ", %s", d->prev_val[3]);
@@ -1959,9 +1965,24 @@ write_types_process_field (type_p f, con
case TYPE_UNION:
case TYPE_LANG_STRUCT:
case TYPE_PARAM_STRUCT:
- oprintf (d->of, "%*sgt_%s_", d->indent, "", wtd->prefix);
- output_mangled_typename (d->of, f);
- oprintf (d->of, " (%s%s);\n", cast, d->val);
+ if (wtd->pass_addresses && d->needs_cast_p
+ && f->kind != TYPE_PARAM_STRUCT)
+ {
+ /* Manually expand the NULL test, to get the cast
+ in the right place. */
+ oprintf (d->of, "%*sif (%s%s != NULL)\n", d->indent, "",
+ cast, d->val);
+ oprintf (d->of, "%*s gt_%sx_", d->indent, "", wtd->prefix);
+ oprintf (d->of, f->u.s.tag);
+ oprintf (d->of, " (&%s);\n", d->val);
+ }
+ else
+ {
+ oprintf (d->of, "%*sgt_%s_", d->indent, "", wtd->prefix);
+ output_mangled_typename (d->of, f);
+ oprintf (d->of, " (%s%s%s);\n", cast,
+ wtd->pass_addresses ? "&" : "", d->val);
+ }
if (d->reorder_fn && wtd->reorder_note_routine)
oprintf (d->of, "%*s%s (%s%s, %s%s, %s);\n", d->indent, "",
wtd->reorder_note_routine, cast, d->val, cast, d->val,
@@ -1992,8 +2013,22 @@ write_func_for_structure (type_p orig_s,
int i;
const char *chain_next = NULL;
const char *chain_prev = NULL;
+ const char *chain_next_ptr = NULL;
+ const char *chain_prev_ptr = NULL;
options_p opt;
struct walk_type_data d;
+ const char *extra_ptr, *extra_addr;
+
+ if (wtd->pass_addresses)
+ {
+ extra_ptr = "*";
+ extra_addr = "&";
+ }
+ else
+ {
+ extra_ptr = "";
+ extra_addr = "";
+ }
/* This is a hack, and not the good kind either. */
for (i = NUM_PARAM - 1; i >= 0; i--)
@@ -2009,10 +2044,20 @@ write_func_for_structure (type_p orig_s,
chain_next = opt->info;
else if (strcmp (opt->name, "chain_prev") == 0)
chain_prev = opt->info;
+ else if (strcmp (opt->name, "chain_next_ptr") == 0)
+ chain_next_ptr = opt->info;
+ else if (strcmp (opt->name, "chain_prev_ptr") == 0)
+ chain_prev_ptr = opt->info;
if (chain_prev != NULL && chain_next == NULL)
error_at_line (&s->u.s.line, "chain_prev without chain_next");
+ if (chain_prev_ptr != NULL && chain_prev == NULL)
+ error_at_line (&s->u.s.line, "chain_prev_ptr without chain_prev");
+
+ if (chain_next_ptr != NULL && chain_next == NULL)
+ error_at_line (&s->u.s.line, "chain_next_ptr without chain_next");
+
d.process_field = write_types_process_field;
d.cookie = wtd;
d.orig_s = orig_s;
@@ -2024,6 +2069,8 @@ write_func_for_structure (type_p orig_s,
d.prev_val[1] = "not valid postage"; /* Guarantee an error. */
d.prev_val[3] = "x";
d.val = "(*x)";
+ if (wtd->pass_addresses)
+ d.fn_wants_lvalue = true;
oprintf (d.of, "\n");
oprintf (d.of, "void\n");
@@ -2036,17 +2083,31 @@ write_func_for_structure (type_p orig_s,
}
oprintf (d.of, " (void *x_p)\n");
oprintf (d.of, "{\n");
- oprintf (d.of, " %s %s * %sx = (%s %s *)x_p;\n",
- s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag,
- chain_next == NULL ? "const " : "",
- s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
- if (chain_next != NULL)
- oprintf (d.of, " %s %s * xlimit = x;\n",
- s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ if (wtd->pass_addresses)
+ {
+ oprintf (d.of, " %s %s * x ATTRIBUTE_UNUSED;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ if (chain_next != NULL)
+ oprintf (d.of, " %s %s ** xlimit = x_p, * x_final;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ }
+ else
+ {
+ oprintf (d.of, " %s %s * %sx = (%s %s *)x_p;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag,
+ chain_next == NULL ? "const " : "",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ if (chain_next != NULL)
+ oprintf (d.of, " %s %s * xlimit = x_p;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ }
+
if (chain_next == NULL)
{
oprintf (d.of, " if (%s (x", wtd->marker_routine);
- if (wtd->param_prefix)
+ if (wtd->pass_addresses)
+ oprintf (d.of, "_p");
+ else if (wtd->param_prefix)
{
oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
output_mangled_typename (d.of, orig_s);
@@ -2070,7 +2131,9 @@ write_func_for_structure (type_p orig_s,
}
else
{
- oprintf (d.of, " while (%s (xlimit", wtd->marker_routine);
+ oprintf (d.of, " while (%s%s (xlimit",
+ wtd->pass_addresses && chain_next_ptr ? "xlimit && " : "",
+ wtd->marker_routine);
if (wtd->param_prefix)
{
oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
@@ -2092,23 +2155,51 @@ write_func_for_structure (type_p orig_s,
oprintf (d.of, ", gt_types_enum_last");
}
oprintf (d.of, "))\n");
- oprintf (d.of, " xlimit = (");
- d.prev_val[2] = "*xlimit";
- output_escaped_param (&d, chain_next, "chain_next");
+ oprintf (d.of, " xlimit = ");
+ if (wtd->pass_addresses && chain_next_ptr == NULL)
+ oprintf (d.of, "&");
+ oprintf (d.of, "(");
+ d.prev_val[2] = wtd->pass_addresses ? "**xlimit" : "*xlimit";
+ if (wtd->pass_addresses && chain_next_ptr)
+ output_escaped_param (&d, chain_next_ptr, "chain_next_ptr");
+ else
+ output_escaped_param (&d, chain_next, "chain_next");
oprintf (d.of, ");\n");
+
+ if (wtd->pass_addresses)
+ {
+ oprintf (d.of, " x = *(%s %s **)x_p;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ if (chain_next_ptr)
+ oprintf (d.of, " x_final = xlimit ? *xlimit : NULL;\n");
+ else
+ oprintf (d.of, " x_final = *xlimit;\n");
+ }
+
if (chain_prev != NULL)
{
- oprintf (d.of, " if (x != xlimit)\n");
+ oprintf (d.of, " if (x != %s)\n",
+ wtd->pass_addresses ? "x_final" : "xlimit");
oprintf (d.of, " for (;;)\n");
oprintf (d.of, " {\n");
- oprintf (d.of, " %s %s * const xprev = (",
- s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ oprintf (d.of, " %s %s *%s const xprev = ",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag,
+ wtd->pass_addresses ? "*" : "");
+ if (wtd->pass_addresses && chain_prev_ptr == NULL)
+ oprintf (d.of, "&");
+ oprintf (d.of, "(");
d.prev_val[2] = "*x";
- output_escaped_param (&d, chain_prev, "chain_prev");
+ if (wtd->pass_addresses && chain_prev_ptr)
+ output_escaped_param (&d, chain_prev_ptr, "chain_prev_ptr");
+ else
+ output_escaped_param (&d, chain_prev, "chain_prev");
oprintf (d.of, ");\n");
- oprintf (d.of, " if (xprev == NULL) break;\n");
- oprintf (d.of, " x = xprev;\n");
+ if (wtd->pass_addresses)
+ oprintf (d.of, " if (%sxprev == NULL) break;\n",
+ chain_prev_ptr ? "" : "*");
+ else
+ oprintf (d.of, " if (xprev == NULL) break;\n");
oprintf (d.of, " (void) %s (xprev",
wtd->marker_routine);
if (wtd->param_prefix)
@@ -2132,12 +2223,23 @@ write_func_for_structure (type_p orig_s,
oprintf (d.of, ", gt_types_enum_last");
}
oprintf (d.of, ");\n");
+
+ if (wtd->pass_addresses)
+ oprintf (d.of, " x = *xprev;\n");
+ else
+ oprintf (d.of, " x = xprev;\n");
+
oprintf (d.of, " }\n");
}
- oprintf (d.of, " while (x != xlimit)\n");
+ oprintf (d.of, " while (x != %s)\n",
+ wtd->pass_addresses ? "x_final" : "xlimit");
}
oprintf (d.of, " {\n");
+ if (chain_next == NULL && wtd->pass_addresses)
+ oprintf (d.of, " x = *(%s %s **)x_p;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+
d.prev_val[2] = "*x";
d.indent = 6;
walk_type (s, &d);
@@ -2176,8 +2278,8 @@ write_types (type_p structures, type_p p
output_mangled_typename (header_file, s);
oprintf (header_file, "(X) do { \\\n");
oprintf (header_file,
- " if (X != NULL) gt_%sx_%s (X);\\\n", wtd->prefix,
- s->u.s.tag);
+ " if (X != NULL) gt_%sx_%s (X);\\\n",
+ wtd->prefix, s->u.s.tag);
oprintf (header_file,
" } while (0)\n");
@@ -2252,17 +2354,23 @@ write_types (type_p structures, type_p p
static const struct write_types_data ggc_wtd =
{
- "ggc_m", NULL, "ggc_mark", "ggc_test_and_set_mark", NULL,
+ "ggc_m", NULL, "ggc_mark", "ggc_test_and_set_mark", NULL, 0,
"GC marker procedures. "
};
static const struct write_types_data pch_wtd =
{
"pch_n", "pch_p", "gt_pch_note_object", "gt_pch_note_object",
- "gt_pch_note_reorder",
+ "gt_pch_note_reorder", 0,
"PCH type-walking procedures. "
};
+static const struct write_types_data copy_wtd =
+{
+ "ggc_c", NULL, "ggc_copy_mark", "ggc_copy_test_and_set_mark", NULL, 1,
+ "Copying GC marker procedures. "
+};
+
/* Write out the local pointer-walking routines. */
/* process_field routine for local pointer-walking. */
@@ -2673,7 +2781,8 @@ write_root (outf_p f, pair_p v, type_p t
if (! has_length && UNION_OR_STRUCT_P (tp))
{
oprintf (f, " >_ggc_mx_%s,\n", tp->u.s.tag);
- oprintf (f, " >_pch_nx_%s", tp->u.s.tag);
+ oprintf (f, " >_pch_nx_%s,\n", tp->u.s.tag);
+ oprintf (f, " >_ggc_cx_%s", tp->u.s.tag);
}
else if (! has_length && tp->kind == TYPE_PARAM_STRUCT)
{
@@ -2681,12 +2790,15 @@ write_root (outf_p f, pair_p v, type_p t
output_mangled_typename (f, tp);
oprintf (f, ",\n >_pch_n_");
output_mangled_typename (f, tp);
+ oprintf (f, ",\n >_ggc_c_");
+ output_mangled_typename (f, tp);
}
else if (has_length
&& (tp->kind == TYPE_POINTER || UNION_OR_STRUCT_P (tp)))
{
oprintf (f, " >_ggc_ma_%s,\n", name);
- oprintf (f, " >_pch_na_%s", name);
+ oprintf (f, " >_pch_na_%s,\n", name);
+ oprintf (f, " >_ggc_ca_%s", name);
}
else
{
@@ -2707,7 +2819,8 @@ write_root (outf_p f, pair_p v, type_p t
oprintf (f, " 1, \n");
oprintf (f, " sizeof (%s),\n", v->name);
oprintf (f, " >_ggc_m_S,\n");
- oprintf (f, " (gt_pointer_walker) >_pch_n_S\n");
+ oprintf (f, " (gt_pointer_walker) >_pch_n_S,\n");
+ oprintf (f, " >_ggc_c_S\n");
oprintf (f, " },\n");
}
break;
@@ -2738,6 +2851,8 @@ write_array (outf_p f, pair_p v, const s
d.opt = v->opt;
d.bitmap = get_base_file_bitmap (v->line.file);
d.param = NULL;
+ if (wtd->pass_addresses)
+ d.fn_wants_lvalue = true;
d.prev_val[3] = prevval3 = xasprintf ("&%s", v->name);
@@ -2829,6 +2944,7 @@ write_roots (pair_p variables)
{
write_array (f, v, &ggc_wtd);
write_array (f, v, &pch_wtd);
+ write_array (f, v, ©_wtd);
}
}
@@ -2896,7 +3012,7 @@ write_roots (pair_p variables)
oprintf (f, "[] = {\n");
}
- oprintf (f, " { &%s, 1, sizeof (%s), NULL, NULL },\n",
+ oprintf (f, " { &%s, 1, sizeof (%s), NULL, NULL, NULL },\n",
v->name, v->name);
}
@@ -3012,7 +3128,7 @@ write_roots (pair_p variables)
oprintf (f, "[] = {\n");
}
- oprintf (f, " { &%s, 1, sizeof (%s), NULL, NULL },\n",
+ oprintf (f, " { &%s, 1, sizeof (%s), NULL, NULL, NULL },\n",
v->name, v->name);
}
@@ -3081,6 +3197,7 @@ main(int ARG_UNUSED (argc), char ** ARG_
write_enum_defn (structures, param_structs);
write_types (structures, param_structs, &ggc_wtd);
write_types (structures, param_structs, &pch_wtd);
+ write_types (structures, param_structs, ©_wtd);
write_local (structures, param_structs);
write_roots (variables);
write_rtx_next ();
Index: gcc-copying/gcc/ada/ada-tree.h
===================================================================
--- gcc-copying.orig/gcc/ada/ada-tree.h 2005-02-10 08:50:48.000000000 -0500
+++ gcc-copying/gcc/ada/ada-tree.h 2005-03-12 20:25:20.000000000 -0500
@@ -36,7 +36,7 @@ enum gnat_tree_code {
/* Ada uses the lang_decl and lang_type fields to hold a tree. */
union lang_tree_node
GTY((desc ("0"),
- chain_next ("(union lang_tree_node *)TREE_CHAIN (&%h.t)")))
+ chain_next ("*(union lang_tree_node **)&TREE_CHAIN (&%h.t)")))
{
union tree_node GTY((tag ("0"))) t;
};
Index: gcc-copying/gcc/java/java-tree.h
===================================================================
--- gcc-copying.orig/gcc/java/java-tree.h 2005-03-06 03:42:32.000000000 -0500
+++ gcc-copying/gcc/java/java-tree.h 2005-03-12 20:25:40.000000000 -0500
@@ -702,7 +702,7 @@ struct lang_identifier GTY(())
/* The resulting tree type. */
union lang_tree_node
GTY((desc ("TREE_CODE (&%h.generic) == IDENTIFIER_NODE"),
- chain_next ("(union lang_tree_node *)TREE_CHAIN (&%h.generic)")))
+ chain_next ("*(union lang_tree_node **)&TREE_CHAIN (&%h.generic)")))
{
union tree_node GTY ((tag ("0"),
desc ("tree_node_structure (&%h)")))
Index: gcc-copying/gcc/fortran/f95-lang.c
===================================================================
--- gcc-copying.orig/gcc/fortran/f95-lang.c 2005-02-09 19:22:17.000000000 -0500
+++ gcc-copying/gcc/fortran/f95-lang.c 2005-03-12 20:25:33.000000000 -0500
@@ -62,7 +62,7 @@ GTY(())
union lang_tree_node
GTY((desc ("TREE_CODE (&%h.generic) == IDENTIFIER_NODE"),
- chain_next ("(union lang_tree_node *)TREE_CHAIN (&%h.generic)")))
+ chain_next ("*(union lang_tree_node **)&TREE_CHAIN (&%h.generic)")))
{
union tree_node GTY((tag ("0"),
desc ("tree_node_structure (&%h)"))) generic;
Index: gcc-copying/gcc/ggc-zone.c
===================================================================
--- gcc-copying.orig/gcc/ggc-zone.c 2005-03-12 00:42:17.000000000 -0500
+++ gcc-copying/gcc/ggc-zone.c 2005-03-12 19:38:41.000000000 -0500
@@ -253,6 +253,9 @@ typedef struct page_entry
/* Is this page part of the loaded PCH? */
bool pch_p;
+
+ /* Is this page a source page for the copy collector? */
+ bool uncopied_p;
} page_entry;
/* Additional data needed for small pages. */
@@ -430,6 +433,9 @@ struct alloc_zone
/* True if this zone should be destroyed after the next collection. */
bool dead;
+ /* When copy collecting, the set of pages being copied from. */
+ struct small_page_entry *old_pages;
+
#ifdef GATHER_STATISTICS
struct
{
@@ -722,6 +728,7 @@ zone_allocate_marks (void)
{
page->mark_bits = cur_marks;
cur_marks += mark_words_per_page;
+ page->common.uncopied_p = true;
#ifdef ENABLE_CHECKING
n++;
#endif
@@ -910,6 +917,7 @@ free_small_page (struct small_page_entry
entry->next = entry->common.zone->free_pages;
entry->common.zone->free_pages = entry;
entry->common.zone->n_small_pages--;
+ entry->common.uncopied_p = false;
}
/* Release a large page that is no longer needed. */
@@ -1355,6 +1363,240 @@ ggc_free (void *p)
}
}
+/* BEGIN: The copying collector. */
+int
+ggc_copy_set_mark (void **p_slot)
+{
+ struct page_entry *page;
+ void *p = *p_slot;
+ const char *ptr = (const char *) p;
+
+ page = zone_get_object_page (p);
+
+ if (page->pch_p)
+ {
+ size_t mark_word, mark_bit, offset;
+ offset = (ptr - pch_zone.page) / BYTES_PER_MARK_BIT;
+ mark_word = offset / (8 * sizeof (mark_type));
+ mark_bit = offset % (8 * sizeof (mark_type));
+
+ if (pch_zone.mark_bits[mark_word] & (1 << mark_bit))
+ return 1;
+ pch_zone.mark_bits[mark_word] |= (1 << mark_bit);
+ }
+ else if (page->large_p)
+ {
+ struct large_page_entry *large_page
+ = (struct large_page_entry *) page;
+
+ if (large_page->mark_p)
+ return 1;
+ large_page->mark_p = true;
+ }
+ else
+ {
+ struct small_page_entry *small_page
+ = (struct small_page_entry *) page;
+
+ /* We set UNCOPIED_P on all the existing pages in this zone before
+ we began marking. All objects on newly allocated pages are already
+ marked - the object contents may not be, but we will recurse
+ through the uncopied object to take care of that.
+
+ This should not be necessary; an optimal marking algorithm
+ would call ggc_copy_set_mark only once for a particular
+ slot. However, there are a lot of excess calls in our
+ marking. For example, a mark routine using chain_next
+ will first mark each object on the chain, and then mark
+ the children of each object. But one of the children
+ will be the same as the chain. */
+ if (!small_page->common.uncopied_p)
+ return 1;
+
+ if (small_page->mark_bits[zone_get_object_mark_word (p)]
+ & (1 << zone_get_object_mark_bit (p)))
+ {
+ /* We don't copy tree identifiers. */
+ if (small_page->common.zone == &tree_id_zone)
+ return 1;
+
+ /* Otherwise, we must already have copied this object. */
+ *p_slot = ** (void ***) p_slot;
+
+ return 1;
+ }
+
+ small_page->mark_bits[zone_get_object_mark_word (p)]
+ |= (1 << zone_get_object_mark_bit (p));
+
+ /* We don't copy tree identifiers. */
+ if (small_page->common.zone != &tree_id_zone)
+ {
+ /* TODO: Can we statically determine the size at the
+ call site? More efficient... */
+ unsigned long size = ggc_get_size (p);
+
+ /* TODO: This needs to handle the memory statistics,
+ and update the detailed memory statistics hash tables. */
+ void *new_object = ggc_alloc_zone (size,
+ small_page->common.zone);
+
+ memcpy (new_object, p, size);
+
+ *p_slot = new_object;
+
+ /* Save the address of the new object. */
+ * (void **) p = new_object;
+ }
+ }
+
+ if (GGC_DEBUG_LEVEL >= 4)
+ fprintf (G.debug_file, "Marking %p\n", p);
+
+ return 0;
+}
+
+/* Free all empty pages and objects within a page for a given zone */
+
+static void
+copy_sweep_pages (struct alloc_zone *zone)
+{
+ struct large_page_entry **lpp, *lp, *lnext;
+ struct small_page_entry **spp, *sp, *snext;
+ size_t allocated = 0;
+
+ /* Large pages are all or none affairs. Either they are completely
+ empty, or they are completely full. */
+ lpp = &zone->large_pages;
+ for (lp = zone->large_pages; lp != NULL; lp = lnext)
+ {
+ gcc_assert (lp->common.large_p);
+
+ lnext = lp->next;
+
+#ifdef GATHER_STATISTICS
+ /* This page has now survived another collection. */
+ lp->common.survived++;
+#endif
+
+ if (lp->mark_p)
+ {
+ lp->mark_p = false;
+ allocated += lp->bytes;
+ lpp = &lp->next;
+ }
+ else
+ {
+ *lpp = lnext;
+#ifdef ENABLE_GC_CHECKING
+ /* Poison the page. */
+ memset (lp->common.page, 0xb5, SMALL_PAGE_SIZE);
+#endif
+ if (lp->prev)
+ lp->prev->next = lp->next;
+ if (lp->next)
+ lp->next->prev = lp->prev;
+ free_large_page (lp);
+ }
+ }
+
+ spp = &zone->old_pages;
+ for (sp = zone->old_pages; sp != NULL; sp = snext)
+ {
+ snext = sp->next;
+ *spp = snext;
+#ifdef ENABLE_GC_CHECKING
+ VALGRIND_DISCARD (VALGRIND_MAKE_WRITABLE (sp->common.page, SMALL_PAGE_SIZE));
+ /* Poison the page. */
+ memset (sp->common.page, 0xb5, SMALL_PAGE_SIZE);
+#endif
+ memset (sp->alloc_bits, 0,
+ G.small_page_overhead - PAGE_OVERHEAD);
+ free_small_page (sp);
+ }
+}
+
+/* Top level collection routine for the copy collector. */
+
+void
+ggc_copy_collect (void)
+{
+ struct alloc_zone *zone;
+
+ timevar_push (TV_GC);
+
+ zone_allocate_marks ();
+
+ for (zone = G.zones; zone; zone = zone->next_zone)
+ {
+ if (zone == &tree_id_zone)
+ continue;
+
+ /* First, reset the free_chunks lists, since we are going to
+ re-free free chunks in hopes of coalescing them into large
+ chunks. */
+ memset (zone->free_chunks, 0, sizeof (zone->free_chunks));
+ zone->high_free_bin = 0;
+ zone->cached_free = NULL;
+ zone->cached_free_size = 0;
+
+ /* FIXME: This output is going to be garbage because it isn't
+ staggered right; because marking modifies allocated, not just
+ sweeping. */
+ if (!quiet_flag)
+ fprintf (stderr, " {%s GC %luk -> ",
+ zone->name, (unsigned long) zone->allocated / 1024);
+
+ /* Zero the total allocated bytes. This will be recalculated in the
+ marking and sweep phases. */
+ zone->allocated = 0;
+
+ /* Release the pages we freed the last time we collected, but
+ didn't reuse in the interim. */
+ release_pages (zone);
+
+ zone->old_pages = zone->pages;
+ zone->pages = NULL;
+ }
+
+ ggc_copy_mark_roots ();
+#ifdef GATHER_STATISTICS
+ ggc_prune_overhead_list ();
+#endif
+
+ for (zone = G.zones; zone; zone = zone->next_zone)
+ {
+ if (zone == &tree_id_zone)
+ continue;
+
+ copy_sweep_pages (zone);
+ zone->allocated_last_gc = zone->allocated;
+ if (!quiet_flag)
+ fprintf (stderr, "%luk}", (unsigned long) zone->allocated / 1024);
+ }
+
+#ifdef GATHER_STATISTICS
+ /* Print page survival stats, if someone wants them. */
+ if (GGC_DEBUG_LEVEL >= 2)
+ {
+ for (zone = G.zones; zone; zone = zone->next_zone)
+ {
+ if (zone->was_collected)
+ {
+ float f = calculate_average_page_survival (zone);
+ printf ("Average page survival in zone `%s' is %f\n",
+ zone->name, f);
+ }
+ }
+ }
+#endif
+
+ zone_free_marks ();
+
+ timevar_pop (TV_GC);
+}
+/* END: The copying collector. */
+
/* If P is not marked, mark it and return false. Otherwise return true.
P must have been allocated by the GC allocator; it mustn't point to
static objects, stack variables, or memory allocated with malloc. */
Index: gcc-copying/gcc/ggc-common.c
===================================================================
--- gcc-copying.orig/gcc/ggc-common.c 2005-03-12 00:42:17.000000000 -0500
+++ gcc-copying/gcc/ggc-common.c 2005-03-12 18:17:21.000000000 -0500
@@ -131,6 +131,60 @@ ggc_mark_roots (void)
}
}
+/* Process a slot of an htab by deleting it if it has not been marked.
+ For the copy collector, mark the address of the slot instead of its
+ contents. */
+
+static int
+ggc_copy_htab_delete (void **slot, void *info)
+{
+ const struct ggc_cache_tab *r = (const struct ggc_cache_tab *) info;
+
+ if (! (*r->marked_p) (*slot))
+ htab_clear_slot (*r->base, slot);
+ else
+ (*r->copy_cb) (slot);
+
+ return 1;
+}
+
+/* Iterate through all registered roots and mark each element. For
+ the copy collector, we mark the addresses of roots instead of the
+ values of roots. */
+
+void
+ggc_copy_mark_roots (void)
+{
+ const struct ggc_root_tab *const *rt;
+ const struct ggc_root_tab *rti;
+ const struct ggc_cache_tab *const *ct;
+ const struct ggc_cache_tab *cti;
+ size_t i;
+
+ for (rt = gt_ggc_deletable_rtab; *rt; rt++)
+ for (rti = *rt; rti->base != NULL; rti++)
+ memset (rti->base, 0, rti->stride);
+
+ for (rt = gt_ggc_rtab; *rt; rt++)
+ for (rti = *rt; rti->base != NULL; rti++)
+ for (i = 0; i < rti->nelt; i++)
+ (*rti->copy_cb) ((char *)rti->base + rti->stride * i);
+
+ ggc_copy_mark_stringpool ();
+
+ /* Now scan all hash tables that have objects which are to be deleted if
+ they are not already marked. */
+ for (ct = gt_ggc_cache_rtab; *ct; ct++)
+ for (cti = *ct; cti->base != NULL; cti++)
+ if (*cti->base)
+ {
+ ggc_copy_set_mark ((void **) cti->base);
+ htab_traverse_noresize (*cti->base, ggc_copy_htab_delete,
+ (void *) cti);
+ ggc_copy_set_mark ((void **) &(*cti->base)->entries);
+ }
+}
+
/* Allocate a block of memory, then clear it. */
void *
ggc_alloc_cleared_stat (size_t size MEM_STAT_DECL)
Index: gcc-copying/gcc/c-decl.c
===================================================================
--- gcc-copying.orig/gcc/c-decl.c 2005-03-01 21:50:16.000000000 -0500
+++ gcc-copying/gcc/c-decl.c 2005-03-12 15:47:09.000000000 -0500
@@ -245,7 +245,7 @@ extern char C_SIZEOF_STRUCT_LANG_IDENTIF
union lang_tree_node
GTY((desc ("TREE_CODE (&%h.generic) == IDENTIFIER_NODE"),
- chain_next ("TREE_CODE (&%h.generic) == INTEGER_TYPE ? (union lang_tree_node *) TYPE_NEXT_VARIANT (&%h.generic) : (union lang_tree_node *) TREE_CHAIN (&%h.generic)")))
+ chain_next ("*(union lang_tree_node **) (TREE_CODE (&%h.generic) == INTEGER_TYPE ? &TYPE_NEXT_VARIANT (&%h.generic) : &TREE_CHAIN (&%h.generic))")))
{
union tree_node GTY ((tag ("0"),
desc ("tree_node_structure (&%h)")))
Index: gcc-copying/gcc/ggc.h
===================================================================
--- gcc-copying.orig/gcc/ggc.h 2005-03-12 00:42:17.000000000 -0500
+++ gcc-copying/gcc/ggc.h 2005-03-12 21:42:34.000000000 -0500
@@ -72,8 +72,9 @@ struct ggc_root_tab {
size_t stride;
gt_pointer_walker cb;
gt_pointer_walker pchw;
+ gt_pointer_walker copy_cb;
};
-#define LAST_GGC_ROOT_TAB { NULL, 0, 0, NULL, NULL }
+#define LAST_GGC_ROOT_TAB { NULL, 0, 0, NULL, NULL, NULL }
/* Pointers to arrays of ggc_root_tab, terminated by NULL. */
extern const struct ggc_root_tab * const gt_ggc_rtab[];
extern const struct ggc_root_tab * const gt_ggc_deletable_rtab[];
@@ -88,9 +89,10 @@ struct ggc_cache_tab {
size_t stride;
gt_pointer_walker cb;
gt_pointer_walker pchw;
+ gt_pointer_walker copy_cb;
int (*marked_p) (const void *);
};
-#define LAST_GGC_CACHE_TAB { NULL, 0, 0, NULL, NULL, NULL }
+#define LAST_GGC_CACHE_TAB { NULL, 0, 0, NULL, NULL, NULL, NULL }
/* Pointers to arrays of ggc_cache_tab, terminated by NULL. */
extern const struct ggc_cache_tab * const gt_ggc_cache_rtab[];
@@ -113,6 +115,26 @@ extern const struct ggc_cache_tab * cons
pointers in this data structure should not be traversed. */
extern int ggc_set_mark (const void *);
+/* Equivalent operations for copying collection. The argument has
+ an additional layer of indirection; ggc_set_copy_mark may change
+ *EXPR, whether or not it returns nonzero. */
+
+#define ggc_copy_test_and_set_mark(EXPR) \
+ (*(void **)(EXPR) != NULL \
+ && (*(void **) (EXPR)) != (void *) 1 \
+ && ! ggc_copy_set_mark ((void **) EXPR))
+
+/* FIXME: Is the case to (void *) safe? I'm being flexible with aliasing
+ here. */
+#define ggc_copy_mark(EXPR) \
+ do { \
+ void *const a__ = (void *) *(EXPR); \
+ if (a__ != NULL && a__ != (void *) 1) \
+ ggc_copy_set_mark ((void *) (EXPR)); \
+ } while (0)
+
+extern int ggc_copy_set_mark (void **);
+
/* Return 1 if P has been marked, zero otherwise.
P must have been allocated by the GC allocator; it mustn't point to
static objects, stack variables, or memory allocated with malloc. */
@@ -120,11 +142,16 @@ extern int ggc_marked_p (const void *);
/* Mark the entries in the string pool. */
extern void ggc_mark_stringpool (void);
+extern void ggc_copy_mark_stringpool (void);
/* Call ggc_set_mark on all the roots. */
extern void ggc_mark_roots (void);
+/* Call ggc_copy_set_mark on all the roots. */
+
+extern void ggc_copy_mark_roots (void);
+
/* Save and restore the string pool entries for PCH. */
extern void gt_pch_save_stringpool (void);
@@ -136,6 +163,7 @@ extern void gt_pch_restore_stringpool (v
extern void gt_pch_p_S (void *, void *, gt_pointer_operator, void *);
extern void gt_pch_n_S (const void *);
extern void gt_ggc_m_S (void *);
+extern void gt_ggc_c_S (void *);
/* Initialize the string pool. */
extern void init_stringpool (void);
@@ -268,6 +296,12 @@ extern const char *ggc_alloc_string (con
function is called, not during allocations. */
extern void ggc_collect (void);
+/* Invoke the copy collector. Copying garbage collection occurs only
+ when this function is called, not during allocations or calls to
+ ggc_collect. */
+/* FIXME: What if we don't have a copy collector? */
+extern void ggc_copy_collect (void);
+
/* Return the number of bytes allocated at the indicated address. */
extern size_t ggc_get_size (const void *);