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   (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::unordered_remove works correctly.  */
 386
 387 static void
 388 test_unordered_remove ()
 389 {
 390   auto_vec <int> v;
 391   safe_push_range (v, 0, 10);
 392   v.unordered_remove (5);
 393   ASSERT_EQ (9, v.length ());
 394 }
 395
 396 /* Verify that vec::block_remove works correctly.  */
 397
 398 static void
 399 test_block_remove ()
 400 {
 401   auto_vec <int> v;
 402   safe_push_range (v, 0, 10);
 403   v.block_remove (5, 3);
 404   ASSERT_EQ (3, v[3]);
 405   ASSERT_EQ (4, v[4]);
 406   ASSERT_EQ (8, v[5]);
 407   ASSERT_EQ (9, v[6]);
 408   ASSERT_EQ (7, v.length ());
 409 }
 410
 411 /* Comparator for use by test_qsort.  */
 412
 413 static int
 414 reverse_cmp (const void *p_i, const void *p_j)
 415 {
 416   return *(const int *)p_j - *(const int *)p_i;
 417 }
 418
 419 /* Verify that vec::qsort works correctly.  */
 420
 421 static void
 422 test_qsort ()
 423 {
 424   auto_vec <int> v;
 425   safe_push_range (v, 0, 10);
 426   v.qsort (reverse_cmp);
 427   ASSERT_EQ (9, v[0]);
 428   ASSERT_EQ (8, v[1]);
 429   ASSERT_EQ (1, v[8]);
 430   ASSERT_EQ (0, v[9]);
 431   ASSERT_EQ (10, v.length ());
 432 }
 433
 434 /* Run all of the selftests within this file.  */
 435
 436 void
 437 vec_c_tests ()
 438 {
 439   test_quick_push ();
 440   test_safe_push ();
 441   test_truncate ();
 442   test_safe_grow_cleared ();
 443   test_pop ();
 444   test_safe_insert ();
 445   test_ordered_remove ();
 446   test_unordered_remove ();
 447   test_block_remove ();
 448   test_qsort ();
 449 }
 450
 451 } // namespace selftest
 452
 453 #endif /* #if CHECKING_P */
 454 #endif /* #ifndef GENERATOR_FILE */