1/* Profile counter container type.
2 Copyright (C) 2017-2023 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
24struct function;
25struct profile_count;
26class sreal;
27
28/* Quality of the profile count. Because gengtype does not support enums
29 inside of classes, this is in global namespace. */
30enum profile_quality {
31 /* Uninitialized value. */
32 UNINITIALIZED_PROFILE,
33
34 /* Profile is based on static branch prediction heuristics and may
35 or may not match reality. It is local to function and cannot be compared
36 inter-procedurally. Never used by probabilities (they are always local).
37 */
38 GUESSED_LOCAL,
39
40 /* Profile was read by feedback and was 0, we used local heuristics to guess
41 better. This is the case of functions not run in profile feedback.
42 Never used by probabilities. */
43 GUESSED_GLOBAL0,
44
45 /* Same as GUESSED_GLOBAL0 but global count is adjusted 0. */
46 GUESSED_GLOBAL0_ADJUSTED,
47
48 /* Profile is based on static branch prediction heuristics. It may or may
49 not reflect the reality but it can be compared interprocedurally
50 (for example, we inlined function w/o profile feedback into function
51 with feedback and propagated from that).
52 Never used by probabilities. */
53 GUESSED,
54
55 /* Profile was determined by autofdo. */
56 AFDO,
57
58 /* Profile was originally based on feedback but it was adjusted
59 by code duplicating optimization. It may not precisely reflect the
60 particular code path. */
61 ADJUSTED,
62
63 /* Profile was read from profile feedback or determined by accurate static
64 method. */
65 PRECISE
66};
67
68extern const char *profile_quality_as_string (enum profile_quality);
69extern bool parse_profile_quality (const char *value,
70 profile_quality *quality);
71
72/* The base value for branch probability notes and edge probabilities. */
73#define REG_BR_PROB_BASE 10000
74
75#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
76
77bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res);
78
79/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
80
81inline bool
82safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
83{
84#if (GCC_VERSION >= 5000)
85 uint64_t tmp;
86 if (!__builtin_mul_overflow (a, b, &tmp)
87 && !__builtin_add_overflow (tmp, c/2, &tmp))
88 {
89 *res = tmp / c;
90 return true;
91 }
92 if (c == 1)
93 {
94 *res = (uint64_t) -1;
95 return false;
96 }
97#else
98 if (a < ((uint64_t)1 << 31)
99 && b < ((uint64_t)1 << 31)
100 && c < ((uint64_t)1 << 31))
101 {
102 *res = (a * b + (c / 2)) / c;
103 return true;
104 }
105#endif
106 return slow_safe_scale_64bit (a, b, c, res);
107}
108
109/* Data type to hold probabilities. It implements fixed point arithmetics
110 with capping so probability is always in range [0,1] and scaling requiring
111 values greater than 1 needs to be represented otherwise.
112
113 In addition to actual value the quality of profile is tracked and propagated
114 through all operations. Special value UNINITIALIZED_PROFILE is used for probabilities
115 that has not been determined yet (for example because of
116 -fno-guess-branch-probability)
117
118 Typically probabilities are derived from profile feedback (via
119 probability_in_gcov_type), autoFDO or guessed statically and then propagated
120 thorough the compilation.
121
122 Named probabilities are available:
123 - never (0 probability)
124 - guessed_never
125 - very_unlikely (1/2000 probability)
126 - unlikely (1/5 probability)
127 - even (1/2 probability)
128 - likely (4/5 probability)
129 - very_likely (1999/2000 probability)
130 - guessed_always
131 - always
132
133 Named probabilities except for never/always are assumed to be statically
134 guessed and thus not necessarily accurate. The difference between never
135 and guessed_never is that the first one should be used only in case that
136 well behaving program will very likely not execute the "never" path.
137 For example if the path is going to abort () call or it exception handling.
138
139 Always and guessed_always probabilities are symmetric.
140
141 For legacy code we support conversion to/from REG_BR_PROB_BASE based fixpoint
142 integer arithmetics. Once the code is converted to branch probabilities,
143 these conversions will probably go away because they are lossy.
144*/
145
146class GTY((user)) profile_probability
147{
148 static const int n_bits = 29;
149 /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that
150 will lead to harder multiplication sequences. */
151 static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2);
152 static const uint32_t uninitialized_probability
153 = ((uint32_t) 1 << (n_bits - 1)) - 1;
154
155 uint32_t m_val : 29;
156 enum profile_quality m_quality : 3;
157
158 friend struct profile_count;
159public:
160 profile_probability (): m_val (uninitialized_probability),
161 m_quality (GUESSED)
162 {}
163
164 profile_probability (uint32_t val, profile_quality quality):
165 m_val (val), m_quality (quality)
166 {}
167
168 /* Named probabilities. */
169 static profile_probability never ()
170 {
171 profile_probability ret;
172 ret.m_val = 0;
173 ret.m_quality = PRECISE;
174 return ret;
175 }
176
177 static profile_probability guessed_never ()
178 {
179 profile_probability ret;
180 ret.m_val = 0;
181 ret.m_quality = GUESSED;
182 return ret;
183 }
184
185 static profile_probability very_unlikely ()
186 {
187 /* Be consistent with PROB_VERY_UNLIKELY in predict.h. */
188 profile_probability r = guessed_always () / 2000;
189 r.m_val--;
190 return r;
191 }
192
193 static profile_probability unlikely ()
194 {
195 /* Be consistent with PROB_VERY_LIKELY in predict.h. */
196 profile_probability r = guessed_always () / 5;
197 r.m_val--;
198 return r;
199 }
200
201 static profile_probability even ()
202 {
203 return guessed_always () / 2;
204 }
205
206 static profile_probability very_likely ()
207 {
208 return always () - very_unlikely ();
209 }
210
211 static profile_probability likely ()
212 {
213 return always () - unlikely ();
214 }
215 /* Return true when value is not zero and can be used for scaling. */
216 bool nonzero_p () const
217 {
218 return initialized_p () && m_val != 0;
219 }
220
221 static profile_probability guessed_always ()
222 {
223 profile_probability ret;
224 ret.m_val = max_probability;
225 ret.m_quality = GUESSED;
226 return ret;
227 }
228
229 static profile_probability always ()
230 {
231 profile_probability ret;
232 ret.m_val = max_probability;
233 ret.m_quality = PRECISE;
234 return ret;
235 }
236
237 /* Probabilities which has not been initialized. Either because
238 initialization did not happen yet or because profile is unknown. */
239 static profile_probability uninitialized ()
240 {
241 profile_probability c;
242 c.m_val = uninitialized_probability;
243 c.m_quality = GUESSED;
244 return c;
245 }
246
247 /* Return true if value has been initialized. */
248 bool initialized_p () const
249 {
250 return m_val != uninitialized_probability;
251 }
252
253 /* Return true if value can be trusted. */
254 bool reliable_p () const
255 {
256 return m_quality >= ADJUSTED;
257 }
258
259 /* Conversion from and to REG_BR_PROB_BASE integer fixpoint arithmetics.
260 this is mostly to support legacy code and should go away. */
261 static profile_probability from_reg_br_prob_base (int v)
262 {
263 profile_probability ret;
264 gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE);
265 ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE);
266 ret.m_quality = GUESSED;
267 return ret;
268 }
269
270 /* Return THIS with quality set to ADJUSTED. */
271 profile_probability adjusted () const
272 {
273 profile_probability ret = *this;
274 if (!initialized_p ())
275 return *this;
276 ret.m_quality = ADJUSTED;
277 return ret;
278 }
279
280 int to_reg_br_prob_base () const
281 {
282 gcc_checking_assert (initialized_p ());
283 return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability);
284 }
285
286 /* Conversion to and from RTL representation of profile probabilities. */
287 static profile_probability from_reg_br_prob_note (int v)
288 {
289 profile_probability ret;
290 ret.m_val = ((unsigned int)v) / 8;
291 ret.m_quality = (enum profile_quality)(v & 7);
292 return ret;
293 }
294
295 int to_reg_br_prob_note () const
296 {
297 gcc_checking_assert (initialized_p ());
298 int ret = m_val * 8 + m_quality;
299 gcc_checking_assert (from_reg_br_prob_note (ret) == *this);
300 return ret;
301 }
302
303 /* Return VAL1/VAL2. */
304 static profile_probability probability_in_gcov_type
305 (gcov_type val1, gcov_type val2)
306 {
307 profile_probability ret;
308 gcc_checking_assert (val1 >= 0 && val2 > 0);
309 if (val1 > val2)
310 ret.m_val = max_probability;
311 else
312 {
313 uint64_t tmp;
314 safe_scale_64bit (a: val1, b: max_probability, c: val2, res: &tmp);
315 gcc_checking_assert (tmp <= max_probability);
316 ret.m_val = tmp;
317 }
318 ret.m_quality = PRECISE;
319 return ret;
320 }
321
322 /* Basic operations. */
323 bool operator== (const profile_probability &other) const
324 {
325 return m_val == other.m_val && m_quality == other.m_quality;
326 }
327
328 profile_probability operator+ (const profile_probability &other) const
329 {
330 if (other == never ())
331 return *this;
332 if (*this == never ())
333 return other;
334 if (!initialized_p () || !other.initialized_p ())
335 return uninitialized ();
336
337 profile_probability ret;
338 ret.m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability);
339 ret.m_quality = MIN (m_quality, other.m_quality);
340 return ret;
341 }
342
343 profile_probability &operator+= (const profile_probability &other)
344 {
345 if (other == never ())
346 return *this;
347 if (*this == never ())
348 {
349 *this = other;
350 return *this;
351 }
352 if (!initialized_p () || !other.initialized_p ())
353 return *this = uninitialized ();
354 else
355 {
356 m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability);
357 m_quality = MIN (m_quality, other.m_quality);
358 }
359 return *this;
360 }
361
362 profile_probability operator- (const profile_probability &other) const
363 {
364 if (*this == never ()
365 || other == never ())
366 return *this;
367 if (!initialized_p () || !other.initialized_p ())
368 return uninitialized ();
369 profile_probability ret;
370 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
371 ret.m_quality = MIN (m_quality, other.m_quality);
372 return ret;
373 }
374
375 profile_probability &operator-= (const profile_probability &other)
376 {
377 if (*this == never ()
378 || other == never ())
379 return *this;
380 if (!initialized_p () || !other.initialized_p ())
381 return *this = uninitialized ();
382 else
383 {
384 m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
385 m_quality = MIN (m_quality, other.m_quality);
386 }
387 return *this;
388 }
389
390 profile_probability operator* (const profile_probability &other) const
391 {
392 if (*this == never ()
393 || other == never ())
394 return never ();
395 if (!initialized_p () || !other.initialized_p ())
396 return uninitialized ();
397 profile_probability ret;
398 ret.m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability);
399 ret.m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED);
400 return ret;
401 }
402
403 profile_probability &operator*= (const profile_probability &other)
404 {
405 if (*this == never ()
406 || other == never ())
407 return *this = never ();
408 if (!initialized_p () || !other.initialized_p ())
409 return *this = uninitialized ();
410 else
411 {
412 m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability);
413 m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED);
414 }
415 return *this;
416 }
417
418 profile_probability operator/ (const profile_probability &other) const
419 {
420 if (*this == never ())
421 return never ();
422 if (!initialized_p () || !other.initialized_p ())
423 return uninitialized ();
424 profile_probability ret;
425 /* If we get probability above 1, mark it as unreliable and return 1. */
426 if (m_val >= other.m_val)
427 {
428 ret.m_val = max_probability;
429 ret.m_quality = MIN (MIN (m_quality, other.m_quality),
430 GUESSED);
431 return ret;
432 }
433 else if (!m_val)
434 ret.m_val = 0;
435 else
436 {
437 gcc_checking_assert (other.m_val);
438 ret.m_val = MIN (RDIV ((uint64_t)m_val * max_probability,
439 other.m_val),
440 max_probability);
441 }
442 ret.m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED);
443 return ret;
444 }
445
446 profile_probability &operator/= (const profile_probability &other)
447 {
448 if (*this == never ())
449 return *this = never ();
450 if (!initialized_p () || !other.initialized_p ())
451 return *this = uninitialized ();
452 else
453 {
454 /* If we get probability above 1, mark it as unreliable
455 and return 1. */
456 if (m_val > other.m_val)
457 {
458 m_val = max_probability;
459 m_quality = MIN (MIN (m_quality, other.m_quality),
460 GUESSED);
461 return *this;
462 }
463 else if (!m_val)
464 ;
465 else
466 {
467 gcc_checking_assert (other.m_val);
468 m_val = MIN (RDIV ((uint64_t)m_val * max_probability,
469 other.m_val),
470 max_probability);
471 }
472 m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED);
473 }
474 return *this;
475 }
476
477 /* Split *THIS (ORIG) probability into 2 probabilities, such that
478 the returned one (FIRST) is *THIS * CPROB and *THIS is
479 adjusted (SECOND) so that FIRST + FIRST.invert () * SECOND
480 == ORIG. This is useful e.g. when splitting a conditional
481 branch like:
482 if (cond)
483 goto lab; // ORIG probability
484 into
485 if (cond1)
486 goto lab; // FIRST = ORIG * CPROB probability
487 if (cond2)
488 goto lab; // SECOND probability
489 such that the overall probability of jumping to lab remains
490 the same. CPROB gives the relative probability between the
491 branches. */
492 profile_probability split (const profile_probability &cprob)
493 {
494 profile_probability ret = *this * cprob;
495 /* The following is equivalent to:
496 *this = cprob.invert () * *this / ret.invert ();
497 Avoid scaling when overall outcome is supposed to be always.
498 Without knowing that one is inverse of other, the result would be
499 conservative. */
500 if (!(*this == always ()))
501 *this = (*this - ret) / ret.invert ();
502 return ret;
503 }
504
505 gcov_type apply (gcov_type val) const
506 {
507 if (*this == uninitialized ())
508 return val / 2;
509 return RDIV (val * m_val, max_probability);
510 }
511
512 /* Return 1-*THIS. */
513 profile_probability invert () const
514 {
515 return always() - *this;
516 }
517
518 /* Return THIS with quality dropped to GUESSED. */
519 profile_probability guessed () const
520 {
521 profile_probability ret = *this;
522 ret.m_quality = GUESSED;
523 return ret;
524 }
525
526 /* Return THIS with quality dropped to AFDO. */
527 profile_probability afdo () const
528 {
529 profile_probability ret = *this;
530 ret.m_quality = AFDO;
531 return ret;
532 }
533
534 /* Return *THIS * NUM / DEN. */
535 profile_probability apply_scale (int64_t num, int64_t den) const
536 {
537 if (*this == never ())
538 return *this;
539 if (!initialized_p ())
540 return uninitialized ();
541 profile_probability ret;
542 uint64_t tmp;
543 safe_scale_64bit (a: m_val, b: num, c: den, res: &tmp);
544 ret.m_val = MIN (tmp, max_probability);
545 ret.m_quality = MIN (m_quality, ADJUSTED);
546 return ret;
547 }
548
549 /* Return *THIS * NUM / DEN. */
550 profile_probability apply_scale (profile_probability num,
551 profile_probability den) const
552 {
553 if (*this == never ())
554 return *this;
555 if (num == never ())
556 return num;
557 if (!initialized_p () || !num.initialized_p () || !den.initialized_p ())
558 return uninitialized ();
559 if (num == den)
560 return *this;
561 gcc_checking_assert (den.m_val);
562
563 profile_probability ret;
564 uint64_t val;
565 safe_scale_64bit (a: m_val, b: num.m_val, c: den.m_val, res: &val);
566 ret.m_val = MIN (val, max_probability);
567 ret.m_quality = MIN (MIN (MIN (m_quality, ADJUSTED),
568 num.m_quality), den.m_quality);
569 return ret;
570 }
571
572 /* Return true when the probability of edge is reliable.
573
574 The profile guessing code is good at predicting branch outcome (i.e.
575 taken/not taken), that is predicted right slightly over 75% of time.
576 It is however notoriously poor on predicting the probability itself.
577 In general the profile appear a lot flatter (with probabilities closer
578 to 50%) than the reality so it is bad idea to use it to drive optimization
579 such as those disabling dynamic branch prediction for well predictable
580 branches.
581
582 There are two exceptions - edges leading to noreturn edges and edges
583 predicted by number of iterations heuristics are predicted well. This macro
584 should be able to distinguish those, but at the moment it simply check for
585 noreturn heuristic that is only one giving probability over 99% or bellow
586 1%. In future we might want to propagate reliability information across the
587 CFG if we find this information useful on multiple places. */
588 bool probably_reliable_p () const
589 {
590 if (m_quality >= ADJUSTED)
591 return true;
592 if (!initialized_p ())
593 return false;
594 return m_val < max_probability / 100
595 || m_val > max_probability - max_probability / 100;
596 }
597
598 /* Return false if profile_probability is bogus. */
599 bool verify () const
600 {
601 gcc_checking_assert (m_quality != UNINITIALIZED_PROFILE);
602 if (m_val == uninitialized_probability)
603 return m_quality == GUESSED;
604 else if (m_quality < GUESSED)
605 return false;
606 return m_val <= max_probability;
607 }
608
609 /* Comparisons are three-state and conservative. False is returned if
610 the inequality cannot be decided. */
611 bool operator< (const profile_probability &other) const
612 {
613 return initialized_p () && other.initialized_p () && m_val < other.m_val;
614 }
615
616 bool operator> (const profile_probability &other) const
617 {
618 return initialized_p () && other.initialized_p () && m_val > other.m_val;
619 }
620
621 bool operator<= (const profile_probability &other) const
622 {
623 return initialized_p () && other.initialized_p () && m_val <= other.m_val;
624 }
625
626 bool operator>= (const profile_probability &other) const
627 {
628 return initialized_p () && other.initialized_p () && m_val >= other.m_val;
629 }
630
631 profile_probability operator* (int64_t num) const
632 {
633 return apply_scale (num, den: 1);
634 }
635
636 profile_probability operator*= (int64_t num)
637 {
638 *this = apply_scale (num, den: 1);
639 return *this;
640 }
641
642 profile_probability operator/ (int64_t den) const
643 {
644 return apply_scale (num: 1, den);
645 }
646
647 profile_probability operator/= (int64_t den)
648 {
649 *this = apply_scale (num: 1, den);
650 return *this;
651 }
652
653 /* Compute n-th power. */
654 profile_probability pow (int) const;
655
656 /* Compute sware root. */
657 profile_probability sqrt () const;
658
659 /* Get the value of the count. */
660 uint32_t value () const { return m_val; }
661
662 /* Get the quality of the count. */
663 enum profile_quality quality () const { return m_quality; }
664
665 /* Output THIS to F. */
666 void dump (FILE *f) const;
667
668 /* Output THIS to BUFFER. */
669 void dump (char *buffer) const;
670
671 /* Print THIS to stderr. */
672 void debug () const;
673
674 /* Return true if THIS is known to differ significantly from OTHER. */
675 bool differs_from_p (profile_probability other) const;
676
677 /* Return if difference is greater than 50%. */
678 bool differs_lot_from_p (profile_probability other) const;
679
680 /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
681 happens with COUNT2 probability. Return probability that either *THIS or
682 OTHER happens. */
683 profile_probability combine_with_count (profile_count count1,
684 profile_probability other,
685 profile_count count2) const;
686
687 /* Return probability as sreal. */
688 sreal to_sreal () const;
689 /* LTO streaming support. */
690 static profile_probability stream_in (class lto_input_block *);
691 void stream_out (struct output_block *);
692 void stream_out (struct lto_output_stream *);
693};
694
695/* Main data type to hold profile counters in GCC. Profile counts originate
696 either from profile feedback, static profile estimation or both. We do not
697 perform whole program profile propagation and thus profile estimation
698 counters are often local to function, while counters from profile feedback
699 (or special cases of profile estimation) can be used inter-procedurally.
700
701 There are 3 basic types
702 1) local counters which are result of intra-procedural static profile
703 estimation.
704 2) ipa counters which are result of profile feedback or special case
705 of static profile estimation (such as in function main).
706 3) counters which counts as 0 inter-procedurally (because given function
707 was never run in train feedback) but they hold local static profile
708 estimate.
709
710 Counters of type 1 and 3 cannot be mixed with counters of different type
711 within operation (because whole function should use one type of counter)
712 with exception that global zero mix in most operations where outcome is
713 well defined.
714
715 To take local counter and use it inter-procedurally use ipa member function
716 which strips information irrelevant at the inter-procedural level.
717
718 Counters are 61bit integers representing number of executions during the
719 train run or normalized frequency within the function.
720
721 As the profile is maintained during the compilation, many adjustments are
722 made. Not all transformations can be made precisely, most importantly
723 when code is being duplicated. It also may happen that part of CFG has
724 profile counts known while other do not - for example when LTO optimizing
725 partly profiled program or when profile was lost due to COMDAT merging.
726
727 For this reason profile_count tracks more information than
728 just unsigned integer and it is also ready for profile mismatches.
729 The API of this data type represent operations that are natural
730 on profile counts - sum, difference and operation with scales and
731 probabilities. All operations are safe by never getting negative counts
732 and they do end up in uninitialized scale if any of the parameters is
733 uninitialized.
734
735 All comparisons that are three state and handling of probabilities. Thus
736 a < b is not equal to !(a >= b).
737
738 The following pre-defined counts are available:
739
740 profile_count::zero () for code that is known to execute zero times at
741 runtime (this can be detected statically i.e. for paths leading to
742 abort ();
743 profile_count::one () for code that is known to execute once (such as
744 main () function
745 profile_count::uninitialized () for unknown execution count.
746
747 */
748
749struct GTY(()) profile_count
750{
751public:
752 /* Use 62bit to hold basic block counters. Should be at least
753 64bit. Although a counter cannot be negative, we use a signed
754 type to hold various extra stages. */
755
756 static const int n_bits = 61;
757 static const uint64_t max_count = ((uint64_t) 1 << n_bits) - 2;
758private:
759 static const uint64_t uninitialized_count = ((uint64_t) 1 << n_bits) - 1;
760
761#if defined (__arm__) && (__GNUC__ >= 6 && __GNUC__ <= 8)
762 /* Work-around for PR88469. A bug in the gcc-6/7/8 PCS layout code
763 incorrectly detects the alignment of a structure where the only
764 64-bit aligned object is a bit-field. We force the alignment of
765 the entire field to mitigate this. */
766#define UINT64_BIT_FIELD_ALIGN __attribute__ ((aligned(8)))
767#else
768#define UINT64_BIT_FIELD_ALIGN
769#endif
770 uint64_t UINT64_BIT_FIELD_ALIGN m_val : n_bits;
771#undef UINT64_BIT_FIELD_ALIGN
772 enum profile_quality m_quality : 3;
773public:
774
775 /* Return true if both values can meaningfully appear in single function
776 body. We have either all counters in function local or global, otherwise
777 operations between them are not really defined well. */
778 bool compatible_p (const profile_count other) const
779 {
780 if (!initialized_p () || !other.initialized_p ())
781 return true;
782 if (*this == zero ()
783 || other == zero ())
784 return true;
785 /* Do not allow nonzero global profile together with local guesses
786 that are globally0. */
787 if (ipa ().nonzero_p ()
788 && !(other.ipa () == other))
789 return false;
790 if (other.ipa ().nonzero_p ()
791 && !(ipa () == *this))
792 return false;
793
794 return ipa_p () == other.ipa_p ();
795 }
796
797 /* Used for counters which are expected to be never executed. */
798 static profile_count zero ()
799 {
800 return from_gcov_type (v: 0);
801 }
802
803 static profile_count adjusted_zero ()
804 {
805 profile_count c;
806 c.m_val = 0;
807 c.m_quality = ADJUSTED;
808 return c;
809 }
810
811 static profile_count guessed_zero ()
812 {
813 profile_count c;
814 c.m_val = 0;
815 c.m_quality = GUESSED;
816 return c;
817 }
818
819 static profile_count one ()
820 {
821 return from_gcov_type (v: 1);
822 }
823
824 /* Value of counters which has not been initialized. Either because
825 initialization did not happen yet or because profile is unknown. */
826 static profile_count uninitialized ()
827 {
828 profile_count c;
829 c.m_val = uninitialized_count;
830 c.m_quality = GUESSED_LOCAL;
831 return c;
832 }
833
834 /* Conversion to gcov_type is lossy. */
835 gcov_type to_gcov_type () const
836 {
837 gcc_checking_assert (initialized_p ());
838 return m_val;
839 }
840
841 /* Return true if value has been initialized. */
842 bool initialized_p () const
843 {
844 return m_val != uninitialized_count;
845 }
846
847 /* Return true if value can be trusted. */
848 bool reliable_p () const
849 {
850 return m_quality >= ADJUSTED;
851 }
852
853 /* Return true if value can be operated inter-procedurally. */
854 bool ipa_p () const
855 {
856 return !initialized_p () || m_quality >= GUESSED_GLOBAL0;
857 }
858
859 /* Return true if quality of profile is precise. */
860 bool precise_p () const
861 {
862 return m_quality == PRECISE;
863 }
864
865 /* Get the value of the count. */
866 uint64_t value () const { return m_val; }
867
868 /* Get the quality of the count. */
869 enum profile_quality quality () const { return m_quality; }
870
871 /* When merging basic blocks, the two different profile counts are unified.
872 Return true if this can be done without losing info about profile.
873 The only case we care about here is when first BB contains something
874 that makes it terminate in a way not visible in CFG. */
875 bool ok_for_merging (profile_count other) const
876 {
877 if (m_quality < ADJUSTED
878 || other.m_quality < ADJUSTED)
879 return true;
880 return !(other < *this);
881 }
882
883 /* When merging two BBs with different counts, pick common count that looks
884 most representative. */
885 profile_count merge (profile_count other) const
886 {
887 if (*this == other || !other.initialized_p ()
888 || m_quality > other.m_quality)
889 return *this;
890 if (other.m_quality > m_quality
891 || other > *this)
892 return other;
893 return *this;
894 }
895
896 /* Basic operations. */
897 bool operator== (const profile_count &other) const
898 {
899 return m_val == other.m_val && m_quality == other.m_quality;
900 }
901
902 profile_count operator+ (const profile_count &other) const
903 {
904 if (other == zero ())
905 return *this;
906 if (*this == zero ())
907 return other;
908 if (!initialized_p () || !other.initialized_p ())
909 return uninitialized ();
910
911 profile_count ret;
912 gcc_checking_assert (compatible_p (other));
913 ret.m_val = m_val + other.m_val;
914 ret.m_quality = MIN (m_quality, other.m_quality);
915 return ret;
916 }
917
918 profile_count &operator+= (const profile_count &other)
919 {
920 if (other == zero ())
921 return *this;
922 if (*this == zero ())
923 {
924 *this = other;
925 return *this;
926 }
927 if (!initialized_p () || !other.initialized_p ())
928 return *this = uninitialized ();
929 else
930 {
931 gcc_checking_assert (compatible_p (other));
932 m_val += other.m_val;
933 m_quality = MIN (m_quality, other.m_quality);
934 }
935 return *this;
936 }
937
938 profile_count operator- (const profile_count &other) const
939 {
940 if (*this == zero () || other == zero ())
941 return *this;
942 if (!initialized_p () || !other.initialized_p ())
943 return uninitialized ();
944 gcc_checking_assert (compatible_p (other));
945 profile_count ret;
946 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
947 ret.m_quality = MIN (m_quality, other.m_quality);
948 return ret;
949 }
950
951 profile_count &operator-= (const profile_count &other)
952 {
953 if (*this == zero () || other == zero ())
954 return *this;
955 if (!initialized_p () || !other.initialized_p ())
956 return *this = uninitialized ();
957 else
958 {
959 gcc_checking_assert (compatible_p (other));
960 m_val = m_val >= other.m_val ? m_val - other.m_val: 0;
961 m_quality = MIN (m_quality, other.m_quality);
962 }
963 return *this;
964 }
965
966 /* Return false if profile_count is bogus. */
967 bool verify () const
968 {
969 gcc_checking_assert (m_quality != UNINITIALIZED_PROFILE);
970 return m_val != uninitialized_count || m_quality == GUESSED_LOCAL;
971 }
972
973 /* Comparisons are three-state and conservative. False is returned if
974 the inequality cannot be decided. */
975 bool operator< (const profile_count &other) const
976 {
977 if (!initialized_p () || !other.initialized_p ())
978 return false;
979 if (*this == zero ())
980 return !(other == zero ());
981 if (other == zero ())
982 return false;
983 gcc_checking_assert (compatible_p (other));
984 return m_val < other.m_val;
985 }
986
987 bool operator> (const profile_count &other) const
988 {
989 if (!initialized_p () || !other.initialized_p ())
990 return false;
991 if (*this == zero ())
992 return false;
993 if (other == zero ())
994 return !(*this == zero ());
995 gcc_checking_assert (compatible_p (other));
996 return initialized_p () && other.initialized_p () && m_val > other.m_val;
997 }
998
999 bool operator< (const gcov_type other) const
1000 {
1001 gcc_checking_assert (ipa_p ());
1002 gcc_checking_assert (other >= 0);
1003 return ipa ().initialized_p () && ipa ().m_val < (uint64_t) other;
1004 }
1005
1006 bool operator> (const gcov_type other) const
1007 {
1008 gcc_checking_assert (ipa_p ());
1009 gcc_checking_assert (other >= 0);
1010 return ipa ().initialized_p () && ipa ().m_val > (uint64_t) other;
1011 }
1012
1013 bool operator<= (const profile_count &other) const
1014 {
1015 if (!initialized_p () || !other.initialized_p ())
1016 return false;
1017 if (*this == zero ())
1018 return true;
1019 if (other == zero ())
1020 return (*this == zero ());
1021 gcc_checking_assert (compatible_p (other));
1022 return m_val <= other.m_val;
1023 }
1024
1025 bool operator>= (const profile_count &other) const
1026 {
1027 if (!initialized_p () || !other.initialized_p ())
1028 return false;
1029 if (other == zero ())
1030 return true;
1031 if (*this == zero ())
1032 return (other == zero ());
1033 gcc_checking_assert (compatible_p (other));
1034 return m_val >= other.m_val;
1035 }
1036
1037 bool operator<= (const gcov_type other) const
1038 {
1039 gcc_checking_assert (ipa_p ());
1040 gcc_checking_assert (other >= 0);
1041 return ipa ().initialized_p () && ipa ().m_val <= (uint64_t) other;
1042 }
1043
1044 bool operator>= (const gcov_type other) const
1045 {
1046 gcc_checking_assert (ipa_p ());
1047 gcc_checking_assert (other >= 0);
1048 return ipa ().initialized_p () && ipa ().m_val >= (uint64_t) other;
1049 }
1050
1051 profile_count operator* (int64_t num) const
1052 {
1053 return apply_scale (num, den: 1);
1054 }
1055
1056 profile_count operator*= (int64_t num)
1057 {
1058 *this = apply_scale (num, den: 1);
1059 return *this;
1060 }
1061
1062 profile_count operator/ (int64_t den) const
1063 {
1064 return apply_scale (num: 1, den);
1065 }
1066
1067 profile_count operator/= (int64_t den)
1068 {
1069 *this = apply_scale (num: 1, den);
1070 return *this;
1071 }
1072
1073 /* Return true when value is not zero and can be used for scaling.
1074 This is different from *this > 0 because that requires counter to
1075 be IPA. */
1076 bool nonzero_p () const
1077 {
1078 return initialized_p () && m_val != 0;
1079 }
1080
1081 /* Make counter forcibly nonzero. */
1082 profile_count force_nonzero () const
1083 {
1084 if (!initialized_p ())
1085 return *this;
1086 profile_count ret = *this;
1087 if (ret.m_val == 0)
1088 {
1089 ret.m_val = 1;
1090 ret.m_quality = MIN (m_quality, ADJUSTED);
1091 }
1092 return ret;
1093 }
1094
1095 profile_count max (profile_count other) const
1096 {
1097 profile_count val = *this;
1098
1099 /* Always prefer nonzero IPA counts over local counts. */
1100 if (ipa ().nonzero_p () || other.ipa ().nonzero_p ())
1101 {
1102 val = ipa ();
1103 other = other.ipa ();
1104 }
1105 if (!initialized_p ())
1106 return other;
1107 if (!other.initialized_p ())
1108 return *this;
1109 if (*this == zero ())
1110 return other;
1111 if (other == zero ())
1112 return *this;
1113 gcc_checking_assert (compatible_p (other));
1114 if (val.m_val < other.m_val || (m_val == other.m_val
1115 && val.m_quality < other.m_quality))
1116 return other;
1117 return *this;
1118 }
1119
1120 /* PROB is a probability in scale 0...REG_BR_PROB_BASE. Scale counter
1121 accordingly. */
1122 profile_count apply_probability (int prob) const
1123 {
1124 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
1125 if (m_val == 0)
1126 return *this;
1127 if (!initialized_p ())
1128 return uninitialized ();
1129 profile_count ret;
1130 ret.m_val = RDIV (m_val * prob, REG_BR_PROB_BASE);
1131 ret.m_quality = MIN (m_quality, ADJUSTED);
1132 return ret;
1133 }
1134
1135 /* Scale counter according to PROB. */
1136 profile_count apply_probability (profile_probability prob) const
1137 {
1138 if (*this == zero () || prob == profile_probability::always ())
1139 return *this;
1140 if (prob == profile_probability::never ())
1141 return zero ();
1142 if (!initialized_p () || !prob.initialized_p ())
1143 return uninitialized ();
1144 profile_count ret;
1145 uint64_t tmp;
1146 safe_scale_64bit (a: m_val, b: prob.m_val, c: profile_probability::max_probability,
1147 res: &tmp);
1148 ret.m_val = tmp;
1149 ret.m_quality = MIN (m_quality, prob.m_quality);
1150 return ret;
1151 }
1152
1153 /* Return *THIS * NUM / DEN. */
1154 profile_count apply_scale (int64_t num, int64_t den) const
1155 {
1156 if (m_val == 0)
1157 return *this;
1158 if (!initialized_p ())
1159 return uninitialized ();
1160 profile_count ret;
1161 uint64_t tmp;
1162
1163 gcc_checking_assert (num >= 0 && den > 0);
1164 safe_scale_64bit (a: m_val, b: num, c: den, res: &tmp);
1165 ret.m_val = MIN (tmp, max_count);
1166 ret.m_quality = MIN (m_quality, ADJUSTED);
1167 return ret;
1168 }
1169
1170 profile_count apply_scale (profile_count num, profile_count den) const
1171 {
1172 if (*this == zero ())
1173 return *this;
1174 if (num == zero ())
1175 return num;
1176 if (!initialized_p () || !num.initialized_p () || !den.initialized_p ())
1177 return uninitialized ();
1178 if (num == den)
1179 return *this;
1180 gcc_checking_assert (den.m_val);
1181
1182 profile_count ret;
1183 uint64_t val;
1184 safe_scale_64bit (a: m_val, b: num.m_val, c: den.m_val, res: &val);
1185 ret.m_val = MIN (val, max_count);
1186 ret.m_quality = MIN (MIN (MIN (m_quality, ADJUSTED),
1187 num.m_quality), den.m_quality);
1188 /* Be sure that ret is not local if num is global.
1189 Also ensure that ret is not global0 when num is global. */
1190 if (num.ipa_p ())
1191 ret.m_quality = MAX (ret.m_quality,
1192 num == num.ipa () ? GUESSED : num.m_quality);
1193 return ret;
1194 }
1195
1196 /* Return THIS with quality dropped to GUESSED_LOCAL. */
1197 profile_count guessed_local () const
1198 {
1199 profile_count ret = *this;
1200 if (!initialized_p ())
1201 return *this;
1202 ret.m_quality = GUESSED_LOCAL;
1203 return ret;
1204 }
1205
1206 /* We know that profile is globally 0 but keep local profile if present. */
1207 profile_count global0 () const
1208 {
1209 profile_count ret = *this;
1210 if (!initialized_p ())
1211 return *this;
1212 ret.m_quality = GUESSED_GLOBAL0;
1213 return ret;
1214 }
1215
1216 /* We know that profile is globally adjusted 0 but keep local profile
1217 if present. */
1218 profile_count global0adjusted () const
1219 {
1220 profile_count ret = *this;
1221 if (!initialized_p ())
1222 return *this;
1223 ret.m_quality = GUESSED_GLOBAL0_ADJUSTED;
1224 return ret;
1225 }
1226
1227 /* Return THIS with quality dropped to GUESSED. */
1228 profile_count guessed () const
1229 {
1230 profile_count ret = *this;
1231 ret.m_quality = MIN (ret.m_quality, GUESSED);
1232 return ret;
1233 }
1234
1235 /* Return variant of profile count which is always safe to compare
1236 across functions. */
1237 profile_count ipa () const
1238 {
1239 if (m_quality > GUESSED_GLOBAL0_ADJUSTED)
1240 return *this;
1241 if (m_quality == GUESSED_GLOBAL0)
1242 return zero ();
1243 if (m_quality == GUESSED_GLOBAL0_ADJUSTED)
1244 return adjusted_zero ();
1245 return uninitialized ();
1246 }
1247
1248 /* Return THIS with quality dropped to AFDO. */
1249 profile_count afdo () const
1250 {
1251 profile_count ret = *this;
1252 ret.m_quality = AFDO;
1253 return ret;
1254 }
1255
1256 /* Return probability of event with counter THIS within event with counter
1257 OVERALL. */
1258 profile_probability probability_in (const profile_count overall) const
1259 {
1260 if (*this == zero ()
1261 && !(overall == zero ()))
1262 return profile_probability::never ();
1263 if (!initialized_p () || !overall.initialized_p ()
1264 || !overall.m_val)
1265 return profile_probability::uninitialized ();
1266 if (*this == overall && m_quality == PRECISE)
1267 return profile_probability::always ();
1268 profile_probability ret;
1269 gcc_checking_assert (compatible_p (overall));
1270
1271 if (overall.m_val < m_val)
1272 {
1273 ret.m_val = profile_probability::max_probability;
1274 ret.m_quality = GUESSED;
1275 return ret;
1276 }
1277 else
1278 ret.m_val = RDIV (m_val * profile_probability::max_probability,
1279 overall.m_val);
1280 ret.m_quality = MIN (MAX (MIN (m_quality, overall.m_quality),
1281 GUESSED), ADJUSTED);
1282 return ret;
1283 }
1284
1285 /* Return true if profile count is very large, so we risk overflows
1286 with loop transformations. */
1287 bool
1288 very_large_p ()
1289 {
1290 if (!initialized_p ())
1291 return false;
1292 return m_val > max_count / 65536;
1293 }
1294
1295 int to_frequency (struct function *fun) const;
1296 int to_cgraph_frequency (profile_count entry_bb_count) const;
1297 sreal to_sreal_scale (profile_count in, bool *known = NULL) const;
1298
1299 /* Output THIS to F. */
1300 void dump (FILE *f, struct function *fun = NULL) const;
1301
1302 /* Output THIS to BUFFER. */
1303 void dump (char *buffer, struct function *fun = NULL) const;
1304
1305 /* Print THIS to stderr. */
1306 void debug () const;
1307
1308 /* Return true if THIS is known to differ significantly from OTHER. */
1309 bool differs_from_p (profile_count other) const;
1310
1311 /* We want to scale profile across function boundary from NUM to DEN.
1312 Take care of the side case when NUM and DEN are zeros of incompatible
1313 kinds. */
1314 static void adjust_for_ipa_scaling (profile_count *num, profile_count *den);
1315
1316 /* THIS is a count of bb which is known to be executed IPA times.
1317 Combine this information into bb counter. This means returning IPA
1318 if it is nonzero, not changing anything if IPA is uninitialized
1319 and if IPA is zero, turning THIS into corresponding local profile with
1320 global0. */
1321 profile_count combine_with_ipa_count (profile_count ipa);
1322
1323 /* Same as combine_with_ipa_count but inside function with count IPA2. */
1324 profile_count combine_with_ipa_count_within
1325 (profile_count ipa, profile_count ipa2);
1326
1327 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
1328 Conversions back and forth are used to read the coverage and get it
1329 into internal representation. */
1330 static profile_count from_gcov_type (gcov_type v,
1331 profile_quality quality = PRECISE);
1332
1333 /* LTO streaming support. */
1334 static profile_count stream_in (class lto_input_block *);
1335 void stream_out (struct output_block *);
1336 void stream_out (struct lto_output_stream *);
1337};
1338#endif
1339

source code of gcc/profile-count.h