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_SIZE_UNIT (t));
 382       ggc_mark_tree (DECL_NAME (t));
 383       ggc_mark_tree (DECL_CONTEXT (t));
 384       ggc_mark_tree (DECL_ARGUMENTS (t));
 385       ggc_mark_tree (DECL_RESULT (t));
 386       ggc_mark_tree (DECL_INITIAL (t));
 387       ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
 388       ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
 389       ggc_mark_tree (DECL_SECTION_NAME (t));
 390       ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
 391       ggc_mark_rtx (DECL_RTL (t));
 392       ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
 393       ggc_mark_tree (DECL_VINDEX (t));
 394       lang_mark_tree (t);
 395       break;
 396
 397     case 't': /* A type node.  */
 398       ggc_mark_tree (TYPE_SIZE (t));
 399       ggc_mark_tree (TYPE_SIZE_UNIT (t));
 400       ggc_mark_tree (TYPE_ATTRIBUTES (t));
 401       ggc_mark_tree (TYPE_VALUES (t));
 402       ggc_mark_tree (TYPE_POINTER_TO (t));
 403       ggc_mark_tree (TYPE_REFERENCE_TO (t));
 404       ggc_mark_tree (TYPE_NAME (t));
 405       ggc_mark_tree (TYPE_MIN_VALUE (t));
 406       ggc_mark_tree (TYPE_MAX_VALUE (t));
 407       ggc_mark_tree (TYPE_NEXT_VARIANT (t));
 408       ggc_mark_tree (TYPE_MAIN_VARIANT (t));
 409       ggc_mark_tree (TYPE_BINFO (t));
 410       ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
 411       ggc_mark_tree (TYPE_CONTEXT (t));
 412       lang_mark_tree (t);
 413       break;
 414
 415     case 'b': /* A lexical block.  */
 416       ggc_mark_tree (BLOCK_VARS (t));
 417       ggc_mark_tree (BLOCK_SUBBLOCKS (t));
 418       ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
 419       ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
 420       break;
 421
 422     case 'c': /* A constant.  */
 423       ggc_mark_rtx (TREE_CST_RTL (t));
 424       break;
 425
 426     case 'r': case '<': case '1':
 427     case '2': case 'e': case 's': /* Expressions.  */
 428       {
 429         int i = tree_code_length[TREE_CODE (t)];
 430         while (--i >= 0)
 431           ggc_mark_tree (TREE_OPERAND (t, i));
 432         break;
 433       }
 434
 435     case 'x':
 436       lang_mark_tree (t);
 437       break;
 438     }
 439 }
 440
 441 /* Mark all the elements of the varray V, which contains rtxs.  */
 442
 443 void
 444 ggc_mark_rtx_varray (v)
 445      varray_type v;
 446 {
 447   int i;
 448
 449   if (v)
 450     for (i = v->num_elements - 1; i >= 0; --i)
 451       ggc_mark_rtx (VARRAY_RTX (v, i));
 452 }
 453
 454 /* Mark all the elements of the varray V, which contains trees.  */
 455
 456 void
 457 ggc_mark_tree_varray (v)
 458      varray_type v;
 459 {
 460   int i;
 461
 462   if (v)
 463     for (i = v->num_elements - 1; i >= 0; --i)
 464       ggc_mark_tree (VARRAY_TREE (v, i));
 465 }
 466
 467 /* Mark the hash table-entry HE.  It's key field is really a tree.  */
 468
 469 static boolean
 470 ggc_mark_tree_hash_table_entry (he, k)
 471      struct hash_entry *he;
 472      hash_table_key k ATTRIBUTE_UNUSED;
 473 {
 474   ggc_mark_tree ((tree) he->key);
 475   return true;
 476 }
 477
 478 /* Mark all the elements of the hash-table H, which contains trees.  */
 479
 480 void
 481 ggc_mark_tree_hash_table (ht)
 482      struct hash_table *ht;
 483 {
 484   hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
 485 }
 486
 487 /* Type-correct function to pass to ggc_add_root.  It just forwards
 488    *ELT (which is an rtx) to ggc_mark_rtx.  */
 489
 490 static void
 491 ggc_mark_rtx_ptr (elt)
 492      void *elt;
 493 {
 494   ggc_mark_rtx (*(rtx *) elt);
 495 }
 496
 497 /* Type-correct function to pass to ggc_add_root.  It just forwards
 498    *ELT (which is a tree) to ggc_mark_tree.  */
 499
 500 static void
 501 ggc_mark_tree_ptr (elt)
 502      void *elt;
 503 {
 504   ggc_mark_tree (*(tree *) elt);
 505 }
 506
 507 /* Type-correct function to pass to ggc_add_root.  It just forwards
 508    ELT (which is really a varray_type *) to ggc_mark_rtx_varray.  */
 509
 510 static void
 511 ggc_mark_rtx_varray_ptr (elt)
 512      void *elt;
 513 {
 514   ggc_mark_rtx_varray (*(varray_type *) elt);
 515 }
 516
 517 /* Type-correct function to pass to ggc_add_root.  It just forwards
 518    ELT (which is really a varray_type *) to ggc_mark_tree_varray.  */
 519
 520 static void
 521 ggc_mark_tree_varray_ptr (elt)
 522      void *elt;
 523 {
 524   ggc_mark_tree_varray (*(varray_type *) elt);
 525 }
 526
 527 /* Type-correct function to pass to ggc_add_root.  It just forwards
 528    ELT (which is really a struct hash_table **) to
 529    ggc_mark_tree_hash_table.  */
 530
 531 static void
 532 ggc_mark_tree_hash_table_ptr (elt)
 533      void *elt;
 534 {
 535   ggc_mark_tree_hash_table (*(struct hash_table **) elt);
 536 }
 537
 538 /* Type-correct function to pass to ggc_add_root.  It just forwards
 539    ELT (which is really a char **) to ggc_mark_string.  */
 540
 541 static void
 542 ggc_mark_string_ptr (elt)
 543      void *elt;
 544 {
 545   ggc_mark_string (*(char **) elt);
 546 }
 547
 548 /* Allocate a gc-able string.  If CONTENTS is null, then the memory will
 549    be uninitialized.  If LENGTH is -1, then CONTENTS is assumed to be a
 550    null-terminated string and the memory sized accordingly.  Otherwise,
 551    the memory is filled with LENGTH bytes from CONTENTS.  */
 552
 553 char *
 554 ggc_alloc_string (contents, length)
 555      const char *contents;
 556      int length;
 557 {
 558   char *string;
 559
 560   if (length < 0)
 561     {
 562       if (contents == NULL)
 563         return NULL;
 564       length = strlen (contents);
 565     }
 566
 567   string = (char *) ggc_alloc_obj (length + 1, 0);
 568   if (contents != NULL)
 569     memcpy (string, contents, length);
 570   string[length] = 0;
 571
 572   return string;
 573 }
 574
 575 /* Print statistics that are independent of the collector in use.  */
 576
 577 void
 578 ggc_print_statistics (stream, stats)
 579      FILE *stream;
 580      ggc_statistics *stats;
 581 {
 582   int code;
 583
 584   /* Set the pointer so that during collection we will actually gather
 585      the statistics.  */
 586   ggc_stats = stats;
 587
 588   /* Then do one collection to fill in the statistics.  */
 589   ggc_collect ();
 590
 591   /* Total the statistics.  */
 592   for (code = 0; code < MAX_TREE_CODES; ++code)
 593     {
 594       stats->total_num_trees += stats->num_trees[code];
 595       stats->total_size_trees += stats->size_trees[code];
 596     }
 597   for (code = 0; code < NUM_RTX_CODE; ++code)
 598     {
 599       stats->total_num_rtxs += stats->num_rtxs[code];
 600       stats->total_size_rtxs += stats->size_rtxs[code];
 601     }
 602
 603   /* Print the statistics for trees.  */
 604   fprintf (stream, "%-22s%-16s%-16s%-7s\n", "Code",
 605            "Number", "Bytes", "% Total");
 606   for (code = 0; code < MAX_TREE_CODES; ++code)
 607     if (ggc_stats->num_trees[code])
 608       {
 609         fprintf (stream, "%s%*s%-15u %-15lu %7.3f\n",
 610                  tree_code_name[code],
 611                  22 - (int) strlen (tree_code_name[code]), "",
 612                  ggc_stats->num_trees[code],
 613                  (unsigned long) ggc_stats->size_trees[code],
 614                  (100 * ((double) ggc_stats->size_trees[code])
 615                   / ggc_stats->total_size_trees));
 616       }
 617   fprintf (stream,
 618            "%-22s%-15u %-15lu\n", "Total",
 619            ggc_stats->total_num_trees,
 620            (unsigned long) ggc_stats->total_size_trees);
 621
 622   /* Print the statistics for RTL.  */
 623   fprintf (stream, "\n%-22s%-16s%-16s%-7s\n", "Code",
 624            "Number", "Bytes", "% Total");
 625   for (code = 0; code < NUM_RTX_CODE; ++code)
 626     if (ggc_stats->num_rtxs[code])
 627       {
 628         fprintf (stream, "%s%*s%-15u %-15lu %7.3f\n",
 629                  rtx_name[code],
 630                  22 - (int) strlen (rtx_name[code]), "",
 631                  ggc_stats->num_rtxs[code],
 632                  (unsigned long) ggc_stats->size_rtxs[code],
 633                  (100 * ((double) ggc_stats->size_rtxs[code])
 634                   / ggc_stats->total_size_rtxs));
 635       }
 636   fprintf (stream,
 637            "%-22s%-15u %-15lu\n", "Total",
 638            ggc_stats->total_num_rtxs,
 639            (unsigned long) ggc_stats->total_size_rtxs);
 640
 641
 642   /* Don't gather statistics any more.  */
 643   ggc_stats = NULL;
 644 }