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> 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" 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. */ 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), m_element_size (0) {} 56 57 /* Constructor. */ 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) {} 63 64 /* Sum the usage with SECOND usage. */ 65 vec_usage 66 operator+ (const vec_usage &second) 67 { 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); 73 } 74 75 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */ 76 inline void 77 dump (mem_location *loc, mem_usage &total) const 78 { 79 char s[4096]; 80 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (), 81 loc->m_line, loc->m_function); 82 83 s[48] = '\0'; 84 85 fprintf (stderr, 86 "%-48s %10" PRIu64 PRsa (10) ":%4.1f%%" PRsa (9) "%10" PRIu64 87 ":%4.1f%%" PRsa (10) PRsa (10) "\n", 88 s, 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)); 95 } 96 97 /* Dump footer. */ 98 inline void 99 dump_footer () 100 { 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)); 104 } 105 106 /* Dump header with NAME. */ 107 static inline void 108 dump_header (const char *name) 109 { 110 fprintf (stderr, "%-48s %10s%11s%16s%10s%17s%11s\n", name, "sizeof(T)", 111 "Leak", "Peak", "Times", "Leak items", "Peak items"); 112 } 113 114 /* Current number of items allocated. */ 115 size_t m_items; 116 /* Peak value of number of allocated items. */ 117 size_t m_items_peak; 118 /* Size of element of the vector. */ 119 size_t m_element_size; 120 }; 121 122 /* Vector memory description. */ 123 static mem_alloc_description <vec_usage> vec_mem_desc; 124 125 /* Account the overhead. */ 126 127 void 128 vec_prefix::register_overhead (void *ptr, size_t elements, 129 size_t element_size MEM_STAT_DECL) 130 { 131 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false 132 FINAL_PASS_MEM_STAT); 133 vec_usage *usage 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; 139 } 140 141 /* Notice that the memory allocated for the vector has been freed. */ 142 143 void 144 vec_prefix::release_overhead (void *ptr, size_t size, size_t elements, 145 bool in_dtor MEM_STAT_DECL) 146 { 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, 151 in_dtor); 152 usage->m_items -= elements; 153 } 154 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. */ 157 158 unsigned 159 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired) 160 { 161 /* We must have run out of room. */ 162 gcc_assert (alloc < desired); 163 164 /* Exponential growth. */ 165 if (!alloc) 166 alloc = 4; 167 else if (alloc < 16) 168 /* Double when small. */ 169 alloc = alloc * 2; 170 else 171 /* Grow slower when large. */ 172 alloc = (alloc * 3 / 2); 173 174 /* If this is still too small, set it to the right size. */ 175 if (alloc < desired) 176 alloc = desired; 177 return alloc; 178 } 179 180 /* Dump per-site memory statistics. */ 181 182 void 183 dump_vec_loc_statistics (void) 184 { 185 vec_mem_desc.dump (VEC_ORIGIN); 186 } 187 188 #if CHECKING_P 189 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as 190 witness elements. */ 191 ATTRIBUTE_NORETURN ATTRIBUTE_COLD 192 static void 193 qsort_chk_error (const void *p1, const void *p2, const void *p3, 194 int (*cmp) (const void *, const void *)) 195 { 196 if (!p3) 197 { 198 int r1 = cmp (p1, p2), r2 = cmp (p2, p1); 199 error ("qsort comparator not anti-commutative: %d, %d", r1, r2); 200 } 201 else if (p1 == p2) 202 { 203 int r = cmp (p1, p3); 204 error ("qsort comparator non-negative on sorted output: %d", r); 205 } 206 else 207 { 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); 210 } 211 internal_error ("qsort checking failed"); 212 } 213 214 /* Verify anti-symmetry and transitivity for comparator CMP on sorted array 215 of N SIZE-sized elements pointed to by BASE. */ 216 void 217 qsort_chk (void *base, size_t n, size_t size, 218 int (*cmp)(const void *, const void *)) 219 { 220 #if 0 221 #define LIM(n) (n) 222 #else 223 /* Limit overall time complexity to O(n log n). */ 224 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) 225 #endif 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) 230 size_t i1, i2, i, j; 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) 234 { 235 /* Position i2 one past last element that compares equal to i1'th. */ 236 for (i2 = i1 + 1; i2 < n; i2++) 237 if (CMP (i1, i2)) 238 break; 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++) 245 if (CMP (i, j)) 246 return ERR3 (i, i1, j); 247 else if (CMP (j, i)) 248 return ERR2 (i, 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++) 253 if (CMP (i, j) >= 0) 254 return ERR3 (i, i1, j); 255 else if (CMP (j, i) <= 0) 256 return ERR2 (i, j); 257 } 258 #undef ERR3 259 #undef ERR2 260 #undef CMP 261 #undef ELT 262 #undef LIM 263 } 264 #endif /* #if CHECKING_P */ 265 266 #ifndef GENERATOR_FILE 267 #if CHECKING_P 268 269 namespace selftest { 270 271 /* Selftests. */ 272 273 /* Call V.safe_push for all ints from START up to, but not including LIMIT. 274 Helper function for selftests. */ 275 276 static void 277 safe_push_range (vec <int>&v, int start, int limit) 278 { 279 for (int i = start; i < limit; i++) 280 v.safe_push (i); 281 } 282 283 /* Verify that vec::quick_push works correctly. */ 284 285 static void 286 test_quick_push () 287 { 288 auto_vec <int> v; 289 ASSERT_EQ (0, v.length ()); 290 v.reserve (3); 291 ASSERT_EQ (0, v.length ()); 292 ASSERT_TRUE (v.space (3)); 293 v.quick_push (5); 294 v.quick_push (6); 295 v.quick_push (7); 296 ASSERT_EQ (3, v.length ()); 297 ASSERT_EQ (5, v[0]); 298 ASSERT_EQ (6, v[1]); 299 ASSERT_EQ (7, v[2]); 300 } 301 302 /* Verify that vec::safe_push works correctly. */ 303 304 static void 305 test_safe_push () 306 { 307 auto_vec <int> v; 308 ASSERT_EQ (0, v.length ()); 309 v.safe_push (5); 310 v.safe_push (6); 311 v.safe_push (7); 312 ASSERT_EQ (3, v.length ()); 313 ASSERT_EQ (5, v[0]); 314 ASSERT_EQ (6, v[1]); 315 ASSERT_EQ (7, v[2]); 316 } 317 318 /* Verify that vec::truncate works correctly. */ 319 320 static void 321 test_truncate () 322 { 323 auto_vec <int> v; 324 ASSERT_EQ (0, v.length ()); 325 safe_push_range (v, 0, 10); 326 ASSERT_EQ (10, v.length ()); 327 328 v.truncate (5); 329 ASSERT_EQ (5, v.length ()); 330 } 331 332 /* Verify that vec::safe_grow_cleared works correctly. */ 333 334 static void 335 test_safe_grow_cleared () 336 { 337 auto_vec <int> v; 338 ASSERT_EQ (0, v.length ()); 339 v.safe_grow_cleared (50); 340 ASSERT_EQ (50, v.length ()); 341 ASSERT_EQ (0, v[0]); 342 ASSERT_EQ (0, v[49]); 343 } 344 345 /* Verify that vec::pop works correctly. */ 346 347 static void 348 test_pop () 349 { 350 auto_vec <int> v; 351 safe_push_range (v, 5, 20); 352 ASSERT_EQ (15, v.length ()); 353 354 int last = v.pop (); 355 ASSERT_EQ (19, last); 356 ASSERT_EQ (14, v.length ()); 357 } 358 359 /* Verify that vec::safe_insert works correctly. */ 360 361 static void 362 test_safe_insert () 363 { 364 auto_vec <int> v; 365 safe_push_range (v, 0, 10); 366 v.safe_insert (5, 42); 367 ASSERT_EQ (4, v[4]); 368 ASSERT_EQ (42, v[5]); 369 ASSERT_EQ (5, v[6]); 370 ASSERT_EQ (11, v.length ()); 371 } 372 373 /* Verify that vec::ordered_remove works correctly. */ 374 375 static void 376 test_ordered_remove () 377 { 378 auto_vec <int> v; 379 safe_push_range (v, 0, 10); 380 v.ordered_remove (5); 381 ASSERT_EQ (4, v[4]); 382 ASSERT_EQ (6, v[5]); 383 ASSERT_EQ (9, v.length ()); 384 } 385 386 /* Verify that vec::ordered_remove_if works correctly. */ 387 388 static void 389 test_ordered_remove_if (void) 390 { 391 auto_vec <int> v; 392 safe_push_range (v, 0, 10); 393 unsigned ix, ix2; 394 int *elem_ptr; 395 VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, 396 *elem_ptr == 5 || *elem_ptr == 7); 397 ASSERT_EQ (4, v[4]); 398 ASSERT_EQ (6, v[5]); 399 ASSERT_EQ (8, v[6]); 400 ASSERT_EQ (8, v.length ()); 401 402 v.truncate (0); 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); 406 ASSERT_EQ (4, v[4]); 407 ASSERT_EQ (6, v[5]); 408 ASSERT_EQ (7, v[6]); 409 ASSERT_EQ (9, v.length ()); 410 411 v.truncate (0); 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); 417 ASSERT_EQ (4, v[4]); 418 ASSERT_EQ (5, v[5]); 419 ASSERT_EQ (6, v[6]); 420 ASSERT_EQ (10, v.length ()); 421 422 v.truncate (0); 423 safe_push_range (v, 0, 10); 424 VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5); 425 ASSERT_EQ (4, v[4]); 426 ASSERT_EQ (6, v[5]); 427 ASSERT_EQ (7, v[6]); 428 ASSERT_EQ (9, v.length ()); 429 } 430 431 /* Verify that vec::unordered_remove works correctly. */ 432 433 static void 434 test_unordered_remove () 435 { 436 auto_vec <int> v; 437 safe_push_range (v, 0, 10); 438 v.unordered_remove (5); 439 ASSERT_EQ (9, v.length ()); 440 } 441 442 /* Verify that vec::block_remove works correctly. */ 443 444 static void 445 test_block_remove () 446 { 447 auto_vec <int> v; 448 safe_push_range (v, 0, 10); 449 v.block_remove (5, 3); 450 ASSERT_EQ (3, v[3]); 451 ASSERT_EQ (4, v[4]); 452 ASSERT_EQ (8, v[5]); 453 ASSERT_EQ (9, v[6]); 454 ASSERT_EQ (7, v.length ()); 455 } 456 457 /* Comparator for use by test_qsort. */ 458 459 static int 460 reverse_cmp (const void *p_i, const void *p_j) 461 { 462 return *(const int *)p_j - *(const int *)p_i; 463 } 464 465 /* Verify that vec::qsort works correctly. */ 466 467 static void 468 test_qsort () 469 { 470 auto_vec <int> v; 471 safe_push_range (v, 0, 10); 472 v.qsort (reverse_cmp); 473 ASSERT_EQ (9, v[0]); 474 ASSERT_EQ (8, v[1]); 475 ASSERT_EQ (1, v[8]); 476 ASSERT_EQ (0, v[9]); 477 ASSERT_EQ (10, v.length ()); 478 } 479 480 /* Verify that vec::reverse works correctly. */ 481 482 static void 483 test_reverse () 484 { 485 /* Reversing an empty vec ought to be a no-op. */ 486 { 487 auto_vec <int> v; 488 ASSERT_EQ (0, v.length ()); 489 v.reverse (); 490 ASSERT_EQ (0, v.length ()); 491 } 492 493 /* Verify reversing a vec with even length. */ 494 { 495 auto_vec <int> v; 496 safe_push_range (v, 0, 4); 497 v.reverse (); 498 ASSERT_EQ (3, v[0]); 499 ASSERT_EQ (2, v[1]); 500 ASSERT_EQ (1, v[2]); 501 ASSERT_EQ (0, v[3]); 502 ASSERT_EQ (4, v.length ()); 503 } 504 505 /* Verify reversing a vec with odd length. */ 506 { 507 auto_vec <int> v; 508 safe_push_range (v, 0, 3); 509 v.reverse (); 510 ASSERT_EQ (2, v[0]); 511 ASSERT_EQ (1, v[1]); 512 ASSERT_EQ (0, v[2]); 513 ASSERT_EQ (3, v.length ()); 514 } 515 } 516 517 /* Run all of the selftests within this file. */ 518 519 void 520 vec_c_tests () 521 { 522 test_quick_push (); 523 test_safe_push (); 524 test_truncate (); 525 test_safe_grow_cleared (); 526 test_pop (); 527 test_safe_insert (); 528 test_ordered_remove (); 529 test_ordered_remove_if (); 530 test_unordered_remove (); 531 test_block_remove (); 532 test_qsort (); 533 test_reverse (); 534 } 535 536 } // namespace selftest 537 538 #endif /* #if CHECKING_P */ 539 #endif /* #ifndef GENERATOR_FILE */ 540