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 | #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 | /* Comparison operator. */ |

64 | inline bool |

65 | operator< (const vec_usage &second) const |

66 | { |

67 | return (m_allocated == second.m_allocated ? |

68 | (m_peak == second.m_peak ? m_times < second.m_times |

69 | : m_peak < second.m_peak) : m_allocated < second.m_allocated); |

70 | } |

71 | |

72 | /* Sum the usage with SECOND usage. */ |

73 | vec_usage |

74 | operator+ (const vec_usage &second) |

75 | { |

76 | return vec_usage (m_allocated + second.m_allocated, |

77 | m_times + second.m_times, |

78 | m_peak + second.m_peak, |

79 | m_items + second.m_items, |

80 | m_items_peak + second.m_items_peak); |

81 | } |

82 | |

83 | /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */ |

84 | inline void |

85 | dump (mem_location *loc, mem_usage &total) const |

86 | { |

87 | char s[4096]; |

88 | sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (), |

89 | loc->m_line, loc->m_function); |

90 | |

91 | s[48] = '\0'; |

92 | |

93 | fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s, |

94 | (long)m_allocated, m_allocated * 100.0 / total.m_allocated, |

95 | (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times, |

96 | (long)m_items, (long)m_items_peak); |

97 | } |

98 | |

99 | /* Dump footer. */ |

100 | inline void |

101 | dump_footer () |

102 | { |

103 | print_dash_line (); |

104 | fprintf (stderr, "%s%55li%25li%17li\n", "Total", ( long)m_allocated, |

105 | (long)m_times, (long)m_items); |

106 | print_dash_line (); |

107 | } |

108 | |

109 | /* Dump header with NAME. */ |

110 | static inline void |

111 | dump_header (const char *name) |

112 | { |

113 | fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak", |

114 | "Times", "Leak items", "Peak items"); |

115 | print_dash_line (); |

116 | } |

117 | |

118 | /* Compare wrapper used by qsort method. */ |

119 | static int |

120 | compare (const void *first, const void *second) |

121 | { |

122 | typedef std::pair<mem_location *, vec_usage *> mem_pair_t; |

123 | |

124 | const mem_pair_t f = *(const mem_pair_t *)first; |

125 | const mem_pair_t s = *(const mem_pair_t *)second; |

126 | |

127 | return (*f.second) < (*s.second); |

128 | } |

129 | |

130 | /* Current number of items allocated. */ |

131 | size_t m_items; |

132 | /* Peak value of number of allocated items. */ |

133 | size_t m_items_peak; |

134 | }; |

135 | |

136 | /* Vector memory description. */ |

137 | static mem_alloc_description <vec_usage> vec_mem_desc; |

138 | |

139 | /* Account the overhead. */ |

140 | |

141 | void |

142 | vec_prefix::register_overhead (void *ptr, size_t size, size_t elements |

143 | MEM_STAT_DECL) |

144 | { |

145 | vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false |

146 | FINAL_PASS_MEM_STAT); |

147 | vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr); |

148 | usage->m_items += elements; |

149 | if (usage->m_items_peak < usage->m_items) |

150 | usage->m_items_peak = usage->m_items; |

151 | } |

152 | |

153 | /* Notice that the memory allocated for the vector has been freed. */ |

154 | |

155 | void |

156 | vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor |

157 | MEM_STAT_DECL) |

158 | { |

159 | if (!vec_mem_desc.contains_descriptor_for_instance (ptr)) |

160 | vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, |

161 | false FINAL_PASS_MEM_STAT); |

162 | vec_mem_desc.release_instance_overhead (ptr, size, in_dtor); |

163 | } |

164 | |

165 | |

166 | /* Calculate the number of slots to reserve a vector, making sure that |

167 | it is of at least DESIRED size by growing ALLOC exponentially. */ |

168 | |

169 | unsigned |

170 | vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired) |

171 | { |

172 | /* We must have run out of room. */ |

173 | gcc_assert (alloc < desired); |

174 | |

175 | /* Exponential growth. */ |

176 | if (!alloc) |

177 | alloc = 4; |

178 | else if (alloc < 16) |

179 | /* Double when small. */ |

180 | alloc = alloc * 2; |

181 | else |

182 | /* Grow slower when large. */ |

183 | alloc = (alloc * 3 / 2); |

184 | |

185 | /* If this is still too small, set it to the right size. */ |

186 | if (alloc < desired) |

187 | alloc = desired; |

188 | return alloc; |

189 | } |

190 | |

191 | /* Dump per-site memory statistics. */ |

192 | |

193 | void |

194 | dump_vec_loc_statistics (void) |

195 | { |

196 | vec_mem_desc.dump (VEC_ORIGIN); |

197 | } |

198 | |

199 | #if CHECKING_P |

200 | /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as |

201 | witness elements. */ |

202 | ATTRIBUTE_NORETURN ATTRIBUTE_COLD |

203 | static void |

204 | qsort_chk_error (const void *p1, const void *p2, const void *p3, |

205 | int (*cmp) (const void *, const void *)) |

