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