1 | /* Profile counter container type. |
---|---|

2 | Copyright (C) 2017 Free Software Foundation, Inc. |

3 | Contributed by Jan Hubicka |

4 | |

5 | This file is part of GCC. |

6 | |

7 | GCC is free software; you can redistribute it and/or modify it under |

8 | the terms of the GNU General Public License as published by the Free |

9 | Software Foundation; either version 3, or (at your option) any later |

10 | version. |

11 | |

12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

15 | for more details. |

16 | |

17 | You should have received a copy of the GNU General Public License |

18 | along with GCC; see the file COPYING3. If not see |

19 | <http://www.gnu.org/licenses/>. */ |

20 | |

21 | #ifndef GCC_PROFILE_COUNT_H |

22 | #define GCC_PROFILE_COUNT_H |

23 | |

24 | struct function; |

25 | |

26 | /* Quality of the profile count. Because gengtype does not support enums |

27 | inside of classes, this is in global namespace. */ |

28 | enum profile_quality { |

29 | /* Profile is based on static branch prediction heuristics and may |

30 | or may not match reality. It is local to function and can not be compared |

31 | inter-procedurally. Never used by probabilities (they are always local). |

32 | */ |

33 | profile_guessed_local = 0, |

34 | /* Profile was read by feedback and was 0, we used local heuristics to guess |

35 | better. This is the case of functions not run in profile fedback. |

36 | Never used by probabilities. */ |

37 | profile_guessed_global0 = 1, |

38 | |

39 | /* Same as profile_guessed_global0 but global count is adjusted 0. */ |

40 | profile_guessed_global0adjusted = 2, |

41 | |

42 | /* Profile is based on static branch prediction heuristics. It may or may |

43 | not reflect the reality but it can be compared interprocedurally |

44 | (for example, we inlined function w/o profile feedback into function |

45 | with feedback and propagated from that). |

46 | Never used by probablities. */ |

47 | profile_guessed = 3, |

48 | /* Profile was determined by autofdo. */ |

49 | profile_afdo = 4, |

50 | /* Profile was originally based on feedback but it was adjusted |

51 | by code duplicating optimization. It may not precisely reflect the |

52 | particular code path. */ |

53 | profile_adjusted = 5, |

54 | /* Profile was read from profile feedback or determined by accurate static |

55 | method. */ |

56 | profile_precise = 7 |

57 | }; |

58 | |

59 | /* The base value for branch probability notes and edge probabilities. */ |

60 | #define REG_BR_PROB_BASE 10000 |

61 | |

62 | #define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) |

63 | |

64 | bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res); |

65 | |

66 | /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */ |

67 | |

68 | inline bool |

69 | safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res) |

70 | { |

71 | #if (GCC_VERSION >= 5000) |

72 | uint64_t tmp; |

73 | if (!__builtin_mul_overflow (a, b, &tmp) |

74 | && !__builtin_add_overflow (tmp, c/2, &tmp)) |

75 | { |

76 | *res = tmp / c; |

77 | return true; |

78 | } |

79 | if (c == 1) |

80 | { |

81 | *res = (uint64_t) -1; |

82 | return false; |

83 | } |

84 | #else |

85 | if (a < ((uint64_t)1 << 31) |

86 | && b < ((uint64_t)1 << 31) |

87 | && c < ((uint64_t)1 << 31)) |

88 | { |

89 | *res = (a * b + (c / 2)) / c; |

90 | return true; |

91 | } |

92 | #endif |

93 | return slow_safe_scale_64bit (a, b, c, res); |

94 | } |

95 | |

96 | /* Data type to hold probabilities. It implements fixed point arithmetics |

97 | with capping so probability is always in range [0,1] and scaling requiring |

98 | values greater than 1 needs to be represented otherwise. |

99 | |

100 | In addition to actual value the quality of profile is tracked and propagated |

101 | through all operations. Special value UNINITIALIZED is used for probabilities |

102 | that has not been determined yet (for example bacause of |

103 | -fno-guess-branch-probability) |

104 | |

105 | Typically probabilities are derived from profile feedback (via |

106 | probability_in_gcov_type), autoFDO or guessed statically and then propagated |

107 | thorough the compilation. |

108 | |

109 | Named probabilities are available: |

110 | - never (0 probability) |

111 | - guessed_never |

112 | - very_unlikely (1/2000 probability) |

113 | - unlikely (1/5 probablity) |

114 | - even (1/2 probability) |

115 | - likely (4/5 probability) |

116 | - very_likely (1999/2000 probability) |

117 | - guessed_always |

118 | - always |

119 | |

120 | Named probabilities except for never/always are assumed to be statically |

121 | guessed and thus not necessarily accurate. The difference between never |

122 | and guessed_never is that the first one should be used only in case that |

123 | well behaving program will very likely not execute the "never" path. |

124 | For example if the path is going to abort () call or it exception handling. |

125 | |

126 | Always and guessed_always probabilities are symmetric. |

127 | |

128 | For legacy code we support conversion to/from REG_BR_PROB_BASE based fixpoint |

129 | integer arithmetics. Once the code is converted to branch probabilities, |

130 | these conversions will probably go away because they are lossy. |

131 | */ |

132 | |

133 | class GTY((user)) profile_probability |

