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
  28 /* Debugging flags.  */
  29 #undef GGC_DUMP
  30 #define GGC_POISON
  31
  32 /* Global lists of roots, rtxs, and trees.  */
  33
  34 struct ggc_root
  35 {
  36   struct ggc_root *next;
  37   void *base;
  38   int nelt;
  39   int size;
  40   void (*cb)(void *);
  41 };
  42
  43 static struct ggc_root *roots;
  44
  45 struct ggc_rtx
  46 {
  47   struct ggc_rtx *chain;
  48   struct rtx_def rtx;
  49 };
  50
  51 static struct ggc_rtx *rtxs;
  52
  53 struct ggc_rtvec
  54 {
  55   struct ggc_rtvec *chain;
  56   struct rtvec_def vec;
  57 };
  58
  59 static struct ggc_rtvec *vecs;
  60
  61 struct ggc_tree
  62 {
  63   struct ggc_tree *chain;
  64   union tree_node tree;
  65 };
  66
  67 static struct ggc_tree *trees;
  68
  69 struct ggc_string
  70 {
  71   struct ggc_string *chain;
  72   int magic_mark;
  73   char string[1];
  74 };
  75
  76 #define GGC_STRING_MAGIC        ((unsigned int)0xa1b2c3d4)
  77
  78 static struct ggc_string *strings;
  79
  80 /* Some statistics.  */
  81
  82 static int n_rtxs_collected;
  83 static int n_vecs_collected;
  84 static int n_trees_collected;
  85 static int n_strings_collected;
  86 static int bytes_alloced_since_gc;
  87 extern int gc_time;
  88
  89 #ifdef GGC_DUMP
  90 static FILE *dump;
  91 #endif
  92
  93 /* Local function prototypes.  */
  94
  95 static void ggc_free_rtx PROTO ((struct ggc_rtx *r));
  96 static void ggc_free_tree PROTO ((struct ggc_tree *t));
  97 static void ggc_mark_rtx_ptr PROTO ((void *elt));
  98 static void ggc_mark_tree_ptr PROTO ((void *elt));
  99
 100 /* These allocators are dreadfully simple, with no caching whatsoever so
 101    that Purify-like tools that do allocation versioning can catch errors.
 102    This collector is never going to go fast anyway.  */
 103
 104 rtx
 105 ggc_alloc_rtx (nslots)
 106      int nslots;
 107 {
 108   struct ggc_rtx *n;
 109   int size = sizeof(*n) + (nslots-1) * sizeof(rtunion);
 110
 111   n = (struct ggc_rtx *) xmalloc (size);
 112   bzero ((char *) n, size);
 113   n->chain = rtxs;
 114   rtxs = n;
 115
 116 #ifdef GGC_DUMP
 117   fprintf (dump, "alloc rtx %p\n", &n->rtx);
 118 #endif
 119
 120   bytes_alloced_since_gc += size;
 121
 122   return &n->rtx;
 123 }
 124
 125 rtvec
 126 ggc_alloc_rtvec (nelt)
 127      int nelt;
 128 {
 129   struct ggc_rtvec *v;
 130   int size = sizeof (*v) + (nelt - 1) * sizeof (rtunion);
 131
 132   v = (struct ggc_rtvec *) xmalloc (size);
 133   bzero ((char *) v, size);
 134   v->chain = vecs;
 135   vecs = v;
 136
 137 #ifdef GGC_DUMP
 138   fprintf(dump, "alloc vec %p\n", &v->vec);
 139 #endif
 140
 141   bytes_alloced_since_gc += size;
 142
 143   return &v->vec;
 144 }
 145
 146 tree
 147 ggc_alloc_tree (length)
 148      int length;
 149 {
 150   struct ggc_tree *n;
 151   int size = sizeof(*n) - sizeof(n->tree) + length;
 152
 153   n = (struct ggc_tree *) xmalloc (size);
 154   bzero ((char *) n, size);
 155   n->chain = trees;
 156   trees = n;
 157
 158 #ifdef GGC_DUMP
 159   fprintf(dump, "alloc tree %p\n", &n->tree);
 160 #endif
 161
 162   bytes_alloced_since_gc += size;
 163
 164   return &n->tree;
 165 }
 166
 167 char *
 168 ggc_alloc_string (contents, length)
 169      const char *contents;
 170      int length;
 171 {
 172   struct ggc_string *s;
 173   int size;
 174
 175   if (length < 0)
 176     {
 177       if (contents == NULL)
 178         return NULL;
 179       length = strlen (contents);
 180     }
 181
 182   size = (s->string - (char *)s) + length + 1;
 183   s = (struct ggc_string *) xmalloc(size);
 184   s->chain = strings;
 185   s->magic_mark = GGC_STRING_MAGIC;
 186   if (contents)
 187     bcopy (contents, s->string, length);
 188   s->string[length] = 0;
 189   strings = s;
 190
 191 #ifdef GGC_DUMP
 192   fprintf(dump, "alloc string %p\n", &n->tree);
 193 #endif
 194
 195   bytes_alloced_since_gc += size;
 196
 197   return s->string;
 198 }
 199
 200
 201 /* Freeing a bit of rtl isn't quite as simple as calling free, there are
 202    a few associated bits that might need freeing as well.  */
 203
 204 static void
 205 ggc_free_rtx (r)
 206      struct ggc_rtx *r;
 207 {
 208 #ifdef GGC_DUMP
 209   fprintf (dump, "collect rtx %p\n", &r->rtx);
 210 #endif
 211 #ifdef GGC_POISON
 212   memset (r, 0xAA, sizeof(*r));
 213 #endif
 214
 215   free (r);
 216 }
 217
 218 /* Freeing an rtvec is as simple as calling free.  */
 219
 220 static void
 221 ggc_free_rtvec (v)
 222      struct ggc_rtvec *v;
 223 {
 224 #ifdef GGC_DUMP
 225   fprintf(dump, "collect vec %p\n", &v->vec);
 226 #endif
 227 #ifdef GGC_POISON
 228   memset (v, 0xBB, sizeof (*v) + ((GET_NUM_ELEM (&v->vec) - 1)
 229                                   * sizeof (rtunion)));
 230 #endif
 231
 232   free (v);
 233 }
 234
 235 /* Freeing a tree node is almost, but not quite, as simple as calling free.
 236    Mostly we need to let the language clean up its lang_specific bits.  */
 237
 238 static void
 239 ggc_free_tree (t)
 240      struct ggc_tree *t;
 241 {
 242   switch (TREE_CODE_CLASS (TREE_CODE (&t->tree)))
 243     {
 244     case 'd': /* A decl node.  */
 245     case 't': /* A type node.  */
 246       lang_cleanup_tree (&t->tree);
 247       break;
 248     }
 249
 250 #ifdef GGC_DUMP
 251   fprintf (dump, "collect tree %p\n", &t->tree);
 252 #endif
 253 #ifdef GGC_POISON
 254   memset(&t->tree.common, 0xCC, sizeof(t->tree.common));
 255 #endif
 256
 257   free (t);
 258 }
 259
 260 /* Freeing a string is as simple as calling free.  */
 261
 262 static void
 263 ggc_free_string (s)
 264      struct ggc_string *s;
 265 {
 266 #ifdef GGC_DUMP
 267   fprintf(dump, "collect string %p\n", s->string);
 268 #endif
 269 #ifdef GGC_POISON
 270   s->magic_mark = 0xDDDDDDDD;
 271   s->string[0] = 0xDD;
 272 #endif
 273
 274   free (s);
 275 }
 276
 277 /* Mark a node.  */
 278
 279 void
 280 ggc_mark_rtx (r)
 281      rtx r;
 282 {
 283   const char *fmt;
 284   int i;
 285
 286   if (r == NULL_RTX || r->gc_mark)
 287     return;
 288   r->gc_mark = 1;
 289
 290   /* ??? If (some of) these are really pass-dependant info, do we have
 291      any right poking our noses in?  */
 292   switch (GET_CODE (r))
 293     {
 294     case JUMP_INSN:
 295       ggc_mark_rtx (JUMP_LABEL (r));
 296       break;
 297     case CODE_LABEL:
 298       ggc_mark_rtx (LABEL_REFS (r));
 299       break;
 300     case LABEL_REF:
 301       ggc_mark_rtx (LABEL_NEXTREF (r));
 302       ggc_mark_rtx (CONTAINING_INSN (r));
 303       break;
 304     case ADDRESSOF:
 305       ggc_mark_tree (ADDRESSOF_DECL (r));
 306       break;
 307     case CONST_DOUBLE:
 308       ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
 309       break;
 310
 311     default:
 312       break;
 313     }
 314
 315   for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
 316     {
 317       switch (*fmt)
 318         {
 319         case 'e': case 'u':
 320           ggc_mark_rtx (XEXP (r, i));
 321           break;
 322         case 'V': case 'E':
 323           ggc_mark_rtvec (XVEC (r, i));
 324           break;
 325         case 'S': case 's':
 326           ggc_mark_string (XSTR (r, i));
 327           break;
 328         }
 329     }
 330 }
 331
 332 void
 333 ggc_mark_rtvec (v)
 334      rtvec v;
 335 {
 336   int i;
 337
 338   if (v == NULL || v->gc_mark)
 339     return;
 340   v->gc_mark = 1;
 341
 342   i = GET_NUM_ELEM (v);
 343   while (--i >= 0)
 344     ggc_mark_rtx (RTVEC_ELT (v, i));
 345 }
 346
 347 void
 348 ggc_mark_tree (t)
 349      tree t;
 350 {
 351   if (t == NULL_TREE || t->common.gc_mark)
 352     return;
 353   t->common.gc_mark = 1;
 354
 355   /* Bits from common.  */
 356   ggc_mark_tree (TREE_TYPE (t));
 357   ggc_mark_tree (TREE_CHAIN (t));
 358
 359   /* Some nodes require special handling.  */
 360   switch (TREE_CODE (t))
 361     {
 362     case TREE_LIST:
 363       ggc_mark_tree (TREE_PURPOSE (t));
 364       ggc_mark_tree (TREE_VALUE (t));
 365       return;
 366
 367     case TREE_VEC:
 368       {
 369         int i = TREE_VEC_LENGTH (t);
 370         while (--i >= 0)
 371           ggc_mark_tree (TREE_VEC_ELT (t, i));
 372         return;
 373       }
 374
 375     case SAVE_EXPR:
 376       ggc_mark_tree (TREE_OPERAND (t, 0));
 377       ggc_mark_tree (SAVE_EXPR_CONTEXT (t));
 378       ggc_mark_rtx (SAVE_EXPR_RTL (t));
 379       return;
 380
 381     case RTL_EXPR:
 382       ggc_mark_rtx (RTL_EXPR_SEQUENCE (t));
 383       ggc_mark_rtx (RTL_EXPR_RTL (t));
 384       return;
 385
 386     case CALL_EXPR:
 387       ggc_mark_tree (TREE_OPERAND (t, 0));
 388       ggc_mark_tree (TREE_OPERAND (t, 1));
 389       ggc_mark_rtx (CALL_EXPR_RTL (t));
 390       return;
 391
 392     case COMPLEX_CST:
 393       ggc_mark_tree (TREE_REALPART (t));
 394       ggc_mark_tree (TREE_IMAGPART (t));
 395       break;
 396
 397     case STRING_CST:
 398       ggc_mark_string (TREE_STRING_POINTER (t));
 399       break;
 400
 401     case PARM_DECL:
 402       ggc_mark_rtx (DECL_INCOMING_RTL (t));
 403       break;
 404
 405     case IDENTIFIER_NODE:
 406       ggc_mark_string (IDENTIFIER_POINTER (t));
 407       lang_mark_tree (t);
 408       return;
 409
 410     default:
 411       break;
 412     }
 413
 414   /* But in general we can handle them by class.  */
 415   switch (TREE_CODE_CLASS (TREE_CODE (t)))
 416     {
 417     case 'd': /* A decl node.  */
 418       ggc_mark_tree (DECL_SIZE (t));
 419       ggc_mark_tree (DECL_NAME (t));
 420       ggc_mark_tree (DECL_CONTEXT (t));
 421       ggc_mark_tree (DECL_ARGUMENTS (t));
 422       ggc_mark_tree (DECL_RESULT (t));
 423       ggc_mark_tree (DECL_INITIAL (t));
 424       ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
 425       ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
 426       ggc_mark_tree (DECL_SECTION_NAME (t));
 427       ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
 428       ggc_mark_rtx (DECL_RTL (t));
 429       ggc_mark_tree (DECL_VINDEX (t));
 430       lang_mark_tree (t);
 431       break;
 432
 433     case 't': /* A type node.  */
 434       ggc_mark_tree (TYPE_SIZE (t));
 435       ggc_mark_tree (TYPE_SIZE_UNIT (t));
 436       ggc_mark_tree (TYPE_ATTRIBUTES (t));
 437       ggc_mark_tree (TYPE_VALUES (t));
 438       ggc_mark_tree (TYPE_POINTER_TO (t));
 439       ggc_mark_tree (TYPE_REFERENCE_TO (t));
 440       ggc_mark_tree (TYPE_NAME (t));
 441       ggc_mark_tree (TYPE_MIN_VALUE (t));
 442       ggc_mark_tree (TYPE_MAX_VALUE (t));
 443       ggc_mark_tree (TYPE_NEXT_VARIANT (t));
 444       ggc_mark_tree (TYPE_MAIN_VARIANT (t));
 445       ggc_mark_tree (TYPE_BINFO (t));
 446       ggc_mark_tree (TYPE_NONCOPIED_PARTS (t));
 447       ggc_mark_tree (TYPE_CONTEXT (t));
 448       lang_mark_tree (t);
 449       break;
 450
 451     case 'b': /* A lexical block.  */
 452       ggc_mark_tree (BLOCK_VARS (t));
 453       ggc_mark_tree (BLOCK_TYPE_TAGS (t));
 454       ggc_mark_tree (BLOCK_SUBBLOCKS (t));
 455       ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
 456       ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
 457       ggc_mark_rtx (BLOCK_END_NOTE (t));
 458       break;
 459
 460     case 'c': /* A constant.  */
 461       ggc_mark_rtx (TREE_CST_RTL (t));
 462       break;
 463
 464     case 'r': case '<': case '1':
 465     case '2': case 'e': case 's': /* Expressions.  */
 466       {
 467         int i = tree_code_length[TREE_CODE (t)];
 468         while (--i >= 0)
 469           ggc_mark_tree (TREE_OPERAND (t, i));
 470         break;
 471       }
 472     }
 473 }
 474
 475 void
 476 ggc_mark_string (s)
 477      char *s;
 478 {
 479   unsigned int *magic = (unsigned int *)s - 1;
 480
 481   if (s == NULL)
 482     return;
 483
 484   if ((*magic & ~(unsigned)1) != GGC_STRING_MAGIC)
 485     return;   /* abort? */
 486   *magic = GGC_STRING_MAGIC | 1;
 487 }
 488
 489 /* The top level mark-and-sweep routine.  */
 490
 491 void
 492 ggc_collect ()
 493 {
 494   struct ggc_rtx *r, **rp;
 495   struct ggc_rtvec *v, **vp;
 496   struct ggc_tree *t, **tp;
 497   struct ggc_string *s, **sp;
 498   struct ggc_root *x;
 499   int time, n_rtxs, n_trees, n_vecs, n_strings;
 500
 501 #ifndef ENABLE_CHECKING
 502   /* See if it's even worth our while.  */
 503   if (bytes_alloced_since_gc < 64*1024)
 504     return;
 505 #endif
 506
 507   if (!quiet_flag)
 508     fputs (" {GC ", stderr);
 509
 510   time = get_run_time ();
 511
 512   /* Clean out all of the GC marks.  */
 513   for (r = rtxs; r != NULL; r = r->chain)
 514     r->rtx.gc_mark = 0;
 515   for (v = vecs; v != NULL; v = v->chain)
 516     v->vec.gc_mark = 0;
 517   for (t = trees; t != NULL; t = t->chain)
 518     t->tree.common.gc_mark = 0;
 519   for (s = strings; s != NULL; s = s->chain)
 520     s->magic_mark = GGC_STRING_MAGIC;
 521
 522   /* Mark through all the roots.  */
 523   for (x = roots; x != NULL; x = x->next)
 524     {
 525       char *elt = x->base;
 526       int s = x->size, n = x->nelt;
 527       void (*cb)(void *) = x->cb;
 528       int i;
 529
 530       for (i = 0; i < n; ++i, elt += s)
 531         (*cb)(elt);
 532     }
 533
 534   /* Sweep the resulting dead nodes.  */
 535   rp = &rtxs, r = rtxs, n_rtxs = 0;
 536   while (r != NULL)
 537     {
 538       struct ggc_rtx *chain = r->chain;
 539       if (!r->rtx.gc_mark)
 540         {
 541           ggc_free_rtx (r);
 542           *rp = chain;
 543           n_rtxs++;
 544         }
 545       else
 546         rp = &r->chain;
 547       r = chain;
 548     }
 549   *rp = NULL;
 550   n_rtxs_collected += n_rtxs;
 551
 552   vp = &vecs, v = vecs, n_vecs = 0;
 553   while (v != NULL)
 554     {
 555       struct ggc_rtvec *chain = v->chain;
 556       if (!v->vec.gc_mark)
 557         {
 558           ggc_free_rtvec (v);
 559           *vp = chain;
 560           n_vecs++;
 561         }
 562       else
 563         vp = &v->chain;
 564       v = chain;
 565     }
 566   *vp = NULL;
 567   n_vecs_collected += n_vecs;
 568
 569   tp = &trees, t = trees, n_trees = 0;
 570   while (t != NULL)
 571     {
 572       struct ggc_tree *chain = t->chain;
 573       if (!t->tree.common.gc_mark)
 574         {
 575           ggc_free_tree (t);
 576           *tp = chain;
 577           n_trees++;
 578         }
 579       else
 580         tp = &t->chain;
 581       t = chain;
 582     }
 583   *tp = NULL;
 584   n_trees_collected += n_trees;
 585
 586   sp = &strings, s = strings, n_strings = 0;
 587   while (s != NULL)
 588     {
 589       struct ggc_string *chain = s->chain;
 590       if (!(s->magic_mark & 1))
 591         {
 592           ggc_free_string (s);
 593           *sp = chain;
 594           n_strings++;
 595         }
 596       else
 597         sp = &s->chain;
 598       s = chain;
 599     }
 600   *sp = NULL;
 601   n_strings_collected += n_strings;
 602
 603   gc_time += time = get_run_time () - time;
 604
 605   if (!quiet_flag)
 606     {
 607       time = (time + 500) / 1000;
 608       fprintf (stderr, "%d,%d,%d,%d %d.%03d}", n_rtxs, n_vecs, n_trees,
 609                n_strings, time / 1000, time % 1000);
 610     }
 611 }
 612
 613 /* Manipulate global roots that are needed between calls to gc.  */
 614
 615 void
 616 ggc_add_root (base, nelt, size, cb)
 617      void *base;
 618      int nelt, size;
 619      void (*cb) PROTO ((void *));
 620 {
 621   struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof(*x));
 622
 623   x->next = roots;
 624   x->base = base;
 625   x->nelt = nelt;
 626   x->size = size;
 627   x->cb = cb;
 628
 629   roots = x;
 630 }
 631
 632 void
 633 ggc_add_rtx_root (base, nelt)
 634      rtx *base;
 635      int nelt;
 636 {
 637   ggc_add_root (base, nelt, sizeof(rtx), ggc_mark_rtx_ptr);
 638 }
 639
 640 void
 641 ggc_add_tree_root (base, nelt)
 642      tree *base;
 643      int nelt;
 644 {
 645   ggc_add_root (base, nelt, sizeof(tree), ggc_mark_tree_ptr);
 646 }
 647
 648 void
 649 ggc_del_root (base)
 650      void *base;
 651 {
 652   struct ggc_root *x, **p;
 653
 654   p = &roots, x = roots;
 655   while (x)
 656     {
 657       if (x->base == base)
 658         {
 659           *p = x->next;
 660           free (x);
 661           return;
 662         }
 663       p = &x->next;
 664       x = x->next;
 665     }
 666
 667   abort();
 668 }
 669
 670 static void
 671 ggc_mark_rtx_ptr (elt)
 672      void *elt;
 673 {
 674   ggc_mark_rtx (*(rtx *)elt);
 675 }
 676
 677 static void
 678 ggc_mark_tree_ptr (elt)
 679      void *elt;
 680 {
 681   ggc_mark_tree (*(tree *)elt);
 682 }
 683
 684 #ifdef GGC_DUMP
 685 /* Don't enable this unless you want a really really lot of data.  */
 686 static void __attribute__((constructor))
 687 init(void)
 688 {
 689   dump = fopen ("zgcdump", "w");
 690   setlinebuf (dump);
 691 }
 692 #endif
 693
 694 #if 0
 695 /* GDB really should have a memory search function.  Since this is just
 696    for initial debugging, I won't even pretend to get the __data_start
 697    to work on any but alpha-dec-linux-gnu.  */
 698 static void **
 699 search_data(void **start, void *target)
 700 {
 701   extern void *__data_start[];
 702   void **_end = (void **)sbrk(0);
 703
 704   if (start == NULL)
 705     start = __data_start;
 706   while (start < _end)
 707     {
 708       if (*start == target)
 709         return start;
 710       start++;
 711     }
 712   return NULL;
 713 }
 714 #endif