]>
Commit | Line | Data |
---|---|---|
190183c5 | 1 | /* Vector API for GNU compiler. |
fbd26352 | 2 | Copyright (C) 2004-2019 Free Software Foundation, Inc. |
190183c5 | 3 | Contributed by Nathan Sidwell <nathan@codesourcery.com> |
2b15d2ba | 4 | Re-implemented in C++ by Diego Novillo <dnovillo@google.com> |
190183c5 | 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 | |
8c4c00c1 | 10 | Software Foundation; either version 3, or (at your option) any later |
190183c5 | 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 | |
8c4c00c1 | 19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
190183c5 | 21 | |
c169e46c | 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 | |
190183c5 | 27 | #include "config.h" |
c169e46c | 28 | #endif |
29 | ||
190183c5 | 30 | #include "system.h" |
72e5da43 | 31 | #include "coretypes.h" |
64486212 | 32 | #include "hash-table.h" |
99b4f3a2 | 33 | #include "selftest.h" |
c3808779 | 34 | #ifdef GENERATOR_FILE |
35 | #include "errors.h" | |
36 | #else | |
37 | #include "input.h" | |
38 | #include "diagnostic-core.h" | |
39 | #endif | |
190183c5 | 40 | |
1e094109 | 41 | /* vNULL is an empty type with a template cast operation that returns |
42 | a zero-initialized vec<T, A, L> instance. Use this when you want | |
43 | to assign nil values to new vec instances or pass a nil vector as | |
44 | a function call argument. | |
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 | ||
0ff42de5 | 51 | /* Vector memory usage. */ |
52 | struct vec_usage: public mem_usage | |
eec2888b | 53 | { |
0ff42de5 | 54 | /* Default constructor. */ |
8f9d6dd9 | 55 | vec_usage (): m_items (0), m_items_peak (0), m_element_size (0) {} |
0ff42de5 | 56 | |
57 | /* Constructor. */ | |
58 | vec_usage (size_t allocated, size_t times, size_t peak, | |
8f9d6dd9 | 59 | size_t items, size_t items_peak, size_t element_size) |
0ff42de5 | 60 | : mem_usage (allocated, times, peak), |
8f9d6dd9 | 61 | m_items (items), m_items_peak (items_peak), |
62 | m_element_size (element_size) {} | |
0ff42de5 | 63 | |
0ff42de5 | 64 | /* Sum the usage with SECOND usage. */ |
94302dfa | 65 | vec_usage |
66 | operator+ (const vec_usage &second) | |
0ff42de5 | 67 | { |
68 | return vec_usage (m_allocated + second.m_allocated, | |
69 | m_times + second.m_times, | |
70 | m_peak + second.m_peak, | |
71 | m_items + second.m_items, | |
8f9d6dd9 | 72 | m_items_peak + second.m_items_peak, 0); |
0ff42de5 | 73 | } |
74 | ||
75 | /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */ | |
94302dfa | 76 | inline void |
77 | dump (mem_location *loc, mem_usage &total) const | |
0ff42de5 | 78 | { |
79 | char s[4096]; | |
80 | sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (), | |
81 | loc->m_line, loc->m_function); | |
82 | ||
83 | s[48] = '\0'; | |
84 | ||
7a413494 | 85 | fprintf (stderr, |
03fac02c | 86 | "%-48s %10" PRIu64 PRsa (10) ":%4.1f%%" PRsa (9) "%10" PRIu64 |
87 | ":%4.1f%%" PRsa (10) PRsa (10) "\n", | |
7a413494 | 88 | s, |
03fac02c | 89 | (uint64_t)m_element_size, |
7a413494 | 90 | SIZE_AMOUNT (m_allocated), |
91 | m_allocated * 100.0 / total.m_allocated, | |
03fac02c | 92 | SIZE_AMOUNT (m_peak), (uint64_t)m_times, |
7a413494 | 93 | m_times * 100.0 / total.m_times, |
94 | SIZE_AMOUNT (m_items), SIZE_AMOUNT (m_items_peak)); | |
0ff42de5 | 95 | } |
96 | ||
97 | /* Dump footer. */ | |
94302dfa | 98 | inline void |
99 | dump_footer () | |
0ff42de5 | 100 | { |
03fac02c | 101 | fprintf (stderr, "%s" PRsa (64) PRsa (25) PRsa (16) "\n", |
7a413494 | 102 | "Total", SIZE_AMOUNT (m_allocated), |
103 | SIZE_AMOUNT (m_times), SIZE_AMOUNT (m_items)); | |
0ff42de5 | 104 | } |
105 | ||
106 | /* Dump header with NAME. */ | |
94302dfa | 107 | static inline void |
108 | dump_header (const char *name) | |
0ff42de5 | 109 | { |
8f9d6dd9 | 110 | fprintf (stderr, "%-48s %10s%11s%16s%10s%17s%11s\n", name, "sizeof(T)", |
111 | "Leak", "Peak", "Times", "Leak items", "Peak items"); | |
0ff42de5 | 112 | } |
113 | ||
0ff42de5 | 114 | /* Current number of items allocated. */ |
115 | size_t m_items; | |
116 | /* Peak value of number of allocated items. */ | |
117 | size_t m_items_peak; | |
8f9d6dd9 | 118 | /* Size of element of the vector. */ |
119 | size_t m_element_size; | |
eec2888b | 120 | }; |
121 | ||
0ff42de5 | 122 | /* Vector memory description. */ |
123 | static mem_alloc_description <vec_usage> vec_mem_desc; | |
eec2888b | 124 | |
125 | /* Account the overhead. */ | |
f1f41a6c | 126 | |
127 | void | |
8f9d6dd9 | 128 | vec_prefix::register_overhead (void *ptr, size_t elements, |
129 | size_t element_size MEM_STAT_DECL) | |
eec2888b | 130 | { |
a80feb6c | 131 | vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false |
132 | FINAL_PASS_MEM_STAT); | |
8f9d6dd9 | 133 | vec_usage *usage |
134 | = vec_mem_desc.register_instance_overhead (elements * element_size, ptr); | |
135 | usage->m_element_size = element_size; | |
0ff42de5 | 136 | usage->m_items += elements; |
137 | if (usage->m_items_peak < usage->m_items) | |
138 | usage->m_items_peak = usage->m_items; | |
eec2888b | 139 | } |
140 | ||
f1f41a6c | 141 | /* Notice that the memory allocated for the vector has been freed. */ |
142 | ||
143 | void | |
8f9d6dd9 | 144 | vec_prefix::release_overhead (void *ptr, size_t size, size_t elements, |
145 | bool in_dtor MEM_STAT_DECL) | |
eec2888b | 146 | { |
0ff42de5 | 147 | if (!vec_mem_desc.contains_descriptor_for_instance (ptr)) |
a80feb6c | 148 | vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, |
149 | false FINAL_PASS_MEM_STAT); | |
8f9d6dd9 | 150 | vec_usage *usage = vec_mem_desc.release_instance_overhead (ptr, size, |
151 | in_dtor); | |
152 | usage->m_items -= elements; | |
eec2888b | 153 | } |
154 | ||
f1f41a6c | 155 | /* Calculate the number of slots to reserve a vector, making sure that |
ec456ba8 | 156 | it is of at least DESIRED size by growing ALLOC exponentially. */ |
046bfc77 | 157 | |
f1f41a6c | 158 | unsigned |
ec456ba8 | 159 | vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired) |
046bfc77 | 160 | { |
046bfc77 | 161 | /* We must have run out of room. */ |
ec456ba8 | 162 | gcc_assert (alloc < desired); |
163 | ||
164 | /* Exponential growth. */ | |
165 | if (!alloc) | |
166 | alloc = 4; | |
167 | else if (alloc < 16) | |
168 | /* Double when small. */ | |
169 | alloc = alloc * 2; | |
046bfc77 | 170 | else |
ec456ba8 | 171 | /* Grow slower when large. */ |
172 | alloc = (alloc * 3 / 2); | |
173 | ||
174 | /* If this is still too small, set it to the right size. */ | |
175 | if (alloc < desired) | |
176 | alloc = desired; | |
046bfc77 | 177 | return alloc; |
178 | } | |
179 | ||
eec2888b | 180 | /* Dump per-site memory statistics. */ |
ecd52ea9 | 181 | |
eec2888b | 182 | void |
183 | dump_vec_loc_statistics (void) | |
184 | { | |
a80feb6c | 185 | vec_mem_desc.dump (VEC_ORIGIN); |
eec2888b | 186 | } |
99b4f3a2 | 187 | |
c3808779 | 188 | #if CHECKING_P |
189 | /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as | |
190 | witness elements. */ | |
191 | ATTRIBUTE_NORETURN ATTRIBUTE_COLD | |
192 | static void | |
193 | qsort_chk_error (const void *p1, const void *p2, const void *p3, | |
194 | int (*cmp) (const void *, const void *)) | |
195 | { | |
196 | if (!p3) | |
197 | { | |
198 | int r1 = cmp (p1, p2), r2 = cmp (p2, p1); | |
199 | error ("qsort comparator not anti-commutative: %d, %d", r1, r2); | |
200 | } | |
201 | else if (p1 == p2) | |
202 | { | |
203 | int r = cmp (p1, p3); | |
204 | error ("qsort comparator non-negative on sorted output: %d", r); | |
205 | } | |
206 | else | |
207 | { | |
208 | int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3); | |
209 | error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3); | |
210 | } | |
211 | internal_error ("qsort checking failed"); | |
212 | } | |
213 | ||
8c16143c | 214 | /* Verify anti-symmetry and transitivity for comparator CMP on sorted array |
215 | of N SIZE-sized elements pointed to by BASE. */ | |
c3808779 | 216 | void |
217 | qsort_chk (void *base, size_t n, size_t size, | |
218 | int (*cmp)(const void *, const void *)) | |
219 | { | |
c3808779 | 220 | #if 0 |
221 | #define LIM(n) (n) | |
222 | #else | |
223 | /* Limit overall time complexity to O(n log n). */ | |
224 | #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) | |
225 | #endif | |
226 | #define ELT(i) ((const char *) base + (i) * size) | |
227 | #define CMP(i, j) cmp (ELT (i), ELT (j)) | |
228 | #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp) | |
229 | #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) | |
230 | size_t i1, i2, i, j; | |
231 | /* This outer loop iterates over maximum spans [i1, i2) such that | |
232 | elements within each span compare equal to each other. */ | |
233 | for (i1 = 0; i1 < n; i1 = i2) | |
234 | { | |
235 | /* Position i2 one past last element that compares equal to i1'th. */ | |
236 | for (i2 = i1 + 1; i2 < n; i2++) | |
237 | if (CMP (i1, i2)) | |
238 | break; | |
239 | else if (CMP (i2, i1)) | |
240 | return ERR2 (i1, i2); | |
241 | size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); | |
242 | /* Verify that other pairs within current span compare equal. */ | |
243 | for (i = i1 + 1; i + 1 < i2; i++) | |
244 | for (j = i + 1; j < i1 + lim1; j++) | |
245 | if (CMP (i, j)) | |
246 | return ERR3 (i, i1, j); | |
247 | else if (CMP (j, i)) | |
248 | return ERR2 (i, j); | |
249 | /* Verify that elements within this span compare less than | |
250 | elements beyond the span. */ | |
251 | for (i = i1; i < i2; i++) | |
252 | for (j = i2; j < i2 + lim2; j++) | |
253 | if (CMP (i, j) >= 0) | |
254 | return ERR3 (i, i1, j); | |
255 | else if (CMP (j, i) <= 0) | |
256 | return ERR2 (i, j); | |
257 | } | |
258 | #undef ERR3 | |
259 | #undef ERR2 | |
260 | #undef CMP | |
261 | #undef ELT | |
262 | #undef LIM | |
263 | } | |
264 | #endif /* #if CHECKING_P */ | |
265 | ||
99b4f3a2 | 266 | #ifndef GENERATOR_FILE |
267 | #if CHECKING_P | |
268 | ||
269 | namespace selftest { | |
270 | ||
271 | /* Selftests. */ | |
272 | ||
273 | /* Call V.safe_push for all ints from START up to, but not including LIMIT. | |
274 | Helper function for selftests. */ | |
275 | ||
276 | static void | |
277 | safe_push_range (vec <int>&v, int start, int limit) | |
278 | { | |
279 | for (int i = start; i < limit; i++) | |
280 | v.safe_push (i); | |
281 | } | |
282 | ||
283 | /* Verify that vec::quick_push works correctly. */ | |
284 | ||
285 | static void | |
286 | test_quick_push () | |
287 | { | |
288 | auto_vec <int> v; | |
289 | ASSERT_EQ (0, v.length ()); | |
290 | v.reserve (3); | |
291 | ASSERT_EQ (0, v.length ()); | |
292 | ASSERT_TRUE (v.space (3)); | |
293 | v.quick_push (5); | |
294 | v.quick_push (6); | |
295 | v.quick_push (7); | |
296 | ASSERT_EQ (3, v.length ()); | |
297 | ASSERT_EQ (5, v[0]); | |
298 | ASSERT_EQ (6, v[1]); | |
299 | ASSERT_EQ (7, v[2]); | |
300 | } | |
301 | ||
302 | /* Verify that vec::safe_push works correctly. */ | |
303 | ||
304 | static void | |
305 | test_safe_push () | |
306 | { | |
307 | auto_vec <int> v; | |
308 | ASSERT_EQ (0, v.length ()); | |
309 | v.safe_push (5); | |
310 | v.safe_push (6); | |
311 | v.safe_push (7); | |
312 | ASSERT_EQ (3, v.length ()); | |
313 | ASSERT_EQ (5, v[0]); | |
314 | ASSERT_EQ (6, v[1]); | |
315 | ASSERT_EQ (7, v[2]); | |
316 | } | |
317 | ||
318 | /* Verify that vec::truncate works correctly. */ | |
319 | ||
320 | static void | |
321 | test_truncate () | |
322 | { | |
323 | auto_vec <int> v; | |
324 | ASSERT_EQ (0, v.length ()); | |
325 | safe_push_range (v, 0, 10); | |
326 | ASSERT_EQ (10, v.length ()); | |
327 | ||
328 | v.truncate (5); | |
329 | ASSERT_EQ (5, v.length ()); | |
330 | } | |
331 | ||
332 | /* Verify that vec::safe_grow_cleared works correctly. */ | |
333 | ||
334 | static void | |
335 | test_safe_grow_cleared () | |
336 | { | |
337 | auto_vec <int> v; | |
338 | ASSERT_EQ (0, v.length ()); | |
339 | v.safe_grow_cleared (50); | |
340 | ASSERT_EQ (50, v.length ()); | |
341 | ASSERT_EQ (0, v[0]); | |
342 | ASSERT_EQ (0, v[49]); | |
343 | } | |
344 | ||
345 | /* Verify that vec::pop works correctly. */ | |
346 | ||
347 | static void | |
348 | test_pop () | |
349 | { | |
350 | auto_vec <int> v; | |
351 | safe_push_range (v, 5, 20); | |
352 | ASSERT_EQ (15, v.length ()); | |
353 | ||
354 | int last = v.pop (); | |
355 | ASSERT_EQ (19, last); | |
356 | ASSERT_EQ (14, v.length ()); | |
357 | } | |
358 | ||
359 | /* Verify that vec::safe_insert works correctly. */ | |
360 | ||
361 | static void | |
362 | test_safe_insert () | |
363 | { | |
364 | auto_vec <int> v; | |
365 | safe_push_range (v, 0, 10); | |
366 | v.safe_insert (5, 42); | |
367 | ASSERT_EQ (4, v[4]); | |
368 | ASSERT_EQ (42, v[5]); | |
369 | ASSERT_EQ (5, v[6]); | |
370 | ASSERT_EQ (11, v.length ()); | |
371 | } | |
372 | ||
373 | /* Verify that vec::ordered_remove works correctly. */ | |
374 | ||
375 | static void | |
376 | test_ordered_remove () | |
377 | { | |
378 | auto_vec <int> v; | |
379 | safe_push_range (v, 0, 10); | |
380 | v.ordered_remove (5); | |
381 | ASSERT_EQ (4, v[4]); | |
382 | ASSERT_EQ (6, v[5]); | |
383 | ASSERT_EQ (9, v.length ()); | |
384 | } | |
385 | ||
620610fa | 386 | /* Verify that vec::ordered_remove_if works correctly. */ |
387 | ||
388 | static void | |
389 | test_ordered_remove_if (void) | |
390 | { | |
391 | auto_vec <int> v; | |
392 | safe_push_range (v, 0, 10); | |
393 | unsigned ix, ix2; | |
394 | int *elem_ptr; | |
395 | VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, | |
396 | *elem_ptr == 5 || *elem_ptr == 7); | |
397 | ASSERT_EQ (4, v[4]); | |
398 | ASSERT_EQ (6, v[5]); | |
399 | ASSERT_EQ (8, v[6]); | |
400 | ASSERT_EQ (8, v.length ()); | |
401 | ||
402 | v.truncate (0); | |
403 | safe_push_range (v, 0, 10); | |
404 | VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6, | |
405 | *elem_ptr == 5 || *elem_ptr == 7); | |
406 | ASSERT_EQ (4, v[4]); | |
407 | ASSERT_EQ (6, v[5]); | |
408 | ASSERT_EQ (7, v[6]); | |
409 | ASSERT_EQ (9, v.length ()); | |
410 | ||
411 | v.truncate (0); | |
412 | safe_push_range (v, 0, 10); | |
413 | VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 5, | |
414 | *elem_ptr == 5 || *elem_ptr == 7); | |
415 | VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10, | |
416 | *elem_ptr == 5 || *elem_ptr == 7); | |
417 | ASSERT_EQ (4, v[4]); | |
418 | ASSERT_EQ (5, v[5]); | |
419 | ASSERT_EQ (6, v[6]); | |
420 | ASSERT_EQ (10, v.length ()); | |
421 | ||
422 | v.truncate (0); | |
423 | safe_push_range (v, 0, 10); | |
424 | VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5); | |
425 | ASSERT_EQ (4, v[4]); | |
426 | ASSERT_EQ (6, v[5]); | |
427 | ASSERT_EQ (7, v[6]); | |
428 | ASSERT_EQ (9, v.length ()); | |
429 | } | |
430 | ||
99b4f3a2 | 431 | /* Verify that vec::unordered_remove works correctly. */ |
432 | ||
433 | static void | |
434 | test_unordered_remove () | |
435 | { | |
436 | auto_vec <int> v; | |
437 | safe_push_range (v, 0, 10); | |
438 | v.unordered_remove (5); | |
439 | ASSERT_EQ (9, v.length ()); | |
440 | } | |
441 | ||
442 | /* Verify that vec::block_remove works correctly. */ | |
443 | ||
444 | static void | |
445 | test_block_remove () | |
446 | { | |
447 | auto_vec <int> v; | |
448 | safe_push_range (v, 0, 10); | |
449 | v.block_remove (5, 3); | |
450 | ASSERT_EQ (3, v[3]); | |
451 | ASSERT_EQ (4, v[4]); | |
452 | ASSERT_EQ (8, v[5]); | |
453 | ASSERT_EQ (9, v[6]); | |
454 | ASSERT_EQ (7, v.length ()); | |
455 | } | |
456 | ||
457 | /* Comparator for use by test_qsort. */ | |
458 | ||
459 | static int | |
460 | reverse_cmp (const void *p_i, const void *p_j) | |
461 | { | |
462 | return *(const int *)p_j - *(const int *)p_i; | |
463 | } | |
464 | ||
465 | /* Verify that vec::qsort works correctly. */ | |
466 | ||
467 | static void | |
468 | test_qsort () | |
469 | { | |
470 | auto_vec <int> v; | |
471 | safe_push_range (v, 0, 10); | |
472 | v.qsort (reverse_cmp); | |
473 | ASSERT_EQ (9, v[0]); | |
474 | ASSERT_EQ (8, v[1]); | |
475 | ASSERT_EQ (1, v[8]); | |
476 | ASSERT_EQ (0, v[9]); | |
477 | ASSERT_EQ (10, v.length ()); | |
478 | } | |
479 | ||
e4323fde | 480 | /* Verify that vec::reverse works correctly. */ |
481 | ||
482 | static void | |
483 | test_reverse () | |
484 | { | |
485 | /* Reversing an empty vec ought to be a no-op. */ | |
486 | { | |
487 | auto_vec <int> v; | |
488 | ASSERT_EQ (0, v.length ()); | |
489 | v.reverse (); | |
490 | ASSERT_EQ (0, v.length ()); | |
491 | } | |
492 | ||
493 | /* Verify reversing a vec with even length. */ | |
494 | { | |
495 | auto_vec <int> v; | |
496 | safe_push_range (v, 0, 4); | |
497 | v.reverse (); | |
498 | ASSERT_EQ (3, v[0]); | |
499 | ASSERT_EQ (2, v[1]); | |
500 | ASSERT_EQ (1, v[2]); | |
501 | ASSERT_EQ (0, v[3]); | |
502 | ASSERT_EQ (4, v.length ()); | |
503 | } | |
504 | ||
505 | /* Verify reversing a vec with odd length. */ | |
506 | { | |
507 | auto_vec <int> v; | |
508 | safe_push_range (v, 0, 3); | |
509 | v.reverse (); | |
510 | ASSERT_EQ (2, v[0]); | |
511 | ASSERT_EQ (1, v[1]); | |
512 | ASSERT_EQ (0, v[2]); | |
513 | ASSERT_EQ (3, v.length ()); | |
514 | } | |
515 | } | |
516 | ||
99b4f3a2 | 517 | /* Run all of the selftests within this file. */ |
518 | ||
519 | void | |
520 | vec_c_tests () | |
521 | { | |
522 | test_quick_push (); | |
523 | test_safe_push (); | |
524 | test_truncate (); | |
525 | test_safe_grow_cleared (); | |
526 | test_pop (); | |
527 | test_safe_insert (); | |
528 | test_ordered_remove (); | |
620610fa | 529 | test_ordered_remove_if (); |
99b4f3a2 | 530 | test_unordered_remove (); |
531 | test_block_remove (); | |
532 | test_qsort (); | |
e4323fde | 533 | test_reverse (); |
99b4f3a2 | 534 | } |
535 | ||
536 | } // namespace selftest | |
537 | ||
538 | #endif /* #if CHECKING_P */ | |
539 | #endif /* #ifndef GENERATOR_FILE */ |