1/* Virtual array support.
2   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007, 2008
3   Free Software Foundation, Inc.
4   Contributed by Cygnus Solutions.
5
6   This file is part of GCC.
7
8   GCC is free software; you can redistribute it and/or modify it
9   under the terms of the GNU General Public License as published by
10   the Free Software Foundation; either version 3, or (at your option)
11   any later version.
12
13   GCC is distributed in the hope that it will be useful, but WITHOUT
14   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
16   License for more details.
17
18   You should have received a copy of the GNU General Public License
19   along with GCC; see the file COPYING3.  If not see
20   <http://www.gnu.org/licenses/>.  */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "toplev.h"
27#include "varray.h"
28#include "ggc.h"
29#include "hashtab.h"
30
31#define VARRAY_HDR_SIZE (sizeof (struct varray_head_tag) - sizeof (varray_data))
32
33#ifdef GATHER_STATISTICS
34
35/* Store information about each particular varray.  */
36struct varray_descriptor
37{
38  const char *name;
39  int allocated;
40  int created;
41  int resized;
42  int copied;
43};
44
45/* Hashtable mapping varray names to descriptors.  */
46static htab_t varray_hash;
47
48/* Hashtable helpers.  */
49static hashval_t
50hash_descriptor (const void *p)
51{
52  const struct varray_descriptor *d = (const struct varray_descriptor *) p;
53  return htab_hash_pointer (d->name);
54}
55static int
56eq_descriptor (const void *p1, const void *p2)
57{
58  const struct varray_descriptor *d = (const struct varray_descriptor *) p1;
59  return d->name == p2;
60}
61
62/* For given name, return descriptor, create new if needed.  */
63static struct varray_descriptor *
64varray_descriptor (const char *name)
65{
66  struct varray_descriptor **slot;
67
68  if (!varray_hash)
69    varray_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
70
71  slot = (struct varray_descriptor **)
72    htab_find_slot_with_hash (varray_hash, name,
73		    	      htab_hash_pointer (name),
74			      INSERT);
75  if (*slot)
76    return *slot;
77  *slot = XCNEW (struct varray_descriptor);
78  (*slot)->name = name;
79  return *slot;
80}
81#endif
82
83/* Do not add any more non-GC items here.  Please either remove or GC
84   those items that are not GCed.  */
85
86static const struct {
87  unsigned char size;
88  bool uses_ggc;
89} element[NUM_VARRAY_DATA] = {
90  { sizeof (char), 1 },
91  { sizeof (unsigned char), 1 },
92  { sizeof (short), 1 },
93  { sizeof (unsigned short), 1 },
94  { sizeof (int), 1 },
95  { sizeof (unsigned int), 1 },
96  { sizeof (long), 1 },
97  { sizeof (unsigned long), 1 },
98  { sizeof (HOST_WIDE_INT), 1 },
99  { sizeof (unsigned HOST_WIDE_INT), 1 },
100  { sizeof (void *), 1 },
101  { sizeof (void *), 0 },
102  { sizeof (char *), 1 },
103  { sizeof (struct rtx_def *), 1 },
104  { sizeof (struct rtvec_def *), 1 },
105  { sizeof (union tree_node *), 1 },
106  { sizeof (struct bitmap_head_def *), 1 },
107  { sizeof (struct reg_info_def *), 0 },
108  { sizeof (struct basic_block_def *), 1 },
109  { sizeof (struct elt_list *), 1 },
110  { sizeof (struct edge_def *), 1 },
111  { sizeof (tree *), 1 },
112};
113
114/* Allocate a virtual array with NUM_ELEMENT elements, each of which is
115   ELEMENT_SIZE bytes long, named NAME.  Array elements are zeroed.  */
116varray_type
117varray_init (size_t num_elements, enum varray_data_enum element_kind,
118	     const char *name)
119{
120  size_t data_size = num_elements * element[element_kind].size;
121  varray_type ptr;
122#ifdef GATHER_STATISTICS
123  struct varray_descriptor *desc = varray_descriptor (name);
124
125  desc->created++;
126  desc->allocated += data_size + VARRAY_HDR_SIZE;
127#endif
128  if (element[element_kind].uses_ggc)
129    ptr = GGC_CNEWVAR (struct varray_head_tag, VARRAY_HDR_SIZE + data_size);
130  else
131    ptr = XCNEWVAR (struct varray_head_tag, VARRAY_HDR_SIZE + data_size);
132
133  ptr->num_elements = num_elements;
134  ptr->elements_used = 0;
135  ptr->type = element_kind;
136  ptr->name = name;
137  return ptr;
138}
139
140/* Grow/shrink the virtual array VA to N elements.  Zero any new elements
141   allocated.  */
142varray_type
143varray_grow (varray_type va, size_t n)
144{
145  size_t old_elements = va->num_elements;
146  if (n != old_elements)
147    {
148      size_t elem_size = element[va->type].size;
149      size_t old_data_size = old_elements * elem_size;
150      size_t data_size = n * elem_size;
151#ifdef GATHER_STATISTICS
152      struct varray_descriptor *desc = varray_descriptor (va->name);
153      varray_type oldva = va;
154
155      if (data_size > old_data_size)
156        desc->allocated += data_size - old_data_size;
157      desc->resized ++;
158#endif
159
160
161      if (element[va->type].uses_ggc)
162	va = GGC_RESIZEVAR (struct varray_head_tag, va,
163			    VARRAY_HDR_SIZE + data_size);
164      else
165	va = XRESIZEVAR (struct varray_head_tag, va,
166			 VARRAY_HDR_SIZE + data_size);
167      va->num_elements = n;
168      if (n > old_elements)
169	memset (&va->data.vdt_c[old_data_size], 0, data_size - old_data_size);
170#ifdef GATHER_STATISTICS
171      if (oldva != va)
172        desc->copied++;
173#endif
174    }
175
176  return va;
177}
178
179/* Reset a varray to its original state.  */
180void
181varray_clear (varray_type va)
182{
183  size_t data_size = element[va->type].size * va->num_elements;
184
185  memset (va->data.vdt_c, 0, data_size);
186  va->elements_used = 0;
187}
188
189/* Check the bounds of a varray access.  */
190
191#if defined ENABLE_CHECKING && (GCC_VERSION >= 2007)
192
193void
194varray_check_failed (varray_type va, size_t n, const char *file, int line,
195		     const char *function)
196{
197  internal_error ("virtual array %s[%lu]: element %lu out of bounds "
198		  "in %s, at %s:%d",
199		  va->name, (unsigned long) va->num_elements, (unsigned long) n,
200		  function, trim_filename (file), line);
201}
202
203void
204varray_underflow (varray_type va, const char *file, int line,
205		  const char *function)
206{
207  internal_error ("underflowed virtual array %s in %s, at %s:%d",
208		  va->name, function, trim_filename (file), line);
209}
210
211#endif
212
213
214/* Output per-varray statistics.  */
215#ifdef GATHER_STATISTICS
216
217/* Used to accumulate statistics about varray sizes.  */
218struct output_info
219{
220  int count;
221  int size;
222};
223
224/* Called via htab_traverse.  Output varray descriptor pointed out by SLOT
225   and update statistics.  */
226static int
227print_statistics (void **slot, void *b)
228{
229  struct varray_descriptor *d = (struct varray_descriptor *) *slot;
230  struct output_info *i = (struct output_info *) b;
231
232  if (d->allocated)
233    {
234      fprintf (stderr, "%-21s %6d %10d %7d %7d\n", d->name,
235	       d->created, d->allocated, d->resized, d->copied);
236      i->size += d->allocated;
237      i->count += d->created;
238    }
239  return 1;
240}
241#endif
242
243/* Output per-varray memory usage statistics.  */
244void
245dump_varray_statistics (void)
246{
247#ifdef GATHER_STATISTICS
248  struct output_info info;
249
250  if (varray_hash)
251    {
252      fprintf (stderr, "\nVARRAY Kind            Count      Bytes  Resized copied\n");
253      fprintf (stderr, "-------------------------------------------------------\n");
254      info.count = 0;
255      info.size = 0;
256      htab_traverse (varray_hash, print_statistics, &info);
257      fprintf (stderr, "-------------------------------------------------------\n");
258      fprintf (stderr, "%-20s %7d %10d\n",
259	       "Total", info.count, info.size);
260      fprintf (stderr, "-------------------------------------------------------\n");
261   }
262#endif
263}
264