1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2018 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
));
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
));
108 /* Dump header with NAME. */
110 dump_header (const char *name
)
112 fprintf (stderr
, "%-48s %10s%11s%16s%10s%17s%11s\n", name
, "sizeof(T)",
113 "Leak", "Peak", "Times", "Leak items", "Peak items");
117 /* Current number of items allocated. */
119 /* Peak value of number of allocated items. */
121 /* Size of element of the vector. */
122 size_t m_element_size
;
125 /* Vector memory description. */
126 static mem_alloc_description
<vec_usage
> vec_mem_desc
;
128 /* Account the overhead. */
131 vec_prefix::register_overhead (void *ptr
, size_t elements
,
132 size_t element_size MEM_STAT_DECL
)
134 vec_mem_desc
.register_descriptor (ptr
, VEC_ORIGIN
, false
135 FINAL_PASS_MEM_STAT
);
137 = vec_mem_desc
.register_instance_overhead (elements
* element_size
, ptr
);
138 usage
->m_element_size
= element_size
;
139 usage
->m_items
+= elements
;
140 if (usage
->m_items_peak
< usage
->m_items
)
141 usage
->m_items_peak
= usage
->m_items
;
144 /* Notice that the memory allocated for the vector has been freed. */
147 vec_prefix::release_overhead (void *ptr
, size_t size
, size_t elements
,
148 bool in_dtor MEM_STAT_DECL
)
150 if (!vec_mem_desc
.contains_descriptor_for_instance (ptr
))
151 vec_mem_desc
.register_descriptor (ptr
, VEC_ORIGIN
,
152 false FINAL_PASS_MEM_STAT
);
153 vec_usage
*usage
= vec_mem_desc
.release_instance_overhead (ptr
, size
,
155 usage
->m_items
-= elements
;
158 /* Calculate the number of slots to reserve a vector, making sure that
159 it is of at least DESIRED size by growing ALLOC exponentially. */
162 vec_prefix::calculate_allocation_1 (unsigned alloc
, unsigned desired
)
164 /* We must have run out of room. */
165 gcc_assert (alloc
< desired
);
167 /* Exponential growth. */
171 /* Double when small. */
174 /* Grow slower when large. */
175 alloc
= (alloc
* 3 / 2);
177 /* If this is still too small, set it to the right size. */
183 /* Dump per-site memory statistics. */
186 dump_vec_loc_statistics (void)
188 vec_mem_desc
.dump (VEC_ORIGIN
);
192 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
194 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
196 qsort_chk_error (const void *p1
, const void *p2
, const void *p3
,
197 int (*cmp
) (const void *, const void *))
201 int r1
= cmp (p1
, p2
), r2
= cmp (p2
, p1
);
202 error ("qsort comparator not anti-commutative: %d, %d", r1
, r2
);
206 int r
= cmp (p1
, p3
);
207 error ("qsort comparator non-negative on sorted output: %d", r
);
211 int r1
= cmp (p1
, p2
), r2
= cmp (p2
, p3
), r3
= cmp (p1
, p3
);
212 error ("qsort comparator not transitive: %d, %d, %d", r1
, r2
, r3
);
214 internal_error ("qsort checking failed");
217 /* Verify anti-symmetry and transitivity for comparator CMP on sorted array
218 of N SIZE-sized elements pointed to by BASE. */
220 qsort_chk (void *base
, size_t n
, size_t size
,
221 int (*cmp
)(const void *, const void *))
226 /* Limit overall time complexity to O(n log n). */
227 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
229 #define ELT(i) ((const char *) base + (i) * size)
230 #define CMP(i, j) cmp (ELT (i), ELT (j))
231 #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
232 #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
234 /* This outer loop iterates over maximum spans [i1, i2) such that
235 elements within each span compare equal to each other. */
236 for (i1
= 0; i1
< n
; i1
= i2
)
238 /* Position i2 one past last element that compares equal to i1'th. */
239 for (i2
= i1
+ 1; i2
< n
; i2
++)
242 else if (CMP (i2
, i1
))
243 return ERR2 (i1
, i2
);
244 size_t lim1
= LIM (i2
- i1
), lim2
= LIM (n
- i2
);
245 /* Verify that other pairs within current span compare equal. */
246 for (i
= i1
+ 1; i
+ 1 < i2
; i
++)
247 for (j
= i
+ 1; j
< i1
+ lim1
; j
++)
249 return ERR3 (i
, i1
, j
);
252 /* Verify that elements within this span compare less than
253 elements beyond the span. */
254 for (i
= i1
; i
< i2
; i
++)
255 for (j
= i2
; j
< i2
+ lim2
; j
++)
257 return ERR3 (i
, i1
, j
);
258 else if (CMP (j
, i
) <= 0)
267 #endif /* #if CHECKING_P */
269 #ifndef GENERATOR_FILE
276 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
277 Helper function for selftests. */
280 safe_push_range (vec
<int>&v
, int start
, int limit
)
282 for (int i
= start
; i
< limit
; i
++)
286 /* Verify that vec::quick_push works correctly. */
292 ASSERT_EQ (0, v
.length ());
294 ASSERT_EQ (0, v
.length ());
295 ASSERT_TRUE (v
.space (3));
299 ASSERT_EQ (3, v
.length ());
305 /* Verify that vec::safe_push works correctly. */
311 ASSERT_EQ (0, v
.length ());
315 ASSERT_EQ (3, v
.length ());
321 /* Verify that vec::truncate works correctly. */
327 ASSERT_EQ (0, v
.length ());
328 safe_push_range (v
, 0, 10);
329 ASSERT_EQ (10, v
.length ());
332 ASSERT_EQ (5, v
.length ());
335 /* Verify that vec::safe_grow_cleared works correctly. */
338 test_safe_grow_cleared ()
341 ASSERT_EQ (0, v
.length ());
342 v
.safe_grow_cleared (50);
343 ASSERT_EQ (50, v
.length ());
345 ASSERT_EQ (0, v
[49]);
348 /* Verify that vec::pop works correctly. */
354 safe_push_range (v
, 5, 20);
355 ASSERT_EQ (15, v
.length ());
358 ASSERT_EQ (19, last
);
359 ASSERT_EQ (14, v
.length ());
362 /* Verify that vec::safe_insert works correctly. */
368 safe_push_range (v
, 0, 10);
369 v
.safe_insert (5, 42);
371 ASSERT_EQ (42, v
[5]);
373 ASSERT_EQ (11, v
.length ());
376 /* Verify that vec::ordered_remove works correctly. */
379 test_ordered_remove ()
382 safe_push_range (v
, 0, 10);
383 v
.ordered_remove (5);
386 ASSERT_EQ (9, v
.length ());
389 /* Verify that vec::ordered_remove_if works correctly. */
392 test_ordered_remove_if (void)
395 safe_push_range (v
, 0, 10);
398 VEC_ORDERED_REMOVE_IF (v
, ix
, ix2
, elem_ptr
,
399 *elem_ptr
== 5 || *elem_ptr
== 7);
403 ASSERT_EQ (8, v
.length ());
406 safe_push_range (v
, 0, 10);
407 VEC_ORDERED_REMOVE_IF_FROM_TO (v
, ix
, ix2
, elem_ptr
, 0, 6,
408 *elem_ptr
== 5 || *elem_ptr
== 7);
412 ASSERT_EQ (9, v
.length ());
415 safe_push_range (v
, 0, 10);
416 VEC_ORDERED_REMOVE_IF_FROM_TO (v
, ix
, ix2
, elem_ptr
, 0, 5,
417 *elem_ptr
== 5 || *elem_ptr
== 7);
418 VEC_ORDERED_REMOVE_IF_FROM_TO (v
, ix
, ix2
, elem_ptr
, 8, 10,
419 *elem_ptr
== 5 || *elem_ptr
== 7);
423 ASSERT_EQ (10, v
.length ());
426 safe_push_range (v
, 0, 10);
427 VEC_ORDERED_REMOVE_IF (v
, ix
, ix2
, elem_ptr
, *elem_ptr
== 5);
431 ASSERT_EQ (9, v
.length ());
434 /* Verify that vec::unordered_remove works correctly. */
437 test_unordered_remove ()
440 safe_push_range (v
, 0, 10);
441 v
.unordered_remove (5);
442 ASSERT_EQ (9, v
.length ());
445 /* Verify that vec::block_remove works correctly. */
451 safe_push_range (v
, 0, 10);
452 v
.block_remove (5, 3);
457 ASSERT_EQ (7, v
.length ());
460 /* Comparator for use by test_qsort. */
463 reverse_cmp (const void *p_i
, const void *p_j
)
465 return *(const int *)p_j
- *(const int *)p_i
;
468 /* Verify that vec::qsort works correctly. */
474 safe_push_range (v
, 0, 10);
475 v
.qsort (reverse_cmp
);
480 ASSERT_EQ (10, v
.length ());
483 /* Verify that vec::reverse works correctly. */
488 /* Reversing an empty vec ought to be a no-op. */
491 ASSERT_EQ (0, v
.length ());
493 ASSERT_EQ (0, v
.length ());
496 /* Verify reversing a vec with even length. */
499 safe_push_range (v
, 0, 4);
505 ASSERT_EQ (4, v
.length ());
508 /* Verify reversing a vec with odd length. */
511 safe_push_range (v
, 0, 3);
516 ASSERT_EQ (3, v
.length ());
520 /* Run all of the selftests within this file. */
528 test_safe_grow_cleared ();
531 test_ordered_remove ();
532 test_ordered_remove_if ();
533 test_unordered_remove ();
534 test_block_remove ();
539 } // namespace selftest
541 #endif /* #if CHECKING_P */
542 #endif /* #ifndef GENERATOR_FILE */