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