OSDN Git Service

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