vec.c 15.9 KB
Newer Older
1
/* Vector API for GNU compiler.
2 3
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
   Free Software Foundation, Inc.
4 5 6 7 8 9
   Contributed by Nathan Sidwell <nathan@codesourcery.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
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 12 13 14 15 16 17 18
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
19 20
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */
21

22 23 24 25 26
/* This file is compiled twice: once for the generator programs
   once for the compiler.  */
#ifdef GENERATOR_FILE
#include "bconfig.h"
#else
27
#include "config.h"
28 29
#endif

30 31 32 33
#include "system.h"
#include "ggc.h"
#include "vec.h"
#include "coretypes.h"
34
#include "diagnostic-core.h"
35
#include "hashtab.h"
36

H.J. Lu committed
37
struct vec_prefix
38
{
39 40
  unsigned num;
  unsigned alloc;
41 42 43
  void *vec[1];
};

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

#ifdef GATHER_STATISTICS

/* Store information about each particular vector.  */
struct vec_descriptor
{
  const char *function;
  const char *file;
  int line;
  size_t allocated;
  size_t times;
  size_t peak;
};


/* Hashtable mapping vec addresses to descriptors.  */
static htab_t vec_desc_hash;

/* Hashtable helpers.  */
static hashval_t
hash_descriptor (const void *p)
{
  const struct vec_descriptor *const d =
    (const struct vec_descriptor *) p;
  return htab_hash_pointer (d->file) + d->line;
}
static int
eq_descriptor (const void *p1, const void *p2)
{
  const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
  const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
  return d->file == l->file && d->function == l->function && d->line == l->line;
}

/* Hashtable converting address of allocated field to loc descriptor.  */
static htab_t ptr_hash;
struct ptr_hash_entry
{
  void *ptr;
  struct vec_descriptor *loc;
  size_t allocated;
};

/* Hash table helpers functions.  */
static hashval_t
hash_ptr (const void *p)
{
  const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;

  return htab_hash_pointer (d->ptr);
}

static int
eq_ptr (const void *p1, const void *p2)
{
  const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;

  return (p->ptr == p2);
}

/* Return descriptor for given call site, create new one if needed.  */
static struct vec_descriptor *
vec_descriptor (const char *name, int line, const char *function)
{
  struct vec_descriptor loc;
  struct vec_descriptor **slot;

  loc.file = name;
  loc.line = line;
  loc.function = function;
  if (!vec_desc_hash)
    vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);

117 118
  slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
						    INSERT);
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  if (*slot)
    return *slot;
  *slot = XCNEW (struct vec_descriptor);
  (*slot)->file = name;
  (*slot)->line = line;
  (*slot)->function = function;
  (*slot)->allocated = 0;
  (*slot)->peak = 0;
  return *slot;
}

/* Account the overhead.  */
static void
register_overhead (struct vec_prefix *ptr, size_t size,
		   const char *name, int line, const char *function)
{
  struct vec_descriptor *loc = vec_descriptor (name, line, function);
  struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
  PTR *slot;

  p->ptr = ptr;
  p->loc = loc;
  p->allocated = size;
  if (!ptr_hash)
    ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
  slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
  gcc_assert (!*slot);
  *slot = p;

  loc->allocated += size;
  if (loc->peak < loc->allocated)
    loc->peak += loc->allocated;
  loc->times++;
}

/* Notice that the pointer has been freed.  */
static void
free_overhead (struct vec_prefix *ptr)
{
  PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
					NO_INSERT);
  struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
  p->loc->allocated -= p->allocated;
  htab_clear_slot (ptr_hash, slot);
  free (p);
}

void
vec_heap_free (void *ptr)
{
  free_overhead ((struct vec_prefix *)ptr);
  free (ptr);
}
#endif

174 175
/* Calculate the new ALLOC value, making sure that RESERVE slots are
   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 181 182
{
  unsigned alloc = 0;
  unsigned num = 0;

183 184
  gcc_assert (reserve >= 0);

185 186 187 188 189 190 191 192 193
  if (pfx)
    {
      alloc = pfx->alloc;
      num = pfx->num;
    }
  else if (!reserve)
    /* If there's no prefix, and we've not requested anything, then we
       will create a NULL vector.  */
    return 0;
H.J. Lu committed
194

195
  /* We must have run out of room.  */
196
  gcc_assert (alloc - num < (unsigned) reserve);
H.J. Lu committed
197

198
  if (exact)
199
    /* Exact size.  */
200
    alloc = num + reserve;
201 202 203 204 205 206 207 208 209 210 211
  else
    {
      /* Exponential growth. */
      if (!alloc)
	alloc = 4;
      else if (alloc < 16)
	/* Double when small.  */
	alloc = alloc * 2;
      else
	/* Grow slower when large.  */
	alloc = (alloc * 3 / 2);
H.J. Lu committed
212

213 214 215 216 217 218 219
      /* If this is still too small, set it to the right size. */
      if (alloc < num + reserve)
	alloc = num + reserve;
    }
  return alloc;
}

