gcc/ggc-common.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* Generic garbage collection (GC) functions and data, not specific to
  22    any particular GC implementation.  */
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "rtl.h"
  27 #include "tree.h"
  28 #include "tm_p.h"
  29 #include "hashtab.h"
  30 #include "varray.h"
  31 #include "ggc.h"
  32 #include "langhooks.h"
  33
  34 /* Statistics about the allocation.  */
  35 static ggc_statistics *ggc_stats;
  36
  37 static void ggc_mark_rtx_children_1 PARAMS ((rtx));
  38 static int ggc_htab_delete PARAMS ((void **, void *));
  39
  40 /* Maintain global roots that are preserved during GC.  */
  41
  42 /* Global roots that are preserved during calls to gc.  */
  43
  44 struct ggc_root
  45 {
  46   struct ggc_root *next;
  47   void *base;
  48   int nelt;
  49   int size;
  50   void (*cb) PARAMS ((void *));
  51 };
  52
  53 static struct ggc_root *roots;
  54
  55 /* Add BASE as a new garbage collection root.  It is an array of
  56    length NELT with each element SIZE bytes long.  CB is a
  57    function that will be called with a pointer to each element
  58    of the array; it is the intention that CB call the appropriate
  59    routine to mark gc-able memory for that element.  */
  60
  61 void
  62 ggc_add_root (base, nelt, size, cb)
  63      void *base;
  64      int nelt, size;
  65      void (*cb) PARAMS ((void *));
  66 {
  67   struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof (*x));
  68
  69   x->next = roots;
  70   x->base = base;
  71   x->nelt = nelt;
  72   x->size = size;
  73   x->cb = cb;
  74
  75   roots = x;
  76 }
  77
  78 /* Process a slot of an htab by deleting it if it has not been marked.  */
  79
  80 static int
  81 ggc_htab_delete (slot, info)
  82      void **slot;
  83      void *info;
  84 {
  85   const struct ggc_cache_tab *r = (const struct ggc_cache_tab *) info;
  86
  87   if (! (*r->marked_p) (*slot))
  88     htab_clear_slot (*r->base, slot);
  89   else
  90     (*r->cb) (*slot);
  91
  92   return 1;
  93 }
  94
  95 /* Iterate through all registered roots and mark each element.  */
  96
  97 void
  98 ggc_mark_roots ()
  99 {
 100   struct ggc_root *x;
 101   const struct ggc_root_tab *const *rt;
 102   const struct ggc_root_tab *rti;
 103   const struct ggc_cache_tab *const *ct;
 104   const struct ggc_cache_tab *cti;
 105   size_t i;
 106
 107   for (rt = gt_ggc_deletable_rtab; *rt; rt++)
 108     for (rti = *rt; rti->base != NULL; rti++)
 109       memset (rti->base, 0, rti->stride);
 110
 111   for (rt = gt_ggc_rtab; *rt; rt++)
 112     for (rti = *rt; rti->base != NULL; rti++)
 113       for (i = 0; i < rti->nelt; i++)
 114         (*rti->cb)(*(void **)((char *)rti->base + rti->stride * i));
 115
 116   for (x = roots; x != NULL; x = x->next)
 117     {
 118       char *elt = x->base;
 119       int s = x->size, n = x->nelt;
 120       void (*cb) PARAMS ((void *)) = x->cb;
 121       int i;
 122
 123       for (i = 0; i < n; ++i, elt += s)
 124         (*cb)(elt);
 125     }
 126
 127   /* Now scan all hash tables that have objects which are to be deleted if
 128      they are not already marked.  */
 129   for (ct = gt_ggc_cache_rtab; *ct; ct++)
 130     for (cti = *ct; cti->base != NULL; cti++)
 131       htab_traverse (*cti->base, ggc_htab_delete, (PTR) cti);
 132 }
 133
 134 /* R had not been previously marked, but has now been marked via
 135    ggc_set_mark.  Now recurse and process the children.  */
 136
 137 void
 138 ggc_mark_rtx_children (r)
 139      rtx r;
 140 {
 141   rtx i, last;
 142
 143   /* Special case the instruction chain.  This is a data structure whose
 144      chain length is potentially unbounded, and which contain references
 145      within the chain (e.g. label_ref and insn_list).  If do nothing here,
 146      we risk blowing the stack recursing through a long chain of insns.
 147
 148      Combat this by marking all of the instructions in the chain before
 149      marking the contents of those instructions.  */
 150
 151   switch (GET_CODE (r))
 152     {
 153     case INSN:
 154     case JUMP_INSN:
 155     case CALL_INSN:
 156     case NOTE:
 157     case CODE_LABEL:
 158     case BARRIER:
 159       for (i = NEXT_INSN (r); ; i = NEXT_INSN (i))
 160         if (! ggc_test_and_set_mark (i))
 161           break;
 162       last = i;
 163
 164       for (i = NEXT_INSN (r); i != last; i = NEXT_INSN (i))
 165         ggc_mark_rtx_children_1 (i);
 166
 167     default:
 168       break;
 169     }
 170
 171   ggc_mark_rtx_children_1 (r);
 172 }
 173
 174 static void
 175 ggc_mark_rtx_children_1 (r)
 176      rtx r;
 177 {
 178   const char *fmt;
 179   int i;
 180   rtx next_rtx;
 181
 182   do
 183     {
 184       enum rtx_code code = GET_CODE (r);
 185       /* This gets set to a child rtx to eliminate tail recursion.  */
 186       next_rtx = NULL;
 187
 188       /* Collect statistics, if appropriate.  */
 189       if (ggc_stats)
 190         {
 191           ++ggc_stats->num_rtxs[(int) code];
 192           ggc_stats->size_rtxs[(int) code] += ggc_get_size (r);
 193         }
 194
 195       /* ??? If (some of) these are really pass-dependent info, do we
 196          have any right poking our noses in?  */
 197       switch (code)
 198         {
 199         case MEM:
 200           gt_ggc_m_mem_attrs (MEM_ATTRS (r));
 201           break;
 202         case JUMP_INSN:
 203           ggc_mark_rtx (JUMP_LABEL (r));
 204           break;
 205         case CODE_LABEL:
 206           ggc_mark_rtx (LABEL_REFS (r));
 207           break;
 208         case LABEL_REF:
 209           ggc_mark_rtx (LABEL_NEXTREF (r));
 210           ggc_mark_rtx (CONTAINING_INSN (r));
 211           break;
 212         case ADDRESSOF:
 213           ggc_mark_tree (ADDRESSOF_DECL (r));
 214           break;
 215         case NOTE:
 216           switch (NOTE_LINE_NUMBER (r))
 217             {
 218             case NOTE_INSN_RANGE_BEG:
 219             case NOTE_INSN_RANGE_END:
 220             case NOTE_INSN_LIVE:
 221             case NOTE_INSN_EXPECTED_VALUE:
 222               ggc_mark_rtx (NOTE_RANGE_INFO (r));
 223               break;
 224
 225             case NOTE_INSN_BLOCK_BEG:
 226             case NOTE_INSN_BLOCK_END:
 227               ggc_mark_tree (NOTE_BLOCK (r));
 228               break;
 229
 230             default:
 231               break;
 232             }
 233           break;
 234
 235         default:
 236           break;
 237         }
 238
 239       for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
 240         {
 241           rtx exp;
 242           switch (*fmt)
 243             {
 244             case 'e': case 'u':
 245               exp = XEXP (r, i);
 246               if (ggc_test_and_set_mark (exp))
 247                 {
 248                   if (next_rtx == NULL)
 249                     next_rtx = exp;
 250                   else
 251                     ggc_mark_rtx_children (exp);
 252                 }
 253               break;
 254             case 'V': case 'E':
 255               gt_ggc_m_rtvec_def (XVEC (r, i));
 256               break;
 257             }
 258         }
 259     }
 260   while ((r = next_rtx) != NULL);
 261 }
 262
 263 /* Various adaptor functions.  */
 264 void
 265 gt_ggc_mx_rtx_def (x)
 266      void *x;
 267 {
 268   ggc_mark_rtx((rtx)x);
 269 }
 270
 271 /* Allocate a block of memory, then clear it.  */
 272 void *
 273 ggc_alloc_cleared (size)
 274      size_t size;
 275 {
 276   void *buf = ggc_alloc (size);
 277   memset (buf, 0, size);
 278   return buf;
 279 }
 280
 281 /* Resize a block of memory, possibly re-allocating it.  */
 282 void *
 283 ggc_realloc (x, size)
 284      void *x;
 285      size_t size;
 286 {
 287   void *r;
 288   size_t old_size;
 289
 290   if (x == NULL)
 291     return ggc_alloc (size);
 292
 293   old_size = ggc_get_size (x);
 294   if (size <= old_size)
 295     return x;
 296
 297   r = ggc_alloc (size);
 298   memcpy (r, x, old_size);
 299   return r;
 300 }
 301
 302 /* Like ggc_alloc_cleared, but performs a multiplication.  */
 303 void *
 304 ggc_calloc (s1, s2)
 305      size_t s1, s2;
 306 {
 307   return ggc_alloc_cleared (s1 * s2);
 308 }
 309
 310 /* Print statistics that are independent of the collector in use.  */
 311 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 312                   ? (x) \
 313                   : ((x) < 1024*1024*10 \
 314                      ? (x) / 1024 \
 315                      : (x) / (1024*1024))))
 316 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 317
 318 void
 319 ggc_print_common_statistics (stream, stats)
 320      FILE *stream;
 321      ggc_statistics *stats;
 322 {
 323   int code;
 324
 325   /* Set the pointer so that during collection we will actually gather
 326      the statistics.  */
 327   ggc_stats = stats;
 328
 329   /* Then do one collection to fill in the statistics.  */
 330   ggc_collect ();
 331
 332   /* Total the statistics.  */
 333   for (code = 0; code < MAX_TREE_CODES; ++code)
 334     {
 335       stats->total_num_trees += stats->num_trees[code];
 336       stats->total_size_trees += stats->size_trees[code];
 337     }
 338   for (code = 0; code < NUM_RTX_CODE; ++code)
 339     {
 340       stats->total_num_rtxs += stats->num_rtxs[code];
 341       stats->total_size_rtxs += stats->size_rtxs[code];
 342     }
 343
 344   /* Print the statistics for trees.  */
 345   fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
 346            "Number", "Bytes", "% Total");
 347   for (code = 0; code < MAX_TREE_CODES; ++code)
 348     if (ggc_stats->num_trees[code])
 349       {
 350         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 351                  tree_code_name[code],
 352                  ggc_stats->num_trees[code],
 353                  SCALE (ggc_stats->size_trees[code]),
 354                  LABEL (ggc_stats->size_trees[code]),
 355                  (100 * ((double) ggc_stats->size_trees[code])
 356                   / ggc_stats->total_size_trees));
 357       }
 358   fprintf (stream,
 359            "%-17s%10u%16ld%c\n", "Total",
 360            ggc_stats->total_num_trees,
 361            SCALE (ggc_stats->total_size_trees),
 362            LABEL (ggc_stats->total_size_trees));
 363
 364   /* Print the statistics for RTL.  */
 365   fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
 366            "Number", "Bytes", "% Total");
 367   for (code = 0; code < NUM_RTX_CODE; ++code)
 368     if (ggc_stats->num_rtxs[code])
 369       {
 370         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 371                  rtx_name[code],
 372                  ggc_stats->num_rtxs[code],
 373                  SCALE (ggc_stats->size_rtxs[code]),
 374                  LABEL (ggc_stats->size_rtxs[code]),
 375                  (100 * ((double) ggc_stats->size_rtxs[code])
 376                   / ggc_stats->total_size_rtxs));
 377       }
 378   fprintf (stream,
 379            "%-17s%10u%16ld%c\n", "Total",
 380            ggc_stats->total_num_rtxs,
 381            SCALE (ggc_stats->total_size_rtxs),
 382            LABEL (ggc_stats->total_size_rtxs));
 383
 384   /* Don't gather statistics any more.  */
 385   ggc_stats = NULL;
 386 }