contrib/gcc-4.4/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, 1);
 117   if (*slot)
 118     return *slot;
 119   *slot = XCNEW (struct vec_descriptor);
 120   (*slot)->file = name;
 121   (*slot)->line = line;
 122   (*slot)->function = function;
 123   (*slot)->allocated = 0;
 124   (*slot)->peak = 0;
 125   return *slot;
 126 }
 127
 128 /* Account the overhead.  */
 129 static void
 130 register_overhead (struct vec_prefix *ptr, size_t size,
 131                    const char *name, int line, const char *function)
 132 {
 133   struct vec_descriptor *loc = vec_descriptor (name, line, function);
 134   struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
 135   PTR *slot;
 136
 137   p->ptr = ptr;
 138   p->loc = loc;
 139   p->allocated = size;
 140   if (!ptr_hash)
 141     ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
 142   slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
 143   gcc_assert (!*slot);
 144   *slot = p;
 145
 146   loc->allocated += size;
 147   if (loc->peak < loc->allocated)
 148     loc->peak += loc->allocated;
 149   loc->times++;
 150 }
 151
 152 /* Notice that the pointer has been freed.  */
 153 static void
 154 free_overhead (struct vec_prefix *ptr)
 155 {
 156   PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
 157                                         NO_INSERT);
 158   struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
 159   p->loc->allocated -= p->allocated;
 160   htab_clear_slot (ptr_hash, slot);
 161   free (p);
 162 }
 163
 164 void
 165 vec_heap_free (void *ptr)
 166 {
 167   free_overhead ((struct vec_prefix *)ptr);
 168   free (ptr);
 169 }
 170 #endif
 171
 172 /* Calculate the new ALLOC value, making sure that RESERVE slots are
 173    free.  If EXACT grow exactly, otherwise grow exponentially.  */
 174
 175 static inline unsigned
 176 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
 177 {
 178   unsigned alloc = 0;
 179   unsigned num = 0;
 180
 181   gcc_assert (reserve >= 0);
 182
 183   if (pfx)
 184     {
 185       alloc = pfx->alloc;
 186       num = pfx->num;
 187     }
 188   else if (!reserve)
 189     /* If there's no prefix, and we've not requested anything, then we
 190        will create a NULL vector.  */
 191     return 0;
 192
 193   /* We must have run out of room.  */
 194   gcc_assert (alloc - num < (unsigned) reserve);
 195
 196   if (exact)
 197     /* Exact size.  */
 198     alloc = num + reserve;
 199   else
 200     {
 201       /* Exponential growth. */
 202       if (!alloc)
 203         alloc = 4;
 204       else if (alloc < 16)
 205         /* Double when small.  */
 206         alloc = alloc * 2;
 207       else
 208         /* Grow slower when large.  */
 209         alloc = (alloc * 3 / 2);
 210
 211       /* If this is still too small, set it to the right size. */
 212       if (alloc < num + reserve)
 213         alloc = num + reserve;
 214     }
 215   return alloc;
 216 }
 217
 218 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
 219    exactly, else grow exponentially.  As a special case, if VEC is
 220    NULL and RESERVE is 0, no vector will be created.  The vector's
 221    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 222    sized elements.  */
 223
 224 static void *
 225 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
 226                     bool exact MEM_STAT_DECL)
 227 {
 228   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 229   unsigned alloc = alloc = calculate_allocation (pfx, reserve, exact);
 230
 231   if (!alloc)
 232     {
 233       if (pfx)
 234         ggc_free (pfx);
 235       return NULL;
 236     }
 237
 238   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
 239   ((struct vec_prefix *)vec)->alloc = alloc;
 240   if (!pfx)
 241     ((struct vec_prefix *)vec)->num = 0;
 242
 243   return vec;
 244 }
 245
 246 /* Ensure there are at least RESERVE free slots in VEC, growing
 247    exponentially.  If RESERVE < 0 grow exactly, else grow
 248    exponentially.  As a special case, if VEC is NULL, and RESERVE is
 249    0, no vector will be created. */
 250
 251 void *
 252 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 253 {
 254   return vec_gc_o_reserve_1 (vec, reserve,
 255                              offsetof (struct vec_prefix, vec),
 256                              sizeof (void *), false
 257                              PASS_MEM_STAT);
 258 }
 259
 260 /* Ensure there are at least RESERVE free slots in VEC, growing
 261    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
 262    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
 263    created. */
 264
 265 void *
 266 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 267 {
 268   return vec_gc_o_reserve_1 (vec, reserve,
 269                              offsetof (struct vec_prefix, vec),
 270                              sizeof (void *), true
 271                              PASS_MEM_STAT);
 272 }
 273
 274 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
 275    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 276    sized elements.  */
 277
 278 void *
 279 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 280                   MEM_STAT_DECL)
 281 {
 282   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 283                              PASS_MEM_STAT);
 284 }
 285
 286 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
 287    vector's trailing array is at VEC_OFFSET offset and consists of
 288    ELT_SIZE sized elements.  */
 289
 290 void *
 291 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 292                         size_t elt_size MEM_STAT_DECL)
 293 {
 294   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 295                              PASS_MEM_STAT);
 296 }
 297
 298 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
 299
 300 static void *
 301 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 302                       size_t elt_size, bool exact MEM_STAT_DECL)
 303 {
 304   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 305   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 306
 307   if (!alloc)
 308     {
 309       if (pfx)
 310         vec_heap_free (pfx);
 311       return NULL;
 312     }
 313
 314 #ifdef GATHER_STATISTICS
 315   if (vec)
 316     free_overhead (pfx);
 317 #endif
 318
 319   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 320   ((struct vec_prefix *)vec)->alloc = alloc;
 321   if (!pfx)
 322     ((struct vec_prefix *)vec)->num = 0;
 323 #ifdef GATHER_STATISTICS
 324   if (vec)
 325     register_overhead ((struct vec_prefix *)vec,
 326                        vec_offset + alloc * elt_size PASS_MEM_STAT);
 327 #endif
 328
 329   return vec;
 330 }
 331
 332 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 333
 334 void *
 335 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 336 {
 337   return vec_heap_o_reserve_1 (vec, reserve,
 338                                offsetof (struct vec_prefix, vec),
 339                                sizeof (void *), false
 340                                PASS_MEM_STAT);
 341 }
 342
 343 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
 344
 345 void *
 346 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 347 {
 348   return vec_heap_o_reserve_1 (vec, reserve,
 349                                offsetof (struct vec_prefix, vec),
 350                                sizeof (void *), true
 351                                PASS_MEM_STAT);
 352 }
 353
 354 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 355
 356 void *
 357 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 358                     MEM_STAT_DECL)
 359 {
 360   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 361                                PASS_MEM_STAT);
 362 }
 363
 364 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
 365
 366 void *
 367 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 368                           size_t elt_size MEM_STAT_DECL)
 369 {
 370   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 371                                PASS_MEM_STAT);
 372 }
 373
 374 #if ENABLE_CHECKING
 375 /* Issue a vector domain error, and then fall over.  */
 376
 377 void
 378 vec_assert_fail (const char *op, const char *struct_name,
 379                  const char *file, unsigned int line, const char *function)
 380 {
 381   internal_error ("vector %s %s domain error, in %s at %s:%u",
 382                   struct_name, op, function, trim_filename (file), line);
 383 }
 384 #endif
 385
 386 #ifdef GATHER_STATISTICS
 387 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 388 static int
 389 cmp_statistic (const void *loc1, const void *loc2)
 390 {
 391   const struct vec_descriptor *const l1 =
 392     *(const struct vec_descriptor *const *) loc1;
 393   const struct vec_descriptor *const l2 =
 394     *(const struct vec_descriptor *const *) loc2;
 395   long diff;
 396   diff = l1->allocated - l2->allocated;
 397   if (!diff)
 398     diff = l1->peak - l2->peak;
 399   if (!diff)
 400     diff = l1->times - l2->times;
 401   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 402 }
 403 /* Collect array of the descriptors from hashtable.  */
 404 static struct vec_descriptor **loc_array;
 405 static int
 406 add_statistics (void **slot, void *b)
 407 {
 408   int *n = (int *)b;
 409   loc_array[*n] = (struct vec_descriptor *) *slot;
 410   (*n)++;
 411   return 1;
 412 }
 413
 414 /* Dump per-site memory statistics.  */
 415 #endif
 416 void
 417 dump_vec_loc_statistics (void)
 418 {
 419 #ifdef GATHER_STATISTICS
 420   int nentries = 0;
 421   char s[4096];
 422   size_t allocated = 0;
 423   size_t times = 0;
 424   int i;
 425
 426   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 427   fprintf (stderr, "Heap vectors:\n");
 428   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 429            "source location", "Leak", "Peak", "Times");
 430   fprintf (stderr, "-------------------------------------------------------\n");
 431   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 432   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 433   for (i = 0; i < nentries; i++)
 434     {
 435       struct vec_descriptor *d = loc_array[i];
 436       allocated += d->allocated;
 437       times += d->times;
 438     }
 439   for (i = 0; i < nentries; i++)
 440     {
 441       struct vec_descriptor *d = loc_array[i];
 442       const char *s1 = d->file;
 443       const char *s2;
 444       while ((s2 = strstr (s1, "gcc/")))
 445         s1 = s2 + 4;
 446       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 447       s[48] = 0;
 448       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 449                (long)d->allocated,
 450                (d->allocated) * 100.0 / allocated,
 451                (long)d->peak,
 452                (long)d->times,
 453                (d->times) * 100.0 / times);
 454     }
 455   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 456            "Total", (long)allocated, (long)times);
 457   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 458            "source location", "Leak", "Peak", "Times");
 459   fprintf (stderr, "-------------------------------------------------------\n");
 460 #endif
 461 }