134 | { |

135 | static const int n_bits = 29; |

136 | /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that |

137 | will lead to harder multiplication sequences. */ |

138 | static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2); |

139 | static const uint32_t uninitialized_probability |

140 | = ((uint32_t) 1 << (n_bits - 1)) - 1; |

141 | |

142 | uint32_t m_val : 29; |

143 | enum profile_quality m_quality : 3; |

144 | |

145 | friend class profile_count; |

146 | public: |

147 | |

148 | /* Named probabilities. */ |

149 | static profile_probability never () |

150 | { |

151 | profile_probability ret; |

152 | ret.m_val = 0; |

153 | ret.m_quality = profile_precise; |

154 | return ret; |

155 | } |

156 | static profile_probability guessed_never () |

157 | { |

158 | profile_probability ret; |

159 | ret.m_val = 0; |

160 | ret.m_quality = profile_guessed; |

161 | return ret; |

162 | } |

163 | static profile_probability very_unlikely () |

164 | { |

165 | /* Be consistent with PROB_VERY_UNLIKELY in predict.h. */ |

166 | profile_probability r |

167 | = profile_probability::always ().apply_scale (1, 2000); |

168 | r.m_val--; |

169 | return r; |

170 | } |

171 | static profile_probability unlikely () |

172 | { |

173 | /* Be consistent with PROB_VERY_LIKELY in predict.h. */ |

174 | profile_probability r |

175 | = profile_probability::always ().apply_scale (1, 5); |

176 | r.m_val--; |

177 | return r; |

178 | } |

179 | static profile_probability even () |

180 | { |

181 | return profile_probability::always ().apply_scale (1, 2); |

182 | } |

183 | static profile_probability very_likely () |

184 | { |

185 | return profile_probability::always () - very_unlikely (); |

186 | } |

187 | static profile_probability likely () |

188 | { |

189 | return profile_probability::always () - unlikely (); |

190 | } |

191 | static profile_probability guessed_always () |

192 | { |

193 | profile_probability ret; |

194 | ret.m_val = max_probability; |

195 | ret.m_quality = profile_guessed; |

196 | return ret; |

197 | } |

198 | static profile_probability always () |

199 | { |

200 | profile_probability ret; |

201 | ret.m_val = max_probability; |

202 | ret.m_quality = profile_precise; |

203 | return ret; |

204 | } |

205 | /* Probabilities which has not been initialized. Either because |

206 | initialization did not happen yet or because profile is unknown. */ |

207 | static profile_probability uninitialized () |

208 | { |

209 | profile_probability c; |

210 | c.m_val = uninitialized_probability; |

211 | c.m_quality = profile_guessed; |

212 | return c; |

213 | } |

214 | |

215 | |

216 | /* Return true if value has been initialized. */ |

217 | bool initialized_p () const |

218 | { |

219 | return m_val != uninitialized_probability; |

220 | } |

221 | /* Return true if value can be trusted. */ |

222 | bool reliable_p () const |

223 | { |

224 | return m_quality >= profile_adjusted; |

225 | } |

226 | |

227 | /* Conversion from and to REG_BR_PROB_BASE integer fixpoint arithmetics. |

228 | this is mostly to support legacy code and should go away. */ |

229 | static profile_probability from_reg_br_prob_base (int v) |

230 | { |

231 | profile_probability ret; |

232 | gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE); |

233 | ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE); |

234 | ret.m_quality = profile_guessed; |

235 | return ret; |

236 | } |

237 | int to_reg_br_prob_base () const |

238 | { |

239 | gcc_checking_assert (initialized_p ()); |

240 | return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability); |

241 | } |

242 | |

243 | /* Conversion to and from RTL representation of profile probabilities. */ |

244 | static profile_probability from_reg_br_prob_note (int v) |

245 | { |

246 | profile_probability ret; |

247 | ret.m_val = ((unsigned int)v) / 8; |

248 | ret.m_quality = (enum profile_quality)(v & 7); |

249 | return ret; |

250 | } |

251 | int to_reg_br_prob_note () const |

252 | { |

253 | gcc_checking_assert (initialized_p ()); |

254 | int ret = m_val * 8 + m_quality; |

255 | gcc_checking_assert (profile_probability::from_reg_br_prob_note (ret) |

256 | == *this); |

257 | return ret; |

258 | } |

259 | |

260 | /* Return VAL1/VAL2. */ |

261 | static profile_probability probability_in_gcov_type |

262 | (gcov_type val1, gcov_type val2) |

263 | { |

264 | profile_probability ret; |

265 | gcc_checking_assert (val1 >= 0 && val2 > 0); |

266 | if (val1 > val2) |

267 | ret.m_val = max_probability; |

268 | else |

269 | { |

270 | uint64_t tmp; |

271 | safe_scale_64bit (val1, max_probability, val2, &tmp); |

272 | gcc_checking_assert (tmp <= max_probability); |

273 | ret.m_val = tmp; |

274 | } |

275 | ret.m_quality = profile_precise; |

276 | return ret; |

277 | } |

278 | |

279 | /* Basic operations. */ |

280 | bool operator== (const profile_probability &other) const |

281 | { |

282 | return m_val == other.m_val && m_quality == other.m_quality; |

283 | } |

