OSDN Git Service

14567827dcd1a20c3cc4b73bc2383cb739c74350
[pf3gnuchains/gcc-fork.git] / gcc / vec.c
1 /* Vector API for GNU compiler.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3    Contributed by Nathan Sidwell <nathan@codesourcery.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This file is compiled twice: once for the generator programs
22    once for the compiler.  */
23 #ifdef GENERATOR_FILE
24 #include "bconfig.h"
25 #else
26 #include "config.h"
27 #endif
28
29 #include "system.h"
30 #include "ggc.h"
31 #include "vec.h"
32 #include "coretypes.h"
33 #include "toplev.h"
34 #include "hashtab.h"
35
36 struct vec_prefix 
37 {
38   unsigned num;
39   unsigned alloc;
40   void *vec[1];
41 };
42
43
44 #ifdef GATHER_STATISTICS
45
46 /* Store information about each particular vector.  */
47 struct vec_descriptor
48 {
49   const char *function;
50   const char *file;
51   int line;
52   size_t allocated;
53   size_t times;
54   size_t peak;
55 };
56
57
58 /* Hashtable mapping vec addresses to descriptors.  */
59 static htab_t vec_desc_hash;
60
61 /* Hashtable helpers.  */
62 static hashval_t
63 hash_descriptor (const void *p)
64 {
65   const struct vec_descriptor *const d =
66     (const struct vec_descriptor *) p;
67   return htab_hash_pointer (d->file) + d->line;
68 }
69 static int
70 eq_descriptor (const void *p1, const void *p2)
71 {
72   const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
73   const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
74   return d->file == l->file && d->function == l->function && d->line == l->line;
75 }
76
77 /* Hashtable converting address of allocated field to loc descriptor.  */
78 static htab_t ptr_hash;
79 struct ptr_hash_entry
80 {
81   void *ptr;
82   struct vec_descriptor *loc;
83   size_t allocated;
84 };
85
86 /* Hash table helpers functions.  */
87 static hashval_t
88 hash_ptr (const void *p)
89 {
90   const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
91
92   return htab_hash_pointer (d->ptr);
93 }
94
95 static int
96 eq_ptr (const void *p1, const void *p2)
97 {
98   const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
99
100   return (p->ptr == p2);
101 }
102
103 /* Return descriptor for given call site, create new one if needed.  */
104 static struct vec_descriptor *
105 vec_descriptor (const char *name, int line, const char *function)
106 {
107   struct vec_descriptor loc;
108   struct vec_descriptor **slot;
109
110   loc.file = name;
111   loc.line = line;
112   loc.function = function;
113   if (!vec_desc_hash)
114     vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
115
116   slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc, 1);
117   if (*slot)
118     return *slot;
119   *slot = XCNEW (struct vec_descriptor);
120   (*slot)->file = name;
121   (*slot)->line = line;
122   (*slot)->function = function;
123   (*slot)->allocated = 0;
124   (*slot)->peak = 0;
125   return *slot;
126 }
127
128 /* Account the overhead.  */
129 static void
130 register_overhead (struct vec_prefix *ptr, size_t size,
131                    const char *name, int line, const char *function)
132 {
133   struct vec_descriptor *loc = vec_descriptor (name, line, function);
134   struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
135   PTR *slot;
136
137   p->ptr = ptr;
138   p->loc = loc;
139   p->allocated = size;
140   if (!ptr_hash)
141     ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
142   slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
143   gcc_assert (!*slot);
144   *slot = p;
145
146   loc->allocated += size;
147   if (loc->peak < loc->allocated)
148     loc->peak += loc->allocated;
149   loc->times++;
150 }
151
152 /* Notice that the pointer has been freed.  */
153 static void
154 free_overhead (struct vec_prefix *ptr)
155 {
156   PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
157                                         NO_INSERT);
158   struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
159   p->loc->allocated -= p->allocated;
160   htab_clear_slot (ptr_hash, slot);
161   free (p);
162 }
163
164 void
165 vec_heap_free (void *ptr)
166 {
167   free_overhead ((struct vec_prefix *)ptr);
168   free (ptr);
169 }
170 #endif
171
172 /* Calculate the new ALLOC value, making sure that RESERVE slots are
173    free.  If EXACT grow exactly, otherwise grow exponentially.  */
174
175 static inline unsigned
176 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
177 {
178   unsigned alloc = 0;
179   unsigned num = 0;
180
181   gcc_assert (reserve >= 0);
182
183   if (pfx)
184     {
185       alloc = pfx->alloc;
186       num = pfx->num;
187     }
188   else if (!reserve)
189     /* If there's no prefix, and we've not requested anything, then we
190        will create a NULL vector.  */
191     return 0;
192   
193   /* We must have run out of room.  */
194   gcc_assert (alloc - num < (unsigned) reserve);
195   
196   if (exact)
197     /* Exact size.  */
198     alloc = num + reserve;
199   else
200     {
201       /* Exponential growth. */
202       if (!alloc)
203         alloc = 4;
204       else if (alloc < 16)
205         /* Double when small.  */
206         alloc = alloc * 2;
207       else
208         /* Grow slower when large.  */
209         alloc = (alloc * 3 / 2);
210       
211       /* If this is still too small, set it to the right size. */
212       if (alloc < num + reserve)
213         alloc = num + reserve;
214     }
215   return alloc;
216 }
217
218 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
219    exactly, else grow exponentially.  As a special case, if VEC is
220    NULL and RESERVE is 0, no vector will be created.  The vector's
221    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
222    sized elements.  */
223
224 static void *
225 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
226                     bool exact MEM_STAT_DECL)
227 {
228   struct vec_prefix *pfx = (struct vec_prefix *) vec;
229   unsigned alloc = alloc = calculate_allocation (pfx, reserve, exact);
230   
231   if (!alloc)
232     {
233       if (pfx)
234         ggc_free (pfx);
235       return NULL;
236     }
237   
238   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
239   ((struct vec_prefix *)vec)->alloc = alloc;
240   if (!pfx)
241     ((struct vec_prefix *)vec)->num = 0;
242   
243   return vec;
244 }
245
246 /* Ensure there are at least RESERVE free slots in VEC, growing
247    exponentially.  If RESERVE < 0 grow exactly, else grow
248    exponentially.  As a special case, if VEC is NULL, and RESERVE is
249    0, no vector will be created. */
250
251 void *
252 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
253 {
254   return vec_gc_o_reserve_1 (vec, reserve,
255                              offsetof (struct vec_prefix, vec),
256                              sizeof (void *), false
257                              PASS_MEM_STAT);
258 }
259
260 /* Ensure there are at least RESERVE free slots in VEC, growing
261    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
262    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
263    created. */
264
265 void *
266 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
267 {
268   return vec_gc_o_reserve_1 (vec, reserve,
269                              offsetof (struct vec_prefix, vec),
270                              sizeof (void *), true
271                              PASS_MEM_STAT);
272 }
273
274 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
275    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
276    sized elements.  */
277
278 void *
279 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
280                   MEM_STAT_DECL)
281 {
282   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
283                              PASS_MEM_STAT);
284 }
285
286 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
287    vector's trailing array is at VEC_OFFSET offset and consists of
288    ELT_SIZE sized elements.  */
289
290 void *
291 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
292                         size_t elt_size MEM_STAT_DECL)
293 {
294   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
295                              PASS_MEM_STAT);
296 }
297
298 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
299
300 static void *
301 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
302                       size_t elt_size, bool exact MEM_STAT_DECL)
303 {
304   struct vec_prefix *pfx = (struct vec_prefix *) vec;
305   unsigned alloc = calculate_allocation (pfx, reserve, exact);
306
307   if (!alloc)
308     {
309       if (pfx)
310         vec_heap_free (pfx);
311       return NULL;
312     }
313
314 #ifdef GATHER_STATISTICS
315   if (vec)
316     free_overhead (pfx);
317 #endif
318   
319   vec = xrealloc (vec, vec_offset + alloc * elt_size);
320   ((struct vec_prefix *)vec)->alloc = alloc;
321   if (!pfx)
322     ((struct vec_prefix *)vec)->num = 0;
323 #ifdef GATHER_STATISTICS
324   if (vec)
325     register_overhead ((struct vec_prefix *)vec,
326                        vec_offset + alloc * elt_size PASS_MEM_STAT);
327 #endif
328   
329   return vec;
330 }
331
332 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
333
334 void *
335 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
336 {
337   return vec_heap_o_reserve_1 (vec, reserve,
338                                offsetof (struct vec_prefix, vec),
339                                sizeof (void *), false
340                                PASS_MEM_STAT);
341 }
342
343 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
344
345 void *
346 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
347 {
348   return vec_heap_o_reserve_1 (vec, reserve,
349                                offsetof (struct vec_prefix, vec),
350                                sizeof (void *), true
351                                PASS_MEM_STAT);
352 }
353
354 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
355
356 void *
357 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
358                     MEM_STAT_DECL)
359 {
360   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
361                                PASS_MEM_STAT);
362 }
363
364 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
365
366 void *
367 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
368                           size_t elt_size MEM_STAT_DECL)
369 {
370   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
371                                PASS_MEM_STAT);
372 }
373
374 #if ENABLE_CHECKING
375 /* Issue a vector domain error, and then fall over.  */
376
377 void
378 vec_assert_fail (const char *op, const char *struct_name,
379                  const char *file, unsigned int line, const char *function)
380 {
381   internal_error ("vector %s %s domain error, in %s at %s:%u",
382                   struct_name, op, function, trim_filename (file), line);
383 }
384 #endif
385
386 #ifdef GATHER_STATISTICS
387 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
388 static int
389 cmp_statistic (const void *loc1, const void *loc2)
390 {
391   const struct vec_descriptor *const l1 =
392     *(const struct vec_descriptor *const *) loc1;
393   const struct vec_descriptor *const l2 =
394     *(const struct vec_descriptor *const *) loc2;
395   long diff;
396   diff = l1->allocated - l2->allocated;
397   if (!diff)
398     diff = l1->peak - l2->peak;
399   if (!diff)
400     diff = l1->times - l2->times;
401   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
402 }
403 /* Collect array of the descriptors from hashtable.  */
404 static struct vec_descriptor **loc_array;
405 static int
406 add_statistics (void **slot, void *b)
407 {
408   int *n = (int *)b;
409   loc_array[*n] = (struct vec_descriptor *) *slot;
410   (*n)++;
411   return 1;
412 }
413
414 /* Dump per-site memory statistics.  */
415 #endif
416 void
417 dump_vec_loc_statistics (void)
418 {
419 #ifdef GATHER_STATISTICS
420   int nentries = 0;
421   char s[4096];
422   size_t allocated = 0;
423   size_t times = 0;
424   int i;
425
426   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
427   fprintf (stderr, "Heap vectors:\n");
428   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
429            "source location", "Leak", "Peak", "Times");
430   fprintf (stderr, "-------------------------------------------------------\n");
431   htab_traverse (vec_desc_hash, add_statistics, &nentries);
432   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
433   for (i = 0; i < nentries; i++)
434     {
435       struct vec_descriptor *d = loc_array[i];
436       allocated += d->allocated;
437       times += d->times;
438     }
439   for (i = 0; i < nentries; i++)
440     {
441       struct vec_descriptor *d = loc_array[i];
442       const char *s1 = d->file;
443       const char *s2;
444       while ((s2 = strstr (s1, "gcc/")))
445         s1 = s2 + 4;
446       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
447       s[48] = 0;
448       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
449                (long)d->allocated,
450                (d->allocated) * 100.0 / allocated,
451                (long)d->peak,
452                (long)d->times,
453                (d->times) * 100.0 / times);
454     }
455   fprintf (stderr, "%-48s %10ld                        %10ld\n",
456            "Total", (long)allocated, (long)times);
457   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
458            "source location", "Leak", "Peak", "Times");
459   fprintf (stderr, "-------------------------------------------------------\n");
460 #endif
461 }