gcc/vec.c

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