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