206 | { |

207 | if (!p3) |

208 | { |

209 | int r1 = cmp (p1, p2), r2 = cmp (p2, p1); |

210 | error ("qsort comparator not anti-commutative: %d, %d", r1, r2); |

211 | } |

212 | else if (p1 == p2) |

213 | { |

214 | int r = cmp (p1, p3); |

215 | error ("qsort comparator non-negative on sorted output: %d", r); |

216 | } |

217 | else |

218 | { |

219 | int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3); |

220 | error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3); |

221 | } |

222 | internal_error ("qsort checking failed"); |

223 | } |

224 | |

225 | /* Wrapper around qsort with checking that CMP is consistent on given input. |

226 | |

227 | Strictly speaking, passing invalid (non-transitive, non-anti-commutative) |

228 | comparators to libc qsort can result in undefined behavior. Therefore we |

229 | should ideally perform consistency checks prior to invoking qsort, but in |

230 | order to do that optimally we'd need to sort the array ourselves beforehand |

231 | with a sorting routine known to be "safe". Instead, we expect that most |

232 | implementations in practice will still produce some permutation of input |

233 | array even for invalid comparators, which enables us to perform checks on |

234 | the output array. */ |

235 | void |

236 | qsort_chk (void *base, size_t n, size_t size, |

237 | int (*cmp)(const void *, const void *)) |

238 | { |

239 | (qsort) (base, n, size, cmp); |

240 | #if 0 |

241 | #define LIM(n) (n) |

242 | #else |

243 | /* Limit overall time complexity to O(n log n). */ |

244 | #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) |

245 | #endif |

246 | #define ELT(i) ((const char *) base + (i) * size) |

247 | #define CMP(i, j) cmp (ELT (i), ELT (j)) |

248 | #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp) |

249 | #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) |

250 | size_t i1, i2, i, j; |

251 | /* This outer loop iterates over maximum spans [i1, i2) such that |

252 | elements within each span compare equal to each other. */ |

253 | for (i1 = 0; i1 < n; i1 = i2) |

254 | { |

255 | /* Position i2 one past last element that compares equal to i1'th. */ |

256 | for (i2 = i1 + 1; i2 < n; i2++) |

257 | if (CMP (i1, i2)) |

258 | break; |

259 | else if (CMP (i2, i1)) |

260 | return ERR2 (i1, i2); |

261 | size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); |

262 | /* Verify that other pairs within current span compare equal. */ |

263 | for (i = i1 + 1; i + 1 < i2; i++) |

264 | for (j = i + 1; j < i1 + lim1; j++) |

265 | if (CMP (i, j)) |

266 | return ERR3 (i, i1, j); |

267 | else if (CMP (j, i)) |

268 | return ERR2 (i, j); |

269 | /* Verify that elements within this span compare less than |

270 | elements beyond the span. */ |

271 | for (i = i1; i < i2; i++) |

272 | for (j = i2; j < i2 + lim2; j++) |

273 | if (CMP (i, j) >= 0) |

274 | return ERR3 (i, i1, j); |

275 | else if (CMP (j, i) <= 0) |

276 | return ERR2 (i, j); |

277 | } |

278 | #undef ERR3 |

279 | #undef ERR2 |

280 | #undef CMP |

281 | #undef ELT |

282 | #undef LIM |

283 | } |

284 | #endif /* #if CHECKING_P */ |

285 | |

286 | #ifndef GENERATOR_FILE |

287 | #if CHECKING_P |

288 | |

