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