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