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           ggc_mark_string (LABEL_ALTERNATE_NAME (r));
 228           break;
 229         case LABEL_REF:
 230           ggc_mark_rtx (LABEL_NEXTREF (r));
 231           ggc_mark_rtx (CONTAINING_INSN (r));
 232           break;
 233         case ADDRESSOF:
 234           ggc_mark_tree (ADDRESSOF_DECL (r));
 235           break;
 236         case CONST_DOUBLE:
 237           ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
 238           break;
 239         case NOTE:
 240           switch (NOTE_LINE_NUMBER (r))
 241             {
 242             case NOTE_INSN_RANGE_BEG:
 243             case NOTE_INSN_RANGE_END:
 244             case NOTE_INSN_LIVE:
 245             case NOTE_INSN_EXPECTED_VALUE:
 246               ggc_mark_rtx (NOTE_RANGE_INFO (r));
 247               break;
 248
 249             case NOTE_INSN_BLOCK_BEG:
 250             case NOTE_INSN_BLOCK_END:
 251               ggc_mark_tree (NOTE_BLOCK (r));
 252               break;
 253
 254             default:
 255               if (NOTE_LINE_NUMBER (r) >= 0)
 256                 {
 257             case NOTE_INSN_DELETED_LABEL:
 258                   ggc_mark_string (NOTE_SOURCE_FILE (r));
 259                 }
 260               break;
 261             }
 262           break;
 263
 264         default:
 265           break;
 266         }
 267
 268       for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
 269         {
 270           rtx exp;
 271           switch (*fmt)
 272             {
 273             case 'e': case 'u':
 274               exp = XEXP (r, i);
 275               if (ggc_test_and_set_mark (exp))
 276                 {
 277                   if (next_rtx == NULL)
 278                     next_rtx = exp;
 279                   else
 280                     ggc_mark_rtx_children (exp);
 281                 }
 282               break;
 283             case 'V': case 'E':
 284               ggc_mark_rtvec (XVEC (r, i));
 285               break;
 286             case 'S': case 's':
 287               ggc_mark_if_gcable (XSTR (r, i));
 288               break;
 289             }
 290         }
 291     }
 292   while ((r = next_rtx) != NULL);
 293 }
 294
 295 /* V had not been previously marked, but has now been marked via
 296    ggc_set_mark.  Now recurse and process the children.  */
 297
 298 void
 299 ggc_mark_rtvec_children (v)
 300      rtvec v;
 301 {
 302   int i;
 303
 304   i = GET_NUM_ELEM (v);
 305   while (--i >= 0)
 306     ggc_mark_rtx (RTVEC_ELT (v, i));
 307 }
 308
 309 /* Recursively set marks on all of the children of the
 310    GCC_PENDING_TREES.  */
 311
 312 static void
 313 ggc_mark_trees ()
 314 {
 315   while (ggc_pending_trees->elements_used)
 316     {
 317       tree t;
 318       enum tree_code code;
 319
 320       t = VARRAY_TOP_TREE (ggc_pending_trees);
 321       VARRAY_POP (ggc_pending_trees);
 322       code = TREE_CODE (t);
 323
 324       /* Collect statistics, if appropriate.  */
 325       if (ggc_stats)
 326         {
 327           ++ggc_stats->num_trees[(int) code];
 328           ggc_stats->size_trees[(int) code] += ggc_get_size (t);
 329         }
 330
 331       /* Bits from common.  */
 332       ggc_mark_tree (TREE_TYPE (t));
 333       ggc_mark_tree (TREE_CHAIN (t));
 334
 335       /* Some nodes require special handling.  */
 336       switch (code)
 337         {
 338         case TREE_LIST:
 339           ggc_mark_tree (TREE_PURPOSE (t));
 340           ggc_mark_tree (TREE_VALUE (t));
 341           continue;
 342
 343         case TREE_VEC:
 344           {
 345             int i = TREE_VEC_LENGTH (t);
 346
 347             while (--i >= 0)
 348               ggc_mark_tree (TREE_VEC_ELT (t, i));
 349             continue;
 350           }
 351
 352         case COMPLEX_CST:
 353           ggc_mark_tree (TREE_REALPART (t));
 354           ggc_mark_tree (TREE_IMAGPART (t));
 355           break;
 356
 357         case STRING_CST:
 358           ggc_mark_string (TREE_STRING_POINTER (t));
 359           break;
 360
 361         case PARM_DECL:
 362           ggc_mark_rtx (DECL_INCOMING_RTL (t));
 363           break;
 364
 365         case FIELD_DECL:
 366           ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
 367           break;
 368
 369         case IDENTIFIER_NODE:
 370           ggc_mark_string (IDENTIFIER_POINTER (t));
 371           lang_mark_tree (t);
 372           continue;
 373
 374         default:
 375           break;
 376         }
 377
 378       /* But in general we can handle them by class.  */
 379       switch (TREE_CODE_CLASS (code))
 380         {
 381         case 'd': /* A decl node.  */
 382           ggc_mark_string (DECL_SOURCE_FILE (t));
 383           ggc_mark_tree (DECL_SIZE (t));
 384           ggc_mark_tree (DECL_SIZE_UNIT (t));
 385           ggc_mark_tree (DECL_NAME (t));
 386           ggc_mark_tree (DECL_CONTEXT (t));
 387           ggc_mark_tree (DECL_ARGUMENTS (t));
 388           ggc_mark_tree (DECL_RESULT_FLD (t));
 389           ggc_mark_tree (DECL_INITIAL (t));
 390           ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
 391           ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
 392           ggc_mark_tree (DECL_SECTION_NAME (t));
 393           ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
 394           ggc_mark_rtx (DECL_RTL (t));
 395           ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
 396           ggc_mark_tree (DECL_VINDEX (t));
 397           lang_mark_tree (t);
 398           break;
 399
 400         case 't': /* A type node.  */
 401           ggc_mark_tree (TYPE_SIZE (t));
 402           ggc_mark_tree (TYPE_SIZE_UNIT (t));
 403           ggc_mark_tree (TYPE_ATTRIBUTES (t));
 404           ggc_mark_tree (TYPE_VALUES (t));
 405           ggc_mark_tree (TYPE_POINTER_TO (t));
 406           ggc_mark_tree (TYPE_REFERENCE_TO (t));
 407           ggc_mark_tree (TYPE_NAME (t));
 408           ggc_mark_tree (TYPE_MIN_VALUE (t));
 409           ggc_mark_tree (TYPE_MAX_VALUE (t));
 410           ggc_mark_tree (TYPE_NEXT_VARIANT (t));
 411           ggc_mark_tree (TYPE_MAIN_VARIANT (t));
 412           ggc_mark_tree (TYPE_BINFO (t));
 413           ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
 414           ggc_mark_tree (TYPE_CONTEXT (t));
 415           lang_mark_tree (t);
 416           break;
 417
 418         case 'b': /* A lexical block.  */
 419           ggc_mark_tree (BLOCK_VARS (t));
 420           ggc_mark_tree (BLOCK_SUBBLOCKS (t));
 421           ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
 422           ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
 423           break;
 424
 425         case 'c': /* A constant.  */
 426           ggc_mark_rtx (TREE_CST_RTL (t));
 427           break;
 428
 429         case 'r': case '<': case '1':
 430         case '2': case 'e': case 's': /* Expressions.  */
 431           {
 432             int i = TREE_CODE_LENGTH (TREE_CODE (t));
 433             int first_rtl = first_rtl_op (TREE_CODE (t));
 434
 435             while (--i >= 0)
 436               {
 437                 if (i >= first_rtl)
 438                   ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
 439                 else
 440                   ggc_mark_tree (TREE_OPERAND (t, i));
 441               }
 442             break;
 443           }
 444
 445         case 'x':
 446           lang_mark_tree (t);
 447           break;
 448         }
 449     }
 450 }
 451
 452 /* Mark all the elements of the varray V, which contains rtxs.  */
 453
 454 void
 455 ggc_mark_rtx_varray (v)
 456      varray_type v;
 457 {
 458   int i;
 459
 460   if (v)
 461     for (i = v->num_elements - 1; i >= 0; --i)
 462       ggc_mark_rtx (VARRAY_RTX (v, i));
 463 }
 464
 465 /* Mark all the elements of the varray V, which contains trees.  */
 466
 467 void
 468 ggc_mark_tree_varray (v)
 469      varray_type v;
 470 {
 471   int i;
 472
 473   if (v)
 474     for (i = v->num_elements - 1; i >= 0; --i)
 475       ggc_mark_tree (VARRAY_TREE (v, i));
 476 }
 477
 478 /* Mark the hash table-entry HE.  It's key field is really a tree.  */
 479
 480 static boolean
 481 ggc_mark_tree_hash_table_entry (he, k)
 482      struct hash_entry *he;
 483      hash_table_key k ATTRIBUTE_UNUSED;
 484 {
 485   ggc_mark_tree ((tree) he->key);
 486   return true;
 487 }
 488
 489 /* Mark all the elements of the hash-table H, which contains trees.  */
 490
 491 void
 492 ggc_mark_tree_hash_table (ht)
 493      struct hash_table *ht;
 494 {
 495   hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
 496 }
 497
 498 /* Type-correct function to pass to ggc_add_root.  It just forwards
 499    *ELT (which is an rtx) to ggc_mark_rtx.  */
 500
 501 static void
 502 ggc_mark_rtx_ptr (elt)
 503      void *elt;
 504 {
 505   ggc_mark_rtx (*(rtx *) elt);
 506 }
 507
 508 /* Type-correct function to pass to ggc_add_root.  It just forwards
 509    *ELT (which is a tree) to ggc_mark_tree.  */
 510
 511 static void
 512 ggc_mark_tree_ptr (elt)
 513      void *elt;
 514 {
 515   ggc_mark_tree (*(tree *) elt);
 516 }
 517
 518 /* Type-correct function to pass to ggc_add_root.  It just forwards
 519    ELT (which is really a varray_type *) to ggc_mark_rtx_varray.  */
 520
 521 static void
 522 ggc_mark_rtx_varray_ptr (elt)
 523      void *elt;
 524 {
 525   ggc_mark_rtx_varray (*(varray_type *) 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_tree_varray.  */
 530
 531 static void
 532 ggc_mark_tree_varray_ptr (elt)
 533      void *elt;
 534 {
 535   ggc_mark_tree_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 struct hash_table **) to
 540    ggc_mark_tree_hash_table.  */
 541
 542 static void
 543 ggc_mark_tree_hash_table_ptr (elt)
 544      void *elt;
 545 {
 546   ggc_mark_tree_hash_table (*(struct hash_table **) elt);
 547 }
 548
 549 /* Allocate a block of memory, then clear it.  */
 550 void *
 551 ggc_alloc_cleared (size)
 552      size_t size;
 553 {
 554   void *buf = ggc_alloc (size);
 555   memset (buf, 0, size);
 556   return buf;
 557 }
 558
 559 /* Print statistics that are independent of the collector in use.  */
 560 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 561                   ? (x) \
 562                   : ((x) < 1024*1024*10 \
 563                      ? (x) / 1024 \
 564                      : (x) / (1024*1024))))
 565 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 566
 567 void
 568 ggc_print_common_statistics (stream, stats)
 569      FILE *stream;
 570      ggc_statistics *stats;
 571 {
 572   int code;
 573
 574   /* Set the pointer so that during collection we will actually gather
 575      the statistics.  */
 576   ggc_stats = stats;
 577
 578   /* Then do one collection to fill in the statistics.  */
 579   ggc_collect ();
 580
 581   /* Total the statistics.  */
 582   for (code = 0; code < MAX_TREE_CODES; ++code)
 583     {
 584       stats->total_num_trees += stats->num_trees[code];
 585       stats->total_size_trees += stats->size_trees[code];
 586     }
 587   for (code = 0; code < NUM_RTX_CODE; ++code)
 588     {
 589       stats->total_num_rtxs += stats->num_rtxs[code];
 590       stats->total_size_rtxs += stats->size_rtxs[code];
 591     }
 592
 593   /* Print the statistics for trees.  */
 594   fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
 595            "Number", "Bytes", "% Total");
 596   for (code = 0; code < MAX_TREE_CODES; ++code)
 597     if (ggc_stats->num_trees[code])
 598       {
 599         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 600                  tree_code_name[code],
 601                  ggc_stats->num_trees[code],
 602                  SCALE (ggc_stats->size_trees[code]),
 603                  LABEL (ggc_stats->size_trees[code]),
 604                  (100 * ((double) ggc_stats->size_trees[code])
 605                   / ggc_stats->total_size_trees));
 606       }
 607   fprintf (stream,
 608            "%-17s%10u%16ld%c\n", "Total",
 609            ggc_stats->total_num_trees,
 610            SCALE (ggc_stats->total_size_trees),
 611            LABEL (ggc_stats->total_size_trees));
 612
 613   /* Print the statistics for RTL.  */
 614   fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
 615            "Number", "Bytes", "% Total");
 616   for (code = 0; code < NUM_RTX_CODE; ++code)
 617     if (ggc_stats->num_rtxs[code])
 618       {
 619         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 620                  rtx_name[code],
 621                  ggc_stats->num_rtxs[code],
 622                  SCALE (ggc_stats->size_rtxs[code]),
 623                  LABEL (ggc_stats->size_rtxs[code]),
 624                  (100 * ((double) ggc_stats->size_rtxs[code])
 625                   / ggc_stats->total_size_rtxs));
 626       }
 627   fprintf (stream,
 628            "%-17s%10u%16ld%c\n", "Total",
 629            ggc_stats->total_num_rtxs,
 630            SCALE (ggc_stats->total_size_rtxs),
 631            LABEL (ggc_stats->total_size_rtxs));
 632
 633   /* Don't gather statistics any more.  */
 634   ggc_stats = NULL;
 635 }