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