Line data Source code
1 : /* Profile counter container type.
2 : Copyright (C) 2017-2026 Free Software Foundation, Inc.
3 : Contributed by Jan Hubicka
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "profile-count.h"
25 : #include "options.h"
26 : #include "tree.h"
27 : #include "basic-block.h"
28 : #include "function.h"
29 : #include "cfg.h"
30 : #include "gimple.h"
31 : #include "data-streamer.h"
32 : #include "cgraph.h"
33 : #include "wide-int.h"
34 : #include "sreal.h"
35 : #include "profile.h"
36 :
37 : /* Names from profile_quality enum values. */
38 :
39 : const char *profile_quality_names[] =
40 : {
41 : "uninitialized",
42 : "guessed_local",
43 : "guessed_global0afdo",
44 : "guessed_global0adjusted",
45 : "guessed_global0",
46 : "guessed",
47 : "afdo",
48 : "adjusted",
49 : "precise"
50 : };
51 :
52 : /* Get a string describing QUALITY. */
53 :
54 : const char *
55 42720 : profile_quality_as_string (enum profile_quality quality)
56 : {
57 42720 : return profile_quality_names[quality];
58 : }
59 :
60 : /* Parse VALUE as profile quality and return true when a valid QUALITY. */
61 :
62 : bool
63 1092 : parse_profile_quality (const char *value, profile_quality *quality)
64 : {
65 6327 : for (unsigned i = 0; i < ARRAY_SIZE (profile_quality_names); i++)
66 6075 : if (strcmp (profile_quality_names[i], value) == 0)
67 : {
68 840 : *quality = (profile_quality)i;
69 840 : return true;
70 : }
71 :
72 : return false;
73 : }
74 :
75 : /* Display names from profile_quality enum values. */
76 :
77 : const char *profile_quality_display_names[] =
78 : {
79 : NULL,
80 : "estimated locally",
81 : "estimated locally, globally 0 auto FDO",
82 : "estimated locally, globally 0 adjusted",
83 : "estimated locally, globally 0",
84 : "guessed",
85 : "auto FDO",
86 : "adjusted",
87 : "precise"
88 : };
89 :
90 : /* Dump THIS to F. */
91 :
92 : void
93 79001 : profile_count::dump (FILE *f, struct function *fun) const
94 : {
95 79001 : if (!initialized_p ())
96 17 : fprintf (f, "uninitialized");
97 130469 : else if (fun && initialized_p ()
98 51485 : && fun->cfg
99 130469 : && ENTRY_BLOCK_PTR_FOR_FN (fun)->count.initialized_p ())
100 : {
101 51485 : if (compatible_p (ENTRY_BLOCK_PTR_FOR_FN (fun)->count))
102 51485 : fprintf (f, "%" PRId64 " (%s, freq %.4f)", m_val,
103 51485 : profile_quality_display_names[m_quality],
104 : to_sreal_scale
105 102970 : (ENTRY_BLOCK_PTR_FOR_FN (fun)->count).to_double ());
106 : else
107 0 : fprintf (f, "%" PRId64 " (%s, incompatible with entry block count)",
108 0 : m_val, profile_quality_display_names[m_quality]);
109 : }
110 : else
111 27499 : fprintf (f, "%" PRId64 " (%s)", m_val,
112 27499 : profile_quality_display_names[m_quality]);
113 79001 : }
114 :
115 : /* Dump THIS to stderr. */
116 :
117 : void
118 0 : profile_count::debug () const
119 : {
120 0 : dump (stderr, cfun);
121 0 : fprintf (stderr, "\n");
122 0 : }
123 :
124 : /* Return true if THIS differs from OTHER; tolerate small differences. */
125 :
126 : bool
127 53226967 : profile_count::differs_from_p (profile_count other) const
128 : {
129 53226967 : gcc_checking_assert (compatible_p (other));
130 53226967 : if (!initialized_p () || !other.initialized_p ())
131 47 : return initialized_p () != other.initialized_p ();
132 53226920 : if ((uint64_t)m_val - (uint64_t)other.m_val < 100
133 985174 : || (uint64_t)other.m_val - (uint64_t)m_val < 100)
134 : return false;
135 323989 : if (!other.m_val)
136 : return true;
137 323082 : uint64_t ratio;
138 323082 : safe_scale_64bit (m_val, 100, other.m_val, &ratio);
139 323082 : return ratio < 99 || ratio > 101;
140 : }
141 :
142 : /* Stream THIS from IB. */
143 :
144 : profile_count
145 1543617 : profile_count::stream_in (class lto_input_block *ib)
146 : {
147 1543617 : profile_count ret;
148 1543617 : ret.m_val = streamer_read_gcov_count (ib);
149 1543617 : ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
150 1543617 : return ret;
151 : }
152 :
153 : /* Stream THIS to OB. */
154 :
155 : void
156 912188 : profile_count::stream_out (struct output_block *ob)
157 : {
158 912188 : streamer_write_gcov_count (ob, m_val);
159 912188 : streamer_write_uhwi (ob, m_quality);
160 912188 : }
161 :
162 : /* Stream THIS to OB. */
163 :
164 : void
165 1052012 : profile_count::stream_out (struct lto_output_stream *ob)
166 : {
167 1052012 : streamer_write_gcov_count_stream (ob, m_val);
168 1052012 : streamer_write_uhwi_stream (ob, m_quality);
169 1052012 : }
170 :
171 :
172 : /* Output THIS to BUFFER. */
173 :
174 : void
175 60475 : profile_probability::dump (char *buffer) const
176 : {
177 60475 : if (!initialized_p ())
178 0 : sprintf (buffer, "uninitialized");
179 : else
180 : {
181 : /* Make difference between 0.00 as a roundoff error and actual 0.
182 : Similarly for 1. */
183 60475 : if (m_val == 0)
184 3102 : buffer += sprintf (buffer, "never");
185 57373 : else if (m_val == max_probability)
186 19945 : buffer += sprintf (buffer, "always");
187 : else
188 37428 : buffer += sprintf (buffer, "%3.1f%%", (double)m_val * 100 / max_probability);
189 :
190 60475 : if (quality () == ADJUSTED)
191 5804 : sprintf (buffer, " (adjusted)");
192 54671 : else if (quality () == AFDO)
193 0 : sprintf (buffer, " (auto FDO)");
194 54671 : else if (quality () == GUESSED)
195 33097 : sprintf (buffer, " (guessed)");
196 : }
197 60475 : }
198 :
199 : /* Dump THIS to F. */
200 :
201 : void
202 60461 : profile_probability::dump (FILE *f) const
203 : {
204 60461 : char buffer[64];
205 60461 : dump (buffer);
206 60461 : fputs (buffer, f);
207 60461 : }
208 :
209 : /* Dump THIS to stderr. */
210 :
211 : void
212 0 : profile_probability::debug () const
213 : {
214 0 : dump (stderr);
215 0 : fprintf (stderr, "\n");
216 0 : }
217 :
218 : /* Return true if THIS differs from OTHER; tolerate small differences. */
219 :
220 : bool
221 10825 : profile_probability::differs_from_p (profile_probability other) const
222 : {
223 10825 : if (!initialized_p () || !other.initialized_p ())
224 : return false;
225 10825 : if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
226 9 : || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
227 : return false;
228 0 : if (!other.m_val)
229 : return true;
230 0 : int64_t ratio = (int64_t)m_val * 100 / other.m_val;
231 0 : return ratio < 99 || ratio > 101;
232 : }
233 :
234 : /* Return true if THIS differs significantly from OTHER. */
235 :
236 : bool
237 233286 : profile_probability::differs_lot_from_p (profile_probability other) const
238 : {
239 233286 : if (!initialized_p () || !other.initialized_p ())
240 : return false;
241 233165 : uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
242 233165 : return d > max_probability / 2;
243 : }
244 :
245 : /* Stream THIS from IB. */
246 :
247 : profile_probability
248 860249 : profile_probability::stream_in (class lto_input_block *ib)
249 : {
250 860249 : profile_probability ret;
251 860249 : ret.m_val = streamer_read_uhwi (ib);
252 860249 : ret.m_adjusted_quality = streamer_read_uhwi (ib);
253 860249 : return ret;
254 : }
255 :
256 : /* Stream THIS to OB. */
257 :
258 : void
259 1038054 : profile_probability::stream_out (struct output_block *ob)
260 : {
261 1038054 : streamer_write_uhwi (ob, m_val);
262 1038054 : streamer_write_uhwi (ob, m_adjusted_quality);
263 1038054 : }
264 :
265 : /* Stream THIS to OB. */
266 :
267 : void
268 0 : profile_probability::stream_out (struct lto_output_stream *ob)
269 : {
270 0 : streamer_write_uhwi_stream (ob, m_val);
271 0 : streamer_write_uhwi_stream (ob, m_adjusted_quality);
272 0 : }
273 :
274 : /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
275 :
276 : bool
277 2253956 : slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
278 : {
279 2253956 : FIXED_WIDE_INT (128) tmp = a;
280 2253956 : wi::overflow_type overflow;
281 2253956 : tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
282 2253956 : gcc_checking_assert (!overflow);
283 2253956 : if (wi::fits_uhwi_p (tmp))
284 : {
285 2253257 : *res = tmp.to_uhwi ();
286 2253257 : return true;
287 : }
288 699 : *res = (uint64_t) -1;
289 699 : return false;
290 : }
291 :
292 : /* Return count as frequency within FUN scaled in range 0 to REG_FREQ_MAX
293 : Used for legacy code and should not be used anymore. */
294 :
295 : int
296 1093821652 : profile_count::to_frequency (struct function *fun) const
297 : {
298 1093821652 : if (!initialized_p ())
299 : return BB_FREQ_MAX;
300 1092010558 : if (*this == zero ())
301 15450211 : return 0;
302 1076560347 : STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
303 1076560347 : gcc_assert (fun->cfg->count_max.initialized_p ());
304 1076560347 : profile_probability prob = probability_in (fun->cfg->count_max);
305 1076560347 : if (!prob.initialized_p ())
306 : return REG_BR_PROB_BASE;
307 1076559959 : return prob.to_reg_br_prob_base ();
308 : }
309 :
310 : /* Return count as frequency within FUN scaled in range 0 to CGRAPH_FREQ_MAX
311 : where CGRAPH_FREQ_BASE means that count equals to entry block count.
312 : Used for legacy code and should not be used anymore. */
313 :
314 : int
315 187456 : profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
316 : {
317 187456 : if (!initialized_p () || !entry_bb_count.initialized_p ())
318 : return CGRAPH_FREQ_BASE;
319 187199 : if (*this == zero ())
320 220 : return 0;
321 186979 : gcc_checking_assert (entry_bb_count.initialized_p ());
322 186979 : uint64_t scale;
323 186979 : gcc_checking_assert (compatible_p (entry_bb_count));
324 373958 : if (!safe_scale_64bit (!entry_bb_count.m_val ? m_val + 1 : m_val,
325 186979 : CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), &scale))
326 : return CGRAPH_FREQ_MAX;
327 186979 : return MIN (scale, CGRAPH_FREQ_MAX);
328 : }
329 :
330 : /* Return THIS/IN as sreal value. */
331 :
332 : sreal
333 311306952 : profile_count::to_sreal_scale (profile_count in, bool *known) const
334 : {
335 334630976 : if (*this == zero ()
336 23324024 : && !(in == zero ()))
337 : {
338 23173425 : if (known)
339 5 : *known = true;
340 23173425 : return 0;
341 : }
342 288133527 : if (!initialized_p () || !in.initialized_p ())
343 : {
344 38079276 : if (known)
345 0 : *known = false;
346 38079276 : return 1;
347 : }
348 250054251 : if (known)
349 9023366 : *known = in.m_val != 0;
350 250054251 : if (*this == in)
351 46695351 : return 1;
352 203358900 : gcc_checking_assert (compatible_p (in));
353 203358900 : if (m_val == in.m_val)
354 415 : return 1;
355 203358485 : if (!in.m_val)
356 10946 : return m_val * 4;
357 : /* Auto-FDO 0 really just means that we have no samples.
358 : Treat it as small non-zero frequency. */
359 203347539 : if (!m_val && quality () == AFDO)
360 0 : return (sreal)1 / (sreal)in.m_val;
361 203347539 : return (sreal)m_val / (sreal)in.m_val;
362 : }
363 :
364 : /* We want to scale profile across function boundary from NUM to DEN.
365 : Take care of the side case when DEN is zeros. We still want to behave
366 : sanely here which means
367 : - scale to profile_count::zero () if NUM is profile_count::zero
368 : - do not affect anything if NUM == DEN
369 : - preserve counter value but adjust quality in other cases. */
370 :
371 : void
372 27150774 : profile_count::adjust_for_ipa_scaling (profile_count *num,
373 : profile_count *den)
374 : {
375 : /* Scaling is no-op if NUM and DEN are the same. */
376 27150774 : if (*num == *den)
377 : return;
378 : /* Scaling to zero is always zero. */
379 20846314 : if (*num == zero ())
380 102541 : return;
381 : /* If den is non-zero we are safe.
382 : However take care of zeros in AFDO profiles since
383 : they simply means that no useful samples were collected.
384 : Called function still may contain important loop. */
385 41474885 : if (den->force_nonzero () == *den
386 20731112 : && num->quality () != AFDO)
387 20731112 : return;
388 : /* Force both to non-zero so we do not push profiles to 0 when
389 : both num == 0 and den == 0. */
390 12661 : *den = den->force_nonzero ();
391 12661 : *num = num->force_nonzero ();
392 : }
393 :
394 : /* THIS is a count of bb which is known to be executed IPA times.
395 : Combine this information into bb counter. This means returning IPA
396 : if it is nonzero, not changing anything if IPA is uninitialized
397 : and if IPA is zero, turning THIS into corresponding local profile with
398 : global0. */
399 :
400 : profile_count
401 26218959 : profile_count::combine_with_ipa_count (profile_count ipa)
402 : {
403 26218959 : if (!initialized_p ())
404 18731 : return *this;
405 26200228 : ipa = ipa.ipa ();
406 26200228 : if (ipa.nonzero_p ())
407 111 : return ipa;
408 27262329 : if (!ipa.initialized_p () || *this == zero ())
409 26200037 : return *this;
410 80 : if (ipa == zero ())
411 44 : return this->global0 ();
412 36 : if (ipa == afdo_zero ())
413 0 : return this->global0afdo ();
414 36 : return this->global0adjusted ();
415 : }
416 :
417 : /* Same as profile_count::combine_with_ipa_count but within function with count
418 : IPA2. */
419 : profile_count
420 6852040 : profile_count::combine_with_ipa_count_within (profile_count ipa,
421 : profile_count ipa2)
422 : {
423 6852040 : profile_count ret;
424 6852040 : if (!initialized_p ())
425 867065 : return *this;
426 6193128 : if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
427 208153 : ret = ipa;
428 : else
429 : {
430 : /* For inconsistent profiles we may end up having ipa2 of GLOBAL0
431 : while ipa is non-zero (i.e. non-zero IPA counters within function
432 : executed 0 times). Be sure we produce GLOBAL0 as well
433 : so counters remain compatible. */
434 5776822 : if (ipa.nonzero_p ()
435 5776822 : && ipa2.ipa ().initialized_p ())
436 0 : ipa = ipa2.ipa ();
437 5776822 : ret = combine_with_ipa_count (ipa);
438 : }
439 5984975 : gcc_checking_assert (ret.compatible_p (ipa2));
440 5984975 : return ret;
441 : }
442 :
443 : /* The profiling runtime uses gcov_type, which is usually 64bit integer.
444 : Conversions back and forth are used to read the coverage and get it
445 : into internal representation. */
446 :
447 : profile_count
448 18368916564 : profile_count::from_gcov_type (gcov_type v, profile_quality quality)
449 : {
450 18368916564 : profile_count ret;
451 18368916564 : gcc_checking_assert (v >= 0);
452 18368916564 : if (dump_file && v >= (gcov_type)max_count)
453 0 : fprintf (dump_file,
454 : "Capping gcov count %" PRId64 " to max_count %" PRId64 "\n",
455 : (int64_t) v, (int64_t) max_count);
456 18368916564 : ret.m_val = MIN (v, (gcov_type)max_count);
457 18368916564 : ret.m_quality = quality;
458 18368916564 : return ret;
459 : }
460 :
461 : /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
462 : happens with COUNT2 probability. Return probability that either *THIS or
463 : OTHER happens. */
464 :
465 : profile_probability
466 1307949 : profile_probability::combine_with_count (profile_count count1,
467 : profile_probability other,
468 : profile_count count2) const
469 : {
470 : /* If probabilities are same, we are done.
471 : If counts are nonzero we can distribute accordingly. In remaining
472 : cases just average the values and hope for the best. */
473 33591 : if (*this == other || count1 == count2
474 1341554 : || (count2 == profile_count::zero ()
475 14 : && !(count1 == profile_count::zero ())))
476 1274372 : return *this;
477 34179 : if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
478 602 : return other;
479 33632 : else if (count1.nonzero_p () || count2.nonzero_p ())
480 32975 : return *this * count1.probability_in (count1 + count2)
481 65950 : + other * count2.probability_in (count1 + count2);
482 : else
483 0 : return *this * even () + other * even ();
484 : }
485 :
486 : /* Return probability as sreal in range [0, 1]. */
487 :
488 : sreal
489 49471858 : profile_probability::to_sreal () const
490 : {
491 49471858 : gcc_checking_assert (initialized_p ());
492 49471858 : return ((sreal)m_val) >> (n_bits - 2);
493 : }
494 :
495 : /* Compute square root. */
496 :
497 : profile_probability
498 2594 : profile_probability::sqrt () const
499 : {
500 2594 : if (!initialized_p () || *this == never () || *this == always ())
501 0 : return *this;
502 2594 : profile_probability ret = *this;
503 5188 : ret.set_quality (MIN (ret.quality (), ADJUSTED));
504 2594 : uint32_t min_range = m_val;
505 2594 : uint32_t max_range = max_probability;
506 2594 : if (!m_val)
507 0 : max_range = 0;
508 2594 : if (m_val == max_probability)
509 0 : min_range = max_probability;
510 64850 : while (min_range != max_range)
511 : {
512 62256 : uint32_t val = (min_range + max_range) / 2;
513 62256 : uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
514 62256 : if (val2 == m_val)
515 : min_range = max_range = m_val;
516 62256 : else if (val2 > m_val)
517 23346 : max_range = val - 1;
518 38910 : else if (val2 < m_val)
519 38910 : min_range = val + 1;
520 : }
521 2594 : ret.m_val = min_range;
522 2594 : return ret;
523 : }
524 :
525 : /* Compute n-th power of THIS. */
526 :
527 : profile_probability
528 0 : profile_probability::pow (int n) const
529 : {
530 0 : if (n == 1 || !initialized_p ())
531 0 : return *this;
532 0 : if (!n)
533 0 : return profile_probability::always ();
534 0 : if (!nonzero_p ()
535 0 : || !(profile_probability::always () - *this).nonzero_p ())
536 0 : return *this;
537 0 : profile_probability ret = profile_probability::always ();
538 0 : profile_probability v = *this;
539 0 : int p = 1;
540 0 : while (true)
541 : {
542 0 : if (n & p)
543 0 : ret = ret * v;
544 0 : p <<= 1;
545 0 : if (p > n)
546 : break;
547 0 : v = v * v;
548 : }
549 0 : return ret;
550 : }
551 : profile_count
552 3857378 : profile_count::operator* (const sreal &num) const
553 : {
554 3857378 : if (m_val == 0)
555 835082 : return *this;
556 3022296 : if (!initialized_p ())
557 0 : return uninitialized ();
558 3022296 : sreal scaled = num * m_val;
559 3022296 : gcc_checking_assert (scaled >= 0);
560 3022296 : profile_count ret;
561 3022296 : if (scaled > max_count)
562 : ret.m_val = max_count;
563 : else
564 3022296 : ret.m_val = scaled.to_nearest_int ();
565 3022296 : ret.m_quality = MIN (m_quality, ADJUSTED);
566 3022296 : return ret;
567 : }
568 :
569 : profile_count
570 0 : profile_count::operator*= (const sreal &num)
571 : {
572 0 : return *this * num;
573 : }
574 :
575 : /* Make counter forcibly nonzero. */
576 : profile_count
577 24655954 : profile_count::force_nonzero () const
578 : {
579 24655954 : if (!initialized_p ())
580 3891982 : return *this;
581 20763972 : profile_count ret = *this;
582 : /* Generally values are forced non-zero to handle inconsistent profile
583 : where count 0 needs to be scaled up to non-zero.
584 :
585 : Use cutoff value here to avoid situation where profile has large
586 : cutoff and we perform count = count * num / den where num is non-zero
587 : and den is 0. If profile was scaled by large factor, forcing value
588 : to 1 would lead to large scale factor. */
589 20763972 : gcov_unsigned_t small = profile_info ? profile_info->cutoff / 2 + 1
590 : : 1;
591 20763972 : if (ret.m_val < small)
592 : {
593 32750 : ret.m_val = small;
594 32750 : ret.m_quality = MIN (m_quality, ADJUSTED);
595 : }
596 20763972 : return ret;
597 : }
|
