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. */
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_children_1
PARAMS ((rtx
));
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
)
283 /* Special case the instruction chain. This is a data structure whose
284 chain length is potentially unbounded, and which contain references
285 within the chain (e.g. label_ref and insn_list). If do nothing here,
286 we risk blowing the stack recursing through a long chain of insns.
288 Combat this by marking all of the instructions in the chain before
289 marking the contents of those instructions. */
291 switch (GET_CODE (r
))
299 for (i
= NEXT_INSN (r
); ; i
= NEXT_INSN (i
))
300 if (! ggc_test_and_set_mark (i
))
304 for (i
= NEXT_INSN (r
); i
!= last
; i
= NEXT_INSN (i
))
305 ggc_mark_rtx_children_1 (i
);
311 ggc_mark_rtx_children_1 (r
);
315 ggc_mark_rtx_children_1 (r
)
324 enum rtx_code code
= GET_CODE (r
);
325 /* This gets set to a child rtx to eliminate tail recursion. */
328 /* Collect statistics, if appropriate. */
331 ++ggc_stats
->num_rtxs
[(int) code
];
332 ggc_stats
->size_rtxs
[(int) code
] += ggc_get_size (r
);
335 /* ??? If (some of) these are really pass-dependent info, do we
336 have any right poking our noses in? */
340 ggc_mark (MEM_ATTRS (r
));
343 ggc_mark_rtx (JUMP_LABEL (r
));
346 ggc_mark_rtx (LABEL_REFS (r
));
349 ggc_mark_rtx (LABEL_NEXTREF (r
));
350 ggc_mark_rtx (CONTAINING_INSN (r
));
353 ggc_mark_tree (ADDRESSOF_DECL (r
));
356 ggc_mark_rtx (CONST_DOUBLE_CHAIN (r
));
359 switch (NOTE_LINE_NUMBER (r
))
361 case NOTE_INSN_RANGE_BEG
:
362 case NOTE_INSN_RANGE_END
:
364 case NOTE_INSN_EXPECTED_VALUE
:
365 ggc_mark_rtx (NOTE_RANGE_INFO (r
));
368 case NOTE_INSN_BLOCK_BEG
:
369 case NOTE_INSN_BLOCK_END
:
370 ggc_mark_tree (NOTE_BLOCK (r
));
382 for (fmt
= GET_RTX_FORMAT (GET_CODE (r
)), i
= 0; *fmt
; ++fmt
, ++i
)
389 if (ggc_test_and_set_mark (exp
))
391 if (next_rtx
== NULL
)
394 ggc_mark_rtx_children (exp
);
398 ggc_mark_rtvec (XVEC (r
, i
));
403 while ((r
= next_rtx
) != NULL
);
406 /* V had not been previously marked, but has now been marked via
407 ggc_set_mark. Now recurse and process the children. */
410 ggc_mark_rtvec_children (v
)
415 i
= GET_NUM_ELEM (v
);
417 ggc_mark_rtx (RTVEC_ELT (v
, i
));
420 /* Recursively set marks on all of the children of the
421 GCC_PENDING_TREES. */
426 while (ggc_pending_trees
->elements_used
)
431 t
= VARRAY_TOP_TREE (ggc_pending_trees
);
432 VARRAY_POP (ggc_pending_trees
);
433 code
= TREE_CODE (t
);
435 /* Collect statistics, if appropriate. */
438 ++ggc_stats
->num_trees
[(int) code
];
439 ggc_stats
->size_trees
[(int) code
] += ggc_get_size (t
);
442 /* Bits from common. */
443 ggc_mark_tree (TREE_TYPE (t
));
444 ggc_mark_tree (TREE_CHAIN (t
));
446 /* Some nodes require special handling. */
450 ggc_mark_tree (TREE_PURPOSE (t
));
451 ggc_mark_tree (TREE_VALUE (t
));
456 int i
= TREE_VEC_LENGTH (t
);
459 ggc_mark_tree (TREE_VEC_ELT (t
, i
));
464 ggc_mark_tree (TREE_REALPART (t
));
465 ggc_mark_tree (TREE_IMAGPART (t
));
469 ggc_mark_rtx (DECL_INCOMING_RTL (t
));
473 ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t
));
476 case IDENTIFIER_NODE
:
484 /* But in general we can handle them by class. */
485 switch (TREE_CODE_CLASS (code
))
487 case 'd': /* A decl node. */
488 ggc_mark_tree (DECL_SIZE (t
));
489 ggc_mark_tree (DECL_SIZE_UNIT (t
));
490 ggc_mark_tree (DECL_NAME (t
));
491 ggc_mark_tree (DECL_CONTEXT (t
));
492 ggc_mark_tree (DECL_ARGUMENTS (t
));
493 ggc_mark_tree (DECL_RESULT_FLD (t
));
494 ggc_mark_tree (DECL_INITIAL (t
));
495 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t
));
496 ggc_mark_tree (DECL_SECTION_NAME (t
));
497 ggc_mark_tree (DECL_ATTRIBUTES (t
));
498 if (DECL_RTL_SET_P (t
))
499 ggc_mark_rtx (DECL_RTL (t
));
500 ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t
));
501 ggc_mark_tree (DECL_VINDEX (t
));
502 if (DECL_ASSEMBLER_NAME_SET_P (t
))
503 ggc_mark_tree (DECL_ASSEMBLER_NAME (t
));
504 if (TREE_CODE (t
) == FUNCTION_DECL
)
506 ggc_mark_tree (DECL_SAVED_TREE (t
));
507 ggc_mark_tree (DECL_INLINED_FNS (t
));
508 if (DECL_SAVED_INSNS (t
))
509 ggc_mark_struct_function (DECL_SAVED_INSNS (t
));
514 case 't': /* A type node. */
515 ggc_mark_tree (TYPE_SIZE (t
));
516 ggc_mark_tree (TYPE_SIZE_UNIT (t
));
517 ggc_mark_tree (TYPE_ATTRIBUTES (t
));
518 ggc_mark_tree (TYPE_VALUES (t
));
519 ggc_mark_tree (TYPE_POINTER_TO (t
));
520 ggc_mark_tree (TYPE_REFERENCE_TO (t
));
521 ggc_mark_tree (TYPE_NAME (t
));
522 ggc_mark_tree (TYPE_MIN_VALUE (t
));
523 ggc_mark_tree (TYPE_MAX_VALUE (t
));
524 ggc_mark_tree (TYPE_NEXT_VARIANT (t
));
525 ggc_mark_tree (TYPE_MAIN_VARIANT (t
));
526 ggc_mark_tree (TYPE_BINFO (t
));
527 ggc_mark_tree (TYPE_CONTEXT (t
));
531 case 'b': /* A lexical block. */
532 ggc_mark_tree (BLOCK_VARS (t
));
533 ggc_mark_tree (BLOCK_SUBBLOCKS (t
));
534 ggc_mark_tree (BLOCK_SUPERCONTEXT (t
));
535 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t
));
538 case 'c': /* A constant. */
539 ggc_mark_rtx (TREE_CST_RTL (t
));
542 case 'r': case '<': case '1':
543 case '2': case 'e': case 's': /* Expressions. */
545 int i
= TREE_CODE_LENGTH (TREE_CODE (t
));
546 int first_rtl
= first_rtl_op (TREE_CODE (t
));
551 ggc_mark_rtx ((rtx
) TREE_OPERAND (t
, i
));
553 ggc_mark_tree (TREE_OPERAND (t
, i
));
565 /* Mark all the elements of the varray V, which contains rtxs. */
568 ggc_mark_rtx_varray (v
)
574 for (i
= v
->num_elements
- 1; i
>= 0; --i
)
575 ggc_mark_rtx (VARRAY_RTX (v
, i
));
578 /* Mark all the elements of the varray V, which contains trees. */
581 ggc_mark_tree_varray (v
)
587 for (i
= v
->num_elements
- 1; i
>= 0; --i
)
588 ggc_mark_tree (VARRAY_TREE (v
, i
));
591 /* Mark the hash table-entry HE. Its key field is really a tree. */
594 ggc_mark_tree_hash_table_entry (he
, k
)
595 struct hash_entry
*he
;
596 hash_table_key k ATTRIBUTE_UNUSED
;
598 ggc_mark_tree ((tree
) he
->key
);
602 /* Mark all the elements of the hash-table H, which contains trees. */
605 ggc_mark_tree_hash_table (ht
)
606 struct hash_table
*ht
;
608 hash_traverse (ht
, ggc_mark_tree_hash_table_entry
, /*info=*/0);
611 /* Type-correct function to pass to ggc_add_root. It just forwards
612 *ELT (which is an rtx) to ggc_mark_rtx. */
615 ggc_mark_rtx_ptr (elt
)
618 ggc_mark_rtx (*(rtx
*) elt
);
621 /* Type-correct function to pass to ggc_add_root. It just forwards
622 *ELT (which is a tree) to ggc_mark_tree. */
625 ggc_mark_tree_ptr (elt
)
628 ggc_mark_tree (*(tree
*) elt
);
631 /* Type-correct function to pass to ggc_add_root. It just forwards
632 ELT (which is really a varray_type *) to ggc_mark_rtx_varray. */
635 ggc_mark_rtx_varray_ptr (elt
)
638 ggc_mark_rtx_varray (*(varray_type
*) elt
);
641 /* Type-correct function to pass to ggc_add_root. It just forwards
642 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
645 ggc_mark_tree_varray_ptr (elt
)
648 ggc_mark_tree_varray (*(varray_type
*) elt
);
651 /* Type-correct function to pass to ggc_add_root. It just forwards
652 ELT (which is really a struct hash_table **) to
653 ggc_mark_tree_hash_table. */
656 ggc_mark_tree_hash_table_ptr (elt
)
659 ggc_mark_tree_hash_table (*(struct hash_table
**) elt
);
662 /* Allocate a block of memory, then clear it. */
664 ggc_alloc_cleared (size
)
667 void *buf
= ggc_alloc (size
);
668 memset (buf
, 0, size
);
672 /* Print statistics that are independent of the collector in use. */
673 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
675 : ((x) < 1024*1024*10 \
677 : (x) / (1024*1024))))
678 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
681 ggc_print_common_statistics (stream
, stats
)
683 ggc_statistics
*stats
;
687 /* Set the pointer so that during collection we will actually gather
691 /* Then do one collection to fill in the statistics. */
694 /* Total the statistics. */
695 for (code
= 0; code
< MAX_TREE_CODES
; ++code
)
697 stats
->total_num_trees
+= stats
->num_trees
[code
];
698 stats
->total_size_trees
+= stats
->size_trees
[code
];
700 for (code
= 0; code
< NUM_RTX_CODE
; ++code
)
702 stats
->total_num_rtxs
+= stats
->num_rtxs
[code
];
703 stats
->total_size_rtxs
+= stats
->size_rtxs
[code
];
706 /* Print the statistics for trees. */
707 fprintf (stream
, "\n%-17s%10s %16s %10s\n", "Tree",
708 "Number", "Bytes", "% Total");
709 for (code
= 0; code
< MAX_TREE_CODES
; ++code
)
710 if (ggc_stats
->num_trees
[code
])
712 fprintf (stream
, "%-17s%10u%16ld%c %10.3f\n",
713 tree_code_name
[code
],
714 ggc_stats
->num_trees
[code
],
715 SCALE (ggc_stats
->size_trees
[code
]),
716 LABEL (ggc_stats
->size_trees
[code
]),
717 (100 * ((double) ggc_stats
->size_trees
[code
])
718 / ggc_stats
->total_size_trees
));
721 "%-17s%10u%16ld%c\n", "Total",
722 ggc_stats
->total_num_trees
,
723 SCALE (ggc_stats
->total_size_trees
),
724 LABEL (ggc_stats
->total_size_trees
));
726 /* Print the statistics for RTL. */
727 fprintf (stream
, "\n%-17s%10s %16s %10s\n", "RTX",
728 "Number", "Bytes", "% Total");
729 for (code
= 0; code
< NUM_RTX_CODE
; ++code
)
730 if (ggc_stats
->num_rtxs
[code
])
732 fprintf (stream
, "%-17s%10u%16ld%c %10.3f\n",
734 ggc_stats
->num_rtxs
[code
],
735 SCALE (ggc_stats
->size_rtxs
[code
]),
736 LABEL (ggc_stats
->size_rtxs
[code
]),
737 (100 * ((double) ggc_stats
->size_rtxs
[code
])
738 / ggc_stats
->total_size_rtxs
));
741 "%-17s%10u%16ld%c\n", "Total",
742 ggc_stats
->total_num_rtxs
,
743 SCALE (ggc_stats
->total_size_rtxs
),
744 LABEL (ggc_stats
->total_size_rtxs
));
746 /* Don't gather statistics any more. */