284 | profile_probability operator+ (const profile_probability &other) const |

285 | { |

286 | if (other == profile_probability::never ()) |

287 | return *this; |

288 | if (*this == profile_probability::never ()) |

289 | return other; |

290 | if (!initialized_p () || !other.initialized_p ()) |

291 | return profile_probability::uninitialized (); |

292 | |

293 | profile_probability ret; |

294 | ret.m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability); |

295 | ret.m_quality = MIN (m_quality, other.m_quality); |

296 | return ret; |

297 | } |

298 | profile_probability &operator+= (const profile_probability &other) |

299 | { |

300 | if (other == profile_probability::never ()) |

301 | return *this; |

302 | if (*this == profile_probability::never ()) |

303 | { |

304 | *this = other; |

305 | return *this; |

306 | } |

307 | if (!initialized_p () || !other.initialized_p ()) |

308 | return *this = profile_probability::uninitialized (); |

309 | else |

310 | { |

311 | m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability); |

312 | m_quality = MIN (m_quality, other.m_quality); |

313 | } |

314 | return *this; |

315 | } |

316 | profile_probability operator- (const profile_probability &other) const |

317 | { |

318 | if (*this == profile_probability::never () |

319 | || other == profile_probability::never ()) |

320 | return *this; |

321 | if (!initialized_p () || !other.initialized_p ()) |

322 | return profile_probability::uninitialized (); |

323 | profile_probability ret; |

324 | ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0; |

325 | ret.m_quality = MIN (m_quality, other.m_quality); |

326 | return ret; |

327 | } |

328 | profile_probability &operator-= (const profile_probability &other) |

329 | { |

330 | if (*this == profile_probability::never () |

331 | || other == profile_probability::never ()) |

332 | return *this; |

333 | if (!initialized_p () || !other.initialized_p ()) |

334 | return *this = profile_probability::uninitialized (); |

335 | else |

336 | { |

337 | m_val = m_val >= other.m_val ? m_val - other.m_val : 0; |

338 | m_quality = MIN (m_quality, other.m_quality); |

339 | } |

340 | return *this; |

341 | } |

342 | profile_probability operator* (const profile_probability &other) const |

343 | { |

344 | if (*this == profile_probability::never () |

345 | || other == profile_probability::never ()) |

346 | return profile_probability::never (); |

347 | if (!initialized_p () || !other.initialized_p ()) |

348 | return profile_probability::uninitialized (); |

349 | profile_probability ret; |

350 | ret.m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability); |

351 | ret.m_quality = MIN (m_quality, other.m_quality); |

352 | return ret; |

353 | } |

354 | profile_probability &operator*= (const profile_probability &other) |

355 | { |

356 | if (*this == profile_probability::never () |

357 | || other == profile_probability::never ()) |

358 | return *this = profile_probability::never (); |

359 | if (!initialized_p () || !other.initialized_p ()) |

360 | return *this = profile_probability::uninitialized (); |

361 | else |

362 | { |

363 | m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability); |

364 | m_quality = MIN (m_quality, other.m_quality); |

365 | } |

366 | return *this; |

367 | } |

368 | profile_probability operator/ (const profile_probability &other) const |

369 | { |

370 | if (*this == profile_probability::never ()) |

371 | return profile_probability::never (); |

372 | if (!initialized_p () || !other.initialized_p ()) |

373 | return profile_probability::uninitialized (); |

374 | profile_probability ret; |

375 | if (m_val >= other.m_val) |

376 | ret.m_val = max_probability; |

377 | else if (!m_val) |

378 | ret.m_val = 0; |

379 | else |

380 | { |

381 | gcc_checking_assert (other.m_val); |

382 | ret.m_val = MIN (RDIV ((uint64_t)m_val * max_probability, |

383 | other.m_val), |

384 | max_probability); |

385 | } |

386 | ret.m_quality = MIN (m_quality, other.m_quality); |

387 | return ret; |

388 | } |

389 | profile_probability &operator/= (const profile_probability &other) |

390 | { |

391 | if (*this == profile_probability::never ()) |

392 | return *this = profile_probability::never (); |

393 | if (!initialized_p () || !other.initialized_p ()) |

394 | return *this = profile_probability::uninitialized (); |

395 | else |

396 | { |

397 | if (m_val > other.m_val) |

398 | m_val = max_probability; |

399 | else if (!m_val) |

400 | ; |

401 | else |

402 | { |

403 | gcc_checking_assert (other.m_val); |

404 | m_val = MIN (RDIV ((uint64_t)m_val * max_probability, |

405 | other.m_val), |

406 | max_probability); |

407 | } |

408 | m_quality = MIN (m_quality, other.m_quality); |

409 | } |

410 | return *this; |

411 | } |

412 | |

413 | gcov_type apply (gcov_type val) const |

414 | { |

415 | if (*this == profile_probability::uninitialized ()) |

416 | return val / 2; |

417 | return RDIV (val * m_val, max_probability); |

418 | } |

419 | |

420 | /* Return 1-*THIS. */ |

421 | profile_probability invert () const |

422 | { |

423 | return profile_probability::always() - *this; |

424 | } |

425 | |

426 | /* Return THIS with quality dropped to GUESSED. */ |

