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