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