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