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