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