427 | profile_probability guessed () const |

428 | { |

429 | profile_probability ret = *this; |

430 | ret.m_quality = profile_guessed; |

431 | return ret; |

432 | } |

433 | |

434 | /* Return THIS with quality dropped to AFDO. */ |

435 | profile_probability afdo () const |

436 | { |

437 | profile_probability ret = *this; |

438 | ret.m_quality = profile_afdo; |

439 | return ret; |

440 | } |

441 | |

442 | profile_probability combine_with_freq (int freq1, profile_probability other, |

443 | int freq2) const |

444 | { |

445 | profile_probability ret; |

446 | |

447 | if (*this == profile_probability::uninitialized () |

448 | || other == profile_probability::uninitialized ()) |

449 | return profile_probability::uninitialized (); |

450 | |

451 | gcc_checking_assert (freq1 >= 0 && freq2 >= 0); |

452 | if (!freq1 && !freq2) |

453 | { |

454 | ret.m_val = (m_val + other.m_val) / 2; |

455 | } |

456 | else |

457 | ret.m_val = RDIV (m_val * (uint64_t) freq1 |

458 | + other.m_val * (uint64_t) freq2, freq1 + freq2); |

459 | ret.m_quality = MIN (m_quality, other.m_quality); |

460 | return ret; |

461 | } |

462 | |

463 | /* Return *THIS * NUM / DEN. */ |

464 | profile_probability apply_scale (int64_t num, int64_t den) const |

465 | { |

466 | if (*this == profile_probability::never ()) |

467 | return *this; |

468 | if (!initialized_p ()) |

469 | return profile_probability::uninitialized (); |

470 | profile_probability ret; |

471 | uint64_t tmp; |

472 | safe_scale_64bit (m_val, num, den, &tmp); |

473 | ret.m_val = MIN (tmp, max_probability); |

474 | ret.m_quality = MIN (m_quality, profile_adjusted); |

475 | return ret; |

476 | } |

477 | |

478 | /* Return true when the probability of edge is reliable. |

479 | |

480 | The profile guessing code is good at predicting branch outcome (ie. |

481 | taken/not taken), that is predicted right slightly over 75% of time. |

482 | It is however notoriously poor on predicting the probability itself. |

483 | In general the profile appear a lot flatter (with probabilities closer |

484 | to 50%) than the reality so it is bad idea to use it to drive optimization |

485 | such as those disabling dynamic branch prediction for well predictable |

486 | branches. |

487 | |

488 | There are two exceptions - edges leading to noreturn edges and edges |

489 | predicted by number of iterations heuristics are predicted well. This macro |

490 | should be able to distinguish those, but at the moment it simply check for |

491 | noreturn heuristic that is only one giving probability over 99% or bellow |

492 | 1%. In future we might want to propagate reliability information across the |

493 | CFG if we find this information useful on multiple places. */ |

494 | |

495 | bool probably_reliable_p () const |

496 | { |

497 | if (m_quality >= profile_adjusted) |

498 | return true; |

499 | if (!initialized_p ()) |

500 | return false; |

501 | return m_val < max_probability / 100 |

502 | || m_val > max_probability - max_probability / 100; |

503 | } |

504 | |

505 | /* Return false if profile_probability is bogus. */ |

506 | bool verify () const |

507 | { |

508 | if (m_val == uninitialized_probability) |

509 | return m_quality == profile_guessed; |

510 | else if (m_quality < profile_guessed) |

511 | return false; |

512 | return m_val <= max_probability; |

513 | } |

514 | |

515 | /* Comparsions are three-state and conservative. False is returned if |

516 | the inequality can not be decided. */ |

517 | bool operator< (const profile_probability &other) const |

518 | { |

519 | return initialized_p () && other.initialized_p () && m_val < other.m_val; |

520 | } |

521 | bool operator> (const profile_probability &other) const |

522 | { |

523 | return initialized_p () && other.initialized_p () && m_val > other.m_val; |

524 | } |

525 | |

526 | bool operator<= (const profile_probability &other) const |

527 | { |

528 | return initialized_p () && other.initialized_p () && m_val <= other.m_val; |

529 | } |

530 | bool operator>= (const profile_probability &other) const |

531 | { |

532 | return initialized_p () && other.initialized_p () && m_val >= other.m_val; |

533 | } |

534 | |

535 | /* Output THIS to F. */ |

536 | void dump (FILE *f) const; |

537 | |

538 | /* Print THIS to stderr. */ |

539 | void debug () const; |

540 | |

541 | /* Return true if THIS is known to differ significantly from OTHER. */ |

542 | bool differs_from_p (profile_probability other) const; |

543 | /* Return if difference is greater than 50%. */ |

544 | bool differs_lot_from_p (profile_probability other) const; |

545 | |

546 | /* LTO streaming support. */ |

547 | static profile_probability stream_in (struct lto_input_block *); |

548 | void stream_out (struct output_block *); |

549 | void stream_out (struct lto_output_stream *); |

550 | }; |

551 | |

