gcc-common.c (lang_mark_false_label_stack): Remove.
[gcc.git] / gcc / ggc-common.c
1 /* Simple garbage collection for the GNU compiler.
2 Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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
9 version.
10
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
14 for more details.
15
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
19 02111-1307, USA. */
20
21 /* Generic garbage collection (GC) functions and data, not specific to
22 any particular GC implementation. */
23
24 #include "config.h"
25 #include "system.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "tm_p.h"
29 #include "hash.h"
30 #include "hashtab.h"
31 #include "varray.h"
32 #include "ggc.h"
33 #include "langhooks.h"
34
35 /* Statistics about the allocation. */
36 static ggc_statistics *ggc_stats;
37
38 /* Trees that have been marked, but whose children still need marking. */
39 varray_type ggc_pending_trees;
40
41 static void ggc_mark_rtx_ptr PARAMS ((void *));
42 static void ggc_mark_tree_ptr PARAMS ((void *));
43 static void ggc_mark_rtx_varray_ptr PARAMS ((void *));
44 static void ggc_mark_tree_varray_ptr PARAMS ((void *));
45 static void ggc_mark_tree_hash_table_ptr PARAMS ((void *));
46 static int ggc_htab_delete PARAMS ((void **, void *));
47 static void ggc_mark_trees PARAMS ((void));
48 static bool ggc_mark_tree_hash_table_entry PARAMS ((struct hash_entry *,
49 hash_table_key));
50
51 /* Maintain global roots that are preserved during GC. */
52
53 /* Global roots that are preserved during calls to gc. */
54
55 struct ggc_root
56 {
57 struct ggc_root *next;
58 void *base;
59 int nelt;
60 int size;
61 void (*cb) PARAMS ((void *));
62 };
63
64 static struct ggc_root *roots;
65
66 /* Add BASE as a new garbage collection root. It is an array of
67 length NELT with each element SIZE bytes long. CB is a
68 function that will be called with a pointer to each element
69 of the array; it is the intention that CB call the appropriate
70 routine to mark gc-able memory for that element. */
71
72 void
73 ggc_add_root (base, nelt, size, cb)
74 void *base;
75 int nelt, size;
76 void (*cb) PARAMS ((void *));
77 {
78 struct ggc_root *x = (struct ggc_root *) xmalloc (sizeof (*x));
79
80 x->next = roots;
81 x->base = base;
82 x->nelt = nelt;
83 x->size = size;
84 x->cb = cb;
85
86 roots = x;
87 }
88
89 /* Register an array of rtx as a GC root. */
90
91 void
92 ggc_add_rtx_root (base, nelt)
93 rtx *base;
94 int nelt;
95 {
96 ggc_add_root (base, nelt, sizeof (rtx), ggc_mark_rtx_ptr);
97 }
98
99 /* Register an array of trees as a GC root. */
100
101 void
102 ggc_add_tree_root (base, nelt)
103 tree *base;
104 int nelt;
105 {
106 ggc_add_root (base, nelt, sizeof (tree), ggc_mark_tree_ptr);
107 }
108
109 /* Register a varray of rtxs as a GC root. */
110
111 void
112 ggc_add_rtx_varray_root (base, nelt)
113 varray_type *base;
114 int nelt;
115 {
116 ggc_add_root (base, nelt, sizeof (varray_type),
117 ggc_mark_rtx_varray_ptr);
118 }
119
120 /* Register a varray of trees as a GC root. */
121
122 void
123 ggc_add_tree_varray_root (base, nelt)
124 varray_type *base;
125 int nelt;
126 {
127 ggc_add_root (base, nelt, sizeof (varray_type),
128 ggc_mark_tree_varray_ptr);
129 }
130
131 /* Register a hash table of trees as a GC root. */
132
133 void
134 ggc_add_tree_hash_table_root (base, nelt)
135 struct hash_table **base;
136 int nelt;
137 {
138 ggc_add_root (base, nelt, sizeof (struct hash_table *),
139 ggc_mark_tree_hash_table_ptr);
140 }
141
142 /* Remove the previously registered GC root at BASE. */
143
144 void
145 ggc_del_root (base)
146 void *base;
147 {
148 struct ggc_root *x, **p;
149
150 p = &roots, x = roots;
151 while (x)
152 {
153 if (x->base == base)
154 {
155 *p = x->next;
156 free (x);
157 return;
158 }
159 p = &x->next;
160 x = x->next;
161 }
162
163 abort ();
164 }
165
166 /* Add a hash table to be scanned when all roots have been processed. We
167 delete any entry in the table that has not been marked. */
168
169 struct d_htab_root
170 {
171 struct d_htab_root *next;
172 htab_t htab;
173 ggc_htab_marked_p marked_p;
174 ggc_htab_mark mark;
175 };
176
177 static struct d_htab_root *d_htab_roots;
178
179 /* Add X, an htab, to a list of htabs that contain objects which are allocated
180 from GC memory. Once all other roots are marked, we check each object in
181 the htab to see if it has already been marked. If not, it is deleted.
182
183 MARKED_P, if specified, is a function that returns 1 if the entry is to
184 be considered as "marked". If not present, the data structure pointed to
185 by the htab slot is tested. This function should be supplied if some
186 other object (such as something pointed to by that object) should be tested
187 in which case the function tests whether that object (or objects) are
188 marked (using ggc_marked_p) and returns nonzero if it is.
189
190 MARK, if specified, is a function that is passed the contents of a slot
191 that has been determined to have been "marked" (via the above function)
192 and marks any other objects pointed to by that object. For example,
193 we might have a hash table of memory attribute blocks, which are pointed
194 to by a MEM RTL but have a pointer to a DECL. MARKED_P in that case will
195 not be specified because we want to know if the attribute block is pointed
196 to by the MEM, but MARK must be specified because if the block has been
197 marked, we need to mark the DECL. */
198
199 void
200 ggc_add_deletable_htab (x, marked_p, mark)
201 PTR x;
202 ggc_htab_marked_p marked_p;
203 ggc_htab_mark mark;
204 {
205 struct d_htab_root *r
206 = (struct d_htab_root *) xmalloc (sizeof (struct d_htab_root));
207
208 r->next = d_htab_roots;
209 r->htab = (htab_t) x;
210 r->marked_p = marked_p ? marked_p : ggc_marked_p;
211 r->mark = mark;
212 d_htab_roots = r;
213 }
214
215 /* Process a slot of an htab by deleting it if it has not been marked. */
216
217 static int
218 ggc_htab_delete (slot, info)
219 void **slot;
220 void *info;
221 {
222 struct d_htab_root *r = (struct d_htab_root *) info;
223
224 if (! (*r->marked_p) (*slot))
225 htab_clear_slot (r->htab, slot);
226 else if (r->mark)
227 (*r->mark) (*slot);
228
229 return 1;
230 }
231
232 /* Iterate through all registered roots and mark each element. */
233
234 void
235 ggc_mark_roots ()
236 {
237 struct ggc_root *x;
238 struct d_htab_root *y;
239
240 VARRAY_TREE_INIT (ggc_pending_trees, 4096, "ggc_pending_trees");
241
242 for (x = roots; x != NULL; x = x->next)
243 {
244 char *elt = x->base;
245 int s = x->size, n = x->nelt;
246 void (*cb) PARAMS ((void *)) = x->cb;
247 int i;
248
249 for (i = 0; i < n; ++i, elt += s)
250 (*cb)(elt);
251 }
252
253 /* Mark all the queued up trees, and their children. */
254 ggc_mark_trees ();
255 VARRAY_FREE (ggc_pending_trees);
256
257 /* Now scan all hash tables that have objects which are to be deleted if
258 they are not already marked. Since these may mark more trees, we need
259 to reinitialize that varray. */
260 VARRAY_TREE_INIT (ggc_pending_trees, 1024, "ggc_pending_trees");
261
262 for (y = d_htab_roots; y != NULL; y = y->next)
263 htab_traverse (y->htab, ggc_htab_delete, (PTR) y);
264 ggc_mark_trees ();
265 VARRAY_FREE (ggc_pending_trees);
266 }
267
268 /* R had not been previously marked, but has now been marked via
269 ggc_set_mark. Now recurse and process the children. */
270
271 void
272 ggc_mark_rtx_children (r)
273 rtx r;
274 {
275 const char *fmt;
276 int i;
277 rtx next_rtx;
278
279 do
280 {
281 enum rtx_code code = GET_CODE (r);
282 /* This gets set to a child rtx to eliminate tail recursion. */
283 next_rtx = NULL;
284
285 /* Collect statistics, if appropriate. */
286 if (ggc_stats)
287 {
288 ++ggc_stats->num_rtxs[(int) code];
289 ggc_stats->size_rtxs[(int) code] += ggc_get_size (r);
290 }
291
292 /* ??? If (some of) these are really pass-dependent info, do we
293 have any right poking our noses in? */
294 switch (code)
295 {
296 case MEM:
297 ggc_mark (MEM_ATTRS (r));
298 break;
299 case JUMP_INSN:
300 ggc_mark_rtx (JUMP_LABEL (r));
301 break;
302 case CODE_LABEL:
303 ggc_mark_rtx (LABEL_REFS (r));
304 break;
305 case LABEL_REF:
306 ggc_mark_rtx (LABEL_NEXTREF (r));
307 ggc_mark_rtx (CONTAINING_INSN (r));
308 break;
309 case ADDRESSOF:
310 ggc_mark_tree (ADDRESSOF_DECL (r));
311 break;
312 case CONST_DOUBLE:
313 ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
314 break;
315 case NOTE:
316 switch (NOTE_LINE_NUMBER (r))
317 {
318 case NOTE_INSN_RANGE_BEG:
319 case NOTE_INSN_RANGE_END:
320 case NOTE_INSN_LIVE:
321 case NOTE_INSN_EXPECTED_VALUE:
322 ggc_mark_rtx (NOTE_RANGE_INFO (r));
323 break;
324
325 case NOTE_INSN_BLOCK_BEG:
326 case NOTE_INSN_BLOCK_END:
327 ggc_mark_tree (NOTE_BLOCK (r));
328 break;
329
330 default:
331 break;
332 }
333 break;
334
335 default:
336 break;
337 }
338
339 for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
340 {
341 rtx exp;
342 switch (*fmt)
343 {
344 case 'e': case 'u':
345 exp = XEXP (r, i);
346 if (ggc_test_and_set_mark (exp))
347 {
348 if (next_rtx == NULL)
349 next_rtx = exp;
350 else
351 ggc_mark_rtx_children (exp);
352 }
353 break;
354 case 'V': case 'E':
355 ggc_mark_rtvec (XVEC (r, i));
356 break;
357 }
358 }
359 }
360 while ((r = next_rtx) != NULL);
361 }
362
363 /* V had not been previously marked, but has now been marked via
364 ggc_set_mark. Now recurse and process the children. */
365
366 void
367 ggc_mark_rtvec_children (v)
368 rtvec v;
369 {
370 int i;
371
372 i = GET_NUM_ELEM (v);
373 while (--i >= 0)
374 ggc_mark_rtx (RTVEC_ELT (v, i));
375 }
376
377 /* Recursively set marks on all of the children of the
378 GCC_PENDING_TREES. */
379
380 static void
381 ggc_mark_trees ()
382 {
383 while (ggc_pending_trees->elements_used)
384 {
385 tree t;
386 enum tree_code code;
387
388 t = VARRAY_TOP_TREE (ggc_pending_trees);
389 VARRAY_POP (ggc_pending_trees);
390 code = TREE_CODE (t);
391
392 /* Collect statistics, if appropriate. */
393 if (ggc_stats)
394 {
395 ++ggc_stats->num_trees[(int) code];
396 ggc_stats->size_trees[(int) code] += ggc_get_size (t);
397 }
398
399 /* Bits from common. */
400 ggc_mark_tree (TREE_TYPE (t));
401 ggc_mark_tree (TREE_CHAIN (t));
402
403 /* Some nodes require special handling. */
404 switch (code)
405 {
406 case TREE_LIST:
407 ggc_mark_tree (TREE_PURPOSE (t));
408 ggc_mark_tree (TREE_VALUE (t));
409 continue;
410
411 case TREE_VEC:
412 {
413 int i = TREE_VEC_LENGTH (t);
414
415 while (--i >= 0)
416 ggc_mark_tree (TREE_VEC_ELT (t, i));
417 continue;
418 }
419
420 case COMPLEX_CST:
421 ggc_mark_tree (TREE_REALPART (t));
422 ggc_mark_tree (TREE_IMAGPART (t));
423 break;
424
425 case PARM_DECL:
426 ggc_mark_rtx (DECL_INCOMING_RTL (t));
427 break;
428
429 case FIELD_DECL:
430 ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
431 break;
432
433 case IDENTIFIER_NODE:
434 (*lang_hooks.mark_tree) (t);
435 continue;
436
437 default:
438 break;
439 }
440
441 /* But in general we can handle them by class. */
442 switch (TREE_CODE_CLASS (code))
443 {
444 case 'd': /* A decl node. */
445 ggc_mark_tree (DECL_SIZE (t));
446 ggc_mark_tree (DECL_SIZE_UNIT (t));
447 ggc_mark_tree (DECL_NAME (t));
448 ggc_mark_tree (DECL_CONTEXT (t));
449 ggc_mark_tree (DECL_ARGUMENTS (t));
450 ggc_mark_tree (DECL_RESULT_FLD (t));
451 ggc_mark_tree (DECL_INITIAL (t));
452 ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
453 ggc_mark_tree (DECL_SECTION_NAME (t));
454 ggc_mark_tree (DECL_ATTRIBUTES (t));
455 if (DECL_RTL_SET_P (t))
456 ggc_mark_rtx (DECL_RTL (t));
457 ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
458 ggc_mark_tree (DECL_VINDEX (t));
459 if (DECL_ASSEMBLER_NAME_SET_P (t))
460 ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
461 if (TREE_CODE (t) == FUNCTION_DECL)
462 {
463 ggc_mark_tree (DECL_SAVED_TREE (t));
464 ggc_mark_tree (DECL_INLINED_FNS (t));
465 if (DECL_SAVED_INSNS (t))
466 ggc_mark_struct_function (DECL_SAVED_INSNS (t));
467 }
468 (*lang_hooks.mark_tree) (t);
469 break;
470
471 case 't': /* A type node. */
472 ggc_mark_tree (TYPE_SIZE (t));
473 ggc_mark_tree (TYPE_SIZE_UNIT (t));
474 ggc_mark_tree (TYPE_ATTRIBUTES (t));
475 ggc_mark_tree (TYPE_VALUES (t));
476 ggc_mark_tree (TYPE_POINTER_TO (t));
477 ggc_mark_tree (TYPE_REFERENCE_TO (t));
478 ggc_mark_tree (TYPE_NAME (t));
479 ggc_mark_tree (TYPE_MIN_VALUE (t));
480 ggc_mark_tree (TYPE_MAX_VALUE (t));
481 ggc_mark_tree (TYPE_NEXT_VARIANT (t));
482 ggc_mark_tree (TYPE_MAIN_VARIANT (t));
483 ggc_mark_tree (TYPE_BINFO (t));
484 ggc_mark_tree (TYPE_CONTEXT (t));
485 (*lang_hooks.mark_tree) (t);
486 break;
487
488 case 'b': /* A lexical block. */
489 ggc_mark_tree (BLOCK_VARS (t));
490 ggc_mark_tree (BLOCK_SUBBLOCKS (t));
491 ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
492 ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
493 break;
494
495 case 'c': /* A constant. */
496 ggc_mark_rtx (TREE_CST_RTL (t));
497 break;
498
499 case 'r': case '<': case '1':
500 case '2': case 'e': case 's': /* Expressions. */
501 {
502 int i = TREE_CODE_LENGTH (TREE_CODE (t));
503 int first_rtl = first_rtl_op (TREE_CODE (t));
504
505 while (--i >= 0)
506 {
507 if (i >= first_rtl)
508 ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
509 else
510 ggc_mark_tree (TREE_OPERAND (t, i));
511 }
512 break;
513 }
514
515 case 'x':
516 (*lang_hooks.mark_tree) (t);
517 break;
518 }
519 }
520 }
521
522 /* Mark all the elements of the varray V, which contains rtxs. */
523
524 void
525 ggc_mark_rtx_varray (v)
526 varray_type v;
527 {
528 int i;
529
530 if (v)
531 for (i = v->num_elements - 1; i >= 0; --i)
532 ggc_mark_rtx (VARRAY_RTX (v, i));
533 }
534
535 /* Mark all the elements of the varray V, which contains trees. */
536
537 void
538 ggc_mark_tree_varray (v)
539 varray_type v;
540 {
541 int i;
542
543 if (v)
544 for (i = v->num_elements - 1; i >= 0; --i)
545 ggc_mark_tree (VARRAY_TREE (v, i));
546 }
547
548 /* Mark the hash table-entry HE. Its key field is really a tree. */
549
550 static bool
551 ggc_mark_tree_hash_table_entry (he, k)
552 struct hash_entry *he;
553 hash_table_key k ATTRIBUTE_UNUSED;
554 {
555 ggc_mark_tree ((tree) he->key);
556 return true;
557 }
558
559 /* Mark all the elements of the hash-table H, which contains trees. */
560
561 void
562 ggc_mark_tree_hash_table (ht)
563 struct hash_table *ht;
564 {
565 hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
566 }
567
568 /* Type-correct function to pass to ggc_add_root. It just forwards
569 *ELT (which is an rtx) to ggc_mark_rtx. */
570
571 static void
572 ggc_mark_rtx_ptr (elt)
573 void *elt;
574 {
575 ggc_mark_rtx (*(rtx *) elt);
576 }
577
578 /* Type-correct function to pass to ggc_add_root. It just forwards
579 *ELT (which is a tree) to ggc_mark_tree. */
580
581 static void
582 ggc_mark_tree_ptr (elt)
583 void *elt;
584 {
585 ggc_mark_tree (*(tree *) elt);
586 }
587
588 /* Type-correct function to pass to ggc_add_root. It just forwards
589 ELT (which is really a varray_type *) to ggc_mark_rtx_varray. */
590
591 static void
592 ggc_mark_rtx_varray_ptr (elt)
593 void *elt;
594 {
595 ggc_mark_rtx_varray (*(varray_type *) elt);
596 }
597
598 /* Type-correct function to pass to ggc_add_root. It just forwards
599 ELT (which is really a varray_type *) to ggc_mark_tree_varray. */
600
601 static void
602 ggc_mark_tree_varray_ptr (elt)
603 void *elt;
604 {
605 ggc_mark_tree_varray (*(varray_type *) elt);
606 }
607
608 /* Type-correct function to pass to ggc_add_root. It just forwards
609 ELT (which is really a struct hash_table **) to
610 ggc_mark_tree_hash_table. */
611
612 static void
613 ggc_mark_tree_hash_table_ptr (elt)
614 void *elt;
615 {
616 ggc_mark_tree_hash_table (*(struct hash_table **) elt);
617 }
618
619 /* Allocate a block of memory, then clear it. */
620 void *
621 ggc_alloc_cleared (size)
622 size_t size;
623 {
624 void *buf = ggc_alloc (size);
625 memset (buf, 0, size);
626 return buf;
627 }
628
629 /* Print statistics that are independent of the collector in use. */
630 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
631 ? (x) \
632 : ((x) < 1024*1024*10 \
633 ? (x) / 1024 \
634 : (x) / (1024*1024))))
635 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
636
637 void
638 ggc_print_common_statistics (stream, stats)
639 FILE *stream;
640 ggc_statistics *stats;
641 {
642 int code;
643
644 /* Set the pointer so that during collection we will actually gather
645 the statistics. */
646 ggc_stats = stats;
647
648 /* Then do one collection to fill in the statistics. */
649 ggc_collect ();
650
651 /* Total the statistics. */
652 for (code = 0; code < MAX_TREE_CODES; ++code)
653 {
654 stats->total_num_trees += stats->num_trees[code];
655 stats->total_size_trees += stats->size_trees[code];
656 }
657 for (code = 0; code < NUM_RTX_CODE; ++code)
658 {
659 stats->total_num_rtxs += stats->num_rtxs[code];
660 stats->total_size_rtxs += stats->size_rtxs[code];
661 }
662
663 /* Print the statistics for trees. */
664 fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree",
665 "Number", "Bytes", "% Total");
666 for (code = 0; code < MAX_TREE_CODES; ++code)
667 if (ggc_stats->num_trees[code])
668 {
669 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
670 tree_code_name[code],
671 ggc_stats->num_trees[code],
672 SCALE (ggc_stats->size_trees[code]),
673 LABEL (ggc_stats->size_trees[code]),
674 (100 * ((double) ggc_stats->size_trees[code])
675 / ggc_stats->total_size_trees));
676 }
677 fprintf (stream,
678 "%-17s%10u%16ld%c\n", "Total",
679 ggc_stats->total_num_trees,
680 SCALE (ggc_stats->total_size_trees),
681 LABEL (ggc_stats->total_size_trees));
682
683 /* Print the statistics for RTL. */
684 fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX",
685 "Number", "Bytes", "% Total");
686 for (code = 0; code < NUM_RTX_CODE; ++code)
687 if (ggc_stats->num_rtxs[code])
688 {
689 fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
690 rtx_name[code],
691 ggc_stats->num_rtxs[code],
692 SCALE (ggc_stats->size_rtxs[code]),
693 LABEL (ggc_stats->size_rtxs[code]),
694 (100 * ((double) ggc_stats->size_rtxs[code])
695 / ggc_stats->total_size_rtxs));
696 }
697 fprintf (stream,
698 "%-17s%10u%16ld%c\n", "Total",
699 ggc_stats->total_num_rtxs,
700 SCALE (ggc_stats->total_size_rtxs),
701 LABEL (ggc_stats->total_size_rtxs));
702
703 /* Don't gather statistics any more. */
704 ggc_stats = NULL;
705 }