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
  35 /* vNULL is an empty type with a template cast operation that returns
  36    a zero-initialized vec<T, A, L> instance.  Use this when you want
  37    to assign nil values to new vec instances or pass a nil vector as
  38    a function call argument.
  39
  40    We use this technique because vec<T, A, L> must be PODs (they are
  41    stored in unions and passed in vararg functions), this means that
  42    they cannot have ctors/dtors.  */
  43 vnull vNULL;
  44
  45 /* Vector memory usage.  */
  46 struct vec_usage: public mem_usage
  47 {
  48   /* Default constructor.  */
  49   vec_usage (): m_items (0), m_items_peak (0) {}
  50
  51   /* Constructor.  */
  52   vec_usage (size_t allocated, size_t times, size_t peak,
  53              size_t items, size_t items_peak)
  54     : mem_usage (allocated, times, peak),
  55     m_items (items), m_items_peak (items_peak) {}
  56
  57   /* Comparison operator.  */
  58   inline bool
  59   operator< (const vec_usage &second) const
  60   {
  61     return (m_allocated == second.m_allocated ?
  62             (m_peak == second.m_peak ? m_times < second.m_times
  63              : m_peak < second.m_peak) : m_allocated < second.m_allocated);
  64   }
  65
  66   /* Sum the usage with SECOND usage.  */
  67   vec_usage
  68   operator+ (const vec_usage &second)
  69   {
  70     return vec_usage (m_allocated + second.m_allocated,
  71                       m_times + second.m_times,
  72                       m_peak + second.m_peak,
  73                       m_items + second.m_items,
  74                       m_items_peak + second.m_items_peak);
  75   }
  76
  77   /* Dump usage coupled to LOC location, where TOTAL is sum of all rows.  */
  78   inline void
  79   dump (mem_location *loc, mem_usage &total) const
  80   {
  81     char s[4096];
  82     sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
  83              loc->m_line, loc->m_function);
  84
  85     s[48] = '\0';
  86
  87     fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s,
  88              (long)m_allocated, m_allocated * 100.0 / total.m_allocated,
  89              (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times,
  90              (long)m_items, (long)m_items_peak);
  91   }
  92
  93   /* Dump footer.  */
  94   inline void
  95   dump_footer ()
  96   {
  97     print_dash_line ();
  98     fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated,
  99              (long)m_times, (long)m_items);
 100     print_dash_line ();
 101   }
 102
 103   /* Dump header with NAME.  */
 104   static inline void
 105   dump_header (const char *name)
 106   {
 107     fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak",
 108              "Times", "Leak items", "Peak items");
 109     print_dash_line ();
 110   }
 111
 112   /* Compare wrapper used by qsort method.  */
 113   static int
 114   compare (const void *first, const void *second)
 115   {
 116     typedef std::pair<mem_location *, vec_usage *> mem_pair_t;
 117
 118     const mem_pair_t f = *(const mem_pair_t *)first;
 119     const mem_pair_t s = *(const mem_pair_t *)second;
 120
 121     return (*f.second) < (*s.second);
 122   }
 123
 124   /* Current number of items allocated.  */
 125   size_t m_items;
 126   /* Peak value of number of allocated items.  */
 127   size_t m_items_peak;
 128 };
 129
 130 /* Vector memory description.  */
 131 static mem_alloc_description <vec_usage> vec_mem_desc;
 132
 133 /* Account the overhead.  */
 134
 135 void
 136 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements
 137                                MEM_STAT_DECL)
 138 {
 139   vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
 140                                     FINAL_PASS_MEM_STAT);
 141   vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr);
 142   usage->m_items += elements;
 143   if (usage->m_items_peak < usage->m_items)
 144     usage->m_items_peak = usage->m_items;
 145 }
 146
 147 /* Notice that the memory allocated for the vector has been freed.  */
 148
 149 void
 150 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor
 151                               MEM_STAT_DECL)
 152 {
 153   if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
 154     vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
 155                                       false FINAL_PASS_MEM_STAT);
 156   vec_mem_desc.release_instance_overhead (ptr, size, in_dtor);
 157 }
 158
 159
 160 /* Calculate the number of slots to reserve a vector, making sure that
 161    it is of at least DESIRED size by growing ALLOC exponentially.  */
 162
 163 unsigned
 164 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
 165 {
 166   /* We must have run out of room.  */
 167   gcc_assert (alloc < desired);
 168
 169   /* Exponential growth. */
 170   if (!alloc)
 171     alloc = 4;
 172   else if (alloc < 16)
 173     /* Double when small.  */
 174     alloc = alloc * 2;
 175   else
 176     /* Grow slower when large.  */
 177     alloc = (alloc * 3 / 2);
 178
 179   /* If this is still too small, set it to the right size. */
 180   if (alloc < desired)
 181     alloc = desired;
 182   return alloc;
 183 }
 184
 185 /* Dump per-site memory statistics.  */
 186
 187 void
 188 dump_vec_loc_statistics (void)
 189 {
 190   vec_mem_desc.dump (VEC_ORIGIN);
 191 }
 192
 193 #ifndef GENERATOR_FILE
 194 #if CHECKING_P
 195
 196 namespace selftest {
 197
 198 /* Selftests.  */
 199
 200 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
 201    Helper function for selftests.  */
 202
 203 static void
 204 safe_push_range (vec <int>&v, int start, int limit)
 205 {
 206   for (int i = start; i < limit; i++)
 207     v.safe_push (i);
 208 }
 209
 210 /* Verify that vec::quick_push works correctly.  */
 211
 212 static void
 213 test_quick_push ()
 214 {
 215   auto_vec <int> v;
 216   ASSERT_EQ (0, v.length ());
 217   v.reserve (3);
 218   ASSERT_EQ (0, v.length ());
 219   ASSERT_TRUE (v.space (3));
 220   v.quick_push (5);
 221   v.quick_push (6);
 222   v.quick_push (7);
 223   ASSERT_EQ (3, v.length ());
 224   ASSERT_EQ (5, v[0]);
 225   ASSERT_EQ (6, v[1]);
 226   ASSERT_EQ (7, v[2]);
 227 }
 228
 229 /* Verify that vec::safe_push works correctly.  */
 230
 231 static void
 232 test_safe_push ()
 233 {
 234   auto_vec <int> v;
 235   ASSERT_EQ (0, v.length ());
 236   v.safe_push (5);
 237   v.safe_push (6);
 238   v.safe_push (7);
 239   ASSERT_EQ (3, v.length ());
 240   ASSERT_EQ (5, v[0]);
 241   ASSERT_EQ (6, v[1]);
 242   ASSERT_EQ (7, v[2]);
 243 }
 244
 245 /* Verify that vec::truncate works correctly.  */
 246
 247 static void
 248 test_truncate ()
 249 {
 250   auto_vec <int> v;
 251   ASSERT_EQ (0, v.length ());
 252   safe_push_range (v, 0, 10);
 253   ASSERT_EQ (10, v.length ());
 254
 255   v.truncate (5);
 256   ASSERT_EQ (5, v.length ());
 257 }
 258
 259 /* Verify that vec::safe_grow_cleared works correctly.  */
 260
 261 static void
 262 test_safe_grow_cleared ()
 263 {
 264   auto_vec <int> v;
 265   ASSERT_EQ (0, v.length ());
 266   v.safe_grow_cleared (50);
 267   ASSERT_EQ (50, v.length ());
 268   ASSERT_EQ (0, v[0]);
 269   ASSERT_EQ (0, v[49]);
 270 }
 271
 272 /* Verify that vec::pop works correctly.  */
 273
 274 static void
 275 test_pop ()
 276 {
 277   auto_vec <int> v;
 278   safe_push_range (v, 5, 20);
 279   ASSERT_EQ (15, v.length ());
 280
 281   int last = v.pop ();
 282   ASSERT_EQ (19, last);
 283   ASSERT_EQ (14, v.length ());
 284 }
 285
 286 /* Verify that vec::safe_insert works correctly.  */
 287
 288 static void
 289 test_safe_insert ()
 290 {
 291   auto_vec <int> v;
 292   safe_push_range (v, 0, 10);
 293   v.safe_insert (5, 42);
 294   ASSERT_EQ (4, v[4]);
 295   ASSERT_EQ (42, v[5]);
 296   ASSERT_EQ (5, v[6]);
 297   ASSERT_EQ (11, v.length ());
 298 }
 299
 300 /* Verify that vec::ordered_remove works correctly.  */
 301
 302 static void
 303 test_ordered_remove ()
 304 {
 305   auto_vec <int> v;
 306   safe_push_range (v, 0, 10);
 307   v.ordered_remove (5);
 308   ASSERT_EQ (4, v[4]);
 309   ASSERT_EQ (6, v[5]);
 310   ASSERT_EQ (9, v.length ());
 311 }
 312
 313 /* Verify that vec::unordered_remove works correctly.  */
 314
 315 static void
 316 test_unordered_remove ()
 317 {
 318   auto_vec <int> v;
 319   safe_push_range (v, 0, 10);
 320   v.unordered_remove (5);
 321   ASSERT_EQ (9, v.length ());
 322 }
 323
 324 /* Verify that vec::block_remove works correctly.  */
 325
 326 static void
 327 test_block_remove ()
 328 {
 329   auto_vec <int> v;
 330   safe_push_range (v, 0, 10);
 331   v.block_remove (5, 3);
 332   ASSERT_EQ (3, v[3]);
 333   ASSERT_EQ (4, v[4]);
 334   ASSERT_EQ (8, v[5]);
 335   ASSERT_EQ (9, v[6]);
 336   ASSERT_EQ (7, v.length ());
 337 }
 338
 339 /* Comparator for use by test_qsort.  */
 340
 341 static int
 342 reverse_cmp (const void *p_i, const void *p_j)
 343 {
 344   return *(const int *)p_j - *(const int *)p_i;
 345 }
 346
 347 /* Verify that vec::qsort works correctly.  */
 348
 349 static void
 350 test_qsort ()
 351 {
 352   auto_vec <int> v;
 353   safe_push_range (v, 0, 10);
 354   v.qsort (reverse_cmp);
 355   ASSERT_EQ (9, v[0]);
 356   ASSERT_EQ (8, v[1]);
 357   ASSERT_EQ (1, v[8]);
 358   ASSERT_EQ (0, v[9]);
 359   ASSERT_EQ (10, v.length ());
 360 }
 361
 362 /* Run all of the selftests within this file.  */
 363
 364 void
 365 vec_c_tests ()
 366 {
 367   test_quick_push ();
 368   test_safe_push ();
 369   test_truncate ();
 370   test_safe_grow_cleared ();
 371   test_pop ();
 372   test_safe_insert ();
 373   test_ordered_remove ();
 374   test_unordered_remove ();
 375   test_block_remove ();
 376   test_qsort ();
 377 }
 378
 379 } // namespace selftest
 380
 381 #endif /* #if CHECKING_P */
 382 #endif /* #ifndef GENERATOR_FILE */