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