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>
6 This file is part of GCC.
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
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
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/>. */
22 /* This file is compiled twice: once for the generator programs
23 once for the compiler. */
31 #include "coretypes.h"
34 #include "diagnostic-core.h"
37 /* Store information about each particular vector. */
49 /* Hashtable mapping vec addresses to descriptors. */
50 static htab_t vec_desc_hash
;
52 /* Hashtable helpers. */
54 hash_descriptor (const void *p
)
56 const struct vec_descriptor
*const d
=
57 (const struct vec_descriptor
*) p
;
58 return htab_hash_pointer (d
->file
) + d
->line
;
61 eq_descriptor (const void *p1
, const void *p2
)
63 const struct vec_descriptor
*const d
= (const struct vec_descriptor
*) p1
;
64 const struct vec_descriptor
*const l
= (const struct vec_descriptor
*) p2
;
65 return d
->file
== l
->file
&& d
->function
== l
->function
&& d
->line
== l
->line
;
68 /* Hashtable converting address of allocated field to loc descriptor. */
69 static htab_t ptr_hash
;
73 struct vec_descriptor
*loc
;
77 /* Hash table helpers functions. */
79 hash_ptr (const void *p
)
81 const struct ptr_hash_entry
*const d
= (const struct ptr_hash_entry
*) p
;
83 return htab_hash_pointer (d
->ptr
);
87 eq_ptr (const void *p1
, const void *p2
)
89 const struct ptr_hash_entry
*const p
= (const struct ptr_hash_entry
*) p1
;
91 return (p
->ptr
== p2
);
94 /* Return descriptor for given call site, create new one if needed. */
95 static struct vec_descriptor
*
96 vec_descriptor (const char *name
, int line
, const char *function
)
98 struct vec_descriptor loc
;
99 struct vec_descriptor
**slot
;
103 loc
.function
= function
;
105 vec_desc_hash
= htab_create (10, hash_descriptor
, eq_descriptor
, NULL
);
107 slot
= (struct vec_descriptor
**) htab_find_slot (vec_desc_hash
, &loc
,
111 *slot
= XCNEW (struct vec_descriptor
);
112 (*slot
)->file
= name
;
113 (*slot
)->line
= line
;
114 (*slot
)->function
= function
;
115 (*slot
)->allocated
= 0;
120 /* Account the overhead. */
122 register_overhead (struct vec_prefix
*ptr
, size_t size
,
123 const char *name
, int line
, const char *function
)
125 struct vec_descriptor
*loc
= vec_descriptor (name
, line
, function
);
126 struct ptr_hash_entry
*p
= XNEW (struct ptr_hash_entry
);
133 ptr_hash
= htab_create (10, hash_ptr
, eq_ptr
, NULL
);
134 slot
= htab_find_slot_with_hash (ptr_hash
, ptr
, htab_hash_pointer (ptr
), INSERT
);
138 loc
->allocated
+= size
;
139 if (loc
->peak
< loc
->allocated
)
140 loc
->peak
+= loc
->allocated
;
144 /* Notice that the pointer has been freed. */
146 free_overhead (struct vec_prefix
*ptr
)
148 PTR
*slot
= htab_find_slot_with_hash (ptr_hash
, ptr
, htab_hash_pointer (ptr
),
150 struct ptr_hash_entry
*p
= (struct ptr_hash_entry
*) *slot
;
151 p
->loc
->allocated
-= p
->allocated
;
152 htab_clear_slot (ptr_hash
, slot
);
157 vec_heap_free (void *ptr
)
159 if (GATHER_STATISTICS
)
160 free_overhead ((struct vec_prefix
*)ptr
);
164 /* Calculate the new ALLOC value, making sure that RESERVE slots are
165 free. If EXACT grow exactly, otherwise grow exponentially. */
167 static inline unsigned
168 calculate_allocation (const struct vec_prefix
*pfx
, int reserve
, bool exact
)
173 gcc_assert (reserve
>= 0);
181 /* If there's no prefix, and we've not requested anything, then we
182 will create a NULL vector. */
185 /* We must have run out of room. */
186 gcc_assert (alloc
- num
< (unsigned) reserve
);
190 alloc
= num
+ reserve
;
193 /* Exponential growth. */
197 /* Double when small. */
200 /* Grow slower when large. */
201 alloc
= (alloc
* 3 / 2);
203 /* If this is still too small, set it to the right size. */
204 if (alloc
< num
+ reserve
)
205 alloc
= num
+ reserve
;
210 /* Ensure there are at least RESERVE free slots in VEC. If EXACT grow
211 exactly, else grow exponentially. As a special case, if VEC is
212 NULL and RESERVE is 0, no vector will be created. The vector's
213 trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
217 vec_gc_o_reserve_1 (void *vec
, int reserve
, size_t vec_offset
, size_t elt_size
,
218 bool exact MEM_STAT_DECL
)
220 struct vec_prefix
*pfx
= (struct vec_prefix
*) vec
;
221 unsigned alloc
= calculate_allocation (pfx
, reserve
, exact
);
231 /* Calculate the amount of space we want. */
232 size
= vec_offset
+ alloc
* elt_size
;
233 /* Ask the allocator how much space it will really give us. */
234 size
= ggc_round_alloc_size (size
);
235 /* Adjust the number of slots accordingly. */
236 alloc
= (size
- vec_offset
) / elt_size
;
237 /* And finally, recalculate the amount of space we ask for. */
238 size
= vec_offset
+ alloc
* elt_size
;
240 vec
= ggc_realloc_stat (vec
, size PASS_MEM_STAT
);
242 ((struct vec_prefix
*)vec
)->alloc
= alloc
;
244 ((struct vec_prefix
*)vec
)->num
= 0;
249 /* Ensure there are at least RESERVE free slots in VEC, growing
250 exponentially. If RESERVE < 0 grow exactly, else grow
251 exponentially. As a special case, if VEC is NULL, and RESERVE is
252 0, no vector will be created. */
255 vec_gc_p_reserve (void *vec
, int reserve MEM_STAT_DECL
)
257 return vec_gc_o_reserve_1 (vec
, reserve
,
258 sizeof (struct vec_prefix
),
259 sizeof (void *), false
263 /* Ensure there are at least RESERVE free slots in VEC, growing
264 exactly. If RESERVE < 0 grow exactly, else grow exponentially. As
265 a special case, if VEC is NULL, and RESERVE is 0, no vector will be
269 vec_gc_p_reserve_exact (void *vec
, int reserve MEM_STAT_DECL
)
271 return vec_gc_o_reserve_1 (vec
, reserve
,
272 sizeof (struct vec_prefix
),
273 sizeof (void *), true
277 /* As for vec_gc_p_reserve, but for object vectors. The vector's
278 trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
282 vec_gc_o_reserve (void *vec
, int reserve
, size_t vec_offset
, size_t elt_size
285 return vec_gc_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
, false
289 /* As for vec_gc_p_reserve_exact, but for object vectors. The
290 vector's trailing array is at VEC_OFFSET offset and consists of
291 ELT_SIZE sized elements. */
294 vec_gc_o_reserve_exact (void *vec
, int reserve
, size_t vec_offset
,
295 size_t elt_size MEM_STAT_DECL
)
297 return vec_gc_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
, true
301 /* As for vec_gc_o_reserve_1, but for heap allocated vectors. */
304 vec_heap_o_reserve_1 (void *vec
, int reserve
, size_t vec_offset
,
305 size_t elt_size
, bool exact MEM_STAT_DECL
)
307 struct vec_prefix
*pfx
= (struct vec_prefix
*) vec
;
308 unsigned alloc
= calculate_allocation (pfx
, reserve
, exact
);
317 if (GATHER_STATISTICS
&& vec
)
320 vec
= xrealloc (vec
, vec_offset
+ alloc
* elt_size
);
321 ((struct vec_prefix
*)vec
)->alloc
= alloc
;
323 ((struct vec_prefix
*)vec
)->num
= 0;
324 if (GATHER_STATISTICS
&& vec
)
325 register_overhead ((struct vec_prefix
*)vec
,
326 vec_offset
+ alloc
* elt_size FINAL_PASS_MEM_STAT
);
331 /* As for vec_gc_p_reserve, but for heap allocated vectors. */
334 vec_heap_p_reserve (void *vec
, int reserve MEM_STAT_DECL
)
336 return vec_heap_o_reserve_1 (vec
, reserve
,
337 sizeof (struct vec_prefix
),
338 sizeof (void *), false
342 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors. */
345 vec_heap_p_reserve_exact (void *vec
, int reserve MEM_STAT_DECL
)
347 return vec_heap_o_reserve_1 (vec
, reserve
,
348 sizeof (struct vec_prefix
),
349 sizeof (void *), true
353 /* As for vec_gc_o_reserve, but for heap allocated vectors. */
356 vec_heap_o_reserve (void *vec
, int reserve
, size_t vec_offset
, size_t elt_size
359 return vec_heap_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
, false
363 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors. */
366 vec_heap_o_reserve_exact (void *vec
, int reserve
, size_t vec_offset
,
367 size_t elt_size MEM_STAT_DECL
)
369 return vec_heap_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
, true
373 /* Stack vectors are a little different. VEC_alloc turns into a call
374 to vec_stack_p_reserve_exact1 and passes in space allocated via a
375 call to alloca. We record that pointer so that we know that we
376 shouldn't free it. If the vector is resized, we resize it on the
377 heap. We record the pointers in a vector and search it in LIFO
378 order--i.e., we look for the newest stack vectors first. We don't
379 expect too many stack vectors at any one level, and searching from
380 the end should normally be efficient even if they are used in a
381 recursive function. */
383 typedef void *void_p
;
385 DEF_VEC_ALLOC_P(void_p
,heap
);
387 static VEC(void_p
,heap
) *stack_vecs
;
389 /* Allocate a vector which uses alloca for the initial allocation.
390 SPACE is space allocated using alloca, ALLOC is the number of
391 entries allocated. */
394 vec_stack_p_reserve_exact_1 (int alloc
, void *space
)
396 struct vec_prefix
*pfx
= (struct vec_prefix
*) space
;
398 VEC_safe_push (void_p
, heap
, stack_vecs
, space
);
406 /* Grow a vector allocated using alloca. When this happens, we switch
407 back to heap allocation. We remove the vector from stack_vecs, if
408 it is there, since we no longer need to avoid freeing it. */
411 vec_stack_o_reserve_1 (void *vec
, int reserve
, size_t vec_offset
,
412 size_t elt_size
, bool exact MEM_STAT_DECL
)
419 for (ix
= VEC_length (void_p
, stack_vecs
); ix
> 0; --ix
)
421 if (VEC_index (void_p
, stack_vecs
, ix
- 1) == vec
)
423 VEC_unordered_remove (void_p
, stack_vecs
, ix
- 1);
431 /* VEC is already on the heap. */
432 return vec_heap_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
,
433 exact PASS_MEM_STAT
);
436 /* Move VEC to the heap. */
437 reserve
+= ((struct vec_prefix
*) vec
)->num
;
438 newvec
= vec_heap_o_reserve_1 (NULL
, reserve
, vec_offset
, elt_size
,
439 exact PASS_MEM_STAT
);
442 ((struct vec_prefix
*) newvec
)->num
= ((struct vec_prefix
*) vec
)->num
;
443 memcpy (((struct vec_prefix
*) newvec
)+1,
444 ((struct vec_prefix
*) vec
)+1,
445 ((struct vec_prefix
*) vec
)->num
* elt_size
);
450 /* Grow a vector allocated on the stack. */
453 vec_stack_p_reserve (void *vec
, int reserve MEM_STAT_DECL
)
455 return vec_stack_o_reserve_1 (vec
, reserve
,
456 sizeof (struct vec_prefix
),
457 sizeof (void *), false
461 /* Exact version of vec_stack_p_reserve. */
464 vec_stack_p_reserve_exact (void *vec
, int reserve MEM_STAT_DECL
)
466 return vec_stack_o_reserve_1 (vec
, reserve
,
467 sizeof (struct vec_prefix
),
468 sizeof (void *), true
472 /* Like vec_stack_p_reserve, but for objects. */
475 vec_stack_o_reserve (void *vec
, int reserve
, size_t vec_offset
,
476 size_t elt_size MEM_STAT_DECL
)
478 return vec_stack_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
, false
482 /* Like vec_stack_p_reserve_exact, but for objects. */
485 vec_stack_o_reserve_exact (void *vec
, int reserve
, size_t vec_offset
,
486 size_t elt_size MEM_STAT_DECL
)
488 return vec_stack_o_reserve_1 (vec
, reserve
, vec_offset
, elt_size
, true
492 /* Free a vector allocated on the stack. Don't actually free it if we
493 find it in the hash table. */
496 vec_stack_free (void *vec
)
500 for (ix
= VEC_length (void_p
, stack_vecs
); ix
> 0; --ix
)
502 if (VEC_index (void_p
, stack_vecs
, ix
- 1) == vec
)
504 VEC_unordered_remove (void_p
, stack_vecs
, ix
- 1);
509 /* VEC was not on the list of vecs allocated on the stack, so it
510 must be allocated on the heap. */
515 /* Issue a vector domain error, and then fall over. */
518 vec_assert_fail (const char *op
, const char *struct_name
,
519 const char *file
, unsigned int line
, const char *function
)
521 internal_error ("vector %s %s domain error, in %s at %s:%u",
522 struct_name
, op
, function
, trim_filename (file
), line
);
526 /* Helper for qsort; sort descriptors by amount of memory consumed. */
528 cmp_statistic (const void *loc1
, const void *loc2
)
530 const struct vec_descriptor
*const l1
=
531 *(const struct vec_descriptor
*const *) loc1
;
532 const struct vec_descriptor
*const l2
=
533 *(const struct vec_descriptor
*const *) loc2
;
535 diff
= l1
->allocated
- l2
->allocated
;
537 diff
= l1
->peak
- l2
->peak
;
539 diff
= l1
->times
- l2
->times
;
540 return diff
> 0 ? 1 : diff
< 0 ? -1 : 0;
542 /* Collect array of the descriptors from hashtable. */
543 static struct vec_descriptor
**loc_array
;
545 add_statistics (void **slot
, void *b
)
548 loc_array
[*n
] = (struct vec_descriptor
*) *slot
;
553 /* Dump per-site memory statistics. */
556 dump_vec_loc_statistics (void)
560 size_t allocated
= 0;
564 if (! GATHER_STATISTICS
)
567 loc_array
= XCNEWVEC (struct vec_descriptor
*, vec_desc_hash
->n_elements
);
568 fprintf (stderr
, "Heap vectors:\n");
569 fprintf (stderr
, "\n%-48s %10s %10s %10s\n",
570 "source location", "Leak", "Peak", "Times");
571 fprintf (stderr
, "-------------------------------------------------------\n");
572 htab_traverse (vec_desc_hash
, add_statistics
, &nentries
);
573 qsort (loc_array
, nentries
, sizeof (*loc_array
), cmp_statistic
);
574 for (i
= 0; i
< nentries
; i
++)
576 struct vec_descriptor
*d
= loc_array
[i
];
577 allocated
+= d
->allocated
;
580 for (i
= 0; i
< nentries
; i
++)
582 struct vec_descriptor
*d
= loc_array
[i
];
583 const char *s1
= d
->file
;
585 while ((s2
= strstr (s1
, "gcc/")))
587 sprintf (s
, "%s:%i (%s)", s1
, d
->line
, d
->function
);
589 fprintf (stderr
, "%-48s %10li:%4.1f%% %10li %10li:%4.1f%% \n", s
,
591 (d
->allocated
) * 100.0 / allocated
,
594 (d
->times
) * 100.0 / times
);
596 fprintf (stderr
, "%-48s %10ld %10ld\n",
597 "Total", (long)allocated
, (long)times
);
598 fprintf (stderr
, "\n%-48s %10s %10s %10s\n",
599 "source location", "Leak", "Peak", "Times");
600 fprintf (stderr
, "-------------------------------------------------------\n");