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 /* Trees that have been marked, but whose children still need marking. */
39 varray_type ggc_pending_trees
;
41 static void ggc_mark_rtx_children_1
PARAMS ((rtx
));
42 static void ggc_mark_rtx_ptr
PARAMS ((void *));
43 static void ggc_mark_tree_ptr
PARAMS ((void *));
44 static void ggc_mark_rtx_varray_ptr
PARAMS ((void *));
45 static void ggc_mark_tree_varray_ptr
PARAMS ((void *));
46 static void ggc_mark_tree_hash_table_ptr
PARAMS ((void *));
47 static int ggc_htab_delete
PARAMS ((void **, void *));
48 static void ggc_mark_trees
PARAMS ((void));
49 static bool ggc_mark_tree_hash_table_entry
PARAMS ((struct hash_entry
*,
52 /* Maintain global roots that are preserved during GC. */
54 /* Global roots that are preserved during calls to gc. */
58 struct ggc_root
*next
;
62 void (*cb
) PARAMS ((void *));
65 static struct ggc_root
*roots
;
67 /* Add BASE as a new garbage collection root. It is an array of
68 length NELT with each element SIZE bytes long. CB is a
69 function that will be called with a pointer to each element
70 of the array; it is the intention that CB call the appropriate
71 routine to mark gc-able memory for that element. */
74 ggc_add_root (base
, nelt
, size
, cb
)
77 void (*cb
) PARAMS ((void *));
79 struct ggc_root
*x
= (struct ggc_root
*) xmalloc (sizeof (*x
));
90 /* Register an array of rtx as a GC root. */
93 ggc_add_rtx_root (base
, nelt
)
97 ggc_add_root (base
, nelt
, sizeof (rtx
), ggc_mark_rtx_ptr
);
100 /* Register an array of trees as a GC root. */
103 ggc_add_tree_root (base
, nelt
)
107 ggc_add_root (base
, nelt
, sizeof (tree
), ggc_mark_tree_ptr
);
110 /* Register a varray of rtxs as a GC root. */
113 ggc_add_rtx_varray_root (base
, nelt
)
117 ggc_add_root (base
, nelt
, sizeof (varray_type
),
118 ggc_mark_rtx_varray_ptr
);
121 /* Register a varray of trees as a GC root. */
124 ggc_add_tree_varray_root (base
, nelt
)
128 ggc_add_root (base
, nelt
, sizeof (varray_type
),
129 ggc_mark_tree_varray_ptr
);
132 /* Register a hash table of trees as a GC root. */
135 ggc_add_tree_hash_table_root (base
, nelt
)
136 struct hash_table
**base
;
139 ggc_add_root (base
, nelt
, sizeof (struct hash_table
*),
140 ggc_mark_tree_hash_table_ptr
);
143 /* Remove the previously registered GC root at BASE. */
149 struct ggc_root
*x
, **p
;
151 p
= &roots
, x
= roots
;
167 /* Add a hash table to be scanned when all roots have been processed. We
168 delete any entry in the table that has not been marked. */
172 struct d_htab_root
*next
;
174 ggc_htab_marked_p marked_p
;
178 static struct d_htab_root
*d_htab_roots
;
180 /* Add X, an htab, to a list of htabs that contain objects which are allocated
181 from GC memory. Once all other roots are marked, we check each object in
182 the htab to see if it has already been marked. If not, it is deleted.
184 MARKED_P, if specified, is a function that returns 1 if the entry is to
185 be considered as "marked". If not present, the data structure pointed to
186 by the htab slot is tested. This function should be supplied if some
187 other object (such as something pointed to by that object) should be tested
188 in which case the function tests whether that object (or objects) are
189 marked (using ggc_marked_p) and returns nonzero if it is.
191 MARK, if specified, is a function that is passed the contents of a slot
192 that has been determined to have been "marked" (via the above function)
193 and marks any other objects pointed to by that object. For example,
194 we might have a hash table of memory attribute blocks, which are pointed
195 to by a MEM RTL but have a pointer to a DECL. MARKED_P in that case will
196 not be specified because we want to know if the attribute block is pointed
197 to by the MEM, but MARK must be specified because if the block has been
198 marked, we need to mark the DECL. */
201 ggc_add_deletable_htab (x
, marked_p
, mark
)
203 ggc_htab_marked_p marked_p
;
206 struct d_htab_root
*r
207 = (struct d_htab_root
*) xmalloc (sizeof (struct d_htab_root
));
209 r
->next
= d_htab_roots
;
210 r
->htab
= (htab_t
) x
;
211 r
->marked_p
= marked_p
? marked_p
: ggc_marked_p
;
216 /* Process a slot of an htab by deleting it if it has not been marked. */
219 ggc_htab_delete (slot
, info
)
223 struct d_htab_root
*r
= (struct d_htab_root
*) info
;
225 if (! (*r
->marked_p
) (*slot
))
226 htab_clear_slot (r
->htab
, slot
);
233 /* Iterate through all registered roots and mark each element. */
239 struct d_htab_root
*y
;
241 VARRAY_TREE_INIT (ggc_pending_trees
, 4096, "ggc_pending_trees");
243 for (x
= roots
; x
!= NULL
; x
= x
->next
)
246 int s
= x
->size
, n
= x
->nelt
;
247 void (*cb
) PARAMS ((void *)) = x
->cb
;
250 for (i
= 0; i
< n
; ++i
, elt
+= s
)
254 /* Mark all the queued up trees, and their children. */
256 VARRAY_FREE (ggc_pending_trees
);
258 /* Now scan all hash tables that have objects which are to be deleted if
259 they are not already marked. Since these may mark more trees, we need
260 to reinitialize that varray. */
261 VARRAY_TREE_INIT (ggc_pending_trees
, 1024, "ggc_pending_trees");
263 for (y
= d_htab_roots
; y
!= NULL
; y
= y
->next
)
264 htab_traverse (y
->htab
, ggc_htab_delete
, (PTR
) y
);
266 VARRAY_FREE (ggc_pending_trees
);
269 /* R had not been previously marked, but has now been marked via
270 ggc_set_mark. Now recurse and process the children. */
273 ggc_mark_rtx_children (r
)
278 /* Special case the instruction chain. This is a data structure whose
279 chain length is potentially unbounded, and which contain references
280 within the chain (e.g. label_ref and insn_list). If do nothing here,
281 we risk blowing the stack recursing through a long chain of insns.
283 Combat this by marking all of the instructions in the chain before
284 marking the contents of those instructions. */
286 switch (GET_CODE (r
))
294 for (i
= NEXT_INSN (r
); ; i
= NEXT_INSN (i
))
295 if (! ggc_test_and_set_mark (i
))
299 for (i
= NEXT_INSN (r
); i
!= last
; i
= NEXT_INSN (i
))
300 ggc_mark_rtx_children_1 (i
);
306 ggc_mark_rtx_children_1 (r
);
310 ggc_mark_rtx_children_1 (r
)
319 enum rtx_code code
= GET_CODE (r
);
320 /* This gets set to a child rtx to eliminate tail recursion. */
323 /* Collect statistics, if appropriate. */
326 ++ggc_stats
->num_rtxs
[(int) code
];
327 ggc_stats
->size_rtxs
[(int) code
] += ggc_get_size (r
);
330 /* ??? If (some of) these are really pass-dependent info, do we
331 have any right poking our noses in? */
335 ggc_mark (MEM_ATTRS (r
));
338 ggc_mark_rtx (JUMP_LABEL (r
));
341 ggc_mark_rtx (LABEL_REFS (r
));
344 ggc_mark_rtx (LABEL_NEXTREF (r
));
345 ggc_mark_rtx (CONTAINING_INSN (r
));
348 ggc_mark_tree (ADDRESSOF_DECL (r
));
351 switch (NOTE_LINE_NUMBER (r
))
353 case NOTE_INSN_RANGE_BEG
:
354 case NOTE_INSN_RANGE_END
:
356 case NOTE_INSN_EXPECTED_VALUE
:
357 ggc_mark_rtx (NOTE_RANGE_INFO (r
));
360 case NOTE_INSN_BLOCK_BEG
:
361 case NOTE_INSN_BLOCK_END
:
362 ggc_mark_tree (NOTE_BLOCK (r
));
374 for (fmt
= GET_RTX_FORMAT (GET_CODE (r
)), i
= 0; *fmt
; ++fmt
, ++i
)
381 if (ggc_test_and_set_mark (exp
))
383 if (next_rtx
== NULL
)
386 ggc_mark_rtx_children (exp
);
390 ggc_mark_rtvec (XVEC (r
, i
));
395 while ((r
= next_rtx
) != NULL
);
398 /* V had not been previously marked, but has now been marked via
399 ggc_set_mark. Now recurse and process the children. */
402 ggc_mark_rtvec_children (v
)
407 i
= GET_NUM_ELEM (v
);
409 ggc_mark_rtx (RTVEC_ELT (v
, i
));
412 /* Recursively set marks on all of the children of the
413 GCC_PENDING_TREES. */
418 while (ggc_pending_trees
->elements_used
)
423 t
= VARRAY_TOP_TREE (ggc_pending_trees
);
424 VARRAY_POP (ggc_pending_trees
);
425 code
= TREE_CODE (t
);
427 /* Collect statistics, if appropriate. */
430 ++ggc_stats
->num_trees
[(int) code
];
431 ggc_stats
->size_trees
[(int) code
] += ggc_get_size (t
);
434 /* Bits from common. */
435 ggc_mark_tree (TREE_TYPE (t
));
436 ggc_mark_tree (TREE_CHAIN (t
));
438 /* Some nodes require special handling. */
442 ggc_mark_tree (TREE_PURPOSE (t
));
443 ggc_mark_tree (TREE_VALUE (t
));
448 int i
= TREE_VEC_LENGTH (t
);
451 ggc_mark_tree (TREE_VEC_ELT (t
, i
));
456 ggc_mark_tree (TREE_REALPART (t
));
457 ggc_mark_tree (TREE_IMAGPART (t
));
461 ggc_mark_rtx (DECL_INCOMING_RTL (t
));
465 ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t
));
468 case IDENTIFIER_NODE
:
469 (*lang_hooks
.mark_tree
) (t
);
476 /* But in general we can handle them by class. */
477 switch (TREE_CODE_CLASS (code
))
479 case 'd': /* A decl node. */
480 ggc_mark_tree (DECL_SIZE (t
));
481 ggc_mark_tree (DECL_SIZE_UNIT (t
));
482 ggc_mark_tree (DECL_NAME (t
));
483 ggc_mark_tree (DECL_CONTEXT (t
));
484 ggc_mark_tree (DECL_ARGUMENTS (t
));
485 ggc_mark_tree (DECL_RESULT_FLD (t
));
486 ggc_mark_tree (DECL_INITIAL (t
));
487 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t
));
488 ggc_mark_tree (DECL_SECTION_NAME (t
));
489 ggc_mark_tree (DECL_ATTRIBUTES (t
));
490 if (DECL_RTL_SET_P (t
))
491 ggc_mark_rtx (DECL_RTL (t
));
492 ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t
));
493 ggc_mark_tree (DECL_VINDEX (t
));
494 if (DECL_ASSEMBLER_NAME_SET_P (t
))
495 ggc_mark_tree (DECL_ASSEMBLER_NAME (t
));
496 if (TREE_CODE (t
) == FUNCTION_DECL
)
498 ggc_mark_tree (DECL_SAVED_TREE (t
));
499 ggc_mark_tree (DECL_INLINED_FNS (t
));
500 if (DECL_SAVED_INSNS (t
))
501 ggc_mark_struct_function (DECL_SAVED_INSNS (t
));
503 (*lang_hooks
.mark_tree
) (t
);
506 case 't': /* A type node. */
507 ggc_mark_tree (TYPE_SIZE (t
));
508 ggc_mark_tree (TYPE_SIZE_UNIT (t
));
509 ggc_mark_tree (TYPE_ATTRIBUTES (t
));
510 ggc_mark_tree (TYPE_VALUES (t
));
511 ggc_mark_tree (TYPE_POINTER_TO (t
));
512 ggc_mark_tree (TYPE_REFERENCE_TO (t
));
513 ggc_mark_tree (TYPE_NAME (t
));
514 ggc_mark_tree (TYPE_MIN_VALUE (t
));
515 ggc_mark_tree (TYPE_MAX_VALUE (t
));
516 ggc_mark_tree (TYPE_NEXT_VARIANT (t
));
517 ggc_mark_tree (TYPE_MAIN_VARIANT (t
));
518 ggc_mark_tree (TYPE_BINFO (t
));
519 ggc_mark_tree (TYPE_CONTEXT (t
));
520 (*lang_hooks
.mark_tree
) (t
);
523 case 'b': /* A lexical block. */
524 ggc_mark_tree (BLOCK_VARS (t
));
525 ggc_mark_tree (BLOCK_SUBBLOCKS (t
));
526 ggc_mark_tree (BLOCK_SUPERCONTEXT (t
));
527 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t
));
530 case 'c': /* A constant. */
531 ggc_mark_rtx (TREE_CST_RTL (t
));
534 case 'r': case '<': case '1':
535 case '2': case 'e': case 's': /* Expressions. */
537 int i
= TREE_CODE_LENGTH (TREE_CODE (t
));
538 int first_rtl
= first_rtl_op (TREE_CODE (t
));
543 ggc_mark_rtx ((rtx
) TREE_OPERAND (t
, i
));
545 ggc_mark_tree (TREE_OPERAND (t
, i
));
551 (*lang_hooks
.mark_tree
) (t
);
557 /* Mark all the elements of the varray V, which contains rtxs. */
560 ggc_mark_rtx_varray (v
)
566 for (i
= v
->num_elements
- 1; i
>= 0; --i
)
567 ggc_mark_rtx (VARRAY_RTX (v
, i
));
570 /* Mark all the elements of the varray V, which contains trees. */
573 ggc_mark_tree_varray (v
)
579 for (i
= v
->num_elements
- 1; i
>= 0; --i
)
580 ggc_mark_tree (VARRAY_TREE (v
, i
));
583 /* Mark the hash table-entry HE. Its key field is really a tree. */
586 ggc_mark_tree_hash_table_entry (he
, k
)
587 struct hash_entry
*he
;
588 hash_table_key k ATTRIBUTE_UNUSED
;
590 ggc_mark_tree ((tree
) he
->key
);
594 /* Mark all the elements of the hash-table H, which contains trees. */
597 ggc_mark_tree_hash_table (ht
)
598 struct hash_table
*ht
;
600 hash_traverse (ht
, ggc_mark_tree_hash_table_entry
, /*info=*/0);
603 /* Type-correct function to pass to ggc_add_root. It just forwards
604 *ELT (which is an rtx) to ggc_mark_rtx. */
607 ggc_mark_rtx_ptr (elt
)
610 ggc_mark_rtx (*(rtx
*) elt
);
613 /* Type-correct function to pass to ggc_add_root. It just forwards
614 *ELT (which is a tree) to ggc_mark_tree. */
617 ggc_mark_tree_ptr (elt
)
620 ggc_mark_tree (*(tree
*) elt
);
623 /* Type-correct function to pass to ggc_add_root. It just forwards
624 ELT (which is really a varray_type *) to ggc_mark_rtx_varray. */
627 ggc_mark_rtx_varray_ptr (elt
)
630 ggc_mark_rtx_varray (*(varray_type
*) elt
);
633 /* Type-correct function to pass to ggc_add_root. It just forwards
634 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
637 ggc_mark_tree_varray_ptr (elt
)
640 ggc_mark_tree_varray (*(varray_type
*) elt
);
643 /* Type-correct function to pass to ggc_add_root. It just forwards
644 ELT (which is really a struct hash_table **) to
645 ggc_mark_tree_hash_table. */
648 ggc_mark_tree_hash_table_ptr (elt
)
651 ggc_mark_tree_hash_table (*(struct hash_table
**) elt
);
654 /* Allocate a block of memory, then clear it. */
656 ggc_alloc_cleared (size
)
659 void *buf
= ggc_alloc (size
);
660 memset (buf
, 0, size
);
664 /* Print statistics that are independent of the collector in use. */
665 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
667 : ((x) < 1024*1024*10 \
669 : (x) / (1024*1024))))
670 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
673 ggc_print_common_statistics (stream
, stats
)
675 ggc_statistics
*stats
;
679 /* Set the pointer so that during collection we will actually gather
683 /* Then do one collection to fill in the statistics. */
686 /* Total the statistics. */
687 for (code
= 0; code
< MAX_TREE_CODES
; ++code
)
689 stats
->total_num_trees
+= stats
->num_trees
[code
];
690 stats
->total_size_trees
+= stats
->size_trees
[code
];
692 for (code
= 0; code
< NUM_RTX_CODE
; ++code
)
694 stats
->total_num_rtxs
+= stats
->num_rtxs
[code
];
695 stats
->total_size_rtxs
+= stats
->size_rtxs
[code
];
698 /* Print the statistics for trees. */
699 fprintf (stream
, "\n%-17s%10s %16s %10s\n", "Tree",
700 "Number", "Bytes", "% Total");
701 for (code
= 0; code
< MAX_TREE_CODES
; ++code
)
702 if (ggc_stats
->num_trees
[code
])
704 fprintf (stream
, "%-17s%10u%16ld%c %10.3f\n",
705 tree_code_name
[code
],
706 ggc_stats
->num_trees
[code
],
707 SCALE (ggc_stats
->size_trees
[code
]),
708 LABEL (ggc_stats
->size_trees
[code
]),
709 (100 * ((double) ggc_stats
->size_trees
[code
])
710 / ggc_stats
->total_size_trees
));
713 "%-17s%10u%16ld%c\n", "Total",
714 ggc_stats
->total_num_trees
,
715 SCALE (ggc_stats
->total_size_trees
),
716 LABEL (ggc_stats
->total_size_trees
));
718 /* Print the statistics for RTL. */
719 fprintf (stream
, "\n%-17s%10s %16s %10s\n", "RTX",
720 "Number", "Bytes", "% Total");
721 for (code
= 0; code
< NUM_RTX_CODE
; ++code
)
722 if (ggc_stats
->num_rtxs
[code
])
724 fprintf (stream
, "%-17s%10u%16ld%c %10.3f\n",
726 ggc_stats
->num_rtxs
[code
],
727 SCALE (ggc_stats
->size_rtxs
[code
]),
728 LABEL (ggc_stats
->size_rtxs
[code
]),
729 (100 * ((double) ggc_stats
->size_rtxs
[code
])
730 / ggc_stats
->total_size_rtxs
));
733 "%-17s%10u%16ld%c\n", "Total",
734 ggc_stats
->total_num_rtxs
,
735 SCALE (ggc_stats
->total_size_rtxs
),
736 LABEL (ggc_stats
->total_size_rtxs
));
738 /* Don't gather statistics any more. */