gcc/vec.c

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004-2013 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 "ggc.h"
  33 #include "vec.h"
  34 #include "diagnostic-core.h"
  35 #include "hashtab.h"
  36
  37 /* vNULL is an empty type with a template cast operation that returns
  38    a zero-initialized vec<T, A, L> instance.  Use this when you want
  39    to assign nil values to new vec instances or pass a nil vector as
  40    a function call argument.
  41
  42    We use this technique because vec<T, A, L> must be PODs (they are
  43    stored in unions and passed in vararg functions), this means that
  44    they cannot have ctors/dtors.  */
  45 vnull vNULL;
  46
  47
  48 /* Store information about each particular vector.  */
  49 struct vec_descriptor
  50 {
  51   const char *function;
  52   const char *file;
  53   int line;
  54   size_t allocated;
  55   size_t times;
  56   size_t peak;
  57 };
  58
  59
  60 /* Hashtable mapping vec addresses to descriptors.  */
  61 static htab_t vec_desc_hash;
  62
  63 /* Hashtable helpers.  */
  64 static hashval_t
  65 hash_descriptor (const void *p)
  66 {
  67   const struct vec_descriptor *const d =
  68     (const struct vec_descriptor *) p;
  69   return htab_hash_pointer (d->file) + d->line;
  70 }
  71 static int
  72 eq_descriptor (const void *p1, const void *p2)
  73 {
  74   const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
  75   const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
  76   return d->file == l->file && d->function == l->function && d->line == l->line;
  77 }
  78
  79 /* Hashtable converting address of allocated field to loc descriptor.  */
  80 static htab_t ptr_hash;
  81 struct ptr_hash_entry
  82 {
  83   void *ptr;
  84   struct vec_descriptor *loc;
  85   size_t allocated;
  86 };
  87
  88 /* Hash table helpers functions.  */
  89 static hashval_t
  90 hash_ptr (const void *p)
  91 {
  92   const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
  93
  94   return htab_hash_pointer (d->ptr);
  95 }
  96
  97 static int
  98 eq_ptr (const void *p1, const void *p2)
  99 {
 100   const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
 101
 102   return (p->ptr == p2);
 103 }
 104
 105 /* Return descriptor for given call site, create new one if needed.  */
 106 static struct vec_descriptor *
 107 vec_descriptor (const char *name, int line, const char *function)
 108 {
 109   struct vec_descriptor loc;
 110   struct vec_descriptor **slot;
 111
 112   loc.file = name;
 113   loc.line = line;
 114   loc.function = function;
 115   if (!vec_desc_hash)
 116     vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
 117
 118   slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
 119                                                     INSERT);
 120   if (*slot)
 121     return *slot;
 122   *slot = XCNEW (struct vec_descriptor);
 123   (*slot)->file = name;
 124   (*slot)->line = line;
 125   (*slot)->function = function;
 126   (*slot)->allocated = 0;
 127   (*slot)->peak = 0;
 128   return *slot;
 129 }
 130
 131 /* Account the overhead.  */
 132
 133 void
 134 vec_prefix::register_overhead (size_t size, const char *name, int line,
 135                                const char *function)
 136 {
 137   struct vec_descriptor *loc = vec_descriptor (name, line, function);
 138   struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
 139   PTR *slot;
 140
 141   p->ptr = this;
 142   p->loc = loc;
 143   p->allocated = size;
 144   if (!ptr_hash)
 145     ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
 146   slot = htab_find_slot_with_hash (ptr_hash, this, htab_hash_pointer (this),
 147                                    INSERT);
 148   gcc_assert (!*slot);
 149   *slot = p;
 150
 151   loc->allocated += size;
 152   if (loc->peak < loc->allocated)
 153     loc->peak += loc->allocated;
 154   loc->times++;
 155 }
 156
 157
 158 /* Notice that the memory allocated for the vector has been freed.  */
 159
 160 void
 161 vec_prefix::release_overhead (void)
 162 {
 163   PTR *slot = htab_find_slot_with_hash (ptr_hash, this,
 164                                         htab_hash_pointer (this),
 165                                         NO_INSERT);
 166   struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
 167   p->loc->allocated -= p->allocated;
 168   htab_clear_slot (ptr_hash, slot);
 169   ::free (p);
 170 }
 171
 172
 173 /* Calculate the number of slots to reserve a vector, making sure that
 174    RESERVE slots are free.  If EXACT grow exactly, otherwise grow
 175    exponentially.  PFX is the control data for the vector.  */
 176
 177 unsigned
 178 vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
 179                                   bool exact)
 180 {
 181   unsigned alloc = 0;
 182   unsigned num = 0;
 183
 184   if (pfx)
 185     {
 186       alloc = pfx->m_alloc;
 187       num = pfx->m_num;
 188     }
 189   else if (!reserve)
 190     /* If there's no vector, and we've not requested anything, then we
 191        will create a NULL vector.  */
 192     return 0;
 193
 194   /* We must have run out of room.  */
 195   gcc_assert (alloc - num < reserve);
 196
 197   if (exact)
 198     /* Exact size.  */
 199     alloc = num + reserve;
 200   else
 201     {
 202       /* Exponential growth. */
 203       if (!alloc)
 204         alloc = 4;
 205       else if (alloc < 16)
 206         /* Double when small.  */
 207         alloc = alloc * 2;
 208       else
 209         /* Grow slower when large.  */
 210         alloc = (alloc * 3 / 2);
 211
 212       /* If this is still too small, set it to the right size. */
 213       if (alloc < num + reserve)
 214         alloc = num + reserve;
 215     }
 216   return alloc;
 217 }
 218
 219
 220 /* Stack vectors are a little different.  VEC_alloc turns into a call
 221    to vec<T, A>::stack_reserve and passes in space allocated via a
 222    call to alloca.  We record that pointer so that we know that we
 223    shouldn't free it.  If the vector is resized, we resize it on the
 224    heap.  We record the pointers in a vector and search it in LIFO
 225    order--i.e., we look for the newest stack vectors first.  We don't
 226    expect too many stack vectors at any one level, and searching from
 227    the end should normally be efficient even if they are used in a
 228    recursive function.  */
 229
 230 static vec<void *> stack_vecs;
 231
 232 /* Add a stack vector to STACK_VECS.  */
 233
 234 void
 235 register_stack_vec (void *vec)
 236 {
 237   stack_vecs.safe_push (vec);
 238 }
 239
 240
 241 /* If VEC is registered in STACK_VECS, return its index.
 242    Otherwise, return -1.  */
 243
 244 int
 245 stack_vec_register_index (void *vec)
 246 {
 247   for (unsigned ix = stack_vecs.length (); ix > 0; --ix)
 248     if (stack_vecs[ix - 1] == vec)
 249       return static_cast<int> (ix - 1);
 250   return -1;
 251 }
 252
 253
 254 /* Remove vector at slot IX from the list of registered stack vectors.  */
 255
 256 void
 257 unregister_stack_vec (unsigned ix)
 258 {
 259   stack_vecs.unordered_remove (ix);
 260 }
 261
 262
 263 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 264
 265 static int
 266 cmp_statistic (const void *loc1, const void *loc2)
 267 {
 268   const struct vec_descriptor *const l1 =
 269     *(const struct vec_descriptor *const *) loc1;
 270   const struct vec_descriptor *const l2 =
 271     *(const struct vec_descriptor *const *) loc2;
 272   long diff;
 273   diff = l1->allocated - l2->allocated;
 274   if (!diff)
 275     diff = l1->peak - l2->peak;
 276   if (!diff)
 277     diff = l1->times - l2->times;
 278   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 279 }
 280
 281
 282 /* Collect array of the descriptors from hashtable.  */
 283
 284 static struct vec_descriptor **loc_array;
 285 static int
 286 add_statistics (void **slot, void *b)
 287 {
 288   int *n = (int *)b;
 289   loc_array[*n] = (struct vec_descriptor *) *slot;
 290   (*n)++;
 291   return 1;
 292 }
 293
 294 /* Dump per-site memory statistics.  */
 295
 296 void
 297 dump_vec_loc_statistics (void)
 298 {
 299   int nentries = 0;
 300   char s[4096];
 301   size_t allocated = 0;
 302   size_t times = 0;
 303   int i;
 304
 305   if (! GATHER_STATISTICS)
 306     return;
 307
 308   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 309   fprintf (stderr, "Heap vectors:\n");
 310   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 311            "source location", "Leak", "Peak", "Times");
 312   fprintf (stderr, "-------------------------------------------------------\n");
 313   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 314   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 315   for (i = 0; i < nentries; i++)
 316     {
 317       struct vec_descriptor *d = loc_array[i];
 318       allocated += d->allocated;
 319       times += d->times;
 320     }
 321   for (i = 0; i < nentries; i++)
 322     {
 323       struct vec_descriptor *d = loc_array[i];
 324       const char *s1 = d->file;
 325       const char *s2;
 326       while ((s2 = strstr (s1, "gcc/")))
 327         s1 = s2 + 4;
 328       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 329       s[48] = 0;
 330       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 331                (long)d->allocated,
 332                (d->allocated) * 100.0 / allocated,
 333                (long)d->peak,
 334                (long)d->times,
 335                (d->times) * 100.0 / times);
 336     }
 337   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 338            "Total", (long)allocated, (long)times);
 339   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 340            "source location", "Leak", "Peak", "Times");
 341   fprintf (stderr, "-------------------------------------------------------\n");
 342 }