OSDN Git Service

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