/* Simple garbage collection for the GNU compiler.
- Copyright (C) 1998 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
- This file is part of GNU CC.
+ This file is part of GCC.
- GNU CC is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
+ 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.
- GNU CC 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.
+ 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 GNU CC; see the file COPYING. If not, write to
- the Free Software Foundation, 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA. */
+ 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 "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "tree.h"
-#include "ggc.h"
+#include "tm_p.h"
#include "flags.h"
#include "varray.h"
-#include "hash.h"
+#include "ggc.h"
+#include "toplev.h"
+#include "timevar.h"
+#include "params.h"
/* Debugging flags. */
/* Zap memory before freeing to catch dangling pointers. */
-#define GGC_POISON
+#undef GGC_POISON
-/* Log alloc and release. Don't enable this unless you want a
- really really lot of data. */
-#undef GGC_DUMP
+/* Collect statistics on how bushy the search tree is. */
+#undef GGC_BALANCE
-/* Global lists of roots, rtxs, and trees. */
+/* Always verify that the to-be-marked memory is collectable. */
+#undef GGC_ALWAYS_VERIFY
-struct ggc_root
-{
- struct ggc_root *next;
- void *base;
- int nelt;
- int size;
- void (*cb) PROTO ((void *));
-};
+#ifdef ENABLE_GC_CHECKING
+#define GGC_POISON
+#define GGC_ALWAYS_VERIFY
+#endif
-static struct ggc_root *roots;
+#ifndef HOST_BITS_PER_PTR
+#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
+#endif
-struct ggc_rtx
-{
- struct ggc_rtx *chain;
- struct rtx_def rtx;
-};
+/* We'd like a balanced tree, but we don't really want to pay for the
+ cost of keeping the tree balanced. We'll settle for the next best
+ thing -- nearly balanced.
-struct ggc_rtvec
-{
- struct ggc_rtvec *chain;
- struct rtvec_def vec;
-};
+ In this context, the most natural key is the node pointer itself,
+ but due to the way memory managers work, we'd be virtually certain
+ to wind up with a completely degenerate straight line. What's needed
+ is to make something more variable, and yet predictable, be more
+ significant in the comparison.
-struct ggc_tree
-{
- struct ggc_tree *chain;
- union tree_node tree;
-};
+ The handiest source of variability is the low bits of the pointer
+ value itself. Any sort of bit/byte swap would do, but such machine
+ specific operations are not handy, and we don't want to put that much
+ effort into it. */
-struct ggc_string
-{
- struct ggc_string *chain;
- int magic_mark;
- char string[1];
-};
+#define PTR_KEY(p) ((size_t)p << (HOST_BITS_PER_PTR - 8) \
+ | ((size_t)p & 0xff00) << (HOST_BITS_PER_PTR - 24) \
+ | (size_t)p >> 16)
-/* A generic allocation, with an external mark bit. */
+/* GC'able memory; a node in a binary search tree. */
-struct ggc_any
+struct ggc_mem
{
- struct ggc_any *chain;
- char mark;
+ /* A combination of the standard left/right nodes, indexable by `<'. */
+ struct ggc_mem *sub[2];
+
+ unsigned int mark : 1;
+ unsigned int context : 7;
+ unsigned int size : 24;
/* Make sure the data is reasonably aligned. */
union {
- char c;
- HOST_WIDE_INT i;
+ HOST_WIDEST_INT i;
+#ifdef HAVE_LONG_DOUBLE
long double d;
+#else
+ double d;
+#endif
} u;
};
-#define GGC_STRING_MAGIC ((unsigned int)0xa1b2c3d4)
-
-struct ggc_status
+static struct globals
{
- struct ggc_status *next;
- struct ggc_rtx *rtxs;
- struct ggc_rtvec *vecs;
- struct ggc_tree *trees;
- struct ggc_string *strings;
- struct ggc_any *anys;
- size_t bytes_alloced_since_gc;
-};
+ /* Root of the object tree. */
+ struct ggc_mem *root;
-/* A chain of GGC contexts. The currently active context is at the
- front of the chain. */
-static struct ggc_status *ggc_chain;
+ /* Data bytes currently allocated. */
+ size_t allocated;
-/* Some statistics. */
+ /* Data objects currently allocated. */
+ size_t objects;
-static int n_rtxs_collected;
-static int n_vecs_collected;
-static int n_trees_collected;
-static int n_strings_collected;
-static int n_anys_collected;
-extern int gc_time;
+ /* Data bytes allocated at time of last GC. */
+ size_t allocated_last_gc;
-#ifdef GGC_DUMP
-static FILE *dump;
-#endif
+ /* Current context level. */
+ int context;
+} G;
/* Local function prototypes. */
-static void ggc_free_rtx PROTO ((struct ggc_rtx *r));
-static void ggc_free_tree PROTO ((struct ggc_tree *t));
-static void ggc_mark_rtx_ptr PROTO ((void *elt));
-static void ggc_mark_tree_ptr PROTO ((void *elt));
-static void ggc_mark_tree_varray_ptr PROTO ((void *elt));
-static void ggc_mark_tree_hash_table_ptr PROTO ((void *elt));
-static boolean ggc_mark_tree_hash_table_entry PROTO ((struct hash_entry *,
- hash_table_key));
+static void tree_insert PARAMS ((struct ggc_mem *));
+static int tree_lookup PARAMS ((struct ggc_mem *));
+static void clear_marks PARAMS ((struct ggc_mem *));
+static void sweep_objs PARAMS ((struct ggc_mem **));
+static void ggc_pop_context_1 PARAMS ((struct ggc_mem *, int));
-/* Called once to initialize the garbage collector. */
+/* For use from debugger. */
+extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int));
-void
-init_ggc PROTO ((void))
-{
- /* Initialize the global context. */
- ggc_push_context ();
-
-#ifdef GGC_DUMP
- dump = fopen ("zgcdump", "w");
- setlinebuf (dump);
+#ifdef GGC_BALANCE
+extern void debug_ggc_balance PARAMS ((void));
#endif
-}
+static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *));
-/* Start a new GGC context. Memory allocated in previous contexts
- will not be collected while the new context is active. */
+/* Insert V into the search tree. */
-void
-ggc_push_context PROTO ((void))
+static inline void
+tree_insert (v)
+ struct ggc_mem *v;
{
- struct ggc_status *gs = (struct ggc_status *) xcalloc (1, sizeof (*gs));
- gs->next = ggc_chain;
- ggc_chain = gs;
-}
+ size_t v_key = PTR_KEY (v);
+ struct ggc_mem *p, **pp;
-/* Finish a GC context. Any uncollected memory in the new context
- will be merged with the old context. */
-
-void
-ggc_pop_context PROTO ((void))
-{
- struct ggc_rtx *r;
- struct ggc_rtvec *v;
- struct ggc_tree *t;
- struct ggc_string *s;
- struct ggc_status *gs;
-
- gs = ggc_chain;
-
- r = gs->rtxs;
- if (r)
+ for (pp = &G.root, p = *pp; p ; p = *pp)
{
- while (r->chain)
- r = r->chain;
- r->chain = gs->next->rtxs;
- gs->next->rtxs = gs->rtxs;
- }
-
- v = gs->vecs;
- if (v)
- {
- while (v->chain)
- v = v->chain;
- v->chain = gs->next->vecs;
- gs->next->vecs = gs->vecs;
+ size_t p_key = PTR_KEY (p);
+ pp = &p->sub[v_key < p_key];
}
+ *pp = v;
+}
- t = gs->trees;
- if (t)
- {
- while (t->chain)
- t = t->chain;
- t->chain = gs->next->trees;
- gs->next->trees = gs->trees;
- }
+/* Return true if V is in the tree. */
- s = gs->strings;
- if (s)
+static inline int
+tree_lookup (v)
+ struct ggc_mem *v;
+{
+ size_t v_key = PTR_KEY (v);
+ struct ggc_mem *p = G.root;
+
+ while (p)
{
- while (s->chain)
- s = s->chain;
- s->chain = gs->next->strings;
- gs->next->strings = gs->strings;
+ size_t p_key = PTR_KEY (p);
+ if (p == v)
+ return 1;
+ p = p->sub[v_key < p_key];
}
- ggc_chain = gs->next;
- free (gs);
+ return 0;
}
-/* These allocators are dreadfully simple, with no caching whatsoever so
- that Purify-like tools that do allocation versioning can catch errors.
- This collector is never going to go fast anyway. */
+/* Alloc SIZE bytes of GC'able memory. If ZERO, clear the memory. */
-rtx
-ggc_alloc_rtx (nslots)
- int nslots;
+void *
+ggc_alloc (size)
+ size_t size;
{
- struct ggc_rtx *n;
- int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
+ struct ggc_mem *x;
- n = (struct ggc_rtx *) xcalloc (1, size);
- n->chain = ggc_chain->rtxs;
- ggc_chain->rtxs = n;
+ x = (struct ggc_mem *) xmalloc (offsetof (struct ggc_mem, u) + size);
+ x->sub[0] = NULL;
+ x->sub[1] = NULL;
+ x->mark = 0;
+ x->context = G.context;
+ x->size = size;
-#ifdef GGC_DUMP
- fprintf (dump, "alloc rtx %p\n", &n->rtx);
+#ifdef GGC_POISON
+ memset (&x->u, 0xaf, size);
#endif
- ggc_chain->bytes_alloced_since_gc += size;
+ tree_insert (x);
+ G.allocated += size;
+ G.objects += 1;
- return &n->rtx;
+ return &x->u;
}
-rtvec
-ggc_alloc_rtvec (nelt)
- int nelt;
-{
- struct ggc_rtvec *v;
- int size = sizeof (*v) + (nelt - 1) * sizeof (rtx);
-
- v = (struct ggc_rtvec *) xcalloc (1, size);
- v->chain = ggc_chain->vecs;
- ggc_chain->vecs = v;
-
-#ifdef GGC_DUMP
- fprintf(dump, "alloc vec %p\n", &v->vec);
-#endif
-
- ggc_chain->bytes_alloced_since_gc += size;
-
- return &v->vec;
-}
+/* Mark a node. */
-tree
-ggc_alloc_tree (length)
- int length;
+int
+ggc_set_mark (p)
+ const void *p;
{
- struct ggc_tree *n;
- int size = sizeof(*n) - sizeof(n->tree) + length;
-
- n = (struct ggc_tree *) xcalloc (1, size);
- n->chain = ggc_chain->trees;
- ggc_chain->trees = n;
+ struct ggc_mem *x;
-#ifdef GGC_DUMP
- fprintf(dump, "alloc tree %p\n", &n->tree);
+ x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+#ifdef GGC_ALWAYS_VERIFY
+ if (! tree_lookup (x))
+ abort ();
#endif
- ggc_chain->bytes_alloced_since_gc += size;
+ if (x->mark)
+ return 1;
- return &n->tree;
-}
+ x->mark = 1;
+ G.allocated += x->size;
+ G.objects += 1;
-char *
-ggc_alloc_string (contents, length)
- const char *contents;
- int length;
-{
- struct ggc_string *s;
- int size;
-
- if (length < 0)
- {
- if (contents == NULL)
- return NULL;
- length = strlen (contents);
- }
-
- size = (s->string - (char *)s) + length + 1;
- s = (struct ggc_string *) xmalloc(size);
- s->chain = ggc_chain->strings;
- s->magic_mark = GGC_STRING_MAGIC;
- if (contents)
- bcopy (contents, s->string, length);
- s->string[length] = 0;
- ggc_chain->strings = s;
-
-#ifdef GGC_DUMP
- fprintf(dump, "alloc string %p\n", &s->string);
-#endif
-
- ggc_chain->bytes_alloced_since_gc += size;
-
- return s->string;
+ return 0;
}
-/* Like xmalloc, but allocates GC-able memory. */
+/* Return 1 if P has been marked, zero otherwise. */
-void *
-ggc_alloc (bytes)
- size_t bytes;
+int
+ggc_marked_p (p)
+ const void *p;
{
- struct ggc_any *a;
+ struct ggc_mem *x;
- if (bytes == 0)
- bytes = 1;
- bytes += (&((struct ggc_any *) 0)->u.c - (char *) 0);
-
- a = (struct ggc_any *) xmalloc (bytes);
- a->chain = ggc_chain->anys;
- ggc_chain->anys = a;
-
- return &a->u;
-}
-
-/* Freeing a bit of rtl is as simple as calling free. */
-
-static void
-ggc_free_rtx (r)
- struct ggc_rtx *r;
-{
-#ifdef GGC_DUMP
- fprintf (dump, "collect rtx %p\n", &r->rtx);
-#endif
-#ifdef GGC_POISON
- memset (r, 0xAA, sizeof(*r) + ((GET_RTX_LENGTH (r->rtx.code) -1)
- * sizeof(rtunion)));
+ x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+#ifdef GGC_ALWAYS_VERIFY
+ if (! tree_lookup (x))
+ abort ();
#endif
- free (r);
+ return x->mark;
}
-/* Freeing an rtvec is as simple as calling free. */
+/* Return the size of the gc-able object P. */
-static void
-ggc_free_rtvec (v)
- struct ggc_rtvec *v;
+size_t
+ggc_get_size (p)
+ const void *p;
{
-#ifdef GGC_DUMP
- fprintf(dump, "collect vec %p\n", &v->vec);
-#endif
-#ifdef GGC_POISON
- memset (v, 0xBB, sizeof (*v) + ((GET_NUM_ELEM (&v->vec) - 1)
- * sizeof (rtunion)));
-#endif
-
- free (v);
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ return x->size;
}
-/* Freeing a tree node is almost, but not quite, as simple as calling free.
- Mostly we need to let the language clean up its lang_specific bits. */
+/* Unmark all objects. */
static void
-ggc_free_tree (t)
- struct ggc_tree *t;
+clear_marks (x)
+ struct ggc_mem *x;
{
- switch (TREE_CODE_CLASS (TREE_CODE (&t->tree)))
- {
- case 'd': /* A decl node. */
- case 't': /* A type node. */
- lang_cleanup_tree (&t->tree);
- break;
- }
-
-#ifdef GGC_DUMP
- fprintf (dump, "collect tree %p\n", &t->tree);
-#endif
-#ifdef GGC_POISON
- memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
-#endif
-
- free (t);
+ x->mark = 0;
+ if (x->sub[0])
+ clear_marks (x->sub[0]);
+ if (x->sub[1])
+ clear_marks (x->sub[1]);
}
-/* Freeing a string is as simple as calling free. */
+/* Free all objects in the current context that are not marked. */
static void
-ggc_free_string (s)
- struct ggc_string *s;
+sweep_objs (root)
+ struct ggc_mem **root;
{
-#ifdef GGC_DUMP
- fprintf(dump, "collect string %p\n", s->string);
-#endif
-#ifdef GGC_POISON
- s->magic_mark = 0xDDDDDDDD;
- s->string[0] = 0xDD;
-#endif
-
- free (s);
-}
-
-/* Mark a node. */
-
-void
-ggc_mark_rtx (r)
- rtx r;
-{
- const char *fmt;
- int i;
-
- if (r == NULL_RTX || r->gc_mark)
+ struct ggc_mem *x = *root;
+ if (!x)
return;
- r->gc_mark = 1;
- /* ??? If (some of) these are really pass-dependant info, do we have
- any right poking our noses in? */
- switch (GET_CODE (r))
+ sweep_objs (&x->sub[0]);
+ sweep_objs (&x->sub[1]);
+
+ if (! x->mark && x->context >= G.context)
{
- case JUMP_INSN:
- ggc_mark_rtx (JUMP_LABEL (r));
- break;
- case CODE_LABEL:
- ggc_mark_rtx (LABEL_REFS (r));
- break;
- case LABEL_REF:
- ggc_mark_rtx (LABEL_NEXTREF (r));
- ggc_mark_rtx (CONTAINING_INSN (r));
- break;
- case ADDRESSOF:
- ggc_mark_tree (ADDRESSOF_DECL (r));
- break;
- case CONST_DOUBLE:
- ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
- break;
- case NOTE:
- switch (NOTE_LINE_NUMBER (r))
+ struct ggc_mem *l, *r;
+
+ l = x->sub[0];
+ r = x->sub[1];
+ if (!l)
+ *root = r;
+ else if (!r)
+ *root = l;
+ else if (!l->sub[1])
{
- case NOTE_INSN_RANGE_START:
- case NOTE_INSN_RANGE_END:
- case NOTE_INSN_LIVE:
- ggc_mark_rtx (NOTE_RANGE_INFO (r));
- break;
-
- default:
- if (NOTE_LINE_NUMBER (r) >= 0)
- ggc_mark_string (NOTE_SOURCE_FILE (r));
- break;
+ *root = l;
+ l->sub[1] = r;
}
- break;
-
- default:
- break;
- }
-
- for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
- {
- switch (*fmt)
+ else if (!r->sub[0])
{
- case 'e': case 'u':
- ggc_mark_rtx (XEXP (r, i));
- break;
- case 'V': case 'E':
- ggc_mark_rtvec (XVEC (r, i));
- break;
- case 'S': case 's':
- ggc_mark_string (XSTR (r, i));
- break;
+ *root = r;
+ r->sub[0] = l;
+ }
+ else
+ {
+ *root = l;
+ do {
+ root = &l->sub[1];
+ } while ((l = *root) != NULL);
+ *root = r;
}
- }
-}
-
-void
-ggc_mark_rtvec (v)
- rtvec v;
-{
- int i;
- if (v == NULL || v->gc_mark)
- return;
- v->gc_mark = 1;
+#ifdef GGC_POISON
+ memset (&x->u, 0xA5, x->size);
+#endif
- i = GET_NUM_ELEM (v);
- while (--i >= 0)
- ggc_mark_rtx (RTVEC_ELT (v, i));
+ free (x);
+ }
}
+/* The top level mark-and-sweep routine. */
+
void
-ggc_mark_tree (t)
- tree t;
+ggc_collect ()
{
- if (t == NULL_TREE || t->common.gc_mark)
- return;
- t->common.gc_mark = 1;
+ /* 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);
- /* Bits from common. */
- ggc_mark_tree (TREE_TYPE (t));
- ggc_mark_tree (TREE_CHAIN (t));
+ size_t min_expand = allocated_last_gc * PARAM_VALUE (GGC_MIN_EXPAND) / 100;
- /* Some nodes require special handling. */
- switch (TREE_CODE (t))
- {
- case TREE_LIST:
- ggc_mark_tree (TREE_PURPOSE (t));
- ggc_mark_tree (TREE_VALUE (t));
- return;
+ if (G.allocated < allocated_last_gc + min_expand)
+ return;
- case TREE_VEC:
- {
- int i = TREE_VEC_LENGTH (t);
- while (--i >= 0)
- ggc_mark_tree (TREE_VEC_ELT (t, i));
- return;
- }
-
- case SAVE_EXPR:
- ggc_mark_tree (TREE_OPERAND (t, 0));
- ggc_mark_tree (SAVE_EXPR_CONTEXT (t));
- ggc_mark_rtx (SAVE_EXPR_RTL (t));
- return;
+#ifdef GGC_BALANCE
+ debug_ggc_balance ();
+#endif
- case RTL_EXPR:
- ggc_mark_rtx (RTL_EXPR_SEQUENCE (t));
- ggc_mark_rtx (RTL_EXPR_RTL (t));
- return;
+ timevar_push (TV_GC);
+ if (!quiet_flag)
+ fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
- case CALL_EXPR:
- ggc_mark_tree (TREE_OPERAND (t, 0));
- ggc_mark_tree (TREE_OPERAND (t, 1));
- ggc_mark_rtx (CALL_EXPR_RTL (t));
- return;
+ G.allocated = 0;
+ G.objects = 0;
- case COMPLEX_CST:
- ggc_mark_tree (TREE_REALPART (t));
- ggc_mark_tree (TREE_IMAGPART (t));
- break;
+ clear_marks (G.root);
+ ggc_mark_roots ();
+ sweep_objs (&G.root);
- case STRING_CST:
- ggc_mark_string (TREE_STRING_POINTER (t));
- break;
+ G.allocated_last_gc = G.allocated;
- case PARM_DECL:
- ggc_mark_rtx (DECL_INCOMING_RTL (t));
- break;
+ timevar_pop (TV_GC);
- case IDENTIFIER_NODE:
- ggc_mark_string (IDENTIFIER_POINTER (t));
- lang_mark_tree (t);
- return;
+ if (!quiet_flag)
+ fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
- default:
- break;
- }
-
- /* But in general we can handle them by class. */
- switch (TREE_CODE_CLASS (TREE_CODE (t)))
- {
- case 'd': /* A decl node. */
- ggc_mark_tree (DECL_SIZE (t));
- ggc_mark_tree (DECL_NAME (t));
- ggc_mark_tree (DECL_CONTEXT (t));
- ggc_mark_tree (DECL_ARGUMENTS (t));
- ggc_mark_tree (DECL_RESULT (t));
- ggc_mark_tree (DECL_INITIAL (t));
- ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
- ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
- ggc_mark_tree (DECL_SECTION_NAME (t));
- ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
- ggc_mark_rtx (DECL_RTL (t));
- ggc_mark_tree (DECL_VINDEX (t));
- lang_mark_tree (t);
- break;
-
- case 't': /* A type node. */
- ggc_mark_tree (TYPE_SIZE (t));
- ggc_mark_tree (TYPE_SIZE_UNIT (t));
- ggc_mark_tree (TYPE_ATTRIBUTES (t));
- ggc_mark_tree (TYPE_VALUES (t));
- ggc_mark_tree (TYPE_POINTER_TO (t));
- ggc_mark_tree (TYPE_REFERENCE_TO (t));
- ggc_mark_tree (TYPE_NAME (t));
- ggc_mark_tree (TYPE_MIN_VALUE (t));
- ggc_mark_tree (TYPE_MAX_VALUE (t));
- ggc_mark_tree (TYPE_NEXT_VARIANT (t));
- ggc_mark_tree (TYPE_MAIN_VARIANT (t));
- ggc_mark_tree (TYPE_BINFO (t));
- ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
- ggc_mark_tree (TYPE_CONTEXT (t));
- lang_mark_tree (t);
- break;
-
- case 'b': /* A lexical block. */
- ggc_mark_tree (BLOCK_VARS (t));
- ggc_mark_tree (BLOCK_TYPE_TAGS (t));
- ggc_mark_tree (BLOCK_SUBBLOCKS (t));
- ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
- ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
- ggc_mark_rtx (BLOCK_END_NOTE (t));
- break;
-
- case 'c': /* A constant. */
- ggc_mark_rtx (TREE_CST_RTL (t));
- break;
-
- case 'r': case '<': case '1':
- case '2': case 'e': case 's': /* Expressions. */
- {
- int i = tree_code_length[TREE_CODE (t)];
- while (--i >= 0)
- ggc_mark_tree (TREE_OPERAND (t, i));
- break;
- }
-
- case 'x':
- lang_mark_tree (t);
- break;
- }
+#ifdef GGC_BALANCE
+ debug_ggc_balance ();
+#endif
}
-/* Mark all the elements of the varray V, which contains trees. */
+/* Called once to initialize the garbage collector. */
void
-ggc_mark_tree_varray (v)
- varray_type v;
+init_ggc ()
{
- int i;
-
- if (v)
- for (i = v->num_elements - 1; i >= 0; --i)
- ggc_mark_tree (VARRAY_TREE (v, i));
}
-/* Mark the hash table-entry HE. It's key field is really a tree. */
-
-static boolean
-ggc_mark_tree_hash_table_entry (he, k)
- struct hash_entry *he;
- hash_table_key k ATTRIBUTE_UNUSED;
-{
- ggc_mark_tree ((tree) he->key);
- return true;
-}
-
-/* Mark all the elements of the hash-table H, which contains trees. */
+/* Start a new GGC context. Memory allocated in previous contexts
+ will not be collected while the new context is active. */
void
-ggc_mark_tree_hash_table (ht)
- struct hash_table *ht;
+ggc_push_context ()
{
- hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
+ G.context++;
+
+ /* We only allocated 7 bits in the node for the context. This
+ should be more than enough. */
+ if (G.context >= 128)
+ abort ();
}
+/* Finish a GC context. Any uncollected memory in the new context
+ will be merged with the old context. */
+
void
-ggc_mark_string (s)
- char *s;
+ggc_pop_context ()
{
- unsigned int *magic = (unsigned int *)s - 1;
-
- if (s == NULL)
- return;
-
- if ((*magic & ~(unsigned)1) != GGC_STRING_MAGIC)
- return; /* abort? */
- *magic = GGC_STRING_MAGIC | 1;
+ G.context--;
+ if (G.root)
+ ggc_pop_context_1 (G.root, G.context);
}
-/* Mark P, allocated with ggc_alloc. */
-
-void
-ggc_mark (p)
- void *p;
+static void
+ggc_pop_context_1 (x, c)
+ struct ggc_mem *x;
+ int c;
{
- struct ggc_any *a;
- ptrdiff_t d = (&((struct ggc_any *) 0)->u.c - (char *) 0);
- a = (struct ggc_any *) (((char*) p) - d);
- a->mark = 1;
+ if (x->context > c)
+ x->context = c;
+ if (x->sub[0])
+ ggc_pop_context_1 (x->sub[0], c);
+ if (x->sub[1])
+ ggc_pop_context_1 (x->sub[1], c);
}
-/* The top level mark-and-sweep routine. */
+/* Dump a tree. */
void
-ggc_collect ()
+debug_ggc_tree (p, indent)
+ struct ggc_mem *p;
+ int indent;
{
- struct ggc_rtx *r, **rp;
- struct ggc_rtvec *v, **vp;
- struct ggc_tree *t, **tp;
- struct ggc_string *s, **sp;
- struct ggc_root *x;
- struct ggc_status *gs;
- struct ggc_any *a, **ap;
- int time, n_rtxs, n_trees, n_vecs, n_strings, n_anys;
-
-#ifndef ENABLE_CHECKING
- /* See if it's even worth our while. */
- if (ggc_chain->bytes_alloced_since_gc < 64*1024)
- return;
-#endif
-
- if (!quiet_flag)
- fputs (" {GC ", stderr);
-
- time = get_run_time ();
+ int i;
- /* Clean out all of the GC marks. */
- for (gs = ggc_chain; gs; gs = gs->next)
+ if (!p)
{
- for (r = gs->rtxs; r != NULL; r = r->chain)
- r->rtx.gc_mark = 0;
- for (v = gs->vecs; v != NULL; v = v->chain)
- v->vec.gc_mark = 0;
- for (t = gs->trees; t != NULL; t = t->chain)
- t->tree.common.gc_mark = 0;
- for (s = gs->strings; s != NULL; s = s->chain)
- s->magic_mark = GGC_STRING_MAGIC;
- for (a = gs->anys; a != NULL; a = a->chain)
- a->mark = 0;
+ fputs ("(nil)\n", stderr);
+ return;
}
- /* Mark through all the roots. */
- for (x = roots; x != NULL; x = x->next)
- {
- char *elt = x->base;
- int s = x->size, n = x->nelt;
- void (*cb) PROTO ((void *)) = x->cb;
- int i;
+ if (p->sub[0])
+ debug_ggc_tree (p->sub[0], indent + 1);
- for (i = 0; i < n; ++i, elt += s)
- (*cb)(elt);
- }
+ for (i = 0; i < indent; ++i)
+ putc (' ', stderr);
+ fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), p);
- /* Sweep the resulting dead nodes. */
+ if (p->sub[1])
+ debug_ggc_tree (p->sub[1], indent + 1);
+}
- /* The RTXs. */
+#ifdef GGC_BALANCE
+/* Collect tree balance metrics */
- rp = &ggc_chain->rtxs;
- r = ggc_chain->rtxs;
- n_rtxs = 0;
- while (r != NULL)
- {
- struct ggc_rtx *chain = r->chain;
- if (!r->rtx.gc_mark)
- {
- ggc_free_rtx (r);
- *rp = chain;
- n_rtxs++;
- }
- else
- rp = &r->chain;
- r = chain;
- }
- *rp = NULL;
- n_rtxs_collected += n_rtxs;
+#include <math.h>
- /* The vectors. */
+void
+debug_ggc_balance ()
+{
+ size_t nleaf, sumdepth;
- vp = &ggc_chain->vecs;
- v = ggc_chain->vecs;
- n_vecs = 0;
- while (v != NULL)
- {
- struct ggc_rtvec *chain = v->chain;
- if (!v->vec.gc_mark)
- {
- ggc_free_rtvec (v);
- *vp = chain;
- n_vecs++;
- }
- else
- vp = &v->chain;
- v = chain;
- }
- *vp = NULL;
- n_vecs_collected += n_vecs;
+ nleaf = sumdepth = 0;
+ tally_leaves (G.root, 0, &nleaf, &sumdepth);
- /* The trees. */
+ fprintf (stderr, " {B %.2f,%.1f,%.1f}",
+ /* In a balanced tree, leaf/node should approach 1/2. */
+ (float)nleaf / (float)G.objects,
+ /* In a balanced tree, average leaf depth should approach lg(n). */
+ (float)sumdepth / (float)nleaf,
+ log ((double) G.objects) / M_LN2);
+}
+#endif
- tp = &ggc_chain->trees;
- t = ggc_chain->trees;
- n_trees = 0;
- while (t != NULL)
+/* Used by debug_ggc_balance, and also by ggc_print_statistics. */
+static void
+tally_leaves (x, depth, nleaf, sumdepth)
+ struct ggc_mem *x;
+ int depth;
+ size_t *nleaf;
+ size_t *sumdepth;
+{
+ if (! x->sub[0] && !x->sub[1])
{
- struct ggc_tree *chain = t->chain;
- if (!t->tree.common.gc_mark)
- {
- ggc_free_tree (t);
- *tp = chain;
- n_trees++;
- }
- else
- tp = &t->chain;
- t = chain;
+ *nleaf += 1;
+ *sumdepth += depth;
}
- *tp = NULL;
- n_trees_collected += n_trees;
-
- /* The strings. */
-
- sp = &ggc_chain->strings;
- s = ggc_chain->strings;
- n_strings = 0;
- while (s != NULL)
+ else
{
- struct ggc_string *chain = s->chain;
- if (!(s->magic_mark & 1))
- {
- ggc_free_string (s);
- *sp = chain;
- n_strings++;
- }
- else
- sp = &s->chain;
- s = chain;
+ if (x->sub[0])
+ tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
+ if (x->sub[1])
+ tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
}
- *sp = NULL;
- n_strings_collected += n_strings;
-
- /* The generic data. */
+}
- ap = &ggc_chain->anys;
- a = ggc_chain->anys;
- n_anys = 0;
- while (a != NULL)
- {
- struct ggc_any *chain = a->chain;
- if (!a->mark)
- {
- free (a);
- *ap = chain;
- n_anys++;
- }
- else
- ap = &a->chain;
- a = chain;
- }
- n_anys_collected += n_anys;
+#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'))
- ggc_chain->bytes_alloced_since_gc = 0;
+/* Report on GC memory usage. */
+void
+ggc_print_statistics ()
+{
+ struct ggc_statistics stats;
+ size_t nleaf = 0, sumdepth = 0;
- time = get_run_time () - time;
- gc_time += time;
+ /* Clear the statistics. */
+ memset (&stats, 0, sizeof (stats));
- if (!quiet_flag)
- {
- time = (time + 500) / 1000;
- fprintf (stderr, "%dr,%dv,%dt,%ds,%da %d.%03d}", n_rtxs, n_vecs,
- n_trees, n_strings, n_anys, time / 1000, time % 1000);
- }
-}
+ /* Make sure collection will really occur. */
+ G.allocated_last_gc = 0;
-/* Manipulate global roots that are needed between calls to gc. */
+ /* Collect and print the statistics common across collectors. */
+ ggc_print_common_statistics (stderr, &stats);
-void
-ggc_add_root (base, nelt, size, cb)
- void *base;
- int nelt, size;
- void (*cb) PROTO ((void *));
-{
- struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof(*x));
+ /* Report on tree balancing. */
+ tally_leaves (G.root, 0, &nleaf, &sumdepth);
- x->next = roots;
- x->base = base;
- x->nelt = nelt;
- x->size = size;
- x->cb = cb;
+ fprintf (stderr, "\n\
+Total internal data (bytes)\t%ld%c\n\
+Number of leaves in tree\t%lu\n\
+Average leaf depth\t\t%.1f\n",
+ SCALE(G.objects * offsetof (struct ggc_mem, u)),
+ LABEL(G.objects * offsetof (struct ggc_mem, u)),
+ (unsigned long)nleaf, (double)sumdepth / (double)nleaf);
- roots = x;
+ /* Report overall memory usage. */
+ fprintf (stderr, "\n\
+Total objects allocated\t\t%ld\n\
+Total memory in GC arena\t%ld%c\n",
+ (unsigned long)G.objects,
+ SCALE(G.allocated), LABEL(G.allocated));
}
-
-void
-ggc_add_rtx_root (base, nelt)
- rtx *base;
- int nelt;
+\f
+struct ggc_pch_data *
+init_ggc_pch ()
{
- ggc_add_root (base, nelt, sizeof(rtx), ggc_mark_rtx_ptr);
+ sorry ("Generating PCH files is not supported when using ggc-simple.c");
+ /* It could be supported, but the code is not yet written. */
+ return NULL;
}
-void
-ggc_add_tree_root (base, nelt)
- tree *base;
- int nelt;
+void
+ggc_pch_count_object (d, x, size)
+ struct ggc_pch_data *d ATTRIBUTE_UNUSED;
+ void *x ATTRIBUTE_UNUSED;
+ size_t size ATTRIBUTE_UNUSED;
{
- ggc_add_root (base, nelt, sizeof(tree), ggc_mark_tree_ptr);
}
-
-/* Add V (a varray full of trees) to the list of GC roots. */
-
-void
-ggc_add_tree_varray_root (base, nelt)
- varray_type *base;
- int nelt;
+
+size_t
+ggc_pch_total_size (d)
+ struct ggc_pch_data *d ATTRIBUTE_UNUSED;
{
- ggc_add_root (base, nelt, sizeof (varray_type),
- ggc_mark_tree_varray_ptr);
+ return 0;
}
-/* Add HT (a hash-table where ever key is a tree) to the list of GC
- roots. */
-
void
-ggc_add_tree_hash_table_root (base, nelt)
- struct hash_table **base;
- int nelt;
+ggc_pch_this_base (d, base)
+ struct ggc_pch_data *d ATTRIBUTE_UNUSED;
+ void *base ATTRIBUTE_UNUSED;
{
- ggc_add_root (base, nelt, sizeof (struct hash_table *),
- ggc_mark_tree_hash_table_ptr);
}
-void
-ggc_del_root (base)
- void *base;
-{
- struct ggc_root *x, **p;
- p = &roots, x = roots;
- while (x)
- {
- if (x->base == base)
- {
- *p = x->next;
- free (x);
- return;
- }
- p = &x->next;
- x = x->next;
- }
-
- abort();
-}
-
-static void
-ggc_mark_rtx_ptr (elt)
- void *elt;
+char *
+ggc_pch_alloc_object (d, x, size)
+ struct ggc_pch_data *d ATTRIBUTE_UNUSED;
+ void *x ATTRIBUTE_UNUSED;
+ size_t size ATTRIBUTE_UNUSED;
{
- ggc_mark_rtx (*(rtx *)elt);
+ return NULL;
}
-static void
-ggc_mark_tree_ptr (elt)
- void *elt;
+void
+ggc_pch_prepare_write (d, f)
+ struct ggc_pch_data * d ATTRIBUTE_UNUSED;
+ FILE * f ATTRIBUTE_UNUSED;
{
- ggc_mark_tree (*(tree *)elt);
}
-/* Type-correct function to pass to ggc_add_root. It just forwards
- ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
-
-static void
-ggc_mark_tree_varray_ptr (elt)
- void *elt;
+void
+ggc_pch_write_object (d, f, x, newx, size)
+ struct ggc_pch_data * d ATTRIBUTE_UNUSED;
+ FILE *f ATTRIBUTE_UNUSED;
+ void *x ATTRIBUTE_UNUSED;
+ void *newx ATTRIBUTE_UNUSED;
+ size_t size ATTRIBUTE_UNUSED;
{
- ggc_mark_tree_varray (*(varray_type *)elt);
}
-/* Type-correct function to pass to ggc_add_root. It just forwards
- ELT (which is really a struct hash_table **) to
- ggc_mark_tree_hash_table. */
-
-static void
-ggc_mark_tree_hash_table_ptr (elt)
- void *elt;
+void
+ggc_pch_finish (d, f)
+ struct ggc_pch_data * d ATTRIBUTE_UNUSED;
+ FILE *f ATTRIBUTE_UNUSED;
{
- ggc_mark_tree_hash_table (*(struct hash_table **) elt);
}
-#if 0
-/* GDB really should have a memory search function. Since this is just
- for initial debugging, I won't even pretend to get the __data_start
- to work on any but alpha-dec-linux-gnu. */
-static void **
-search_data(void **start, void *target)
+void
+ggc_pch_read (f, addr)
+ FILE *f ATTRIBUTE_UNUSED;
+ void *addr ATTRIBUTE_UNUSED;
{
- extern void *__data_start[];
- void **_end = (void **)sbrk(0);
-
- if (start == NULL)
- start = __data_start;
- while (start < _end)
- {
- if (*start == target)
- return start;
- start++;
- }
- return NULL;
+ /* This should be impossible, since we won't generate any valid PCH
+ files for this configuration. */
+ abort ();
}
-#endif