OSDN Git Service

PR c++/14179
[pf3gnuchains/gcc-fork.git] / gcc / vec.c
1 /* Vector API for GNU compiler.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
3    Free Software Foundation, Inc.
4    Contributed by Nathan Sidwell <nathan@codesourcery.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 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 /* This file is compiled twice: once for the generator programs
23    once for the compiler.  */
24 #ifdef GENERATOR_FILE
25 #include "bconfig.h"
26 #else
27 #include "config.h"
28 #endif
29
30 #include "system.h"
31 #include "coretypes.h"
32 #include "ggc.h"
33 #include "vec.h"
34 #include "diagnostic-core.h"
35 #include "hashtab.h"
36
37 #ifdef GATHER_STATISTICS
38
39 /* Store information about each particular vector.  */
40 struct vec_descriptor
41 {
42   const char *function;
43   const char *file;
44   int line;
45   size_t allocated;
46   size_t times;
47   size_t peak;
48 };
49
50
51 /* Hashtable mapping vec addresses to descriptors.  */
52 static htab_t vec_desc_hash;
53
54 /* Hashtable helpers.  */
55 static hashval_t
56 hash_descriptor (const void *p)
57 {
58   const struct vec_descriptor *const d =
59     (const struct vec_descriptor *) p;
60   return htab_hash_pointer (d->file) + d->line;
61 }
62 static int
63 eq_descriptor (const void *p1, const void *p2)
64 {
65   const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
66   const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
67   return d->file == l->file && d->function == l->function && d->line == l->line;
68 }
69
70 /* Hashtable converting address of allocated field to loc descriptor.  */
71 static htab_t ptr_hash;
72 struct ptr_hash_entry
73 {
74   void *ptr;
75   struct vec_descriptor *loc;
76   size_t allocated;
77 };
78
79 /* Hash table helpers functions.  */
80 static hashval_t
81 hash_ptr (const void *p)
82 {
83   const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
84
85   return htab_hash_pointer (d->ptr);
86 }
87
88 static int
89 eq_ptr (const void *p1, const void *p2)
90 {
91   const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
92
93   return (p->ptr == p2);
94 }
95
96 /* Return descriptor for given call site, create new one if needed.  */
97 static struct vec_descriptor *
98 vec_descriptor (const char *name, int line, const char *function)
99 {
100   struct vec_descriptor loc;
101   struct vec_descriptor **slot;
102
103   loc.file = name;
104   loc.line = line;
105   loc.function = function;
106   if (!vec_desc_hash)
107     vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
108
109   slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
110                                                     INSERT);
111   if (*slot)
112     return *slot;
113   *slot = XCNEW (struct vec_descriptor);
114   (*slot)->file = name;
115   (*slot)->line = line;
116   (*slot)->function = function;
117   (*slot)->allocated = 0;
118   (*slot)->peak = 0;
119   return *slot;
120 }
121
122 /* Account the overhead.  */
123 static void
124 register_overhead (struct vec_prefix *ptr, size_t size,
125                    const char *name, int line, const char *function)
126 {
127   struct vec_descriptor *loc = vec_descriptor (name, line, function);
128   struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
129   PTR *slot;
130
131   p->ptr = ptr;
132   p->loc = loc;
133   p->allocated = size;
134   if (!ptr_hash)
135     ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
136   slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
137   gcc_assert (!*slot);
138   *slot = p;
139
140   loc->allocated += size;
141   if (loc->peak < loc->allocated)
142     loc->peak += loc->allocated;
143   loc->times++;
144 }
145
146 /* Notice that the pointer has been freed.  */
147 static void
148 free_overhead (struct vec_prefix *ptr)
149 {
150   PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
151                                         NO_INSERT);
152   struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
153   p->loc->allocated -= p->allocated;
154   htab_clear_slot (ptr_hash, slot);
155   free (p);
156 }
157
158 void
159 vec_heap_free (void *ptr)
160 {
161   free_overhead ((struct vec_prefix *)ptr);
162   free (ptr);
163 }
164 #endif
165
166 /* Calculate the new ALLOC value, making sure that RESERVE slots are
167    free.  If EXACT grow exactly, otherwise grow exponentially.  */
168
169 static inline unsigned
170 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
171 {
172   unsigned alloc = 0;
173   unsigned num = 0;
174
175   gcc_assert (reserve >= 0);
176
177   if (pfx)
178     {
179       alloc = pfx->alloc;
180       num = pfx->num;
181     }
182   else if (!reserve)
183     /* If there's no prefix, and we've not requested anything, then we
184        will create a NULL vector.  */
185     return 0;
186
187   /* We must have run out of room.  */
188   gcc_assert (alloc - num < (unsigned) reserve);
189
190   if (exact)
191     /* Exact size.  */
192     alloc = num + reserve;
193   else
194     {
195       /* Exponential growth. */
196       if (!alloc)
197         alloc = 4;
198       else if (alloc < 16)
199         /* Double when small.  */
200         alloc = alloc * 2;
201       else
202         /* Grow slower when large.  */
203         alloc = (alloc * 3 / 2);
204
205       /* If this is still too small, set it to the right size. */
206       if (alloc < num + reserve)
207         alloc = num + reserve;
208     }
209   return alloc;
210 }
211
212 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
213    exactly, else grow exponentially.  As a special case, if VEC is
214    NULL and RESERVE is 0, no vector will be created.  The vector's
215    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
216    sized elements.  */
217
218 static void *
219 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
220                     bool exact MEM_STAT_DECL)
221 {
222   struct vec_prefix *pfx = (struct vec_prefix *) vec;
223   unsigned alloc = calculate_allocation (pfx, reserve, exact);
224   size_t size;
225
226   if (!alloc)
227     {
228       if (pfx)
229         ggc_free (pfx);
230       return NULL;
231     }
232
233   /* Calculate the amount of space we want.  */
234   size = vec_offset + alloc * elt_size;
235   /* Ask the allocator how much space it will really give us.  */
236   size = ggc_round_alloc_size (size);
237   /* Adjust the number of slots accordingly.  */
238   alloc = (size - vec_offset) / elt_size;
239   /* And finally, recalculate the amount of space we ask for.  */
240   size = vec_offset + alloc * elt_size;
241
242   vec = ggc_realloc_stat (vec, size PASS_MEM_STAT);
243
244   ((struct vec_prefix *)vec)->alloc = alloc;
245   if (!pfx)
246     ((struct vec_prefix *)vec)->num = 0;
247
248   return vec;
249 }
250
251 /* Ensure there are at least RESERVE free slots in VEC, growing
252    exponentially.  If RESERVE < 0 grow exactly, else grow
253    exponentially.  As a special case, if VEC is NULL, and RESERVE is
254    0, no vector will be created. */
255
256 void *
257 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
258 {
259   return vec_gc_o_reserve_1 (vec, reserve,
260                              sizeof (struct vec_prefix),
261                              sizeof (void *), false
262                              PASS_MEM_STAT);
263 }
264
265 /* Ensure there are at least RESERVE free slots in VEC, growing
266    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
267    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
268    created. */
269
270 void *
271 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
272 {
273   return vec_gc_o_reserve_1 (vec, reserve,
274                              sizeof (struct vec_prefix),
275                              sizeof (void *), true
276                              PASS_MEM_STAT);
277 }
278
279 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
280    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
281    sized elements.  */
282
283 void *
284 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
285                   MEM_STAT_DECL)
286 {
287   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
288                              PASS_MEM_STAT);
289 }
290
291 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
292    vector's trailing array is at VEC_OFFSET offset and consists of
293    ELT_SIZE sized elements.  */
294
295 void *
296 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
297                         size_t elt_size MEM_STAT_DECL)
298 {
299   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
300                              PASS_MEM_STAT);
301 }
302
303 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
304
305 static void *
306 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
307                       size_t elt_size, bool exact MEM_STAT_DECL)
308 {
309   struct vec_prefix *pfx = (struct vec_prefix *) vec;
310   unsigned alloc = calculate_allocation (pfx, reserve, exact);
311
312   if (!alloc)
313     {
314       if (pfx)
315         vec_heap_free (pfx);
316       return NULL;
317     }
318
319 #ifdef GATHER_STATISTICS
320   if (vec)
321     free_overhead (pfx);
322 #endif
323
324   vec = xrealloc (vec, vec_offset + alloc * elt_size);
325   ((struct vec_prefix *)vec)->alloc = alloc;
326   if (!pfx)
327     ((struct vec_prefix *)vec)->num = 0;
328 #ifdef GATHER_STATISTICS
329   if (vec)
330     register_overhead ((struct vec_prefix *)vec,
331                        vec_offset + alloc * elt_size PASS_MEM_STAT);
332 #endif
333
334   return vec;
335 }
336
337 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
338
339 void *
340 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
341 {
342   return vec_heap_o_reserve_1 (vec, reserve,
343                                sizeof (struct vec_prefix),
344                                sizeof (void *), false
345                                PASS_MEM_STAT);
346 }
347
348 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
349
350 void *
351 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
352 {
353   return vec_heap_o_reserve_1 (vec, reserve,
354                                sizeof (struct vec_prefix),
355                                sizeof (void *), true
356                                PASS_MEM_STAT);
357 }
358
359 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
360
361 void *
362 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
363                     MEM_STAT_DECL)
364 {
365   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
366                                PASS_MEM_STAT);
367 }
368
369 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
370
371 void *
372 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
373                           size_t elt_size MEM_STAT_DECL)
374 {
375   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
376                                PASS_MEM_STAT);
377 }
378
379 /* Stack vectors are a little different.  VEC_alloc turns into a call
380    to vec_stack_p_reserve_exact1 and passes in space allocated via a
381    call to alloca.  We record that pointer so that we know that we
382    shouldn't free it.  If the vector is resized, we resize it on the
383    heap.  We record the pointers in a vector and search it in LIFO
384    order--i.e., we look for the newest stack vectors first.  We don't
385    expect too many stack vectors at any one level, and searching from
386    the end should normally be efficient even if they are used in a
387    recursive function.  */
388
389 typedef void *void_p;
390 DEF_VEC_P(void_p);
391 DEF_VEC_ALLOC_P(void_p,heap);
392
393 static VEC(void_p,heap) *stack_vecs;
394
395 /* Allocate a vector which uses alloca for the initial allocation.
396    SPACE is space allocated using alloca, ALLOC is the number of
397    entries allocated.  */
398
399 void *
400 vec_stack_p_reserve_exact_1 (int alloc, void *space)
401 {
402   struct vec_prefix *pfx = (struct vec_prefix *) space;
403
404   VEC_safe_push (void_p, heap, stack_vecs, space);
405
406   pfx->num = 0;
407   pfx->alloc = alloc;
408
409   return space;
410 }
411
412 /* Grow a vector allocated using alloca.  When this happens, we switch
413    back to heap allocation.  We remove the vector from stack_vecs, if
414    it is there, since we no longer need to avoid freeing it.  */
415
416 static void *
417 vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
418                        size_t elt_size, bool exact MEM_STAT_DECL)
419 {
420   bool found;
421   unsigned int ix;
422   void *newvec;
423
424   found = false;
425   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
426     {
427       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
428         {
429           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
430           found = true;
431           break;
432         }
433     }
434
435   if (!found)
436     {
437       /* VEC is already on the heap.  */
438       return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
439                                    exact PASS_MEM_STAT);
440     }
441
442   /* Move VEC to the heap.  */
443   reserve += ((struct vec_prefix *) vec)->num;
444   newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
445                                  exact PASS_MEM_STAT);
446   if (newvec && vec)
447     {
448       ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
449       memcpy (((struct vec_prefix *) newvec)+1,
450               ((struct vec_prefix *) vec)+1,
451               ((struct vec_prefix *) vec)->num * elt_size);
452     }
453   return newvec;
454 }
455
456 /* Grow a vector allocated on the stack.  */
457
458 void *
459 vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
460 {
461   return vec_stack_o_reserve_1 (vec, reserve,
462                                 sizeof (struct vec_prefix),
463                                 sizeof (void *), false
464                                 PASS_MEM_STAT);
465 }
466
467 /* Exact version of vec_stack_p_reserve.  */
468
469 void *
470 vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
471 {
472   return vec_stack_o_reserve_1 (vec, reserve,
473                                 sizeof (struct vec_prefix),
474                                 sizeof (void *), true
475                                 PASS_MEM_STAT);
476 }
477
478 /* Like vec_stack_p_reserve, but for objects.  */
479
480 void *
481 vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
482                      size_t elt_size MEM_STAT_DECL)
483 {
484   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
485                                 PASS_MEM_STAT);
486 }
487
488 /* Like vec_stack_p_reserve_exact, but for objects.  */
489
490 void *
491 vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
492                             size_t elt_size MEM_STAT_DECL)
493 {
494   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
495                                 PASS_MEM_STAT);
496 }
497
498 /* Free a vector allocated on the stack.  Don't actually free it if we
499    find it in the hash table.  */
500
501 void
502 vec_stack_free (void *vec)
503 {
504   unsigned int ix;
505
506   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
507     {
508       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
509         {
510           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
511           return;
512         }
513     }
514
515   /* VEC was not on the list of vecs allocated on the stack, so it
516      must be allocated on the heap.  */
517   vec_heap_free (vec);
518 }
519
520 #if ENABLE_CHECKING
521 /* Issue a vector domain error, and then fall over.  */
522
523 void
524 vec_assert_fail (const char *op, const char *struct_name,
525                  const char *file, unsigned int line, const char *function)
526 {
527   internal_error ("vector %s %s domain error, in %s at %s:%u",
528                   struct_name, op, function, trim_filename (file), line);
529 }
530 #endif
531
532 #ifdef GATHER_STATISTICS
533 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
534 static int
535 cmp_statistic (const void *loc1, const void *loc2)
536 {
537   const struct vec_descriptor *const l1 =
538     *(const struct vec_descriptor *const *) loc1;
539   const struct vec_descriptor *const l2 =
540     *(const struct vec_descriptor *const *) loc2;
541   long diff;
542   diff = l1->allocated - l2->allocated;
543   if (!diff)
544     diff = l1->peak - l2->peak;
545   if (!diff)
546     diff = l1->times - l2->times;
547   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
548 }
549 /* Collect array of the descriptors from hashtable.  */
550 static struct vec_descriptor **loc_array;
551 static int
552 add_statistics (void **slot, void *b)
553 {
554   int *n = (int *)b;
555   loc_array[*n] = (struct vec_descriptor *) *slot;
556   (*n)++;
557   return 1;
558 }
559
560 /* Dump per-site memory statistics.  */
561 #endif
562 void
563 dump_vec_loc_statistics (void)
564 {
565 #ifdef GATHER_STATISTICS
566   int nentries = 0;
567   char s[4096];
568   size_t allocated = 0;
569   size_t times = 0;
570   int i;
571
572   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
573   fprintf (stderr, "Heap vectors:\n");
574   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
575            "source location", "Leak", "Peak", "Times");
576   fprintf (stderr, "-------------------------------------------------------\n");
577   htab_traverse (vec_desc_hash, add_statistics, &nentries);
578   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
579   for (i = 0; i < nentries; i++)
580     {
581       struct vec_descriptor *d = loc_array[i];
582       allocated += d->allocated;
583       times += d->times;
584     }
585   for (i = 0; i < nentries; i++)
586     {
587       struct vec_descriptor *d = loc_array[i];
588       const char *s1 = d->file;
589       const char *s2;
590       while ((s2 = strstr (s1, "gcc/")))
591         s1 = s2 + 4;
592       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
593       s[48] = 0;
594       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
595                (long)d->allocated,
596                (d->allocated) * 100.0 / allocated,
597                (long)d->peak,
598                (long)d->times,
599                (d->times) * 100.0 / times);
600     }
601   fprintf (stderr, "%-48s %10ld                        %10ld\n",
602            "Total", (long)allocated, (long)times);
603   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
604            "source location", "Leak", "Peak", "Times");
605   fprintf (stderr, "-------------------------------------------------------\n");
606 #endif
607 }