OSDN Git Service

c1d003492e3c2d802ba6713f7fdb3c463e8e8a87
[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
225   if (!alloc)
226     {
227       if (pfx)
228         ggc_free (pfx);
229       return NULL;
230     }
231
232   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
233   ((struct vec_prefix *)vec)->alloc = alloc;
234   if (!pfx)
235     ((struct vec_prefix *)vec)->num = 0;
236
237   return vec;
238 }
239
240 /* Ensure there are at least RESERVE free slots in VEC, growing
241    exponentially.  If RESERVE < 0 grow exactly, else grow
242    exponentially.  As a special case, if VEC is NULL, and RESERVE is
243    0, no vector will be created. */
244
245 void *
246 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
247 {
248   return vec_gc_o_reserve_1 (vec, reserve,
249                              sizeof (struct vec_prefix),
250                              sizeof (void *), false
251                              PASS_MEM_STAT);
252 }
253
254 /* Ensure there are at least RESERVE free slots in VEC, growing
255    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
256    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
257    created. */
258
259 void *
260 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
261 {
262   return vec_gc_o_reserve_1 (vec, reserve,
263                              sizeof (struct vec_prefix),
264                              sizeof (void *), true
265                              PASS_MEM_STAT);
266 }
267
268 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
269    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
270    sized elements.  */
271
272 void *
273 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
274                   MEM_STAT_DECL)
275 {
276   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
277                              PASS_MEM_STAT);
278 }
279
280 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
281    vector's trailing array is at VEC_OFFSET offset and consists of
282    ELT_SIZE sized elements.  */
283
284 void *
285 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
286                         size_t elt_size MEM_STAT_DECL)
287 {
288   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
289                              PASS_MEM_STAT);
290 }
291
292 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
293
294 static void *
295 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
296                       size_t elt_size, bool exact MEM_STAT_DECL)
297 {
298   struct vec_prefix *pfx = (struct vec_prefix *) vec;
299   unsigned alloc = calculate_allocation (pfx, reserve, exact);
300
301   if (!alloc)
302     {
303       if (pfx)
304         vec_heap_free (pfx);
305       return NULL;
306     }
307
308 #ifdef GATHER_STATISTICS
309   if (vec)
310     free_overhead (pfx);
311 #endif
312
313   vec = xrealloc (vec, vec_offset + alloc * elt_size);
314   ((struct vec_prefix *)vec)->alloc = alloc;
315   if (!pfx)
316     ((struct vec_prefix *)vec)->num = 0;
317 #ifdef GATHER_STATISTICS
318   if (vec)
319     register_overhead ((struct vec_prefix *)vec,
320                        vec_offset + alloc * elt_size PASS_MEM_STAT);
321 #endif
322
323   return vec;
324 }
325
326 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
327
328 void *
329 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
330 {
331   return vec_heap_o_reserve_1 (vec, reserve,
332                                sizeof (struct vec_prefix),
333                                sizeof (void *), false
334                                PASS_MEM_STAT);
335 }
336
337 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
338
339 void *
340 vec_heap_p_reserve_exact (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 *), true
345                                PASS_MEM_STAT);
346 }
347
348 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
349
350 void *
351 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
352                     MEM_STAT_DECL)
353 {
354   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
355                                PASS_MEM_STAT);
356 }
357
358 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
359
360 void *
361 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
362                           size_t elt_size MEM_STAT_DECL)
363 {
364   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
365                                PASS_MEM_STAT);
366 }
367
368 /* Stack vectors are a little different.  VEC_alloc turns into a call
369    to vec_stack_p_reserve_exact1 and passes in space allocated via a
370    call to alloca.  We record that pointer so that we know that we
371    shouldn't free it.  If the vector is resized, we resize it on the
372    heap.  We record the pointers in a vector and search it in LIFO
373    order--i.e., we look for the newest stack vectors first.  We don't
374    expect too many stack vectors at any one level, and searching from
375    the end should normally be efficient even if they are used in a
376    recursive function.  */
377
378 typedef void *void_p;
379 DEF_VEC_P(void_p);
380 DEF_VEC_ALLOC_P(void_p,heap);
381
382 static VEC(void_p,heap) *stack_vecs;
383
384 /* Allocate a vector which uses alloca for the initial allocation.
385    SPACE is space allocated using alloca, ALLOC is the number of
386    entries allocated.  */
387
388 void *
389 vec_stack_p_reserve_exact_1 (int alloc, void *space)
390 {
391   struct vec_prefix *pfx = (struct vec_prefix *) space;
392
393   VEC_safe_push (void_p, heap, stack_vecs, space);
394
395   pfx->num = 0;
396   pfx->alloc = alloc;
397
398   return space;
399 }
400
401 /* Grow a vector allocated using alloca.  When this happens, we switch
402    back to heap allocation.  We remove the vector from stack_vecs, if
403    it is there, since we no longer need to avoid freeing it.  */
404
405 static void *
406 vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
407                        size_t elt_size, bool exact MEM_STAT_DECL)
408 {
409   bool found;
410   unsigned int ix;
411   void *newvec;
412
413   found = false;
414   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
415     {
416       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
417         {
418           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
419           found = true;
420           break;
421         }
422     }
423
424   if (!found)
425     {
426       /* VEC is already on the heap.  */
427       return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
428                                    exact PASS_MEM_STAT);
429     }
430
431   /* Move VEC to the heap.  */
432   reserve += ((struct vec_prefix *) vec)->num;
433   newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
434                                  exact PASS_MEM_STAT);
435   if (newvec && vec)
436     {
437       ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
438       memcpy (((struct vec_prefix *) newvec)+1,
439               ((struct vec_prefix *) vec)+1,
440               ((struct vec_prefix *) vec)->num * elt_size);
441     }
442   return newvec;
443 }
444
445 /* Grow a vector allocated on the stack.  */
446
447 void *
448 vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
449 {
450   return vec_stack_o_reserve_1 (vec, reserve,
451                                 sizeof (struct vec_prefix),
452                                 sizeof (void *), false
453                                 PASS_MEM_STAT);
454 }
455
456 /* Exact version of vec_stack_p_reserve.  */
457
458 void *
459 vec_stack_p_reserve_exact (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 *), true
464                                 PASS_MEM_STAT);
465 }
466
467 /* Like vec_stack_p_reserve, but for objects.  */
468
469 void *
470 vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
471                      size_t elt_size MEM_STAT_DECL)
472 {
473   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
474                                 PASS_MEM_STAT);
475 }
476
477 /* Like vec_stack_p_reserve_exact, but for objects.  */
478
479 void *
480 vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
481                             size_t elt_size MEM_STAT_DECL)
482 {
483   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
484                                 PASS_MEM_STAT);
485 }
486
487 /* Free a vector allocated on the stack.  Don't actually free it if we
488    find it in the hash table.  */
489
490 void
491 vec_stack_free (void *vec)
492 {
493   unsigned int ix;
494
495   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
496     {
497       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
498         {
499           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
500           return;
501         }
502     }
503
504   /* VEC was not on the list of vecs allocated on the stack, so it
505      must be allocated on the heap.  */
506   vec_heap_free (vec);
507 }
508
509 #if ENABLE_CHECKING
510 /* Issue a vector domain error, and then fall over.  */
511
512 void
513 vec_assert_fail (const char *op, const char *struct_name,
514                  const char *file, unsigned int line, const char *function)
515 {
516   internal_error ("vector %s %s domain error, in %s at %s:%u",
517                   struct_name, op, function, trim_filename (file), line);
518 }
519 #endif
520
521 #ifdef GATHER_STATISTICS
522 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
523 static int
524 cmp_statistic (const void *loc1, const void *loc2)
525 {
526   const struct vec_descriptor *const l1 =
527     *(const struct vec_descriptor *const *) loc1;
528   const struct vec_descriptor *const l2 =
529     *(const struct vec_descriptor *const *) loc2;
530   long diff;
531   diff = l1->allocated - l2->allocated;
532   if (!diff)
533     diff = l1->peak - l2->peak;
534   if (!diff)
535     diff = l1->times - l2->times;
536   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
537 }
538 /* Collect array of the descriptors from hashtable.  */
539 static struct vec_descriptor **loc_array;
540 static int
541 add_statistics (void **slot, void *b)
542 {
543   int *n = (int *)b;
544   loc_array[*n] = (struct vec_descriptor *) *slot;
545   (*n)++;
546   return 1;
547 }
548
549 /* Dump per-site memory statistics.  */
550 #endif
551 void
552 dump_vec_loc_statistics (void)
553 {
554 #ifdef GATHER_STATISTICS
555   int nentries = 0;
556   char s[4096];
557   size_t allocated = 0;
558   size_t times = 0;
559   int i;
560
561   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
562   fprintf (stderr, "Heap vectors:\n");
563   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
564            "source location", "Leak", "Peak", "Times");
565   fprintf (stderr, "-------------------------------------------------------\n");
566   htab_traverse (vec_desc_hash, add_statistics, &nentries);
567   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
568   for (i = 0; i < nentries; i++)
569     {
570       struct vec_descriptor *d = loc_array[i];
571       allocated += d->allocated;
572       times += d->times;
573     }
574   for (i = 0; i < nentries; i++)
575     {
576       struct vec_descriptor *d = loc_array[i];
577       const char *s1 = d->file;
578       const char *s2;
579       while ((s2 = strstr (s1, "gcc/")))
580         s1 = s2 + 4;
581       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
582       s[48] = 0;
583       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
584                (long)d->allocated,
585                (d->allocated) * 100.0 / allocated,
586                (long)d->peak,
587                (long)d->times,
588                (d->times) * 100.0 / times);
589     }
590   fprintf (stderr, "%-48s %10ld                        %10ld\n",
591            "Total", (long)allocated, (long)times);
592   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
593            "source location", "Leak", "Peak", "Times");
594   fprintf (stderr, "-------------------------------------------------------\n");
595 #endif
596 }