fold-const.c (hashtab.h): Include.
[platform/upstream/gcc.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 JUMP_INSN:
302           ggc_mark_rtx (JUMP_LABEL (r));
303           break;
304         case CODE_LABEL:
305           ggc_mark_rtx (LABEL_REFS (r));
306           break;
307         case LABEL_REF:
308           ggc_mark_rtx (LABEL_NEXTREF (r));
309           ggc_mark_rtx (CONTAINING_INSN (r));
310           break;
311         case ADDRESSOF:
312           ggc_mark_tree (ADDRESSOF_DECL (r));
313           break;
314         case CONST_DOUBLE:
315           ggc_mark_rtx (CONST_DOUBLE_CHAIN (r));
316           break;
317         case NOTE:
318           switch (NOTE_LINE_NUMBER (r))
319             {
320             case NOTE_INSN_RANGE_BEG:
321             case NOTE_INSN_RANGE_END:
322             case NOTE_INSN_LIVE:
323             case NOTE_INSN_EXPECTED_VALUE:
324               ggc_mark_rtx (NOTE_RANGE_INFO (r));
325               break;
326
327             case NOTE_INSN_BLOCK_BEG:
328             case NOTE_INSN_BLOCK_END:
329               ggc_mark_tree (NOTE_BLOCK (r));
330               break;
331
332             default:
333               break;
334             }
335           break;
336
337         default:
338           break;
339         }
340
341       for (fmt = GET_RTX_FORMAT (GET_CODE (r)), i = 0; *fmt ; ++fmt, ++i)
342         {
343           rtx exp;
344           switch (*fmt)
345             {
346             case 'e': case 'u':
347               exp = XEXP (r, i);
348               if (ggc_test_and_set_mark (exp))
349                 { 
350                   if (next_rtx == NULL) 
351                     next_rtx = exp; 
352                   else 
353                     ggc_mark_rtx_children (exp);
354                 } 
355               break;
356             case 'V': case 'E':
357               ggc_mark_rtvec (XVEC (r, i));
358               break;
359             }
360         }
361     }
362   while ((r = next_rtx) != NULL);
363 }
364
365 /* V had not been previously marked, but has now been marked via
366    ggc_set_mark.  Now recurse and process the children.  */
367
368 void
369 ggc_mark_rtvec_children (v)
370      rtvec v;
371 {
372   int i;
373
374   i = GET_NUM_ELEM (v);
375   while (--i >= 0)
376     ggc_mark_rtx (RTVEC_ELT (v, i));
377 }
378
379 /* Recursively set marks on all of the children of the
380    GCC_PENDING_TREES.  */
381
382 static void
383 ggc_mark_trees ()
384 {
385   while (ggc_pending_trees->elements_used)
386     {
387       tree t;
388       enum tree_code code;
389
390       t = VARRAY_TOP_TREE (ggc_pending_trees);
391       VARRAY_POP (ggc_pending_trees);
392       code = TREE_CODE (t);
393
394       /* Collect statistics, if appropriate.  */
395       if (ggc_stats)
396         {
397           ++ggc_stats->num_trees[(int) code];
398           ggc_stats->size_trees[(int) code] += ggc_get_size (t);
399         }
400
401       /* Bits from common.  */
402       ggc_mark_tree (TREE_TYPE (t));
403       ggc_mark_tree (TREE_CHAIN (t));
404
405       /* Some nodes require special handling.  */
406       switch (code)
407         {
408         case TREE_LIST:
409           ggc_mark_tree (TREE_PURPOSE (t));
410           ggc_mark_tree (TREE_VALUE (t));
411           continue;
412
413         case TREE_VEC:
414           {
415             int i = TREE_VEC_LENGTH (t);
416
417             while (--i >= 0)
418               ggc_mark_tree (TREE_VEC_ELT (t, i));
419             continue;
420           }
421
422         case COMPLEX_CST:
423           ggc_mark_tree (TREE_REALPART (t));
424           ggc_mark_tree (TREE_IMAGPART (t));
425           break;
426
427         case PARM_DECL:
428           ggc_mark_rtx (DECL_INCOMING_RTL (t));
429           break;
430
431         case FIELD_DECL:
432           ggc_mark_tree (DECL_FIELD_BIT_OFFSET (t));
433           break;
434
435         case IDENTIFIER_NODE:
436           lang_mark_tree (t);
437           continue;
438
439         default:
440           break;
441         }
442   
443       /* But in general we can handle them by class.  */
444       switch (TREE_CODE_CLASS (code))
445         {
446         case 'd': /* A decl node.  */
447           ggc_mark_tree (DECL_SIZE (t));
448           ggc_mark_tree (DECL_SIZE_UNIT (t));
449           ggc_mark_tree (DECL_NAME (t));
450           ggc_mark_tree (DECL_CONTEXT (t));
451           ggc_mark_tree (DECL_ARGUMENTS (t));
452           ggc_mark_tree (DECL_RESULT_FLD (t));
453           ggc_mark_tree (DECL_INITIAL (t));
454           ggc_mark_tree (DECL_ABSTRACT_ORIGIN (t));
455           ggc_mark_tree (DECL_SECTION_NAME (t));
456           ggc_mark_tree (DECL_MACHINE_ATTRIBUTES (t));
457           if (DECL_RTL_SET_P (t))
458             ggc_mark_rtx (DECL_RTL (t));
459           ggc_mark_rtx (DECL_LIVE_RANGE_RTL (t));
460           ggc_mark_tree (DECL_VINDEX (t));
461           if (DECL_ASSEMBLER_NAME_SET_P (t))
462             ggc_mark_tree (DECL_ASSEMBLER_NAME (t));
463           if (TREE_CODE (t) == FUNCTION_DECL && DECL_SAVED_INSNS (t))
464             ggc_mark_struct_function (DECL_SAVED_INSNS (t));
465           lang_mark_tree (t);
466           break;
467
468         case 't': /* A type node.  */
469           ggc_mark_tree (TYPE_SIZE (t));
470           ggc_mark_tree (TYPE_SIZE_UNIT (t));
471           ggc_mark_tree (TYPE_ATTRIBUTES (t));
472           ggc_mark_tree (TYPE_VALUES (t));
473           ggc_mark_tree (TYPE_POINTER_TO (t));
474           ggc_mark_tree (TYPE_REFERENCE_TO (t));
475           ggc_mark_tree (TYPE_NAME (t));
476           ggc_mark_tree (TYPE_MIN_VALUE (t));
477           ggc_mark_tree (TYPE_MAX_VALUE (t));
478           ggc_mark_tree (TYPE_NEXT_VARIANT (t));
479           ggc_mark_tree (TYPE_MAIN_VARIANT (t));
480           ggc_mark_tree (TYPE_BINFO (t));
481           ggc_mark_tree (TYPE_CONTEXT (t));
482           lang_mark_tree (t);
483           break;
484
485         case 'b': /* A lexical block.  */
486           ggc_mark_tree (BLOCK_VARS (t));
487           ggc_mark_tree (BLOCK_SUBBLOCKS (t));
488           ggc_mark_tree (BLOCK_SUPERCONTEXT (t));
489           ggc_mark_tree (BLOCK_ABSTRACT_ORIGIN (t));
490           break;
491
492         case 'c': /* A constant.  */
493           ggc_mark_rtx (TREE_CST_RTL (t));
494           break;
495
496         case 'r': case '<': case '1':
497         case '2': case 'e': case 's': /* Expressions.  */
498           {
499             int i = TREE_CODE_LENGTH (TREE_CODE (t));
500             int first_rtl = first_rtl_op (TREE_CODE (t));
501
502             while (--i >= 0)
503               {
504                 if (i >= first_rtl)
505                   ggc_mark_rtx ((rtx) TREE_OPERAND (t, i));
506                 else
507                   ggc_mark_tree (TREE_OPERAND (t, i));
508               }
509             break;      
510           }
511
512         case 'x':
513           lang_mark_tree (t);
514           break;
515         }
516     }
517 }
518
519 /* Mark all the elements of the varray V, which contains rtxs.  */
520
521 void
522 ggc_mark_rtx_varray (v)
523      varray_type v;
524 {
525   int i;
526
527   if (v)
528     for (i = v->num_elements - 1; i >= 0; --i) 
529       ggc_mark_rtx (VARRAY_RTX (v, i));
530 }
531
532 /* Mark all the elements of the varray V, which contains trees.  */
533
534 void
535 ggc_mark_tree_varray (v)
536      varray_type v;
537 {
538   int i;
539
540   if (v)
541     for (i = v->num_elements - 1; i >= 0; --i) 
542       ggc_mark_tree (VARRAY_TREE (v, i));
543 }
544
545 /* Mark the hash table-entry HE.  Its key field is really a tree.  */
546
547 static bool
548 ggc_mark_tree_hash_table_entry (he, k)
549      struct hash_entry *he;
550      hash_table_key k ATTRIBUTE_UNUSED;
551 {
552   ggc_mark_tree ((tree) he->key);
553   return true;
554 }
555
556 /* Mark all the elements of the hash-table H, which contains trees.  */
557
558 void
559 ggc_mark_tree_hash_table (ht)
560      struct hash_table *ht;
561 {
562   hash_traverse (ht, ggc_mark_tree_hash_table_entry, /*info=*/0);
563 }
564
565 /* Type-correct function to pass to ggc_add_root.  It just forwards
566    *ELT (which is an rtx) to ggc_mark_rtx.  */
567
568 static void
569 ggc_mark_rtx_ptr (elt)
570      void *elt;
571 {
572   ggc_mark_rtx (*(rtx *) elt);
573 }
574
575 /* Type-correct function to pass to ggc_add_root.  It just forwards
576    *ELT (which is a tree) to ggc_mark_tree.  */
577
578 static void
579 ggc_mark_tree_ptr (elt)
580      void *elt;
581 {
582   ggc_mark_tree (*(tree *) elt);
583 }
584
585 /* Type-correct function to pass to ggc_add_root.  It just forwards
586    ELT (which is really a varray_type *) to ggc_mark_rtx_varray.  */
587
588 static void
589 ggc_mark_rtx_varray_ptr (elt)
590      void *elt;
591 {
592   ggc_mark_rtx_varray (*(varray_type *) elt);
593 }
594
595 /* Type-correct function to pass to ggc_add_root.  It just forwards
596    ELT (which is really a varray_type *) to ggc_mark_tree_varray.  */
597
598 static void
599 ggc_mark_tree_varray_ptr (elt)
600      void *elt;
601 {
602   ggc_mark_tree_varray (*(varray_type *) elt);
603 }
604
605 /* Type-correct function to pass to ggc_add_root.  It just forwards
606    ELT (which is really a struct hash_table **) to
607    ggc_mark_tree_hash_table.  */
608
609 static void
610 ggc_mark_tree_hash_table_ptr (elt)
611      void *elt;
612 {
613   ggc_mark_tree_hash_table (*(struct hash_table **) elt);
614 }
615
616 /* Allocate a block of memory, then clear it.  */
617 void *
618 ggc_alloc_cleared (size)
619      size_t size;
620 {
621   void *buf = ggc_alloc (size);
622   memset (buf, 0, size);
623   return buf;
624 }
625
626 /* Print statistics that are independent of the collector in use.  */
627 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
628                   ? (x) \
629                   : ((x) < 1024*1024*10 \
630                      ? (x) / 1024 \
631                      : (x) / (1024*1024))))
632 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
633
634 void
635 ggc_print_common_statistics (stream, stats)
636      FILE *stream;
637      ggc_statistics *stats;
638 {
639   int code;
640
641   /* Set the pointer so that during collection we will actually gather
642      the statistics.  */
643   ggc_stats = stats;
644
645   /* Then do one collection to fill in the statistics.  */
646   ggc_collect ();
647
648   /* Total the statistics.  */
649   for (code = 0; code < MAX_TREE_CODES; ++code)
650     {
651       stats->total_num_trees += stats->num_trees[code];
652       stats->total_size_trees += stats->size_trees[code];
653     }
654   for (code = 0; code < NUM_RTX_CODE; ++code)
655     {
656       stats->total_num_rtxs += stats->num_rtxs[code];
657       stats->total_size_rtxs += stats->size_rtxs[code];
658     }
659
660   /* Print the statistics for trees.  */
661   fprintf (stream, "\n%-17s%10s %16s %10s\n", "Tree", 
662            "Number", "Bytes", "% Total");
663   for (code = 0; code < MAX_TREE_CODES; ++code)
664     if (ggc_stats->num_trees[code]) 
665       {
666         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
667                  tree_code_name[code],
668                  ggc_stats->num_trees[code],
669                  SCALE (ggc_stats->size_trees[code]),
670                  LABEL (ggc_stats->size_trees[code]),
671                  (100 * ((double) ggc_stats->size_trees[code]) 
672                   / ggc_stats->total_size_trees));
673       }
674   fprintf (stream,
675            "%-17s%10u%16ld%c\n", "Total",
676            ggc_stats->total_num_trees,
677            SCALE (ggc_stats->total_size_trees),
678            LABEL (ggc_stats->total_size_trees));
679
680   /* Print the statistics for RTL.  */
681   fprintf (stream, "\n%-17s%10s %16s %10s\n", "RTX", 
682            "Number", "Bytes", "% Total");
683   for (code = 0; code < NUM_RTX_CODE; ++code)
684     if (ggc_stats->num_rtxs[code]) 
685       {
686         fprintf (stream, "%-17s%10u%16ld%c %10.3f\n",
687                  rtx_name[code],
688                  ggc_stats->num_rtxs[code],
689                  SCALE (ggc_stats->size_rtxs[code]),
690                  LABEL (ggc_stats->size_rtxs[code]),
691                  (100 * ((double) ggc_stats->size_rtxs[code]) 
692                   / ggc_stats->total_size_rtxs));
693       }
694   fprintf (stream,
695            "%-17s%10u%16ld%c\n", "Total",
696            ggc_stats->total_num_rtxs,
697            SCALE (ggc_stats->total_size_rtxs),
698            LABEL (ggc_stats->total_size_rtxs));
699
700   /* Don't gather statistics any more.  */
701   ggc_stats = NULL;
702 }