1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2019 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.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"
32 #include "hash-table.h"
38 #include "diagnostic-core.h"
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.
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. */
51 /* Vector memory usage. */
52 struct vec_usage
: public mem_usage
54 /* Default constructor. */
55 vec_usage (): m_items (0), m_items_peak (0), m_element_size (0) {}
58 vec_usage (size_t allocated
, size_t times
, size_t peak
,
59 size_t items
, size_t items_peak
, size_t element_size
)
60 : mem_usage (allocated
, times
, peak
),
61 m_items (items
), m_items_peak (items_peak
),
62 m_element_size (element_size
) {}
64 /* Sum the usage with SECOND usage. */
66 operator+ (const vec_usage
&second
)
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
,
72 m_items_peak
+ second
.m_items_peak
, 0);
75 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
77 dump (mem_location
*loc
, mem_usage
&total
) const
80 sprintf (s
, "%s:%i (%s)", loc
->get_trimmed_filename (),
81 loc
->m_line
, loc
->m_function
);
86 "%-48s %10" PRIu64
PRsa (10) ":%4.1f%%" PRsa (9) "%10" PRIu64
87 ":%4.1f%%" PRsa (10) PRsa (10) "\n",
89 (uint64_t)m_element_size
,
90 SIZE_AMOUNT (m_allocated
),
91 m_allocated
* 100.0 / total
.m_allocated
,
92 SIZE_AMOUNT (m_peak
), (uint64_t)m_times
,
93 m_times
* 100.0 / total
.m_times
,
94 SIZE_AMOUNT (m_items
), SIZE_AMOUNT (m_items_peak
));
101 fprintf (stderr
, "%s" PRsa (64) PRsa (25) PRsa (16) "\n",
102 "Total", SIZE_AMOUNT (m_allocated
),
103 SIZE_AMOUNT (m_times
), SIZE_AMOUNT (m_items
));
106 /* Dump header with NAME. */
108 dump_header (const char *name
)
110 fprintf (stderr
, "%-48s %10s%11s%16s%10s%17s%11s\n", name
, "sizeof(T)",
111 "Leak", "Peak", "Times", "Leak items", "Peak items");
114 /* Current number of items allocated. */
116 /* Peak value of number of allocated items. */
118 /* Size of element of the vector. */
119 size_t m_element_size
;
122 /* Vector memory description. */
123 static mem_alloc_description
<vec_usage
> vec_mem_desc
;
125 /* Account the overhead. */
128 vec_prefix::register_overhead (void *ptr
, size_t elements
,
129 size_t element_size MEM_STAT_DECL
)
131 vec_mem_desc
.register_descriptor (ptr
, VEC_ORIGIN
, false
132 FINAL_PASS_MEM_STAT
);
134 = vec_mem_desc
.register_instance_overhead (elements
* element_size
, ptr
);
135 usage
->m_element_size
= element_size
;
136 usage
->m_items
+= elements
;
137 if (usage
->m_items_peak
< usage
->m_items
)
138 usage
->m_items_peak
= usage
->m_items
;
141 /* Notice that the memory allocated for the vector has been freed. */
144 vec_prefix::release_overhead (void *ptr
, size_t size
, size_t elements
,
145 bool in_dtor MEM_STAT_DECL
)
147 if (!vec_mem_desc
.contains_descriptor_for_instance (ptr
))
148 vec_mem_desc
.register_descriptor (ptr
, VEC_ORIGIN
,
149 false FINAL_PASS_MEM_STAT
);
150 vec_usage
*usage
= vec_mem_desc
.release_instance_overhead (ptr
, size
,
152 usage
->m_items
-= elements
;
155 /* Calculate the number of slots to reserve a vector, making sure that
156 it is of at least DESIRED size by growing ALLOC exponentially. */
159 vec_prefix::calculate_allocation_1 (unsigned alloc
, unsigned desired
)
161 /* We must have run out of room. */
162 gcc_assert (alloc
< desired
);
164 /* Exponential growth. */
168 /* Double when small. */
171 /* Grow slower when large. */
172 alloc
= (alloc
* 3 / 2);
174 /* If this is still too small, set it to the right size. */
180 /* Dump per-site memory statistics. */
183 dump_vec_loc_statistics (void)
185 vec_mem_desc
.dump (VEC_ORIGIN
);
189 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
191 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
193 qsort_chk_error (const void *p1
, const void *p2
, const void *p3
,
194 int (*cmp
) (const void *, const void *))
198 int r1
= cmp (p1
, p2
), r2
= cmp (p2
, p1
);
199 error ("qsort comparator not anti-commutative: %d, %d", r1
, r2
);
203 int r
= cmp (p1
, p3
);
204 error ("qsort comparator non-negative on sorted output: %d", r
);
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
);
211 internal_error ("qsort checking failed");
214 /* Verify anti-symmetry and transitivity for comparator CMP on sorted array
215 of N SIZE-sized elements pointed to by BASE. */
217 qsort_chk (void *base
, size_t n
, size_t size
,
218 int (*cmp
)(const void *, const void *))
223 /* Limit overall time complexity to O(n log n). */
224 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
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)
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
)
235 /* Position i2 one past last element that compares equal to i1'th. */
236 for (i2
= i1
+ 1; i2
< n
; i2
++)
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
++)
246 return ERR3 (i
, i1
, 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
++)
254 return ERR3 (i
, i1
, j
);
255 else if (CMP (j
, i
) <= 0)
264 #endif /* #if CHECKING_P */
266 #ifndef GENERATOR_FILE
273 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
274 Helper function for selftests. */
277 safe_push_range (vec
<int>&v
, int start
, int limit
)
279 for (int i
= start
; i
< limit
; i
++)
283 /* Verify that vec::quick_push works correctly. */
289 ASSERT_EQ (0, v
.length ());
291 ASSERT_EQ (0, v
.length ());
292 ASSERT_TRUE (v
.space (3));
296 ASSERT_EQ (3, v
.length ());
302 /* Verify that vec::safe_push works correctly. */
308 ASSERT_EQ (0, v
.length ());
312 ASSERT_EQ (3, v
.length ());
318 /* Verify that vec::truncate works correctly. */
324 ASSERT_EQ (0, v
.length ());
325 safe_push_range (v
, 0, 10);
326 ASSERT_EQ (10, v
.length ());
329 ASSERT_EQ (5, v
.length ());
332 /* Verify that vec::safe_grow_cleared works correctly. */
335 test_safe_grow_cleared ()
338 ASSERT_EQ (0, v
.length ());
339 v
.safe_grow_cleared (50);
340 ASSERT_EQ (50, v
.length ());
342 ASSERT_EQ (0, v
[49]);
345 /* Verify that vec::pop works correctly. */
351 safe_push_range (v
, 5, 20);
352 ASSERT_EQ (15, v
.length ());
355 ASSERT_EQ (19, last
);
356 ASSERT_EQ (14, v
.length ());
359 /* Verify that vec::safe_insert works correctly. */
365 safe_push_range (v
, 0, 10);
366 v
.safe_insert (5, 42);
368 ASSERT_EQ (42, v
[5]);
370 ASSERT_EQ (11, v
.length ());
373 /* Verify that vec::ordered_remove works correctly. */
376 test_ordered_remove ()
379 safe_push_range (v
, 0, 10);
380 v
.ordered_remove (5);
383 ASSERT_EQ (9, v
.length ());
386 /* Verify that vec::ordered_remove_if works correctly. */
389 test_ordered_remove_if (void)
392 safe_push_range (v
, 0, 10);
395 VEC_ORDERED_REMOVE_IF (v
, ix
, ix2
, elem_ptr
,
396 *elem_ptr
== 5 || *elem_ptr
== 7);
400 ASSERT_EQ (8, v
.length ());
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);
409 ASSERT_EQ (9, v
.length ());
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);
420 ASSERT_EQ (10, v
.length ());
423 safe_push_range (v
, 0, 10);
424 VEC_ORDERED_REMOVE_IF (v
, ix
, ix2
, elem_ptr
, *elem_ptr
== 5);
428 ASSERT_EQ (9, v
.length ());
431 /* Verify that vec::unordered_remove works correctly. */
434 test_unordered_remove ()
437 safe_push_range (v
, 0, 10);
438 v
.unordered_remove (5);
439 ASSERT_EQ (9, v
.length ());
442 /* Verify that vec::block_remove works correctly. */
448 safe_push_range (v
, 0, 10);
449 v
.block_remove (5, 3);
454 ASSERT_EQ (7, v
.length ());
457 /* Comparator for use by test_qsort. */
460 reverse_cmp (const void *p_i
, const void *p_j
)
462 return *(const int *)p_j
- *(const int *)p_i
;
465 /* Verify that vec::qsort works correctly. */
471 safe_push_range (v
, 0, 10);
472 v
.qsort (reverse_cmp
);
477 ASSERT_EQ (10, v
.length ());
480 /* Verify that vec::reverse works correctly. */
485 /* Reversing an empty vec ought to be a no-op. */
488 ASSERT_EQ (0, v
.length ());
490 ASSERT_EQ (0, v
.length ());
493 /* Verify reversing a vec with even length. */
496 safe_push_range (v
, 0, 4);
502 ASSERT_EQ (4, v
.length ());
505 /* Verify reversing a vec with odd length. */
508 safe_push_range (v
, 0, 3);
513 ASSERT_EQ (3, v
.length ());
517 /* Run all of the selftests within this file. */
525 test_safe_grow_cleared ();
528 test_ordered_remove ();
529 test_ordered_remove_if ();
530 test_unordered_remove ();
531 test_block_remove ();
536 } // namespace selftest
538 #endif /* #if CHECKING_P */
539 #endif /* #ifndef GENERATOR_FILE */