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