gcc/vec.c

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004-2014 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    it is of at least DESIRED size by growing ALLOC exponentially.  */
 175
 176 unsigned
 177 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
 178 {
 179   /* We must have run out of room.  */
 180   gcc_assert (alloc < desired);
 181
 182   /* Exponential growth. */
 183   if (!alloc)
 184     alloc = 4;
 185   else if (alloc < 16)
 186     /* Double when small.  */
 187     alloc = alloc * 2;
 188   else
 189     /* Grow slower when large.  */
 190     alloc = (alloc * 3 / 2);
 191
 192   /* If this is still too small, set it to the right size. */
 193   if (alloc < desired)
 194     alloc = desired;
 195   return alloc;
 196 }
 197
 198
 199 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 200
 201 static int
 202 cmp_statistic (const void *loc1, const void *loc2)
 203 {
 204   const struct vec_descriptor *const l1 =
 205     *(const struct vec_descriptor *const *) loc1;
 206   const struct vec_descriptor *const l2 =
 207     *(const struct vec_descriptor *const *) loc2;
 208   long diff;
 209   diff = l1->allocated - l2->allocated;
 210   if (!diff)
 211     diff = l1->peak - l2->peak;
 212   if (!diff)
 213     diff = l1->times - l2->times;
 214   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 215 }
 216
 217
 218 /* Collect array of the descriptors from hashtable.  */
 219
 220 static struct vec_descriptor **loc_array;
 221 static int
 222 add_statistics (void **slot, void *b)
 223 {
 224   int *n = (int *)b;
 225   loc_array[*n] = (struct vec_descriptor *) *slot;
 226   (*n)++;
 227   return 1;
 228 }
 229
 230 /* Dump per-site memory statistics.  */
 231
 232 void
 233 dump_vec_loc_statistics (void)
 234 {
 235   int nentries = 0;
 236   char s[4096];
 237   size_t allocated = 0;
 238   size_t times = 0;
 239   int i;
 240
 241   if (! GATHER_STATISTICS)
 242     return;
 243
 244   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 245   fprintf (stderr, "Heap vectors:\n");
 246   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 247            "source location", "Leak", "Peak", "Times");
 248   fprintf (stderr, "-------------------------------------------------------\n");
 249   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 250   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 251   for (i = 0; i < nentries; i++)
 252     {
 253       struct vec_descriptor *d = loc_array[i];
 254       allocated += d->allocated;
 255       times += d->times;
 256     }
 257   for (i = 0; i < nentries; i++)
 258     {
 259       struct vec_descriptor *d = loc_array[i];
 260       const char *s1 = d->file;
 261       const char *s2;
 262       while ((s2 = strstr (s1, "gcc/")))
 263         s1 = s2 + 4;
 264       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 265       s[48] = 0;
 266       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 267                (long)d->allocated,
 268                (d->allocated) * 100.0 / allocated,
 269                (long)d->peak,
 270                (long)d->times,
 271                (d->times) * 100.0 / times);
 272     }
 273   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 274            "Total", (long)allocated, (long)times);
 275   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 276            "source location", "Leak", "Peak", "Times");
 277   fprintf (stderr, "-------------------------------------------------------\n");
 278 }