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