289 | namespace selftest { |

290 | |

291 | /* Selftests. */ |

292 | |

293 | /* Call V.safe_push for all ints from START up to, but not including LIMIT. |

294 | Helper function for selftests. */ |

295 | |

296 | static void |

297 | safe_push_range (vec <int>&v, int start, int limit) |

298 | { |

299 | for (int i = start; i < limit; i++) |

300 | v.safe_push (i); |

301 | } |

302 | |

303 | /* Verify that vec::quick_push works correctly. */ |

304 | |

305 | static void |

306 | test_quick_push () |

307 | { |

308 | auto_vec <int> v; |

309 | ASSERT_EQ (0, v.length ()); |

310 | v.reserve (3); |

311 | ASSERT_EQ (0, v.length ()); |

312 | ASSERT_TRUE (v.space (3)); |

313 | v.quick_push (5); |

314 | v.quick_push (6); |

315 | v.quick_push (7); |

316 | ASSERT_EQ (3, v.length ()); |

317 | ASSERT_EQ (5, v[0]); |

318 | ASSERT_EQ (6, v[1]); |

319 | ASSERT_EQ (7, v[2]); |

320 | } |

321 | |

322 | /* Verify that vec::safe_push works correctly. */ |

323 | |

324 | static void |

325 | test_safe_push () |

326 | { |

327 | auto_vec <int> v; |

328 | ASSERT_EQ (0, v.length ()); |

329 | v.safe_push (5); |

330 | v.safe_push (6); |

331 | v.safe_push (7); |

332 | ASSERT_EQ (3, v.length ()); |

333 | ASSERT_EQ (5, v[0]); |

334 | ASSERT_EQ (6, v[1]); |

335 | ASSERT_EQ (7, v[2]); |

336 | } |

337 | |

338 | /* Verify that vec::truncate works correctly. */ |

339 | |

340 | static void |

341 | test_truncate () |

342 | { |

343 | auto_vec <int> v; |

344 | ASSERT_EQ (0, v.length ()); |

345 | safe_push_range (v, 0, 10); |

346 | ASSERT_EQ (10, v.length ()); |

347 | |

348 | v.truncate (5); |

349 | ASSERT_EQ (5, v.length ()); |

350 | } |

351 | |

352 | /* Verify that vec::safe_grow_cleared works correctly. */ |

353 | |

354 | static void |

355 | test_safe_grow_cleared () |

356 | { |

357 | auto_vec <int> v; |

358 | ASSERT_EQ (0, v.length ()); |

359 | v.safe_grow_cleared (50); |

360 | ASSERT_EQ (50, v.length ()); |

361 | ASSERT_EQ (0, v[0]); |

362 | ASSERT_EQ (0, v[49]); |

363 | } |

364 | |

365 | /* Verify that vec::pop works correctly. */ |

366 | |

367 | static void |

368 | test_pop () |

369 | { |

370 | auto_vec <int> v; |

371 | safe_push_range (v, 5, 20); |

372 | ASSERT_EQ (15, v.length ()); |

373 | |

374 | int last = v.pop (); |

375 | ASSERT_EQ (19, last); |

376 | ASSERT_EQ (14, v.length ()); |

377 | } |

378 | |

379 | /* Verify that vec::safe_insert works correctly. */ |

380 | |

381 | static void |

382 | test_safe_insert () |

383 | { |

384 | auto_vec <int> v; |

385 | safe_push_range (v, 0, 10); |

386 | v.safe_insert (5, 42); |

387 | ASSERT_EQ (4, v[4]); |

388 | ASSERT_EQ (42, v[5]); |

389 | ASSERT_EQ (5, v[6]); |

390 | ASSERT_EQ (11, v.length ()); |

391 | } |

392 | |

393 | /* Verify that vec::ordered_remove works correctly. */ |

394 | |

395 | static void |

396 | test_ordered_remove () |

397 | { |

398 | auto_vec <int> v; |

399 | safe_push_range (v, 0, 10); |

400 | v.ordered_remove (5); |

401 | ASSERT_EQ (4, v[4]); |

402 | ASSERT_EQ (6, v[5]); |

403 | ASSERT_EQ (9, v.length ()); |

404 | } |

405 | |

406 | /* Verify that vec::unordered_remove works correctly. */ |

407 | |

408 | static void |

409 | test_unordered_remove () |

410 | { |

411 | auto_vec <int> v; |

412 | safe_push_range (v, 0, 10); |

413 | v.unordered_remove (5); |

414 | ASSERT_EQ (9, v.length ()); |

415 | } |

416 | |

417 | /* Verify that vec::block_remove works correctly. */ |

418 | |

419 | static void |

420 | test_block_remove () |

421 | { |

422 | auto_vec <int> v; |

423 | safe_push_range (v, 0, 10); |

424 | v.block_remove (5, 3); |

425 | ASSERT_EQ (3, v[3]); |

426 | ASSERT_EQ (4, v[4]); |

427 | ASSERT_EQ (8, v[5]); |

428 | ASSERT_EQ (9, v[6]); |

429 | ASSERT_EQ (7, v.length ()); |

430 | } |

431 | |

432 | /* Comparator for use by test_qsort. */ |

433 | |

434 | static int |

435 | reverse_cmp (const void *p_i, const void *p_j) |

436 | { |

437 | return *(const int *)p_j - *(const int *)p_i; |

438 | } |

439 | |

440 | /* Verify that vec::qsort works correctly. */ |

441 | |

442 | static void |

443 | test_qsort () |

444 | { |

445 | auto_vec <int> v; |

446 | safe_push_range (v, 0, 10); |

447 | v.qsort (reverse_cmp); |

448 | ASSERT_EQ (9, v[0]); |

449 | ASSERT_EQ (8, v[1]); |

450 | ASSERT_EQ (1, v[8]); |

451 | ASSERT_EQ (0, v[9]); |

452 | ASSERT_EQ (10, v.length ()); |

453 | } |

454 | |

455 | /* Run all of the selftests within this file. */ |

456 | |

457 | void |

458 | vec_c_tests () |

459 | { |

460 | test_quick_push (); |

461 | test_safe_push (); |

462 | test_truncate (); |

463 | test_safe_grow_cleared (); |

464 | test_pop (); |

465 | test_safe_insert (); |

466 | test_ordered_remove (); |

467 | test_unordered_remove (); |

468 | test_block_remove (); |

469 | test_qsort (); |

470 | } |

471 | |

472 | } // namespace selftest |

473 | |

474 | #endif /* #if CHECKING_P */ |

475 | #endif /* #ifndef GENERATOR_FILE */ |

476 |