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
 225   if (!alloc)
 226     {
 227       if (pfx)
 228         ggc_free (pfx);
 229       return NULL;
 230     }
 231
 232   vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
 233   ((struct vec_prefix *)vec)->alloc = alloc;
 234   if (!pfx)
 235     ((struct vec_prefix *)vec)->num = 0;
 236
 237   return vec;
 238 }
 239
 240 /* Ensure there are at least RESERVE free slots in VEC, growing
 241    exponentially.  If RESERVE < 0 grow exactly, else grow
 242    exponentially.  As a special case, if VEC is NULL, and RESERVE is
 243    0, no vector will be created. */
 244
 245 void *
 246 vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 247 {
 248   return vec_gc_o_reserve_1 (vec, reserve,
 249                              sizeof (struct vec_prefix),
 250                              sizeof (void *), false
 251                              PASS_MEM_STAT);
 252 }
 253
 254 /* Ensure there are at least RESERVE free slots in VEC, growing
 255    exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
 256    a special case, if VEC is NULL, and RESERVE is 0, no vector will be
 257    created. */
 258
 259 void *
 260 vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
 261 {
 262   return vec_gc_o_reserve_1 (vec, reserve,
 263                              sizeof (struct vec_prefix),
 264                              sizeof (void *), true
 265                              PASS_MEM_STAT);
 266 }
 267
 268 /* As for vec_gc_p_reserve, but for object vectors.  The vector's
 269    trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
 270    sized elements.  */
 271
 272 void *
 273 vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 274                   MEM_STAT_DECL)
 275 {
 276   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 277                              PASS_MEM_STAT);
 278 }
 279
 280 /* As for vec_gc_p_reserve_exact, but for object vectors.  The
 281    vector's trailing array is at VEC_OFFSET offset and consists of
 282    ELT_SIZE sized elements.  */
 283
 284 void *
 285 vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 286                         size_t elt_size MEM_STAT_DECL)
 287 {
 288   return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 289                              PASS_MEM_STAT);
 290 }
 291
 292 /* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
 293
 294 static void *
 295 vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 296                       size_t elt_size, bool exact MEM_STAT_DECL)
 297 {
 298   struct vec_prefix *pfx = (struct vec_prefix *) vec;
 299   unsigned alloc = calculate_allocation (pfx, reserve, exact);
 300
 301   if (!alloc)
 302     {
 303       if (pfx)
 304         vec_heap_free (pfx);
 305       return NULL;
 306     }
 307
 308 #ifdef GATHER_STATISTICS
 309   if (vec)
 310     free_overhead (pfx);
 311 #endif
 312
 313   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 314   ((struct vec_prefix *)vec)->alloc = alloc;
 315   if (!pfx)
 316     ((struct vec_prefix *)vec)->num = 0;
 317 #ifdef GATHER_STATISTICS
 318   if (vec)
 319     register_overhead ((struct vec_prefix *)vec,
 320                        vec_offset + alloc * elt_size PASS_MEM_STAT);
 321 #endif
 322
 323   return vec;
 324 }
 325
 326 /* As for vec_gc_p_reserve, but for heap allocated vectors.  */
 327
 328 void *
 329 vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 330 {
 331   return vec_heap_o_reserve_1 (vec, reserve,
 332                                sizeof (struct vec_prefix),
 333                                sizeof (void *), false
 334                                PASS_MEM_STAT);
 335 }
 336
 337 /* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
 338
 339 void *
 340 vec_heap_p_reserve_exact (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 *), true
 345                                PASS_MEM_STAT);
 346 }
 347
 348 /* As for vec_gc_o_reserve, but for heap allocated vectors.  */
 349
 350 void *
 351 vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
 352                     MEM_STAT_DECL)
 353 {
 354   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 355                                PASS_MEM_STAT);
 356 }
 357
 358 /* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
 359
 360 void *
 361 vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 362                           size_t elt_size MEM_STAT_DECL)
 363 {
 364   return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 365                                PASS_MEM_STAT);
 366 }
 367
 368 /* Stack vectors are a little different.  VEC_alloc turns into a call
 369    to vec_stack_p_reserve_exact1 and passes in space allocated via a
 370    call to alloca.  We record that pointer so that we know that we
 371    shouldn't free it.  If the vector is resized, we resize it on the
 372    heap.  We record the pointers in a vector and search it in LIFO
 373    order--i.e., we look for the newest stack vectors first.  We don't
 374    expect too many stack vectors at any one level, and searching from
 375    the end should normally be efficient even if they are used in a
 376    recursive function.  */
 377
 378 typedef void *void_p;
 379 DEF_VEC_P(void_p);
 380 DEF_VEC_ALLOC_P(void_p,heap);
 381
 382 static VEC(void_p,heap) *stack_vecs;
 383
 384 /* Allocate a vector which uses alloca for the initial allocation.
 385    SPACE is space allocated using alloca, ALLOC is the number of
 386    entries allocated.  */
 387
 388 void *
 389 vec_stack_p_reserve_exact_1 (int alloc, void *space)
 390 {
 391   struct vec_prefix *pfx = (struct vec_prefix *) space;
 392
 393   VEC_safe_push (void_p, heap, stack_vecs, space);
 394
 395   pfx->num = 0;
 396   pfx->alloc = alloc;
 397
 398   return space;
 399 }
 400
 401 /* Grow a vector allocated using alloca.  When this happens, we switch
 402    back to heap allocation.  We remove the vector from stack_vecs, if
 403    it is there, since we no longer need to avoid freeing it.  */
 404
 405 static void *
 406 vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
 407                        size_t elt_size, bool exact MEM_STAT_DECL)
 408 {
 409   bool found;
 410   unsigned int ix;
 411   void *newvec;
 412
 413   found = false;
 414   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
 415     {
 416       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
 417         {
 418           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
 419           found = true;
 420           break;
 421         }
 422     }
 423
 424   if (!found)
 425     {
 426       /* VEC is already on the heap.  */
 427       return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
 428                                    exact PASS_MEM_STAT);
 429     }
 430
 431   /* Move VEC to the heap.  */
 432   reserve += ((struct vec_prefix *) vec)->num;
 433   newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
 434                                  exact PASS_MEM_STAT);
 435   if (newvec && vec)
 436     {
 437       ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
 438       memcpy (((struct vec_prefix *) newvec)+1,
 439               ((struct vec_prefix *) vec)+1,
 440               ((struct vec_prefix *) vec)->num * elt_size);
 441     }
 442   return newvec;
 443 }
 444
 445 /* Grow a vector allocated on the stack.  */
 446
 447 void *
 448 vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
 449 {
 450   return vec_stack_o_reserve_1 (vec, reserve,
 451                                 sizeof (struct vec_prefix),
 452                                 sizeof (void *), false
 453                                 PASS_MEM_STAT);
 454 }
 455
 456 /* Exact version of vec_stack_p_reserve.  */
 457
 458 void *
 459 vec_stack_p_reserve_exact (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 *), true
 464                                 PASS_MEM_STAT);
 465 }
 466
 467 /* Like vec_stack_p_reserve, but for objects.  */
 468
 469 void *
 470 vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
 471                      size_t elt_size MEM_STAT_DECL)
 472 {
 473   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
 474                                 PASS_MEM_STAT);
 475 }
 476
 477 /* Like vec_stack_p_reserve_exact, but for objects.  */
 478
 479 void *
 480 vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
 481                             size_t elt_size MEM_STAT_DECL)
 482 {
 483   return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
 484                                 PASS_MEM_STAT);
 485 }
 486
 487 /* Free a vector allocated on the stack.  Don't actually free it if we
 488    find it in the hash table.  */
 489
 490 void
 491 vec_stack_free (void *vec)
 492 {
 493   unsigned int ix;
 494
 495   for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
 496     {
 497       if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
 498         {
 499           VEC_unordered_remove (void_p, stack_vecs, ix - 1);
 500           return;
 501         }
 502     }
 503
 504   /* VEC was not on the list of vecs allocated on the stack, so it
 505      must be allocated on the heap.  */
 506   vec_heap_free (vec);
 507 }
 508
 509 #if ENABLE_CHECKING
 510 /* Issue a vector domain error, and then fall over.  */
 511
 512 void
 513 vec_assert_fail (const char *op, const char *struct_name,
 514                  const char *file, unsigned int line, const char *function)
 515 {
 516   internal_error ("vector %s %s domain error, in %s at %s:%u",
 517                   struct_name, op, function, trim_filename (file), line);
 518 }
 519 #endif
 520
 521 #ifdef GATHER_STATISTICS
 522 /* Helper for qsort; sort descriptors by amount of memory consumed.  */
 523 static int
 524 cmp_statistic (const void *loc1, const void *loc2)
 525 {
 526   const struct vec_descriptor *const l1 =
 527     *(const struct vec_descriptor *const *) loc1;
 528   const struct vec_descriptor *const l2 =
 529     *(const struct vec_descriptor *const *) loc2;
 530   long diff;
 531   diff = l1->allocated - l2->allocated;
 532   if (!diff)
 533     diff = l1->peak - l2->peak;
 534   if (!diff)
 535     diff = l1->times - l2->times;
 536   return diff > 0 ? 1 : diff < 0 ? -1 : 0;
 537 }
 538 /* Collect array of the descriptors from hashtable.  */
 539 static struct vec_descriptor **loc_array;
 540 static int
 541 add_statistics (void **slot, void *b)
 542 {
 543   int *n = (int *)b;
 544   loc_array[*n] = (struct vec_descriptor *) *slot;
 545   (*n)++;
 546   return 1;
 547 }
 548
 549 /* Dump per-site memory statistics.  */
 550 #endif
 551 void
 552 dump_vec_loc_statistics (void)
 553 {
 554 #ifdef GATHER_STATISTICS
 555   int nentries = 0;
 556   char s[4096];
 557   size_t allocated = 0;
 558   size_t times = 0;
 559   int i;
 560
 561   loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
 562   fprintf (stderr, "Heap vectors:\n");
 563   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 564            "source location", "Leak", "Peak", "Times");
 565   fprintf (stderr, "-------------------------------------------------------\n");
 566   htab_traverse (vec_desc_hash, add_statistics, &nentries);
 567   qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
 568   for (i = 0; i < nentries; i++)
 569     {
 570       struct vec_descriptor *d = loc_array[i];
 571       allocated += d->allocated;
 572       times += d->times;
 573     }
 574   for (i = 0; i < nentries; i++)
 575     {
 576       struct vec_descriptor *d = loc_array[i];
 577       const char *s1 = d->file;
 578       const char *s2;
 579       while ((s2 = strstr (s1, "gcc/")))
 580         s1 = s2 + 4;
 581       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
 582       s[48] = 0;
 583       fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
 584                (long)d->allocated,
 585                (d->allocated) * 100.0 / allocated,
 586                (long)d->peak,
 587                (long)d->times,
 588                (d->times) * 100.0 / times);
 589     }
 590   fprintf (stderr, "%-48s %10ld                        %10ld\n",
 591            "Total", (long)allocated, (long)times);
 592   fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
 593            "source location", "Leak", "Peak", "Times");
 594   fprintf (stderr, "-------------------------------------------------------\n");
 595 #endif
 596 }