ggc-common.c revision 90075
1/* Simple garbage collection for the GNU compiler. 2 Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 20 21/* Generic garbage collection (GC) functions and data, not specific to 22 any particular GC implementation. */ 23 24#include "config.h" 25#include "system.h" 26#include "rtl.h" 27#include "tree.h" 28#include "tm_p.h" 29#include "hash.h" 30#include "hashtab.h" 31#include "varray.h" 32#include "ggc.h" 33 34/* Statistics about the allocation. */ 35static ggc_statistics *ggc_stats; 36 37/* The FALSE_LABEL_STACK, declared in except.h, has language-dependent 38 semantics. If a front-end needs to mark the false label stack, it 39 should set this pointer to a non-NULL value. Otherwise, no marking 40 will be done. */ 41void (*lang_mark_false_label_stack) PARAMS ((struct label_node *)); 42 43/* Trees that have been marked, but whose children still need marking. */ 44varray_type ggc_pending_trees; 45 46static void ggc_mark_rtx_ptr PARAMS ((void *)); 47static void ggc_mark_tree_ptr PARAMS ((void *)); 48static void ggc_mark_rtx_varray_ptr PARAMS ((void *)); 49static void ggc_mark_tree_varray_ptr PARAMS ((void *)); 50static void ggc_mark_tree_hash_table_ptr PARAMS ((void *)); 51static int ggc_htab_delete PARAMS ((void **, void *)); 52static void ggc_mark_trees PARAMS ((void)); 53static bool ggc_mark_tree_hash_table_entry PARAMS ((struct hash_entry *, 54 hash_table_key)); 55 56/* Maintain global roots that are preserved during GC. */ 57 58/* Global roots that are preserved during calls to gc. */ 59 60struct ggc_root 61{ 62 struct ggc_root *next; 63 void *base; 64 int nelt; 65 int size; 66 void (*cb) PARAMS ((void *)); 67}; 68 69static struct ggc_root *roots; 70 71/* Add BASE as a new garbage collection root. It is an array of 72 length NELT with each element SIZE bytes long. CB is a 73 function that will be called with a pointer to each element 74 of the array; it is the intention that CB call the appropriate 75 routine to mark gc-able memory for that element. */ 76 77void 78ggc_add_root (base, nelt, size, cb) 79 void *base; 80 int nelt, size; 81 void (*cb) PARAMS ((void *)); 82{ 83 struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof (*x)); 84 85 x->next = roots; 86 x->base = base; 87 x->nelt = nelt; 88 x->size = size; 89 x->cb = cb; 90 91 roots = x; 92} 93 94/* Register an array of rtx as a GC root. */ 95 96void 97ggc_add_rtx_root (base, nelt) 98 rtx *base; 99 int nelt; 100{ 101 ggc_add_root (base, nelt, sizeof (rtx), ggc_mark_rtx_ptr); 102} 103 104/* Register an array of trees as a GC root. */ 105 106void 107ggc_add_tree_root (base, nelt) 108 tree *base; 109 int nelt; 110{ 111 ggc_add_root (base, nelt, sizeof (tree), ggc_mark_tree_ptr); 112} 113 114/* Register a varray of rtxs as a GC root. */ 115 116void 117ggc_add_rtx_varray_root (base, nelt) 118 varray_type *base; 119 int nelt; 120{ 121 ggc_add_root (base, nelt, sizeof (varray_type), 122 ggc_mark_rtx_varray_ptr); 123} 124 125/* Register a varray of trees as a GC root. */ 126 127void 128ggc_add_tree_varray_root (base, nelt) 129 varray_type *base; 130 int nelt; 131{ 132 ggc_add_root (base, nelt, sizeof (varray_type), 133 ggc_mark_tree_varray_ptr); 134} 135 136/* Register a hash table of trees as a GC root. */ 137 138void 139ggc_add_tree_hash_table_root (base, nelt) 140 struct hash_table **base; 141 int nelt; 142{ 143 ggc_add_root (base, nelt, sizeof (struct hash_table *), 144 ggc_mark_tree_hash_table_ptr); 145} 146 147/* Remove the previously registered GC root at BASE. */ 148 149void 150ggc_del_root (base) 151 void *base; 152{ 153 struct ggc_root *x, **p; 154 155 p = &roots, x = roots; 156 while (x) 157 { 158 if (x->base == base) 159 { 160 *p = x->next; 161 free (x); 162 return; 163 } 164 p = &x->next; 165 x = x->next; 166 } 167 168 abort (); 169} 170 171/* Add a hash table to be scanned when all roots have been processed. We 172 delete any entry in the table that has not been marked. */ 173 174struct d_htab_root 175{ 176 struct d_htab_root *next; 177 htab_t htab; 178 ggc_htab_marked_p marked_p; 179 ggc_htab_mark mark; 180}; 181 182static struct d_htab_root *d_htab_roots; 183 184/* Add X, an htab, to a list of htabs that contain objects which are allocated 185 from GC memory. Once all other roots are marked, we check each object in 186 the htab to see if it has already been marked. If not, it is deleted. 187 188 MARKED_P, if specified, is a function that returns 1 if the entry is to 189 be considered as "marked". If not present, the data structure pointed to 190 by the htab slot is tested. This function should be supplied if some 191 other object (such as something pointed to by that object) should be tested 192 in which case the function tests whether that object (or objects) are 193 marked (using ggc_marked_p) and returns nonzero if it is. 194 195 MARK, if specified, is a function that is passed the contents of a slot 196 that has been determined to have been "marked" (via the above function) 197 and marks any other objects pointed to by that object. For example, 198 we might have a hash table of memory attribute blocks, which are pointed 199 to by a MEM RTL but have a pointer to a DECL. MARKED_P in that case will 200 not be specified because we want to know if the attribute block is pointed 201 to by the MEM, but MARK must be specified because if the block has been 202 marked, we need to mark the DECL. */ 203 204void 205ggc_add_deletable_htab (x, marked_p, mark) 206 PTR x; 207 ggc_htab_marked_p marked_p; 208 ggc_htab_mark mark; 209{ 210 struct d_htab_root *r 211 = (struct d_htab_root *) xmalloc (sizeof (struct d_htab_root)); 212 213 r->next = d_htab_roots; 214 r->htab = (htab_t) x; 215 r->marked_p = marked_p ? marked_p : ggc_marked_p; 216 r->mark = mark; 217 d_htab_roots = r; 218} 219 220/* Process a slot of an htab by deleting it if it has not been marked. */ 221 222static int 223ggc_htab_delete (slot, info) 224 void **slot; 225 void *info; 226{ 227 struct d_htab_root *r = (struct d_htab_root *) info; 228 229 if (! (*r->marked_p) (*slot)) 230 htab_clear_slot (r->htab, slot); 231 else if (r->mark) 232 (*r->mark) (*slot); 233 234 return 1; 235} 236 237/* Iterate through all registered roots and mark each element. */ 238 239void 240ggc_mark_roots () 241{ 242 struct ggc_root *x; 243 struct d_htab_root *y; 244 245 VARRAY_TREE_INIT (ggc_pending_trees, 4096, "ggc_pending_trees"); 246 247 for (x = roots; x != NULL; x = x->next) 248 { 249 char *elt = x->base; 250 int s = x->size, n = x->nelt; 251 void (*cb) PARAMS ((void *)) = x->cb; 252 int i; 253 254 for (i = 0; i < n; ++i, elt += s) 255 (*cb)(elt); 256 } 257 258 /* Mark all the queued up trees, and their children. */ 259 ggc_mark_trees (); 260 VARRAY_FREE (ggc_pending_trees); 261 262 /* Now scan all hash tables that have objects which are to be deleted if 263 they are not already marked. Since these may mark more trees, we need 264 to reinitialize that varray. */ 265 VARRAY_TREE_INIT (ggc_pending_trees, 1024, "ggc_pending_trees"); 266 267 for (y = d_htab_roots; y != NULL; y = y->next) 268 htab_traverse (y->htab, ggc_htab_delete, (PTR) y); 269 ggc_mark_trees (); 270 VARRAY_FREE (ggc_pending_trees); 271} 272 273/* R had not been previously marked, but has now been marked via 274 ggc_set_mark. Now recurse and process the children. */ 275 276void 277ggc_mark_rtx_children (r) 278 rtx r; 279{ 280 const char *fmt; 281 int i; 282 rtx next_rtx; 283 284 do 285 { 286 enum rtx_code code = GET_CODE (r); 287 /* This gets set to a child rtx to eliminate tail recursion. */ 288 next_rtx = NULL; 289 290 /* Collect statistics, if appropriate. */ 291 if (ggc_stats) 292 { 293 ++ggc_stats->num_rtxs[(int) code]; 294 ggc_stats->size_rtxs[(int) code] += ggc_get_size (r); 295 } 296 297 /* ??? If (some of) these are really pass-dependent info, do we 298 have any right poking our noses in? */ 299 switch (code) 300 { 301 case MEM: 302 ggc_mark (MEM_ATTRS (r)); 303 break; 304 case JUMP_INSN: 305 ggc_mark_rtx (JUMP_LABEL (r)); 306 break; 307 case CODE_LABEL: 308 ggc_mark_rtx (LABEL_REFS (r)); 309 break; 310 case LABEL_REF: 311 ggc_mark_rtx (LABEL_NEXTREF (r)); 312 ggc_mark_rtx (CONTAINING_INSN (r)); 313 break; 314 case ADDRESSOF: 315 ggc_mark_tree (ADDRESSOF_DECL (r)); 316 break; 317 case CONST_DOUBLE: 318 ggc_mark_rtx (CONST_DOUBLE_CHAIN (r)); 319 break; 320 case NOTE: 321 switch (NOTE_LINE_NUMBER (r)) 322 { 323 case NOTE_INSN_RANGE_BEG: 324 case NOTE_INSN_RANGE_END: 325 case NOTE_INSN_LIVE: 326 case NOTE_INSN_EXPECTED_VALUE: 327 ggc_mark_rtx (NOTE_RANGE_INFO (r)); 328 break; 329 330 case NOTE_INSN_BLOCK_BEG: 331 case NOTE_INSN_BLOCK_END: 332 ggc_mark_tree (NOTE_BLOCK (r)); 333 break; 334 335 default: 336 break; 337 } 338 break; 339 340 default: 341 break; 342 } 343 344 for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i) 345 { 346 rtx exp; 347 switch (*fmt) 348 { 349 case 'e': case 'u': 350 exp = XEXP (r, i); 351 if (ggc_test_and_set_mark (exp)) 352 { 353 if (next_rtx == NULL) 354 next_rtx = exp; 355 else 356 ggc_mark_rtx_children (exp); 357 } 358 break; 359 case 'V': case 'E': 360 ggc_mark_rtvec (XVEC (r, i)); 361 break; 362 } 363 } 364 } 365 while ((r = next_rtx) != NULL); 366} 367 368/* V had not been previously marked, but has now been marked via 369 ggc_set_mark. Now recurse and process the children. */ 370 371void 372ggc_mark_rtvec_children (v) 373 rtvec v; 374{ 375 int i; 376 377 i = GET_NUM_ELEM (v); 378 while (--i >= 0) 379 ggc_mark_rtx (RTVEC_ELT (v, i)); 380} 381 382/* Recursively set marks on all of the children of the 383 GCC_PENDING_TREES. */ 384 385static void 386ggc_mark_trees () 387{ 388 while (ggc_pending_trees->elements_used) 389 { 390 tree t; 391 enum tree_code code; 392 393 t = VARRAY_TOP_TREE (ggc_pending_trees); 394 VARRAY_POP (ggc_pending_trees); 395 code = TREE_CODE (t); 396 397 /* Collect statistics, if appropriate. */ 398 if (ggc_stats) 399 { 400 ++ggc_stats->num_trees[(int) code]; 401 ggc_stats->size_trees[(int) code] += ggc_get_size (t); 402 } 403 404 /* Bits from common. */ 405 ggc_mark_tree (TREE_TYPE (t)); 406 ggc_mark_tree (TREE_CHAIN (t)); 407 408 /* Some nodes require special handling. */ 409 switch (code) 410 { 411 case TREE_LIST: 412 ggc_mark_tree (TREE_PURPOSE (t)); 413 ggc_mark_tree (TREE_VALUE (t)); 414 continue; 415 416 case TREE_VEC: 417 { 418 int i = TREE_VEC_LENGTH (t); 419 420 while (--i >= 0) 421 ggc_mark_tree (TREE_VEC_ELT (t, i)); 422 continue; 423 } 424 425 case COMPLEX_CST: 426 ggc_mark_tree (TREE_REALPART (t)); 427 ggc_mark_tree (TREE_IMAGPART (t)); 428 break; 429 430 case PARM_DECL: 431 ggc_mark_rtx (DECL_INCOMING_RTL (t)); 432 break; 433 434 case FIELD_DECL: 435 ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t)); 436 break; 437 438 case IDENTIFIER_NODE: 439 lang_mark_tree (t); 440 continue; 441 442 default: 443 break; 444 } 445 446 /* But in general we can handle them by class. */ 447 switch (TREE_CODE_CLASS (code)) 448 { 449 case 'd': /* A decl node. */ 450 ggc_mark_tree (DECL_SIZE (t)); 451 ggc_mark_tree (DECL_SIZE_UNIT (t)); 452 ggc_mark_tree (DECL_NAME (t)); 453 ggc_mark_tree (DECL_CONTEXT (t)); 454 ggc_mark_tree (DECL_ARGUMENTS (t)); 455 ggc_mark_tree (DECL_RESULT_FLD (t)); 456 ggc_mark_tree (DECL_INITIAL (t)); 457 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t)); 458 ggc_mark_tree (DECL_SECTION_NAME (t)); 459 ggc_mark_tree (DECL_ATTRIBUTES (t)); 460 if (DECL_RTL_SET_P (t)) 461 ggc_mark_rtx (DECL_RTL (t)); 462 ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t)); 463 ggc_mark_tree (DECL_VINDEX (t)); 464 if (DECL_ASSEMBLER_NAME_SET_P (t)) 465 ggc_mark_tree (DECL_ASSEMBLER_NAME (t)); 466 if (TREE_CODE (t) == FUNCTION_DECL) 467 { 468 ggc_mark_tree (DECL_SAVED_TREE (t)); 469 ggc_mark_tree (DECL_INLINED_FNS (t)); 470 if (DECL_SAVED_INSNS (t)) 471 ggc_mark_struct_function (DECL_SAVED_INSNS (t)); 472 } 473 lang_mark_tree (t); 474 break; 475 476 case 't': /* A type node. */ 477 ggc_mark_tree (TYPE_SIZE (t)); 478 ggc_mark_tree (TYPE_SIZE_UNIT (t)); 479 ggc_mark_tree (TYPE_ATTRIBUTES (t)); 480 ggc_mark_tree (TYPE_VALUES (t)); 481 ggc_mark_tree (TYPE_POINTER_TO (t)); 482 ggc_mark_tree (TYPE_REFERENCE_TO (t)); 483 ggc_mark_tree (TYPE_NAME (t)); 484 ggc_mark_tree (TYPE_MIN_VALUE (t)); 485 ggc_mark_tree (TYPE_MAX_VALUE (t)); 486 ggc_mark_tree (TYPE_NEXT_VARIANT (t)); 487 ggc_mark_tree (TYPE_MAIN_VARIANT (t)); 488 ggc_mark_tree (TYPE_BINFO (t)); 489 ggc_mark_tree (TYPE_CONTEXT (t)); 490 lang_mark_tree (t); 491 break; 492 493 case 'b': /* A lexical block. */ 494 ggc_mark_tree (BLOCK_VARS (t)); 495 ggc_mark_tree (BLOCK_SUBBLOCKS (t)); 496 ggc_mark_tree (BLOCK_SUPERCONTEXT (t)); 497 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t)); 498 break; 499 500 case 'c': /* A constant. */ 501 ggc_mark_rtx (TREE_CST_RTL (t)); 502 break; 503 504 case 'r': case '<': case '1': 505 case '2': case 'e': case 's': /* Expressions. */ 506 { 507 int i = TREE_CODE_LENGTH (TREE_CODE (t)); 508 int first_rtl = first_rtl_op (TREE_CODE (t)); 509 510 while (--i >= 0) 511 { 512 if (i >= first_rtl) 513 ggc_mark_rtx ((rtx) TREE_OPERAND (t, i)); 514 else 515 ggc_mark_tree (TREE_OPERAND (t, i)); 516 } 517 break; 518 } 519 520 case 'x': 521 lang_mark_tree (t); 522 break; 523 } 524 } 525} 526 527/* Mark all the elements of the varray V, which contains rtxs. */ 528 529void 530ggc_mark_rtx_varray (v) 531 varray_type v; 532{ 533 int i; 534 535 if (v) 536 for (i = v->num_elements - 1; i >= 0; --i) 537 ggc_mark_rtx (VARRAY_RTX (v, i)); 538} 539 540/* Mark all the elements of the varray V, which contains trees. */ 541 542void 543ggc_mark_tree_varray (v) 544 varray_type v; 545{ 546 int i; 547 548 if (v) 549 for (i = v->num_elements - 1; i >= 0; --i) 550 ggc_mark_tree (VARRAY_TREE (v, i)); 551} 552 553/* Mark the hash table-entry HE. Its key field is really a tree. */ 554 555static bool 556ggc_mark_tree_hash_table_entry (he, k) 557 struct hash_entry *he; 558 hash_table_key k ATTRIBUTE_UNUSED; 559{ 560 ggc_mark_tree ((tree) he->key); 561 return true; 562} 563 564/* Mark all the elements of the hash-table H, which contains trees. */ 565 566void 567ggc_mark_tree_hash_table (ht) 568 struct hash_table *ht; 569{ 570 hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0); 571} 572 573/* Type-correct function to pass to ggc_add_root. It just forwards 574 *ELT (which is an rtx) to ggc_mark_rtx. */ 575 576static void 577ggc_mark_rtx_ptr (elt) 578 void *elt; 579{ 580 ggc_mark_rtx (*(rtx *) elt); 581} 582 583/* Type-correct function to pass to ggc_add_root. It just forwards 584 *ELT (which is a tree) to ggc_mark_tree. */ 585 586static void 587ggc_mark_tree_ptr (elt) 588 void *elt; 589{ 590 ggc_mark_tree (*(tree *) elt); 591} 592 593/* Type-correct function to pass to ggc_add_root. It just forwards 594 ELT (which is really a varray_type *) to ggc_mark_rtx_varray. */ 595 596static void 597ggc_mark_rtx_varray_ptr (elt) 598 void *elt; 599{ 600 ggc_mark_rtx_varray (*(varray_type *) elt); 601} 602 603/* Type-correct function to pass to ggc_add_root. It just forwards 604 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */ 605 606static void 607ggc_mark_tree_varray_ptr (elt) 608 void *elt; 609{ 610 ggc_mark_tree_varray (*(varray_type *) elt); 611} 612 613/* Type-correct function to pass to ggc_add_root. It just forwards 614 ELT (which is really a struct hash_table **) to 615 ggc_mark_tree_hash_table. */ 616 617static void 618ggc_mark_tree_hash_table_ptr (elt) 619 void *elt; 620{ 621 ggc_mark_tree_hash_table (*(struct hash_table **) elt); 622} 623 624/* Allocate a block of memory, then clear it. */ 625void * 626ggc_alloc_cleared (size) 627 size_t size; 628{ 629 void *buf = ggc_alloc (size); 630 memset (buf, 0, size); 631 return buf; 632} 633 634/* Print statistics that are independent of the collector in use. */ 635#define SCALE(x) ((unsigned long) ((x) < 1024*10 \ 636 ? (x) \ 637 : ((x) < 1024*1024*10 \ 638 ? (x) / 1024 \ 639 : (x) / (1024*1024)))) 640#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) 641 642void 643ggc_print_common_statistics (stream, stats) 644 FILE *stream; 645 ggc_statistics *stats; 646{ 647 int code; 648 649 /* Set the pointer so that during collection we will actually gather 650 the statistics. */ 651 ggc_stats = stats; 652 653 /* Then do one collection to fill in the statistics. */ 654 ggc_collect (); 655 656 /* Total the statistics. */ 657 for (code = 0; code < MAX_TREE_CODES; ++code) 658 { 659 stats->total_num_trees += stats->num_trees[code]; 660 stats->total_size_trees += stats->size_trees[code]; 661 } 662 for (code = 0; code < NUM_RTX_CODE; ++code) 663 { 664 stats->total_num_rtxs += stats->num_rtxs[code]; 665 stats->total_size_rtxs += stats->size_rtxs[code]; 666 } 667 668 /* Print the statistics for trees. */ 669 fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree", 670 "Number", "Bytes", "% Total"); 671 for (code = 0; code < MAX_TREE_CODES; ++code) 672 if (ggc_stats->num_trees[code]) 673 { 674 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n", 675 tree_code_name[code], 676 ggc_stats->num_trees[code], 677 SCALE (ggc_stats->size_trees[code]), 678 LABEL (ggc_stats->size_trees[code]), 679 (100 * ((double) ggc_stats->size_trees[code]) 680 / ggc_stats->total_size_trees)); 681 } 682 fprintf (stream, 683 "%-17s%10u%16ld%c\n", "Total", 684 ggc_stats->total_num_trees, 685 SCALE (ggc_stats->total_size_trees), 686 LABEL (ggc_stats->total_size_trees)); 687 688 /* Print the statistics for RTL. */ 689 fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX", 690 "Number", "Bytes", "% Total"); 691 for (code = 0; code < NUM_RTX_CODE; ++code) 692 if (ggc_stats->num_rtxs[code]) 693 { 694 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n", 695 rtx_name[code], 696 ggc_stats->num_rtxs[code], 697 SCALE (ggc_stats->size_rtxs[code]), 698 LABEL (ggc_stats->size_rtxs[code]), 699 (100 * ((double) ggc_stats->size_rtxs[code]) 700 / ggc_stats->total_size_rtxs)); 701 } 702 fprintf (stream, 703 "%-17s%10u%16ld%c\n", "Total", 704 ggc_stats->total_num_rtxs, 705 SCALE (ggc_stats->total_size_rtxs), 706 LABEL (ggc_stats->total_size_rtxs)); 707 708 /* Don't gather statistics any more. */ 709 ggc_stats = NULL; 710} 711