220 221 222 223 224
/* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
   exactly, else grow exponentially.  As a special case, if VEC is
   NULL and RESERVE is 0, no vector will be created.  The vector's
   trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
   sized elements.  */
225

226 227 228
static void *
vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
		    bool exact MEM_STAT_DECL)
229
{
230
  struct vec_prefix *pfx = (struct vec_prefix *) vec;
231
  unsigned alloc = calculate_allocation (pfx, reserve, exact);
H.J. Lu committed
232

233
  if (!alloc)
234 235 236 237 238
    {
      if (pfx)
        ggc_free (pfx);
      return NULL;
    }
H.J. Lu committed
239

240 241 242 243
  vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
  ((struct vec_prefix *)vec)->alloc = alloc;
  if (!pfx)
    ((struct vec_prefix *)vec)->num = 0;
H.J. Lu committed
244

245 246 247
  return vec;
}

248 249 250 251
/* Ensure there are at least RESERVE free slots in VEC, growing
   exponentially.  If RESERVE < 0 grow exactly, else grow
   exponentially.  As a special case, if VEC is NULL, and RESERVE is
   0, no vector will be created. */
252 253

void *
254
vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
255
{
256 257 258
  return vec_gc_o_reserve_1 (vec, reserve,
			     offsetof (struct vec_prefix, vec),
			     sizeof (void *), false
259 260 261
			     PASS_MEM_STAT);
}

262 263 264 265
/* Ensure there are at least RESERVE free slots in VEC, growing
   exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
   a special case, if VEC is NULL, and RESERVE is 0, no vector will be
   created. */
266 267

void *
268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
{
  return vec_gc_o_reserve_1 (vec, reserve,
			     offsetof (struct vec_prefix, vec),
			     sizeof (void *), true
			     PASS_MEM_STAT);
}

/* As for vec_gc_p_reserve, but for object vectors.  The vector's
   trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
   sized elements.  */

void *
vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
		  MEM_STAT_DECL)
{
  return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
			     PASS_MEM_STAT);
}

/* As for vec_gc_p_reserve_exact, but for object vectors.  The
   vector's trailing array is at VEC_OFFSET offset and consists of
   ELT_SIZE sized elements.  */

void *
vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
			size_t elt_size MEM_STAT_DECL)
{
  return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
			     PASS_MEM_STAT);
}

/* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */

static void *
vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
		      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 312 313 314 315 316 317 318 319
    {
      if (pfx)
        vec_heap_free (pfx);
      return NULL;
    }

#ifdef GATHER_STATISTICS
  if (vec)
    free_overhead (pfx);
#endif
H.J. Lu committed
320

321 322 323 324
  vec = xrealloc (vec, vec_offset + alloc * elt_size);
  ((struct vec_prefix *)vec)->alloc = alloc;
  if (!pfx)
    ((struct vec_prefix *)vec)->num = 0;
325 326 327 328 329
#ifdef GATHER_STATISTICS
  if (vec)
    register_overhead ((struct vec_prefix *)vec,
    		       vec_offset + alloc * elt_size PASS_MEM_STAT);
#endif
H.J. Lu committed
330

331 332 333
  return vec;
}

334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375
/* As for vec_gc_p_reserve, but for heap allocated vectors.  */

void *
vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
{
  return vec_heap_o_reserve_1 (vec, reserve,
			       offsetof (struct vec_prefix, vec),
			       sizeof (void *), false
			       PASS_MEM_STAT);
}

/* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */

void *
vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
{
  return vec_heap_o_reserve_1 (vec, reserve,
			       offsetof (struct vec_prefix, vec),
			       sizeof (void *), true
			       PASS_MEM_STAT);
}

/* As for vec_gc_o_reserve, but for heap allocated vectors.  */

void *
vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
		    MEM_STAT_DECL)
{
  return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
			       PASS_MEM_STAT);
}

/* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */

void *
vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
			  size_t elt_size MEM_STAT_DECL)
{
  return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
			       PASS_MEM_STAT);
}

376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516
/* Stack vectors are a little different.  VEC_alloc turns into a call
   to vec_stack_p_reserve_exact1 and passes in space allocated via a
   call to alloca.  We record that pointer so that we know that we
   shouldn't free it.  If the vector is resized, we resize it on the
   heap.  We record the pointers in a vector and search it in LIFO
   order--i.e., we look for the newest stack vectors first.  We don't
   expect too many stack vectors at any one level, and searching from
   the end should normally be efficient even if they are used in a
   recursive function.  */

typedef void *void_p;
DEF_VEC_P(void_p);
DEF_VEC_ALLOC_P(void_p,heap);

static VEC(void_p,heap) *stack_vecs;

/* Allocate a vector which uses alloca for the initial allocation.
   SPACE is space allocated using alloca, ALLOC is the number of
   entries allocated.  */

void *
vec_stack_p_reserve_exact_1 (int alloc, void *space)
{
  struct vec_prefix *pfx = (struct vec_prefix *) space;

  VEC_safe_push (void_p, heap, stack_vecs, space);

  pfx->num = 0;
  pfx->alloc = alloc;

  return space;
}

