gcc/ggc-common.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GNU CC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY 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 GNU CC; 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 "hash.h"
  30 #include "varray.h"
  31 #include "ggc.h"
  32
  33 /* Statistics about the allocation.  */
  34 static ggc_statistics *ggc_stats;
  35
  36 /* The FALSE_LABEL_STACK, declared in except.h, has language-dependent
  37    semantics.  If a front-end needs to mark the false label stack, it
  38    should set this pointer to a non-NULL value.  Otherwise, no marking
  39    will be done.  */
  40 void (*lang_mark_false_label_stack) PARAMS ((struct label_node *));
  41
  42 /* Trees that have been marked, but whose children still need marking.  */
  43 varray_type ggc_pending_trees;
  44
  45 static void ggc_mark_rtx_ptr PARAMS ((void *));
  46 static void ggc_mark_tree_ptr PARAMS ((void *));
  47 static void ggc_mark_rtx_varray_ptr PARAMS ((void *));
  48 static void ggc_mark_tree_varray_ptr PARAMS ((void *));
  49 static void ggc_mark_tree_hash_table_ptr PARAMS ((void *));
  50 static void ggc_mark_trees PARAMS ((void));
  51 static bool ggc_mark_tree_hash_table_entry PARAMS ((struct hash_entry *,
  52                                                        hash_table_key));
  53
  54 /* Maintain global roots that are preserved during GC.  */
  55
  56 /* Global roots that are preserved during calls to gc.  */
  57
  58 struct ggc_root
  59 {
  60   struct ggc_root *next;
  61   void *base;
  62   int nelt;
  63   int size;
  64   void (*cb) PARAMS ((void *));
  65 };
  66
  67 static struct ggc_root *roots;
  68
  69 /* Add BASE as a new garbage collection root.  It is an array of
  70    length NELT with each element SIZE bytes long.  CB is a
  71    function that will be called with a pointer to each element
  72    of the array; it is the intention that CB call the appropriate
  73    routine to mark gc-able memory for that element.  */
  74
  75 void
  76 ggc_add_root (base, nelt, size, cb)
  77      void *base;
  78      int nelt, size;
  79      void (*cb) PARAMS ((void *));
  80 {
  81   struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof (*x));
  82
  83   x->next = roots;
  84   x->base = base;
  85   x->nelt = nelt;
  86   x->size = size;
  87   x->cb = cb;
  88
  89   roots = x;
  90 }
  91
  92 /* Register an array of rtx as a GC root.  */
  93
  94 void
  95 ggc_add_rtx_root (base, nelt)
  96      rtx *base;
  97      int nelt;
  98 {
  99   ggc_add_root (base, nelt, sizeof (rtx), ggc_mark_rtx_ptr);
 100 }
 101
 102 /* Register an array of trees as a GC root.  */
 103
 104 void
 105 ggc_add_tree_root (base, nelt)
 106      tree *base;
 107      int nelt;
 108 {
 109   ggc_add_root (base, nelt, sizeof (tree), ggc_mark_tree_ptr);
 110 }
 111
 112 /* Register a varray of rtxs as a GC root.  */
 113
 114 void
 115 ggc_add_rtx_varray_root (base, nelt)
 116      varray_type *base;
 117      int nelt;
 118 {
 119   ggc_add_root (base, nelt, sizeof (varray_type),
 120                 ggc_mark_rtx_varray_ptr);
 121 }
 122
 123 /* Register a varray of trees as a GC root.  */
 124
 125 void
 126 ggc_add_tree_varray_root (base, nelt)
 127      varray_type *base;
 128      int nelt;
 129 {
 130   ggc_add_root (base, nelt, sizeof (varray_type),
 131                 ggc_mark_tree_varray_ptr);
 132 }
 133
 134 /* Register a hash table of trees as a GC root.  */
 135
 136 void
 137 ggc_add_tree_hash_table_root (base, nelt)
 138      struct hash_table **base;
 139      int nelt;
 140 {
 141   ggc_add_root (base, nelt, sizeof (struct hash_table *),
 142                 ggc_mark_tree_hash_table_ptr);
 143 }
 144
 145 /* Remove the previously registered GC root at BASE.  */
 146
 147 void
 148 ggc_del_root (base)
 149      void *base;
 150 {
 151   struct ggc_root *x, **p;
 152
 153   p = &roots, x = roots;
 154   while (x)
 155     {
 156       if (x->base == base)
 157         {
 158           *p = x->next;
 159           free (x);
 160           return;
 161         }
 162       p = &x->next;
 163       x = x->next;
 164     }
 165
 166   abort();
 167 }
 168
 169 /* Iterate through all registered roots and mark each element.  */
 170
 171 void
 172 ggc_mark_roots ()
 173 {
 174   struct ggc_root* x;
 175
 176   VARRAY_TREE_INIT (ggc_pending_trees, 4096, "ggc_pending_trees");
 177
 178   for (x = roots; x != NULL; x = x->next)
 179     {
 180       char *elt = x->base;
 181       int s = x->size, n = x->nelt;
 182       void (*cb) PARAMS ((void *)) = x->cb;
 183       int i;
 184
 185       for (i = 0; i < n; ++i, elt += s)
 186         (*cb)(elt);
 187     }
 188
 189   /* Mark all the queued up trees, and their children.  */
 190   ggc_mark_trees ();
 191   VARRAY_FREE (ggc_pending_trees);
 192 }
 193
 194 /* R had not been previously marked, but has now been marked via
 195    ggc_set_mark.  Now recurse and process the children.  */
 196
 197 void
 198 ggc_mark_rtx_children (r)
 199      rtx r;
 200 {
 201   const char *fmt;
 202   int i;
 203   rtx next_rtx;
 204
 205   do
 206     {
 207       enum rtx_code code = GET_CODE (r);
 208       /* This gets set to a child rtx to eliminate tail recursion.  */
 209       next_rtx = NULL;
 210
 211       /* Collect statistics, if appropriate.  */
 212       if (ggc_stats)
 213         {
 214           ++ggc_stats->num_rtxs[(int) code];
 215           ggc_stats->size_rtxs[(int) code] += ggc_get_size (r);
 216         }
 217
 218       /* ??? If (some of) these are really pass-dependent info, do we
 219          have any right poking our noses in?  */
 220       switch (code)
 221         {
 222         case JUMP_INSN:
 223           ggc_mark_rtx (JUMP_LABEL (r));
 224           break;
 225         case CODE_LABEL:
 226           ggc_mark_rtx (LABEL_REFS (r));
 227           break;
 228         case LABEL_REF:
 229           ggc_mark_rtx (LABEL_NEXTREF (r));
 230           ggc_mark_rtx (CONTAINING_INSN (r));
 231           break;
 232         case ADDRESSOF:
 233           ggc_mark_tree (ADDRESSOF_DECL (r));
 234           break;
 235         case CONST_DOUBLE:
 236           ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
 237           break;
 238         case NOTE:
 239           switch (NOTE_LINE_NUMBER (r))
 240             {
 241             case NOTE_INSN_RANGE_BEG:
 242             case NOTE_INSN_RANGE_END:
 243             case NOTE_INSN_LIVE:
 244             case NOTE_INSN_EXPECTED_VALUE:
 245               ggc_mark_rtx (NOTE_RANGE_INFO (r));
 246               break;
 247
 248             case NOTE_INSN_BLOCK_BEG:
 249             case NOTE_INSN_BLOCK_END:
 250               ggc_mark_tree (NOTE_BLOCK (r));
 251               break;
 252
 253             default:
 254               break;
 255             }
 256           break;
 257
 258         default:
 259           break;
 260         }
 261
 262       for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
 263         {
 264           rtx exp;
 265           switch (*fmt)
 266             {
 267             case 'e': case 'u':
 268               exp = XEXP (r, i);
 269               if (ggc_test_and_set_mark (exp))
 270                 {
 271                   if (next_rtx == NULL)
 272                     next_rtx = exp;
 273                   else
 274                     ggc_mark_rtx_children (exp);
 275                 }
 276               break;
 277             case 'V': case 'E':
 278               ggc_mark_rtvec (XVEC (r, i));
 279               break;
 280             }
 281         }
 282     }
 283   while ((r = next_rtx) != NULL);
 284 }
 285
 286 /* V had not been previously marked, but has now been marked via
 287    ggc_set_mark.  Now recurse and process the children.  */
 288
 289 void
 290 ggc_mark_rtvec_children (v)
 291      rtvec v;
 292 {
 293   int i;
 294
 295   i = GET_NUM_ELEM (v);
 296   while (--i >= 0)
 297     ggc_mark_rtx (RTVEC_ELT (v, i));
 298 }
 299
 300 /* Recursively set marks on all of the children of the
 301    GCC_PENDING_TREES.  */
 302
 303 static void
 304 ggc_mark_trees ()
 305 {
 306   while (ggc_pending_trees->elements_used)
 307     {
 308       tree t;
 309       enum tree_code code;
 310
 311       t = VARRAY_TOP_TREE (ggc_pending_trees);
 312       VARRAY_POP (ggc_pending_trees);
 313       code = TREE_CODE (t);
 314
 315       /* Collect statistics, if appropriate.  */
 316       if (ggc_stats)
 317         {
 318           ++ggc_stats->num_trees[(int) code];
 319           ggc_stats->size_trees[(int) code] += ggc_get_size (t);
 320         }
 321
 322       /* Bits from common.  */
 323       ggc_mark_tree (TREE_TYPE (t));
 324       ggc_mark_tree (TREE_CHAIN (t));
 325
 326       /* Some nodes require special handling.  */
 327       switch (code)
 328         {
 329         case TREE_LIST:
 330           ggc_mark_tree (TREE_PURPOSE (t));
 331           ggc_mark_tree (TREE_VALUE (t));
 332           continue;
 333
 334         case TREE_VEC:
 335           {
 336             int i = TREE_VEC_LENGTH (t);
 337
 338             while (--i >= 0)
 339               ggc_mark_tree (TREE_VEC_ELT (t, i));
 340             continue;
 341           }
 342
 343         case COMPLEX_CST:
 344           ggc_mark_tree (TREE_REALPART (t));
 345           ggc_mark_tree (TREE_IMAGPART (t));
 346           break;
 347
 348         case PARM_DECL:
 349           ggc_mark_rtx (DECL_INCOMING_RTL (t));
 350           break;
 351
 352         case FIELD_DECL:
 353           ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
 354           break;
 355
 356         case IDENTIFIER_NODE:
 357           lang_mark_tree (t);
 358           continue;
 359
 360         default:
 361           break;
 362         }
 363
 364       /* But in general we can handle them by class.  */
 365       switch (TREE_CODE_CLASS (code))
 366         {
 367         case 'd': /* A decl node.  */
 368           ggc_mark_tree (DECL_SIZE (t));
 369           ggc_mark_tree (DECL_SIZE_UNIT (t));
 370           ggc_mark_tree (DECL_NAME (t));
 371           ggc_mark_tree (DECL_CONTEXT (t));
 372           ggc_mark_tree (DECL_ARGUMENTS (t));
 373           ggc_mark_tree (DECL_RESULT_FLD (t));
 374           ggc_mark_tree (DECL_INITIAL (t));
 375           ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
 376           ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
 377           ggc_mark_tree (DECL_SECTION_NAME (t));
 378           ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
 379           if (DECL_RTL_SET_P (t))
 380             ggc_mark_rtx (DECL_RTL (t));
 381           ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
 382           ggc_mark_tree (DECL_VINDEX (t));
 383           lang_mark_tree (t);
 384           break;
 385
 386         case 't': /* A type node.  */
 387           ggc_mark_tree (TYPE_SIZE (t));
 388           ggc_mark_tree (TYPE_SIZE_UNIT (t));
 389           ggc_mark_tree (TYPE_ATTRIBUTES (t));
 390           ggc_mark_tree (TYPE_VALUES (t));
 391           ggc_mark_tree (TYPE_POINTER_TO (t));
 392           ggc_mark_tree (TYPE_REFERENCE_TO (t));
 393           ggc_mark_tree (TYPE_NAME (t));
 394           ggc_mark_tree (TYPE_MIN_VALUE (t));
 395           ggc_mark_tree (TYPE_MAX_VALUE (t));
 396           ggc_mark_tree (TYPE_NEXT_VARIANT (t));
 397           ggc_mark_tree (TYPE_MAIN_VARIANT (t));
 398           ggc_mark_tree (TYPE_BINFO (t));
 399           ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
 400           ggc_mark_tree (TYPE_CONTEXT (t));
 401           lang_mark_tree (t);
 402           break;
 403
 404         case 'b': /* A lexical block.  */
 405           ggc_mark_tree (BLOCK_VARS (t));
 406           ggc_mark_tree (BLOCK_SUBBLOCKS (t));
 407           ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
 408           ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
 409           break;
 410
 411         case 'c': /* A constant.  */
 412           ggc_mark_rtx (TREE_CST_RTL (t));
 413           break;
 414
 415         case 'r': case '<': case '1':
 416         case '2': case 'e': case 's': /* Expressions.  */
 417           {
 418             int i = TREE_CODE_LENGTH (TREE_CODE (t));
 419             int first_rtl = first_rtl_op (TREE_CODE (t));
 420
 421             while (--i >= 0)
 422               {
 423                 if (i >= first_rtl)
 424                   ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
 425                 else
 426                   ggc_mark_tree (TREE_OPERAND (t, i));
 427               }
 428             break;
 429           }
 430
 431         case 'x':
 432           lang_mark_tree (t);
 433           break;
 434         }
 435     }
 436 }
 437
 438 /* Mark all the elements of the varray V, which contains rtxs.  */
 439
 440 void
 441 ggc_mark_rtx_varray (v)
 442      varray_type v;
 443 {
 444   int i;
 445
 446   if (v)
 447     for (i = v->num_elements - 1; i >= 0; --i)
 448       ggc_mark_rtx (VARRAY_RTX (v, i));
 449 }
 450
 451 /* Mark all the elements of the varray V, which contains trees.  */
 452
 453 void
 454 ggc_mark_tree_varray (v)
 455      varray_type v;
 456 {
 457   int i;
 458
 459   if (v)
 460     for (i = v->num_elements - 1; i >= 0; --i)
 461       ggc_mark_tree (VARRAY_TREE (v, i));
 462 }
 463
 464 /* Mark the hash table-entry HE.  It's key field is really a tree.  */
 465
 466 static bool
 467 ggc_mark_tree_hash_table_entry (he, k)
 468      struct hash_entry *he;
 469      hash_table_key k ATTRIBUTE_UNUSED;
 470 {
 471   ggc_mark_tree ((tree) he->key);
 472   return true;
 473 }
 474
 475 /* Mark all the elements of the hash-table H, which contains trees.  */
 476
 477 void
 478 ggc_mark_tree_hash_table (ht)
 479      struct hash_table *ht;
 480 {
 481   hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
 482 }
 483
 484 /* Type-correct function to pass to ggc_add_root.  It just forwards
 485    *ELT (which is an rtx) to ggc_mark_rtx.  */
 486
 487 static void
 488 ggc_mark_rtx_ptr (elt)
 489      void *elt;
 490 {
 491   ggc_mark_rtx (*(rtx *) elt);
 492 }
 493
 494 /* Type-correct function to pass to ggc_add_root.  It just forwards
 495    *ELT (which is a tree) to ggc_mark_tree.  */
 496
 497 static void
 498 ggc_mark_tree_ptr (elt)
 499      void *elt;
 500 {
 501   ggc_mark_tree (*(tree *) elt);
 502 }
 503
 504 /* Type-correct function to pass to ggc_add_root.  It just forwards
 505    ELT (which is really a varray_type *) to ggc_mark_rtx_varray.  */
 506
 507 static void
 508 ggc_mark_rtx_varray_ptr (elt)
 509      void *elt;
 510 {
 511   ggc_mark_rtx_varray (*(varray_type *) elt);
 512 }
 513
 514 /* Type-correct function to pass to ggc_add_root.  It just forwards
 515    ELT (which is really a varray_type *) to ggc_mark_tree_varray.  */
 516
 517 static void
 518 ggc_mark_tree_varray_ptr (elt)
 519      void *elt;
 520 {
 521   ggc_mark_tree_varray (*(varray_type *) elt);
 522 }
 523
 524 /* Type-correct function to pass to ggc_add_root.  It just forwards
 525    ELT (which is really a struct hash_table **) to
 526    ggc_mark_tree_hash_table.  */
 527
 528 static void
 529 ggc_mark_tree_hash_table_ptr (elt)
 530      void *elt;
 531 {
 532   ggc_mark_tree_hash_table (*(struct hash_table **) elt);
 533 }
 534
 535 /* Allocate a block of memory, then clear it.  */
 536 void *
 537 ggc_alloc_cleared (size)
 538      size_t size;
 539 {
 540   void *buf = ggc_alloc (size);
 541   memset (buf, 0, size);
 542   return buf;
 543 }
 544
 545 /* Print statistics that are independent of the collector in use.  */
 546 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 547                   ? (x) \
 548                   : ((x) < 1024*1024*10 \
 549                      ? (x) / 1024 \
 550                      : (x) / (1024*1024))))
 551 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 552
 553 void
 554 ggc_print_common_statistics (stream, stats)
 555      FILE *stream;
 556      ggc_statistics *stats;
 557 {
 558   int code;
 559
 560   /* Set the pointer so that during collection we will actually gather
 561      the statistics.  */
 562   ggc_stats = stats;
 563
 564   /* Then do one collection to fill in the statistics.  */
 565   ggc_collect ();
 566
 567   /* Total the statistics.  */
 568   for (code = 0; code < MAX_TREE_CODES; ++code)
 569     {
 570       stats->total_num_trees += stats->num_trees[code];
 571       stats->total_size_trees += stats->size_trees[code];
 572     }
 573   for (code = 0; code < NUM_RTX_CODE; ++code)
 574     {
 575       stats->total_num_rtxs += stats->num_rtxs[code];
 576       stats->total_size_rtxs += stats->size_rtxs[code];
 577     }
 578
 579   /* Print the statistics for trees.  */
 580   fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
 581            "Number", "Bytes", "% Total");
 582   for (code = 0; code < MAX_TREE_CODES; ++code)
 583     if (ggc_stats->num_trees[code])
 584       {
 585         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 586                  tree_code_name[code],
 587                  ggc_stats->num_trees[code],
 588                  SCALE (ggc_stats->size_trees[code]),
 589                  LABEL (ggc_stats->size_trees[code]),
 590                  (100 * ((double) ggc_stats->size_trees[code])
 591                   / ggc_stats->total_size_trees));
 592       }
 593   fprintf (stream,
 594            "%-17s%10u%16ld%c\n", "Total",
 595            ggc_stats->total_num_trees,
 596            SCALE (ggc_stats->total_size_trees),
 597            LABEL (ggc_stats->total_size_trees));
 598
 599   /* Print the statistics for RTL.  */
 600   fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
 601            "Number", "Bytes", "% Total");
 602   for (code = 0; code < NUM_RTX_CODE; ++code)
 603     if (ggc_stats->num_rtxs[code])
 604       {
 605         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 606                  rtx_name[code],
 607                  ggc_stats->num_rtxs[code],
 608                  SCALE (ggc_stats->size_rtxs[code]),
 609                  LABEL (ggc_stats->size_rtxs[code]),
 610                  (100 * ((double) ggc_stats->size_rtxs[code])
 611                   / ggc_stats->total_size_rtxs));
 612       }
 613   fprintf (stream,
 614            "%-17s%10u%16ld%c\n", "Total",
 615            ggc_stats->total_num_rtxs,
 616            SCALE (ggc_stats->total_size_rtxs),
 617            LABEL (ggc_stats->total_size_rtxs));
 618
 619   /* Don't gather statistics any more.  */
 620   ggc_stats = NULL;
 621 }