1 /* Vector API for GNU compiler. 2 Copyright (C) 2004-2018 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 #ifdef GENERATOR_FILE 35 #include "errors.h" 36 #else 37 #include "input.h" 38 #include "diagnostic-core.h" 39 #endif 40 41 /* vNULL is an empty type with a template cast operation that returns 42 a zero-initialized vec<T, A, L> instance. Use this when you want 43 to assign nil values to new vec instances or pass a nil vector as 44 a function call argument. 45 46 We use this technique because vec<T, A, L> must be PODs (they are 47 stored in unions and passed in vararg functions), this means that 48 they cannot have ctors/dtors. */ 49 vnull vNULL; 50 51 /* Vector memory usage. */ 52 struct vec_usage: public mem_usage 53 { 54 /* Default constructor. */ 55 vec_usage (): m_items (0), m_items_peak (0) {} 56 57 /* Constructor. */ 58 vec_usage (size_t allocated, size_t times, size_t peak, 59 size_t items, size_t items_peak) 60 : mem_usage (allocated, times, peak), 61 m_items (items), m_items_peak (items_peak) {} 62 63 /* Sum the usage with SECOND usage. */ 64 vec_usage 65 operator+ (const vec_usage &second) 66 { 67 return vec_usage (m_allocated + second.m_allocated, 68 m_times + second.m_times, 69 m_peak + second.m_peak, 70 m_items + second.m_items, 71 m_items_peak + second.m_items_peak); 72 } 73 74 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */ 75 inline void 76 dump (mem_location *loc, mem_usage &total) const 77 { 78 char s[4096]; 79 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (), 80 loc->m_line, loc->m_function); 81 82 s[48] = '\0'; 83 84 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s, 85 (long)m_allocated, m_allocated * 100.0 / total.m_allocated, 86 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times, 87 (long)m_items, (long)m_items_peak); 88 } 89 90 /* Dump footer. */ 91 inline void 92 dump_footer () 93 { 94 print_dash_line (); 95 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated, 96 (long)m_times, (long)m_items); 97 print_dash_line (); 98 } 99 100 /* Dump header with NAME. */ 101 static inline void 102 dump_header (const char *name) 103 { 104 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak", 105 "Times", "Leak items", "Peak items"); 106 print_dash_line (); 107 } 108 109 /* Current number of items allocated. */ 110 size_t m_items; 111 /* Peak value of number of allocated items. */ 112 size_t m_items_peak; 113 }; 114 115 /* Vector memory description. */ 116 static mem_alloc_description <vec_usage> vec_mem_desc; 117 118 /* Account the overhead. */ 119 120 void 121 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements 122 MEM_STAT_DECL) 123 { 124 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false 125 FINAL_PASS_MEM_STAT); 126 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr); 127 usage->m_items += elements; 128 if (usage->m_items_peak < usage->m_items) 129 usage->m_items_peak = usage->m_items; 130 } 131 132 /* Notice that the memory allocated for the vector has been freed. */ 133 134 void 135 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor 136 MEM_STAT_DECL) 137 { 138 if (!vec_mem_desc.contains_descriptor_for_instance (ptr)) 139 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, 140 false FINAL_PASS_MEM_STAT); 141 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor); 142 } 143 144 145 /* Calculate the number of slots to reserve a vector, making sure that 146 it is of at least DESIRED size by growing ALLOC exponentially. */ 147 148 unsigned 149 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired) 150 { 151 /* We must have run out of room. */ 152 gcc_assert (alloc < desired); 153 154 /* Exponential growth. */ 155 if (!alloc) 156 alloc = 4; 157 else if (alloc < 16) 158 /* Double when small. */ 159 alloc = alloc * 2; 160 else 161 /* Grow slower when large. */ 162 alloc = (alloc * 3 / 2); 163 164 /* If this is still too small, set it to the right size. */ 165 if (alloc < desired) 166 alloc = desired; 167 return alloc; 168 } 169 170 /* Dump per-site memory statistics. */ 171 172 void 173 dump_vec_loc_statistics (void) 174 { 175 vec_mem_desc.dump (VEC_ORIGIN); 176 } 177 178 #if CHECKING_P 179 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as 180 witness elements. */ 181 ATTRIBUTE_NORETURN ATTRIBUTE_COLD 182 static void 183 qsort_chk_error (const void *p1, const void *p2, const void *p3, 184 int (*cmp) (const void *, const void *)) 185 { 186 if (!p3) 187 { 188 int r1 = cmp (p1, p2), r2 = cmp (p2, p1); 189 error ("qsort comparator not anti-commutative: %d, %d", r1, r2); 190 } 191 else if (p1 == p2) 192 { 193 int r = cmp (p1, p3); 194 error ("qsort comparator non-negative on sorted output: %d", r); 195 } 196 else 197 { 198 int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3); 199 error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3); 200 } 201 internal_error ("qsort checking failed"); 202 } 203 204 /* Wrapper around qsort with checking that CMP is consistent on given input. 205 206 Strictly speaking, passing invalid (non-transitive, non-anti-commutative) 207 comparators to libc qsort can result in undefined behavior. Therefore we 208 should ideally perform consistency checks prior to invoking qsort, but in 209 order to do that optimally we'd need to sort the array ourselves beforehand 210 with a sorting routine known to be "safe". Instead, we expect that most 211 implementations in practice will still produce some permutation of input 212 array even for invalid comparators, which enables us to perform checks on 213 the output array. */ 214 void 215 qsort_chk (void *base, size_t n, size_t size, 216 int (*cmp)(const void *, const void *)) 217 { 218 (qsort) (base, n, size, cmp); 219 #if 0 220 #define LIM(n) (n) 221 #else 222 /* Limit overall time complexity to O(n log n). */ 223 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) 224 #endif 225 #define ELT(i) ((const char *) base + (i) * size) 226 #define CMP(i, j) cmp (ELT (i), ELT (j)) 227 #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp) 228 #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) 229 size_t i1, i2, i, j; 230 /* This outer loop iterates over maximum spans [i1, i2) such that 231 elements within each span compare equal to each other. */ 232 for (i1 = 0; i1 < n; i1 = i2) 233 { 234 /* Position i2 one past last element that compares equal to i1'th. */ 235 for (i2 = i1 + 1; i2 < n; i2++) 236 if (CMP (i1, i2)) 237 break; 238 else if (CMP (i2, i1)) 239 return ERR2 (i1, i2); 240 size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); 241 /* Verify that other pairs within current span compare equal. */ 242 for (i = i1 + 1; i + 1 < i2; i++) 243 for (j = i + 1; j < i1 + lim1; j++) 244 if (CMP (i, j)) 245 return ERR3 (i, i1, j); 246 else if (CMP (j, i)) 247 return ERR2 (i, j); 248 /* Verify that elements within this span compare less than 249 elements beyond the span. */ 250 for (i = i1; i < i2; i++) 251 for (j = i2; j < i2 + lim2; j++) 252 if (CMP (i, j) >= 0) 253 return ERR3 (i, i1, j); 254 else if (CMP (j, i) <= 0) 255 return ERR2 (i, j); 256 } 257 #undef ERR3 258 #undef ERR2 259 #undef CMP 260 #undef ELT 261 #undef LIM 262 } 263 #endif /* #if CHECKING_P */ 264 265 #ifndef GENERATOR_FILE 266 #if CHECKING_P 267 268 namespace selftest { 269 270 /* Selftests. */ 271 272 /* Call V.safe_push for all ints from START up to, but not including LIMIT. 273 Helper function for selftests. */ 274 275 static void 276 safe_push_range (vec <int>&v, int start, int limit) 277 { 278 for (int i = start; i < limit; i++) 279 v.safe_push (i); 280 } 281 282 /* Verify that vec::quick_push works correctly. */ 283 284 static void 285 test_quick_push () 286 { 287 auto_vec <int> v; 288 ASSERT_EQ (0, v.length ()); 289 v.reserve (3); 290 ASSERT_EQ (0, v.length ()); 291 ASSERT_TRUE (v.space (3)); 292 v.quick_push (5); 293 v.quick_push (6); 294 v.quick_push (7); 295 ASSERT_EQ (3, v.length ()); 296 ASSERT_EQ (5, v[0]); 297 ASSERT_EQ (6, v[1]); 298 ASSERT_EQ (7, v[2]); 299 } 300 301 /* Verify that vec::safe_push works correctly. */ 302 303 static void 304 test_safe_push () 305 { 306 auto_vec <int> v; 307 ASSERT_EQ (0, v.length ()); 308 v.safe_push (5); 309 v.safe_push (6); 310 v.safe_push (7); 311 ASSERT_EQ (3, v.length ()); 312 ASSERT_EQ (5, v[0]); 313 ASSERT_EQ (6, v[1]); 314 ASSERT_EQ (7, v[2]); 315 } 316 317 /* Verify that vec::truncate works correctly. */ 318 319 static void 320 test_truncate () 321 { 322 auto_vec <int> v; 323 ASSERT_EQ (0, v.length ()); 324 safe_push_range (v, 0, 10); 325 ASSERT_EQ (10, v.length ()); 326 327 v.truncate (5); 328 ASSERT_EQ (5, v.length ()); 329 } 330 331 /* Verify that vec::safe_grow_cleared works correctly. */ 332 333 static void 334 test_safe_grow_cleared () 335 { 336 auto_vec <int> v; 337 ASSERT_EQ (0, v.length ()); 338 v.safe_grow_cleared (50); 339 ASSERT_EQ (50, v.length ()); 340 ASSERT_EQ (0, v[0]); 341 ASSERT_EQ (0, v[49]); 342 } 343 344 /* Verify that vec::pop works correctly. */ 345 346 static void 347 test_pop () 348 { 349 auto_vec <int> v; 350 safe_push_range (v, 5, 20); 351 ASSERT_EQ (15, v.length ()); 352 353 int last = v.pop (); 354 ASSERT_EQ (19, last); 355 ASSERT_EQ (14, v.length ()); 356 } 357 358 /* Verify that vec::safe_insert works correctly. */ 359 360 static void 361 test_safe_insert () 362 { 363 auto_vec <int> v; 364 safe_push_range (v, 0, 10); 365 v.safe_insert (5, 42); 366 ASSERT_EQ (4, v[4]); 367 ASSERT_EQ (42, v[5]); 368 ASSERT_EQ (5, v[6]); 369 ASSERT_EQ (11, v.length ()); 370 } 371 372 /* Verify that vec::ordered_remove works correctly. */ 373 374 static void 375 test_ordered_remove () 376 { 377 auto_vec <int> v; 378 safe_push_range (v, 0, 10); 379 v.ordered_remove (5); 380 ASSERT_EQ (4, v[4]); 381 ASSERT_EQ (6, v[5]); 382 ASSERT_EQ (9, v.length ()); 383 } 384 385 /* Verify that vec::unordered_remove works correctly. */ 386 387 static void 388 test_unordered_remove () 389 { 390 auto_vec <int> v; 391 safe_push_range (v, 0, 10); 392 v.unordered_remove (5); 393 ASSERT_EQ (9, v.length ()); 394 } 395 396 /* Verify that vec::block_remove works correctly. */ 397 398 static void 399 test_block_remove () 400 { 401 auto_vec <int> v; 402 safe_push_range (v, 0, 10); 403 v.block_remove (5, 3); 404 ASSERT_EQ (3, v[3]); 405 ASSERT_EQ (4, v[4]); 406 ASSERT_EQ (8, v[5]); 407 ASSERT_EQ (9, v[6]); 408 ASSERT_EQ (7, v.length ()); 409 } 410 411 /* Comparator for use by test_qsort. */ 412 413 static int 414 reverse_cmp (const void *p_i, const void *p_j) 415 { 416 return *(const int *)p_j - *(const int *)p_i; 417 } 418 419 /* Verify that vec::qsort works correctly. */ 420 421 static void 422 test_qsort () 423 { 424 auto_vec <int> v; 425 safe_push_range (v, 0, 10); 426 v.qsort (reverse_cmp); 427 ASSERT_EQ (9, v[0]); 428 ASSERT_EQ (8, v[1]); 429 ASSERT_EQ (1, v[8]); 430 ASSERT_EQ (0, v[9]); 431 ASSERT_EQ (10, v.length ()); 432 } 433 434 /* Run all of the selftests within this file. */ 435 436 void 437 vec_c_tests () 438 { 439 test_quick_push (); 440 test_safe_push (); 441 test_truncate (); 442 test_safe_grow_cleared (); 443 test_pop (); 444 test_safe_insert (); 445 test_ordered_remove (); 446 test_unordered_remove (); 447 test_block_remove (); 448 test_qsort (); 449 } 450 451 } // namespace selftest 452 453 #endif /* #if CHECKING_P */ 454 #endif /* #ifndef GENERATOR_FILE */ 455