* Re: Timings for copying collection vs non-copying collection
[not found] <1122918C-0ED0-11D7-AA8D-000393B2ABA2@apple.com>
@ 2002-12-13 21:23 ` Daniel Berlin
0 siblings, 0 replies; only message in thread
From: Daniel Berlin @ 2002-12-13 21:23 UTC (permalink / raw)
To: Matt Austern; +Cc: gcc-patches
On Fri, 13 Dec 2002, Matt Austern wrote:
> On Friday, December 13, 2002, at 09:35 AM, Daniel Berlin wrote:
>
> > Would people like me to post the patch against the pch branch for
> > copying collection so they can try it out themselves?
>
> I'd like to see it. I think there are a few GC
> experiments we ought to be trying, and this is
> clearly one of them.
>
> --Matt
>
>
I've attached the stack rewriting version that works
I've been making improvements on the non-stack rewriting version (it's
ggc-copy2.c), but it's non-functional right now as a result.
To be clear, I have no plans to make a real implementation submittable for
inclusion. Ever. I'm too busy with tree-ssa stuff.
Even with the non-stack rewriting version (which is a variant on mostly
copying), was only being done with performance testing of memory
fragmentation and locality in mind (what's necessary to get rid of stack
rewriting is the same as what is necessary to be able to easily make it
generational).
The internals of the actual collector are hackish to the extreme.
This is the result of it being done in about 4 hours in between studying
for finals.
If someone wants to make a production version, you should be able to keep
the gengtype stuff, and just redo the actual collector itstelf.
That said, here's the patch. It's against the pch-branch.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.822.2.40
diff -u -3 -p -r1.822.2.40 Makefile.in
--- Makefile.in 26 Nov 2002 22:29:24 -0000 1.822.2.40
+++ Makefile.in 14 Dec 2002 05:09:09 -0000
@@ -1346,6 +1346,9 @@ ggc-simple.o: ggc-simple.c $(CONFIG_H) $
ggc-page.o: ggc-page.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h \
toplev.h $(GGC_H) varray.h $(TIMEVAR_H) $(TM_P_H) $(PARAMS_H)
+ggc-copy.o: ggc-copy.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h \
+ toplev.h $(GGC_H) varray.h $(TIMEVAR_H) $(TM_P_H) $(PARAMS_H)
+
stringpool.o: stringpool.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(OBSTACK_H) \
$(GGC_H) gt-stringpool.h
Index: alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.162.2.7
diff -u -3 -p -r1.162.2.7 alias.c
--- alias.c 10 Nov 2002 07:16:41 -0000 1.162.2.7
+++ alias.c 14 Dec 2002 05:09:09 -0000
@@ -178,6 +178,7 @@ static rtx *alias_invariant;
pseudo-register N. This array is initialized in
init_alias_analysis, and does not change until end_alias_analysis
is called. */
+extern GTY ((length ("reg_known_value_size"))) rtx *reg_known_value;
rtx *reg_known_value;
/* Indicates number of valid entries in reg_known_value. */
@@ -2690,8 +2691,7 @@ init_alias_analysis ()
reg_known_value_size = maxreg;
reg_known_value
- = (rtx *) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (rtx))
- - FIRST_PSEUDO_REGISTER;
+ = (rtx *) ggc_alloc_cleared (maxreg * sizeof (rtx));
reg_known_equiv_p
= (char*) xcalloc ((maxreg - FIRST_PSEUDO_REGISTER), sizeof (char))
- FIRST_PSEUDO_REGISTER;
Index: configure
===================================================================
RCS file: /cvs/gcc/gcc/gcc/configure,v
retrieving revision 1.586.2.14
diff -u -3 -p -r1.586.2.14 configure
--- configure 26 Nov 2002 22:29:27 -0000 1.586.2.14
+++ configure 14 Dec 2002 05:09:11 -0000
@@ -2407,7 +2407,7 @@ EOF
fi
# Find some useful tools
-for ac_prog in mawk gawk nawk awk
+for ac_prog in gawk mawk nawk awk
do
# Extract the first word of "$ac_prog", so it can be a program name with args.
set dummy $ac_prog; ac_word=$2
@@ -8320,7 +8320,7 @@ if test "${with_gc+set}" = set; then
;;
esac
else
- GGC=ggc-page
+ GGC=ggc-copy
fi
Index: configure.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/configure.in,v
retrieving revision 1.576.2.13
diff -u -3 -p -r1.576.2.13 configure.in
--- configure.in 26 Nov 2002 22:29:31 -0000 1.576.2.13
+++ configure.in 14 Dec 2002 05:09:11 -0000
@@ -2410,7 +2410,7 @@ AC_ARG_WITH(gc,
AC_MSG_ERROR([$withval is an invalid option to --with-gc])
;;
esac],
-[GGC=ggc-page])
+[GGC=ggc-copy])
AC_SUBST(GGC)
echo "Using $GGC for garbage collection."
Index: gengtype.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gengtype.c,v
retrieving revision 1.1.2.42
diff -u -3 -p -r1.1.2.42 gengtype.c
--- gengtype.c 12 Dec 2002 04:12:41 -0000 1.1.2.42
+++ gengtype.c 14 Dec 2002 05:09:12 -0000
@@ -1376,9 +1376,30 @@ struct write_types_data
const char *subfield_marker_routine;
const char *marker_routine;
const char *reorder_note_routine;
+ unsigned int pass_address:1;
const char *comment;
};
+static const struct write_types_data ggc_wtd =
+{
+ "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", 0,
+ "PCH type-walking procedures. "
+};
+
+static const struct write_types_data copy_wtd =
+{
+ "copy_n", "copy_p","gt_copy_note_object", "gt_copy_note_object",
+ NULL, 1,
+ "Copying collector type-walking procedures. "
+};
+
static void output_escaped_param PARAMS ((struct walk_type_data *d,
const char *, const char *));
static void output_mangled_typename PARAMS ((outf_p, type_p));
@@ -1393,6 +1414,8 @@ static void write_types PARAMS ((type_p
const struct write_types_data *wtd));
static void write_types_local_process_field
PARAMS ((type_p f, const struct walk_type_data *d));
+static void write_types_local_process_field_spec
+ PARAMS ((type_p f, const struct walk_type_data *d));
static void write_local_func_for_structure
PARAMS ((type_p orig_s, type_p s, type_p * param));
static void write_local PARAMS ((type_p structures,
@@ -1562,6 +1585,8 @@ walk_type (t, d)
;
else if (strcmp (oo->name, "chain_next") == 0)
;
+ else if (strcmp (oo->name, "chain_nextp") == 0)
+ ;
else if (strcmp (oo->name, "chain_prev") == 0)
;
else if (strcmp (oo->name, "reorder") == 0)
@@ -1888,11 +1913,18 @@ write_types_process_field (f, d)
switch (f->kind)
{
case TYPE_POINTER:
+ if (wtd->subfield_marker_routine)
+ {
oprintf (d->of, "%*s%s (%s", d->indent, "",
wtd->subfield_marker_routine, d->val);
if (wtd->param_prefix)
{
- oprintf (d->of, ", %s", d->prev_val[3]);
+ if (wtd->pass_address && d->prev_val[3][0] != '&')
+ oprintf (d->of, ", (void **) &%s", d->prev_val[3]);
+ else if (wtd->pass_address)
+ oprintf (d->of, ", (void **)%s", d->prev_val[3]);
+ else
+ oprintf (d->of, ", %s", d->prev_val[3]);
if (d->orig_s)
{
oprintf (d->of, ", gt_%s_", wtd->param_prefix);
@@ -1906,6 +1938,7 @@ write_types_process_field (f, d)
oprintf (d->of, "%*s%s (%s, %s, %s);\n", d->indent, "",
wtd->reorder_note_routine, d->val,
d->prev_val[3], d->reorder_fn);
+ }
break;
case TYPE_STRING:
@@ -2009,7 +2042,10 @@ write_func_for_structure (orig_s, s, par
oprintf (d.of, " if (%s (x", wtd->marker_routine);
if (wtd->param_prefix)
{
- oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
+ if (wtd->pass_address)
+ oprintf (d.of, ", (void **)&x, gt_%s_", wtd->param_prefix);
+ else
+ oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
output_mangled_typename (d.of, orig_s);
}
oprintf (d.of, "))\n");
@@ -2019,7 +2055,10 @@ write_func_for_structure (orig_s, s, par
oprintf (d.of, " while (%s (xlimit", wtd->marker_routine);
if (wtd->param_prefix)
{
- oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
+ if (wtd->pass_address)
+ oprintf (d.of, ", (void **) &xlimit, gt_%s_", wtd->param_prefix);
+ else
+ oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
output_mangled_typename (d.of, orig_s);
}
oprintf (d.of, "))\n");
@@ -2044,7 +2083,10 @@ write_func_for_structure (orig_s, s, par
wtd->marker_routine);
if (wtd->param_prefix)
{
- oprintf (d.of, ", xprev, gt_%s_", wtd->param_prefix);
+ if (wtd->pass_address)
+ oprintf (d.of, ", (void **)&xprev, gt_%s_", wtd->param_prefix);
+ else
+ oprintf (d.of, ", xprev, gt_%s_", wtd->param_prefix);
output_mangled_typename (d.of, orig_s);
}
oprintf (d.of, ");\n");
@@ -2168,19 +2210,6 @@ write_types (structures, param_structs,
}
}
-static const struct write_types_data ggc_wtd =
-{
- "ggc_m", NULL, "ggc_mark", "ggc_test_and_set_mark", NULL,
- "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",
- "PCH type-walking procedures. "
-};
-
/* Write out the local pointer-walking routines. */
/* process_field routine for local pointer-walking. */
@@ -2211,6 +2240,34 @@ write_types_local_process_field (f, d)
}
}
+static void
+write_types_local_process_field_spec (f, d)
+ type_p f;
+ const struct walk_type_data *d;
+{
+ switch (f->kind)
+ {
+ case TYPE_POINTER:
+ case TYPE_STRUCT:
+ case TYPE_UNION:
+ case TYPE_LANG_STRUCT:
+ case TYPE_PARAM_STRUCT:
+ case TYPE_STRING:
+/* oprintf (d->of, "%*sif ((void *)(%s) == this_obj)\n", d->indent, "",
+ d->prev_val[3]);*/
+ oprintf (d->of, "%*sif ((void *)(%s) != NULL)\n", d->indent, "",
+ d->val);
+ oprintf (d->of, "%*s op (&(%s), cookie);\n", d->indent, "", d->val);
+ break;
+
+ case TYPE_SCALAR:
+ break;
+
+ default:
+ abort ();
+ }
+}
+
/* For S, a structure that's part of ORIG_S, and using parameters
PARAM, write out a routine that:
- Is of type gt_note_pointers
@@ -2262,6 +2319,35 @@ write_local_func_for_structure (orig_s,
d.indent = 2;
walk_type (s, &d);
oprintf (d.of, "}\n");
+
+ memset (&d, 0, sizeof (d));
+ d.of = get_output_file_with_visibility (fn);
+
+ d.process_field = write_types_local_process_field_spec;
+ d.opt = s->u.s.opt;
+ d.line = &s->u.s.line;
+ d.bitmap = s->u.s.bitmap;
+ d.param = param;
+ d.prev_val[0] = d.prev_val[2] = "*x";
+ d.prev_val[1] = "not valid postage"; /* guarantee an error */
+ d.prev_val[3] = "x";
+ d.val = "(*x)";
+ oprintf (d.of, "\n");
+ oprintf (d.of, "void\n");
+ oprintf (d.of, "gt_copy_p_");
+ output_mangled_typename (d.of, orig_s);
+ oprintf (d.of, " (this_obj, x_p, op, cookie)\n");
+ oprintf (d.of, " void *this_obj ATTRIBUTE_UNUSED;\n");
+ oprintf (d.of, " void *x_p;\n");
+ oprintf (d.of, " gt_pointer_operator op ATTRIBUTE_UNUSED;\n");
+ oprintf (d.of, " void *cookie ATTRIBUTE_UNUSED;\n");
+ oprintf (d.of, "{\n");
+ oprintf (d.of, " %s %s * const x ATTRIBUTE_UNUSED = (%s %s *)x_p;\n",
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag,
+ s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
+ d.indent = 2;
+ walk_type (s, &d);
+ oprintf (d.of, "}\n");
}
/* Write out local marker routines for STRUCTURES and PARAM_STRUCTS. */
@@ -2296,6 +2382,11 @@ write_local (structures, param_structs)
oprintf (header_file, " gt_pch_p_");
output_mangled_typename (header_file, t);
oprintf (header_file, "\n");
+ oprintf (header_file, "#define gt_copy_p_");
+ output_mangled_typename (header_file, s);
+ oprintf (header_file, " gt_copy_p_");
+ output_mangled_typename (header_file, t);
+ oprintf (header_file, "\n");
}
else
error_at_line (&s->u.s.line,
@@ -2310,6 +2401,12 @@ write_local (structures, param_structs)
output_mangled_typename (header_file, s);
oprintf (header_file,
"\n PARAMS ((void *, void *, gt_pointer_operator, void *));\n");
+
+ /* Declare the marker procedure only once. */
+ oprintf (header_file, "extern void gt_copy_p_");
+ output_mangled_typename (header_file, s);
+ oprintf (header_file,
+ "\n PARAMS ((void *, void *, gt_pointer_operator, void *));\n");
if (s->kind == TYPE_LANG_STRUCT)
{
@@ -2332,6 +2429,11 @@ write_local (structures, param_structs)
output_mangled_typename (header_file, s);
oprintf (header_file,
"\n PARAMS ((void *, void *, gt_pointer_operator, void *));\n");
+
+ oprintf (header_file, "extern void gt_copy_p_");
+ output_mangled_typename (header_file, s);
+ oprintf (header_file,
+ "\n PARAMS ((void *, void *, gt_pointer_operator, void *));\n");
if (stru->u.s.line.file == NULL)
{
@@ -2613,7 +2715,8 @@ write_root (f, v, type, name, has_length
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, " >_copy_nx_%s", tp->u.s.tag);
}
else if (! has_length && tp->kind == TYPE_PARAM_STRUCT)
{
@@ -2621,12 +2724,15 @@ write_root (f, v, type, name, has_length
output_mangled_typename (f, tp);
oprintf (f, ",\n >_pch_n_");
output_mangled_typename (f, tp);
+ oprintf (f, ",\n >_copy_n_");
+ 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, " >_copy_na_%s", name);
}
else
{
@@ -2647,7 +2753,8 @@ write_root (f, v, type, name, has_length
oprintf (f, " 1, \n");
oprintf (f, " sizeof (%s),\n", v->name);
oprintf (f, " >_ggc_m_S,\n");
- oprintf (f, " >_pch_n_S\n");
+ oprintf (f, " >_pch_n_S,\n");
+ oprintf (f, " >_copy_n_S\n");
oprintf (f, " },\n");
}
break;
@@ -2774,6 +2881,7 @@ write_roots (variables)
{
write_array (f, v, &ggc_wtd);
write_array (f, v, &pch_wtd);
+ write_array (f, v, ©_wtd);
}
}
@@ -2841,7 +2949,7 @@ write_roots (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);
}
@@ -2926,6 +3034,40 @@ write_roots (variables)
finish_root_table (flp, "pch_rc", "LAST_GGC_ROOT_TAB", "ggc_root_tab",
"gt_pch_cache_rtab");
+ for (v = variables; v; v = v->next)
+ {
+ outf_p f = get_output_file_with_visibility (v->line.file);
+ struct flist *fli;
+ int length_p = 0;
+ int if_marked_p = 0;
+ options_p o;
+
+ for (o = v->opt; o; o = o->next)
+ if (strcmp (o->name, "length") == 0)
+ length_p = 1;
+ else if (strcmp (o->name, "if_marked") == 0)
+ if_marked_p = 1;
+
+ if (! if_marked_p)
+ continue;
+
+ for (fli = flp; fli; fli = fli->next)
+ if (fli->f == f)
+ break;
+ if (! fli->started_p)
+ {
+ fli->started_p = 1;
+
+ oprintf (f, "struct ggc_root_tab gt_copy_rc_");
+ put_mangled_filename (f, v->line.file);
+ oprintf (f, "[] = {\n");
+ }
+
+ write_root (f, v, v->type, v->name, length_p, &v->line, NULL);
+ }
+
+ finish_root_table (flp, "copy_rc", "LAST_GGC_ROOT_TAB", "ggc_root_tab",
+ "gt_copy_cache_rtab");
for (v = variables; v; v = v->next)
{
@@ -2957,7 +3099,7 @@ write_roots (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);
}
@@ -3018,6 +3160,7 @@ main(argc, argv)
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: ggc-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ggc-common.c,v
retrieving revision 1.46.4.27
diff -u -3 -p -r1.46.4.27 ggc-common.c
--- ggc-common.c 12 Dec 2002 04:12:41 -0000 1.46.4.27
+++ ggc-common.c 14 Dec 2002 05:09:12 -0000
@@ -44,6 +44,7 @@ static ggc_statistics *ggc_stats;
struct traversal_state;
static int ggc_htab_delete PARAMS ((void **, void *));
+static int copy_htab_delete PARAMS ((void **, void *));
static hashval_t saving_htab_hash PARAMS ((const PTR));
static int saving_htab_eq PARAMS ((const PTR, const PTR));
static int call_count PARAMS ((void **, void *));
@@ -72,6 +73,23 @@ ggc_htab_delete (slot, info)
return 1;
}
+static int
+copy_htab_delete (slot, info)
+ void **slot;
+ void *info;
+{
+ const struct ggc_cache_tab *r = (const struct ggc_cache_tab *) info;
+
+ if (! was_forwarded (*slot))
+ htab_clear_slot (*r->base, slot);
+ else
+ {
+ alloc_and_copy ((void **)slot);
+ }
+
+ return 1;
+}
+
/* Iterate through all registered roots and mark each element. */
void
@@ -220,7 +238,6 @@ ggc_print_common_statistics (stream, sta
/* Functions for saving and restoring GCable memory to disk. */
static htab_t saving_htab;
-
struct ptr_data
{
void *obj;
@@ -420,6 +437,44 @@ struct mmap_info
size_t size;
void *preferred_base;
};
+void
+ggc_copy_roots ()
+{
+
+ 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)(*(void **)((char *)rti->base + rti->stride * i));
+ alloc_and_copy ((void **)((char *)rti->base + rti->stride * i));
+ }
+
+ for (rt = gt_pch_cache_rtab; *rt; rt++)
+ for (rti = *rt; rti->base != NULL; rti++)
+ for (i = 0; i < rti->nelt; i++)
+ {
+ (*rti->copy)(*(void **)((char *)rti->base + rti->stride * i));
+ alloc_and_copy ((void **)((char *)rti->base + rti->stride * i));
+ }
+
+ /* 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)
+ {
+ htab_traverse (*cti->base, copy_htab_delete, (PTR) cti);
+ }
+ ggc_copy_stringpool ();
+}
/* Write out the state of the compiler to F. */
@@ -622,4 +677,25 @@ gt_pch_restore (f)
}
gt_pch_restore_stringpool ();
+}
+int
+gt_copy_note_object (obj, note_ptr_cookie, note_ptr_fn)
+ void *obj;
+ void **note_ptr_cookie;
+ gt_note_pointers note_ptr_fn;
+{
+ void **ptr = (void **) note_ptr_cookie;
+ void *old = *note_ptr_cookie;
+ if (ggc_marked_p (*ptr))
+ return 0;
+ ggc_mark (*ptr);
+ if (*note_ptr_cookie != NULL && *note_ptr_cookie != (void *) 1)
+ {
+ note_ptr_fn (obj, *note_ptr_cookie, alloc_and_copy_forwalk, NULL);
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
}
Index: ggc-copy.c
===================================================================
RCS file: ggc-copy.c
diff -N ggc-copy.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ ggc-copy.c 14 Dec 2002 05:09:12 -0000
@@ -0,0 +1,481 @@
+/* "Bag-of-pages" garbage collector for the GNU compiler.
+ Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
+
+#include "config.h"
+#include "system.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "toplev.h"
+#include "varray.h"
+#include "flags.h"
+#include "ggc.h"
+#include "timevar.h"
+#include "splay-tree.h"
+#include "params.h"
+#include "basic-block.h"
+#include <sys/mman.h>
+static struct globals
+{
+ splay_tree marks;
+ int fromspacesize;
+ char *current;
+ char *start;
+ char *end;
+ char *fromspace;
+ char *tospace;
+ char *oldfrom;
+ char *oldend;
+
+ /* Data bytes currently allocated. */
+ size_t allocated;
+
+ /* Data objects currently allocated. */
+ size_t objects;
+
+ /* Data bytes allocated at time of last GC. */
+ size_t allocated_last_gc;
+
+ /* Current context level. */
+ int context;
+} G;
+struct ggc_mem
+{
+ unsigned int size : 24;
+ unsigned int forwarded:1;
+ void *forwardptr;
+ union {
+ HOST_WIDEST_INT i;
+ double d;
+ } u;
+} ;
+void *
+ggc_alloc (size)
+ size_t size;
+{
+ size_t memsize;
+ struct ggc_mem *x;
+ char *place;
+
+ place = G.current;
+ if (G.current + size > G.end)
+ abort();
+ x = (struct ggc_mem *)G.current;
+ x->size = size;
+ memsize = (offsetof (struct ggc_mem, u));
+ G.current += size + memsize;
+
+ G.allocated += size;
+ G.objects += 1;
+ return place + memsize;
+}
+/* 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. */
+
+int
+ggc_marked_p (p)
+ const void *p;
+{
+ return splay_tree_lookup (G.marks, (splay_tree_key) p) != 0;
+}
+
+/* Return the size of the gc-able object P. */
+
+size_t
+ggc_get_size (p)
+ const void *p;
+{
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ return x->size;
+}
+
+
+/* Initialize the ggc-mmap allocator. */
+void
+init_ggc ()
+{
+ G.marks = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
+ G.fromspace = mmap (0, 1024 * 1024 * 64, PROT_WRITE | PROT_READ , MAP_PRIVATE |MAP_ANONYMOUS, -1, 0);
+ G.start = G.fromspace;
+ G.current = G.fromspace;
+ G.end = G.fromspace + (1024 * 1024 * 64);
+}
+
+/* Increment the `GC context'. Objects allocated in an outer context
+ are never freed, eliminating the need to register their roots. */
+
+void
+ggc_push_context ()
+{
+/* Pointless since we stack mark. */
+#if 0
+ ++G.context_depth;
+
+ /* Die on wrap. */
+ if (G.context_depth == 0)
+ abort ();
+#endif
+}
+/* Decrement the `GC context'. All objects allocated since the
+ previous ggc_push_context are migrated to the outer context. */
+
+void
+ggc_pop_context ()
+{
+/* Pointless since we stack mark. */
+#if 0
+ unsigned order, depth;
+
+ depth = --G.context_depth;
+
+ /* Any remaining pages in the popped context are lowered to the new
+ current context; i.e. objects allocated in the popped context and
+ left over are imported into the previous context. */
+ for (order = 2; order < NUM_ORDERS; order++)
+ {
+ page_entry *p;
+
+ for (p = G.pages[order]; p != NULL; p = p->next)
+ {
+ if (p->context_depth > depth)
+ p->context_depth = depth;
+
+ /* If this page is now in the topmost context, and we'd
+ saved its allocation state, restore it. */
+ else if (p->context_depth == depth && p->save_in_use_p)
+ {
+ ggc_recalculate_in_use_p (p);
+ free (p->save_in_use_p);
+ p->save_in_use_p = 0;
+ }
+ }
+ }
+#endif
+}
+bool
+done_already (p)
+ void *p;
+{
+ return ((char *)p) >= G.fromspace && ((char *)p) <= G.end;
+}
+
+int
+ggc_set_mark (p)
+const void *p;
+{
+ if (ggc_marked_p (p))
+ return 1;
+ splay_tree_insert (G.marks, (splay_tree_key) p, 1);
+ return 0;
+}
+/* Top level mark-and-sweep routine. */
+
+extern void ggc_copy_roots PARAMS ((void));
+static void ggc_walk_stack PARAMS ((void));
+static void ggc_fixup_bbs PARAMS ((void));
+void
+ggc_collect ()
+{
+ void *oldfrom;
+ size_t oldfromsize;
+ /* Avoid frequent unnecessary work by skipping collection if the
+ total allocations haven't expanded much since the last
+ collection. */
+ size_t allocated_last_gc =
+ MAX (G.allocated_last_gc, (size_t)PARAM_VALUE (GGC_MIN_HEAPSIZE) * 1024);
+
+ size_t min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
+
+ if (G.allocated < allocated_last_gc + min_expand)
+ return;
+
+ timevar_push (TV_GC);
+ if (!quiet_flag)
+ fprintf (stderr, " {GC %luk -> ", (unsigned long) G.allocated / 1024);
+
+ /* Zero the total allocated bytes. This will be recalculated in the
+ sweep phase. */
+ G.allocated = 0;
+
+ splay_tree_delete (G.marks);
+ G.marks = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
+ G.allocated = 0;
+ G.objects = 0;
+ oldfromsize= G.fromspacesize;
+ G.fromspacesize = 0;
+ G.oldfrom = G.fromspace;
+ G.oldend = G.end;
+ G.tospace = mmap (0, 64 * 1024 * 1024, PROT_WRITE | PROT_READ , MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+ G.fromspace = G.tospace;
+ G.start = G.fromspace;
+ G.current = G.start;
+ G.end = G.start + (64 * 1024 * 1024);
+ G.tospace = NULL;
+ ggc_copy_roots ();
+ ggc_walk_stack ();
+ ggc_fixup_bbs ();
+ munmap (G.oldfrom, 64 * 1024 * 1024);
+ mprotect (G.oldfrom, 64 *1024*1024, PROT_NONE);
+ G.allocated_last_gc = G.allocated;
+
+ timevar_pop (TV_GC);
+
+ if (!quiet_flag)
+ fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
+
+}
+/* FIXME: Do mostly copying, not stack rewriting. */
+#pragma weak __libc_stack_end
+extern char * __libc_stack_end;
+
+static void
+ggc_fixup_bbs ()
+{
+ basic_block bb;
+ FOR_EACH_BB (bb)
+ {
+ alloc_and_copy ((void **)&bb->head);
+ alloc_and_copy ((void **)&bb->end);
+ }
+}
+static void
+ggc_walk_stack ()
+{
+ /* Forces registers to stack. */
+ __builtin_unwind_init();
+ if (&__libc_stack_end == 0)
+ abort();
+ {
+ int sp;
+ char *stackapprox = (char *)&sp;
+ char *stackend = __libc_stack_end;
+ while (stackapprox != stackend)
+ {
+ void **pp = (void **)stackapprox;
+ void *p = *pp;
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ if (((char *)p) >= G.oldfrom && ((char *)p) <= G.oldend)
+ {
+ if (x->forwarded)
+ *(void **)stackapprox = (void *) x->forwardptr;
+ }
+ stackapprox++;
+ }
+ }
+}
+void
+alloc_and_copy_forwalk (p, pp)
+ void *p;
+ void *pp;
+{
+ char * realaddr = (char *) (*(void **) p);
+ if (!(realaddr >= G.oldfrom && realaddr <= G.oldend))
+ return;
+ alloc_and_copy ((void ** )p);
+}
+bool
+was_forwarded (p)
+ void *p;
+{
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ char * realaddr = (char *) p;
+ if (!(realaddr >= G.oldfrom && realaddr <= G.oldend) && !done_already (p))
+ return false;
+ return x->forwarded == 1;
+}
+int
+alloc_and_copy (pp)
+ void **pp;
+{
+ void *newp;
+ void *p = *pp;
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ char * realaddr = (char *) p;
+ if (p == 0)
+ return 0;
+ if (done_already (p))
+ return 0;
+ if (!(realaddr >= G.oldfrom && realaddr <= G.oldend))
+ return 0;
+
+ if (x->forwarded)
+ {
+ *pp = x->forwardptr;
+ return 0;
+ }
+ newp = ggc_alloc (ggc_get_size (p));
+ x->forwarded = 1;
+ x->forwardptr = newp;
+ memcpy (newp, p, ggc_get_size (p));
+ *pp = newp;
+ return 1;
+}
+
+/* Print allocation statistics. */
+#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
+ ? (x) \
+ : ((x) < 1024*1024*10 \
+ ? (x) / 1024 \
+ : (x) / (1024*1024))))
+#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
+
+void
+ggc_print_statistics ()
+{
+#if 0
+ struct ggc_statistics stats;
+ unsigned int i;
+ size_t total_overhead = 0;
+
+ /* Clear the statistics. */
+ memset (&stats, 0, sizeof (stats));
+
+ /* Make sure collection will really occur. */
+ G.allocated_last_gc = 0;
+
+ /* Collect and print the statistics common across collectors. */
+ ggc_print_common_statistics (stderr, &stats);
+
+ /* Release free pages so that we will not count the bytes allocated
+ there as part of the total allocated memory. */
+ release_pages ();
+
+ /* Collect some information about the various sizes of
+ allocation. */
+ fprintf (stderr, "\n%-5s %10s %10s %10s\n",
+ "Size", "Allocated", "Used", "Overhead");
+ for (i = 0; i < NUM_ORDERS; ++i)
+ {
+ page_entry *p;
+ size_t allocated;
+ size_t in_use;
+ size_t overhead;
+
+ /* Skip empty entries. */
+ if (!G.pages[i])
+ continue;
+
+ overhead = allocated = in_use = 0;
+
+ /* Figure out the total number of bytes allocated for objects of
+ this size, and how many of them are actually in use. Also figure
+ out how much memory the page table is using. */
+ for (p = G.pages[i]; p; p = p->next)
+ {
+ allocated += p->bytes;
+ in_use +=
+ (OBJECTS_PER_PAGE (i) - p->num_free_objects) * OBJECT_SIZE (i);
+
+ overhead += (sizeof (page_entry) - sizeof (long)
+ + BITMAP_SIZE (OBJECTS_PER_PAGE (i) + 1));
+ }
+ fprintf (stderr, "%-5lu %10lu%c %10lu%c %10lu%c\n",
+ (unsigned long) OBJECT_SIZE (i),
+ SCALE (allocated), LABEL (allocated),
+ SCALE (in_use), LABEL (in_use),
+ SCALE (overhead), LABEL (overhead));
+ total_overhead += overhead;
+ }
+ fprintf (stderr, "%-5s %10lu%c %10lu%c %10lu%c\n", "Total",
+ SCALE (G.bytes_mapped), LABEL (G.bytes_mapped),
+ SCALE (G.allocated), LABEL(G.allocated),
+ SCALE (total_overhead), LABEL (total_overhead));
+#endif
+}
+struct ggc_pch_data
+{
+};
+
+struct ggc_pch_data *
+init_ggc_pch ()
+{
+ return xcalloc (sizeof (struct ggc_pch_data), 1);
+}
+
+void
+ggc_pch_count_object (d, x, size)
+ struct ggc_pch_data *d;
+ void *x ATTRIBUTE_UNUSED;
+ size_t size;
+{
+}
+
+size_t
+ggc_pch_total_size (d)
+ struct ggc_pch_data *d;
+{
+return 0;
+}
+
+void
+ggc_pch_this_base (d, base)
+ struct ggc_pch_data *d;
+ void *base;
+{
+}
+
+
+char *
+ggc_pch_alloc_object (d, x, size)
+ struct ggc_pch_data *d;
+ void *x ATTRIBUTE_UNUSED;
+ size_t size;
+{
+return 0;
+}
+
+void
+ggc_pch_prepare_write (d, f)
+ struct ggc_pch_data * d ATTRIBUTE_UNUSED;
+ FILE * f ATTRIBUTE_UNUSED;
+{
+ /* Nothing to do. */
+}
+
+void
+ggc_pch_write_object (d, f, x, newx, size)
+ struct ggc_pch_data * d ATTRIBUTE_UNUSED;
+ FILE *f;
+ void *x;
+ void *newx ATTRIBUTE_UNUSED;
+ size_t size;
+{
+}
+
+void
+ggc_pch_finish (d, f)
+ struct ggc_pch_data * d;
+ FILE *f;
+{
+ free (d);
+}
+
+void
+ggc_pch_read (f, addr)
+ FILE *f;
+ void *addr;
+{
+}
Index: ggc-page.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ggc-page.c,v
retrieving revision 1.48.4.8
diff -u -3 -p -r1.48.4.8 ggc-page.c
--- ggc-page.c 26 Nov 2002 22:29:34 -0000 1.48.4.8
+++ ggc-page.c 14 Dec 2002 05:09:12 -0000
@@ -1832,3 +1832,21 @@ ggc_pch_read (f, addr)
G.page_tails[i] = entry;
}
}
+int
+alloc_and_copy (p)
+ void **p;
+{
+ return 0;
+}
+void
+alloc_and_copy_forwalk (p1, p2)
+ void *p1;
+ void *p2;
+{
+}
+bool
+was_forwarded (p1)
+void *p1;
+{
+ return false;
+}
Index: ggc.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ggc.h,v
retrieving revision 1.39.6.25
diff -u -3 -p -r1.39.6.25 ggc.h
--- ggc.h 12 Dec 2002 04:12:42 -0000 1.39.6.25
+++ ggc.h 14 Dec 2002 05:09:12 -0000
@@ -52,6 +52,9 @@ typedef void (*gt_handle_reorder)
extern int gt_pch_note_object
PARAMS ((void *, void *, gt_note_pointers));
+extern int gt_copy_note_object
+ PARAMS ((void *, void **, gt_note_pointers));
+
/* Used by the gt_pch_n_* routines. Register that an object has a reorder
function. */
extern void gt_pch_note_reorder
@@ -68,8 +71,9 @@ struct ggc_root_tab {
size_t stride;
gt_pointer_walker cb;
gt_pointer_walker pchw;
+ gt_pointer_walker copy;
};
-#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[];
@@ -84,9 +88,10 @@ struct ggc_cache_tab {
size_t stride;
gt_pointer_walker cb;
gt_pointer_walker pchw;
+ gt_pointer_walker copy;
int (*marked_p) PARAMS ((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[];
@@ -131,6 +136,9 @@ extern void gt_pch_restore_stringpool PA
extern void gt_pch_p_S PARAMS ((void *, void *,
gt_pointer_operator, void *));
extern void gt_pch_n_S PARAMS ((const void *));
+extern void gt_copy_p_S PARAMS ((void *, void *,
+ gt_pointer_operator, void *));
+extern void gt_copy_n_S PARAMS ((const void *));
extern void gt_ggc_m_S PARAMS ((void *));
@@ -239,3 +247,6 @@ extern void ggc_print_common_statistics
/* Print allocation statistics. */
extern void ggc_print_statistics PARAMS ((void));
extern void stringpool_statistics PARAMS ((void));
+extern int alloc_and_copy PARAMS ((void **));
+extern void alloc_and_copy_forwalk PARAMS ((void *, void *));
+extern bool was_forwarded PARAMS ((void *));
Index: stringpool.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stringpool.c,v
retrieving revision 1.14.6.6
diff -u -3 -p -r1.14.6.6 stringpool.c
--- stringpool.c 12 Dec 2002 04:12:42 -0000 1.14.6.6
+++ stringpool.c 14 Dec 2002 05:09:13 -0000
@@ -169,6 +169,29 @@ ggc_mark_stringpool ()
{
ht_forall (ident_hash, mark_ident, NULL);
}
+static int
+copy_ident (pfile, h, v)
+ struct cpp_reader *pfile ATTRIBUTE_UNUSED;
+ hashnode h;
+ const PTR v ATTRIBUTE_UNUSED;
+{
+ gt_copy_n_9tree_node (HT_IDENT_TO_GCC_IDENT (h));
+ 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_stringpool ()
+{
+ unsigned int i;
+/* ht_forall (ident_hash, copy_ident, NULL);*/
+ for (i = 0; i < ident_hash->nslots; i++)
+ alloc_and_copy ((void **)&ident_hash->entries[i]);
+}
+
/* Strings are _not_ GCed, but this routine exists so that a separate
roots table isn't needed for the few global variables that refer
@@ -199,6 +222,13 @@ gt_pch_n_S (x)
const void *x;
{
gt_pch_note_object ((void *)x, (void *)x, >_pch_p_S);
+}
+
+void
+gt_copy_n_S (x)
+ const void *x;
+{
+/* gt_copy_note_object ((void *)x, (void *)&x, >_pch_p_S);*/
}
/* Handle saving and restoring the string pool for PCH. */
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2002-12-14 5:23 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <1122918C-0ED0-11D7-AA8D-000393B2ABA2@apple.com>
2002-12-13 21:23 ` Timings for copying collection vs non-copying collection Daniel Berlin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).