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 } 608