gcc/ggc-common.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 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 GCC; 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 bool 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             }
 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 /* Recursively set marks on all of the children of the
 301    GCC_PENDING_TREES.  */
 302
 303 static void
 304 ggc_mark_trees ()
 305 {
 306   while (ggc_pending_trees->elements_used)
 307     {
 308       tree t;
 309       enum tree_code code;
 310
 311       t = VARRAY_TOP_TREE (ggc_pending_trees);
 312       VARRAY_POP (ggc_pending_trees);
 313       code = TREE_CODE (t);
 314
 315       /* Collect statistics, if appropriate.  */
 316       if (ggc_stats)
 317         {
 318           ++ggc_stats->num_trees[(int) code];
 319           ggc_stats->size_trees[(int) code] += ggc_get_size (t);
 320         }
 321
 322       /* Bits from common.  */
 323       ggc_mark_tree (TREE_TYPE (t));
 324       ggc_mark_tree (TREE_CHAIN (t));
 325
 326       /* Some nodes require special handling.  */
 327       switch (code)
 328         {
 329         case TREE_LIST:
 330           ggc_mark_tree (TREE_PURPOSE (t));
 331           ggc_mark_tree (TREE_VALUE (t));
 332           continue;
 333
 334         case TREE_VEC:
 335           {
 336             int i = TREE_VEC_LENGTH (t);
 337
 338             while (--i >= 0)
 339               ggc_mark_tree (TREE_VEC_ELT (t, i));
 340             continue;
 341           }
 342
 343         case COMPLEX_CST:
 344           ggc_mark_tree (TREE_REALPART (t));
 345           ggc_mark_tree (TREE_IMAGPART (t));
 346           break;
 347
 348         case PARM_DECL:
 349           ggc_mark_rtx (DECL_INCOMING_RTL (t));
 350           break;
 351
 352         case FIELD_DECL:
 353           ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
 354           break;
 355
 356         case IDENTIFIER_NODE:
 357           lang_mark_tree (t);
 358           continue;
 359
 360         default:
 361           break;
 362         }
 363
 364       /* But in general we can handle them by class.  */
 365       switch (TREE_CODE_CLASS (code))
 366         {
 367         case 'd': /* A decl node.  */
 368           ggc_mark_tree (DECL_SIZE (t));
 369           ggc_mark_tree (DECL_SIZE_UNIT (t));
 370           ggc_mark_tree (DECL_NAME (t));
 371           ggc_mark_tree (DECL_CONTEXT (t));
 372           ggc_mark_tree (DECL_ARGUMENTS (t));
 373           ggc_mark_tree (DECL_RESULT_FLD (t));
 374           ggc_mark_tree (DECL_INITIAL (t));
 375           ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
 376           ggc_mark_tree (DECL_SECTION_NAME (t));
 377           ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
 378           if (DECL_RTL_SET_P (t))
 379             ggc_mark_rtx (DECL_RTL (t));
 380           ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
 381           ggc_mark_tree (DECL_VINDEX (t));
 382           if (DECL_ASSEMBLER_NAME_SET_P (t))
 383             ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
 384           lang_mark_tree (t);
 385           break;
 386
 387         case 't': /* A type node.  */
 388           ggc_mark_tree (TYPE_SIZE (t));
 389           ggc_mark_tree (TYPE_SIZE_UNIT (t));
 390           ggc_mark_tree (TYPE_ATTRIBUTES (t));
 391           ggc_mark_tree (TYPE_VALUES (t));
 392           ggc_mark_tree (TYPE_POINTER_TO (t));
 393           ggc_mark_tree (TYPE_REFERENCE_TO (t));
 394           ggc_mark_tree (TYPE_NAME (t));
 395           ggc_mark_tree (TYPE_MIN_VALUE (t));
 396           ggc_mark_tree (TYPE_MAX_VALUE (t));
 397           ggc_mark_tree (TYPE_NEXT_VARIANT (t));
 398           ggc_mark_tree (TYPE_MAIN_VARIANT (t));
 399           ggc_mark_tree (TYPE_BINFO (t));
 400           ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
 401           ggc_mark_tree (TYPE_CONTEXT (t));
 402           lang_mark_tree (t);
 403           break;
 404
 405         case 'b': /* A lexical block.  */
 406           ggc_mark_tree (BLOCK_VARS (t));
 407           ggc_mark_tree (BLOCK_SUBBLOCKS (t));
 408           ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
 409           ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
 410           break;
 411
 412         case 'c': /* A constant.  */
 413           ggc_mark_rtx (TREE_CST_RTL (t));
 414           break;
 415
 416         case 'r': case '<': case '1':
 417         case '2': case 'e': case 's': /* Expressions.  */
 418           {
 419             int i = TREE_CODE_LENGTH (TREE_CODE (t));
 420             int first_rtl = first_rtl_op (TREE_CODE (t));
 421
 422             while (--i >= 0)
 423               {
 424                 if (i >= first_rtl)
 425                   ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
 426                 else
 427                   ggc_mark_tree (TREE_OPERAND (t, i));
 428               }
 429             break;
 430           }
 431
 432         case 'x':
 433           lang_mark_tree (t);
 434           break;
 435         }
 436     }
 437 }
 438
 439 /* Mark all the elements of the varray V, which contains rtxs.  */
 440
 441 void
 442 ggc_mark_rtx_varray (v)
 443      varray_type v;
 444 {
 445   int i;
 446
 447   if (v)
 448     for (i = v->num_elements - 1; i >= 0; --i)
 449       ggc_mark_rtx (VARRAY_RTX (v, i));
 450 }
 451
 452 /* Mark all the elements of the varray V, which contains trees.  */
 453
 454 void
 455 ggc_mark_tree_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_tree (VARRAY_TREE (v, i));
 463 }
 464
 465 /* Mark the hash table-entry HE.  It's key field is really a tree.  */
 466
 467 static bool
 468 ggc_mark_tree_hash_table_entry (he, k)
 469      struct hash_entry *he;
 470      hash_table_key k ATTRIBUTE_UNUSED;
 471 {
 472   ggc_mark_tree ((tree) he->key);
 473   return true;
 474 }
 475
 476 /* Mark all the elements of the hash-table H, which contains trees.  */
 477
 478 void
 479 ggc_mark_tree_hash_table (ht)
 480      struct hash_table *ht;
 481 {
 482   hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
 483 }
 484
 485 /* Type-correct function to pass to ggc_add_root.  It just forwards
 486    *ELT (which is an rtx) to ggc_mark_rtx.  */
 487
 488 static void
 489 ggc_mark_rtx_ptr (elt)
 490      void *elt;
 491 {
 492   ggc_mark_rtx (*(rtx *) elt);
 493 }
 494
 495 /* Type-correct function to pass to ggc_add_root.  It just forwards
 496    *ELT (which is a tree) to ggc_mark_tree.  */
 497
 498 static void
 499 ggc_mark_tree_ptr (elt)
 500      void *elt;
 501 {
 502   ggc_mark_tree (*(tree *) elt);
 503 }
 504
 505 /* Type-correct function to pass to ggc_add_root.  It just forwards
 506    ELT (which is really a varray_type *) to ggc_mark_rtx_varray.  */
 507
 508 static void
 509 ggc_mark_rtx_varray_ptr (elt)
 510      void *elt;
 511 {
 512   ggc_mark_rtx_varray (*(varray_type *) elt);
 513 }
 514
 515 /* Type-correct function to pass to ggc_add_root.  It just forwards
 516    ELT (which is really a varray_type *) to ggc_mark_tree_varray.  */
 517
 518 static void
 519 ggc_mark_tree_varray_ptr (elt)
 520      void *elt;
 521 {
 522   ggc_mark_tree_varray (*(varray_type *) elt);
 523 }
 524
 525 /* Type-correct function to pass to ggc_add_root.  It just forwards
 526    ELT (which is really a struct hash_table **) to
 527    ggc_mark_tree_hash_table.  */
 528
 529 static void
 530 ggc_mark_tree_hash_table_ptr (elt)
 531      void *elt;
 532 {
 533   ggc_mark_tree_hash_table (*(struct hash_table **) elt);
 534 }
 535
 536 /* Allocate a block of memory, then clear it.  */
 537 void *
 538 ggc_alloc_cleared (size)
 539      size_t size;
 540 {
 541   void *buf = ggc_alloc (size);
 542   memset (buf, 0, size);
 543   return buf;
 544 }
 545
 546 /* Print statistics that are independent of the collector in use.  */
 547 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 548                   ? (x) \
 549                   : ((x) < 1024*1024*10 \
 550                      ? (x) / 1024 \
 551                      : (x) / (1024*1024))))
 552 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 553
 554 void
 555 ggc_print_common_statistics (stream, stats)
 556      FILE *stream;
 557      ggc_statistics *stats;
 558 {
 559   int code;
 560
 561   /* Set the pointer so that during collection we will actually gather
 562      the statistics.  */
 563   ggc_stats = stats;
 564
 565   /* Then do one collection to fill in the statistics.  */
 566   ggc_collect ();
 567
 568   /* Total the statistics.  */
 569   for (code = 0; code < MAX_TREE_CODES; ++code)
 570     {
 571       stats->total_num_trees += stats->num_trees[code];
 572       stats->total_size_trees += stats->size_trees[code];
 573     }
 574   for (code = 0; code < NUM_RTX_CODE; ++code)
 575     {
 576       stats->total_num_rtxs += stats->num_rtxs[code];
 577       stats->total_size_rtxs += stats->size_rtxs[code];
 578     }
 579
 580   /* Print the statistics for trees.  */
 581   fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
 582            "Number", "Bytes", "% Total");
 583   for (code = 0; code < MAX_TREE_CODES; ++code)
 584     if (ggc_stats->num_trees[code])
 585       {
 586         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 587                  tree_code_name[code],
 588                  ggc_stats->num_trees[code],
 589                  SCALE (ggc_stats->size_trees[code]),
 590                  LABEL (ggc_stats->size_trees[code]),
 591                  (100 * ((double) ggc_stats->size_trees[code])
 592                   / ggc_stats->total_size_trees));
 593       }
 594   fprintf (stream,
 595            "%-17s%10u%16ld%c\n", "Total",
 596            ggc_stats->total_num_trees,
 597            SCALE (ggc_stats->total_size_trees),
 598            LABEL (ggc_stats->total_size_trees));
 599
 600   /* Print the statistics for RTL.  */
 601   fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
 602            "Number", "Bytes", "% Total");
 603   for (code = 0; code < NUM_RTX_CODE; ++code)
 604     if (ggc_stats->num_rtxs[code])
 605       {
 606         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
 607                  rtx_name[code],
 608                  ggc_stats->num_rtxs[code],
 609                  SCALE (ggc_stats->size_rtxs[code]),
 610                  LABEL (ggc_stats->size_rtxs[code]),
 611                  (100 * ((double) ggc_stats->size_rtxs[code])
 612                   / ggc_stats->total_size_rtxs));
 613       }
 614   fprintf (stream,
 615            "%-17s%10u%16ld%c\n", "Total",
 616            ggc_stats->total_num_rtxs,
 617            SCALE (ggc_stats->total_size_rtxs),
 618            LABEL (ggc_stats->total_size_rtxs));
 619
 620   /* Don't gather statistics any more.  */
 621   ggc_stats = NULL;
 622 }