Mercurial > hg > CbC > GCC_original

comparison gcc/vec.c @ 16:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Vector API for GNU compiler. 1 /* Vector API for GNU compiler.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 Contributed by Nathan Sidwell <nathan@codesourcery.com> 3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5 5
6 This file is part of GCC. 6 This file is part of GCC.
7 7
8 GCC is free software; you can redistribute it and/or modify it under 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 9 the terms of the GNU General Public License as published by the Free
26 #else 26 #else
27 #include "config.h" 27 #include "config.h"
28 #endif 28 #endif
29 29
30 #include "system.h" 30 #include "system.h"
31 #include "ggc.h"
32 #include "vec.h"
33 #include "coretypes.h" 31 #include "coretypes.h"
32 #include "hash-table.h"
33 #include "selftest.h"
34 #ifdef GENERATOR_FILE
35 #include "errors.h"
36 #else
37 #include "input.h"
34 #include "diagnostic-core.h" 38 #include "diagnostic-core.h"
35 #include "hashtab.h" 39 #endif
36 40
37 struct vec_prefix 41 /* vNULL is an empty type with a template cast operation that returns
38 { 42 a zero-initialized vec<T, A, L> instance. Use this when you want
39 unsigned num; 43 to assign nil values to new vec instances or pass a nil vector as
40 unsigned alloc; 44 a function call argument.
41 void *vec[1]; 45
46 We use this technique because vec<T, A, L> must be PODs (they are
47 stored in unions and passed in vararg functions), this means that
48 they cannot have ctors/dtors. */
49 vnull vNULL;
50
51 /* Vector memory usage. */
52 struct vec_usage: public mem_usage
53 {
54 /* Default constructor. */
55 vec_usage (): m_items (0), m_items_peak (0) {}
56
57 /* Constructor. */
58 vec_usage (size_t allocated, size_t times, size_t peak,
59 size_t items, size_t items_peak)
60 : mem_usage (allocated, times, peak),
61 m_items (items), m_items_peak (items_peak) {}
62
63 /* Comparison operator. */
64 inline bool
65 operator< (const vec_usage &second) const
66 {
67 return (m_allocated == second.m_allocated ?
68 (m_peak == second.m_peak ? m_times < second.m_times
69 : m_peak < second.m_peak) : m_allocated < second.m_allocated);
70 }
71
72 /* Sum the usage with SECOND usage. */
73 vec_usage
74 operator+ (const vec_usage &second)
75 {
76 return vec_usage (m_allocated + second.m_allocated,
77 m_times + second.m_times,
78 m_peak + second.m_peak,
79 m_items + second.m_items,
80 m_items_peak + second.m_items_peak);
81 }
82
83 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
84 inline void
85 dump (mem_location *loc, mem_usage &total) const
86 {
87 char s[4096];
88 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
89 loc->m_line, loc->m_function);
90
91 s[48] = '\0';
92
93 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s,
94 (long)m_allocated, m_allocated * 100.0 / total.m_allocated,
95 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times,
96 (long)m_items, (long)m_items_peak);
97 }
98
99 /* Dump footer. */
100 inline void
101 dump_footer ()
102 {
103 print_dash_line ();
104 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated,
105 (long)m_times, (long)m_items);
106 print_dash_line ();
107 }
108
109 /* Dump header with NAME. */
110 static inline void
111 dump_header (const char *name)
112 {
113 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak",
114 "Times", "Leak items", "Peak items");
115 print_dash_line ();
116 }
117
118 /* Compare wrapper used by qsort method. */
119 static int
120 compare (const void *first, const void *second)
121 {
122 typedef std::pair<mem_location *, vec_usage *> mem_pair_t;
123
124 const mem_pair_t f = *(const mem_pair_t *)first;
125 const mem_pair_t s = *(const mem_pair_t *)second;
126
127 return (*f.second) < (*s.second);
128 }
129
130 /* Current number of items allocated. */
131 size_t m_items;
132 /* Peak value of number of allocated items. */
133 size_t m_items_peak;
42 }; 134 };
43 135
44 136 /* Vector memory description. */
45 #ifdef GATHER_STATISTICS 137 static mem_alloc_description <vec_usage> vec_mem_desc;
46
47 /* Store information about each particular vector. */
48 struct vec_descriptor
49 {
50 const char *function;
51 const char *file;
52 int line;
53 size_t allocated;
54 size_t times;
55 size_t peak;
56 };
57
58
59 /* Hashtable mapping vec addresses to descriptors. */
60 static htab_t vec_desc_hash;
61
62 /* Hashtable helpers. */
63 static hashval_t
64 hash_descriptor (const void *p)
65 {
66 const struct vec_descriptor *const d =
67 (const struct vec_descriptor *) p;
68 return htab_hash_pointer (d->file) + d->line;
69 }
70 static int
71 eq_descriptor (const void *p1, const void *p2)
72 {
73 const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
74 const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
75 return d->file == l->file && d->function == l->function && d->line == l->line;
76 }
77
78 /* Hashtable converting address of allocated field to loc descriptor. */
79 static htab_t ptr_hash;
80 struct ptr_hash_entry
81 {
82 void *ptr;
83 struct vec_descriptor *loc;
84 size_t allocated;
85 };
86
87 /* Hash table helpers functions. */
88 static hashval_t
89 hash_ptr (const void *p)
90 {
91 const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
92
93 return htab_hash_pointer (d->ptr);
94 }
95
96 static int
97 eq_ptr (const void *p1, const void *p2)
98 {
99 const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
100
101 return (p->ptr == p2);
102 }
103
104 /* Return descriptor for given call site, create new one if needed. */
105 static struct vec_descriptor *
106 vec_descriptor (const char *name, int line, const char *function)
107 {
108 struct vec_descriptor loc;
109 struct vec_descriptor **slot;
110
111 loc.file = name;
112 loc.line = line;
113 loc.function = function;
114 if (!vec_desc_hash)
115 vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
116
117 slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
118 INSERT);
119 if (*slot)
120 return *slot;
121 *slot = XCNEW (struct vec_descriptor);
122 (*slot)->file = name;
123 (*slot)->line = line;
124 (*slot)->function = function;
125 (*slot)->allocated = 0;
126 (*slot)->peak = 0;
127 return *slot;
128 }
129 138
130 /* Account the overhead. */ 139 /* Account the overhead. */
131 static void
132 register_overhead (struct vec_prefix *ptr, size_t size,
133 const char *name, int line, const char *function)
134 {
135 struct vec_descriptor *loc = vec_descriptor (name, line, function);
136 struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
137 PTR *slot;
138
139 p->ptr = ptr;
140 p->loc = loc;
141 p->allocated = size;
142 if (!ptr_hash)
143 ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
144 slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
145 gcc_assert (!*slot);
146 *slot = p;
147
148 loc->allocated += size;
149 if (loc->peak < loc->allocated)
150 loc->peak += loc->allocated;
151 loc->times++;
152 }
153
154 /* Notice that the pointer has been freed. */
155 static void
156 free_overhead (struct vec_prefix *ptr)
157 {
158 PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
159 NO_INSERT);
160 struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
161 p->loc->allocated -= p->allocated;
162 htab_clear_slot (ptr_hash, slot);
163 free (p);
164 }
165 140
166 void 141 void
167 vec_heap_free (void *ptr) 142 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements
168 { 143 MEM_STAT_DECL)
169 free_overhead ((struct vec_prefix *)ptr); 144 {
170 free (ptr); 145 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
171 } 146 FINAL_PASS_MEM_STAT);
172 #endif 147 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr);
173 148 usage->m_items += elements;
174 /* Calculate the new ALLOC value, making sure that RESERVE slots are 149 if (usage->m_items_peak < usage->m_items)
175 free. If EXACT grow exactly, otherwise grow exponentially. */ 150 usage->m_items_peak = usage->m_items;
176 151 }
177 static inline unsigned 152
178 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact) 153 /* Notice that the memory allocated for the vector has been freed. */
179 { 154
180 unsigned alloc = 0; 155 void
181 unsigned num = 0; 156 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor
182 157 MEM_STAT_DECL)
183 gcc_assert (reserve >= 0); 158 {
184 159 if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
185 if (pfx) 160 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
161 false FINAL_PASS_MEM_STAT);
162 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor);
163 }
164
165
166 /* Calculate the number of slots to reserve a vector, making sure that
167 it is of at least DESIRED size by growing ALLOC exponentially. */
168
169 unsigned
170 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
171 {
172 /* We must have run out of room. */
173 gcc_assert (alloc < desired);
174
175 /* Exponential growth. */
176 if (!alloc)
177 alloc = 4;
178 else if (alloc < 16)
179 /* Double when small. */
180 alloc = alloc * 2;
181 else
182 /* Grow slower when large. */
183 alloc = (alloc * 3 / 2);
184
185 /* If this is still too small, set it to the right size. */
186 if (alloc < desired)
187 alloc = desired;
188 return alloc;
189 }
190
191 /* Dump per-site memory statistics. */
192
193 void
194 dump_vec_loc_statistics (void)
195 {
196 vec_mem_desc.dump (VEC_ORIGIN);
197 }
198
199 #if CHECKING_P
200 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
201 witness elements. */
202 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
203 static void
204 qsort_chk_error (const void *p1, const void *p2, const void *p3,
205 int (*cmp) (const void *, const void *))
206 {
207 if (!p3)
186 { 208 {
187 alloc = pfx->alloc; 209 int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
188 num = pfx->num; 210 error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
189 } 211 }
190 else if (!reserve) 212 else if (p1 == p2)
191 /* If there's no prefix, and we've not requested anything, then we 213 {
192 will create a NULL vector. */ 214 int r = cmp (p1, p3);
193 return 0; 215 error ("qsort comparator non-negative on sorted output: %d", r);
194 216 }
195 /* We must have run out of room. */
196 gcc_assert (alloc - num < (unsigned) reserve);
197
198 if (exact)
199 /* Exact size. */
200 alloc = num + reserve;
201 else 217 else
202 { 218 {
203 /* Exponential growth. */ 219 int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
204 if (!alloc) 220 error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
205 alloc = 4;
206 else if (alloc < 16)
207 /* Double when small. */
208 alloc = alloc * 2;
209 else
210 /* Grow slower when large. */
211 alloc = (alloc * 3 / 2);
212
213 /* If this is still too small, set it to the right size. */
214 if (alloc < num + reserve)
215 alloc = num + reserve;
216 } 221 }
217 return alloc; 222 internal_error ("qsort checking failed");
218 } 223 }
219 224
220 /* Ensure there are at least RESERVE free slots in VEC. If EXACT grow 225 /* Wrapper around qsort with checking that CMP is consistent on given input.
221 exactly, else grow exponentially. As a special case, if VEC is 226
222 NULL and RESERVE is 0, no vector will be created. The vector's 227 Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
223 trailing array is at VEC_OFFSET offset and consists of ELT_SIZE 228 comparators to libc qsort can result in undefined behavior. Therefore we
224 sized elements. */ 229 should ideally perform consistency checks prior to invoking qsort, but in
225 230 order to do that optimally we'd need to sort the array ourselves beforehand
226 static void * 231 with a sorting routine known to be "safe". Instead, we expect that most
227 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size, 232 implementations in practice will still produce some permutation of input
228 bool exact MEM_STAT_DECL) 233 array even for invalid comparators, which enables us to perform checks on
229 { 234 the output array. */
230 struct vec_prefix *pfx = (struct vec_prefix *) vec; 235 void
231 unsigned alloc = calculate_allocation (pfx, reserve, exact); 236 qsort_chk (void *base, size_t n, size_t size,
232 237 int (*cmp)(const void *, const void *))
233 if (!alloc) 238 {
239 (qsort) (base, n, size, cmp);
240 #if 0
241 #define LIM(n) (n)
242 #else
243 /* Limit overall time complexity to O(n log n). */
244 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
245 #endif
246 #define ELT(i) ((const char *) base + (i) * size)
247 #define CMP(i, j) cmp (ELT (i), ELT (j))
248 #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
249 #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
250 size_t i1, i2, i, j;
251 /* This outer loop iterates over maximum spans [i1, i2) such that
252 elements within each span compare equal to each other. */
253 for (i1 = 0; i1 < n; i1 = i2)
234 { 254 {
235 if (pfx) 255 /* Position i2 one past last element that compares equal to i1'th. */
236 ggc_free (pfx); 256 for (i2 = i1 + 1; i2 < n; i2++)
237 return NULL; 257 if (CMP (i1, i2))
258 break;
259 else if (CMP (i2, i1))
260 return ERR2 (i1, i2);
261 size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
262 /* Verify that other pairs within current span compare equal. */
263 for (i = i1 + 1; i + 1 < i2; i++)
264 for (j = i + 1; j < i1 + lim1; j++)
265 if (CMP (i, j))
266 return ERR3 (i, i1, j);
267 else if (CMP (j, i))
268 return ERR2 (i, j);
269 /* Verify that elements within this span compare less than
270 elements beyond the span. */
271 for (i = i1; i < i2; i++)
272 for (j = i2; j < i2 + lim2; j++)
273 if (CMP (i, j) >= 0)
274 return ERR3 (i, i1, j);
275 else if (CMP (j, i) <= 0)
276 return ERR2 (i, j);
238 } 277 }
239 278 #undef ERR3
240 vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT); 279 #undef ERR2
241 ((struct vec_prefix *)vec)->alloc = alloc; 280 #undef CMP
242 if (!pfx) 281 #undef ELT
243 ((struct vec_prefix *)vec)->num = 0; 282 #undef LIM
244 283 }
245 return vec; 284 #endif /* #if CHECKING_P */
246 } 285
247 286 #ifndef GENERATOR_FILE
248 /* Ensure there are at least RESERVE free slots in VEC, growing 287 #if CHECKING_P
249 exponentially. If RESERVE < 0 grow exactly, else grow 288
250 exponentially. As a special case, if VEC is NULL, and RESERVE is 289 namespace selftest {
251 0, no vector will be created. */ 290
252 291 /* Selftests. */
253 void * 292
254 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL) 293 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
255 { 294 Helper function for selftests. */
256 return vec_gc_o_reserve_1 (vec, reserve, 295
257 offsetof (struct vec_prefix, vec), 296 static void
258 sizeof (void *), false 297 safe_push_range (vec <int>&v, int start, int limit)
259 PASS_MEM_STAT); 298 {
260 } 299 for (int i = start; i < limit; i++)
261 300 v.safe_push (i);
262 /* Ensure there are at least RESERVE free slots in VEC, growing 301 }
263 exactly. If RESERVE < 0 grow exactly, else grow exponentially. As 302
264 a special case, if VEC is NULL, and RESERVE is 0, no vector will be 303 /* Verify that vec::quick_push works correctly. */
265 created. */ 304
266 305 static void
267 void * 306 test_quick_push ()
268 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) 307 {
269 { 308 auto_vec <int> v;
270 return vec_gc_o_reserve_1 (vec, reserve, 309 ASSERT_EQ (0, v.length ());
271 offsetof (struct vec_prefix, vec), 310 v.reserve (3);
272 sizeof (void *), true 311 ASSERT_EQ (0, v.length ());
273 PASS_MEM_STAT); 312 ASSERT_TRUE (v.space (3));
274 } 313 v.quick_push (5);
275 314 v.quick_push (6);
276 /* As for vec_gc_p_reserve, but for object vectors. The vector's 315 v.quick_push (7);
277 trailing array is at VEC_OFFSET offset and consists of ELT_SIZE 316 ASSERT_EQ (3, v.length ());
278 sized elements. */ 317 ASSERT_EQ (5, v[0]);
279 318 ASSERT_EQ (6, v[1]);
280 void * 319 ASSERT_EQ (7, v[2]);
281 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size 320 }
282 MEM_STAT_DECL) 321
283 { 322 /* Verify that vec::safe_push works correctly. */
284 return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false 323
285 PASS_MEM_STAT); 324 static void
286 } 325 test_safe_push ()
287 326 {
288 /* As for vec_gc_p_reserve_exact, but for object vectors. The 327 auto_vec <int> v;
289 vector's trailing array is at VEC_OFFSET offset and consists of 328 ASSERT_EQ (0, v.length ());
290 ELT_SIZE sized elements. */ 329 v.safe_push (5);
291 330 v.safe_push (6);
292 void * 331 v.safe_push (7);
293 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset, 332 ASSERT_EQ (3, v.length ());
294 size_t elt_size MEM_STAT_DECL) 333 ASSERT_EQ (5, v[0]);
295 { 334 ASSERT_EQ (6, v[1]);
296 return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true 335 ASSERT_EQ (7, v[2]);
297 PASS_MEM_STAT); 336 }
298 } 337
299 338 /* Verify that vec::truncate works correctly. */
300 /* As for vec_gc_o_reserve_1, but for heap allocated vectors. */ 339
301 340 static void
302 static void * 341 test_truncate ()
303 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset, 342 {
304 size_t elt_size, bool exact MEM_STAT_DECL) 343 auto_vec <int> v;
305 { 344 ASSERT_EQ (0, v.length ());
306 struct vec_prefix *pfx = (struct vec_prefix *) vec; 345 safe_push_range (v, 0, 10);
307 unsigned alloc = calculate_allocation (pfx, reserve, exact); 346 ASSERT_EQ (10, v.length ());
308 347
309 if (!alloc) 348 v.truncate (5);
310 { 349 ASSERT_EQ (5, v.length ());
311 if (pfx) 350 }
312 vec_heap_free (pfx); 351
313 return NULL; 352 /* Verify that vec::safe_grow_cleared works correctly. */
314 } 353
315 354 static void
316 #ifdef GATHER_STATISTICS 355 test_safe_grow_cleared ()
317 if (vec) 356 {
318 free_overhead (pfx); 357 auto_vec <int> v;
319 #endif 358 ASSERT_EQ (0, v.length ());
320 359 v.safe_grow_cleared (50);
321 vec = xrealloc (vec, vec_offset + alloc * elt_size); 360 ASSERT_EQ (50, v.length ());
322 ((struct vec_prefix *)vec)->alloc = alloc; 361 ASSERT_EQ (0, v[0]);
323 if (!pfx) 362 ASSERT_EQ (0, v[49]);
324 ((struct vec_prefix *)vec)->num = 0; 363 }
325 #ifdef GATHER_STATISTICS 364
326 if (vec) 365 /* Verify that vec::pop works correctly. */
327 register_overhead ((struct vec_prefix *)vec, 366
328 vec_offset + alloc * elt_size PASS_MEM_STAT); 367 static void
329 #endif 368 test_pop ()
330 369 {
331 return vec; 370 auto_vec <int> v;
332 } 371 safe_push_range (v, 5, 20);
333 372 ASSERT_EQ (15, v.length ());
334 /* As for vec_gc_p_reserve, but for heap allocated vectors. */ 373
335 374 int last = v.pop ();
336 void * 375 ASSERT_EQ (19, last);
337 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL) 376 ASSERT_EQ (14, v.length ());
338 { 377 }
339 return vec_heap_o_reserve_1 (vec, reserve, 378
340 offsetof (struct vec_prefix, vec), 379 /* Verify that vec::safe_insert works correctly. */
341 sizeof (void *), false 380
342 PASS_MEM_STAT); 381 static void
343 } 382 test_safe_insert ()
344 383 {
345 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors. */ 384 auto_vec <int> v;
346 385 safe_push_range (v, 0, 10);
347 void * 386 v.safe_insert (5, 42);
348 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) 387 ASSERT_EQ (4, v[4]);
349 { 388 ASSERT_EQ (42, v[5]);
350 return vec_heap_o_reserve_1 (vec, reserve, 389 ASSERT_EQ (5, v[6]);
351 offsetof (struct vec_prefix, vec), 390 ASSERT_EQ (11, v.length ());
352 sizeof (void *), true 391 }
353 PASS_MEM_STAT); 392
354 } 393 /* Verify that vec::ordered_remove works correctly. */
355 394
356 /* As for vec_gc_o_reserve, but for heap allocated vectors. */ 395 static void
357 396 test_ordered_remove ()
358 void * 397 {
359 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size 398 auto_vec <int> v;
360 MEM_STAT_DECL) 399 safe_push_range (v, 0, 10);
361 { 400 v.ordered_remove (5);
362 return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false 401 ASSERT_EQ (4, v[4]);
363 PASS_MEM_STAT); 402 ASSERT_EQ (6, v[5]);
364 } 403 ASSERT_EQ (9, v.length ());
365 404 }
366 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors. */ 405
367 406 /* Verify that vec::unordered_remove works correctly. */
368 void * 407
369 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset, 408 static void
370 size_t elt_size MEM_STAT_DECL) 409 test_unordered_remove ()
371 { 410 {
372 return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true 411 auto_vec <int> v;
373 PASS_MEM_STAT); 412 safe_push_range (v, 0, 10);
374 } 413 v.unordered_remove (5);
375 414 ASSERT_EQ (9, v.length ());
376 /* Stack vectors are a little different. VEC_alloc turns into a call 415 }
377 to vec_stack_p_reserve_exact1 and passes in space allocated via a 416
378 call to alloca. We record that pointer so that we know that we 417 /* Verify that vec::block_remove works correctly. */
379 shouldn't free it. If the vector is resized, we resize it on the 418
380 heap. We record the pointers in a vector and search it in LIFO 419 static void
381 order--i.e., we look for the newest stack vectors first. We don't 420 test_block_remove ()
382 expect too many stack vectors at any one level, and searching from 421 {
383 the end should normally be efficient even if they are used in a 422 auto_vec <int> v;
384 recursive function. */ 423 safe_push_range (v, 0, 10);
385 424 v.block_remove (5, 3);
386 typedef void *void_p; 425 ASSERT_EQ (3, v[3]);
387 DEF_VEC_P(void_p); 426 ASSERT_EQ (4, v[4]);
388 DEF_VEC_ALLOC_P(void_p,heap); 427 ASSERT_EQ (8, v[5]);
389 428 ASSERT_EQ (9, v[6]);
390 static VEC(void_p,heap) *stack_vecs; 429 ASSERT_EQ (7, v.length ());
391 430 }
392 /* Allocate a vector which uses alloca for the initial allocation. 431
393 SPACE is space allocated using alloca, ALLOC is the number of 432 /* Comparator for use by test_qsort. */
394 entries allocated. */ 433
395 434 static int
396 void * 435 reverse_cmp (const void *p_i, const void *p_j)
397 vec_stack_p_reserve_exact_1 (int alloc, void *space) 436 {
398 { 437 return *(const int *)p_j - *(const int *)p_i;
399 struct vec_prefix *pfx = (struct vec_prefix *) space; 438 }
400 439
401 VEC_safe_push (void_p, heap, stack_vecs, space); 440 /* Verify that vec::qsort works correctly. */
402 441
403 pfx->num = 0; 442 static void
404 pfx->alloc = alloc; 443 test_qsort ()
405 444 {
406 return space; 445 auto_vec <int> v;
407 } 446 safe_push_range (v, 0, 10);
408 447 v.qsort (reverse_cmp);
409 /* Grow a vector allocated using alloca. When this happens, we switch 448 ASSERT_EQ (9, v[0]);
410 back to heap allocation. We remove the vector from stack_vecs, if 449 ASSERT_EQ (8, v[1]);
411 it is there, since we no longer need to avoid freeing it. */ 450 ASSERT_EQ (1, v[8]);
412 451 ASSERT_EQ (0, v[9]);
413 static void * 452 ASSERT_EQ (10, v.length ());
414 vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset, 453 }
415 size_t elt_size, bool exact MEM_STAT_DECL) 454
416 { 455 /* Run all of the selftests within this file. */
417 bool found;
418 unsigned int ix;
419 void *newvec;
420
421 found = false;
422 for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
423 {
424 if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
425 {
426 VEC_unordered_remove (void_p, stack_vecs, ix - 1);
427 found = true;
428 break;
429 }
430 }
431
432 if (!found)
433 {
434 /* VEC is already on the heap. */
435 return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
436 exact PASS_MEM_STAT);
437 }
438
439 /* Move VEC to the heap. */
440 reserve += ((struct vec_prefix *) vec)->num;
441 newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
442 exact PASS_MEM_STAT);
443 if (newvec && vec)
444 {
445 ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
446 memcpy (((struct vec_prefix *) newvec)->vec,
447 ((struct vec_prefix *) vec)->vec,
448 ((struct vec_prefix *) vec)->num * elt_size);
449 }
450 return newvec;
451 }
452
453 /* Grow a vector allocated on the stack. */
454
455 void *
456 vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
457 {
458 return vec_stack_o_reserve_1 (vec, reserve,
459 offsetof (struct vec_prefix, vec),
460 sizeof (void *), false
461 PASS_MEM_STAT);
462 }
463
464 /* Exact version of vec_stack_p_reserve. */
465
466 void *
467 vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
468 {
469 return vec_stack_o_reserve_1 (vec, reserve,
470 offsetof (struct vec_prefix, vec),
471 sizeof (void *), true
472 PASS_MEM_STAT);
473 }
474
475 /* Like vec_stack_p_reserve, but for objects. */
476
477 void *
478 vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
479 size_t elt_size MEM_STAT_DECL)
480 {
481 return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
482 PASS_MEM_STAT);
483 }
484
485 /* Like vec_stack_p_reserve_exact, but for objects. */
486
487 void *
488 vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
489 size_t elt_size MEM_STAT_DECL)
490 {
491 return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
492 PASS_MEM_STAT);
493 }
494
495 /* Free a vector allocated on the stack. Don't actually free it if we
496 find it in the hash table. */
497 456
498 void 457 void
499 vec_stack_free (void *vec) 458 vec_c_tests ()
500 { 459 {
501 unsigned int ix; 460 test_quick_push ();
502 461 test_safe_push ();
503 for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix) 462 test_truncate ();
504 { 463 test_safe_grow_cleared ();
505 if (VEC_index (void_p, stack_vecs, ix - 1) == vec) 464 test_pop ();
506 { 465 test_safe_insert ();
507 VEC_unordered_remove (void_p, stack_vecs, ix - 1); 466 test_ordered_remove ();
508 return; 467 test_unordered_remove ();
509 } 468 test_block_remove ();
510 } 469 test_qsort ();
511 470 }
512 /* VEC was not on the list of vecs allocated on the stack, so it 471
513 must be allocated on the heap. */ 472 } // namespace selftest
514 vec_heap_free (vec); 473
515 } 474 #endif /* #if CHECKING_P */
516 475 #endif /* #ifndef GENERATOR_FILE */
517 #if ENABLE_CHECKING
518 /* Issue a vector domain error, and then fall over. */
519
520 void
521 vec_assert_fail (const char *op, const char *struct_name,
522 const char *file, unsigned int line, const char *function)
523 {
524 internal_error ("vector %s %s domain error, in %s at %s:%u",
525 struct_name, op, function, trim_filename (file), line);
526 }
527 #endif
528
529 #ifdef GATHER_STATISTICS
530 /* Helper for qsort; sort descriptors by amount of memory consumed. */
531 static int
532 cmp_statistic (const void *loc1, const void *loc2)
533 {
534 const struct vec_descriptor *const l1 =
535 *(const struct vec_descriptor *const *) loc1;
536 const struct vec_descriptor *const l2 =
537 *(const struct vec_descriptor *const *) loc2;
538 long diff;
539 diff = l1->allocated - l2->allocated;
540 if (!diff)
541 diff = l1->peak - l2->peak;
542 if (!diff)
543 diff = l1->times - l2->times;
544 return diff > 0 ? 1 : diff < 0 ? -1 : 0;
545 }
546 /* Collect array of the descriptors from hashtable. */
547 static struct vec_descriptor **loc_array;
548 static int
549 add_statistics (void **slot, void *b)
550 {
551 int *n = (int *)b;
552 loc_array[*n] = (struct vec_descriptor *) *slot;
553 (*n)++;
554 return 1;
555 }
556
557 /* Dump per-site memory statistics. */
558 #endif
559 void
560 dump_vec_loc_statistics (void)
561 {
562 #ifdef GATHER_STATISTICS
563 int nentries = 0;
564 char s[4096];
565 size_t allocated = 0;
566 size_t times = 0;
567 int i;
568
569 loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
570 fprintf (stderr, "Heap vectors:\n");
571 fprintf (stderr, "\n%-48s %10s %10s %10s\n",
572 "source location", "Leak", "Peak", "Times");
573 fprintf (stderr, "-------------------------------------------------------\n");
574 htab_traverse (vec_desc_hash, add_statistics, &nentries);
575 qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
576 for (i = 0; i < nentries; i++)
577 {
578 struct vec_descriptor *d = loc_array[i];
579 allocated += d->allocated;
580 times += d->times;
581 }
582 for (i = 0; i < nentries; i++)
583 {
584 struct vec_descriptor *d = loc_array[i];
585 const char *s1 = d->file;
586 const char *s2;
587 while ((s2 = strstr (s1, "gcc/")))
588 s1 = s2 + 4;
589 sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
590 s[48] = 0;
591 fprintf (stderr, "%-48s %10li:%4.1f%% %10li %10li:%4.1f%% \n", s,
592 (long)d->allocated,
593 (d->allocated) * 100.0 / allocated,
594 (long)d->peak,
595 (long)d->times,
596 (d->times) * 100.0 / times);
597 }
598 fprintf (stderr, "%-48s %10ld %10ld\n",
599 "Total", (long)allocated, (long)times);
600 fprintf (stderr, "\n%-48s %10s %10s %10s\n",
601 "source location", "Leak", "Peak", "Times");
602 fprintf (stderr, "-------------------------------------------------------\n");
603 #endif
604 }