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