1 /* Simple garbage collection for the GNU compiler.
2 Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
21 /* Generic garbage collection (GC) functions and data, not specific to
22 any particular GC implementation. */
34 /* Statistics about the allocation. */
35 static ggc_statistics *ggc_stats;
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
41 void (*lang_mark_false_label_stack) PARAMS ((struct label_node *));
43 /* Trees that have been marked, but whose children still need marking. */
44 varray_type ggc_pending_trees;
46 static void ggc_mark_rtx_ptr PARAMS ((void *));
47 static void ggc_mark_tree_ptr PARAMS ((void *));
48 static void ggc_mark_rtx_varray_ptr PARAMS ((void *));
49 static void ggc_mark_tree_varray_ptr PARAMS ((void *));
50 static void ggc_mark_tree_hash_table_ptr PARAMS ((void *));
51 static int ggc_htab_delete PARAMS ((void **, void *));
52 static void ggc_mark_trees PARAMS ((void));
53 static bool ggc_mark_tree_hash_table_entry PARAMS ((struct hash_entry *,
56 /* Maintain global roots that are preserved during GC. */
58 /* Global roots that are preserved during calls to gc. */
62 struct ggc_root *next;
66 void (*cb) PARAMS ((void *));
69 static struct ggc_root *roots;
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. */
78 ggc_add_root (base, nelt, size, cb)
81 void (*cb) PARAMS ((void *));
83 struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof (*x));
94 /* Register an array of rtx as a GC root. */
97 ggc_add_rtx_root (base, nelt)
101 ggc_add_root (base, nelt, sizeof (rtx), ggc_mark_rtx_ptr);
104 /* Register an array of trees as a GC root. */
107 ggc_add_tree_root (base, nelt)
111 ggc_add_root (base, nelt, sizeof (tree), ggc_mark_tree_ptr);
114 /* Register a varray of rtxs as a GC root. */
117 ggc_add_rtx_varray_root (base, nelt)
121 ggc_add_root (base, nelt, sizeof (varray_type),
122 ggc_mark_rtx_varray_ptr);
125 /* Register a varray of trees as a GC root. */
128 ggc_add_tree_varray_root (base, nelt)
132 ggc_add_root (base, nelt, sizeof (varray_type),
133 ggc_mark_tree_varray_ptr);
136 /* Register a hash table of trees as a GC root. */
139 ggc_add_tree_hash_table_root (base, nelt)
140 struct hash_table **base;
143 ggc_add_root (base, nelt, sizeof (struct hash_table *),
144 ggc_mark_tree_hash_table_ptr);
147 /* Remove the previously registered GC root at BASE. */
153 struct ggc_root *x, **p;
155 p = &roots, x = roots;
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. */
176 struct d_htab_root *next;
178 ggc_htab_marked_p marked_p;
182 static struct d_htab_root *d_htab_roots;
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.
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.
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. */
205 ggc_add_deletable_htab (x, marked_p, mark)
207 ggc_htab_marked_p marked_p;
210 struct d_htab_root *r
211 = (struct d_htab_root *) xmalloc (sizeof (struct d_htab_root));
213 r->next = d_htab_roots;
214 r->htab = (htab_t) x;
215 r->marked_p = marked_p ? marked_p : ggc_marked_p;
220 /* Process a slot of an htab by deleting it if it has not been marked. */
223 ggc_htab_delete (slot, info)
227 struct d_htab_root *r = (struct d_htab_root *) info;
229 if (! (*r->marked_p) (*slot))
230 htab_clear_slot (r->htab, slot);
237 /* Iterate through all registered roots and mark each element. */
243 struct d_htab_root *y;
245 VARRAY_TREE_INIT (ggc_pending_trees, 4096, "ggc_pending_trees");
247 for (x = roots; x != NULL; x = x->next)
250 int s = x->size, n = x->nelt;
251 void (*cb) PARAMS ((void *)) = x->cb;
254 for (i = 0; i < n; ++i, elt += s)
258 /* Mark all the queued up trees, and their children. */
260 VARRAY_FREE (ggc_pending_trees);
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");
267 for (y = d_htab_roots; y != NULL; y = y->next)
268 htab_traverse (y->htab, ggc_htab_delete, (PTR) y);
270 VARRAY_FREE (ggc_pending_trees);
273 /* R had not been previously marked, but has now been marked via
274 ggc_set_mark. Now recurse and process the children. */
277 ggc_mark_rtx_children (r)
286 enum rtx_code code = GET_CODE (r);
287 /* This gets set to a child rtx to eliminate tail recursion. */
290 /* Collect statistics, if appropriate. */
293 ++ggc_stats->num_rtxs[(int) code];
294 ggc_stats->size_rtxs[(int) code] += ggc_get_size (r);
297 /* ??? If (some of) these are really pass-dependent info, do we
298 have any right poking our noses in? */
302 ggc_mark_rtx (JUMP_LABEL (r));
305 ggc_mark_rtx (LABEL_REFS (r));
308 ggc_mark_rtx (LABEL_NEXTREF (r));
309 ggc_mark_rtx (CONTAINING_INSN (r));
312 ggc_mark_tree (ADDRESSOF_DECL (r));
315 ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
318 switch (NOTE_LINE_NUMBER (r))
320 case NOTE_INSN_RANGE_BEG:
321 case NOTE_INSN_RANGE_END:
323 case NOTE_INSN_EXPECTED_VALUE:
324 ggc_mark_rtx (NOTE_RANGE_INFO (r));
327 case NOTE_INSN_BLOCK_BEG:
328 case NOTE_INSN_BLOCK_END:
329 ggc_mark_tree (NOTE_BLOCK (r));
341 for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
348 if (ggc_test_and_set_mark (exp))
350 if (next_rtx == NULL)
353 ggc_mark_rtx_children (exp);
357 ggc_mark_rtvec (XVEC (r, i));
362 while ((r = next_rtx) != NULL);
365 /* V had not been previously marked, but has now been marked via
366 ggc_set_mark. Now recurse and process the children. */
369 ggc_mark_rtvec_children (v)
374 i = GET_NUM_ELEM (v);
376 ggc_mark_rtx (RTVEC_ELT (v, i));
379 /* Recursively set marks on all of the children of the
380 GCC_PENDING_TREES. */
385 while (ggc_pending_trees->elements_used)
390 t = VARRAY_TOP_TREE (ggc_pending_trees);
391 VARRAY_POP (ggc_pending_trees);
392 code = TREE_CODE (t);
394 /* Collect statistics, if appropriate. */
397 ++ggc_stats->num_trees[(int) code];
398 ggc_stats->size_trees[(int) code] += ggc_get_size (t);
401 /* Bits from common. */
402 ggc_mark_tree (TREE_TYPE (t));
403 ggc_mark_tree (TREE_CHAIN (t));
405 /* Some nodes require special handling. */
409 ggc_mark_tree (TREE_PURPOSE (t));
410 ggc_mark_tree (TREE_VALUE (t));
415 int i = TREE_VEC_LENGTH (t);
418 ggc_mark_tree (TREE_VEC_ELT (t, i));
423 ggc_mark_tree (TREE_REALPART (t));
424 ggc_mark_tree (TREE_IMAGPART (t));
428 ggc_mark_rtx (DECL_INCOMING_RTL (t));
432 ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
435 case IDENTIFIER_NODE:
443 /* But in general we can handle them by class. */
444 switch (TREE_CODE_CLASS (code))
446 case 'd': /* A decl node. */
447 ggc_mark_tree (DECL_SIZE (t));
448 ggc_mark_tree (DECL_SIZE_UNIT (t));
449 ggc_mark_tree (DECL_NAME (t));
450 ggc_mark_tree (DECL_CONTEXT (t));
451 ggc_mark_tree (DECL_ARGUMENTS (t));
452 ggc_mark_tree (DECL_RESULT_FLD (t));
453 ggc_mark_tree (DECL_INITIAL (t));
454 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
455 ggc_mark_tree (DECL_SECTION_NAME (t));
456 ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
457 if (DECL_RTL_SET_P (t))
458 ggc_mark_rtx (DECL_RTL (t));
459 ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
460 ggc_mark_tree (DECL_VINDEX (t));
461 if (DECL_ASSEMBLER_NAME_SET_P (t))
462 ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
463 if (TREE_CODE (t) == FUNCTION_DECL && DECL_SAVED_INSNS (t))
464 ggc_mark_struct_function (DECL_SAVED_INSNS (t));
468 case 't': /* A type node. */
469 ggc_mark_tree (TYPE_SIZE (t));
470 ggc_mark_tree (TYPE_SIZE_UNIT (t));
471 ggc_mark_tree (TYPE_ATTRIBUTES (t));
472 ggc_mark_tree (TYPE_VALUES (t));
473 ggc_mark_tree (TYPE_POINTER_TO (t));
474 ggc_mark_tree (TYPE_REFERENCE_TO (t));
475 ggc_mark_tree (TYPE_NAME (t));
476 ggc_mark_tree (TYPE_MIN_VALUE (t));
477 ggc_mark_tree (TYPE_MAX_VALUE (t));
478 ggc_mark_tree (TYPE_NEXT_VARIANT (t));
479 ggc_mark_tree (TYPE_MAIN_VARIANT (t));
480 ggc_mark_tree (TYPE_BINFO (t));
481 ggc_mark_tree (TYPE_CONTEXT (t));
485 case 'b': /* A lexical block. */
486 ggc_mark_tree (BLOCK_VARS (t));
487 ggc_mark_tree (BLOCK_SUBBLOCKS (t));
488 ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
489 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
492 case 'c': /* A constant. */
493 ggc_mark_rtx (TREE_CST_RTL (t));
496 case 'r': case '<': case '1':
497 case '2': case 'e': case 's': /* Expressions. */
499 int i = TREE_CODE_LENGTH (TREE_CODE (t));
500 int first_rtl = first_rtl_op (TREE_CODE (t));
505 ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
507 ggc_mark_tree (TREE_OPERAND (t, i));
519 /* Mark all the elements of the varray V, which contains rtxs. */
522 ggc_mark_rtx_varray (v)
528 for (i = v->num_elements - 1; i >= 0; --i)
529 ggc_mark_rtx (VARRAY_RTX (v, i));
532 /* Mark all the elements of the varray V, which contains trees. */
535 ggc_mark_tree_varray (v)
541 for (i = v->num_elements - 1; i >= 0; --i)
542 ggc_mark_tree (VARRAY_TREE (v, i));
545 /* Mark the hash table-entry HE. Its key field is really a tree. */
548 ggc_mark_tree_hash_table_entry (he, k)
549 struct hash_entry *he;
550 hash_table_key k ATTRIBUTE_UNUSED;
552 ggc_mark_tree ((tree) he->key);
556 /* Mark all the elements of the hash-table H, which contains trees. */
559 ggc_mark_tree_hash_table (ht)
560 struct hash_table *ht;
562 hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
565 /* Type-correct function to pass to ggc_add_root. It just forwards
566 *ELT (which is an rtx) to ggc_mark_rtx. */
569 ggc_mark_rtx_ptr (elt)
572 ggc_mark_rtx (*(rtx *) elt);
575 /* Type-correct function to pass to ggc_add_root. It just forwards
576 *ELT (which is a tree) to ggc_mark_tree. */
579 ggc_mark_tree_ptr (elt)
582 ggc_mark_tree (*(tree *) elt);
585 /* Type-correct function to pass to ggc_add_root. It just forwards
586 ELT (which is really a varray_type *) to ggc_mark_rtx_varray. */
589 ggc_mark_rtx_varray_ptr (elt)
592 ggc_mark_rtx_varray (*(varray_type *) elt);
595 /* Type-correct function to pass to ggc_add_root. It just forwards
596 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
599 ggc_mark_tree_varray_ptr (elt)
602 ggc_mark_tree_varray (*(varray_type *) elt);
605 /* Type-correct function to pass to ggc_add_root. It just forwards
606 ELT (which is really a struct hash_table **) to
607 ggc_mark_tree_hash_table. */
610 ggc_mark_tree_hash_table_ptr (elt)
613 ggc_mark_tree_hash_table (*(struct hash_table **) elt);
616 /* Allocate a block of memory, then clear it. */
618 ggc_alloc_cleared (size)
621 void *buf = ggc_alloc (size);
622 memset (buf, 0, size);
626 /* Print statistics that are independent of the collector in use. */
627 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
629 : ((x) < 1024*1024*10 \
631 : (x) / (1024*1024))))
632 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
635 ggc_print_common_statistics (stream, stats)
637 ggc_statistics *stats;
641 /* Set the pointer so that during collection we will actually gather
645 /* Then do one collection to fill in the statistics. */
648 /* Total the statistics. */
649 for (code = 0; code < MAX_TREE_CODES; ++code)
651 stats->total_num_trees += stats->num_trees[code];
652 stats->total_size_trees += stats->size_trees[code];
654 for (code = 0; code < NUM_RTX_CODE; ++code)
656 stats->total_num_rtxs += stats->num_rtxs[code];
657 stats->total_size_rtxs += stats->size_rtxs[code];
660 /* Print the statistics for trees. */
661 fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
662 "Number", "Bytes", "% Total");
663 for (code = 0; code < MAX_TREE_CODES; ++code)
664 if (ggc_stats->num_trees[code])
666 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
667 tree_code_name[code],
668 ggc_stats->num_trees[code],
669 SCALE (ggc_stats->size_trees[code]),
670 LABEL (ggc_stats->size_trees[code]),
671 (100 * ((double) ggc_stats->size_trees[code])
672 / ggc_stats->total_size_trees));
675 "%-17s%10u%16ld%c\n", "Total",
676 ggc_stats->total_num_trees,
677 SCALE (ggc_stats->total_size_trees),
678 LABEL (ggc_stats->total_size_trees));
680 /* Print the statistics for RTL. */
681 fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
682 "Number", "Bytes", "% Total");
683 for (code = 0; code < NUM_RTX_CODE; ++code)
684 if (ggc_stats->num_rtxs[code])
686 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
688 ggc_stats->num_rtxs[code],
689 SCALE (ggc_stats->size_rtxs[code]),
690 LABEL (ggc_stats->size_rtxs[code]),
691 (100 * ((double) ggc_stats->size_rtxs[code])
692 / ggc_stats->total_size_rtxs));
695 "%-17s%10u%16ld%c\n", "Total",
696 ggc_stats->total_num_rtxs,
697 SCALE (ggc_stats->total_size_rtxs),
698 LABEL (ggc_stats->total_size_rtxs));
700 /* Don't gather statistics any more. */