552 | /* Main data type to hold profile counters in GCC. Profile counts originate |

553 | either from profile feedback, static profile estimation or both. We do not |

554 | perform whole program profile propagation and thus profile estimation |

555 | counters are often local to function, while counters from profile feedback |

556 | (or special cases of profile estimation) can be used inter-procedurally. |

557 | |

558 | There are 3 basic types |

559 | 1) local counters which are result of intra-procedural static profile |

560 | estimation. |

561 | 2) ipa counters which are result of profile feedback or special case |

562 | of static profile estimation (such as in function main). |

563 | 3) counters which counts as 0 inter-procedurally (beause given function |

564 | was never run in train feedback) but they hold local static profile |

565 | estimate. |

566 | |

567 | Counters of type 1 and 3 can not be mixed with counters of different type |

568 | within operation (because whole function should use one type of counter) |

569 | with exception that global zero mix in most operations where outcome is |

570 | well defined. |

571 | |

572 | To take local counter and use it inter-procedurally use ipa member function |

573 | which strips information irelevant at the inter-procedural level. |

574 | |

575 | Counters are 61bit integers representing number of executions during the |

576 | train run or normalized frequency within the function. |

577 | |

578 | As the profile is maintained during the compilation, many adjustments are |

579 | made. Not all transformations can be made precisely, most importantly |

580 | when code is being duplicated. It also may happen that part of CFG has |

581 | profile counts known while other do not - for example when LTO optimizing |

582 | partly profiled program or when profile was lost due to COMDAT merging. |

583 | |

584 | For this reason profile_count tracks more information than |

585 | just unsigned integer and it is also ready for profile mismatches. |

586 | The API of this data type represent operations that are natural |

587 | on profile counts - sum, difference and operation with scales and |

588 | probabilities. All operations are safe by never getting negative counts |

589 | and they do end up in uninitialized scale if any of the parameters is |

590 | uninitialized. |

591 | |

592 | All comparsions that are three state and handling of probabilities. Thus |

593 | a < b is not equal to !(a >= b). |

594 | |

595 | The following pre-defined counts are available: |

596 | |

597 | profile_count::zero () for code that is known to execute zero times at |

598 | runtime (this can be detected statically i.e. for paths leading to |

599 | abort (); |

600 | profile_count::one () for code that is known to execute once (such as |

601 | main () function |

602 | profile_count::uninitialized () for unknown execution count. |

603 | |

604 | */ |

605 | |

606 | class sreal; |

607 | |

608 | class GTY(()) profile_count |

