This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] Move loop structures to gc memory
Hello,
> Except that you lose all the benefits of it *not* being in GC.
>
> As a concrete example:
>
> Our basic blocks were pool allocated using alloc_pool's.
> Because they started pointing to GC'd structures directly (in order to
> simplify things), we switched them to be gc alloced.
>
> We lost about 1-2% compile time from doing this (see the archives),
> because alloc pools are contiguous in memory, and our gc was just
> handing out random free memory that happened to be around the same
> size.
>
> Things that have a very well defined lifetime (which are basic blocks
> do, for example), should not have to be in GC memory simply because
> they point to GC objects.
>
> You can argue that "well, it doesn't really hurt most of the time",
> "we could improve the GC to get better locality" etc, but it doesn't
> change that basic premise. No one in this thread has yet given a good
> reason we should have to GC things that we don't want to GC, just to
> get things they point to GC'd without really ugly hacks/workarounds.
>
> The only reason i've seen is "well, it's hard".
>
> Speed wise, profiles of the GC have never shown the actual root list
> walking to be slow, only the actual mark lookups and sets. Adding
> dynamic roots would make the root list walking slightly slower, but if
> we have *less* things in GC overall, we will do less mark setting,
> which is where most of GC time goes.
> So it should be a win overall.
something like the patch below? It allows you:
-- to specify a custom marking routine for a particular type, that is
called instead of the one provided by garbage collector. This
enables the objects of this type not to be allocated by gc, and
still survive ggc_collect even if gc collected things point to
them
-- adds dynamic roots to ggc-common
-- implements a particular instance of considering all objects allocated
in an alloc pool to be roots
-- and applies it to make basic blocks pool allocated
I guess this covers most of the profitable cases (basic blocks, edges,
loop structures), but it is easy to extend for other modes of
allocation. For simplicity, the patch allocates all basic blocks from
a single pool; it might be better to use per-function pools instead
(that would however need some more changes, in particular the way
omp code moves basic blocks between functions would break).
Of course, the patch is not quite finished (in particular, I am fairly
sure it breaks pch), but I would like to know whether we are both
thinking about the same thing, or if you imagine something different.
Zdenek
Index: doc/gty.texi
===================================================================
*** doc/gty.texi (revision 124785)
--- doc/gty.texi (working copy)
*************** reachable. This routine should not chang
*** 292,297 ****
--- 292,304 ----
routine. Its only argument is a pointer to the just marked (const)
structure or union.
+ @findex custom_mark
+ @item custom_mark ("@var{marking-routine-name}")
+
+ If provided for a structure or union type, the given
+ @var{marking-routine-name} (between double-quotes) is the name of a
+ routine called to mark the object instead of ggc_set_mark.
+
@findex maybe_undef
@item maybe_undef
Index: gengtype.c
===================================================================
*** gengtype.c (revision 124785)
--- gengtype.c (working copy)
*************** walk_type (type_p t, struct walk_type_da
*** 1914,1919 ****
--- 1914,1921 ----
desc = oo->info;
else if (strcmp (oo->name, "mark_hook") == 0)
;
+ else if (strcmp (oo->name, "custom_mark") == 0)
+ ;
else if (strcmp (oo->name, "nested_ptr") == 0)
nested_ptr_d = (const struct nested_ptr_data *) oo->info;
else if (strcmp (oo->name, "dot") == 0)
*************** write_func_for_structure (type_p orig_s,
*** 2416,2421 ****
--- 2418,2424 ----
const char *chain_next = NULL;
const char *chain_prev = NULL;
const char *mark_hook_name = NULL;
+ const char *marker_routine = wtd->marker_routine;
options_p opt;
struct walk_type_data d;
*************** write_func_for_structure (type_p orig_s,
*** 2435,2440 ****
--- 2438,2447 ----
chain_prev = opt->info;
else if (strcmp (opt->name, "mark_hook") == 0)
mark_hook_name = opt->info;
+ else if (strcmp (opt->name, "custom_mark") == 0
+ /* FIXME -- this will break pch. */
+ && !wtd->param_prefix)
+ marker_routine = opt->info;
if (chain_prev != NULL && chain_next == NULL)
error_at_line (&s->u.s.line, "chain_prev without chain_next");
*************** write_func_for_structure (type_p orig_s,
*** 2471,2477 ****
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)
{
oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
--- 2478,2484 ----
s->kind == TYPE_UNION ? "union" : "struct", s->u.s.tag);
if (chain_next == NULL)
{
! oprintf (d.of, " if (%s (x", marker_routine);
if (wtd->param_prefix)
{
oprintf (d.of, ", x, gt_%s_", wtd->param_prefix);
*************** write_func_for_structure (type_p orig_s,
*** 2482,2488 ****
}
else
{
! oprintf (d.of, " while (%s (xlimit", wtd->marker_routine);
if (wtd->param_prefix)
{
oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
--- 2489,2495 ----
}
else
{
! oprintf (d.of, " while (%s (xlimit", marker_routine);
if (wtd->param_prefix)
{
oprintf (d.of, ", xlimit, gt_%s_", wtd->param_prefix);
*************** write_func_for_structure (type_p orig_s,
*** 2514,2521 ****
oprintf (d.of, ");\n");
oprintf (d.of, " if (xprev == NULL) break;\n");
oprintf (d.of, " x = xprev;\n");
! oprintf (d.of, " (void) %s (xprev",
! wtd->marker_routine);
if (wtd->param_prefix)
{
oprintf (d.of, ", xprev, gt_%s_", wtd->param_prefix);
--- 2521,2527 ----
oprintf (d.of, ");\n");
oprintf (d.of, " if (xprev == NULL) break;\n");
oprintf (d.of, " x = xprev;\n");
! oprintf (d.of, " (void) %s (xprev", marker_routine);
if (wtd->param_prefix)
{
oprintf (d.of, ", xprev, gt_%s_", wtd->param_prefix);
Index: cfg.c
===================================================================
*** cfg.c (revision 124785)
--- cfg.c (working copy)
*************** static void free_edge (edge);
*** 76,92 ****
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
/* Called once at initialization time. */
void
init_flow (void)
{
if (!cfun->cfg)
cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph));
n_edges = 0;
! ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
! EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def));
EXIT_BLOCK_PTR->index = EXIT_BLOCK;
ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
--- 76,110 ----
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+ /* Pool for bb allocation. */
+
+ static alloc_pool bb_pool;
+
+ /* Description of the roots in this alloc pool. */
+
+ static struct alloc_pool_gc_description gc_bb_pool;
+
/* Called once at initialization time. */
void
init_flow (void)
{
+ if (!bb_pool)
+ {
+ bb_pool = create_alloc_pool ("basic blocks",
+ sizeof (struct basic_block_def), 100);
+ gc_bb_pool.pool = bb_pool;
+ gc_bb_pool.mark = gt_ggc_mx_basic_block_def;
+ register_dynamic_root (alloc_pool_gc_root, &gc_bb_pool);
+ }
+
if (!cfun->cfg)
cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph));
+
n_edges = 0;
! ENTRY_BLOCK_PTR = alloc_block ();
ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
! EXIT_BLOCK_PTR = alloc_block ();
EXIT_BLOCK_PTR->index = EXIT_BLOCK;
ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
*************** clear_edges (void)
*** 132,139 ****
basic_block
alloc_block (void)
{
! basic_block bb;
! bb = ggc_alloc_cleared (sizeof (*bb));
return bb;
}
--- 150,157 ----
basic_block
alloc_block (void)
{
! basic_block bb = pool_alloc (bb_pool);
! memset (bb, 0, sizeof (*bb));
return bb;
}
*************** expunge_block (basic_block b)
*** 191,201 ****
unlink_block (b);
SET_BASIC_BLOCK (b->index, NULL);
n_basic_blocks--;
! /* We should be able to ggc_free here, but we are not.
! The dead SSA_NAMES are left pointing to dead statements that are pointing
! to dead basic blocks making garbage collector to die.
! We should be able to release all dead SSA_NAMES and at the same time we should
! clear out BB pointer of dead statements consistently. */
}
/* Connect E to E->src. */
--- 209,215 ----
unlink_block (b);
SET_BASIC_BLOCK (b->index, NULL);
n_basic_blocks--;
! pool_free (bb_pool, b);
}
/* Connect E to E->src. */
Index: alloc-pool.c
===================================================================
*** alloc-pool.c (revision 124785)
--- alloc-pool.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 24,29 ****
--- 24,31 ----
#include "system.h"
#include "alloc-pool.h"
#include "hashtab.h"
+ #include "pointer-set.h"
+ #include "ggc.h"
#define align_eight(x) (((x+7) >> 3) << 3)
*************** create_alloc_pool (const char *name, siz
*** 180,185 ****
--- 182,226 ----
return (pool);
}
+ /* Mark elements of pool described in struct alloc_pool_gc_description
+ as gc roots. */
+
+ void
+ alloc_pool_gc_root (void *data)
+ {
+ struct alloc_pool_gc_description *desc = data;
+ struct pointer_set_t *free_elts = pointer_set_create ();
+ alloc_pool_list elt, block_header;
+ char *block;
+ alloc_pool pool = desc->pool;
+ unsigned i;
+
+ /* Find the allocated elements of the pool. This is somewhat tricky, as
+ we do not track those, but it suffices to traverse all elements of the
+ pool and ignore the free ones. */
+ for (elt = pool->free_list; elt != NULL; elt = elt->next)
+ pointer_set_insert (free_elts, elt);
+
+ for (block_header = pool->block_list;
+ block_header != NULL;
+ block_header = block_header->next)
+ {
+ block = (char *) block_header;
+ block += align_eight (sizeof (struct alloc_pool_list_def));
+
+ for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
+ {
+ elt = (alloc_pool_list) USER_PTR_FROM_ALLOCATION_OBJECT_PTR (block);
+ if (pointer_set_contains (free_elts, elt))
+ continue;
+
+ ggc_mark_dynamic_root (desc->mark, (void *) elt);
+ }
+ }
+
+ pointer_set_destroy (free_elts);
+ }
+
/* Free all memory allocated for the given memory pool. */
void
free_alloc_pool (alloc_pool pool)
Index: alloc-pool.h
===================================================================
*** alloc-pool.h (revision 124785)
--- alloc-pool.h (working copy)
*************** typedef struct alloc_pool_def
*** 47,56 ****
--- 47,69 ----
}
*alloc_pool;
+ /* Description of the alloc pool for marking gc roots. */
+
+ struct alloc_pool_gc_description
+ {
+ /* The pool. */
+ alloc_pool pool;
+
+ /* The function used to traverse the elements of the pool. */
+ void (*mark) (void *);
+ };
+
extern alloc_pool create_alloc_pool (const char *, size_t, size_t);
extern void free_alloc_pool (alloc_pool);
extern void free_alloc_pool_if_empty (alloc_pool *);
extern void *pool_alloc (alloc_pool);
extern void pool_free (alloc_pool, void *);
extern void dump_alloc_pool_statistics (void);
+ extern void alloc_pool_gc_root (void *);
+
#endif
Index: ggc.h
===================================================================
*** ggc.h (revision 124785)
--- ggc.h (working copy)
*************** extern void ggc_mark_stringpool (void);
*** 125,130 ****
--- 125,149 ----
extern void ggc_mark_roots (void);
+ /* Dynamic root management. */
+
+ struct dynamic_root
+ {
+ /* Double linked list of roots. */
+ struct dynamic_root *prev, *next;
+
+ /* Function called to mark the root. */
+ void (*mark) (void *);
+
+ /* Data of the root. */
+ void *data;
+ };
+
+ int ggc_set_dynamic_root_mark (const void *);
+ void ggc_mark_dynamic_root (void (*) (void *), void *);
+ struct dynamic_root *register_dynamic_root (void (*) (void *), void *);
+ void unregister_dynamic_root (struct dynamic_root *);
+
/* Save and restore the string pool entries for PCH. */
extern void gt_pch_save_stringpool (void);
Index: ggc-common.c
===================================================================
*** ggc-common.c (revision 124785)
--- ggc-common.c (working copy)
*************** bool ggc_force_collect;
*** 67,72 ****
--- 67,76 ----
/* Statistics about the allocation. */
static ggc_statistics *ggc_stats;
+ /* Dynamic roots. */
+
+ static struct dynamic_root *dynamic_roots;
+
struct traversal_state;
static int ggc_htab_delete (void **, void *);
*************** ggc_htab_delete (void **slot, void *info
*** 97,102 ****
--- 101,166 ----
return 1;
}
+ /* Mark function for objects that serve as dynamic ggc roots. Returns
+ 1 if it is called because of invocation of the gc traversal function
+ from ggc_mark_dynamic_root, and 0 otherwise. */
+
+ static bool called_from_ggc_mark_dynamic_root;
+ int
+ ggc_set_dynamic_root_mark (const void *p ATTRIBUTE_UNUSED)
+ {
+ if (called_from_ggc_mark_dynamic_root)
+ {
+ called_from_ggc_mark_dynamic_root = false;
+ return 1;
+ }
+
+ return 0;
+ }
+
+ /* Marks dynamic root ROOT, and traverse it using MARK_FUNCTION. */
+
+ void
+ ggc_mark_dynamic_root (void (*mark_function) (void *), void *root)
+ {
+ called_from_ggc_mark_dynamic_root = true;
+ mark_function (root);
+ called_from_ggc_mark_dynamic_root = false;
+ }
+
+ /* Registers and returns a dynamic root with marking function MARK. DATA are
+ passed to MARK when it is run. */
+
+ struct dynamic_root *
+ register_dynamic_root (void (*mark) (void *), void *data)
+ {
+ struct dynamic_root *dr = XNEW (struct dynamic_root);
+
+ dr->mark = mark;
+ dr->data = data;
+ dr->next = dynamic_roots;
+ dr->prev = NULL;
+ if (dr->next)
+ dr->next->prev = dr;
+ dynamic_roots = dr;
+
+ return dr;
+ }
+
+ /* Unregisters and releases a dynamic root DR. */
+
+ void
+ unregister_dynamic_root (struct dynamic_root *dr)
+ {
+ if (dr->next)
+ dr->next->prev = dr->prev;
+
+ if (dr->prev)
+ dr->prev->next = dr->next;
+ else
+ dynamic_roots = dr->next;
+ }
+
/* Iterate through all registered roots and mark each element. */
void
*************** ggc_mark_roots (void)
*** 106,111 ****
--- 170,176 ----
const struct ggc_root_tab *rti;
const struct ggc_cache_tab *const *ct;
const struct ggc_cache_tab *cti;
+ struct dynamic_root *dr;
size_t i;
for (rt = gt_ggc_deletable_rtab; *rt; rt++)
*************** ggc_mark_roots (void)
*** 117,122 ****
--- 182,190 ----
for (i = 0; i < rti->nelt; i++)
(*rti->cb)(*(void **)((char *)rti->base + rti->stride * i));
+ for (dr = dynamic_roots; dr; dr = dr->next)
+ dr->mark (dr->data);
+
ggc_mark_stringpool ();
/* Now scan all hash tables that have objects which are to be deleted if
Index: Makefile.in
===================================================================
*** Makefile.in (revision 124785)
--- Makefile.in (working copy)
*************** value-prof.o : value-prof.c $(CONFIG_H)
*** 2510,2516 ****
loop-doloop.o : loop-doloop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(FLAGS_H) $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) \
toplev.h $(CFGLOOP_H) output.h $(PARAMS_H) $(TARGET_H)
! alloc-pool.o : alloc-pool.c $(CONFIG_H) $(SYSTEM_H) alloc-pool.h $(HASHTAB_H)
flow.o : flow.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(TREE_H) $(FLAGS_H) insn-config.h $(BASIC_BLOCK_H) $(REGS_H) \
hard-reg-set.h output.h toplev.h $(RECOG_H) $(FUNCTION_H) except.h \
--- 2510,2517 ----
loop-doloop.o : loop-doloop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(FLAGS_H) $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) $(TM_P_H) \
toplev.h $(CFGLOOP_H) output.h $(PARAMS_H) $(TARGET_H)
! alloc-pool.o : alloc-pool.c $(CONFIG_H) $(SYSTEM_H) alloc-pool.h $(HASHTAB_H) \
! pointer-set.h $(GGC_H)
flow.o : flow.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(TREE_H) $(FLAGS_H) insn-config.h $(BASIC_BLOCK_H) $(REGS_H) \
hard-reg-set.h output.h toplev.h $(RECOG_H) $(FUNCTION_H) except.h \
Index: basic-block.h
===================================================================
*** basic-block.h (revision 124786)
--- basic-block.h (working copy)
*************** struct rtl_bb_info;
*** 211,217 ****
basic blocks. */
/* Basic block information indexed by block number. */
! struct basic_block_def GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb")))
{
/* The edges into and out of the block. */
VEC(edge,gc) *preds;
--- 211,217 ----
basic blocks. */
/* Basic block information indexed by block number. */
! struct basic_block_def GTY((custom_mark ("ggc_set_dynamic_root_mark")))
{
/* The edges into and out of the block. */
VEC(edge,gc) *preds;