OSDN Git Service

2002-03-30 Daniel Berlin <dan@dberlin.org>
[pf3gnuchains/gcc-fork.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 }