609 | { |

610 | public: |

611 | /* Use 62bit to hold basic block counters. Should be at least |

612 | 64bit. Although a counter cannot be negative, we use a signed |

613 | type to hold various extra stages. */ |

614 | |

615 | static const int n_bits = 61; |

616 | private: |

617 | static const uint64_t max_count = ((uint64_t) 1 << n_bits) - 2; |

618 | static const uint64_t uninitialized_count = ((uint64_t) 1 << n_bits) - 1; |

619 | |

620 | uint64_t m_val : n_bits; |

621 | enum profile_quality m_quality : 3; |

622 | |

623 | /* Return true if both values can meaningfully appear in single function |

624 | body. We have either all counters in function local or global, otherwise |

625 | operations between them are not really defined well. */ |

626 | bool compatible_p (const profile_count other) const |

627 | { |

628 | if (!initialized_p () || !other.initialized_p ()) |

629 | return true; |

630 | if (*this == profile_count::zero () |

631 | || other == profile_count::zero ()) |

632 | return true; |

633 | return ipa_p () == other.ipa_p (); |

634 | } |

635 | public: |

636 | |

637 | /* Used for counters which are expected to be never executed. */ |

638 | static profile_count zero () |

639 | { |

640 | return from_gcov_type (0); |

641 | } |

642 | static profile_count adjusted_zero () |

643 | { |

644 | profile_count c; |

645 | c.m_val = 0; |

646 | c.m_quality = profile_adjusted; |

647 | return c; |

648 | } |

649 | static profile_count guessed_zero () |

650 | { |

651 | profile_count c; |

652 | c.m_val = 0; |

653 | c.m_quality = profile_guessed; |

654 | return c; |

655 | } |

656 | static profile_count one () |

657 | { |

658 | return from_gcov_type (1); |

659 | } |

660 | /* Value of counters which has not been initialized. Either because |

661 | initialization did not happen yet or because profile is unknown. */ |

662 | static profile_count uninitialized () |

663 | { |

664 | profile_count c; |

665 | c.m_val = uninitialized_count; |

666 | c.m_quality = profile_guessed_local; |

667 | return c; |

668 | } |

669 | |

670 | /* Conversion to gcov_type is lossy. */ |

671 | gcov_type to_gcov_type () const |

672 | { |

673 | gcc_checking_assert (initialized_p ()); |

674 | return m_val; |

675 | } |

676 | |

677 | /* Return true if value has been initialized. */ |

678 | bool initialized_p () const |

679 | { |

680 | return m_val != uninitialized_count; |

681 | } |

682 | /* Return true if value can be trusted. */ |

683 | bool reliable_p () const |

684 | { |

685 | return m_quality >= profile_adjusted; |

686 | } |

687 | /* Return true if vlaue can be operated inter-procedurally. */ |

688 | bool ipa_p () const |

689 | { |

690 | return !initialized_p () || m_quality >= profile_guessed_global0; |

691 | } |

692 | |

693 | /* When merging basic blocks, the two different profile counts are unified. |

694 | Return true if this can be done without losing info about profile. |

695 | The only case we care about here is when first BB contains something |

696 | that makes it terminate in a way not visible in CFG. */ |

697 | bool ok_for_merging (profile_count other) const |

698 | { |

699 | if (m_quality < profile_adjusted |

700 | || other.m_quality < profile_adjusted) |

701 | return true; |

702 | return !(other < *this); |

703 | } |

704 | |

705 | /* When merging two BBs with different counts, pick common count that looks |

706 | most representative. */ |

707 | profile_count merge (profile_count other) const |

708 | { |

709 | if (*this == other || !other.initialized_p () |

710 | || m_quality > other.m_quality) |

711 | return *this; |

712 | if (other.m_quality > m_quality |

713 | || other > *this) |

714 | return other; |

715 | return *this; |

716 | } |

717 | |

718 | /* Basic operations. */ |

719 | bool operator== (const profile_count &other) const |

720 | { |

721 | return m_val == other.m_val && m_quality == other.m_quality; |

722 | } |

723 | profile_count operator+ (const profile_count &other) const |

724 | { |

725 | if (other == profile_count::zero ()) |

726 | return *this; |

727 | if (*this == profile_count::zero ()) |

728 | return other; |

729 | if (!initialized_p () || !other.initialized_p ()) |

730 | return profile_count::uninitialized (); |

731 | |

732 | profile_count ret; |

733 | gcc_checking_assert (compatible_p (other)); |

734 | ret.m_val = m_val + other.m_val; |

735 | ret.m_quality = MIN (m_quality, other.m_quality); |

736 | return ret; |

737 | } |

738 | profile_count &operator+= (const profile_count &other) |

739 | { |

740 | if (other == profile_count::zero ()) |

741 | return *this; |

742 | if (*this == profile_count::zero ()) |

743 | { |

744 | *this = other; |

745 | return *this; |

746 | } |

747 | if (!initialized_p () || !other.initialized_p ()) |

748 | return *this = profile_count::uninitialized (); |

749 | else |

750 | { |

751 | gcc_checking_assert (compatible_p (other)); |

752 | m_val += other.m_val; |

753 | m_quality = MIN (m_quality, other.m_quality); |

754 | } |

755 | return *this; |

756 | } |

757 | profile_count operator- (const profile_count &other) const |

758 | { |

759 | if (*this == profile_count::zero () || other == profile_count::zero ()) |

760 | return *this; |

761 | if (!initialized_p () || !other.initialized_p ()) |

762 | return profile_count::uninitialized (); |

763 | gcc_checking_assert (compatible_p (other)); |

764 | profile_count ret; |

765 | ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0; |

766 | ret.m_quality = MIN (m_quality, other.m_quality); |

767 | return ret; |

768 | } |

769 | profile_count &operator-= (const profile_count &other) |

770 | { |

771 | if (*this == profile_count::zero () || other == profile_count::zero ()) |

772 | return *this; |

773 | if (!initialized_p () || !other.initialized_p ()) |

774 | return *this = profile_count::uninitialized (); |

775 | else |

776 | { |

777 | gcc_checking_assert (compatible_p (other)); |

778 | m_val = m_val >= other.m_val ? m_val - other.m_val: 0; |

779 | m_quality = MIN (m_quality, other.m_quality); |

780 | } |

781 | return *this; |

782 | } |

783 | |

784 | /* Return false if profile_count is bogus. */ |

785 | bool verify () const |

786 | { |

787 | return m_val != uninitialized_count || m_quality == profile_guessed_local; |

788 | } |

789 | |

790 | /* Comparsions are three-state and conservative. False is returned if |

791 | the inequality can not be decided. */ |

792 | bool operator< (const profile_count &other) const |

793 | { |

794 | if (!initialized_p () || !other.initialized_p ()) |

795 | return false; |

796 | if (*this == profile_count::zero ()) |

797 | return !(other == profile_count::zero ()); |

798 | if (other == profile_count::zero ()) |

799 | return false; |

800 | gcc_checking_assert (compatible_p (other)); |

801 | return m_val < other.m_val; |

802 | } |

803 | bool operator> (const profile_count &other) const |

804 | { |

805 | if (!initialized_p () || !other.initialized_p ()) |

806 | return false; |

807 | if (*this == profile_count::zero ()) |

808 | return false; |

809 | if (other == profile_count::zero ()) |

810 | return !(*this == profile_count::zero ()); |

811 | gcc_checking_assert (compatible_p (other)); |

812 | return initialized_p () && other.initialized_p () && m_val > other.m_val; |

813 | } |

814 | bool operator< (const gcov_type other) const |

815 | { |

816 | gcc_checking_assert (ipa_p ()); |

817 | gcc_checking_assert (other >= 0); |

818 | return initialized_p () && m_val < (uint64_t) other; |

819 | } |

820 | bool operator> (const gcov_type other) const |

821 | { |

822 | gcc_checking_assert (ipa_p ()); |

823 | gcc_checking_assert (other >= 0); |

824 | return initialized_p () && m_val > (uint64_t) other; |

825 | } |

826 | |

827 | bool operator<= (const profile_count &other) const |

828 | { |

829 | if (!initialized_p () || !other.initialized_p ()) |

830 | return false; |

831 | if (*this == profile_count::zero ()) |

832 | return true; |

833 | if (other == profile_count::zero ()) |

834 | return (*this == profile_count::zero ()); |

835 | gcc_checking_assert (compatible_p (other)); |

836 | return m_val <= other.m_val; |

837 | } |

838 | bool operator>= (const profile_count &other) const |

839 | { |

840 | if (!initialized_p () || !other.initialized_p ()) |

841 | return false; |

842 | if (other == profile_count::zero ()) |

843 | return true; |

844 | if (*this == profile_count::zero ()) |

845 | return !(other == profile_count::zero ()); |

846 | gcc_checking_assert (compatible_p (other)); |

847 | return m_val >= other.m_val; |

848 | } |

849 | bool operator<= (const gcov_type other) const |

850 | { |

851 | gcc_checking_assert (ipa_p ()); |

852 | gcc_checking_assert (other >= 0); |

853 | return initialized_p () && m_val <= (uint64_t) other; |

854 | } |

855 | bool operator>= (const gcov_type other) const |

856 | { |

857 | gcc_checking_assert (ipa_p ()); |

858 | gcc_checking_assert (other >= 0); |

859 | return initialized_p () && m_val >= (uint64_t) other; |

860 | } |

861 | /* Return true when value is not zero and can be used for scaling. |

862 | This is different from *this > 0 because that requires counter to |

863 | be IPA. */ |

864 | bool nonzero_p () const |

865 | { |

866 | return initialized_p () && m_val != 0; |

867 | } |

868 | |

869 | /* Make counter forcingly nonzero. */ |

870 | profile_count force_nonzero () const |

871 | { |

872 | if (!initialized_p ()) |

873 | return *this; |

874 | profile_count ret = *this; |

875 | if (ret.m_val == 0) |

876 | ret.m_val = 1; |

877 | return ret; |

878 | } |

879 | |

880 | profile_count max (profile_count other) const |

881 | { |

882 | if (!initialized_p ()) |

883 | return other; |

884 | if (!other.initialized_p ()) |

885 | return *this; |

886 | if (*this == profile_count::zero ()) |

887 | return other; |

888 | if (other == profile_count::zero ()) |

889 | return *this; |

890 | gcc_checking_assert (compatible_p (other)); |

891 | if (m_val < other.m_val || (m_val == other.m_val |

892 | && m_quality < other.m_quality)) |

893 | return other; |

894 | return *this; |

895 | } |

896 | |

897 | /* PROB is a probability in scale 0...REG_BR_PROB_BASE. Scale counter |

898 | accordingly. */ |

899 | profile_count apply_probability (int prob) const |

900 | { |

901 | gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE); |

902 | if (m_val == 0) |

903 | return *this; |

904 | if (!initialized_p ()) |

905 | return profile_count::uninitialized (); |

906 | profile_count ret; |

907 | ret.m_val = RDIV (m_val * prob, REG_BR_PROB_BASE); |

908 | ret.m_quality = MIN (m_quality, profile_adjusted); |

909 | return ret; |

910 | } |

