gcc/vec.c

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