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 /* Verify anti-symmetry and transitivity for comparator CMP on sorted array
 205    of N SIZE-sized elements pointed to by BASE.  */
 206 void
 207 qsort_chk (void *base, size_t n, size_t size,
 208            int (*cmp)(const void *, const void *))
 209 {
 210 #if 0
 211 #define LIM(n) (n)
 212 #else
 213   /* Limit overall time complexity to O(n log n).  */
 214 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
 215 #endif
 216 #define ELT(i) ((const char *) base + (i) * size)
 217 #define CMP(i, j) cmp (ELT (i), ELT (j))
 218 #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
 219 #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
 220   size_t i1, i2, i, j;
 221   /* This outer loop iterates over maximum spans [i1, i2) such that
 222      elements within each span compare equal to each other.  */
 223   for (i1 = 0; i1 < n; i1 = i2)
 224     {
 225       /* Position i2 one past last element that compares equal to i1'th.  */
 226       for (i2 = i1 + 1; i2 < n; i2++)
 227         if (CMP (i1, i2))
 228           break;
 229         else if (CMP (i2, i1))
 230           return ERR2 (i1, i2);
 231       size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
 232       /* Verify that other pairs within current span compare equal.  */
 233       for (i = i1 + 1; i + 1 < i2; i++)
 234         for (j = i + 1; j < i1 + lim1; j++)
 235           if (CMP (i, j))
 236             return ERR3 (i, i1, j);
 237           else if (CMP (j, i))
 238             return ERR2 (i, j);
 239       /* Verify that elements within this span compare less than
 240          elements beyond the span.  */
 241       for (i = i1; i < i2; i++)
 242         for (j = i2; j < i2 + lim2; j++)
 243           if (CMP (i, j) >= 0)
 244             return ERR3 (i, i1, j);
 245           else if (CMP (j, i) <= 0)
 246             return ERR2 (i, j);
 247     }
 248 #undef ERR3
 249 #undef ERR2
 250 #undef CMP
 251 #undef ELT
 252 #undef LIM
 253 }
 254 #endif /* #if CHECKING_P */
 255
 256 #ifndef GENERATOR_FILE
 257 #if CHECKING_P
 258
 259 namespace selftest {
 260
 261 /* Selftests.  */
 262
 263 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
 264    Helper function for selftests.  */
 265
 266 static void
 267 safe_push_range (vec <int>&v, int start, int limit)
 268 {
 269   for (int i = start; i < limit; i++)
 270     v.safe_push (i);
 271 }
 272
 273 /* Verify that vec::quick_push works correctly.  */
 274
 275 static void
 276 test_quick_push ()
 277 {
 278   auto_vec <int> v;
 279   ASSERT_EQ (0, v.length ());
 280   v.reserve (3);
 281   ASSERT_EQ (0, v.length ());
 282   ASSERT_TRUE (v.space (3));
 283   v.quick_push (5);
 284   v.quick_push (6);
 285   v.quick_push (7);
 286   ASSERT_EQ (3, v.length ());
 287   ASSERT_EQ (5, v[0]);
 288   ASSERT_EQ (6, v[1]);
 289   ASSERT_EQ (7, v[2]);
 290 }
 291
 292 /* Verify that vec::safe_push works correctly.  */
 293
 294 static void
 295 test_safe_push ()
 296 {
 297   auto_vec <int> v;
 298   ASSERT_EQ (0, v.length ());
 299   v.safe_push (5);
 300   v.safe_push (6);
 301   v.safe_push (7);
 302   ASSERT_EQ (3, v.length ());
 303   ASSERT_EQ (5, v[0]);
 304   ASSERT_EQ (6, v[1]);
 305   ASSERT_EQ (7, v[2]);
 306 }
 307
 308 /* Verify that vec::truncate works correctly.  */
 309
 310 static void
 311 test_truncate ()
 312 {
 313   auto_vec <int> v;
 314   ASSERT_EQ (0, v.length ());
 315   safe_push_range (v, 0, 10);
 316   ASSERT_EQ (10, v.length ());
 317
 318   v.truncate (5);
 319   ASSERT_EQ (5, v.length ());
 320 }
 321
 322 /* Verify that vec::safe_grow_cleared works correctly.  */
 323
 324 static void
 325 test_safe_grow_cleared ()
 326 {
 327   auto_vec <int> v;
 328   ASSERT_EQ (0, v.length ());
 329   v.safe_grow_cleared (50);
 330   ASSERT_EQ (50, v.length ());
 331   ASSERT_EQ (0, v[0]);
 332   ASSERT_EQ (0, v[49]);
 333 }
 334
 335 /* Verify that vec::pop works correctly.  */
 336
 337 static void
 338 test_pop ()
 339 {
 340   auto_vec <int> v;
 341   safe_push_range (v, 5, 20);
 342   ASSERT_EQ (15, v.length ());
 343
 344   int last = v.pop ();
 345   ASSERT_EQ (19, last);
 346   ASSERT_EQ (14, v.length ());
 347 }
 348
 349 /* Verify that vec::safe_insert works correctly.  */
 350
 351 static void
 352 test_safe_insert ()
 353 {
 354   auto_vec <int> v;
 355   safe_push_range (v, 0, 10);
 356   v.safe_insert (5, 42);
 357   ASSERT_EQ (4, v[4]);
 358   ASSERT_EQ (42, v[5]);
 359   ASSERT_EQ (5, v[6]);
 360   ASSERT_EQ (11, v.length ());
 361 }
 362
 363 /* Verify that vec::ordered_remove works correctly.  */
 364
 365 static void
 366 test_ordered_remove ()
 367 {
 368   auto_vec <int> v;
 369   safe_push_range (v, 0, 10);
 370   v.ordered_remove (5);
 371   ASSERT_EQ (4, v[4]);
 372   ASSERT_EQ (6, v[5]);
 373   ASSERT_EQ (9, v.length ());
 374 }
 375
 376 /* Verify that vec::ordered_remove_if works correctly.  */
 377
 378 static void
 379 test_ordered_remove_if (void)
 380 {
 381   auto_vec <int> v;
 382   safe_push_range (v, 0, 10);
 383   unsigned ix, ix2;
 384   int *elem_ptr;
 385   VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr,
 386                          *elem_ptr == 5 || *elem_ptr == 7);
 387   ASSERT_EQ (4, v[4]);
 388   ASSERT_EQ (6, v[5]);
 389   ASSERT_EQ (8, v[6]);
 390   ASSERT_EQ (8, v.length ());
 391
 392   v.truncate (0);
 393   safe_push_range (v, 0, 10);
 394   VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6,
 395                                  *elem_ptr == 5 || *elem_ptr == 7);
 396   ASSERT_EQ (4, v[4]);
 397   ASSERT_EQ (6, v[5]);
 398   ASSERT_EQ (7, v[6]);
 399   ASSERT_EQ (9, 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, 5,
 404                                  *elem_ptr == 5 || *elem_ptr == 7);
 405   VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10,
 406                                  *elem_ptr == 5 || *elem_ptr == 7);
 407   ASSERT_EQ (4, v[4]);
 408   ASSERT_EQ (5, v[5]);
 409   ASSERT_EQ (6, v[6]);
 410   ASSERT_EQ (10, v.length ());
 411
 412   v.truncate (0);
 413   safe_push_range (v, 0, 10);
 414   VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5);
 415   ASSERT_EQ (4, v[4]);
 416   ASSERT_EQ (6, v[5]);
 417   ASSERT_EQ (7, v[6]);
 418   ASSERT_EQ (9, v.length ());
 419 }
 420
 421 /* Verify that vec::unordered_remove works correctly.  */
 422
 423 static void
 424 test_unordered_remove ()
 425 {
 426   auto_vec <int> v;
 427   safe_push_range (v, 0, 10);
 428   v.unordered_remove (5);
 429   ASSERT_EQ (9, v.length ());
 430 }
 431
 432 /* Verify that vec::block_remove works correctly.  */
 433
 434 static void
 435 test_block_remove ()
 436 {
 437   auto_vec <int> v;
 438   safe_push_range (v, 0, 10);
 439   v.block_remove (5, 3);
 440   ASSERT_EQ (3, v[3]);
 441   ASSERT_EQ (4, v[4]);
 442   ASSERT_EQ (8, v[5]);
 443   ASSERT_EQ (9, v[6]);
 444   ASSERT_EQ (7, v.length ());
 445 }
 446
 447 /* Comparator for use by test_qsort.  */
 448
 449 static int
 450 reverse_cmp (const void *p_i, const void *p_j)
 451 {
 452   return *(const int *)p_j - *(const int *)p_i;
 453 }
 454
 455 /* Verify that vec::qsort works correctly.  */
 456
 457 static void
 458 test_qsort ()
 459 {
 460   auto_vec <int> v;
 461   safe_push_range (v, 0, 10);
 462   v.qsort (reverse_cmp);
 463   ASSERT_EQ (9, v[0]);
 464   ASSERT_EQ (8, v[1]);
 465   ASSERT_EQ (1, v[8]);
 466   ASSERT_EQ (0, v[9]);
 467   ASSERT_EQ (10, v.length ());
 468 }
 469
 470 /* Verify that vec::reverse works correctly.  */
 471
 472 static void
 473 test_reverse ()
 474 {
 475   /* Reversing an empty vec ought to be a no-op.  */
 476   {
 477     auto_vec <int> v;
 478     ASSERT_EQ (0, v.length ());
 479     v.reverse ();
 480     ASSERT_EQ (0, v.length ());
 481   }
 482
 483   /* Verify reversing a vec with even length.  */
 484   {
 485     auto_vec <int> v;
 486     safe_push_range (v, 0, 4);
 487     v.reverse ();
 488     ASSERT_EQ (3, v[0]);
 489     ASSERT_EQ (2, v[1]);
 490     ASSERT_EQ (1, v[2]);
 491     ASSERT_EQ (0, v[3]);
 492     ASSERT_EQ (4, v.length ());
 493   }
 494
 495   /* Verify reversing a vec with odd length.  */
 496   {
 497     auto_vec <int> v;
 498     safe_push_range (v, 0, 3);
 499     v.reverse ();
 500     ASSERT_EQ (2, v[0]);
 501     ASSERT_EQ (1, v[1]);
 502     ASSERT_EQ (0, v[2]);
 503     ASSERT_EQ (3, v.length ());
 504   }
 505 }
 506
 507 /* Run all of the selftests within this file.  */
 508
 509 void
 510 vec_c_tests ()
 511 {
 512   test_quick_push ();
 513   test_safe_push ();
 514   test_truncate ();
 515   test_safe_grow_cleared ();
 516   test_pop ();
 517   test_safe_insert ();
 518   test_ordered_remove ();
 519   test_ordered_remove_if ();
 520   test_unordered_remove ();
 521   test_block_remove ();
 522   test_qsort ();
 523   test_reverse ();
 524 }
 525
 526 } // namespace selftest
 527
 528 #endif /* #if CHECKING_P */
 529 #endif /* #ifndef GENERATOR_FILE */