1/* Profile counter container type.
2 Copyright (C) 2017-2024 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 uint64_t ret_val = m_val + other.m_val;
914 ret.m_val = MIN (ret_val, max_count);
915 ret.m_quality = MIN (m_quality, other.m_quality);
916 return ret;
917 }
918
919 profile_count &operator+= (const profile_count &other)
920 {
921 if (other == zero ())
922 return *this;
923 if (*this == zero ())
924 {
925 *this = other;
926 return *this;
927 }
928 if (!initialized_p () || !other.initialized_p ())
929 return *this = uninitialized ();
930 else
931 {
932 gcc_checking_assert (compatible_p (other));
933 uint64_t ret_val = m_val + other.m_val;
934 m_val = MIN (ret_val, max_count);
935 m_quality = MIN (m_quality, other.m_quality);
936 }
937 return *this;
938 }
939
940 profile_count operator- (const profile_count &other) const
941 {
942 if (*this == zero () || other == zero ())
943 return *this;
944 if (!initialized_p () || !other.initialized_p ())
945 return uninitialized ();
946 gcc_checking_assert (compatible_p (other));
947 profile_count ret;
948 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
949 ret.m_quality = MIN (m_quality, other.m_quality);
950 return ret;
951 }
952
953 profile_count &operator-= (const profile_count &other)
954 {
955 if (*this == zero () || other == zero ())
956 return *this;
957 if (!initialized_p () || !other.initialized_p ())
958 return *this = uninitialized ();
959 else
960 {
961 gcc_checking_assert (compatible_p (other));
962 m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
963 m_quality = MIN (m_quality, other.m_quality);
964 }
965 return *this;
966 }
967
968 /* Return false if profile_count is bogus. */
969 bool verify () const
970 {
971 gcc_checking_assert (m_quality != UNINITIALIZED_PROFILE);
972 return m_val != uninitialized_count || m_quality == GUESSED_LOCAL;
973 }
974
975 /* Comparisons are three-state and conservative. False is returned if
976 the inequality cannot be decided. */
977 bool operator< (const profile_count &other) const
978 {
979 if (!initialized_p () || !other.initialized_p ())
980 return false;
981 if (*this == zero ())
982 return !(other == zero ());
983 if (other == zero ())
984 return false;
985 gcc_checking_assert (compatible_p (other));
986 return m_val < other.m_val;
987 }
988
989 bool operator> (const profile_count &other) const
990 {
991 if (!initialized_p () || !other.initialized_p ())
992 return false;
993 if (*this == zero ())
994 return false;
995 if (other == zero ())
996 return !(*this == zero ());
997 gcc_checking_assert (compatible_p (other));
998 return initialized_p () && other.initialized_p () && m_val > other.m_val;
999 }
1000
1001 bool operator< (const gcov_type other) const
1002 {
1003 gcc_checking_assert (ipa_p ());
1004 gcc_checking_assert (other >= 0);
1005 return ipa ().initialized_p () && ipa ().m_val < (uint64_t) other;
1006 }
1007
1008 bool operator> (const gcov_type other) const
1009 {
1010 gcc_checking_assert (ipa_p ());
1011 gcc_checking_assert (other >= 0);
1012 return ipa ().initialized_p () && ipa ().m_val > (uint64_t) other;
1013 }
1014
1015 bool operator<= (const profile_count &other) const
1016 {
1017 if (!initialized_p () || !other.initialized_p ())
1018 return false;
1019 if (*this == zero ())
1020 return true;
1021 if (other == zero ())
1022 return (*this == zero ());
1023 gcc_checking_assert (compatible_p (other));
1024 return m_val <= other.m_val;
1025 }
1026
1027 bool operator>= (const profile_count &other) const
1028 {
1029 if (!initialized_p () || !other.initialized_p ())
1030 return false;
1031 if (other == zero ())
1032 return true;
1033 if (*this == zero ())
1034 return (other == zero ());
1035 gcc_checking_assert (compatible_p (other));
1036 return m_val >= other.m_val;
1037 }
1038
1039 bool operator<= (const gcov_type other) const
1040 {
1041 gcc_checking_assert (ipa_p ());
1042 gcc_checking_assert (other >= 0);
1043 return ipa ().initialized_p () && ipa ().m_val <= (uint64_t) other;
1044 }
1045
1046 bool operator>= (const gcov_type other) const
1047 {
1048 gcc_checking_assert (ipa_p ());
1049 gcc_checking_assert (other >= 0);
1050 return ipa ().initialized_p () && ipa ().m_val >= (uint64_t) other;
1051 }
1052
1053 profile_count operator* (int64_t num) const
1054 {
1055 return apply_scale (num, den: 1);
1056 }
1057
1058 profile_count operator*= (int64_t num)
1059 {
1060 *this = apply_scale (num, den: 1);
1061 return *this;
1062 }
1063
1064 profile_count operator/ (int64_t den) const
1065 {
1066 return apply_scale (num: 1, den);
1067 }
1068
1069 profile_count operator/= (int64_t den)
1070 {
1071 *this = apply_scale (num: 1, den);
1072 return *this;
1073 }
1074
1075 /* Return true when value is not zero and can be used for scaling.
1076 This is different from *this > 0 because that requires counter to
1077 be IPA. */
1078 bool nonzero_p () const
1079 {
1080 return initialized_p () && m_val != 0;
1081 }
1082
1083 /* Make counter forcibly nonzero. */
1084 profile_count force_nonzero () const
1085 {
1086 if (!initialized_p ())
1087 return *this;
1088 profile_count ret = *this;
1089 if (ret.m_val == 0)
1090 {
1091 ret.m_val = 1;
1092 ret.m_quality = MIN (m_quality, ADJUSTED);
1093 }
1094 return ret;
1095 }
1096
1097 profile_count max (profile_count other) const
1098 {
1099 profile_count val = *this;
1100
1101 /* Always prefer nonzero IPA counts over local counts. */
1102 if (ipa ().nonzero_p () || other.ipa ().nonzero_p ())
1103 {
1104 val = ipa ();
1105 other = other.ipa ();
1106 }
1107 if (!initialized_p ())
1108 return other;
1109 if (!other.initialized_p ())
1110 return *this;
1111 if (*this == zero ())
1112 return other;
1113 if (other == zero ())
1114 return *this;
1115 gcc_checking_assert (compatible_p (other));
1116 if (val.m_val < other.m_val || (m_val == other.m_val
1117 && val.m_quality < other.m_quality))
1118 return other;
1119 return *this;
1120 }
1121
1122 /* PROB is a probability in scale 0...REG_BR_PROB_BASE. Scale counter
1123 accordingly. */
1124 profile_count apply_probability (int prob) const
1125 {
1126 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
1127 if (m_val == 0)
1128 return *this;
1129 if (!initialized_p ())
1130 return uninitialized ();
1131 profile_count ret;
1132 uint64_t tmp;
1133 safe_scale_64bit (a: m_val, b: prob, REG_BR_PROB_BASE, res: &tmp);
1134 ret.m_val = tmp;
1135 ret.m_quality = MIN (m_quality, ADJUSTED);
1136 return ret;
1137 }
1138
1139 /* Scale counter according to PROB. */
1140 profile_count apply_probability (profile_probability prob) const
1141 {
1142 if (*this == zero () || prob == profile_probability::always ())
1143 return *this;
1144 if (prob == profile_probability::never ())
1145 return zero ();
1146 if (!initialized_p () || !prob.initialized_p ())
1147 return uninitialized ();
1148 profile_count ret;
1149 uint64_t tmp;
1150 safe_scale_64bit (a: m_val, b: prob.m_val, c: profile_probability::max_probability,
1151 res: &tmp);
1152 ret.m_val = tmp;
1153 ret.m_quality = MIN (m_quality, prob.m_quality);
1154 return ret;
1155 }
1156
1157 /* Return *THIS * NUM / DEN. */
1158 profile_count apply_scale (int64_t num, int64_t den) const
1159 {
1160 if (m_val == 0)
1161 return *this;
1162 if (!initialized_p ())
1163 return uninitialized ();
1164 profile_count ret;
1165 uint64_t tmp;
1166
1167 gcc_checking_assert (num >= 0 && den > 0);
1168 safe_scale_64bit (a: m_val, b: num, c: den, res: &tmp);
1169 ret.m_val = MIN (tmp, max_count);
1170 ret.m_quality = MIN (m_quality, ADJUSTED);
1171 return ret;
1172 }
1173
1174 profile_count apply_scale (profile_count num, profile_count den) const
1175 {
1176 if (*this == zero ())
1177 return *this;
1178 if (num == zero ())
1179 return num;
1180 if (!initialized_p () || !num.initialized_p () || !den.initialized_p ())
1181 return uninitialized ();
1182 if (num == den)
1183 return *this;
1184 gcc_checking_assert (den.m_val);
1185
1186 profile_count ret;
1187 uint64_t val;
1188 safe_scale_64bit (a: m_val, b: num.m_val, c: den.m_val, res: &val);
1189 ret.m_val = MIN (val, max_count);
1190 ret.m_quality = MIN (MIN (MIN (m_quality, ADJUSTED),
1191 num.m_quality), den.m_quality);
1192 /* Be sure that ret is not local if num is global.
1193 Also ensure that ret is not global0 when num is global. */
1194 if (num.ipa_p ())
1195 ret.m_quality = MAX (ret.m_quality,
1196 num == num.ipa () ? GUESSED : num.m_quality);
1197 return ret;
1198 }
1199
1200 /* Return THIS with quality dropped to GUESSED_LOCAL. */
1201 profile_count guessed_local () const
1202 {
1203 profile_count ret = *this;
1204 if (!initialized_p ())
1205 return *this;
1206 ret.m_quality = GUESSED_LOCAL;
1207 return ret;
1208 }
1209
1210 /* We know that profile is globally 0 but keep local profile if present. */
1211 profile_count global0 () const
1212 {
1213 profile_count ret = *this;
1214 if (!initialized_p ())
1215 return *this;
1216 ret.m_quality = GUESSED_GLOBAL0;
1217 return ret;
1218 }
1219
1220 /* We know that profile is globally adjusted 0 but keep local profile
1221 if present. */
1222 profile_count global0adjusted () const
1223 {
1224 profile_count ret = *this;
1225 if (!initialized_p ())
1226 return *this;
1227 ret.m_quality = GUESSED_GLOBAL0_ADJUSTED;
1228 return ret;
1229 }
1230
1231 /* Return THIS with quality dropped to GUESSED. */
1232 profile_count guessed () const
1233 {
1234 profile_count ret = *this;
1235 ret.m_quality = MIN (ret.m_quality, GUESSED);
1236 return ret;
1237 }
1238
1239 /* Return variant of profile count which is always safe to compare
1240 across functions. */
1241 profile_count ipa () const
1242 {
1243 if (m_quality > GUESSED_GLOBAL0_ADJUSTED)
1244 return *this;
1245 if (m_quality == GUESSED_GLOBAL0)
1246 return zero ();
1247 if (m_quality == GUESSED_GLOBAL0_ADJUSTED)
1248 return adjusted_zero ();
1249 return uninitialized ();
1250 }
1251
1252 /* Return THIS with quality dropped to AFDO. */
1253 profile_count afdo () const
1254 {
1255 profile_count ret = *this;
1256 ret.m_quality = AFDO;
1257 return ret;
1258 }
1259
1260 /* Return probability of event with counter THIS within event with counter
1261 OVERALL. */
1262 profile_probability probability_in (const profile_count overall) const
1263 {
1264 if (*this == zero ()
1265 && !(overall == zero ()))
1266 return profile_probability::never ();
1267 if (!initialized_p () || !overall.initialized_p ()
1268 || !overall.m_val)
1269 return profile_probability::uninitialized ();
1270 if (*this == overall && m_quality == PRECISE)
1271 return profile_probability::always ();
1272 profile_probability ret;
1273 gcc_checking_assert (compatible_p (overall));
1274
1275 if (overall.m_val < m_val)
1276 {
1277 ret.m_val = profile_probability::max_probability;
1278 ret.m_quality = GUESSED;
1279 return ret;
1280 }
1281 else
1282 ret.m_val = RDIV (m_val * profile_probability::max_probability,
1283 overall.m_val);
1284 ret.m_quality = MIN (MAX (MIN (m_quality, overall.m_quality),
1285 GUESSED), ADJUSTED);
1286 return ret;
1287 }
1288
1289 /* Return true if profile count is very large, so we risk overflows
1290 with loop transformations. */
1291 bool
1292 very_large_p ()
1293 {
1294 if (!initialized_p ())
1295 return false;
1296 return m_val > max_count / 65536;
1297 }
1298
1299 int to_frequency (struct function *fun) const;
1300 int to_cgraph_frequency (profile_count entry_bb_count) const;
1301 sreal to_sreal_scale (profile_count in, bool *known = NULL) const;
1302
1303 /* Output THIS to F. */
1304 void dump (FILE *f, struct function *fun = NULL) const;
1305
1306 /* Print THIS to stderr. */
1307 void debug () const;
1308
1309 /* Return true if THIS is known to differ significantly from OTHER. */
1310 bool differs_from_p (profile_count other) const;
1311
1312 /* We want to scale profile across function boundary from NUM to DEN.
1313 Take care of the side case when NUM and DEN are zeros of incompatible
1314 kinds. */
1315 static void adjust_for_ipa_scaling (profile_count *num, profile_count *den);
1316
1317 /* THIS is a count of bb which is known to be executed IPA times.
1318 Combine this information into bb counter. This means returning IPA
1319 if it is nonzero, not changing anything if IPA is uninitialized
1320 and if IPA is zero, turning THIS into corresponding local profile with
1321 global0. */
1322 profile_count combine_with_ipa_count (profile_count ipa);
1323
1324 /* Same as combine_with_ipa_count but inside function with count IPA2. */
1325 profile_count combine_with_ipa_count_within
1326 (profile_count ipa, profile_count ipa2);
1327
1328 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
1329 Conversions back and forth are used to read the coverage and get it
1330 into internal representation. */
1331 static profile_count from_gcov_type (gcov_type v,
1332 profile_quality quality = PRECISE);
1333
1334 /* LTO streaming support. */
1335 static profile_count stream_in (class lto_input_block *);
1336 void stream_out (struct output_block *);
1337 void stream_out (struct lto_output_stream *);
1338};
1339#endif
1340

source code of gcc/profile-count.h