911 | |

912 | /* Scale counter according to PROB. */ |

913 | profile_count apply_probability (profile_probability prob) const |

914 | { |

915 | if (*this == profile_count::zero ()) |

916 | return *this; |

917 | if (prob == profile_probability::never ()) |

918 | return profile_count::zero (); |

919 | if (!initialized_p ()) |

920 | return profile_count::uninitialized (); |

921 | profile_count ret; |

922 | uint64_t tmp; |

923 | safe_scale_64bit (m_val, prob.m_val, profile_probability::max_probability, |

924 | &tmp); |

925 | ret.m_val = tmp; |

926 | ret.m_quality = MIN (m_quality, prob.m_quality); |

927 | return ret; |

928 | } |

929 | /* Return *THIS * NUM / DEN. */ |

930 | profile_count apply_scale (int64_t num, int64_t den) const |

931 | { |

932 | if (m_val == 0) |

933 | return *this; |

934 | if (!initialized_p ()) |

935 | return profile_count::uninitialized (); |

936 | profile_count ret; |

937 | uint64_t tmp; |

938 | |

939 | gcc_checking_assert (num >= 0 && den > 0); |

940 | safe_scale_64bit (m_val, num, den, &tmp); |

941 | ret.m_val = MIN (tmp, max_count); |

942 | ret.m_quality = MIN (m_quality, profile_adjusted); |

943 | return ret; |

944 | } |

945 | profile_count apply_scale (profile_count num, profile_count den) const |

946 | { |

947 | if (*this == profile_count::zero ()) |

948 | return *this; |

949 | if (num == profile_count::zero ()) |

950 | return num; |

951 | if (!initialized_p () || !num.initialized_p () || !den.initialized_p ()) |

952 | return profile_count::uninitialized (); |

953 | if (num == den) |

954 | return *this; |

955 | gcc_checking_assert (den.m_val); |

956 | |

957 | profile_count ret; |

958 | uint64_t val; |

959 | safe_scale_64bit (m_val, num.m_val, den.m_val, &val); |

960 | ret.m_val = MIN (val, max_count); |

961 | ret.m_quality = MIN (MIN (MIN (m_quality, profile_adjusted), |

962 | num.m_quality), den.m_quality); |

963 | if (num.ipa_p () && !ret.ipa_p ()) |

964 | ret.m_quality = MIN (num.m_quality, profile_guessed); |

965 | return ret; |

966 | } |

