/* Simple garbage collection for the GNU compiler.
- Copyright (C) 1998 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001 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 "rtl.h"
#include "tree.h"
-#include "ggc.h"
+#include "tm_p.h"
#include "flags.h"
#include "varray.h"
+#include "ggc.h"
+#include "timevar.h"
/* Debugging flags. */
-#undef GGC_DUMP
+
+/* Zap memory before freeing to catch dangling pointers. */
#define GGC_POISON
-/* Global lists of roots, rtxs, and trees. */
+/* Collect statistics on how bushy the search tree is. */
+#undef GGC_BALANCE
-struct ggc_root
-{
- struct ggc_root *next;
- void *base;
- int nelt;
- int size;
- void (*cb) PROTO ((void *));
-};
+/* Perform collection every time ggc_collect is invoked. Otherwise,
+ collection is performed only when a significant amount of memory
+ has been allocated since the last collection. */
+#undef GGC_ALWAYS_COLLECT
-static struct ggc_root *roots;
+/* Always verify that the to-be-marked memory is collectable. */
+#undef GGC_ALWAYS_VERIFY
-struct ggc_rtx
-{
- struct ggc_rtx *chain;
- struct rtx_def rtx;
-};
+#ifdef ENABLE_GC_CHECKING
+#define GGC_POISON
+#define GGC_ALWAYS_VERIFY
+#endif
+#ifdef ENABLE_GC_ALWAYS_COLLECT
+#define GGC_ALWAYS_COLLECT
+#endif
-static struct ggc_rtx *rtxs;
+#ifndef HOST_BITS_PER_PTR
+#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG
+#endif
-struct ggc_rtvec
-{
- struct ggc_rtvec *chain;
- struct rtvec_def vec;
-};
+/* 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.
-static struct ggc_rtvec *vecs;
+ 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. */
-static struct ggc_tree *trees;
+#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)
-struct ggc_string
+/* GC'able memory; a node in a binary search tree. */
+
+struct ggc_mem
{
- struct ggc_string *chain;
- int magic_mark;
- char string[1];
+ /* 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 {
+ HOST_WIDEST_INT i;
+#ifdef HAVE_LONG_DOUBLE
+ long double d;
+#else
+ double d;
+#endif
+ } u;
};
-#define GGC_STRING_MAGIC ((unsigned int)0xa1b2c3d4)
+static struct globals
+{
+ /* Root of the object tree. */
+ struct ggc_mem *root;
-static struct ggc_string *strings;
+ /* 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 bytes_alloced_since_gc;
-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. */
+/* Skip garbage collection if the current allocation is not at least
+ this factor times the allocation at the end of the last collection.
+ In other words, total allocation must expand by (this factor minus
+ one) before collection is performed. */
+#define GGC_MIN_EXPAND_FOR_GC (1.3)
-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));
+/* Bound `allocated_last_gc' to 4MB, to prevent the memory expansion
+ test from triggering too often when the heap is small. */
+#define GGC_MIN_LAST_ALLOCATED (4 * 1024 * 1024)
-/* 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. */
+/* Local function prototypes. */
-rtx
-ggc_alloc_rtx (nslots)
- int nslots;
-{
- struct ggc_rtx *n;
- int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
+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));
- n = (struct ggc_rtx *) xmalloc (size);
- bzero ((char *) n, size);
- n->chain = rtxs;
- rtxs = n;
+/* For use from debugger. */
+extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int));
-#ifdef GGC_DUMP
- fprintf (dump, "alloc rtx %p\n", &n->rtx);
+#ifdef GGC_BALANCE
+extern void debug_ggc_balance PARAMS ((void));
#endif
+static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *));
- bytes_alloced_since_gc += size;
-
- return &n->rtx;
-}
+/* Insert V into the search tree. */
-rtvec
-ggc_alloc_rtvec (nelt)
- int nelt;
+static inline void
+tree_insert (v)
+ struct ggc_mem *v;
{
- struct ggc_rtvec *v;
- int size = sizeof (*v) + (nelt - 1) * sizeof (rtunion);
+ size_t v_key = PTR_KEY (v);
+ struct ggc_mem *p, **pp;
- v = (struct ggc_rtvec *) xmalloc (size);
- bzero ((char *) v, size);
- v->chain = vecs;
- vecs = v;
-
-#ifdef GGC_DUMP
- fprintf(dump, "alloc vec %p\n", &v->vec);
-#endif
-
- bytes_alloced_since_gc += size;
-
- return &v->vec;
+ for (pp = &G.root, p = *pp; p ; p = *pp)
+ {
+ size_t p_key = PTR_KEY (p);
+ pp = &p->sub[v_key < p_key];
+ }
+ *pp = v;
}
-tree
-ggc_alloc_tree (length)
- int length;
-{
- struct ggc_tree *n;
- int size = sizeof(*n) - sizeof(n->tree) + length;
-
- n = (struct ggc_tree *) xmalloc (size);
- bzero ((char *) n, size);
- n->chain = trees;
- trees = n;
-
-#ifdef GGC_DUMP
- fprintf(dump, "alloc tree %p\n", &n->tree);
-#endif
-
- bytes_alloced_since_gc += size;
+/* Return true if V is in the tree. */
- return &n->tree;
-}
-
-char *
-ggc_alloc_string (contents, length)
- const char *contents;
- int length;
+static inline int
+tree_lookup (v)
+ struct ggc_mem *v;
{
- struct ggc_string *s;
- int size;
+ size_t v_key = PTR_KEY (v);
+ struct ggc_mem *p = G.root;
- if (length < 0)
+ while (p)
{
- if (contents == NULL)
- return NULL;
- length = strlen (contents);
+ size_t p_key = PTR_KEY (p);
+ if (p == v)
+ return 1;
+ p = p->sub[v_key < p_key];
}
- size = (s->string - (char *)s) + length + 1;
- s = (struct ggc_string *) xmalloc(size);
- s->chain = strings;
- s->magic_mark = GGC_STRING_MAGIC;
- if (contents)
- bcopy (contents, s->string, length);
- s->string[length] = 0;
- strings = s;
-
-#ifdef GGC_DUMP
- fprintf(dump, "alloc string %p\n", &n->tree);
-#endif
-
- bytes_alloced_since_gc += size;
-
- return s->string;
+ return 0;
}
+/* Alloc SIZE bytes of GC'able memory. If ZERO, clear the memory. */
-/* Freeing a bit of rtl isn't quite as simple as calling free, there are
- a few associated bits that might need freeing as well. */
-
-static void
-ggc_free_rtx (r)
- struct ggc_rtx *r;
+void *
+ggc_alloc (size)
+ size_t size;
{
-#ifdef GGC_DUMP
- fprintf (dump, "collect rtx %p\n", &r->rtx);
-#endif
-#ifdef GGC_POISON
- memset (r, 0xAA, sizeof(*r));
-#endif
-
- free (r);
-}
+ struct ggc_mem *x;
-/* Freeing an rtvec is as simple as calling free. */
+ 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;
-static void
-ggc_free_rtvec (v)
- struct ggc_rtvec *v;
-{
-#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)));
+ memset (&x->u, 0xaf, size);
#endif
- free (v);
+ tree_insert (x);
+ G.allocated += size;
+ G.objects += 1;
+
+ return &x->u;
}
-/* 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. */
+/* Mark a node. */
-static void
-ggc_free_tree (t)
- struct ggc_tree *t;
+int
+ggc_set_mark (p)
+ const void *p;
{
- switch (TREE_CODE_CLASS (TREE_CODE (&t->tree)))
- {
- case 'd': /* A decl node. */
- case 't': /* A type node. */
- lang_cleanup_tree (&t->tree);
- break;
- }
+ struct ggc_mem *x;
-#ifdef GGC_DUMP
- fprintf (dump, "collect tree %p\n", &t->tree);
-#endif
-#ifdef GGC_POISON
- memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
+ x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+#ifdef GGC_ALWAYS_VERIFY
+ if (! tree_lookup (x))
+ abort ();
#endif
- free (t);
-}
+ if (x->mark)
+ return 1;
-/* Freeing a string is as simple as calling free. */
+ x->mark = 1;
+ G.allocated += x->size;
+ G.objects += 1;
-static void
-ggc_free_string (s)
- struct ggc_string *s;
-{
-#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);
+ return 0;
}
-/* Mark a node. */
+/* Return 1 if P has been marked, zero otherwise. */
-void
-ggc_mark_rtx (r)
- rtx r;
+int
+ggc_marked_p (p)
+ const void *p;
{
- const char *fmt;
- int i;
-
- if (r == NULL_RTX || r->gc_mark)
- return;
- r->gc_mark = 1;
+ struct ggc_mem *x;
- /* ??? If (some of) these are really pass-dependant info, do we have
- any right poking our noses in? */
- switch (GET_CODE (r))
- {
- 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;
-
- default:
- break;
- }
+ x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+#ifdef GGC_ALWAYS_VERIFY
+ if (! tree_lookup (x))
+ abort ();
+#endif
- for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
- {
- switch (*fmt)
- {
- 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;
- }
- }
+ return x->mark;
}
-void
-ggc_mark_rtvec (v)
- rtvec v;
+/* Return the size of the gc-able object P. */
+
+size_t
+ggc_get_size (p)
+ const void *p;
{
- int i;
+ struct ggc_mem *x
+ = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u));
+ return x->size;
+}
- if (v == NULL || v->gc_mark)
- return;
- v->gc_mark = 1;
+/* Unmark all objects. */
- i = GET_NUM_ELEM (v);
- while (--i >= 0)
- ggc_mark_rtx (RTVEC_ELT (v, i));
+static void
+clear_marks (x)
+ struct ggc_mem *x;
+{
+ x->mark = 0;
+ if (x->sub[0])
+ clear_marks (x->sub[0]);
+ if (x->sub[1])
+ clear_marks (x->sub[1]);
}
-void
-ggc_mark_tree (t)
- tree t;
+/* Free all objects in the current context that are not marked. */
+
+static void
+sweep_objs (root)
+ struct ggc_mem **root;
{
- if (t == NULL_TREE || t->common.gc_mark)
+ struct ggc_mem *x = *root;
+ if (!x)
return;
- t->common.gc_mark = 1;
- /* Bits from common. */
- ggc_mark_tree (TREE_TYPE (t));
- ggc_mark_tree (TREE_CHAIN (t));
+ sweep_objs (&x->sub[0]);
+ sweep_objs (&x->sub[1]);
- /* Some nodes require special handling. */
- switch (TREE_CODE (t))
+ if (! x->mark && x->context >= G.context)
{
- case TREE_LIST:
- ggc_mark_tree (TREE_PURPOSE (t));
- ggc_mark_tree (TREE_VALUE (t));
- 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;
-
- case RTL_EXPR:
- ggc_mark_rtx (RTL_EXPR_SEQUENCE (t));
- ggc_mark_rtx (RTL_EXPR_RTL (t));
- return;
-
- 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;
-
- case COMPLEX_CST:
- ggc_mark_tree (TREE_REALPART (t));
- ggc_mark_tree (TREE_IMAGPART (t));
- break;
-
- case STRING_CST:
- ggc_mark_string (TREE_STRING_POINTER (t));
- break;
-
- case PARM_DECL:
- ggc_mark_rtx (DECL_INCOMING_RTL (t));
- break;
+ 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])
+ {
+ *root = l;
+ l->sub[1] = r;
+ }
+ else if (!r->sub[0])
+ {
+ *root = r;
+ r->sub[0] = l;
+ }
+ else
+ {
+ *root = l;
+ do {
+ root = &l->sub[1];
+ } while ((l = *root) != NULL);
+ *root = r;
+ }
- case IDENTIFIER_NODE:
- ggc_mark_string (IDENTIFIER_POINTER (t));
- lang_mark_tree (t);
- return;
+#ifdef GGC_POISON
+ memset (&x->u, 0xA5, x->size);
+#endif
- 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;
- }
+ free (x);
}
}
-/* Mark all the elements of the varray V, which contains trees. */
-
-void
-ggc_mark_tree_varray (v)
- varray_type v;
-{
- int i;
-
- for (i = v->num_elements - 1; i >= 0; --i)
- ggc_mark_tree (VARRAY_TREE (v, i));
-}
-
-void
-ggc_mark_string (s)
- char *s;
-{
- 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;
-}
-
/* The top level mark-and-sweep routine. */
void
ggc_collect ()
{
- struct ggc_rtx *r, **rp;
- struct ggc_rtvec *v, **vp;
- struct ggc_tree *t, **tp;
- struct ggc_string *s, **sp;
- struct ggc_root *x;
- int time, n_rtxs, n_trees, n_vecs, n_strings;
-
-#ifndef ENABLE_CHECKING
- /* See if it's even worth our while. */
- if (bytes_alloced_since_gc < 64*1024)
+#ifndef GGC_ALWAYS_COLLECT
+ if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc)
return;
#endif
- if (!quiet_flag)
- fputs (" {GC ", stderr);
-
- time = get_run_time ();
-
- /* Clean out all of the GC marks. */
- for (r = rtxs; r != NULL; r = r->chain)
- r->rtx.gc_mark = 0;
- for (v = vecs; v != NULL; v = v->chain)
- v->vec.gc_mark = 0;
- for (t = trees; t != NULL; t = t->chain)
- t->tree.common.gc_mark = 0;
- for (s = strings; s != NULL; s = s->chain)
- s->magic_mark = GGC_STRING_MAGIC;
-
- /* 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;
-
- for (i = 0; i < n; ++i, elt += s)
- (*cb)(elt);
- }
+#ifdef GGC_BALANCE
+ debug_ggc_balance ();
+#endif
- /* Sweep the resulting dead nodes. */
- rp = &rtxs, r = 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;
+ timevar_push (TV_GC);
+ if (!quiet_flag)
+ fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024);
- vp = &vecs, v = 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;
+ G.allocated = 0;
+ G.objects = 0;
- tp = &trees, t = trees, n_trees = 0;
- while (t != NULL)
- {
- 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;
- }
- *tp = NULL;
- n_trees_collected += n_trees;
+ clear_marks (G.root);
+ ggc_mark_roots ();
+ sweep_objs (&G.root);
- sp = &strings, s = strings, n_strings = 0;
- while (s != NULL)
- {
- 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;
- }
- *sp = NULL;
- n_strings_collected += n_strings;
+ G.allocated_last_gc = G.allocated;
+ if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED)
+ G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
- gc_time += time = get_run_time () - time;
+ timevar_pop (TV_GC);
if (!quiet_flag)
- {
- time = (time + 500) / 1000;
- fprintf (stderr, "%d,%d,%d,%d %d.%03d}", n_rtxs, n_vecs, n_trees,
- n_strings, time / 1000, time % 1000);
- }
+ fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024);
+
+#ifdef GGC_BALANCE
+ debug_ggc_balance ();
+#endif
}
-/* Manipulate global roots that are needed between calls to gc. */
+/* Called once to initialize the garbage collector. */
-void
-ggc_add_root (base, nelt, size, cb)
- void *base;
- int nelt, size;
- void (*cb) PROTO ((void *));
+void
+init_ggc ()
{
- struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof(*x));
-
- x->next = roots;
- x->base = base;
- x->nelt = nelt;
- x->size = size;
- x->cb = cb;
-
- roots = x;
+ G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED;
}
+/* Start a new GGC context. Memory allocated in previous contexts
+ will not be collected while the new context is active. */
+
void
-ggc_add_rtx_root (base, nelt)
- rtx *base;
- int nelt;
+ggc_push_context ()
{
- ggc_add_root (base, nelt, sizeof(rtx), ggc_mark_rtx_ptr);
+ G.context++;
+
+ /* We only allocated 7 bits in the node for the context. This
+ should be more than enough. */
+ if (G.context >= 128)
+ abort ();
}
-void
-ggc_add_tree_root (base, nelt)
- tree *base;
- int nelt;
+/* Finish a GC context. Any uncollected memory in the new context
+ will be merged with the old context. */
+
+void
+ggc_pop_context ()
{
- ggc_add_root (base, nelt, sizeof(tree), ggc_mark_tree_ptr);
+ G.context--;
+ if (G.root)
+ ggc_pop_context_1 (G.root, G.context);
}
-/* Add vV (a varray full of trees) to the list of GC roots. */
-
-void
-ggc_add_tree_varray_root (base, nelt)
- varray_type *base;
- int nelt;
+static void
+ggc_pop_context_1 (x, c)
+ struct ggc_mem *x;
+ int c;
{
- ggc_add_root (base, nelt, sizeof (varray_type),
- ggc_mark_tree_varray_ptr);
+ 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);
}
+/* Dump a tree. */
+
void
-ggc_del_root (base)
- void *base;
+debug_ggc_tree (p, indent)
+ struct ggc_mem *p;
+ int indent;
{
- struct ggc_root *x, **p;
+ int i;
- p = &roots, x = roots;
- while (x)
+ if (!p)
{
- if (x->base == base)
- {
- *p = x->next;
- free (x);
- return;
- }
- p = &x->next;
- x = x->next;
+ fputs ("(nil)\n", stderr);
+ return;
}
- abort();
-}
+ if (p->sub[0])
+ debug_ggc_tree (p->sub[0], indent + 1);
-static void
-ggc_mark_rtx_ptr (elt)
- void *elt;
-{
- ggc_mark_rtx (*(rtx *)elt);
+ for (i = 0; i < indent; ++i)
+ putc (' ', stderr);
+ fprintf (stderr, "%lx %p\n", (unsigned long)PTR_KEY (p), p);
+
+ if (p->sub[1])
+ debug_ggc_tree (p->sub[1], indent + 1);
}
-static void
-ggc_mark_tree_ptr (elt)
- void *elt;
-{
- ggc_mark_tree (*(tree *)elt);
-}
+#ifdef GGC_BALANCE
+/* Collect tree balance metrics */
-/* Type-correct function to pass to ggc_add_root. It just forwards
- ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
+#include <math.h>
-static void
-ggc_mark_tree_varray_ptr (elt)
- void *elt;
+void
+debug_ggc_balance ()
{
- ggc_mark_tree_varray (*(varray_type *)elt);
-}
+ size_t nleaf, sumdepth;
-#ifdef GGC_DUMP
-/* Don't enable this unless you want a really really lot of data. */
-static void __attribute__((constructor))
-init(void)
-{
- dump = fopen ("zgcdump", "w");
- setlinebuf (dump);
+ nleaf = sumdepth = 0;
+ tally_leaves (G.root, 0, &nleaf, &sumdepth);
+
+ 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
-#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)
+/* 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;
{
- extern void *__data_start[];
- void **_end = (void **)sbrk(0);
-
- if (start == NULL)
- start = __data_start;
- while (start < _end)
+ if (! x->sub[0] && !x->sub[1])
+ {
+ *nleaf += 1;
+ *sumdepth += depth;
+ }
+ else
{
- if (*start == target)
- return start;
- start++;
+ 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);
}
- return NULL;
}
-#endif
+
+#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'))
+
+/* Report on GC memory usage. */
+void
+ggc_print_statistics ()
+{
+ struct ggc_statistics stats;
+ size_t nleaf = 0, sumdepth = 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);
+
+ /* Report on tree balancing. */
+ tally_leaves (G.root, 0, &nleaf, &sumdepth);
+
+ fprintf (stderr, "\n\
+Total internal data (bytes)\t%ld%c\n\
+Number of leaves in tree\t%d\n\
+Average leaf depth\t\t%.1f\n",
+ SCALE(G.objects * offsetof (struct ggc_mem, u)),
+ LABEL(G.objects * offsetof (struct ggc_mem, u)),
+ nleaf, (double)sumdepth / (double)nleaf);
+
+ /* Report overall memory usage. */
+ fprintf (stderr, "\n\
+Total objects allocated\t\t%d\n\
+Total memory in GC arena\t%ld%c\n",
+ G.objects,
+ SCALE(G.allocated), LABEL(G.allocated));
+}