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