967 | |

968 | /* Return THIS with quality dropped to GUESSED_LOCAL. */ |

969 | profile_count guessed_local () const |

970 | { |

971 | profile_count ret = *this; |

972 | if (!initialized_p ()) |

973 | return *this; |

974 | ret.m_quality = profile_guessed_local; |

975 | return ret; |

976 | } |

977 | |

978 | /* We know that profile is globally 0 but keep local profile if present. */ |

979 | profile_count global0 () const |

980 | { |

981 | profile_count ret = *this; |

982 | if (!initialized_p ()) |

983 | return *this; |

984 | ret.m_quality = profile_guessed_global0; |

985 | return ret; |

986 | } |

987 | |

988 | /* We know that profile is globally adjusted 0 but keep local profile |

989 | if present. */ |

990 | profile_count global0adjusted () const |

991 | { |

992 | profile_count ret = *this; |

993 | if (!initialized_p ()) |

994 | return *this; |

995 | ret.m_quality = profile_guessed_global0adjusted; |

996 | return ret; |

997 | } |

998 | |

999 | /* Return THIS with quality dropped to GUESSED. */ |

1000 | profile_count guessed () const |

1001 | { |

1002 | profile_count ret = *this; |

1003 | ret.m_quality = MIN (ret.m_quality, profile_guessed); |

1004 | return ret; |

1005 | } |

1006 | |

1007 | /* Return variant of profile counte which is always safe to compare |

1008 | acorss functions. */ |

1009 | profile_count ipa () const |

1010 | { |

1011 | if (m_quality > profile_guessed_global0adjusted) |

1012 | return *this; |

1013 | if (m_quality == profile_guessed_global0) |

1014 | return profile_count::zero (); |

1015 | if (m_quality == profile_guessed_global0adjusted) |

1016 | return profile_count::adjusted_zero (); |

1017 | return profile_count::uninitialized (); |

1018 | } |

1019 | |

1020 | /* Return THIS with quality dropped to AFDO. */ |

1021 | profile_count afdo () const |

1022 | { |

1023 | profile_count ret = *this; |

1024 | ret.m_quality = profile_afdo; |

1025 | return ret; |

1026 | } |

1027 | |

1028 | /* Return probability of event with counter THIS within event with counter |

1029 | OVERALL. */ |

1030 | profile_probability probability_in (const profile_count overall) const |

1031 | { |

1032 | if (*this == profile_count::zero ()) |

1033 | return profile_probability::never (); |

1034 | if (!initialized_p () || !overall.initialized_p () |

1035 | || !overall.m_val) |

1036 | return profile_probability::uninitialized (); |

1037 | profile_probability ret; |

1038 | gcc_checking_assert (compatible_p (overall)); |

1039 | |

1040 | if (overall.m_val < m_val) |

1041 | ret.m_val = profile_probability::max_probability; |

1042 | else |

1043 | ret.m_val = RDIV (m_val * profile_probability::max_probability, |

1044 | overall.m_val); |

1045 | ret.m_quality = MAX (MIN (m_quality, overall.m_quality), profile_guessed); |

1046 | return ret; |

1047 | } |

1048 | |

1049 | int to_frequency (struct function *fun) const; |

1050 | int to_cgraph_frequency (profile_count entry_bb_count) const; |

1051 | sreal to_sreal_scale (profile_count in, bool *known = NULL) const; |

1052 | |

1053 | /* Output THIS to F. */ |

1054 | void dump (FILE *f) const; |

1055 | |

1056 | /* Print THIS to stderr. */ |

1057 | void debug () const; |

1058 | |

1059 | /* Return true if THIS is known to differ significantly from OTHER. */ |

1060 | bool differs_from_p (profile_count other) const; |

1061 | |

1062 | /* We want to scale profile across function boundary from NUM to DEN. |

1063 | Take care of the side case when NUM and DEN are zeros of incompatible |

1064 | kinds. */ |

1065 | static void adjust_for_ipa_scaling (profile_count *num, profile_count *den); |

1066 | |

1067 | /* THIS is a count of bb which is known to be executed IPA times. |

1068 | Combine this information into bb counter. This means returning IPA |

1069 | if it is nonzero, not changing anything if IPA is uninitialized |

1070 | and if IPA is zero, turning THIS into corresponding local profile with |

1071 | global0. */ |

1072 | profile_count combine_with_ipa_count (profile_count ipa); |

1073 | |

1074 | /* The profiling runtime uses gcov_type, which is usually 64bit integer. |

1075 | Conversions back and forth are used to read the coverage and get it |

1076 | into internal representation. */ |

1077 | static profile_count from_gcov_type (gcov_type v); |

1078 | |

1079 | /* LTO streaming support. */ |

1080 | static profile_count stream_in (struct lto_input_block *); |

1081 | void stream_out (struct output_block *); |

1082 | void stream_out (struct lto_output_stream *); |

1083 | }; |

1084 | #endif |

1085 |