X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fggc-simple.c;fp=gcc%2Fggc-simple.c;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=81d2c36fc6d0e7d2084abf7727e18fce9494129a;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/ggc-simple.c b/gcc/ggc-simple.c deleted file mode 100644 index 81d2c36f..00000000 --- a/gcc/ggc-simple.c +++ /dev/null @@ -1,517 +0,0 @@ -/* Simple garbage collection for the GNU compiler. - Copyright (C) 1998, 1999, 2000, 2001 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 "rtl.h" -#include "tree.h" -#include "tm_p.h" -#include "flags.h" -#include "varray.h" -#include "ggc.h" -#include "timevar.h" - -/* Debugging flags. */ - -/* Zap memory before freeing to catch dangling pointers. */ -#define GGC_POISON - -/* Collect statistics on how bushy the search tree is. */ -#undef GGC_BALANCE - -/* 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 - -/* Always verify that the to-be-marked memory is collectable. */ -#undef GGC_ALWAYS_VERIFY - -#ifdef ENABLE_GC_CHECKING -#define GGC_POISON -#define GGC_ALWAYS_VERIFY -#endif -#ifdef ENABLE_GC_ALWAYS_COLLECT -#define GGC_ALWAYS_COLLECT -#endif - -#ifndef HOST_BITS_PER_PTR -#define HOST_BITS_PER_PTR HOST_BITS_PER_LONG -#endif - -/* 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. - - 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. - - 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. */ - -#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) - -/* GC'able memory; a node in a binary search tree. */ - -struct ggc_mem -{ - /* 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; -}; - -static struct globals -{ - /* Root of the object tree. */ - struct ggc_mem *root; - - /* 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; - -/* 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) - -/* 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) - -/* Local function prototypes. */ - -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)); - -/* For use from debugger. */ -extern void debug_ggc_tree PARAMS ((struct ggc_mem *, int)); - -#ifdef GGC_BALANCE -extern void debug_ggc_balance PARAMS ((void)); -#endif -static void tally_leaves PARAMS ((struct ggc_mem *, int, size_t *, size_t *)); - -/* Insert V into the search tree. */ - -static inline void -tree_insert (v) - struct ggc_mem *v; -{ - size_t v_key = PTR_KEY (v); - struct ggc_mem *p, **pp; - - 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; -} - -/* Return true if V is in the tree. */ - -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) - { - size_t p_key = PTR_KEY (p); - if (p == v) - return 1; - p = p->sub[v_key < p_key]; - } - - return 0; -} - -/* Alloc SIZE bytes of GC'able memory. If ZERO, clear the memory. */ - -void * -ggc_alloc (size) - size_t size; -{ - struct ggc_mem *x; - - 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_POISON - memset (&x->u, 0xaf, size); -#endif - - tree_insert (x); - G.allocated += size; - G.objects += 1; - - return &x->u; -} - -/* Mark a node. */ - -int -ggc_set_mark (p) - const void *p; -{ - struct ggc_mem *x; - - x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u)); -#ifdef GGC_ALWAYS_VERIFY - if (! tree_lookup (x)) - abort (); -#endif - - if (x->mark) - return 1; - - x->mark = 1; - G.allocated += x->size; - G.objects += 1; - - return 0; -} - -/* Return 1 if P has been marked, zero otherwise. */ - -int -ggc_marked_p (p) - const void *p; -{ - struct ggc_mem *x; - - x = (struct ggc_mem *) ((const char *)p - offsetof (struct ggc_mem, u)); -#ifdef GGC_ALWAYS_VERIFY - if (! tree_lookup (x)) - abort (); -#endif - - return x->mark; -} - -/* 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; -} - -/* Unmark all objects. */ - -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]); -} - -/* Free all objects in the current context that are not marked. */ - -static void -sweep_objs (root) - struct ggc_mem **root; -{ - struct ggc_mem *x = *root; - if (!x) - return; - - sweep_objs (&x->sub[0]); - sweep_objs (&x->sub[1]); - - if (! x->mark && x->context >= G.context) - { - 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; - } - -#ifdef GGC_POISON - memset (&x->u, 0xA5, x->size); -#endif - - free (x); - } -} - -/* The top level mark-and-sweep routine. */ - -void -ggc_collect () -{ -#ifndef GGC_ALWAYS_COLLECT - if (G.allocated < GGC_MIN_EXPAND_FOR_GC * G.allocated_last_gc) - return; -#endif - -#ifdef GGC_BALANCE - debug_ggc_balance (); -#endif - - timevar_push (TV_GC); - if (!quiet_flag) - fprintf (stderr, " {GC %luk -> ", (unsigned long)G.allocated / 1024); - - G.allocated = 0; - G.objects = 0; - - clear_marks (G.root); - ggc_mark_roots (); - sweep_objs (&G.root); - - G.allocated_last_gc = G.allocated; - if (G.allocated_last_gc < GGC_MIN_LAST_ALLOCATED) - G.allocated_last_gc = GGC_MIN_LAST_ALLOCATED; - - timevar_pop (TV_GC); - - if (!quiet_flag) - fprintf (stderr, "%luk}", (unsigned long) G.allocated / 1024); - -#ifdef GGC_BALANCE - debug_ggc_balance (); -#endif -} - -/* Called once to initialize the garbage collector. */ - -void -init_ggc () -{ - 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_push_context () -{ - 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_pop_context () -{ - G.context--; - if (G.root) - ggc_pop_context_1 (G.root, G.context); -} - -static void -ggc_pop_context_1 (x, c) - struct ggc_mem *x; - int c; -{ - 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 -debug_ggc_tree (p, indent) - struct ggc_mem *p; - int indent; -{ - int i; - - if (!p) - { - fputs ("(nil)\n", stderr); - return; - } - - if (p->sub[0]) - debug_ggc_tree (p->sub[0], indent + 1); - - 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); -} - -#ifdef GGC_BALANCE -/* Collect tree balance metrics */ - -#include - -void -debug_ggc_balance () -{ - size_t nleaf, sumdepth; - - 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 - -/* 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]) - { - *nleaf += 1; - *sumdepth += depth; - } - else - { - 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); - } -} - -#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)); -}