gcc/vec.c

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