/* Grow a vector allocated using alloca.  When this happens, we switch
   back to heap allocation.  We remove the vector from stack_vecs, if
   it is there, since we no longer need to avoid freeing it.  */

static void *
vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
		       size_t elt_size, bool exact MEM_STAT_DECL)
{
  bool found;
  unsigned int ix;
  void *newvec;

  found = false;
  for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
    {
      if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
	{
	  VEC_unordered_remove (void_p, stack_vecs, ix - 1);
	  found = true;
	  break;
	}
    }

  if (!found)
    {
      /* VEC is already on the heap.  */
      return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
				   exact PASS_MEM_STAT);
    }

  /* Move VEC to the heap.  */
  reserve += ((struct vec_prefix *) vec)->num;
  newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
				 exact PASS_MEM_STAT);
  if (newvec && vec)
    {
      ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
      memcpy (((struct vec_prefix *) newvec)->vec,
	      ((struct vec_prefix *) vec)->vec,
	      ((struct vec_prefix *) vec)->num * elt_size);
    }
  return newvec;
}

/* Grow a vector allocated on the stack.  */

void *
vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
{
  return vec_stack_o_reserve_1 (vec, reserve,
				offsetof (struct vec_prefix, vec),
				sizeof (void *), false
				PASS_MEM_STAT);
}

/* Exact version of vec_stack_p_reserve.  */

void *
vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
{
  return vec_stack_o_reserve_1 (vec, reserve,
				offsetof (struct vec_prefix, vec),
				sizeof (void *), true
				PASS_MEM_STAT);
}

/* Like vec_stack_p_reserve, but for objects.  */

void *
vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
		     size_t elt_size MEM_STAT_DECL)
{
  return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
				PASS_MEM_STAT);
}

/* Like vec_stack_p_reserve_exact, but for objects.  */

void *
vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
			    size_t elt_size MEM_STAT_DECL)
{
  return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
				PASS_MEM_STAT);
}

/* Free a vector allocated on the stack.  Don't actually free it if we
   find it in the hash table.  */

void
vec_stack_free (void *vec)
{
  unsigned int ix;

  for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
    {
      if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
	{
	  VEC_unordered_remove (void_p, stack_vecs, ix - 1);
	  return;
	}
    }

  /* VEC was not on the list of vecs allocated on the stack, so it
     must be allocated on the heap.  */
  vec_heap_free (vec);
}

517 518 519 520 521
#if ENABLE_CHECKING
/* Issue a vector domain error, and then fall over.  */

void
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 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604

#ifdef GATHER_STATISTICS
/* Helper for qsort; sort descriptors by amount of memory consumed.  */
static int
cmp_statistic (const void *loc1, const void *loc2)
{
  const struct vec_descriptor *const l1 =
    *(const struct vec_descriptor *const *) loc1;
  const struct vec_descriptor *const l2 =
    *(const struct vec_descriptor *const *) loc2;
  long diff;
  diff = l1->allocated - l2->allocated;
  if (!diff)
    diff = l1->peak - l2->peak;
  if (!diff)
    diff = l1->times - l2->times;
  return diff > 0 ? 1 : diff < 0 ? -1 : 0;
}
/* Collect array of the descriptors from hashtable.  */
static struct vec_descriptor **loc_array;
static int
add_statistics (void **slot, void *b)
{
  int *n = (int *)b;
  loc_array[*n] = (struct vec_descriptor *) *slot;
  (*n)++;
  return 1;
}

/* Dump per-site memory statistics.  */
#endif
void
dump_vec_loc_statistics (void)
{
#ifdef GATHER_STATISTICS
  int nentries = 0;
  char s[4096];
  size_t allocated = 0;
  size_t times = 0;
  int i;

  loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
  fprintf (stderr, "Heap vectors:\n");
  fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
	   "source location", "Leak", "Peak", "Times");
  fprintf (stderr, "-------------------------------------------------------\n");
  htab_traverse (vec_desc_hash, add_statistics, &nentries);
  qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
  for (i = 0; i < nentries; i++)
    {
      struct vec_descriptor *d = loc_array[i];
      allocated += d->allocated;
      times += d->times;
    }
  for (i = 0; i < nentries; i++)
    {
      struct vec_descriptor *d = loc_array[i];
      const char *s1 = d->file;
      const char *s2;
      while ((s2 = strstr (s1, "gcc/")))
	s1 = s2 + 4;
      sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
      s[48] = 0;
      fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
	       (long)d->allocated,
	       (d->allocated) * 100.0 / allocated,
	       (long)d->peak,
	       (long)d->times,
	       (d->times) * 100.0 / times);
    }
  fprintf (stderr, "%-48s %10ld                        %10ld\n",
	   "Total", (long)allocated, (long)times);
  fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
	   "source location", "Leak", "Peak", "Times");
  fprintf (stderr, "-------------------------------------------------------\n");
#endif
}