gcc/ggc-simple.c

   1 /* Simple garbage collection for the GNU compiler.
   2    Copyright (C) 1998, 1999 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_rtx
  54 {
  55   struct ggc_rtx *chain;
  56   struct rtx_def rtx;
  57 };
  58
  59 struct ggc_rtvec
  60 {
  61   struct ggc_rtvec *chain;
  62   struct rtvec_def vec;
  63 };
  64
  65 struct ggc_tree
  66 {
  67   struct ggc_tree *chain;
  68   union tree_node tree;
  69 };
  70
  71 struct ggc_string
  72 {
  73   struct ggc_string *chain;
  74   unsigned int magic_mark;
  75   char string[1];
  76 };
  77
  78 /* A generic allocation, with an external mark bit.  */
  79
  80 struct ggc_any
  81 {
  82   struct ggc_any *chain;
  83   unsigned int magic_mark;
  84
  85   /* Make sure the data is reasonably aligned.  */
  86   union {
  87     char c;
  88     HOST_WIDE_INT i;
  89 #ifdef HAVE_LONG_DOUBLE
  90     long double d;
  91 #else
  92     double d;
  93 #endif
  94   } u;
  95 };
  96
  97 struct ggc_status
  98 {
  99   struct ggc_status *next;
 100   struct ggc_rtx *rtxs;
 101   struct ggc_rtvec *vecs;
 102   struct ggc_tree *trees;
 103   struct ggc_string *strings;
 104   struct ggc_any *anys;
 105   size_t bytes_alloced_since_gc;
 106 };
 107
 108 /* A chain of GGC contexts.  The currently active context is at the
 109    front of the chain.  */
 110 static struct ggc_status *ggc_chain;
 111
 112 /* Some statistics.  */
 113
 114 static int n_rtxs_collected;
 115 static int n_vecs_collected;
 116 static int n_trees_collected;
 117 static int n_strings_collected;
 118 static int n_anys_collected;
 119 extern int gc_time;
 120
 121 #ifdef GGC_DUMP
 122 static FILE *dump;
 123 #endif
 124
 125 /* Local function prototypes.  */
 126
 127 static void ggc_free_rtx PROTO ((struct ggc_rtx *r));
 128 static void ggc_free_rtvec PROTO ((struct ggc_rtvec *v));
 129 static void ggc_free_tree PROTO ((struct ggc_tree *t));
 130 static void ggc_free_string PROTO ((struct ggc_string *s));
 131 static void ggc_free_any PROTO ((struct ggc_any *a));
 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   gs->next->bytes_alloced_since_gc += gs->bytes_alloced_since_gc;
 209
 210   ggc_chain = gs->next;
 211   free (gs);
 212 }
 213
 214 /* These allocators are dreadfully simple, with no caching whatsoever so
 215    that Purify-like tools that do allocation versioning can catch errors.
 216    This collector is never going to go fast anyway.  */
 217
 218 rtx
 219 ggc_alloc_rtx (nslots)
 220      int nslots;
 221 {
 222   struct ggc_rtx *n;
 223   int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
 224
 225   n = (struct ggc_rtx *) xcalloc (1, size);
 226   n->chain = ggc_chain->rtxs;
 227   ggc_chain->rtxs = n;
 228
 229 #ifdef GGC_DUMP
 230   fprintf (dump, "alloc rtx %p\n", &n->rtx);
 231 #endif
 232
 233   ggc_chain->bytes_alloced_since_gc += size;
 234
 235   return &n->rtx;
 236 }
 237
 238 rtvec
 239 ggc_alloc_rtvec (nelt)
 240      int nelt;
 241 {
 242   struct ggc_rtvec *v;
 243   int size = sizeof (*v) + (nelt - 1) * sizeof (rtx);
 244
 245   v = (struct ggc_rtvec *) xcalloc (1, size);
 246   v->chain = ggc_chain->vecs;
 247   ggc_chain->vecs = v;
 248
 249 #ifdef GGC_DUMP
 250   fprintf(dump, "alloc vec %p\n", &v->vec);
 251 #endif
 252
 253   ggc_chain->bytes_alloced_since_gc += size;
 254
 255   return &v->vec;
 256 }
 257
 258 tree
 259 ggc_alloc_tree (length)
 260      int length;
 261 {
 262   struct ggc_tree *n;
 263   int size = sizeof(*n) - sizeof(n->tree) + length;
 264
 265   n = (struct ggc_tree *) xcalloc (1, size);
 266   n->chain = ggc_chain->trees;
 267   ggc_chain->trees = n;
 268
 269 #ifdef GGC_DUMP
 270   fprintf(dump, "alloc tree %p\n", &n->tree);
 271 #endif
 272
 273   ggc_chain->bytes_alloced_since_gc += size;
 274
 275   return &n->tree;
 276 }
 277
 278 char *
 279 ggc_alloc_string (contents, length)
 280      const char *contents;
 281      int length;
 282 {
 283   struct ggc_string *s;
 284   int size;
 285
 286   if (length < 0)
 287     {
 288       if (contents == NULL)
 289         return NULL;
 290       length = strlen (contents);
 291     }
 292
 293   size = (s->string - (char *)s) + length + 1;
 294   s = (struct ggc_string *) xmalloc (size);
 295   s->chain = ggc_chain->strings;
 296   s->magic_mark = GGC_STRING_MAGIC;
 297   ggc_chain->strings = s;
 298
 299   if (contents)
 300     memcpy (s->string, contents, length);
 301   s->string[length] = 0;
 302
 303 #ifdef GGC_DUMP
 304   fprintf(dump, "alloc string %p\n", &s->string);
 305 #endif
 306
 307   ggc_chain->bytes_alloced_since_gc += size;
 308
 309   return s->string;
 310 }
 311
 312 /* Like xmalloc, but allocates GC-able memory.  */
 313
 314 void *
 315 ggc_alloc (bytes)
 316      size_t bytes;
 317 {
 318   struct ggc_any *a;
 319
 320   if (bytes == 0)
 321     bytes = 1;
 322   bytes += (&((struct ggc_any *) 0)->u.c - (char *) 0);
 323
 324   a = (struct ggc_any *) xmalloc (bytes);
 325   a->chain = ggc_chain->anys;
 326   a->magic_mark = GGC_ANY_MAGIC;
 327   ggc_chain->anys = a;
 328
 329   ggc_chain->bytes_alloced_since_gc += bytes;
 330
 331   return &a->u;
 332 }
 333
 334 /* Freeing a bit of rtl is as simple as calling free.  */
 335
 336 static inline void
 337 ggc_free_rtx (r)
 338      struct ggc_rtx *r;
 339 {
 340 #ifdef GGC_DUMP
 341   fprintf (dump, "collect rtx %p\n", &r->rtx);
 342 #endif
 343 #ifdef GGC_POISON
 344   memset (r, 0xAA, sizeof(*r) + ((GET_RTX_LENGTH (r->rtx.code) -1)
 345                                  * sizeof(rtunion)));
 346 #endif
 347
 348   free (r);
 349 }
 350
 351 /* Freeing an rtvec is as simple as calling free.  */
 352
 353 static inline void
 354 ggc_free_rtvec (v)
 355      struct ggc_rtvec *v;
 356 {
 357 #ifdef GGC_DUMP
 358   fprintf(dump, "collect vec %p\n", &v->vec);
 359 #endif
 360 #ifdef GGC_POISON
 361   memset (v, 0xBB, sizeof (*v) + ((GET_NUM_ELEM (&v->vec) - 1)
 362                                   * sizeof (rtunion)));
 363 #endif
 364
 365   free (v);
 366 }
 367
 368 /* Freeing a tree node is almost, but not quite, as simple as calling free.
 369    Mostly we need to let the language clean up its lang_specific bits.  */
 370
 371 static inline void
 372 ggc_free_tree (t)
 373      struct ggc_tree *t;
 374 {
 375 #ifdef GGC_DUMP
 376   fprintf (dump, "collect tree %p\n", &t->tree);
 377 #endif
 378 #ifdef GGC_POISON
 379   memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
 380 #endif
 381
 382   free (t);
 383 }
 384
 385 /* Freeing a string is as simple as calling free.  */
 386
 387 static inline void
 388 ggc_free_string (s)
 389      struct ggc_string *s;
 390 {
 391 #ifdef GGC_DUMP
 392   fprintf(dump, "collect string %p\n", s->string);
 393 #endif
 394 #ifdef GGC_POISON
 395   s->magic_mark = 0xDDDDDDDD;
 396   s->string[0] = 0xDD;
 397 #endif
 398
 399   free (s);
 400 }
 401
 402 /* Freeing anonymous memory is as simple as calling free.  */
 403
 404 static inline void
 405 ggc_free_any (a)
 406      struct ggc_any *a;
 407 {
 408 #ifdef GGC_DUMP
 409   fprintf(dump, "collect mem %p\n", &a->u);
 410 #endif
 411 #ifdef GGC_POISON
 412   a->magic_mark = 0xEEEEEEEE;
 413 #endif
 414
 415   free (a);
 416 }
 417
 418 /* Mark a node.  */
 419
 420 int
 421 ggc_set_mark_rtx (r)
 422      rtx r;
 423 {
 424   int marked = r->gc_mark;
 425   if (! marked)
 426     r->gc_mark = 1;
 427   return marked;
 428 }
 429
 430 int
 431 ggc_set_mark_rtvec (v)
 432      rtvec v;
 433 {
 434   int marked = v->gc_mark;
 435   if (! marked)
 436     v->gc_mark = 1;
 437   return marked;
 438 }
 439
 440 int
 441 ggc_set_mark_tree (t)
 442      tree t;
 443 {
 444   int marked = t->common.gc_mark;
 445   if (! marked)
 446     t->common.gc_mark = 1;
 447   return marked;
 448 }
 449
 450 void
 451 ggc_mark_string (s)
 452      char *s;
 453 {
 454   const ptrdiff_t d = (((struct ggc_string *) 0)->string - (char *) 0);
 455   struct ggc_string *gs;
 456
 457   if (s == NULL)
 458     return;
 459
 460   gs = (struct ggc_string *)(s - d);
 461   if (IGNORE_MARK (gs->magic_mark) != GGC_STRING_MAGIC)
 462     return;   /* abort? */
 463   gs->magic_mark = GGC_STRING_MAGIC_MARK;
 464 }
 465
 466 /* Mark P, allocated with ggc_alloc.  */
 467
 468 void
 469 ggc_mark (p)
 470      void *p;
 471 {
 472   const ptrdiff_t d = (&((struct ggc_any *) 0)->u.c - (char *) 0);
 473   struct ggc_any *a;
 474
 475   if (p == NULL)
 476     return;
 477
 478   a = (struct ggc_any *) (((char*) p) - d);
 479   if (IGNORE_MARK (a->magic_mark) != GGC_ANY_MAGIC)
 480     abort ();
 481   a->magic_mark = GGC_ANY_MAGIC_MARK;
 482 }
 483
 484 /* The top level mark-and-sweep routine.  */
 485
 486 void
 487 ggc_collect ()
 488 {
 489   struct ggc_rtx *r, **rp;
 490   struct ggc_rtvec *v, **vp;
 491   struct ggc_tree *t, **tp;
 492   struct ggc_string *s, **sp;
 493   struct ggc_root *x;
 494   struct ggc_status *gs;
 495   struct ggc_any *a, **ap;
 496   int time, n_rtxs, n_trees, n_vecs, n_strings, n_anys;
 497
 498 #if !defined(ENABLE_CHECKING)
 499   /* See if it's even worth our while.  */
 500   if (ggc_chain->bytes_alloced_since_gc < 4*1024*1024)
 501     return;
 502 #endif
 503
 504   if (!quiet_flag)
 505     fputs (" {GC ", stderr);
 506
 507   time = get_run_time ();
 508
 509   /* Clean out all of the GC marks.  */
 510   for (gs = ggc_chain; gs; gs = gs->next)
 511     {
 512       for (r = gs->rtxs; r != NULL; r = r->chain)
 513         r->rtx.gc_mark = 0;
 514       for (v = gs->vecs; v != NULL; v = v->chain)
 515         v->vec.gc_mark = 0;
 516       for (t = gs->trees; t != NULL; t = t->chain)
 517         t->tree.common.gc_mark = 0;
 518       for (s = gs->strings; s != NULL; s = s->chain)
 519         s->magic_mark = GGC_STRING_MAGIC;
 520       for (a = gs->anys; a != NULL; a = a->chain)
 521         a->magic_mark = GGC_ANY_MAGIC;
 522     }
 523
 524   /* Mark through all the roots.  */
 525   for (x = roots; x != NULL; x = x->next)
 526     {
 527       char *elt = x->base;
 528       int s = x->size, n = x->nelt;
 529       void (*cb) PROTO ((void *)) = x->cb;
 530       int i;
 531
 532       for (i = 0; i < n; ++i, elt += s)
 533         (*cb)(elt);
 534     }
 535
 536   /* Sweep the resulting dead nodes.  */
 537
 538   /* The RTXs.  */
 539
 540   rp = &ggc_chain->rtxs;
 541   r = ggc_chain->rtxs;
 542   n_rtxs = 0;
 543   while (r != NULL)
 544     {
 545       struct ggc_rtx *chain = r->chain;
 546       if (!r->rtx.gc_mark)
 547         {
 548           ggc_free_rtx (r);
 549           *rp = chain;
 550           n_rtxs++;
 551         }
 552       else
 553         rp = &r->chain;
 554       r = chain;
 555     }
 556   *rp = NULL;
 557   n_rtxs_collected += n_rtxs;
 558
 559   /* The vectors.  */
 560
 561   vp = &ggc_chain->vecs;
 562   v = ggc_chain->vecs;
 563   n_vecs = 0;
 564   while (v != NULL)
 565     {
 566       struct ggc_rtvec *chain = v->chain;
 567       if (!v->vec.gc_mark)
 568         {
 569           ggc_free_rtvec (v);
 570           *vp = chain;
 571           n_vecs++;
 572         }
 573       else
 574         vp = &v->chain;
 575       v = chain;
 576     }
 577   *vp = NULL;
 578   n_vecs_collected += n_vecs;
 579
 580   /* The trees.  */
 581
 582   tp = &ggc_chain->trees;
 583   t = ggc_chain->trees;
 584   n_trees = 0;
 585   while (t != NULL)
 586     {
 587       struct ggc_tree *chain = t->chain;
 588       if (!t->tree.common.gc_mark)
 589         {
 590           ggc_free_tree (t);
 591           *tp = chain;
 592           n_trees++;
 593         }
 594       else
 595         tp = &t->chain;
 596       t = chain;
 597     }
 598   *tp = NULL;
 599   n_trees_collected += n_trees;
 600
 601   /* The strings.  */
 602
 603   sp = &ggc_chain->strings;
 604   s = ggc_chain->strings;
 605   n_strings = 0;
 606   while (s != NULL)
 607     {
 608       struct ggc_string *chain = s->chain;
 609       if (! IS_MARKED (s->magic_mark))
 610         {
 611           ggc_free_string (s);
 612           *sp = chain;
 613           n_strings++;
 614         }
 615       else
 616         sp = &s->chain;
 617       s = chain;
 618     }
 619   *sp = NULL;
 620   n_strings_collected += n_strings;
 621
 622   /* The generic data.  */
 623
 624   ap = &ggc_chain->anys;
 625   a = ggc_chain->anys;
 626   n_anys = 0;
 627   while (a != NULL)
 628     {
 629       struct ggc_any *chain = a->chain;
 630       if (! IS_MARKED (a->magic_mark))
 631         {
 632           ggc_free_any (a);
 633           *ap = chain;
 634           n_anys++;
 635         }
 636       else
 637         ap = &a->chain;
 638       a = chain;
 639     }
 640   n_anys_collected += n_anys;
 641
 642   ggc_chain->bytes_alloced_since_gc = 0;
 643
 644   time = get_run_time () - time;
 645   gc_time += time;
 646
 647   if (!quiet_flag)
 648     {
 649       time = (time + 500) / 1000;
 650       fprintf (stderr, "%dr,%dv,%dt,%ds,%da %d.%03d}", n_rtxs, n_vecs,
 651                n_trees, n_strings, n_anys, time / 1000, time % 1000);
 652     }
 653 }
 654
 655 #if 0
 656 /* GDB really should have a memory search function.  Since this is just
 657    for initial debugging, I won't even pretend to get the __data_start
 658    to work on any but alpha-dec-linux-gnu.  */
 659 static void **
 660 search_data(void **start, void *target)
 661 {
 662   extern void *__data_start[];
 663   void **_end = (void **)sbrk(0);
 664
 665   if (start == NULL)
 666     start = __data_start;
 667   while (start < _end)
 668     {
 669       if (*start == target)
 670         return start;
 671       start++;
 672     }
 673   return NULL;
 674 }
 675 #endif