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     gcc_unreachable ();
 191
 192   /* We must have run out of room.  */
 193   gcc_assert (alloc - num < reserve);
 194
 195   if (exact)
 196     /* Exact size.  */
 197     alloc = num + reserve;
 198   else
 199     {
 200       /* Exponential growth. */
 201       if (!alloc)
 202         alloc = 4;
 203       else if (alloc < 16)
 204         /* Double when small.  */
 205         alloc = alloc * 2;
 206       else
 207         /* Grow slower when large.  */
 208         alloc = (alloc * 3 / 2);
 209
 210       /* If this is still too small, set it to the right size. */
 211       if (alloc < num + reserve)
 212         alloc = num + reserve;
 213     }
 214   return alloc;
 215 }
 216
 217
 218 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 219
 220 static int
 221 cmp_statistic (const void *loc1, const void *loc2)
 222 {
 223   const struct vec_descriptor *const l1 =
 224     *(const struct vec_descriptor *const *) loc1;
 225   const struct vec_descriptor *const l2 =
 226     *(const struct vec_descriptor *const *) loc2;
 227   long diff;
 228   diff = l1->allocated - l2->allocated;
 229   if (!diff)
 230     diff = l1->peak - l2->peak;
 231   if (!diff)
 232     diff = l1->times - l2->times;
 233   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 234 }
 235
 236
 237 /* Collect array of the descriptors from hashtable.  */
 238
 239 static struct vec_descriptor **loc_array;
 240 static int
 241 add_statistics (void **slot, void *b)
 242 {
 243   int *n = (int *)b;
 244   loc_array[*n] = (struct vec_descriptor *) *slot;
 245   (*n)++;
 246   return 1;
 247 }
 248
 249 /* Dump per-site memory statistics.  */
 250
 251 void
 252 dump_vec_loc_statistics (void)
 253 {
 254   int nentries = 0;
 255   char s[4096];
 256   size_t allocated = 0;
 257   size_t times = 0;
 258   int i;
 259
 260   if (! GATHER_STATISTICS)
 261     return;
 262
 263   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 264   fprintf (stderr, "Heap vectors:\n");
 265   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 266            "source location", "Leak", "Peak", "Times");
 267   fprintf (stderr, "-------------------------------------------------------\n");
 268   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 269   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 270   for (i = 0; i < nentries; i++)
 271     {
 272       struct vec_descriptor *d = loc_array[i];
 273       allocated += d->allocated;
 274       times += d->times;
 275     }
 276   for (i = 0; i < nentries; i++)
 277     {
 278       struct vec_descriptor *d = loc_array[i];
 279       const char *s1 = d->file;
 280       const char *s2;
 281       while ((s2 = strstr (s1, "gcc/")))
 282         s1 = s2 + 4;
 283       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 284       s[48] = 0;
 285       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 286                (long)d->allocated,
 287                (d->allocated) * 100.0 / allocated,
 288                (long)d->peak,
 289                (long)d->times,
 290                (d->times) * 100.0 / times);
 291     }
 292   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 293            "Total", (long)allocated, (long)times);
 294   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 295            "source location", "Leak", "Peak", "Times");
 296   fprintf (stderr, "-------------------------------------------------------\n");
 297 }