gcc/vec.c

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