1 /* Vector API for GNU compiler. 2 Copyright (C) 2004-2013 Free Software Foundation, Inc. 3 Contributed by Nathan Sidwell <nathan@codesourcery.com> 4 Re-implemented in C++ by Diego Novillo <dnovillo@google.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 /* vNULL is an empty type with a template cast operation that returns 38 a zero-initialized vec<T, A, L> instance. Use this when you want 39 to assign nil values to new vec instances or pass a nil vector as 40 a function call argument. 41 42 We use this technique because vec<T, A, L> must be PODs (they are 43 stored in unions and passed in vararg functions), this means that 44 they cannot have ctors/dtors. */ 45 vnull vNULL; 46 47 48 /* Store information about each particular vector. */ 49 struct vec_descriptor 50 { 51 const char *function; 52 const char *file; 53 int line; 54 size_t allocated; 55 size_t times; 56 size_t peak; 57 }; 58 59 60 /* Hashtable mapping vec addresses to descriptors. */ 61 static htab_t vec_desc_hash; 62 63 /* Hashtable helpers. */ 64 static hashval_t 65 hash_descriptor (const void *p) 66 { 67 const struct vec_descriptor *const d = 68 (const struct vec_descriptor *) p; 69 return htab_hash_pointer (d->file) + d->line; 70 } 71 static int 72 eq_descriptor (const void *p1, const void *p2) 73 { 74 const struct vec_descriptor *const d = (const struct vec_descriptor *) p1; 75 const struct vec_descriptor *const l = (const struct vec_descriptor *) p2; 76 return d->file == l->file && d->function == l->function && d->line == l->line; 77 } 78 79 /* Hashtable converting address of allocated field to loc descriptor. */ 80 static htab_t ptr_hash; 81 struct ptr_hash_entry 82 { 83 void *ptr; 84 struct vec_descriptor *loc; 85 size_t allocated; 86 }; 87 88 /* Hash table helpers functions. */ 89 static hashval_t 90 hash_ptr (const void *p) 91 { 92 const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p; 93 94 return htab_hash_pointer (d->ptr); 95 } 96 97 static int 98 eq_ptr (const void *p1, const void *p2) 99 { 100 const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1; 101 102 return (p->ptr == p2); 103 } 104 105 /* Return descriptor for given call site, create new one if needed. */ 106 static struct vec_descriptor * 107 vec_descriptor (const char *name, int line, const char *function) 108 { 109 struct vec_descriptor loc; 110 struct vec_descriptor **slot; 111 112 loc.file = name; 113 loc.line = line; 114 loc.function = function; 115 if (!vec_desc_hash) 116 vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL); 117 118 slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc, 119 INSERT); 120 if (*slot) 121 return *slot; 122 *slot = XCNEW (struct vec_descriptor); 123 (*slot)->file = name; 124 (*slot)->line = line; 125 (*slot)->function = function; 126 (*slot)->allocated = 0; 127 (*slot)->peak = 0; 128 return *slot; 129 } 130 131 /* Account the overhead. */ 132 133 void 134 vec_prefix::register_overhead (size_t size, const char *name, int line, 135 const char *function) 136 { 137 struct vec_descriptor *loc = vec_descriptor (name, line, function); 138 struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry); 139 PTR *slot; 140 141 p->ptr = this; 142 p->loc = loc; 143 p->allocated = size; 144 if (!ptr_hash) 145 ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL); 146 slot = htab_find_slot_with_hash (ptr_hash, this, htab_hash_pointer (this), 147 INSERT); 148 gcc_assert (!*slot); 149 *slot = p; 150 151 loc->allocated += size; 152 if (loc->peak < loc->allocated) 153 loc->peak += loc->allocated; 154 loc->times++; 155 } 156 157 158 /* Notice that the memory allocated for the vector has been freed. */ 159 160 void 161 vec_prefix::release_overhead (void) 162 { 163 PTR *slot = htab_find_slot_with_hash (ptr_hash, this, 164 htab_hash_pointer (this), 165 NO_INSERT); 166 struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot; 167 p->loc->allocated -= p->allocated; 168 htab_clear_slot (ptr_hash, slot); 169 ::free (p); 170 } 171 172 173 /* Calculate the number of slots to reserve a vector, making sure that 174 RESERVE slots are free. If EXACT grow exactly, otherwise grow 175 exponentially. PFX is the control data for the vector. */ 176 177 unsigned 178 vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve, 179 bool exact) 180 { 181 unsigned alloc = 0; 182 unsigned num = 0; 183 184 if (pfx) 185 { 186 alloc = pfx->alloc_; 187 num = pfx->num_; 188 } 189 else if (!reserve) 190 /* If there's no vector, 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 < 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 220 /* Stack vectors are a little different. VEC_alloc turns into a call 221 to vec<T, A>::stack_reserve and passes in space allocated via a 222 call to alloca. We record that pointer so that we know that we 223 shouldn't free it. If the vector is resized, we resize it on the 224 heap. We record the pointers in a vector and search it in LIFO 225 order--i.e., we look for the newest stack vectors first. We don't 226 expect too many stack vectors at any one level, and searching from 227 the end should normally be efficient even if they are used in a 228 recursive function. */ 229 230 static vec<void *> stack_vecs; 231 232 /* Add a stack vector to STACK_VECS. */ 233 234 void 235 register_stack_vec (void *vec) 236 { 237 stack_vecs.safe_push (vec); 238 } 239 240 241 /* If VEC is registered in STACK_VECS, return its index. 242 Otherwise, return -1. */ 243 244 int 245 stack_vec_register_index (void *vec) 246 { 247 for (unsigned ix = stack_vecs.length (); ix > 0; --ix) 248 if (stack_vecs[ix - 1] == vec) 249 return static_cast<int> (ix - 1); 250 return -1; 251 } 252 253 254 /* Remove vector at slot IX from the list of registered stack vectors. */ 255 256 void 257 unregister_stack_vec (unsigned ix) 258 { 259 stack_vecs.unordered_remove (ix); 260 } 261 262 263 /* Helper for qsort; sort descriptors by amount of memory consumed. */ 264 265 static int 266 cmp_statistic (const void *loc1, const void *loc2) 267 { 268 const struct vec_descriptor *const l1 = 269 *(const struct vec_descriptor *const *) loc1; 270 const struct vec_descriptor *const l2 = 271 *(const struct vec_descriptor *const *) loc2; 272 long diff; 273 diff = l1->allocated - l2->allocated; 274 if (!diff) 275 diff = l1->peak - l2->peak; 276 if (!diff) 277 diff = l1->times - l2->times; 278 return diff > 0 ? 1 : diff < 0 ? -1 : 0; 279 } 280 281 282 /* Collect array of the descriptors from hashtable. */ 283 284 static struct vec_descriptor **loc_array; 285 static int 286 add_statistics (void **slot, void *b) 287 { 288 int *n = (int *)b; 289 loc_array[*n] = (struct vec_descriptor *) *slot; 290 (*n)++; 291 return 1; 292 } 293 294 /* Dump per-site memory statistics. */ 295 296 void 297 dump_vec_loc_statistics (void) 298 { 299 int nentries = 0; 300 char s[4096]; 301 size_t allocated = 0; 302 size_t times = 0; 303 int i; 304 305 if (! GATHER_STATISTICS) 306 return; 307 308 loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements); 309 fprintf (stderr, "Heap vectors:\n"); 310 fprintf (stderr, "\n%-48s %10s %10s %10s\n", 311 "source location", "Leak", "Peak", "Times"); 312 fprintf (stderr, "-------------------------------------------------------\n"); 313 htab_traverse (vec_desc_hash, add_statistics, &nentries); 314 qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic); 315 for (i = 0; i < nentries; i++) 316 { 317 struct vec_descriptor *d = loc_array[i]; 318 allocated += d->allocated; 319 times += d->times; 320 } 321 for (i = 0; i < nentries; i++) 322 { 323 struct vec_descriptor *d = loc_array[i]; 324 const char *s1 = d->file; 325 const char *s2; 326 while ((s2 = strstr (s1, "gcc/"))) 327 s1 = s2 + 4; 328 sprintf (s, "%s:%i (%s)", s1, d->line, d->function); 329 s[48] = 0; 330 fprintf (stderr, "%-48s %10li:%4.1f%% %10li %10li:%4.1f%% \n", s, 331 (long)d->allocated, 332 (d->allocated) * 100.0 / allocated, 333 (long)d->peak, 334 (long)d->times, 335 (d->times) * 100.0 / times); 336 } 337 fprintf (stderr, "%-48s %10ld %10ld\n", 338 "Total", (long)allocated, (long)times); 339 fprintf (stderr, "\n%-48s %10s %10s %10s\n", 340 "source location", "Leak", "Peak", "Times"); 341 fprintf (stderr, "-------------------------------------------------------\n"); 342 } 343