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