gcc/vec.c

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Nathan Sidwell <nathan@codesourcery.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 /* Store information about each particular vector.  */
  38 struct vec_descriptor
  39 {
  40   const char *function;
  41   const char *file;
  42   int line;
  43   size_t allocated;
  44   size_t times;
  45   size_t peak;
  46 };
  47
  48
  49 /* Hashtable mapping vec addresses to descriptors.  */
  50 static htab_t vec_desc_hash;
  51
  52 /* Hashtable helpers.  */
  53 static hashval_t
  54 hash_descriptor (const void *p)
  55 {
  56   const struct vec_descriptor *const d =
  57     (const struct vec_descriptor *) p;
  58   return htab_hash_pointer (d->file) + d->line;
  59 }
  60 static int
  61 eq_descriptor (const void *p1, const void *p2)
  62 {
  63   const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
  64   const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
  65   return d->file == l->file && d->function == l->function && d->line == l->line;
  66 }
  67
  68 /* Hashtable converting address of allocated field to loc descriptor.  */
  69 static htab_t ptr_hash;
  70 struct ptr_hash_entry
  71 {
  72   void *ptr;
  73   struct vec_descriptor *loc;
  74   size_t allocated;
  75 };
  76
  77 /* Hash table helpers functions.  */
  78 static hashval_t
  79 hash_ptr (const void *p)
  80 {
  81   const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
  82
  83   return htab_hash_pointer (d->ptr);
  84 }
  85
  86 static int
  87 eq_ptr (const void *p1, const void *p2)
  88 {
  89   const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
  90
  91   return (p->ptr == p2);
  92 }
  93
  94 /* Return descriptor for given call site, create new one if needed.  */
  95 static struct vec_descriptor *
  96 vec_descriptor (const char *name, int line, const char *function)
  97 {
  98   struct vec_descriptor loc;
  99   struct vec_descriptor **slot;
 100
 101   loc.file = name;
 102   loc.line = line;
 103   loc.function = function;
 104   if (!vec_desc_hash)
 105     vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
 106
 107   slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
 108                                                     INSERT);
 109   if (*slot)
 110     return *slot;
 111   *slot = XCNEW (struct vec_descriptor);
 112   (*slot)->file = name;
 113   (*slot)->line = line;
 114   (*slot)->function = function;
 115   (*slot)->allocated = 0;
 116   (*slot)->peak = 0;
 117   return *slot;
 118 }
 119
 120 /* Account the overhead.  */
 121 static void
 122 register_overhead (struct vec_prefix *ptr, size_t size,
 123                    const char *name, int line, const char *function)
 124 {
 125   struct vec_descriptor *loc = vec_descriptor (name, line, function);
 126   struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
 127   PTR *slot;
 128
 129   p->ptr = ptr;
 130   p->loc = loc;
 131   p->allocated = size;
 132   if (!ptr_hash)
 133     ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
 134   slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
 135   gcc_assert (!*slot);
 136   *slot = p;
 137
 138   loc->allocated += size;
 139   if (loc->peak < loc->allocated)
 140     loc->peak += loc->allocated;
 141   loc->times++;
 142 }
 143
 144 /* Notice that the pointer has been freed.  */
 145 static void
 146 free_overhead (struct vec_prefix *ptr)
 147 {
 148   PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
 149                                         NO_INSERT);
 150   struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
 151   p->loc->allocated -= p->allocated;
 152   htab_clear_slot (ptr_hash, slot);
 153   free (p);
 154 }
 155
 156 void
 157 vec_heap_free (void *ptr)
 158 {
 159   if (GATHER_STATISTICS)
 160     free_overhead ((struct vec_prefix *)ptr);
 161   free (ptr);
 162 }
 163
 164 /* Calculate the new ALLOC value, making sure that RESERVE slots are
 165    free.  If EXACT grow exactly, otherwise grow exponentially.  */
 166
 167 static inline unsigned
 168 calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
 169 {
 170   unsigned alloc = 0;
 171   unsigned num = 0;
 172
 173   gcc_assert (reserve >= 0);
 174
 175   if (pfx)
 176     {
 177       alloc = pfx->alloc;
 178       num = pfx->num;
 179     }
 180   else if (!reserve)
 181     /* If there's no prefix, and we've not requested anything, then we
 182        will create a NULL vector.  */
 183     return 0;
 184
 185   /* We must have run out of room.  */
 186   gcc_assert (alloc - num < (unsigned) reserve);
 187
 188   if (exact)
 189     /* Exact size.  */
 190     alloc = num + reserve;
 191   else
 192     {
 193       /* Exponential growth. */
 194       if (!alloc)
 195         alloc = 4;
 196       else if (alloc < 16)
 197         /* Double when small.  */
 198         alloc = alloc * 2;
 199       else
 200         /* Grow slower when large.  */
 201         alloc = (alloc * 3 / 2);
 202
 203       /* If this is still too small, set it to the right size. */
 204       if (alloc < num + reserve)
 205         alloc = num + reserve;
 206     }
 207   return alloc;
 208 }
 209
 210 /* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
 211    exactly, else grow exponentially.  As a special case, if VEC is
 212    NULL and RESERVE is 0, no vector will be created.  The vector's
 213    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 214    sized elements.  */
 215
 216 static void *
 217 vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
 218                     bool exact MEM_STAT_DECL)
 219 {
 220   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 221   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 222   size_t size;
 223
 224   if (!alloc)
 225     {
 226       if (pfx)
 227         ggc_free (pfx);
 228       return NULL;
 229     }
 230
 231   /* Calculate the amount of space we want.  */
 232   size = vec_offset + alloc * elt_size;
 233   /* Ask the allocator how much space it will really give us.  */
 234   size = ggc_round_alloc_size (size);
 235   /* Adjust the number of slots accordingly.  */
 236   alloc = (size - vec_offset) / elt_size;
 237   /* And finally, recalculate the amount of space we ask for.  */
 238   size = vec_offset + alloc * elt_size;
 239
 240   vec = ggc_realloc_stat (vec, size PASS_MEM_STAT);
 241
 242   ((struct vec_prefix *)vec)->alloc = alloc;
 243   if (!pfx)
 244     ((struct vec_prefix *)vec)->num = 0;
 245
 246   return vec;
 247 }
 248
 249 /* Ensure there are at least RESERVE free slots in VEC, growing
 250    exponentially.  If RESERVE < 0 grow exactly, else grow
 251    exponentially.  As a special case, if VEC is NULL, and RESERVE is
 252    0, no vector will be created. */
 253
 254 void *
 255 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 256 {
 257   return vec_gc_o_reserve_1 (vec, reserve,
 258                              sizeof (struct vec_prefix),
 259                              sizeof (void *), false
 260                              PASS_MEM_STAT);
 261 }
 262
 263 /* Ensure there are at least RESERVE free slots in VEC, growing
 264    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
 265    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
 266    created. */
 267
 268 void *
 269 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 270 {
 271   return vec_gc_o_reserve_1 (vec, reserve,
 272                              sizeof (struct vec_prefix),
 273                              sizeof (void *), true
 274                              PASS_MEM_STAT);
 275 }
 276
 277 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
 278    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 279    sized elements.  */
 280
 281 void *
 282 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 283                   MEM_STAT_DECL)
 284 {
 285   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 286                              PASS_MEM_STAT);
 287 }
 288
 289 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
 290    vector's trailing array is at VEC_OFFSET offset and consists of
 291    ELT_SIZE sized elements.  */
 292
 293 void *
 294 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 295                         size_t elt_size MEM_STAT_DECL)
 296 {
 297   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 298                              PASS_MEM_STAT);
 299 }
 300
 301 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
 302
 303 static void *
 304 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 305                       size_t elt_size, bool exact MEM_STAT_DECL)
 306 {
 307   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 308   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 309
 310   if (!alloc)
 311     {
 312       if (pfx)
 313         vec_heap_free (pfx);
 314       return NULL;
 315     }
 316
 317   if (GATHER_STATISTICS && vec)
 318     free_overhead (pfx);
 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   if (GATHER_STATISTICS && vec)
 325     register_overhead ((struct vec_prefix *)vec,
 326                        vec_offset + alloc * elt_size FINAL_PASS_MEM_STAT);
 327
 328   return vec;
 329 }
 330
 331 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 332
 333 void *
 334 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 335 {
 336   return vec_heap_o_reserve_1 (vec, reserve,
 337                                sizeof (struct vec_prefix),
 338                                sizeof (void *), false
 339                                PASS_MEM_STAT);
 340 }
 341
 342 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
 343
 344 void *
 345 vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 346 {
 347   return vec_heap_o_reserve_1 (vec, reserve,
 348                                sizeof (struct vec_prefix),
 349                                sizeof (void *), true
 350                                PASS_MEM_STAT);
 351 }
 352
 353 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 354
 355 void *
 356 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 357                     MEM_STAT_DECL)
 358 {
 359   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 360                                PASS_MEM_STAT);
 361 }
 362
 363 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
 364
 365 void *
 366 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 367                           size_t elt_size MEM_STAT_DECL)
 368 {
 369   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 370                                PASS_MEM_STAT);
 371 }
 372
 373 /* Stack vectors are a little different.  VEC_alloc turns into a call
 374    to vec_stack_p_reserve_exact1 and passes in space allocated via a
 375    call to alloca.  We record that pointer so that we know that we
 376    shouldn't free it.  If the vector is resized, we resize it on the
 377    heap.  We record the pointers in a vector and search it in LIFO
 378    order--i.e., we look for the newest stack vectors first.  We don't
 379    expect too many stack vectors at any one level, and searching from
 380    the end should normally be efficient even if they are used in a
 381    recursive function.  */
 382
 383 typedef void *void_p;
 384 DEF_VEC_P(void_p);
 385 DEF_VEC_ALLOC_P(void_p,heap);
 386
 387 static VEC(void_p,heap) *stack_vecs;
 388
 389 /* Allocate a vector which uses alloca for the initial allocation.
 390    SPACE is space allocated using alloca, ALLOC is the number of
 391    entries allocated.  */
 392
 393 void *
 394 vec_stack_p_reserve_exact_1 (int alloc, void *space)
 395 {
 396   struct vec_prefix *pfx = (struct vec_prefix *) space;
 397
 398   VEC_safe_push (void_p, heap, stack_vecs, space);
 399
 400   pfx->num = 0;
 401   pfx->alloc = alloc;
 402
 403   return space;
 404 }
 405
 406 /* Grow a vector allocated using alloca.  When this happens, we switch
 407    back to heap allocation.  We remove the vector from stack_vecs, if
 408    it is there, since we no longer need to avoid freeing it.  */
 409
 410 static void *
 411 vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 412                        size_t elt_size, bool exact MEM_STAT_DECL)
 413 {
 414   bool found;
 415   unsigned int ix;
 416   void *newvec;
 417
 418   found = false;
 419   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
 420     {
 421       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
 422         {
 423           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
 424           found = true;
 425           break;
 426         }
 427     }
 428
 429   if (!found)
 430     {
 431       /* VEC is already on the heap.  */
 432       return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
 433                                    exact PASS_MEM_STAT);
 434     }
 435
 436   /* Move VEC to the heap.  */
 437   reserve += ((struct vec_prefix *) vec)->num;
 438   newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
 439                                  exact PASS_MEM_STAT);
 440   if (newvec && vec)
 441     {
 442       ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
 443       memcpy (((struct vec_prefix *) newvec)+1,
 444               ((struct vec_prefix *) vec)+1,
 445               ((struct vec_prefix *) vec)->num * elt_size);
 446     }
 447   return newvec;
 448 }
 449
 450 /* Grow a vector allocated on the stack.  */
 451
 452 void *
 453 vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 454 {
 455   return vec_stack_o_reserve_1 (vec, reserve,
 456                                 sizeof (struct vec_prefix),
 457                                 sizeof (void *), false
 458                                 PASS_MEM_STAT);
 459 }
 460
 461 /* Exact version of vec_stack_p_reserve.  */
 462
 463 void *
 464 vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 465 {
 466   return vec_stack_o_reserve_1 (vec, reserve,
 467                                 sizeof (struct vec_prefix),
 468                                 sizeof (void *), true
 469                                 PASS_MEM_STAT);
 470 }
 471
 472 /* Like vec_stack_p_reserve, but for objects.  */
 473
 474 void *
 475 vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
 476                      size_t elt_size MEM_STAT_DECL)
 477 {
 478   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 479                                 PASS_MEM_STAT);
 480 }
 481
 482 /* Like vec_stack_p_reserve_exact, but for objects.  */
 483
 484 void *
 485 vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 486                             size_t elt_size MEM_STAT_DECL)
 487 {
 488   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 489                                 PASS_MEM_STAT);
 490 }
 491
 492 /* Free a vector allocated on the stack.  Don't actually free it if we
 493    find it in the hash table.  */
 494
 495 void
 496 vec_stack_free (void *vec)
 497 {
 498   unsigned int ix;
 499
 500   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
 501     {
 502       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
 503         {
 504           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
 505           return;
 506         }
 507     }
 508
 509   /* VEC was not on the list of vecs allocated on the stack, so it
 510      must be allocated on the heap.  */
 511   vec_heap_free (vec);
 512 }
 513
 514 #if ENABLE_CHECKING
 515 /* Issue a vector domain error, and then fall over.  */
 516
 517 void
 518 vec_assert_fail (const char *op, const char *struct_name,
 519                  const char *file, unsigned int line, const char *function)
 520 {
 521   internal_error ("vector %s %s domain error, in %s at %s:%u",
 522                   struct_name, op, function, trim_filename (file), line);
 523 }
 524 #endif
 525
 526 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 527 static int
 528 cmp_statistic (const void *loc1, const void *loc2)
 529 {
 530   const struct vec_descriptor *const l1 =
 531     *(const struct vec_descriptor *const *) loc1;
 532   const struct vec_descriptor *const l2 =
 533     *(const struct vec_descriptor *const *) loc2;
 534   long diff;
 535   diff = l1->allocated - l2->allocated;
 536   if (!diff)
 537     diff = l1->peak - l2->peak;
 538   if (!diff)
 539     diff = l1->times - l2->times;
 540   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 541 }
 542 /* Collect array of the descriptors from hashtable.  */
 543 static struct vec_descriptor **loc_array;
 544 static int
 545 add_statistics (void **slot, void *b)
 546 {
 547   int *n = (int *)b;
 548   loc_array[*n] = (struct vec_descriptor *) *slot;
 549   (*n)++;
 550   return 1;
 551 }
 552
 553 /* Dump per-site memory statistics.  */
 554
 555 void
 556 dump_vec_loc_statistics (void)
 557 {
 558   int nentries = 0;
 559   char s[4096];
 560   size_t allocated = 0;
 561   size_t times = 0;
 562   int i;
 563
 564   if (! GATHER_STATISTICS)
 565     return;
 566
 567   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 568   fprintf (stderr, "Heap vectors:\n");
 569   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 570            "source location", "Leak", "Peak", "Times");
 571   fprintf (stderr, "-------------------------------------------------------\n");
 572   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 573   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 574   for (i = 0; i < nentries; i++)
 575     {
 576       struct vec_descriptor *d = loc_array[i];
 577       allocated += d->allocated;
 578       times += d->times;
 579     }
 580   for (i = 0; i < nentries; i++)
 581     {
 582       struct vec_descriptor *d = loc_array[i];
 583       const char *s1 = d->file;
 584       const char *s2;
 585       while ((s2 = strstr (s1, "gcc/")))
 586         s1 = s2 + 4;
 587       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 588       s[48] = 0;
 589       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 590                (long)d->allocated,
 591                (d->allocated) * 100.0 / allocated,
 592                (long)d->peak,
 593                (long)d->times,
 594                (d->times) * 100.0 / times);
 595     }
 596   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 597            "Total", (long)allocated, (long)times);
 598   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 599            "source location", "Leak", "Peak", "Times");
 600   fprintf (stderr, "-------------------------------------------------------\n");
 601 }