1 /* Simple garbage collection for the GNU compiler.
2 Copyright (C) 1999, 2000, 2001, 2002 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. */
33 #include "langhooks.h"
35 /* Statistics about the allocation. */
36 static ggc_statistics *ggc_stats;
38 /* The FALSE_LABEL_STACK, declared in except.h, has language-dependent
39 semantics. If a front-end needs to mark the false label stack, it
40 should set this pointer to a non-NULL value. Otherwise, no marking
42 void (*lang_mark_false_label_stack) PARAMS ((struct label_node *));
44 /* Trees that have been marked, but whose children still need marking. */
45 varray_type ggc_pending_trees;
47 static void ggc_mark_rtx_ptr PARAMS ((void *));
48 static void ggc_mark_tree_ptr PARAMS ((void *));
49 static void ggc_mark_rtx_varray_ptr PARAMS ((void *));
50 static void ggc_mark_tree_varray_ptr PARAMS ((void *));
51 static void ggc_mark_tree_hash_table_ptr PARAMS ((void *));
52 static int ggc_htab_delete PARAMS ((void **, void *));
53 static void ggc_mark_trees PARAMS ((void));
54 static bool ggc_mark_tree_hash_table_entry PARAMS ((struct hash_entry *,
57 /* Maintain global roots that are preserved during GC. */
59 /* Global roots that are preserved during calls to gc. */
63 struct ggc_root *next;
67 void (*cb) PARAMS ((void *));
70 static struct ggc_root *roots;
72 /* Add BASE as a new garbage collection root. It is an array of
73 length NELT with each element SIZE bytes long. CB is a
74 function that will be called with a pointer to each element
75 of the array; it is the intention that CB call the appropriate
76 routine to mark gc-able memory for that element. */
79 ggc_add_root (base, nelt, size, cb)
82 void (*cb) PARAMS ((void *));
84 struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof (*x));
95 /* Register an array of rtx as a GC root. */
98 ggc_add_rtx_root (base, nelt)
102 ggc_add_root (base, nelt, sizeof (rtx), ggc_mark_rtx_ptr);
105 /* Register an array of trees as a GC root. */
108 ggc_add_tree_root (base, nelt)
112 ggc_add_root (base, nelt, sizeof (tree), ggc_mark_tree_ptr);
115 /* Register a varray of rtxs as a GC root. */
118 ggc_add_rtx_varray_root (base, nelt)
122 ggc_add_root (base, nelt, sizeof (varray_type),
123 ggc_mark_rtx_varray_ptr);
126 /* Register a varray of trees as a GC root. */
129 ggc_add_tree_varray_root (base, nelt)
133 ggc_add_root (base, nelt, sizeof (varray_type),
134 ggc_mark_tree_varray_ptr);
137 /* Register a hash table of trees as a GC root. */
140 ggc_add_tree_hash_table_root (base, nelt)
141 struct hash_table **base;
144 ggc_add_root (base, nelt, sizeof (struct hash_table *),
145 ggc_mark_tree_hash_table_ptr);
148 /* Remove the previously registered GC root at BASE. */
154 struct ggc_root *x, **p;
156 p = &roots, x = roots;
172 /* Add a hash table to be scanned when all roots have been processed. We
173 delete any entry in the table that has not been marked. */
177 struct d_htab_root *next;
179 ggc_htab_marked_p marked_p;
183 static struct d_htab_root *d_htab_roots;
185 /* Add X, an htab, to a list of htabs that contain objects which are allocated
186 from GC memory. Once all other roots are marked, we check each object in
187 the htab to see if it has already been marked. If not, it is deleted.
189 MARKED_P, if specified, is a function that returns 1 if the entry is to
190 be considered as "marked". If not present, the data structure pointed to
191 by the htab slot is tested. This function should be supplied if some
192 other object (such as something pointed to by that object) should be tested
193 in which case the function tests whether that object (or objects) are
194 marked (using ggc_marked_p) and returns nonzero if it is.
196 MARK, if specified, is a function that is passed the contents of a slot
197 that has been determined to have been "marked" (via the above function)
198 and marks any other objects pointed to by that object. For example,
199 we might have a hash table of memory attribute blocks, which are pointed
200 to by a MEM RTL but have a pointer to a DECL. MARKED_P in that case will
201 not be specified because we want to know if the attribute block is pointed
202 to by the MEM, but MARK must be specified because if the block has been
203 marked, we need to mark the DECL. */
206 ggc_add_deletable_htab (x, marked_p, mark)
208 ggc_htab_marked_p marked_p;
211 struct d_htab_root *r
212 = (struct d_htab_root *) xmalloc (sizeof (struct d_htab_root));
214 r->next = d_htab_roots;
215 r->htab = (htab_t) x;
216 r->marked_p = marked_p ? marked_p : ggc_marked_p;
221 /* Process a slot of an htab by deleting it if it has not been marked. */
224 ggc_htab_delete (slot, info)
228 struct d_htab_root *r = (struct d_htab_root *) info;
230 if (! (*r->marked_p) (*slot))
231 htab_clear_slot (r->htab, slot);
238 /* Iterate through all registered roots and mark each element. */
244 struct d_htab_root *y;
246 VARRAY_TREE_INIT (ggc_pending_trees, 4096, "ggc_pending_trees");
248 for (x = roots; x != NULL; x = x->next)
251 int s = x->size, n = x->nelt;
252 void (*cb) PARAMS ((void *)) = x->cb;
255 for (i = 0; i < n; ++i, elt += s)
259 /* Mark all the queued up trees, and their children. */
261 VARRAY_FREE (ggc_pending_trees);
263 /* Now scan all hash tables that have objects which are to be deleted if
264 they are not already marked. Since these may mark more trees, we need
265 to reinitialize that varray. */
266 VARRAY_TREE_INIT (ggc_pending_trees, 1024, "ggc_pending_trees");
268 for (y = d_htab_roots; y != NULL; y = y->next)
269 htab_traverse (y->htab, ggc_htab_delete, (PTR) y);
271 VARRAY_FREE (ggc_pending_trees);
274 /* R had not been previously marked, but has now been marked via
275 ggc_set_mark. Now recurse and process the children. */
278 ggc_mark_rtx_children (r)
287 enum rtx_code code = GET_CODE (r);
288 /* This gets set to a child rtx to eliminate tail recursion. */
291 /* Collect statistics, if appropriate. */
294 ++ggc_stats->num_rtxs[(int) code];
295 ggc_stats->size_rtxs[(int) code] += ggc_get_size (r);
298 /* ??? If (some of) these are really pass-dependent info, do we
299 have any right poking our noses in? */
303 ggc_mark (MEM_ATTRS (r));
306 ggc_mark_rtx (JUMP_LABEL (r));
309 ggc_mark_rtx (LABEL_REFS (r));
312 ggc_mark_rtx (LABEL_NEXTREF (r));
313 ggc_mark_rtx (CONTAINING_INSN (r));
316 ggc_mark_tree (ADDRESSOF_DECL (r));
319 ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
322 switch (NOTE_LINE_NUMBER (r))
324 case NOTE_INSN_RANGE_BEG:
325 case NOTE_INSN_RANGE_END:
327 case NOTE_INSN_EXPECTED_VALUE:
328 ggc_mark_rtx (NOTE_RANGE_INFO (r));
331 case NOTE_INSN_BLOCK_BEG:
332 case NOTE_INSN_BLOCK_END:
333 ggc_mark_tree (NOTE_BLOCK (r));
345 for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
352 if (ggc_test_and_set_mark (exp))
354 if (next_rtx == NULL)
357 ggc_mark_rtx_children (exp);
361 ggc_mark_rtvec (XVEC (r, i));
366 while ((r = next_rtx) != NULL);
369 /* V had not been previously marked, but has now been marked via
370 ggc_set_mark. Now recurse and process the children. */
373 ggc_mark_rtvec_children (v)
378 i = GET_NUM_ELEM (v);
380 ggc_mark_rtx (RTVEC_ELT (v, i));
383 /* Recursively set marks on all of the children of the
384 GCC_PENDING_TREES. */
389 while (ggc_pending_trees->elements_used)
394 t = VARRAY_TOP_TREE (ggc_pending_trees);
395 VARRAY_POP (ggc_pending_trees);
396 code = TREE_CODE (t);
398 /* Collect statistics, if appropriate. */
401 ++ggc_stats->num_trees[(int) code];
402 ggc_stats->size_trees[(int) code] += ggc_get_size (t);
405 /* Bits from common. */
406 ggc_mark_tree (TREE_TYPE (t));
407 ggc_mark_tree (TREE_CHAIN (t));
409 /* Some nodes require special handling. */
413 ggc_mark_tree (TREE_PURPOSE (t));
414 ggc_mark_tree (TREE_VALUE (t));
419 int i = TREE_VEC_LENGTH (t);
422 ggc_mark_tree (TREE_VEC_ELT (t, i));
427 ggc_mark_tree (TREE_REALPART (t));
428 ggc_mark_tree (TREE_IMAGPART (t));
432 ggc_mark_rtx (DECL_INCOMING_RTL (t));
436 ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
439 case IDENTIFIER_NODE:
440 (*lang_hooks.mark_tree) (t);
447 /* But in general we can handle them by class. */
448 switch (TREE_CODE_CLASS (code))
450 case 'd': /* A decl node. */
451 ggc_mark_tree (DECL_SIZE (t));
452 ggc_mark_tree (DECL_SIZE_UNIT (t));
453 ggc_mark_tree (DECL_NAME (t));
454 ggc_mark_tree (DECL_CONTEXT (t));
455 ggc_mark_tree (DECL_ARGUMENTS (t));
456 ggc_mark_tree (DECL_RESULT_FLD (t));
457 ggc_mark_tree (DECL_INITIAL (t));
458 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
459 ggc_mark_tree (DECL_SECTION_NAME (t));
460 ggc_mark_tree (DECL_ATTRIBUTES (t));
461 if (DECL_RTL_SET_P (t))
462 ggc_mark_rtx (DECL_RTL (t));
463 ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
464 ggc_mark_tree (DECL_VINDEX (t));
465 if (DECL_ASSEMBLER_NAME_SET_P (t))
466 ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
467 if (TREE_CODE (t) == FUNCTION_DECL)
469 ggc_mark_tree (DECL_SAVED_TREE (t));
470 ggc_mark_tree (DECL_INLINED_FNS (t));
471 if (DECL_SAVED_INSNS (t))
472 ggc_mark_struct_function (DECL_SAVED_INSNS (t));
474 (*lang_hooks.mark_tree) (t);
477 case 't': /* A type node. */
478 ggc_mark_tree (TYPE_SIZE (t));
479 ggc_mark_tree (TYPE_SIZE_UNIT (t));
480 ggc_mark_tree (TYPE_ATTRIBUTES (t));
481 ggc_mark_tree (TYPE_VALUES (t));
482 ggc_mark_tree (TYPE_POINTER_TO (t));
483 ggc_mark_tree (TYPE_REFERENCE_TO (t));
484 ggc_mark_tree (TYPE_NAME (t));
485 ggc_mark_tree (TYPE_MIN_VALUE (t));
486 ggc_mark_tree (TYPE_MAX_VALUE (t));
487 ggc_mark_tree (TYPE_NEXT_VARIANT (t));
488 ggc_mark_tree (TYPE_MAIN_VARIANT (t));
489 ggc_mark_tree (TYPE_BINFO (t));
490 ggc_mark_tree (TYPE_CONTEXT (t));
491 (*lang_hooks.mark_tree) (t);
494 case 'b': /* A lexical block. */
495 ggc_mark_tree (BLOCK_VARS (t));
496 ggc_mark_tree (BLOCK_SUBBLOCKS (t));
497 ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
498 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
501 case 'c': /* A constant. */
502 ggc_mark_rtx (TREE_CST_RTL (t));
505 case 'r': case '<': case '1':
506 case '2': case 'e': case 's': /* Expressions. */
508 int i = TREE_CODE_LENGTH (TREE_CODE (t));
509 int first_rtl = first_rtl_op (TREE_CODE (t));
514 ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
516 ggc_mark_tree (TREE_OPERAND (t, i));
522 (*lang_hooks.mark_tree) (t);
528 /* Mark all the elements of the varray V, which contains rtxs. */
531 ggc_mark_rtx_varray (v)
537 for (i = v->num_elements - 1; i >= 0; --i)
538 ggc_mark_rtx (VARRAY_RTX (v, i));
541 /* Mark all the elements of the varray V, which contains trees. */
544 ggc_mark_tree_varray (v)
550 for (i = v->num_elements - 1; i >= 0; --i)
551 ggc_mark_tree (VARRAY_TREE (v, i));
554 /* Mark the hash table-entry HE. Its key field is really a tree. */
557 ggc_mark_tree_hash_table_entry (he, k)
558 struct hash_entry *he;
559 hash_table_key k ATTRIBUTE_UNUSED;
561 ggc_mark_tree ((tree) he->key);
565 /* Mark all the elements of the hash-table H, which contains trees. */
568 ggc_mark_tree_hash_table (ht)
569 struct hash_table *ht;
571 hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
574 /* Type-correct function to pass to ggc_add_root. It just forwards
575 *ELT (which is an rtx) to ggc_mark_rtx. */
578 ggc_mark_rtx_ptr (elt)
581 ggc_mark_rtx (*(rtx *) elt);
584 /* Type-correct function to pass to ggc_add_root. It just forwards
585 *ELT (which is a tree) to ggc_mark_tree. */
588 ggc_mark_tree_ptr (elt)
591 ggc_mark_tree (*(tree *) elt);
594 /* Type-correct function to pass to ggc_add_root. It just forwards
595 ELT (which is really a varray_type *) to ggc_mark_rtx_varray. */
598 ggc_mark_rtx_varray_ptr (elt)
601 ggc_mark_rtx_varray (*(varray_type *) elt);
604 /* Type-correct function to pass to ggc_add_root. It just forwards
605 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
608 ggc_mark_tree_varray_ptr (elt)
611 ggc_mark_tree_varray (*(varray_type *) elt);
614 /* Type-correct function to pass to ggc_add_root. It just forwards
615 ELT (which is really a struct hash_table **) to
616 ggc_mark_tree_hash_table. */
619 ggc_mark_tree_hash_table_ptr (elt)
622 ggc_mark_tree_hash_table (*(struct hash_table **) elt);
625 /* Allocate a block of memory, then clear it. */
627 ggc_alloc_cleared (size)
630 void *buf = ggc_alloc (size);
631 memset (buf, 0, size);
635 /* Print statistics that are independent of the collector in use. */
636 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
638 : ((x) < 1024*1024*10 \
640 : (x) / (1024*1024))))
641 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
644 ggc_print_common_statistics (stream, stats)
646 ggc_statistics *stats;
650 /* Set the pointer so that during collection we will actually gather
654 /* Then do one collection to fill in the statistics. */
657 /* Total the statistics. */
658 for (code = 0; code < MAX_TREE_CODES; ++code)
660 stats->total_num_trees += stats->num_trees[code];
661 stats->total_size_trees += stats->size_trees[code];
663 for (code = 0; code < NUM_RTX_CODE; ++code)
665 stats->total_num_rtxs += stats->num_rtxs[code];
666 stats->total_size_rtxs += stats->size_rtxs[code];
669 /* Print the statistics for trees. */
670 fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
671 "Number", "Bytes", "% Total");
672 for (code = 0; code < MAX_TREE_CODES; ++code)
673 if (ggc_stats->num_trees[code])
675 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
676 tree_code_name[code],
677 ggc_stats->num_trees[code],
678 SCALE (ggc_stats->size_trees[code]),
679 LABEL (ggc_stats->size_trees[code]),
680 (100 * ((double) ggc_stats->size_trees[code])
681 / ggc_stats->total_size_trees));
684 "%-17s%10u%16ld%c\n", "Total",
685 ggc_stats->total_num_trees,
686 SCALE (ggc_stats->total_size_trees),
687 LABEL (ggc_stats->total_size_trees));
689 /* Print the statistics for RTL. */
690 fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
691 "Number", "Bytes", "% Total");
692 for (code = 0; code < NUM_RTX_CODE; ++code)
693 if (ggc_stats->num_rtxs[code])
695 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
697 ggc_stats->num_rtxs[code],
698 SCALE (ggc_stats->size_rtxs[code]),
699 LABEL (ggc_stats->size_rtxs[code]),
700 (100 * ((double) ggc_stats->size_rtxs[code])
701 / ggc_stats->total_size_rtxs));
704 "%-17s%10u%16ld%c\n", "Total",
705 ggc_stats->total_num_rtxs,
706 SCALE (ggc_stats->total_size_rtxs),
707 LABEL (ggc_stats->total_size_rtxs));
709 /* Don't gather statistics any more. */