1/* Vector API for GNU compiler.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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. */
49vnull vNULL;
50
51/* Vector memory usage. */
52struct vec_usage: public mem_usage
53{
54 /* Default constructor. */
55 vec_usage (): m_items (0), m_items_peak (0) {}
56
57 /* Constructor. */
58 vec_usage (size_t allocated, size_t times, size_t peak,
59 size_t items, size_t items_peak)
60 : mem_usage (allocated, times, peak),
61 m_items (items), m_items_peak (items_peak) {}
62
63 /* Comparison operator. */
64 inline bool
65 operator< (const vec_usage &second) const
66 {
67 return (m_allocated == second.m_allocated ?
68 (m_peak == second.m_peak ? m_times < second.m_times
69 : m_peak < second.m_peak) : m_allocated < second.m_allocated);
70 }
71
72 /* Sum the usage with SECOND usage. */
73 vec_usage
74 operator+ (const vec_usage &second)
75 {
76 return vec_usage (m_allocated + second.m_allocated,
77 m_times + second.m_times,
78 m_peak + second.m_peak,
79 m_items + second.m_items,
80 m_items_peak + second.m_items_peak);
81 }
82
83 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
84 inline void
85 dump (mem_location *loc, mem_usage &total) const
86 {
87 char s[4096];
88 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
89 loc->m_line, loc->m_function);
90
91 s[48] = '\0';
92
93 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s,
94 (long)m_allocated, m_allocated * 100.0 / total.m_allocated,
95 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times,
96 (long)m_items, (long)m_items_peak);
97 }
98
99 /* Dump footer. */
100 inline void
101 dump_footer ()
102 {
103 print_dash_line ();
104 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated,
105 (long)m_times, (long)m_items);
106 print_dash_line ();
107 }
108
109 /* Dump header with NAME. */
110 static inline void
111 dump_header (const char *name)
112 {
113 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak",
114 "Times", "Leak items", "Peak items");
115 print_dash_line ();
116 }
117
118 /* Compare wrapper used by qsort method. */
119 static int
120 compare (const void *first, const void *second)
121 {
122 typedef std::pair<mem_location *, vec_usage *> mem_pair_t;
123
124 const mem_pair_t f = *(const mem_pair_t *)first;
125 const mem_pair_t s = *(const mem_pair_t *)second;
126
127 return (*f.second) < (*s.second);
128 }
129
130 /* Current number of items allocated. */
131 size_t m_items;
132 /* Peak value of number of allocated items. */
133 size_t m_items_peak;
134};
135
136/* Vector memory description. */
137static mem_alloc_description <vec_usage> vec_mem_desc;
138
139/* Account the overhead. */
140
141void
142vec_prefix::register_overhead (void *ptr, size_t size, size_t elements
143 MEM_STAT_DECL)
144{
145 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
146 FINAL_PASS_MEM_STAT);
147 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr);
148 usage->m_items += elements;
149 if (usage->m_items_peak < usage->m_items)
150 usage->m_items_peak = usage->m_items;
151}
152
153/* Notice that the memory allocated for the vector has been freed. */
154
155void
156vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor
157 MEM_STAT_DECL)
158{
159 if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
160 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
161 false FINAL_PASS_MEM_STAT);
162 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor);
163}
164
165
166/* Calculate the number of slots to reserve a vector, making sure that
167 it is of at least DESIRED size by growing ALLOC exponentially. */
168
169unsigned
170vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
171{
172 /* We must have run out of room. */
173 gcc_assert (alloc < desired);
174
175 /* Exponential growth. */
176 if (!alloc)
177 alloc = 4;
178 else if (alloc < 16)
179 /* Double when small. */
180 alloc = alloc * 2;
181 else
182 /* Grow slower when large. */
183 alloc = (alloc * 3 / 2);
184
185 /* If this is still too small, set it to the right size. */
186 if (alloc < desired)
187 alloc = desired;
188 return alloc;
189}
190
191/* Dump per-site memory statistics. */
192
193void
194dump_vec_loc_statistics (void)
195{
196 vec_mem_desc.dump (VEC_ORIGIN);
197}
198
199#if CHECKING_P
200/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
201 witness elements. */
202ATTRIBUTE_NORETURN ATTRIBUTE_COLD
203static void
204qsort_chk_error (const void *p1, const void *p2, const void *p3,
205 int (*cmp) (const void *, const void *))
206{
207 if (!p3)
208 {
209 int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
210 error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
211 }
212 else if (p1 == p2)
213 {
214 int r = cmp (p1, p3);
215 error ("qsort comparator non-negative on sorted output: %d", r);
216 }
217 else
218 {
219 int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
220 error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
221 }
222 internal_error ("qsort checking failed");
223}
224
225/* Wrapper around qsort with checking that CMP is consistent on given input.
226
227 Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
228 comparators to libc qsort can result in undefined behavior. Therefore we
229 should ideally perform consistency checks prior to invoking qsort, but in
230 order to do that optimally we'd need to sort the array ourselves beforehand
231 with a sorting routine known to be "safe". Instead, we expect that most
232 implementations in practice will still produce some permutation of input
233 array even for invalid comparators, which enables us to perform checks on
234 the output array. */
235void
236qsort_chk (void *base, size_t n, size_t size,
237 int (*cmp)(const void *, const void *))
238{
239 (qsort) (base, n, size, cmp);
240#if 0
241#define LIM(n) (n)
242#else
243 /* Limit overall time complexity to O(n log n). */
244#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
245#endif
246#define ELT(i) ((const char *) base + (i) * size)
247#define CMP(i, j) cmp (ELT (i), ELT (j))
248#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
249#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
250 size_t i1, i2, i, j;
251 /* This outer loop iterates over maximum spans [i1, i2) such that
252 elements within each span compare equal to each other. */
253 for (i1 = 0; i1 < n; i1 = i2)
254 {
255 /* Position i2 one past last element that compares equal to i1'th. */
256 for (i2 = i1 + 1; i2 < n; i2++)
257 if (CMP (i1, i2))
258 break;
259 else if (CMP (i2, i1))
260 return ERR2 (i1, i2);
261 size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
262 /* Verify that other pairs within current span compare equal. */
263 for (i = i1 + 1; i + 1 < i2; i++)
264 for (j = i + 1; j < i1 + lim1; j++)
265 if (CMP (i, j))
266 return ERR3 (i, i1, j);
267 else if (CMP (j, i))
268 return ERR2 (i, j);
269 /* Verify that elements within this span compare less than
270 elements beyond the span. */
271 for (i = i1; i < i2; i++)
272 for (j = i2; j < i2 + lim2; j++)
273 if (CMP (i, j) >= 0)
274 return ERR3 (i, i1, j);
275 else if (CMP (j, i) <= 0)
276 return ERR2 (i, j);
277 }
278#undef ERR3
279#undef ERR2
280#undef CMP
281#undef ELT
282#undef LIM
283}
284#endif /* #if CHECKING_P */
285
286#ifndef GENERATOR_FILE
287#if CHECKING_P
288
289namespace selftest {
290
291/* Selftests. */
292
293/* Call V.safe_push for all ints from START up to, but not including LIMIT.
294 Helper function for selftests. */
295
296static void
297safe_push_range (vec <int>&v, int start, int limit)
298{
299 for (int i = start; i < limit; i++)
300 v.safe_push (i);
301}
302
303/* Verify that vec::quick_push works correctly. */
304
305static void
306test_quick_push ()
307{
308 auto_vec <int> v;
309 ASSERT_EQ (0, v.length ());
310 v.reserve (3);
311 ASSERT_EQ (0, v.length ());
312 ASSERT_TRUE (v.space (3));
313 v.quick_push (5);
314 v.quick_push (6);
315 v.quick_push (7);
316 ASSERT_EQ (3, v.length ());
317 ASSERT_EQ (5, v[0]);
318 ASSERT_EQ (6, v[1]);
319 ASSERT_EQ (7, v[2]);
320}
321
322/* Verify that vec::safe_push works correctly. */
323
324static void
325test_safe_push ()
326{
327 auto_vec <int> v;
328 ASSERT_EQ (0, v.length ());
329 v.safe_push (5);
330 v.safe_push (6);
331 v.safe_push (7);
332 ASSERT_EQ (3, v.length ());
333 ASSERT_EQ (5, v[0]);
334 ASSERT_EQ (6, v[1]);
335 ASSERT_EQ (7, v[2]);
336}
337
338/* Verify that vec::truncate works correctly. */
339
340static void
341test_truncate ()
342{
343 auto_vec <int> v;
344 ASSERT_EQ (0, v.length ());
345 safe_push_range (v, 0, 10);
346 ASSERT_EQ (10, v.length ());
347
348 v.truncate (5);
349 ASSERT_EQ (5, v.length ());
350}
351
352/* Verify that vec::safe_grow_cleared works correctly. */
353
354static void
355test_safe_grow_cleared ()
356{
357 auto_vec <int> v;
358 ASSERT_EQ (0, v.length ());
359 v.safe_grow_cleared (50);
360 ASSERT_EQ (50, v.length ());
361 ASSERT_EQ (0, v[0]);
362 ASSERT_EQ (0, v[49]);
363}
364
365/* Verify that vec::pop works correctly. */
366
367static void
368test_pop ()
369{
370 auto_vec <int> v;
371 safe_push_range (v, 5, 20);
372 ASSERT_EQ (15, v.length ());
373
374 int last = v.pop ();
375 ASSERT_EQ (19, last);
376 ASSERT_EQ (14, v.length ());
377}
378
379/* Verify that vec::safe_insert works correctly. */
380
381static void
382test_safe_insert ()
383{
384 auto_vec <int> v;
385 safe_push_range (v, 0, 10);
386 v.safe_insert (5, 42);
387 ASSERT_EQ (4, v[4]);
388 ASSERT_EQ (42, v[5]);
389 ASSERT_EQ (5, v[6]);
390 ASSERT_EQ (11, v.length ());
391}
392
393/* Verify that vec::ordered_remove works correctly. */
394
395static void
396test_ordered_remove ()
397{
398 auto_vec <int> v;
399 safe_push_range (v, 0, 10);
400 v.ordered_remove (5);
401 ASSERT_EQ (4, v[4]);
402 ASSERT_EQ (6, v[5]);
403 ASSERT_EQ (9, v.length ());
404}
405
406/* Verify that vec::unordered_remove works correctly. */
407
408static void
409test_unordered_remove ()
410{
411 auto_vec <int> v;
412 safe_push_range (v, 0, 10);
413 v.unordered_remove (5);
414 ASSERT_EQ (9, v.length ());
415}
416
417/* Verify that vec::block_remove works correctly. */
418
419static void
420test_block_remove ()
421{
422 auto_vec <int> v;
423 safe_push_range (v, 0, 10);
424 v.block_remove (5, 3);
425 ASSERT_EQ (3, v[3]);
426 ASSERT_EQ (4, v[4]);
427 ASSERT_EQ (8, v[5]);
428 ASSERT_EQ (9, v[6]);
429 ASSERT_EQ (7, v.length ());
430}
431
432/* Comparator for use by test_qsort. */
433
434static int
435reverse_cmp (const void *p_i, const void *p_j)
436{
437 return *(const int *)p_j - *(const int *)p_i;
438}
439
440/* Verify that vec::qsort works correctly. */
441
442static void
443test_qsort ()
444{
445 auto_vec <int> v;
446 safe_push_range (v, 0, 10);
447 v.qsort (reverse_cmp);
448 ASSERT_EQ (9, v[0]);
449 ASSERT_EQ (8, v[1]);
450 ASSERT_EQ (1, v[8]);
451 ASSERT_EQ (0, v[9]);
452 ASSERT_EQ (10, v.length ());
453}
454
455/* Run all of the selftests within this file. */
456
457void
458vec_c_tests ()
459{
460 test_quick_push ();
461 test_safe_push ();
462 test_truncate ();
463 test_safe_grow_cleared ();
464 test_pop ();
465 test_safe_insert ();
466 test_ordered_remove ();
467 test_unordered_remove ();
468 test_block_remove ();
469 test_qsort ();
470}
471
472} // namespace selftest
473
474#endif /* #if CHECKING_P */
475#endif /* #ifndef GENERATOR_FILE */
476