gcc/vec.c

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
   3    Contributed by Nathan Sidwell <nathan@codesourcery.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file is compiled twice: once for the generator programs
  22    once for the compiler.  */
  23 #ifdef GENERATOR_FILE
  24 #include "bconfig.h"
  25 #else
  26 #include "config.h"
  27 #endif
  28
  29 #include "system.h"
  30 #include "ggc.h"
  31 #include "vec.h"
  32 #include "coretypes.h"
  33 #include "toplev.h"
  34 #include "hashtab.h"
  35
  36 struct vec_prefix
  37 {
  38   unsigned num;
  39   unsigned alloc;
  40   void *vec[1];
  41 };
  42
  43
  44 #ifdef GATHER_STATISTICS
  45
  46 /* Store information about each particular vector.  */
  47 struct vec_descriptor
  48 {
  49   const char *function;
  50   const char *file;
  51   int line;
  52   size_t allocated;
  53   size_t times;
  54   size_t peak;
  55 };
  56
  57
  58 /* Hashtable mapping vec addresses to descriptors.  */
  59 static htab_t vec_desc_hash;
  60
  61 /* Hashtable helpers.  */
  62 static hashval_t
  63 hash_descriptor (const void *p)
  64 {
  65   const struct vec_descriptor *const d =
  66     (const struct vec_descriptor *) p;
  67   return htab_hash_pointer (d->file) + d->line;
  68 }
  69 static int
  70 eq_descriptor (const void *p1, const void *p2)
  71 {
  72   const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
  73   const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
  74   return d->file == l->file && d->function == l->function && d->line == l->line;
  75 }
  76
  77 /* Hashtable converting address of allocated field to loc descriptor.  */
  78 static htab_t ptr_hash;
  79 struct ptr_hash_entry
  80 {
  81   void *ptr;
  82   struct vec_descriptor *loc;
  83   size_t allocated;
  84 };
  85
  86 /* Hash table helpers functions.  */
  87 static hashval_t
  88 hash_ptr (const void *p)
  89 {
  90   const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
  91
  92   return htab_hash_pointer (d->ptr);
  93 }
  94
  95 static int
  96 eq_ptr (const void *p1, const void *p2)
  97 {
  98   const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
  99
 100   return (p->ptr == p2);
 101 }
 102
 103 /* Return descriptor for given call site, create new one if needed.  */
 104 static struct vec_descriptor *
 105 vec_descriptor (const char *name, int line, const char *function)
 106 {
 107   struct vec_descriptor loc;
 108   struct vec_descriptor **slot;
 109
 110   loc.file = name;
 111   loc.line = line;
 112   loc.function = function;
 113   if (!vec_desc_hash)
 114     vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
 115
 116   slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
 117                                                     INSERT);
 118   if (*slot)
 119     return *slot;
 120   *slot = XCNEW (struct vec_descriptor);
 121   (*slot)->file = name;
 122   (*slot)->line = line;
 123   (*slot)->function = function;
 124   (*slot)->allocated = 0;
 125   (*slot)->peak = 0;
 126   return *slot;
 127 }
 128
 129 /* Account the overhead.  */
 130 static void
 131 register_overhead (struct vec_prefix *ptr, size_t size,
 132                    const char *name, int line, const char *function)
 133 {
 134   struct vec_descriptor *loc = vec_descriptor (name, line, function);
 135   struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
 136   PTR *slot;
 137
 138   p->ptr = ptr;
 139   p->loc = loc;
 140   p->allocated = size;
 141   if (!ptr_hash)
 142     ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
 143   slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
 144   gcc_assert (!*slot);
 145   *slot = p;
 146
 147   loc->allocated += size;
 148   if (loc->peak < loc->allocated)
 149     loc->peak += loc->allocated;
 150   loc->times++;
 151 }
 152
 153 /* Notice that the pointer has been freed.  */
 154 static void
 155 free_overhead (struct vec_prefix *ptr)
 156 {
 157   PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
 158                                         NO_INSERT);
 159   struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
 160   p->loc->allocated -= p->allocated;
 161   htab_clear_slot (ptr_hash, slot);
 162   free (p);
 163 }
 164
 165 void
 166 vec_heap_free (void *ptr)
 167 {
 168   free_overhead ((struct vec_prefix *)ptr);
 169   free (ptr);
 170 }
 171 #endif
 172
 173 /* Calculate the new ALLOC value, making sure that RESERVE slots are
 174    free.  If EXACT grow exactly, otherwise grow exponentially.  */
 175
 176 static inline unsigned
 177 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
 178 {
 179   unsigned alloc = 0;
 180   unsigned num = 0;
 181
 182   gcc_assert (reserve >= 0);
 183
 184   if (pfx)
 185     {
 186       alloc = pfx->alloc;
 187       num = pfx->num;
 188     }
 189   else if (!reserve)
 190     /* If there's no prefix, 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 < (unsigned) 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 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
 220    exactly, else grow exponentially.  As a special case, if VEC is
 221    NULL and RESERVE is 0, no vector will be created.  The vector's
 222    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 223    sized elements.  */
 224
 225 static void *
 226 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
 227                     bool exact MEM_STAT_DECL)
 228 {
 229   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 230   unsigned alloc = alloc = calculate_allocation (pfx, reserve, exact);
 231
 232   if (!alloc)
 233     {
 234       if (pfx)
 235         ggc_free (pfx);
 236       return NULL;
 237     }
 238
 239   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
 240   ((struct vec_prefix *)vec)->alloc = alloc;
 241   if (!pfx)
 242     ((struct vec_prefix *)vec)->num = 0;
 243
 244   return vec;
 245 }
 246
 247 /* Ensure there are at least RESERVE free slots in VEC, growing
 248    exponentially.  If RESERVE < 0 grow exactly, else grow
 249    exponentially.  As a special case, if VEC is NULL, and RESERVE is
 250    0, no vector will be created. */
 251
 252 void *
 253 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 254 {
 255   return vec_gc_o_reserve_1 (vec, reserve,
 256                              offsetof (struct vec_prefix, vec),
 257                              sizeof (void *), false
 258                              PASS_MEM_STAT);
 259 }
 260
 261 /* Ensure there are at least RESERVE free slots in VEC, growing
 262    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
 263    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
 264    created. */
 265
 266 void *
 267 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 268 {
 269   return vec_gc_o_reserve_1 (vec, reserve,
 270                              offsetof (struct vec_prefix, vec),
 271                              sizeof (void *), true
 272                              PASS_MEM_STAT);
 273 }
 274
 275 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
 276    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 277    sized elements.  */
 278
 279 void *
 280 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 281                   MEM_STAT_DECL)
 282 {
 283   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 284                              PASS_MEM_STAT);
 285 }
 286
 287 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
 288    vector's trailing array is at VEC_OFFSET offset and consists of
 289    ELT_SIZE sized elements.  */
 290
 291 void *
 292 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 293                         size_t elt_size MEM_STAT_DECL)
 294 {
 295   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 296                              PASS_MEM_STAT);
 297 }
 298
 299 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
 300
 301 static void *
 302 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 303                       size_t elt_size, bool exact MEM_STAT_DECL)
 304 {
 305   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 306   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 307
 308   if (!alloc)
 309     {
 310       if (pfx)
 311         vec_heap_free (pfx);
 312       return NULL;
 313     }
 314
 315 #ifdef GATHER_STATISTICS
 316   if (vec)
 317     free_overhead (pfx);
 318 #endif
 319
 320   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 321   ((struct vec_prefix *)vec)->alloc = alloc;
 322   if (!pfx)
 323     ((struct vec_prefix *)vec)->num = 0;
 324 #ifdef GATHER_STATISTICS
 325   if (vec)
 326     register_overhead ((struct vec_prefix *)vec,
 327                        vec_offset + alloc * elt_size PASS_MEM_STAT);
 328 #endif
 329
 330   return vec;
 331 }
 332
 333 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 334
 335 void *
 336 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 337 {
 338   return vec_heap_o_reserve_1 (vec, reserve,
 339                                offsetof (struct vec_prefix, vec),
 340                                sizeof (void *), false
 341                                PASS_MEM_STAT);
 342 }
 343
 344 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
 345
 346 void *
 347 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 348 {
 349   return vec_heap_o_reserve_1 (vec, reserve,
 350                                offsetof (struct vec_prefix, vec),
 351                                sizeof (void *), true
 352                                PASS_MEM_STAT);
 353 }
 354
 355 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 356
 357 void *
 358 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 359                     MEM_STAT_DECL)
 360 {
 361   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 362                                PASS_MEM_STAT);
 363 }
 364
 365 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
 366
 367 void *
 368 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 369                           size_t elt_size MEM_STAT_DECL)
 370 {
 371   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 372                                PASS_MEM_STAT);
 373 }
 374
 375 #if ENABLE_CHECKING
 376 /* Issue a vector domain error, and then fall over.  */
 377
 378 void
 379 vec_assert_fail (const char *op, const char *struct_name,
 380                  const char *file, unsigned int line, const char *function)
 381 {
 382   internal_error ("vector %s %s domain error, in %s at %s:%u",
 383                   struct_name, op, function, trim_filename (file), line);
 384 }
 385 #endif
 386
 387 #ifdef GATHER_STATISTICS
 388 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 389 static int
 390 cmp_statistic (const void *loc1, const void *loc2)
 391 {
 392   const struct vec_descriptor *const l1 =
 393     *(const struct vec_descriptor *const *) loc1;
 394   const struct vec_descriptor *const l2 =
 395     *(const struct vec_descriptor *const *) loc2;
 396   long diff;
 397   diff = l1->allocated - l2->allocated;
 398   if (!diff)
 399     diff = l1->peak - l2->peak;
 400   if (!diff)
 401     diff = l1->times - l2->times;
 402   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 403 }
 404 /* Collect array of the descriptors from hashtable.  */
 405 static struct vec_descriptor **loc_array;
 406 static int
 407 add_statistics (void **slot, void *b)
 408 {
 409   int *n = (int *)b;
 410   loc_array[*n] = (struct vec_descriptor *) *slot;
 411   (*n)++;
 412   return 1;
 413 }
 414
 415 /* Dump per-site memory statistics.  */
 416 #endif
 417 void
 418 dump_vec_loc_statistics (void)
 419 {
 420 #ifdef GATHER_STATISTICS
 421   int nentries = 0;
 422   char s[4096];
 423   size_t allocated = 0;
 424   size_t times = 0;
 425   int i;
 426
 427   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 428   fprintf (stderr, "Heap vectors:\n");
 429   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 430            "source location", "Leak", "Peak", "Times");
 431   fprintf (stderr, "-------------------------------------------------------\n");
 432   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 433   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 434   for (i = 0; i < nentries; i++)
 435     {
 436       struct vec_descriptor *d = loc_array[i];
 437       allocated += d->allocated;
 438       times += d->times;
 439     }
 440   for (i = 0; i < nentries; i++)
 441     {
 442       struct vec_descriptor *d = loc_array[i];
 443       const char *s1 = d->file;
 444       const char *s2;
 445       while ((s2 = strstr (s1, "gcc/")))
 446         s1 = s2 + 4;
 447       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 448       s[48] = 0;
 449       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 450                (long)d->allocated,
 451                (d->allocated) * 100.0 / allocated,
 452                (long)d->peak,
 453                (long)d->times,
 454                (d->times) * 100.0 / times);
 455     }
 456   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 457            "Total", (long)allocated, (long)times);
 458   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 459            "source location", "Leak", "Peak", "Times");
 460   fprintf (stderr, "-------------------------------------------------------\n");
 461 #endif
 462 }