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 /* Constants for general use.  */
  52
  53 char *empty_string;
  54
  55 /* Global lists of roots, rtxs, and trees.  */
  56
  57 struct ggc_rtx
  58 {
  59   struct ggc_rtx *chain;
  60   struct rtx_def rtx;
  61 };
  62
  63 struct ggc_rtvec
  64 {
  65   struct ggc_rtvec *chain;
  66   struct rtvec_def vec;
  67 };
  68
  69 struct ggc_tree
  70 {
  71   struct ggc_tree *chain;
  72   union tree_node tree;
  73 };
  74
  75 struct ggc_string
  76 {
  77   struct ggc_string *chain;
  78   unsigned int magic_mark;
  79   char string[1];
  80 };
  81
  82 /* A generic allocation, with an external mark bit.  */
  83
  84 struct ggc_any
  85 {
  86   struct ggc_any *chain;
  87   unsigned int magic_mark;
  88
  89   /* Make sure the data is reasonably aligned.  */
  90   union {
  91     char c;
  92     HOST_WIDE_INT i;
  93 #ifdef HAVE_LONG_DOUBLE
  94     long double d;
  95 #else
  96     double d;
  97 #endif
  98   } u;
  99 };
 100
 101 struct ggc_status
 102 {
 103   struct ggc_status *next;
 104   struct ggc_rtx *rtxs;
 105   struct ggc_rtvec *vecs;
 106   struct ggc_tree *trees;
 107   struct ggc_string *strings;
 108   struct ggc_any *anys;
 109   size_t bytes_alloced_since_gc;
 110 };
 111
 112 /* A chain of GGC contexts.  The currently active context is at the
 113    front of the chain.  */
 114 static struct ggc_status *ggc_chain;
 115
 116 /* Some statistics.  */
 117
 118 static int n_rtxs_collected;
 119 static int n_vecs_collected;
 120 static int n_trees_collected;
 121 static int n_strings_collected;
 122 static int n_anys_collected;
 123 extern int gc_time;
 124
 125 #ifdef GGC_DUMP
 126 static FILE *dump;
 127 #endif
 128
 129 /* Local function prototypes.  */
 130
 131 static void ggc_free_rtx PROTO ((struct ggc_rtx *r));
 132 static void ggc_free_rtvec PROTO ((struct ggc_rtvec *v));
 133 static void ggc_free_tree PROTO ((struct ggc_tree *t));
 134 static void ggc_free_string PROTO ((struct ggc_string *s));
 135 static void ggc_free_any PROTO ((struct ggc_any *a));
 136
 137 /* Called once to initialize the garbage collector.  */
 138
 139 void
 140 init_ggc PROTO ((void))
 141 {
 142   /* Initialize the global context.  */
 143   ggc_push_context ();
 144
 145 #ifdef GGC_DUMP
 146   dump = fopen ("zgcdump", "w");
 147   setlinebuf (dump);
 148 #endif
 149
 150   ggc_alloc_string ("", 0);
 151   ggc_add_string_root (&empty_string, 1);
 152 }
 153
 154 /* Start a new GGC context.  Memory allocated in previous contexts
 155    will not be collected while the new context is active.  */
 156
 157 void
 158 ggc_push_context PROTO ((void))
 159 {
 160   struct ggc_status *gs = (struct ggc_status *) xcalloc (1, sizeof (*gs));
 161   gs->next = ggc_chain;
 162   ggc_chain = gs;
 163 }
 164
 165 /* Finish a GC context.  Any uncollected memory in the new context
 166    will be merged with the old context.  */
 167
 168 void
 169 ggc_pop_context PROTO ((void))
 170 {
 171   struct ggc_rtx *r;
 172   struct ggc_rtvec *v;
 173   struct ggc_tree *t;
 174   struct ggc_string *s;
 175   struct ggc_status *gs;
 176
 177   gs = ggc_chain;
 178
 179   r = gs->rtxs;
 180   if (r)
 181     {
 182       while (r->chain)
 183         r = r->chain;
 184       r->chain = gs->next->rtxs;
 185       gs->next->rtxs = gs->rtxs;
 186     }
 187
 188   v = gs->vecs;
 189   if (v)
 190     {
 191       while (v->chain)
 192         v = v->chain;
 193       v->chain = gs->next->vecs;
 194       gs->next->vecs = gs->vecs;
 195     }
 196
 197   t = gs->trees;
 198   if (t)
 199     {
 200       while (t->chain)
 201         t = t->chain;
 202       t->chain = gs->next->trees;
 203       gs->next->trees = gs->trees;
 204     }
 205
 206   s = gs->strings;
 207   if (s)
 208     {
 209       while (s->chain)
 210         s = s->chain;
 211       s->chain = gs->next->strings;
 212       gs->next->strings = gs->strings;
 213     }
 214
 215   gs->next->bytes_alloced_since_gc += gs->bytes_alloced_since_gc;
 216
 217   ggc_chain = gs->next;
 218   free (gs);
 219 }
 220
 221 /* These allocators are dreadfully simple, with no caching whatsoever so
 222    that Purify-like tools that do allocation versioning can catch errors.
 223    This collector is never going to go fast anyway.  */
 224
 225 rtx
 226 ggc_alloc_rtx (nslots)
 227      int nslots;
 228 {
 229   struct ggc_rtx *n;
 230   int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
 231
 232   n = (struct ggc_rtx *) xcalloc (1, size);
 233   n->chain = ggc_chain->rtxs;
 234   ggc_chain->rtxs = n;
 235
 236 #ifdef GGC_DUMP
 237   fprintf (dump, "alloc rtx %p\n", &n->rtx);
 238 #endif
 239
 240   ggc_chain->bytes_alloced_since_gc += size;
 241
 242   return &n->rtx;
 243 }
 244
 245 rtvec
 246 ggc_alloc_rtvec (nelt)
 247      int nelt;
 248 {
 249   struct ggc_rtvec *v;
 250   int size = sizeof (*v) + (nelt - 1) * sizeof (rtx);
 251
 252   v = (struct ggc_rtvec *) xcalloc (1, size);
 253   v->chain = ggc_chain->vecs;
 254   ggc_chain->vecs = v;
 255
 256 #ifdef GGC_DUMP
 257   fprintf(dump, "alloc vec %p\n", &v->vec);
 258 #endif
 259
 260   ggc_chain->bytes_alloced_since_gc += size;
 261
 262   return &v->vec;
 263 }
 264
 265 tree
 266 ggc_alloc_tree (length)
 267      int length;
 268 {
 269   struct ggc_tree *n;
 270   int size = sizeof(*n) - sizeof(n->tree) + length;
 271
 272   n = (struct ggc_tree *) xcalloc (1, size);
 273   n->chain = ggc_chain->trees;
 274   ggc_chain->trees = n;
 275
 276 #ifdef GGC_DUMP
 277   fprintf(dump, "alloc tree %p\n", &n->tree);
 278 #endif
 279
 280   ggc_chain->bytes_alloced_since_gc += size;
 281
 282   return &n->tree;
 283 }
 284
 285 char *
 286 ggc_alloc_string (contents, length)
 287      const char *contents;
 288      int length;
 289 {
 290   struct ggc_string *s;
 291   int size;
 292
 293   if (length < 0)
 294     {
 295       if (contents == NULL)
 296         return NULL;
 297       length = strlen (contents);
 298     }
 299
 300   size = (s->string - (char *)s) + length + 1;
 301   s = (struct ggc_string *) xmalloc (size);
 302   s->chain = ggc_chain->strings;
 303   s->magic_mark = GGC_STRING_MAGIC;
 304   ggc_chain->strings = s;
 305
 306   if (contents)
 307     memcpy (s->string, contents, length);
 308   s->string[length] = 0;
 309
 310 #ifdef GGC_DUMP
 311   fprintf(dump, "alloc string %p\n", &s->string);
 312 #endif
 313
 314   ggc_chain->bytes_alloced_since_gc += size;
 315
 316   return s->string;
 317 }
 318
 319 /* Like xmalloc, but allocates GC-able memory.  */
 320
 321 void *
 322 ggc_alloc (bytes)
 323      size_t bytes;
 324 {
 325   struct ggc_any *a;
 326
 327   if (bytes == 0)
 328     bytes = 1;
 329   bytes += (&((struct ggc_any *) 0)->u.c - (char *) 0);
 330
 331   a = (struct ggc_any *) xmalloc (bytes);
 332   a->chain = ggc_chain->anys;
 333   a->magic_mark = GGC_ANY_MAGIC;
 334   ggc_chain->anys = a;
 335
 336   ggc_chain->bytes_alloced_since_gc += bytes;
 337
 338   return &a->u;
 339 }
 340
 341 /* Freeing a bit of rtl is as simple as calling free.  */
 342
 343 static inline void
 344 ggc_free_rtx (r)
 345      struct ggc_rtx *r;
 346 {
 347 #ifdef GGC_DUMP
 348   fprintf (dump, "collect rtx %p\n", &r->rtx);
 349 #endif
 350 #ifdef GGC_POISON
 351   memset (r, 0xAA, sizeof(*r) + ((GET_RTX_LENGTH (r->rtx.code) -1)
 352                                  * sizeof(rtunion)));
 353 #endif
 354
 355   free (r);
 356 }
 357
 358 /* Freeing an rtvec is as simple as calling free.  */
 359
 360 static inline void
 361 ggc_free_rtvec (v)
 362      struct ggc_rtvec *v;
 363 {
 364 #ifdef GGC_DUMP
 365   fprintf(dump, "collect vec %p\n", &v->vec);
 366 #endif
 367 #ifdef GGC_POISON
 368   memset (v, 0xBB, sizeof (*v) + ((GET_NUM_ELEM (&v->vec) - 1)
 369                                   * sizeof (rtx)));
 370 #endif
 371
 372   free (v);
 373 }
 374
 375 /* Freeing a tree node is almost, but not quite, as simple as calling free.
 376    Mostly we need to let the language clean up its lang_specific bits.  */
 377
 378 static inline void
 379 ggc_free_tree (t)
 380      struct ggc_tree *t;
 381 {
 382 #ifdef GGC_DUMP
 383   fprintf (dump, "collect tree %p\n", &t->tree);
 384 #endif
 385 #ifdef GGC_POISON
 386   memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
 387 #endif
 388
 389   free (t);
 390 }
 391
 392 /* Freeing a string is as simple as calling free.  */
 393
 394 static inline void
 395 ggc_free_string (s)
 396      struct ggc_string *s;
 397 {
 398 #ifdef GGC_DUMP
 399   fprintf(dump, "collect string %p\n", s->string);
 400 #endif
 401 #ifdef GGC_POISON
 402   s->magic_mark = 0xDDDDDDDD;
 403   s->string[0] = 0xDD;
 404 #endif
 405
 406   free (s);
 407 }
 408
 409 /* Freeing anonymous memory is as simple as calling free.  */
 410
 411 static inline void
 412 ggc_free_any (a)
 413      struct ggc_any *a;
 414 {
 415 #ifdef GGC_DUMP
 416   fprintf(dump, "collect mem %p\n", &a->u);
 417 #endif
 418 #ifdef GGC_POISON
 419   a->magic_mark = 0xEEEEEEEE;
 420 #endif
 421
 422   free (a);
 423 }
 424
 425 /* Mark a node.  */
 426
 427 int
 428 ggc_set_mark_rtx (r)
 429      rtx r;
 430 {
 431   int marked = r->gc_mark;
 432   if (! marked)
 433     r->gc_mark = 1;
 434   return marked;
 435 }
 436
 437 int
 438 ggc_set_mark_rtvec (v)
 439      rtvec v;
 440 {
 441   int marked = v->gc_mark;
 442   if (! marked)
 443     v->gc_mark = 1;
 444   return marked;
 445 }
 446
 447 int
 448 ggc_set_mark_tree (t)
 449      tree t;
 450 {
 451   int marked = t->common.gc_mark;
 452   if (! marked)
 453     t->common.gc_mark = 1;
 454   return marked;
 455 }
 456
 457 void
 458 ggc_mark_string (s)
 459      char *s;
 460 {
 461   const ptrdiff_t d = (((struct ggc_string *) 0)->string - (char *) 0);
 462   struct ggc_string *gs;
 463
 464   if (s == NULL)
 465     return;
 466
 467   gs = (struct ggc_string *)(s - d);
 468   if (IGNORE_MARK (gs->magic_mark) != GGC_STRING_MAGIC)
 469     return;   /* abort? */
 470   gs->magic_mark = GGC_STRING_MAGIC_MARK;
 471 }
 472
 473 /* Mark P, allocated with ggc_alloc.  */
 474
 475 void
 476 ggc_mark (p)
 477      void *p;
 478 {
 479   const ptrdiff_t d = (&((struct ggc_any *) 0)->u.c - (char *) 0);
 480   struct ggc_any *a;
 481
 482   if (p == NULL)
 483     return;
 484
 485   a = (struct ggc_any *) (((char*) p) - d);
 486   if (IGNORE_MARK (a->magic_mark) != GGC_ANY_MAGIC)
 487     abort ();
 488   a->magic_mark = GGC_ANY_MAGIC_MARK;
 489 }
 490
 491 /* The top level mark-and-sweep routine.  */
 492
 493 void
 494 ggc_collect ()
 495 {
 496   struct ggc_rtx *r, **rp;
 497   struct ggc_rtvec *v, **vp;
 498   struct ggc_tree *t, **tp;
 499   struct ggc_string *s, **sp;
 500   struct ggc_status *gs;
 501   struct ggc_any *a, **ap;
 502   int time, n_rtxs, n_trees, n_vecs, n_strings, n_anys;
 503
 504 #if !defined(ENABLE_CHECKING)
 505   /* See if it's even worth our while.  */
 506   if (ggc_chain->bytes_alloced_since_gc < 4*1024*1024)
 507     return;
 508 #endif
 509
 510   if (!quiet_flag)
 511     fputs (" {GC ", stderr);
 512
 513   time = get_run_time ();
 514
 515   /* Clean out all of the GC marks.  */
 516   for (gs = ggc_chain; gs; gs = gs->next)
 517     {
 518       for (r = gs->rtxs; r != NULL; r = r->chain)
 519         r->rtx.gc_mark = 0;
 520       for (v = gs->vecs; v != NULL; v = v->chain)
 521         v->vec.gc_mark = 0;
 522       for (t = gs->trees; t != NULL; t = t->chain)
 523         t->tree.common.gc_mark = 0;
 524       for (s = gs->strings; s != NULL; s = s->chain)
 525         s->magic_mark = GGC_STRING_MAGIC;
 526       for (a = gs->anys; a != NULL; a = a->chain)
 527         a->magic_mark = GGC_ANY_MAGIC;
 528     }
 529
 530   ggc_mark_roots ();
 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