gcc/ggc-common.c

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