1 /* Profile counter container type.
2 Copyright (C) 2017 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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
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
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/>. */
21 #ifndef GCC_PROFILE_COUNT_H
22 #define GCC_PROFILE_COUNT_H
24 /* Quality of the profile count. Because gengtype does not support enums
25 inside of classes, this is in global namespace. */
26 enum profile_quality
{
27 /* Profile is based on static branch prediction heuristics. It may or may
28 not reflect the reality. */
30 /* Profile was determined by autofdo. */
32 /* Profile was originally based on feedback but it was adjusted
33 by code duplicating optimization. It may not precisely reflect the
34 particular code path. */
36 /* Profile was read from profile feedback or determined by accurate static
41 /* The base value for branch probability notes and edge probabilities. */
42 #define REG_BR_PROB_BASE 10000
44 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
46 /* Data type to hold probabilities. It implements fixed point arithmetics
47 with capping so probability is always in range [0,1] and scaling requiring
48 values greater than 1 needs to be represented otherwise.
50 In addition to actual value the quality of profile is tracked and propagated
51 through all operations. Special value UNINITIALIZED is used for probabilities
52 that has not been determined yet (for example bacause of
53 -fno-guess-branch-probability)
55 Typically probabilities are derived from profile feedback (via
56 probability_in_gcov_type), autoFDO or guessed statically and then propagated
57 thorough the compilation.
59 Named probabilities are available:
60 - never (0 probability)
62 - very_unlikely (1/2000 probability)
63 - unlikely (1/5 probablity)
64 - even (1/2 probability)
65 - likely (4/5 probability)
66 - very_likely (1999/2000 probability)
70 Named probabilities except for never/always are assumed to be statically
71 guessed and thus not necessarily accurate. The difference between never
72 and guessed_never is that the first one should be used only in case that
73 well behaving program will very likely not execute the "never" path.
74 For example if the path is going to abort () call or it exception handling.
76 Always and guessed_always probabilities are symmetric.
78 For legacy code we support conversion to/from REG_BR_PROB_BASE based fixpoint
79 integer arithmetics. Once the code is converted to branch probabilities,
80 these conversions will probably go away because they are lossy.
83 class GTY((user
)) profile_probability
85 /* For now use values in range 0...REG_BR_PROB_BASE. Later we can use full
86 precision of 30 bits available. */
88 static const int n_bits
= 30;
89 static const uint32_t max_probability
= REG_BR_PROB_BASE
;
90 static const uint32_t uninitialized_probability
= ((uint32_t) 1 << n_bits
) - 1;
93 enum profile_quality m_quality
: 2;
95 friend class profile_count
;
98 /* Named probabilities. */
99 static profile_probability
never ()
101 profile_probability ret
;
103 ret
.m_quality
= profile_precise
;
106 static profile_probability
guessed_never ()
108 profile_probability ret
;
110 ret
.m_quality
= profile_guessed
;
113 static profile_probability
very_unlikely ()
115 /* Be consistent with PROB_VERY_UNLIKELY in predict.h. */
116 profile_probability r
117 = profile_probability::always ().apply_scale (1, 2000);
121 static profile_probability
unlikely ()
123 /* Be consistent with PROB_VERY_LIKELY in predict.h. */
124 profile_probability r
125 = profile_probability::always ().apply_scale (1, 5);
129 static profile_probability
even ()
131 return profile_probability::always ().apply_scale (1, 2);
133 static profile_probability
very_likely ()
135 return profile_probability::always () - very_unlikely ();
137 static profile_probability
likely ()
139 return profile_probability::always () - unlikely ();
141 static profile_probability
guessed_always ()
143 profile_probability ret
;
144 ret
.m_val
= max_probability
;
145 ret
.m_quality
= profile_guessed
;
148 static profile_probability
always ()
150 profile_probability ret
;
151 ret
.m_val
= max_probability
;
152 ret
.m_quality
= profile_precise
;
155 /* Probabilities which has not been initialized. Either because
156 initialization did not happen yet or because profile is unknown. */
157 static profile_probability
uninitialized ()
159 profile_probability c
;
160 c
.m_val
= uninitialized_probability
;
161 c
.m_quality
= profile_guessed
;
166 /* Return true if value has been initialized. */
167 bool initialized_p () const
169 return m_val
!= uninitialized_probability
;
171 /* Return true if value can be trusted. */
172 bool reliable_p () const
174 return initialized_p ();
177 /* Conversion from and to REG_BR_PROB_BASE integer fixpoint arithmetics.
178 this is mostly to support legacy code and should go away. */
179 static profile_probability
from_reg_br_prob_base (int v
)
181 profile_probability ret
;
182 gcc_checking_assert (v
>= 0 && v
<= REG_BR_PROB_BASE
);
183 ret
.m_val
= RDIV (v
* max_probability
, REG_BR_PROB_BASE
);
184 ret
.m_quality
= profile_guessed
;
187 int to_reg_br_prob_base () const
189 gcc_checking_assert (initialized_p ());
190 return RDIV (m_val
* REG_BR_PROB_BASE
, max_probability
);
193 /* Conversion to and from RTL representation of profile probabilities. */
194 static profile_probability
from_reg_br_prob_note (int v
)
196 profile_probability ret
;
197 ret
.m_val
= ((unsigned int)v
) / 4;
198 ret
.m_quality
= (enum profile_quality
)(v
& 3);
201 int to_reg_br_prob_note () const
203 gcc_checking_assert (initialized_p ());
204 int ret
= m_val
* 4 + m_quality
;
205 gcc_checking_assert (profile_probability::from_reg_br_prob_note (ret
)
210 /* Return VAL1/VAL2. */
211 static profile_probability probability_in_gcov_type
212 (gcov_type val1
, gcov_type val2
)
214 profile_probability ret
;
215 gcc_checking_assert (val1
>= 0 && val2
> 0);
217 ret
.m_val
= max_probability
;
219 ret
.m_val
= RDIV (val1
* max_probability
, val2
);
220 ret
.m_quality
= profile_precise
;
224 /* Basic operations. */
225 bool operator== (const profile_probability
&other
) const
227 return m_val
== other
.m_val
&& m_quality
== other
.m_quality
;
229 profile_probability
operator+ (const profile_probability
&other
) const
231 if (other
== profile_probability::never ())
233 if (*this == profile_probability::never ())
235 if (!initialized_p () || !other
.initialized_p ())
236 return profile_probability::uninitialized ();
238 profile_probability ret
;
239 ret
.m_val
= MIN ((uint32_t)(m_val
+ other
.m_val
), max_probability
);
240 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
243 profile_probability
&operator+= (const profile_probability
&other
)
245 if (other
== profile_probability::never ())
247 if (*this == profile_probability::never ())
252 if (!initialized_p () || !other
.initialized_p ())
253 return *this = profile_probability::uninitialized ();
256 m_val
= MIN ((uint32_t)(m_val
+ other
.m_val
), max_probability
);
257 m_quality
= MIN (m_quality
, other
.m_quality
);
261 profile_probability
operator- (const profile_probability
&other
) const
263 if (*this == profile_probability::never ()
264 || other
== profile_probability::never ())
266 if (!initialized_p () || !other
.initialized_p ())
267 return profile_probability::uninitialized ();
268 profile_probability ret
;
269 ret
.m_val
= m_val
>= other
.m_val
? m_val
- other
.m_val
: 0;
270 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
273 profile_probability
&operator-= (const profile_probability
&other
)
275 if (*this == profile_probability::never ()
276 || other
== profile_probability::never ())
278 if (!initialized_p () || !other
.initialized_p ())
279 return *this = profile_probability::uninitialized ();
282 m_val
= m_val
>= other
.m_val
? m_val
- other
.m_val
: 0;
283 m_quality
= MIN (m_quality
, other
.m_quality
);
287 profile_probability
operator* (const profile_probability
&other
) const
289 if (*this == profile_probability::never ()
290 || other
== profile_probability::never ())
291 return profile_probability::never ();
292 if (!initialized_p () || !other
.initialized_p ())
293 return profile_probability::uninitialized ();
294 profile_probability ret
;
295 ret
.m_val
= RDIV ((uint64_t)m_val
* other
.m_val
, max_probability
);
296 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
299 profile_probability
&operator*= (const profile_probability
&other
)
301 if (*this == profile_probability::never ()
302 || other
== profile_probability::never ())
303 return *this = profile_probability::never ();
304 if (!initialized_p () || !other
.initialized_p ())
305 return *this = profile_probability::uninitialized ();
308 m_val
= RDIV ((uint64_t)m_val
* other
.m_val
, max_probability
);
309 m_quality
= MIN (m_quality
, other
.m_quality
);
313 profile_probability
operator/ (const profile_probability
&other
) const
315 if (*this == profile_probability::never ())
316 return profile_probability::never ();
317 if (!initialized_p () || !other
.initialized_p ())
318 return profile_probability::uninitialized ();
319 profile_probability ret
;
320 if (m_val
>= other
.m_val
)
321 ret
.m_val
= max_probability
;
326 gcc_checking_assert (other
.m_val
);
327 ret
.m_val
= MIN (RDIV ((uint64_t)m_val
* max_probability
,
331 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
334 profile_probability
&operator/= (const profile_probability
&other
)
336 if (*this == profile_probability::never ())
337 return *this = profile_probability::never ();
338 if (!initialized_p () || !other
.initialized_p ())
339 return *this = profile_probability::uninitialized ();
342 if (m_val
> other
.m_val
)
343 m_val
= max_probability
;
348 gcc_checking_assert (other
.m_val
);
349 m_val
= MIN (RDIV ((uint64_t)m_val
* max_probability
,
353 m_quality
= MIN (m_quality
, other
.m_quality
);
358 gcov_type
apply (gcov_type val
) const
360 if (*this == profile_probability::uninitialized ())
362 return RDIV (val
* m_val
, max_probability
);
365 /* Return 1-*THIS. */
366 profile_probability
invert () const
368 return profile_probability::always() - *this;
371 /* Return THIS with quality dropped to GUESSED. */
372 profile_probability
guessed () const
374 profile_probability ret
= *this;
375 ret
.m_quality
= profile_guessed
;
379 /* Return THIS with quality dropped to AFDO. */
380 profile_probability
afdo () const
382 profile_probability ret
= *this;
383 ret
.m_quality
= profile_afdo
;
387 profile_probability
combine_with_freq (int freq1
, profile_probability other
,
390 profile_probability ret
;
392 if (*this == profile_probability::uninitialized ()
393 || other
== profile_probability::uninitialized ())
394 return profile_probability::uninitialized ();
396 gcc_checking_assert (freq1
>= 0 && freq2
>= 0);
397 if (!freq1
&& !freq2
)
399 ret
.m_val
= (m_val
+ other
.m_val
) / 2;
402 ret
.m_val
= RDIV (m_val
* (uint64_t) freq1
403 + other
.m_val
* (uint64_t) freq2
, freq1
+ freq2
);
404 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
408 /* Return *THIS * NUM / DEN. */
409 profile_probability
apply_scale (int64_t num
, int64_t den
) const
411 if (*this == profile_probability::never ())
413 if (!initialized_p ())
414 return profile_probability::uninitialized ();
415 profile_probability ret
;
416 ret
.m_val
= MIN (RDIV (m_val
* num
, den
),
418 ret
.m_quality
= MIN (m_quality
, profile_adjusted
);
422 /* Return true when the probability of edge is reliable.
424 The profile guessing code is good at predicting branch outcome (ie.
425 taken/not taken), that is predicted right slightly over 75% of time.
426 It is however notoriously poor on predicting the probability itself.
427 In general the profile appear a lot flatter (with probabilities closer
428 to 50%) than the reality so it is bad idea to use it to drive optimization
429 such as those disabling dynamic branch prediction for well predictable
432 There are two exceptions - edges leading to noreturn edges and edges
433 predicted by number of iterations heuristics are predicted well. This macro
434 should be able to distinguish those, but at the moment it simply check for
435 noreturn heuristic that is only one giving probability over 99% or bellow
436 1%. In future we might want to propagate reliability information across the
437 CFG if we find this information useful on multiple places. */
439 bool probably_reliable_p () const
441 if (m_quality
>= profile_adjusted
)
443 if (!initialized_p ())
445 return m_val
< max_probability
/ 100
446 || m_val
> max_probability
- max_probability
/ 100;
449 /* Return false if profile_probability is bogus. */
452 if (m_val
== uninitialized_probability
)
453 return m_quality
== profile_guessed
;
455 return m_val
<= REG_BR_PROB_BASE
;
458 /* Comparsions are three-state and conservative. False is returned if
459 the inequality can not be decided. */
460 bool operator< (const profile_probability
&other
) const
462 return initialized_p () && other
.initialized_p () && m_val
< other
.m_val
;
464 bool operator> (const profile_probability
&other
) const
466 return initialized_p () && other
.initialized_p () && m_val
> other
.m_val
;
469 bool operator<= (const profile_probability
&other
) const
471 return initialized_p () && other
.initialized_p () && m_val
<= other
.m_val
;
473 bool operator>= (const profile_probability
&other
) const
475 return initialized_p () && other
.initialized_p () && m_val
>= other
.m_val
;
478 /* Output THIS to F. */
479 void dump (FILE *f
) const;
481 /* Print THIS to stderr. */
484 /* Return true if THIS is known to differ significantly from OTHER. */
485 bool differs_from_p (profile_probability other
) const;
486 /* Return if difference is greater than 50%. */
487 bool differs_lot_from_p (profile_probability other
) const;
489 /* LTO streaming support. */
490 static profile_probability
stream_in (struct lto_input_block
*);
491 void stream_out (struct output_block
*);
492 void stream_out (struct lto_output_stream
*);
495 /* Main data type to hold profile counters in GCC. In most cases profile
496 counts originate from profile feedback. They are 64bit integers
497 representing number of executions during the train run.
498 As the profile is maintained during the compilation, many adjustments are
499 made. Not all transformations can be made precisely, most importantly
500 when code is being duplicated. It also may happen that part of CFG has
501 profile counts known while other do not - for example when LTO optimizing
502 partly profiled program or when profile was lost due to COMDAT merging.
504 For this reason profile_count tracks more information than
505 just unsigned integer and it is also ready for profile mismatches.
506 The API of this data type represent operations that are natural
507 on profile counts - sum, difference and operation with scales and
508 probabilities. All operations are safe by never getting negative counts
509 and they do end up in uninitialized scale if any of the parameters is
512 All comparsions that are three state and handling of probabilities. Thus
513 a < b is not equal to !(a >= b).
515 The following pre-defined counts are available:
517 profile_count::zero () for code that is known to execute zero times at
518 runtime (this can be detected statically i.e. for paths leading to
520 profile_count::one () for code that is known to execute once (such as
522 profile_count::uninitialized () for unknown execution count.
526 class GTY(()) profile_count
528 /* Use 62bit to hold basic block counters. Should be at least
529 64bit. Although a counter cannot be negative, we use a signed
530 type to hold various extra stages. */
532 static const int n_bits
= 62;
533 static const uint64_t max_count
= ((uint64_t) 1 << n_bits
) - 2;
534 static const uint64_t uninitialized_count
= ((uint64_t) 1 << n_bits
) - 1;
536 uint64_t m_val
: n_bits
;
537 enum profile_quality m_quality
: 2;
539 /* Assume numbers smaller than this to multiply. This is set to make
540 testsuite pass, in future we may implement precise multiplication in higer
542 static const uint64_t max_safe_multiplier
= 131072;
545 /* Used for counters which are expected to be never executed. */
546 static profile_count
zero ()
548 return from_gcov_type (0);
550 static profile_count
guessed_zero ()
554 c
.m_quality
= profile_guessed
;
557 static profile_count
one ()
559 return from_gcov_type (1);
561 /* Value of counters which has not been initialized. Either because
562 initialization did not happen yet or because profile is unknown. */
563 static profile_count
uninitialized ()
566 c
.m_val
= uninitialized_count
;
567 c
.m_quality
= profile_guessed
;
571 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
572 Conversions back and forth are used to read the coverage and get it
573 into internal representation. */
574 static profile_count
from_gcov_type (gcov_type v
)
577 gcc_checking_assert (v
>= 0 && (uint64_t) v
<= max_count
);
579 ret
.m_quality
= profile_precise
;
583 /* Conversion to gcov_type is lossy. */
584 gcov_type
to_gcov_type () const
586 gcc_checking_assert (initialized_p ());
590 /* Return true if value has been initialized. */
591 bool initialized_p () const
593 return m_val
!= uninitialized_count
;
595 /* Return true if value can be trusted. */
596 bool reliable_p () const
598 return initialized_p ();
601 /* When merging basic blocks, the two different profile counts are unified.
602 Return true if this can be done without losing info about profile.
603 The only case we care about here is when first BB contains something
604 that makes it terminate in a way not visible in CFG. */
605 bool ok_for_merging (profile_count other
) const
607 if (m_quality
< profile_adjusted
608 || other
.m_quality
< profile_adjusted
)
610 return !(other
< *this);
613 /* When merging two BBs with different counts, pick common count that looks
614 most representative. */
615 profile_count
merge (profile_count other
) const
617 if (*this == other
|| !other
.initialized_p ()
618 || m_quality
> other
.m_quality
)
620 if (other
.m_quality
> m_quality
626 /* Basic operations. */
627 bool operator== (const profile_count
&other
) const
629 return m_val
== other
.m_val
&& m_quality
== other
.m_quality
;
631 profile_count
operator+ (const profile_count
&other
) const
633 if (other
== profile_count::zero ())
635 if (*this == profile_count::zero ())
637 if (!initialized_p () || !other
.initialized_p ())
638 return profile_count::uninitialized ();
641 ret
.m_val
= m_val
+ other
.m_val
;
642 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
645 profile_count
&operator+= (const profile_count
&other
)
647 if (other
== profile_count::zero ())
649 if (*this == profile_count::zero ())
654 if (!initialized_p () || !other
.initialized_p ())
655 return *this = profile_count::uninitialized ();
658 m_val
+= other
.m_val
;
659 m_quality
= MIN (m_quality
, other
.m_quality
);
663 profile_count
operator- (const profile_count
&other
) const
665 if (*this == profile_count::zero () || other
== profile_count::zero ())
667 if (!initialized_p () || !other
.initialized_p ())
668 return profile_count::uninitialized ();
670 ret
.m_val
= m_val
>= other
.m_val
? m_val
- other
.m_val
: 0;
671 ret
.m_quality
= MIN (m_quality
, other
.m_quality
);
674 profile_count
&operator-= (const profile_count
&other
)
676 if (*this == profile_count::zero () || other
== profile_count::zero ())
678 if (!initialized_p () || !other
.initialized_p ())
679 return *this = profile_count::uninitialized ();
682 m_val
= m_val
>= other
.m_val
? m_val
- other
.m_val
: 0;
683 m_quality
= MIN (m_quality
, other
.m_quality
);
688 /* Return false if profile_count is bogus. */
691 return m_val
!= uninitialized_count
|| m_quality
== profile_guessed
;
694 /* Comparsions are three-state and conservative. False is returned if
695 the inequality can not be decided. */
696 bool operator< (const profile_count
&other
) const
698 return initialized_p () && other
.initialized_p () && m_val
< other
.m_val
;
700 bool operator> (const profile_count
&other
) const
702 return initialized_p () && other
.initialized_p () && m_val
> other
.m_val
;
704 bool operator< (const gcov_type other
) const
706 gcc_checking_assert (other
>= 0);
707 return initialized_p () && m_val
< (uint64_t) other
;
709 bool operator> (const gcov_type other
) const
711 gcc_checking_assert (other
>= 0);
712 return initialized_p () && m_val
> (uint64_t) other
;
715 bool operator<= (const profile_count
&other
) const
717 return initialized_p () && other
.initialized_p () && m_val
<= other
.m_val
;
719 bool operator>= (const profile_count
&other
) const
721 return initialized_p () && other
.initialized_p () && m_val
>= other
.m_val
;
723 bool operator<= (const gcov_type other
) const
725 gcc_checking_assert (other
>= 0);
726 return initialized_p () && m_val
<= (uint64_t) other
;
728 bool operator>= (const gcov_type other
) const
730 gcc_checking_assert (other
>= 0);
731 return initialized_p () && m_val
>= (uint64_t) other
;
734 /* PROB is a probability in scale 0...REG_BR_PROB_BASE. Scale counter
736 profile_count
apply_probability (int prob
) const
738 gcc_checking_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
741 if (!initialized_p ())
742 return profile_count::uninitialized ();
744 ret
.m_val
= RDIV (m_val
* prob
, REG_BR_PROB_BASE
);
745 ret
.m_quality
= MIN (m_quality
, profile_adjusted
);
749 /* Scale counter according to PROB. */
750 profile_count
apply_probability (profile_probability prob
) const
752 if (*this == profile_count::zero ())
754 if (prob
== profile_probability::never ())
755 return profile_count::zero ();
756 if (!initialized_p ())
757 return profile_count::uninitialized ();
759 ret
.m_val
= RDIV (m_val
* prob
.m_val
,
760 profile_probability::max_probability
);
761 ret
.m_quality
= MIN (m_quality
, prob
.m_quality
);
764 /* Return *THIS * NUM / DEN. */
765 profile_count
apply_scale (int64_t num
, int64_t den
) const
769 if (!initialized_p ())
770 return profile_count::uninitialized ();
772 gcc_checking_assert (num
>= 0 && den
> 0);
773 /* FIXME: shrink wrapping violates this sanity check. */
774 gcc_checking_assert ((num
<= REG_BR_PROB_BASE
775 || den
<= REG_BR_PROB_BASE
) || 1);
776 ret
.m_val
= RDIV (m_val
* num
, den
);
777 ret
.m_quality
= MIN (m_quality
, profile_adjusted
);
780 profile_count
apply_scale (profile_count num
, profile_count den
) const
786 if (!initialized_p () || !num
.initialized_p () || !den
.initialized_p ())
787 return profile_count::uninitialized ();
788 gcc_checking_assert (den
> 0);
793 /* Take care for overflows! */
794 if (num
.m_val
< max_safe_multiplier
|| m_val
< max_safe_multiplier
)
795 ret
.m_val
= RDIV (m_val
* num
.m_val
, den
.m_val
);
797 ret
.m_val
= RDIV (m_val
* RDIV (num
.m_val
* max_safe_multiplier
,
798 den
.m_val
), max_safe_multiplier
);
799 ret
.m_quality
= MIN (m_quality
, profile_adjusted
);
803 /* Return THIS with quality dropped to GUESSED. */
804 profile_count
guessed () const
806 profile_count ret
= *this;
807 ret
.m_quality
= profile_guessed
;
811 /* Return THIS with quality dropped to AFDO. */
812 profile_count
afdo () const
814 profile_count ret
= *this;
815 ret
.m_quality
= profile_afdo
;
819 /* Return probability of event with counter THIS within event with counter
821 profile_probability
probability_in (const profile_count overall
) const
824 return profile_probability::never ();
825 if (!initialized_p () || !overall
.initialized_p ()
827 return profile_probability::uninitialized ();
828 profile_probability ret
;
830 ret
.m_val
= profile_probability::max_probability
;
832 ret
.m_val
= RDIV (m_val
* profile_probability::max_probability
,
834 ret
.m_quality
= MIN (m_quality
, overall
.m_quality
);
838 /* Output THIS to F. */
839 void dump (FILE *f
) const;
841 /* Print THIS to stderr. */
844 /* Return true if THIS is known to differ significantly from OTHER. */
845 bool differs_from_p (profile_count other
) const;
847 /* LTO streaming support. */
848 static profile_count
stream_in (struct lto_input_block
*);
849 void stream_out (struct output_block
*);
850 void stream_out (struct lto_output_stream
*);