gcc/vec.c

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