gcc/vec.c

   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 */