1 /* Vector API for GNU compiler. 2 Copyright (C) 2004-2017 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 "hash-table.h" 33 #include "selftest.h" 34 35 /* vNULL is an empty type with a template cast operation that returns 36 a zero-initialized vec<T, A, L> instance. Use this when you want 37 to assign nil values to new vec instances or pass a nil vector as 38 a function call argument. 39 40 We use this technique because vec<T, A, L> must be PODs (they are 41 stored in unions and passed in vararg functions), this means that 42 they cannot have ctors/dtors. */ 43 vnull vNULL; 44 45 /* Vector memory usage. */ 46 struct vec_usage: public mem_usage 47 { 48 /* Default constructor. */ 49 vec_usage (): m_items (0), m_items_peak (0) {} 50 51 /* Constructor. */ 52 vec_usage (size_t allocated, size_t times, size_t peak, 53 size_t items, size_t items_peak) 54 : mem_usage (allocated, times, peak), 55 m_items (items), m_items_peak (items_peak) {} 56 57 /* Comparison operator. */ 58 inline bool 59 operator< (const vec_usage &second) const 60 { 61 return (m_allocated == second.m_allocated ? 62 (m_peak == second.m_peak ? m_times < second.m_times 63 : m_peak < second.m_peak) : m_allocated < second.m_allocated); 64 } 65 66 /* Sum the usage with SECOND usage. */ 67 vec_usage 68 operator+ (const vec_usage &second) 69 { 70 return vec_usage (m_allocated + second.m_allocated, 71 m_times + second.m_times, 72 m_peak + second.m_peak, 73 m_items + second.m_items, 74 m_items_peak + second.m_items_peak); 75 } 76 77 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */ 78 inline void 79 dump (mem_location *loc, mem_usage &total) const 80 { 81 char s[4096]; 82 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (), 83 loc->m_line, loc->m_function); 84 85 s[48] = '\0'; 86 87 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s, 88 (long)m_allocated, m_allocated * 100.0 / total.m_allocated, 89 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times, 90 (long)m_items, (long)m_items_peak); 91 } 92 93 /* Dump footer. */ 94 inline void 95 dump_footer () 96 { 97 print_dash_line (); 98 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated, 99 (long)m_times, (long)m_items); 100 print_dash_line (); 101 } 102 103 /* Dump header with NAME. */ 104 static inline void 105 dump_header (const char *name) 106 { 107 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak", 108 "Times", "Leak items", "Peak items"); 109 print_dash_line (); 110 } 111 112 /* Compare wrapper used by qsort method. */ 113 static int 114 compare (const void *first, const void *second) 115 { 116 typedef std::pair<mem_location *, vec_usage *> mem_pair_t; 117 118 const mem_pair_t f = *(const mem_pair_t *)first; 119 const mem_pair_t s = *(const mem_pair_t *)second; 120 121 return (*f.second) < (*s.second); 122 } 123 124 /* Current number of items allocated. */ 125 size_t m_items; 126 /* Peak value of number of allocated items. */ 127 size_t m_items_peak; 128 }; 129 130 /* Vector memory description. */ 131 static mem_alloc_description <vec_usage> vec_mem_desc; 132 133 /* Account the overhead. */ 134 135 void 136 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements 137 MEM_STAT_DECL) 138 { 139 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false 140 FINAL_PASS_MEM_STAT); 141 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr); 142 usage->m_items += elements; 143 if (usage->m_items_peak < usage->m_items) 144 usage->m_items_peak = usage->m_items; 145 } 146 147 /* Notice that the memory allocated for the vector has been freed. */ 148 149 void 150 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor 151 MEM_STAT_DECL) 152 { 153 if (!vec_mem_desc.contains_descriptor_for_instance (ptr)) 154 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, 155 false FINAL_PASS_MEM_STAT); 156 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor); 157 } 158 159 160 /* Calculate the number of slots to reserve a vector, making sure that 161 it is of at least DESIRED size by growing ALLOC exponentially. */ 162 163 unsigned 164 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired) 165 { 166 /* We must have run out of room. */ 167 gcc_assert (alloc < desired); 168 169 /* Exponential growth. */ 170 if (!alloc) 171 alloc = 4; 172 else if (alloc < 16) 173 /* Double when small. */ 174 alloc = alloc * 2; 175 else 176 /* Grow slower when large. */ 177 alloc = (alloc * 3 / 2); 178 179 /* If this is still too small, set it to the right size. */ 180 if (alloc < desired) 181 alloc = desired; 182 return alloc; 183 } 184 185 /* Dump per-site memory statistics. */ 186 187 void 188 dump_vec_loc_statistics (void) 189 { 190 vec_mem_desc.dump (VEC_ORIGIN); 191 } 192 193 #ifndef GENERATOR_FILE 194 #if CHECKING_P 195 196 namespace selftest { 197 198 /* Selftests. */ 199 200 /* Call V.safe_push for all ints from START up to, but not including LIMIT. 201 Helper function for selftests. */ 202 203 static void 204 safe_push_range (vec <int>&v, int start, int limit) 205 { 206 for (int i = start; i < limit; i++) 207 v.safe_push (i); 208 } 209 210 /* Verify that vec::quick_push works correctly. */ 211 212 static void 213 test_quick_push () 214 { 215 auto_vec <int> v; 216 ASSERT_EQ (0, v.length ()); 217 v.reserve (3); 218 ASSERT_EQ (0, v.length ()); 219 ASSERT_TRUE (v.space (3)); 220 v.quick_push (5); 221 v.quick_push (6); 222 v.quick_push (7); 223 ASSERT_EQ (3, v.length ()); 224 ASSERT_EQ (5, v[0]); 225 ASSERT_EQ (6, v[1]); 226 ASSERT_EQ (7, v[2]); 227 } 228 229 /* Verify that vec::safe_push works correctly. */ 230 231 static void 232 test_safe_push () 233 { 234 auto_vec <int> v; 235 ASSERT_EQ (0, v.length ()); 236 v.safe_push (5); 237 v.safe_push (6); 238 v.safe_push (7); 239 ASSERT_EQ (3, v.length ()); 240 ASSERT_EQ (5, v[0]); 241 ASSERT_EQ (6, v[1]); 242 ASSERT_EQ (7, v[2]); 243 } 244 245 /* Verify that vec::truncate works correctly. */ 246 247 static void 248 test_truncate () 249 { 250 auto_vec <int> v; 251 ASSERT_EQ (0, v.length ()); 252 safe_push_range (v, 0, 10); 253 ASSERT_EQ (10, v.length ()); 254 255 v.truncate (5); 256 ASSERT_EQ (5, v.length ()); 257 } 258 259 /* Verify that vec::safe_grow_cleared works correctly. */ 260 261 static void 262 test_safe_grow_cleared () 263 { 264 auto_vec <int> v; 265 ASSERT_EQ (0, v.length ()); 266 v.safe_grow_cleared (50); 267 ASSERT_EQ (50, v.length ()); 268 ASSERT_EQ (0, v[0]); 269 ASSERT_EQ (0, v[49]); 270 } 271 272 /* Verify that vec::pop works correctly. */ 273 274 static void 275 test_pop () 276 { 277 auto_vec <int> v; 278 safe_push_range (v, 5, 20); 279 ASSERT_EQ (15, v.length ()); 280 281 int last = v.pop (); 282 ASSERT_EQ (19, last); 283 ASSERT_EQ (14, v.length ()); 284 } 285 286 /* Verify that vec::safe_insert works correctly. */ 287 288 static void 289 test_safe_insert () 290 { 291 auto_vec <int> v; 292 safe_push_range (v, 0, 10); 293 v.safe_insert (5, 42); 294 ASSERT_EQ (4, v[4]); 295 ASSERT_EQ (42, v[5]); 296 ASSERT_EQ (5, v[6]); 297 ASSERT_EQ (11, v.length ()); 298 } 299 300 /* Verify that vec::ordered_remove works correctly. */ 301 302 static void 303 test_ordered_remove () 304 { 305 auto_vec <int> v; 306 safe_push_range (v, 0, 10); 307 v.ordered_remove (5); 308 ASSERT_EQ (4, v[4]); 309 ASSERT_EQ (6, v[5]); 310 ASSERT_EQ (9, v.length ()); 311 } 312 313 /* Verify that vec::unordered_remove works correctly. */ 314 315 static void 316 test_unordered_remove () 317 { 318 auto_vec <int> v; 319 safe_push_range (v, 0, 10); 320 v.unordered_remove (5); 321 ASSERT_EQ (9, v.length ()); 322 } 323 324 /* Verify that vec::block_remove works correctly. */ 325 326 static void 327 test_block_remove () 328 { 329 auto_vec <int> v; 330 safe_push_range (v, 0, 10); 331 v.block_remove (5, 3); 332 ASSERT_EQ (3, v[3]); 333 ASSERT_EQ (4, v[4]); 334 ASSERT_EQ (8, v[5]); 335 ASSERT_EQ (9, v[6]); 336 ASSERT_EQ (7, v.length ()); 337 } 338 339 /* Comparator for use by test_qsort. */ 340 341 static int 342 reverse_cmp (const void *p_i, const void *p_j) 343 { 344 return *(const int *)p_j - *(const int *)p_i; 345 } 346 347 /* Verify that vec::qsort works correctly. */ 348 349 static void 350 test_qsort () 351 { 352 auto_vec <int> v; 353 safe_push_range (v, 0, 10); 354 v.qsort (reverse_cmp); 355 ASSERT_EQ (9, v[0]); 356 ASSERT_EQ (8, v[1]); 357 ASSERT_EQ (1, v[8]); 358 ASSERT_EQ (0, v[9]); 359 ASSERT_EQ (10, v.length ()); 360 } 361 362 /* Run all of the selftests within this file. */ 363 364 void 365 vec_c_tests () 366 { 367 test_quick_push (); 368 test_safe_push (); 369 test_truncate (); 370 test_safe_grow_cleared (); 371 test_pop (); 372 test_safe_insert (); 373 test_ordered_remove (); 374 test_unordered_remove (); 375 test_block_remove (); 376 test_qsort (); 377 } 378 379 } // namespace selftest 380 381 #endif /* #if CHECKING_P */ 382 #endif /* #ifndef GENERATOR_FILE */ 383