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