gcc/ggc-simple.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1998 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
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GNU CC is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License 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
  18    the Free Software Foundation, 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "rtl.h"
  24 #include "tree.h"
  25 #include "ggc.h"
  26 #include "flags.h"
  27 #include "varray.h"
  28 #include "hash.h"
  29
  30 /* Debugging flags.  */
  31
  32 /* Zap memory before freeing to catch dangling pointers.  */
  33 #define GGC_POISON
  34
  35 /* Log alloc and release.  Don't enable this unless you want a
  36    really really lot of data.  */
  37 #undef GGC_DUMP
  38
  39 /* Global lists of roots, rtxs, and trees.  */
  40
  41 struct ggc_root
  42 {
  43   struct ggc_root *next;
  44   void *base;
  45   int nelt;
  46   int size;
  47   void (*cb) PROTO ((void *));
  48 };
  49
  50 static struct ggc_root *roots;
  51
  52 struct ggc_rtx
  53 {
  54   struct ggc_rtx *chain;
  55   struct rtx_def rtx;
  56 };
  57
  58 struct ggc_rtvec
  59 {
  60   struct ggc_rtvec *chain;
  61   struct rtvec_def vec;
  62 };
  63
  64 struct ggc_tree
  65 {
  66   struct ggc_tree *chain;
  67   union tree_node tree;
  68 };
  69
  70 struct ggc_string
  71 {
  72   struct ggc_string *chain;
  73   int magic_mark;
  74   char string[1];
  75 };
  76
  77 /* A generic allocation, with an external mark bit.  */
  78
  79 struct ggc_any
  80 {
  81   struct ggc_any *chain;
  82   char mark;
  83
  84   /* Make sure the data is reasonably aligned.  */
  85   union {
  86     char c;
  87     HOST_WIDE_INT i;
  88     long double d;
  89   } u;
  90 };
  91
  92 #define GGC_STRING_MAGIC        ((unsigned int)0xa1b2c3d4)
  93
  94 struct ggc_status
  95 {
  96   struct ggc_status *next;
  97   struct ggc_rtx *rtxs;
  98   struct ggc_rtvec *vecs;
  99   struct ggc_tree *trees;
 100   struct ggc_string *strings;
 101   struct ggc_any *anys;
 102   size_t bytes_alloced_since_gc;
 103 };
 104
 105 /* A chain of GGC contexts.  The currently active context is at the
 106    front of the chain.  */
 107 static struct ggc_status *ggc_chain;
 108
 109 /* Some statistics.  */
 110
 111 static int n_rtxs_collected;
 112 static int n_vecs_collected;
 113 static int n_trees_collected;
 114 static int n_strings_collected;
 115 static int n_anys_collected;
 116 extern int gc_time;
 117
 118 #ifdef GGC_DUMP
 119 static FILE *dump;
 120 #endif
 121
 122 /* Local function prototypes.  */
 123
 124 static void ggc_free_rtx PROTO ((struct ggc_rtx *r));
 125 static void ggc_free_tree PROTO ((struct ggc_tree *t));
 126 static void ggc_mark_rtx_ptr PROTO ((void *elt));
 127 static void ggc_mark_tree_ptr PROTO ((void *elt));
 128 static void ggc_mark_tree_varray_ptr PROTO ((void *elt));
 129 static void ggc_mark_tree_hash_table_ptr PROTO ((void *elt));
 130 static boolean ggc_mark_tree_hash_table_entry PROTO ((struct hash_entry *,
 131                                                       hash_table_key));
 132
 133 /* Called once to initialize the garbage collector.  */
 134
 135 void
 136 init_ggc PROTO ((void))
 137 {
 138   /* Initialize the global context.  */
 139   ggc_push_context ();
 140
 141 #ifdef GGC_DUMP
 142   dump = fopen ("zgcdump", "w");
 143   setlinebuf (dump);
 144 #endif
 145 }
 146
 147 /* Start a new GGC context.  Memory allocated in previous contexts
 148    will not be collected while the new context is active.  */
 149
 150 void
 151 ggc_push_context PROTO ((void))
 152 {
 153   struct ggc_status *gs = (struct ggc_status *) xcalloc (1, sizeof (*gs));
 154   gs->next = ggc_chain;
 155   ggc_chain = gs;
 156 }
 157
 158 /* Finish a GC context.  Any uncollected memory in the new context
 159    will be merged with the old context.  */
 160
 161 void
 162 ggc_pop_context PROTO ((void))
 163 {
 164   struct ggc_rtx *r;
 165   struct ggc_rtvec *v;
 166   struct ggc_tree *t;
 167   struct ggc_string *s;
 168   struct ggc_status *gs;
 169
 170   gs = ggc_chain;
 171
 172   r = gs->rtxs;
 173   if (r)
 174     {
 175       while (r->chain)
 176         r = r->chain;
 177       r->chain = gs->next->rtxs;
 178       gs->next->rtxs = gs->rtxs;
 179     }
 180
 181   v = gs->vecs;
 182   if (v)
 183     {
 184       while (v->chain)
 185         v = v->chain;
 186       v->chain = gs->next->vecs;
 187       gs->next->vecs = gs->vecs;
 188     }
 189
 190   t = gs->trees;
 191   if (t)
 192     {
 193       while (t->chain)
 194         t = t->chain;
 195       t->chain = gs->next->trees;
 196       gs->next->trees = gs->trees;
 197     }
 198
 199   s = gs->strings;
 200   if (s)
 201     {
 202       while (s->chain)
 203         s = s->chain;
 204       s->chain = gs->next->strings;
 205       gs->next->strings = gs->strings;
 206     }
 207
 208   ggc_chain = gs->next;
 209   free (gs);
 210 }
 211
 212 /* These allocators are dreadfully simple, with no caching whatsoever so
 213    that Purify-like tools that do allocation versioning can catch errors.
 214    This collector is never going to go fast anyway.  */
 215
 216 rtx
 217 ggc_alloc_rtx (nslots)
 218      int nslots;
 219 {
 220   struct ggc_rtx *n;
 221   int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
 222
 223   n = (struct ggc_rtx *) xcalloc (1, size);
 224   n->chain = ggc_chain->rtxs;
 225   ggc_chain->rtxs = n;
 226
 227 #ifdef GGC_DUMP
 228   fprintf (dump, "alloc rtx %p\n", &n->rtx);
 229 #endif
 230
 231   ggc_chain->bytes_alloced_since_gc += size;
 232
 233   return &n->rtx;
 234 }
 235
 236 rtvec
 237 ggc_alloc_rtvec (nelt)
 238      int nelt;
 239 {
 240   struct ggc_rtvec *v;
 241   int size = sizeof (*v) + (nelt - 1) * sizeof (rtx);
 242
 243   v = (struct ggc_rtvec *) xcalloc (1, size);
 244   v->chain = ggc_chain->vecs;
 245   ggc_chain->vecs = v;
 246
 247 #ifdef GGC_DUMP
 248   fprintf(dump, "alloc vec %p\n", &v->vec);
 249 #endif
 250
 251   ggc_chain->bytes_alloced_since_gc += size;
 252
 253   return &v->vec;
 254 }
 255
 256 tree
 257 ggc_alloc_tree (length)
 258      int length;
 259 {
 260   struct ggc_tree *n;
 261   int size = sizeof(*n) - sizeof(n->tree) + length;
 262
 263   n = (struct ggc_tree *) xcalloc (1, size);
 264   n->chain = ggc_chain->trees;
 265   ggc_chain->trees = n;
 266
 267 #ifdef GGC_DUMP
 268   fprintf(dump, "alloc tree %p\n", &n->tree);
 269 #endif
 270
 271   ggc_chain->bytes_alloced_since_gc += size;
 272
 273   return &n->tree;
 274 }
 275
 276 char *
 277 ggc_alloc_string (contents, length)
 278      const char *contents;
 279      int length;
 280 {
 281   struct ggc_string *s;
 282   int size;
 283
 284   if (length < 0)
 285     {
 286       if (contents == NULL)
 287         return NULL;
 288       length = strlen (contents);
 289     }
 290
 291   size = (s->string - (char *)s) + length + 1;
 292   s = (struct ggc_string *) xmalloc(size);
 293   s->chain = ggc_chain->strings;
 294   s->magic_mark = GGC_STRING_MAGIC;
 295   if (contents)
 296     bcopy (contents, s->string, length);
 297   s->string[length] = 0;
 298   ggc_chain->strings = s;
 299
 300 #ifdef GGC_DUMP
 301   fprintf(dump, "alloc string %p\n", &s->string);
 302 #endif
 303
 304   ggc_chain->bytes_alloced_since_gc += size;
 305
 306   return s->string;
 307 }
 308
 309 /* Like xmalloc, but allocates GC-able memory.  */
 310
 311 void *
 312 ggc_alloc (bytes)
 313      size_t bytes;
 314 {
 315   struct ggc_any *a;
 316
 317   if (bytes == 0)
 318     bytes = 1;
 319   bytes += (&((struct ggc_any *) 0)->u.c - (char *) 0);
 320
 321   a = (struct ggc_any *) xmalloc (bytes);
 322   a->chain = ggc_chain->anys;
 323   ggc_chain->anys = a;
 324
 325   return &a->u;
 326 }
 327
 328 /* Freeing a bit of rtl is as simple as calling free.  */
 329
 330 static void
 331 ggc_free_rtx (r)
 332      struct ggc_rtx *r;
 333 {
 334 #ifdef GGC_DUMP
 335   fprintf (dump, "collect rtx %p\n", &r->rtx);
 336 #endif
 337 #ifdef GGC_POISON
 338   memset (r, 0xAA, sizeof(*r) + ((GET_RTX_LENGTH (r->rtx.code) -1)
 339                                  * sizeof(rtunion)));
 340 #endif
 341
 342   free (r);
 343 }
 344
 345 /* Freeing an rtvec is as simple as calling free.  */
 346
 347 static void
 348 ggc_free_rtvec (v)
 349      struct ggc_rtvec *v;
 350 {
 351 #ifdef GGC_DUMP
 352   fprintf(dump, "collect vec %p\n", &v->vec);
 353 #endif
 354 #ifdef GGC_POISON
 355   memset (v, 0xBB, sizeof (*v) + ((GET_NUM_ELEM (&v->vec) - 1)
 356                                   * sizeof (rtunion)));
 357 #endif
 358
 359   free (v);
 360 }
 361
 362 /* Freeing a tree node is almost, but not quite, as simple as calling free.
 363    Mostly we need to let the language clean up its lang_specific bits.  */
 364
 365 static void
 366 ggc_free_tree (t)
 367      struct ggc_tree *t;
 368 {
 369   switch (TREE_CODE_CLASS (TREE_CODE (&t->tree)))
 370     {
 371     case 'd': /* A decl node.  */
 372     case 't': /* A type node.  */
 373       lang_cleanup_tree (&t->tree);
 374       break;
 375     }
 376
 377 #ifdef GGC_DUMP
 378   fprintf (dump, "collect tree %p\n", &t->tree);
 379 #endif
 380 #ifdef GGC_POISON
 381   memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
 382 #endif
 383
 384   free (t);
 385 }
 386
 387 /* Freeing a string is as simple as calling free.  */
 388
 389 static void
 390 ggc_free_string (s)
 391      struct ggc_string *s;
 392 {
 393 #ifdef GGC_DUMP
 394   fprintf(dump, "collect string %p\n", s->string);
 395 #endif
 396 #ifdef GGC_POISON
 397   s->magic_mark = 0xDDDDDDDD;
 398   s->string[0] = 0xDD;
 399 #endif
 400
 401   free (s);
 402 }
 403
 404 /* Mark a node.  */
 405
 406 void
 407 ggc_mark_rtx (r)
 408      rtx r;
 409 {
 410   const char *fmt;
 411   int i;
 412
 413   if (r == NULL_RTX || r->gc_mark)
 414     return;
 415   r->gc_mark = 1;
 416
 417   /* ??? If (some of) these are really pass-dependant info, do we have
 418      any right poking our noses in?  */
 419   switch (GET_CODE (r))
 420     {
 421     case JUMP_INSN:
 422       ggc_mark_rtx (JUMP_LABEL (r));
 423       break;
 424     case CODE_LABEL:
 425       ggc_mark_rtx (LABEL_REFS (r));
 426       break;
 427     case LABEL_REF:
 428       ggc_mark_rtx (LABEL_NEXTREF (r));
 429       ggc_mark_rtx (CONTAINING_INSN (r));
 430       break;
 431     case ADDRESSOF:
 432       ggc_mark_tree (ADDRESSOF_DECL (r));
 433       break;
 434     case CONST_DOUBLE:
 435       ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
 436       break;
 437     case NOTE:
 438       switch (NOTE_LINE_NUMBER (r))
 439         {
 440         case NOTE_INSN_RANGE_START:
 441         case NOTE_INSN_RANGE_END:
 442         case NOTE_INSN_LIVE:
 443           ggc_mark_rtx (NOTE_RANGE_INFO (r));
 444           break;
 445
 446         default:
 447           if (NOTE_LINE_NUMBER (r) >= 0)
 448             ggc_mark_string (NOTE_SOURCE_FILE (r));
 449           break;
 450         }
 451       break;
 452
 453     default:
 454       break;
 455     }
 456
 457   for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
 458     {
 459       switch (*fmt)
 460         {
 461         case 'e': case 'u':
 462           ggc_mark_rtx (XEXP (r, i));
 463           break;
 464         case 'V': case 'E':
 465           ggc_mark_rtvec (XVEC (r, i));
 466           break;
 467         case 'S': case 's':
 468           ggc_mark_string (XSTR (r, i));
 469           break;
 470         }
 471     }
 472 }
 473
 474 void
 475 ggc_mark_rtvec (v)
 476      rtvec v;
 477 {
 478   int i;
 479
 480   if (v == NULL || v->gc_mark)
 481     return;
 482   v->gc_mark = 1;
 483
 484   i = GET_NUM_ELEM (v);
 485   while (--i >= 0)
 486     ggc_mark_rtx (RTVEC_ELT (v, i));
 487 }
 488
 489 void
 490 ggc_mark_tree (t)
 491      tree t;
 492 {
 493   if (t == NULL_TREE || t->common.gc_mark)
 494     return;
 495   t->common.gc_mark = 1;
 496
 497   /* Bits from common.  */
 498   ggc_mark_tree (TREE_TYPE (t));
 499   ggc_mark_tree (TREE_CHAIN (t));
 500
 501   /* Some nodes require special handling.  */
 502   switch (TREE_CODE (t))
 503     {
 504     case TREE_LIST:
 505       ggc_mark_tree (TREE_PURPOSE (t));
 506       ggc_mark_tree (TREE_VALUE (t));
 507       return;
 508
 509     case TREE_VEC:
 510       {
 511         int i = TREE_VEC_LENGTH (t);
 512         while (--i >= 0)
 513           ggc_mark_tree (TREE_VEC_ELT (t, i));
 514         return;
 515       }
 516
 517     case SAVE_EXPR:
 518       ggc_mark_tree (TREE_OPERAND (t, 0));
 519       ggc_mark_tree (SAVE_EXPR_CONTEXT (t));
 520       ggc_mark_rtx (SAVE_EXPR_RTL (t));
 521       return;
 522
 523     case RTL_EXPR:
 524       ggc_mark_rtx (RTL_EXPR_SEQUENCE (t));
 525       ggc_mark_rtx (RTL_EXPR_RTL (t));
 526       return;
 527
 528     case CALL_EXPR:
 529       ggc_mark_tree (TREE_OPERAND (t, 0));
 530       ggc_mark_tree (TREE_OPERAND (t, 1));
 531       ggc_mark_rtx (CALL_EXPR_RTL (t));
 532       return;
 533
 534     case COMPLEX_CST:
 535       ggc_mark_tree (TREE_REALPART (t));
 536       ggc_mark_tree (TREE_IMAGPART (t));
 537       break;
 538
 539     case STRING_CST:
 540       ggc_mark_string (TREE_STRING_POINTER (t));
 541       break;
 542
 543     case PARM_DECL:
 544       ggc_mark_rtx (DECL_INCOMING_RTL (t));
 545       break;
 546
 547     case IDENTIFIER_NODE:
 548       ggc_mark_string (IDENTIFIER_POINTER (t));
 549       lang_mark_tree (t);
 550       return;
 551
 552     default:
 553       break;
 554     }
 555
 556   /* But in general we can handle them by class.  */
 557   switch (TREE_CODE_CLASS (TREE_CODE (t)))
 558     {
 559     case 'd': /* A decl node.  */
 560       ggc_mark_tree (DECL_SIZE (t));
 561       ggc_mark_tree (DECL_NAME (t));
 562       ggc_mark_tree (DECL_CONTEXT (t));
 563       ggc_mark_tree (DECL_ARGUMENTS (t));
 564       ggc_mark_tree (DECL_RESULT (t));
 565       ggc_mark_tree (DECL_INITIAL (t));
 566       ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
 567       ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
 568       ggc_mark_tree (DECL_SECTION_NAME (t));
 569       ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
 570       ggc_mark_rtx (DECL_RTL (t));
 571       ggc_mark_tree (DECL_VINDEX (t));
 572       lang_mark_tree (t);
 573       break;
 574
 575     case 't': /* A type node.  */
 576       ggc_mark_tree (TYPE_SIZE (t));
 577       ggc_mark_tree (TYPE_SIZE_UNIT (t));
 578       ggc_mark_tree (TYPE_ATTRIBUTES (t));
 579       ggc_mark_tree (TYPE_VALUES (t));
 580       ggc_mark_tree (TYPE_POINTER_TO (t));
 581       ggc_mark_tree (TYPE_REFERENCE_TO (t));
 582       ggc_mark_tree (TYPE_NAME (t));
 583       ggc_mark_tree (TYPE_MIN_VALUE (t));
 584       ggc_mark_tree (TYPE_MAX_VALUE (t));
 585       ggc_mark_tree (TYPE_NEXT_VARIANT (t));
 586       ggc_mark_tree (TYPE_MAIN_VARIANT (t));
 587       ggc_mark_tree (TYPE_BINFO (t));
 588       ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
 589       ggc_mark_tree (TYPE_CONTEXT (t));
 590       lang_mark_tree (t);
 591       break;
 592
 593     case 'b': /* A lexical block.  */
 594       ggc_mark_tree (BLOCK_VARS (t));
 595       ggc_mark_tree (BLOCK_TYPE_TAGS (t));
 596       ggc_mark_tree (BLOCK_SUBBLOCKS (t));
 597       ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
 598       ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
 599       ggc_mark_rtx (BLOCK_END_NOTE (t));
 600       break;
 601
 602     case 'c': /* A constant.  */
 603       ggc_mark_rtx (TREE_CST_RTL (t));
 604       break;
 605
 606     case 'r': case '<': case '1':
 607     case '2': case 'e': case 's': /* Expressions.  */
 608       {
 609         int i = tree_code_length[TREE_CODE (t)];
 610         while (--i >= 0)
 611           ggc_mark_tree (TREE_OPERAND (t, i));
 612         break;
 613       }
 614
 615     case 'x':
 616       lang_mark_tree (t);
 617       break;
 618     }
 619 }
 620
 621 /* Mark all the elements of the varray V, which contains trees.  */
 622
 623 void
 624 ggc_mark_tree_varray (v)
 625      varray_type v;
 626 {
 627   int i;
 628
 629   if (v)
 630     for (i = v->num_elements - 1; i >= 0; --i)
 631       ggc_mark_tree (VARRAY_TREE (v, i));
 632 }
 633
 634 /* Mark the hash table-entry HE.  It's key field is really a tree.  */
 635
 636 static boolean
 637 ggc_mark_tree_hash_table_entry (he, k)
 638      struct hash_entry *he;
 639      hash_table_key k ATTRIBUTE_UNUSED;
 640 {
 641   ggc_mark_tree ((tree) he->key);
 642   return true;
 643 }
 644
 645 /* Mark all the elements of the hash-table H, which contains trees.  */
 646
 647 void
 648 ggc_mark_tree_hash_table (ht)
 649      struct hash_table *ht;
 650 {
 651   hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
 652 }
 653
 654 void
 655 ggc_mark_string (s)
 656      char *s;
 657 {
 658   unsigned int *magic = (unsigned int *)s - 1;
 659
 660   if (s == NULL)
 661     return;
 662
 663   if ((*magic & ~(unsigned)1) != GGC_STRING_MAGIC)
 664     return;   /* abort? */
 665   *magic = GGC_STRING_MAGIC | 1;
 666 }
 667
 668 /* Mark P, allocated with ggc_alloc.  */
 669
 670 void
 671 ggc_mark (p)
 672      void *p;
 673 {
 674   struct ggc_any *a;
 675   ptrdiff_t d = (&((struct ggc_any *) 0)->u.c - (char *) 0);
 676   a = (struct ggc_any *) (((char*) p) - d);
 677   a->mark = 1;
 678 }
 679
 680 /* The top level mark-and-sweep routine.  */
 681
 682 void
 683 ggc_collect ()
 684 {
 685   struct ggc_rtx *r, **rp;
 686   struct ggc_rtvec *v, **vp;
 687   struct ggc_tree *t, **tp;
 688   struct ggc_string *s, **sp;
 689   struct ggc_root *x;
 690   struct ggc_status *gs;
 691   struct ggc_any *a, **ap;
 692   int time, n_rtxs, n_trees, n_vecs, n_strings, n_anys;
 693
 694 #ifndef ENABLE_CHECKING
 695   /* See if it's even worth our while.  */
 696   if (ggc_chain->bytes_alloced_since_gc < 64*1024)
 697     return;
 698 #endif
 699
 700   if (!quiet_flag)
 701     fputs (" {GC ", stderr);
 702
 703   time = get_run_time ();
 704
 705   /* Clean out all of the GC marks.  */
 706   for (gs = ggc_chain; gs; gs = gs->next)
 707     {
 708       for (r = gs->rtxs; r != NULL; r = r->chain)
 709         r->rtx.gc_mark = 0;
 710       for (v = gs->vecs; v != NULL; v = v->chain)
 711         v->vec.gc_mark = 0;
 712       for (t = gs->trees; t != NULL; t = t->chain)
 713         t->tree.common.gc_mark = 0;
 714       for (s = gs->strings; s != NULL; s = s->chain)
 715         s->magic_mark = GGC_STRING_MAGIC;
 716       for (a = gs->anys; a != NULL; a = a->chain)
 717         a->mark = 0;
 718     }
 719
 720   /* Mark through all the roots.  */
 721   for (x = roots; x != NULL; x = x->next)
 722     {
 723       char *elt = x->base;
 724       int s = x->size, n = x->nelt;
 725       void (*cb) PROTO ((void *)) = x->cb;
 726       int i;
 727
 728       for (i = 0; i < n; ++i, elt += s)
 729         (*cb)(elt);
 730     }
 731
 732   /* Sweep the resulting dead nodes.  */
 733
 734   /* The RTXs.  */
 735
 736   rp = &ggc_chain->rtxs;
 737   r = ggc_chain->rtxs;
 738   n_rtxs = 0;
 739   while (r != NULL)
 740     {
 741       struct ggc_rtx *chain = r->chain;
 742       if (!r->rtx.gc_mark)
 743         {
 744           ggc_free_rtx (r);
 745           *rp = chain;
 746           n_rtxs++;
 747         }
 748       else
 749         rp = &r->chain;
 750       r = chain;
 751     }
 752   *rp = NULL;
 753   n_rtxs_collected += n_rtxs;
 754
 755   /* The vectors.  */
 756
 757   vp = &ggc_chain->vecs;
 758   v = ggc_chain->vecs;
 759   n_vecs = 0;
 760   while (v != NULL)
 761     {
 762       struct ggc_rtvec *chain = v->chain;
 763       if (!v->vec.gc_mark)
 764         {
 765           ggc_free_rtvec (v);
 766           *vp = chain;
 767           n_vecs++;
 768         }
 769       else
 770         vp = &v->chain;
 771       v = chain;
 772     }
 773   *vp = NULL;
 774   n_vecs_collected += n_vecs;
 775
 776   /* The trees.  */
 777
 778   tp = &ggc_chain->trees;
 779   t = ggc_chain->trees;
 780   n_trees = 0;
 781   while (t != NULL)
 782     {
 783       struct ggc_tree *chain = t->chain;
 784       if (!t->tree.common.gc_mark)
 785         {
 786           ggc_free_tree (t);
 787           *tp = chain;
 788           n_trees++;
 789         }
 790       else
 791         tp = &t->chain;
 792       t = chain;
 793     }
 794   *tp = NULL;
 795   n_trees_collected += n_trees;
 796
 797   /* The strings.  */
 798
 799   sp = &ggc_chain->strings;
 800   s = ggc_chain->strings;
 801   n_strings = 0;
 802   while (s != NULL)
 803     {
 804       struct ggc_string *chain = s->chain;
 805       if (!(s->magic_mark & 1))
 806         {
 807           ggc_free_string (s);
 808           *sp = chain;
 809           n_strings++;
 810         }
 811       else
 812         sp = &s->chain;
 813       s = chain;
 814     }
 815   *sp = NULL;
 816   n_strings_collected += n_strings;
 817
 818   /* The generic data.  */
 819
 820   ap = &ggc_chain->anys;
 821   a = ggc_chain->anys;
 822   n_anys = 0;
 823   while (a != NULL)
 824     {
 825       struct ggc_any *chain = a->chain;
 826       if (!a->mark)
 827         {
 828           free (a);
 829           *ap = chain;
 830           n_anys++;
 831         }
 832       else
 833         ap = &a->chain;
 834       a = chain;
 835     }
 836   n_anys_collected += n_anys;
 837
 838   ggc_chain->bytes_alloced_since_gc = 0;
 839
 840   time = get_run_time () - time;
 841   gc_time += time;
 842
 843   if (!quiet_flag)
 844     {
 845       time = (time + 500) / 1000;
 846       fprintf (stderr, "%dr,%dv,%dt,%ds,%da %d.%03d}", n_rtxs, n_vecs,
 847                n_trees, n_strings, n_anys, time / 1000, time % 1000);
 848     }
 849 }
 850
 851 /* Manipulate global roots that are needed between calls to gc.  */
 852
 853 void
 854 ggc_add_root (base, nelt, size, cb)
 855      void *base;
 856      int nelt, size;
 857      void (*cb) PROTO ((void *));
 858 {
 859   struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof(*x));
 860
 861   x->next = roots;
 862   x->base = base;
 863   x->nelt = nelt;
 864   x->size = size;
 865   x->cb = cb;
 866
 867   roots = x;
 868 }
 869
 870 void
 871 ggc_add_rtx_root (base, nelt)
 872      rtx *base;
 873      int nelt;
 874 {
 875   ggc_add_root (base, nelt, sizeof(rtx), ggc_mark_rtx_ptr);
 876 }
 877
 878 void
 879 ggc_add_tree_root (base, nelt)
 880      tree *base;
 881      int nelt;
 882 {
 883   ggc_add_root (base, nelt, sizeof(tree), ggc_mark_tree_ptr);
 884 }
 885
 886 /* Add V (a varray full of trees) to the list of GC roots.  */
 887
 888 void
 889 ggc_add_tree_varray_root (base, nelt)
 890      varray_type *base;
 891      int nelt;
 892 {
 893   ggc_add_root (base, nelt, sizeof (varray_type),
 894                 ggc_mark_tree_varray_ptr);
 895 }
 896
 897 /* Add HT (a hash-table where ever key is a tree) to the list of GC
 898    roots.  */
 899
 900 void
 901 ggc_add_tree_hash_table_root (base, nelt)
 902      struct hash_table **base;
 903      int nelt;
 904 {
 905   ggc_add_root (base, nelt, sizeof (struct hash_table *),
 906                 ggc_mark_tree_hash_table_ptr);
 907 }
 908
 909 void
 910 ggc_del_root (base)
 911      void *base;
 912 {
 913   struct ggc_root *x, **p;
 914
 915   p = &roots, x = roots;
 916   while (x)
 917     {
 918       if (x->base == base)
 919         {
 920           *p = x->next;
 921           free (x);
 922           return;
 923         }
 924       p = &x->next;
 925       x = x->next;
 926     }
 927
 928   abort();
 929 }
 930
 931 static void
 932 ggc_mark_rtx_ptr (elt)
 933      void *elt;
 934 {
 935   ggc_mark_rtx (*(rtx *)elt);
 936 }
 937
 938 static void
 939 ggc_mark_tree_ptr (elt)
 940      void *elt;
 941 {
 942   ggc_mark_tree (*(tree *)elt);
 943 }
 944
 945 /* Type-correct function to pass to ggc_add_root.  It just forwards
 946    ELT (which is really a varray_type *) to ggc_mark_tree_varray.  */
 947
 948 static void
 949 ggc_mark_tree_varray_ptr (elt)
 950      void *elt;
 951 {
 952   ggc_mark_tree_varray (*(varray_type *)elt);
 953 }
 954
 955 /* Type-correct function to pass to ggc_add_root.  It just forwards
 956    ELT (which is really a struct hash_table **) to
 957    ggc_mark_tree_hash_table.  */
 958
 959 static void
 960 ggc_mark_tree_hash_table_ptr (elt)
 961      void *elt;
 962 {
 963   ggc_mark_tree_hash_table (*(struct hash_table **) elt);
 964 }
 965
 966 #if 0
 967 /* GDB really should have a memory search function.  Since this is just
 968    for initial debugging, I won't even pretend to get the __data_start
 969    to work on any but alpha-dec-linux-gnu.  */
 970 static void **
 971 search_data(void **start, void *target)
 972 {
 973   extern void *__data_start[];
 974   void **_end = (void **)sbrk(0);
 975
 976   if (start == NULL)
 977     start = __data_start;
 978   while (start < _end)
 979     {
 980       if (*start == target)
 981         return start;
 982       start++;
 983     }
 984   return NULL;
 985 }
 986 #endif