Daily bump.
[official-gcc.git] / gcc / vec.c
blobd612703184ba487ab8b617e21aa2b29e3e636a66
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>
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
11 version.
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.
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. */
24 #ifdef GENERATOR_FILE
25 #include "bconfig.h"
26 #else
27 #include "config.h"
28 #endif
30 #include "system.h"
31 #include "coretypes.h"
32 #include "hash-table.h"
33 #include "selftest.h"
35 /* vNULL is an empty type with a template cast operation that returns
36 a zero-initialized vec<T, A, L> instance. Use this when you want
37 to assign nil values to new vec instances or pass a nil vector as
38 a function call argument.
40 We use this technique because vec<T, A, L> must be PODs (they are
41 stored in unions and passed in vararg functions), this means that
42 they cannot have ctors/dtors. */
43 vnull vNULL;
45 /* Vector memory usage. */
46 struct vec_usage: public mem_usage
48 /* Default constructor. */
49 vec_usage (): m_items (0), m_items_peak (0) {}
51 /* Constructor. */
52 vec_usage (size_t allocated, size_t times, size_t peak,
53 size_t items, size_t items_peak)
54 : mem_usage (allocated, times, peak),
55 m_items (items), m_items_peak (items_peak) {}
57 /* Comparison operator. */
58 inline bool
59 operator< (const vec_usage &second) const
61 return (m_allocated == second.m_allocated ?
62 (m_peak == second.m_peak ? m_times < second.m_times
63 : m_peak < second.m_peak) : m_allocated < second.m_allocated);
66 /* Sum the usage with SECOND usage. */
67 vec_usage
68 operator+ (const vec_usage &second)
70 return vec_usage (m_allocated + second.m_allocated,
71 m_times + second.m_times,
72 m_peak + second.m_peak,
73 m_items + second.m_items,
74 m_items_peak + second.m_items_peak);
77 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
78 inline void
79 dump (mem_location *loc, mem_usage &total) const
81 char s[4096];
82 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
83 loc->m_line, loc->m_function);
85 s[48] = '\0';
87 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s,
88 (long)m_allocated, m_allocated * 100.0 / total.m_allocated,
89 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times,
90 (long)m_items, (long)m_items_peak);
93 /* Dump footer. */
94 inline void
95 dump_footer ()
97 print_dash_line ();
98 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated,
99 (long)m_times, (long)m_items);
100 print_dash_line ();
103 /* Dump header with NAME. */
104 static inline void
105 dump_header (const char *name)
107 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak",
108 "Times", "Leak items", "Peak items");
109 print_dash_line ();
112 /* Compare wrapper used by qsort method. */
113 static int
114 compare (const void *first, const void *second)
116 typedef std::pair<mem_location *, vec_usage *> mem_pair_t;
118 const mem_pair_t f = *(const mem_pair_t *)first;
119 const mem_pair_t s = *(const mem_pair_t *)second;
121 return (*f.second) < (*s.second);
124 /* Current number of items allocated. */
125 size_t m_items;
126 /* Peak value of number of allocated items. */
127 size_t m_items_peak;
130 /* Vector memory description. */
131 static mem_alloc_description <vec_usage> vec_mem_desc;
133 /* Account the overhead. */
135 void
136 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements
137 MEM_STAT_DECL)
139 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
140 FINAL_PASS_MEM_STAT);
141 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr);
142 usage->m_items += elements;
143 if (usage->m_items_peak < usage->m_items)
144 usage->m_items_peak = usage->m_items;
147 /* Notice that the memory allocated for the vector has been freed. */
149 void
150 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor
151 MEM_STAT_DECL)
153 if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
154 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
155 false FINAL_PASS_MEM_STAT);
156 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor);
160 /* Calculate the number of slots to reserve a vector, making sure that
161 it is of at least DESIRED size by growing ALLOC exponentially. */
163 unsigned
164 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
166 /* We must have run out of room. */
167 gcc_assert (alloc < desired);
169 /* Exponential growth. */
170 if (!alloc)
171 alloc = 4;
172 else if (alloc < 16)
173 /* Double when small. */
174 alloc = alloc * 2;
175 else
176 /* Grow slower when large. */
177 alloc = (alloc * 3 / 2);
179 /* If this is still too small, set it to the right size. */
180 if (alloc < desired)
181 alloc = desired;
182 return alloc;
185 /* Dump per-site memory statistics. */
187 void
188 dump_vec_loc_statistics (void)
190 vec_mem_desc.dump (VEC_ORIGIN);
193 #ifndef GENERATOR_FILE
194 #if CHECKING_P
196 namespace selftest {
198 /* Selftests. */
200 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
201 Helper function for selftests. */
203 static void
204 safe_push_range (vec <int>&v, int start, int limit)
206 for (int i = start; i < limit; i++)
207 v.safe_push (i);
210 /* Verify that vec::quick_push works correctly. */
212 static void
213 test_quick_push ()
215 auto_vec <int> v;
216 ASSERT_EQ (0, v.length ());
217 v.reserve (3);
218 ASSERT_EQ (0, v.length ());
219 ASSERT_TRUE (v.space (3));
220 v.quick_push (5);
221 v.quick_push (6);
222 v.quick_push (7);
223 ASSERT_EQ (3, v.length ());
224 ASSERT_EQ (5, v[0]);
225 ASSERT_EQ (6, v[1]);
226 ASSERT_EQ (7, v[2]);
229 /* Verify that vec::safe_push works correctly. */
231 static void
232 test_safe_push ()
234 auto_vec <int> v;
235 ASSERT_EQ (0, v.length ());
236 v.safe_push (5);
237 v.safe_push (6);
238 v.safe_push (7);
239 ASSERT_EQ (3, v.length ());
240 ASSERT_EQ (5, v[0]);
241 ASSERT_EQ (6, v[1]);
242 ASSERT_EQ (7, v[2]);
245 /* Verify that vec::truncate works correctly. */
247 static void
248 test_truncate ()
250 auto_vec <int> v;
251 ASSERT_EQ (0, v.length ());
252 safe_push_range (v, 0, 10);
253 ASSERT_EQ (10, v.length ());
255 v.truncate (5);
256 ASSERT_EQ (5, v.length ());
259 /* Verify that vec::safe_grow_cleared works correctly. */
261 static void
262 test_safe_grow_cleared ()
264 auto_vec <int> v;
265 ASSERT_EQ (0, v.length ());
266 v.safe_grow_cleared (50);
267 ASSERT_EQ (50, v.length ());
268 ASSERT_EQ (0, v[0]);
269 ASSERT_EQ (0, v[49]);
272 /* Verify that vec::pop works correctly. */
274 static void
275 test_pop ()
277 auto_vec <int> v;
278 safe_push_range (v, 5, 20);
279 ASSERT_EQ (15, v.length ());
281 int last = v.pop ();
282 ASSERT_EQ (19, last);
283 ASSERT_EQ (14, v.length ());
286 /* Verify that vec::safe_insert works correctly. */
288 static void
289 test_safe_insert ()
291 auto_vec <int> v;
292 safe_push_range (v, 0, 10);
293 v.safe_insert (5, 42);
294 ASSERT_EQ (4, v[4]);
295 ASSERT_EQ (42, v[5]);
296 ASSERT_EQ (5, v[6]);
297 ASSERT_EQ (11, v.length ());
300 /* Verify that vec::ordered_remove works correctly. */
302 static void
303 test_ordered_remove ()
305 auto_vec <int> v;
306 safe_push_range (v, 0, 10);
307 v.ordered_remove (5);
308 ASSERT_EQ (4, v[4]);
309 ASSERT_EQ (6, v[5]);
310 ASSERT_EQ (9, v.length ());
313 /* Verify that vec::unordered_remove works correctly. */
315 static void
316 test_unordered_remove ()
318 auto_vec <int> v;
319 safe_push_range (v, 0, 10);
320 v.unordered_remove (5);
321 ASSERT_EQ (9, v.length ());
324 /* Verify that vec::block_remove works correctly. */
326 static void
327 test_block_remove ()
329 auto_vec <int> v;
330 safe_push_range (v, 0, 10);
331 v.block_remove (5, 3);
332 ASSERT_EQ (3, v[3]);
333 ASSERT_EQ (4, v[4]);
334 ASSERT_EQ (8, v[5]);
335 ASSERT_EQ (9, v[6]);
336 ASSERT_EQ (7, v.length ());
339 /* Comparator for use by test_qsort. */
341 static int
342 reverse_cmp (const void *p_i, const void *p_j)
344 return *(const int *)p_j - *(const int *)p_i;
347 /* Verify that vec::qsort works correctly. */
349 static void
350 test_qsort ()
352 auto_vec <int> v;
353 safe_push_range (v, 0, 10);
354 v.qsort (reverse_cmp);
355 ASSERT_EQ (9, v[0]);
356 ASSERT_EQ (8, v[1]);
357 ASSERT_EQ (1, v[8]);
358 ASSERT_EQ (0, v[9]);
359 ASSERT_EQ (10, v.length ());
362 /* Run all of the selftests within this file. */
364 void
365 vec_c_tests ()
367 test_quick_push ();
368 test_safe_push ();
369 test_truncate ();
370 test_safe_grow_cleared ();
371 test_pop ();
372 test_safe_insert ();
373 test_ordered_remove ();
374 test_unordered_remove ();
375 test_block_remove ();
376 test_qsort ();
379 } // namespace selftest
381 #endif /* #if CHECKING_P */
382 #endif /* #ifndef GENERATOR_FILE */