1 /* Simple garbage collection for the GNU compiler.
2 Copyright (C) 1998 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
30 /* Debugging flags. */
34 /* Global lists of roots, rtxs, and trees. */
38 struct ggc_root
*next
;
42 void (*cb
) PROTO ((void *));
45 static struct ggc_root
*roots
;
49 struct ggc_rtx
*chain
;
53 static struct ggc_rtx
*rtxs
;
57 struct ggc_rtvec
*chain
;
61 static struct ggc_rtvec
*vecs
;
65 struct ggc_tree
*chain
;
69 static struct ggc_tree
*trees
;
73 struct ggc_string
*chain
;
78 #define GGC_STRING_MAGIC ((unsigned int)0xa1b2c3d4)
80 static struct ggc_string
*strings
;
82 /* Some statistics. */
84 static int n_rtxs_collected
;
85 static int n_vecs_collected
;
86 static int n_trees_collected
;
87 static int n_strings_collected
;
88 static int bytes_alloced_since_gc
;
95 /* Local function prototypes. */
97 static void ggc_free_rtx
PROTO ((struct ggc_rtx
*r
));
98 static void ggc_free_tree
PROTO ((struct ggc_tree
*t
));
99 static void ggc_mark_rtx_ptr
PROTO ((void *elt
));
100 static void ggc_mark_tree_ptr
PROTO ((void *elt
));
101 static void ggc_mark_tree_varray_ptr
PROTO ((void *elt
));
102 static void ggc_mark_tree_hash_table_ptr
PROTO ((void *elt
));
103 static boolean ggc_mark_tree_hash_table_entry
PROTO ((struct hash_entry
*,
106 /* These allocators are dreadfully simple, with no caching whatsoever so
107 that Purify-like tools that do allocation versioning can catch errors.
108 This collector is never going to go fast anyway. */
111 ggc_alloc_rtx (nslots
)
115 int size
= sizeof(*n
) + (nslots
-1) * sizeof(rtunion
);
117 n
= (struct ggc_rtx
*) xmalloc (size
);
118 bzero ((char *) n
, size
);
123 fprintf (dump
, "alloc rtx %p\n", &n
->rtx
);
126 bytes_alloced_since_gc
+= size
;
132 ggc_alloc_rtvec (nelt
)
136 int size
= sizeof (*v
) + (nelt
- 1) * sizeof (rtunion
);
138 v
= (struct ggc_rtvec
*) xmalloc (size
);
139 bzero ((char *) v
, size
);
144 fprintf(dump
, "alloc vec %p\n", &v
->vec
);
147 bytes_alloced_since_gc
+= size
;
153 ggc_alloc_tree (length
)
157 int size
= sizeof(*n
) - sizeof(n
->tree
) + length
;
159 n
= (struct ggc_tree
*) xmalloc (size
);
160 bzero ((char *) n
, size
);
165 fprintf(dump
, "alloc tree %p\n", &n
->tree
);
168 bytes_alloced_since_gc
+= size
;
174 ggc_alloc_string (contents
, length
)
175 const char *contents
;
178 struct ggc_string
*s
;
183 if (contents
== NULL
)
185 length
= strlen (contents
);
188 size
= (s
->string
- (char *)s
) + length
+ 1;
189 s
= (struct ggc_string
*) xmalloc(size
);
191 s
->magic_mark
= GGC_STRING_MAGIC
;
193 bcopy (contents
, s
->string
, length
);
194 s
->string
[length
] = 0;
198 fprintf(dump
, "alloc string %p\n", &n
->tree
);
201 bytes_alloced_since_gc
+= size
;
207 /* Freeing a bit of rtl isn't quite as simple as calling free, there are
208 a few associated bits that might need freeing as well. */
215 fprintf (dump
, "collect rtx %p\n", &r
->rtx
);
218 memset (r
, 0xAA, sizeof(*r
));
224 /* Freeing an rtvec is as simple as calling free. */
231 fprintf(dump
, "collect vec %p\n", &v
->vec
);
234 memset (v
, 0xBB, sizeof (*v
) + ((GET_NUM_ELEM (&v
->vec
) - 1)
235 * sizeof (rtunion
)));
241 /* Freeing a tree node is almost, but not quite, as simple as calling free.
242 Mostly we need to let the language clean up its lang_specific bits. */
248 switch (TREE_CODE_CLASS (TREE_CODE (&t
->tree
)))
250 case 'd': /* A decl node. */
251 case 't': /* A type node. */
252 lang_cleanup_tree (&t
->tree
);
257 fprintf (dump
, "collect tree %p\n", &t
->tree
);
260 memset(&t
->tree
.common
, 0xCC, sizeof(t
->tree
.common
));
266 /* Freeing a string is as simple as calling free. */
270 struct ggc_string
*s
;
273 fprintf(dump
, "collect string %p\n", s
->string
);
276 s
->magic_mark
= 0xDDDDDDDD;
292 if (r
== NULL_RTX
|| r
->gc_mark
)
296 /* ??? If (some of) these are really pass-dependant info, do we have
297 any right poking our noses in? */
298 switch (GET_CODE (r
))
301 ggc_mark_rtx (JUMP_LABEL (r
));
304 ggc_mark_rtx (LABEL_REFS (r
));
307 ggc_mark_rtx (LABEL_NEXTREF (r
));
308 ggc_mark_rtx (CONTAINING_INSN (r
));
311 ggc_mark_tree (ADDRESSOF_DECL (r
));
314 ggc_mark_rtx (CONST_DOUBLE_CHAIN (r
));
321 for (fmt
= GET_RTX_FORMAT (GET_CODE (r
)), i
= 0; *fmt
; ++fmt
, ++i
)
326 ggc_mark_rtx (XEXP (r
, i
));
329 ggc_mark_rtvec (XVEC (r
, i
));
332 ggc_mark_string (XSTR (r
, i
));
344 if (v
== NULL
|| v
->gc_mark
)
348 i
= GET_NUM_ELEM (v
);
350 ggc_mark_rtx (RTVEC_ELT (v
, i
));
357 if (t
== NULL_TREE
|| t
->common
.gc_mark
)
359 t
->common
.gc_mark
= 1;
361 /* Bits from common. */
362 ggc_mark_tree (TREE_TYPE (t
));
363 ggc_mark_tree (TREE_CHAIN (t
));
365 /* Some nodes require special handling. */
366 switch (TREE_CODE (t
))
369 ggc_mark_tree (TREE_PURPOSE (t
));
370 ggc_mark_tree (TREE_VALUE (t
));
375 int i
= TREE_VEC_LENGTH (t
);
377 ggc_mark_tree (TREE_VEC_ELT (t
, i
));
382 ggc_mark_tree (TREE_OPERAND (t
, 0));
383 ggc_mark_tree (SAVE_EXPR_CONTEXT (t
));
384 ggc_mark_rtx (SAVE_EXPR_RTL (t
));
388 ggc_mark_rtx (RTL_EXPR_SEQUENCE (t
));
389 ggc_mark_rtx (RTL_EXPR_RTL (t
));
393 ggc_mark_tree (TREE_OPERAND (t
, 0));
394 ggc_mark_tree (TREE_OPERAND (t
, 1));
395 ggc_mark_rtx (CALL_EXPR_RTL (t
));
399 ggc_mark_tree (TREE_REALPART (t
));
400 ggc_mark_tree (TREE_IMAGPART (t
));
404 ggc_mark_string (TREE_STRING_POINTER (t
));
408 ggc_mark_rtx (DECL_INCOMING_RTL (t
));
411 case IDENTIFIER_NODE
:
412 ggc_mark_string (IDENTIFIER_POINTER (t
));
420 /* But in general we can handle them by class. */
421 switch (TREE_CODE_CLASS (TREE_CODE (t
)))
423 case 'd': /* A decl node. */
424 ggc_mark_tree (DECL_SIZE (t
));
425 ggc_mark_tree (DECL_NAME (t
));
426 ggc_mark_tree (DECL_CONTEXT (t
));
427 ggc_mark_tree (DECL_ARGUMENTS (t
));
428 ggc_mark_tree (DECL_RESULT (t
));
429 ggc_mark_tree (DECL_INITIAL (t
));
430 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t
));
431 ggc_mark_tree (DECL_ASSEMBLER_NAME (t
));
432 ggc_mark_tree (DECL_SECTION_NAME (t
));
433 ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t
));
434 ggc_mark_rtx (DECL_RTL (t
));
435 ggc_mark_tree (DECL_VINDEX (t
));
439 case 't': /* A type node. */
440 ggc_mark_tree (TYPE_SIZE (t
));
441 ggc_mark_tree (TYPE_SIZE_UNIT (t
));
442 ggc_mark_tree (TYPE_ATTRIBUTES (t
));
443 ggc_mark_tree (TYPE_VALUES (t
));
444 ggc_mark_tree (TYPE_POINTER_TO (t
));
445 ggc_mark_tree (TYPE_REFERENCE_TO (t
));
446 ggc_mark_tree (TYPE_NAME (t
));
447 ggc_mark_tree (TYPE_MIN_VALUE (t
));
448 ggc_mark_tree (TYPE_MAX_VALUE (t
));
449 ggc_mark_tree (TYPE_NEXT_VARIANT (t
));
450 ggc_mark_tree (TYPE_MAIN_VARIANT (t
));
451 ggc_mark_tree (TYPE_BINFO (t
));
452 ggc_mark_tree (TYPE_NONCOPIED_PARTS (t
));
453 ggc_mark_tree (TYPE_CONTEXT (t
));
457 case 'b': /* A lexical block. */
458 ggc_mark_tree (BLOCK_VARS (t
));
459 ggc_mark_tree (BLOCK_TYPE_TAGS (t
));
460 ggc_mark_tree (BLOCK_SUBBLOCKS (t
));
461 ggc_mark_tree (BLOCK_SUPERCONTEXT (t
));
462 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t
));
463 ggc_mark_rtx (BLOCK_END_NOTE (t
));
466 case 'c': /* A constant. */
467 ggc_mark_rtx (TREE_CST_RTL (t
));
470 case 'r': case '<': case '1':
471 case '2': case 'e': case 's': /* Expressions. */
473 int i
= tree_code_length
[TREE_CODE (t
)];
475 ggc_mark_tree (TREE_OPERAND (t
, i
));
481 /* Mark all the elements of the varray V, which contains trees. */
484 ggc_mark_tree_varray (v
)
489 for (i
= v
->num_elements
- 1; i
>= 0; --i
)
490 ggc_mark_tree (VARRAY_TREE (v
, i
));
493 /* Mark the hash table-entry HE. It's key field is really a tree. */
496 ggc_mark_tree_hash_table_entry (he
, k
)
497 struct hash_entry
*he
;
498 hash_table_key k ATTRIBUTE_UNUSED
;
500 ggc_mark_tree ((tree
) he
->key
);
504 /* Mark all the elements of the hash-table H, which contains trees. */
507 ggc_mark_tree_hash_table (ht
)
508 struct hash_table
*ht
;
510 hash_traverse (ht
, ggc_mark_tree_hash_table_entry
, /*info=*/0);
517 unsigned int *magic
= (unsigned int *)s
- 1;
522 if ((*magic
& ~(unsigned)1) != GGC_STRING_MAGIC
)
524 *magic
= GGC_STRING_MAGIC
| 1;
527 /* The top level mark-and-sweep routine. */
532 struct ggc_rtx
*r
, **rp
;
533 struct ggc_rtvec
*v
, **vp
;
534 struct ggc_tree
*t
, **tp
;
535 struct ggc_string
*s
, **sp
;
537 int time
, n_rtxs
, n_trees
, n_vecs
, n_strings
;
539 #ifndef ENABLE_CHECKING
540 /* See if it's even worth our while. */
541 if (bytes_alloced_since_gc
< 64*1024)
546 fputs (" {GC ", stderr
);
548 time
= get_run_time ();
550 /* Clean out all of the GC marks. */
551 for (r
= rtxs
; r
!= NULL
; r
= r
->chain
)
553 for (v
= vecs
; v
!= NULL
; v
= v
->chain
)
555 for (t
= trees
; t
!= NULL
; t
= t
->chain
)
556 t
->tree
.common
.gc_mark
= 0;
557 for (s
= strings
; s
!= NULL
; s
= s
->chain
)
558 s
->magic_mark
= GGC_STRING_MAGIC
;
560 /* Mark through all the roots. */
561 for (x
= roots
; x
!= NULL
; x
= x
->next
)
564 int s
= x
->size
, n
= x
->nelt
;
565 void (*cb
) PROTO ((void *)) = x
->cb
;
568 for (i
= 0; i
< n
; ++i
, elt
+= s
)
572 /* Sweep the resulting dead nodes. */
573 rp
= &rtxs
, r
= rtxs
, n_rtxs
= 0;
576 struct ggc_rtx
*chain
= r
->chain
;
588 n_rtxs_collected
+= n_rtxs
;
590 vp
= &vecs
, v
= vecs
, n_vecs
= 0;
593 struct ggc_rtvec
*chain
= v
->chain
;
605 n_vecs_collected
+= n_vecs
;
607 tp
= &trees
, t
= trees
, n_trees
= 0;
610 struct ggc_tree
*chain
= t
->chain
;
611 if (!t
->tree
.common
.gc_mark
)
622 n_trees_collected
+= n_trees
;
624 sp
= &strings
, s
= strings
, n_strings
= 0;
627 struct ggc_string
*chain
= s
->chain
;
628 if (!(s
->magic_mark
& 1))
639 n_strings_collected
+= n_strings
;
641 gc_time
+= time
= get_run_time () - time
;
645 time
= (time
+ 500) / 1000;
646 fprintf (stderr
, "%d,%d,%d,%d %d.%03d}", n_rtxs
, n_vecs
, n_trees
,
647 n_strings
, time
/ 1000, time
% 1000);
651 /* Manipulate global roots that are needed between calls to gc. */
654 ggc_add_root (base
, nelt
, size
, cb
)
657 void (*cb
) PROTO ((void *));
659 struct ggc_root
*x
= (struct ggc_root
*) xmalloc (sizeof(*x
));
671 ggc_add_rtx_root (base
, nelt
)
675 ggc_add_root (base
, nelt
, sizeof(rtx
), ggc_mark_rtx_ptr
);
679 ggc_add_tree_root (base
, nelt
)
683 ggc_add_root (base
, nelt
, sizeof(tree
), ggc_mark_tree_ptr
);
686 /* Add V (a varray full of trees) to the list of GC roots. */
689 ggc_add_tree_varray_root (base
, nelt
)
693 ggc_add_root (base
, nelt
, sizeof (varray_type
),
694 ggc_mark_tree_varray_ptr
);
697 /* Add HT (a hash-table where ever key is a tree) to the list of GC
701 ggc_add_tree_hash_table_root (base
, nelt
)
702 struct hash_table
**base
;
705 ggc_add_root (base
, nelt
, sizeof (struct hash_table
*),
706 ggc_mark_tree_hash_table_ptr
);
713 struct ggc_root
*x
, **p
;
715 p
= &roots
, x
= roots
;
732 ggc_mark_rtx_ptr (elt
)
735 ggc_mark_rtx (*(rtx
*)elt
);
739 ggc_mark_tree_ptr (elt
)
742 ggc_mark_tree (*(tree
*)elt
);
745 /* Type-correct function to pass to ggc_add_root. It just forwards
746 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
749 ggc_mark_tree_varray_ptr (elt
)
752 ggc_mark_tree_varray (*(varray_type
*)elt
);
755 /* Type-correct function to pass to ggc_add_root. It just forwards
756 ELT (which is really a struct hash_table **) to
757 ggc_mark_tree_hash_table. */
760 ggc_mark_tree_hash_table_ptr (elt
)
763 ggc_mark_tree_hash_table (*(struct hash_table
**) elt
);
767 /* Don't enable this unless you want a really really lot of data. */
768 static void __attribute__((constructor
))
771 dump
= fopen ("zgcdump", "w");
777 /* GDB really should have a memory search function. Since this is just
778 for initial debugging, I won't even pretend to get the __data_start
779 to work on any but alpha-dec-linux-gnu. */
781 search_data(void **start
, void *target
)
783 extern void *__data_start
[];
784 void **_end
= (void **)sbrk(0);
787 start
= __data_start
;
790 if (*start
== target
)