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 53221464 : profile_count::differs_from_p (profile_count other) const
128 : {
129 53221464 : gcc_checking_assert (compatible_p (other));
130 53221464 : if (!initialized_p () || !other.initialized_p ())
131 47 : return initialized_p () != other.initialized_p ();
132 53221417 : if ((uint64_t)m_val - (uint64_t)other.m_val < 100
133 986354 : || (uint64_t)other.m_val - (uint64_t)m_val < 100)
134 : return false;
135 324520 : if (!other.m_val)
136 : return true;
137 323535 : uint64_t ratio;
138 323535 : safe_scale_64bit (m_val, 100, other.m_val, &ratio);
139 323535 : return ratio < 99 || ratio > 101;
140 : }
141 :
142 : /* Stream THIS from IB. */
143 :
144 : profile_count
145 1541848 : profile_count::stream_in (class lto_input_block *ib)
146 : {
147 1541848 : profile_count ret;
148 1541848 : ret.m_val = streamer_read_gcov_count (ib);
149 1541848 : ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
150 1541848 : return ret;
151 : }
152 :
153 : /* Stream THIS to OB. */
154 :
155 : void
156 911631 : profile_count::stream_out (struct output_block *ob)
157 : {
158 911631 : streamer_write_gcov_count (ob, m_val);
159 911631 : streamer_write_uhwi (ob, m_quality);
160 911631 : }
161 :
162 : /* Stream THIS to OB. */
163 :
164 : void
165 1050839 : profile_count::stream_out (struct lto_output_stream *ob)
166 : {
167 1050839 : streamer_write_gcov_count_stream (ob, m_val);
168 1050839 : streamer_write_uhwi_stream (ob, m_quality);
169 1050839 : }
170 :
171 :
172 : /* Output THIS to BUFFER. */
173 :
174 : void
175 60466 : profile_probability::dump (char *buffer) const
176 : {
177 60466 : 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 60466 : if (m_val == 0)
184 3102 : buffer += sprintf (buffer, "never");
185 57364 : else if (m_val == max_probability)
186 19947 : buffer += sprintf (buffer, "always");
187 : else
188 37417 : buffer += sprintf (buffer, "%3.1f%%", (double)m_val * 100 / max_probability);
189 :
190 60466 : if (quality () == ADJUSTED)
191 5804 : sprintf (buffer, " (adjusted)");
192 54662 : else if (quality () == AFDO)
193 0 : sprintf (buffer, " (auto FDO)");
194 54662 : else if (quality () == GUESSED)
195 33086 : sprintf (buffer, " (guessed)");
196 : }
197 60466 : }
198 :
199 : /* Dump THIS to F. */
200 :
201 : void
202 60452 : profile_probability::dump (FILE *f) const
203 : {
204 60452 : char buffer[64];
205 60452 : dump (buffer);
206 60452 : fputs (buffer, f);
207 60452 : }
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 235442 : profile_probability::differs_lot_from_p (profile_probability other) const
238 : {
239 235442 : if (!initialized_p () || !other.initialized_p ())
240 : return false;
241 235321 : uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
242 235321 : return d > max_probability / 2;
243 : }
244 :
245 : /* Stream THIS from IB. */
246 :
247 : profile_probability
248 859717 : profile_probability::stream_in (class lto_input_block *ib)
249 : {
250 859717 : profile_probability ret;
251 859717 : ret.m_val = streamer_read_uhwi (ib);
252 859717 : ret.m_adjusted_quality = streamer_read_uhwi (ib);
253 859717 : return ret;
254 : }
255 :
256 : /* Stream THIS to OB. */
257 :
258 : void
259 1037518 : profile_probability::stream_out (struct output_block *ob)
260 : {
261 1037518 : streamer_write_uhwi (ob, m_val);
262 1037518 : streamer_write_uhwi (ob, m_adjusted_quality);
263 1037518 : }
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 2243595 : slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
278 : {
279 2243595 : FIXED_WIDE_INT (128) tmp = a;
280 2243595 : wi::overflow_type overflow;
281 2243595 : tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
282 2243595 : gcc_checking_assert (!overflow);
283 2243595 : if (wi::fits_uhwi_p (tmp))
284 : {
285 2242982 : *res = tmp.to_uhwi ();
286 2242982 : return true;
287 : }
288 613 : *res = (uint64_t) -1;
289 613 : 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 1095483363 : profile_count::to_frequency (struct function *fun) const
297 : {
298 1095483363 : if (!initialized_p ())
299 : return BB_FREQ_MAX;
300 1093693982 : if (*this == zero ())
301 15672690 : return 0;
302 1078021292 : STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
303 1078021292 : gcc_assert (fun->cfg->count_max.initialized_p ());
304 1078021292 : profile_probability prob = probability_in (fun->cfg->count_max);
305 1078021292 : if (!prob.initialized_p ())
306 : return REG_BR_PROB_BASE;
307 1078020904 : 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 187408 : profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
316 : {
317 187408 : if (!initialized_p () || !entry_bb_count.initialized_p ())
318 : return CGRAPH_FREQ_BASE;
319 187151 : if (*this == zero ())
320 202 : return 0;
321 186949 : gcc_checking_assert (entry_bb_count.initialized_p ());
322 186949 : uint64_t scale;
323 186949 : gcc_checking_assert (compatible_p (entry_bb_count));
324 373898 : if (!safe_scale_64bit (!entry_bb_count.m_val ? m_val + 1 : m_val,
325 186949 : CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), &scale))
326 : return CGRAPH_FREQ_MAX;
327 186949 : return MIN (scale, CGRAPH_FREQ_MAX);
328 : }
329 :
330 : /* Return THIS/IN as sreal value. */
331 :
332 : sreal
333 316391231 : profile_count::to_sreal_scale (profile_count in, bool *known) const
334 : {
335 340778260 : if (*this == zero ()
336 24387029 : && !(in == zero ()))
337 : {
338 24238419 : if (known)
339 5 : *known = true;
340 24238419 : return 0;
341 : }
342 292152812 : if (!initialized_p () || !in.initialized_p ())
343 : {
344 37983443 : if (known)
345 0 : *known = false;
346 37983443 : return 1;
347 : }
348 254169369 : if (known)
349 9023763 : *known = in.m_val != 0;
350 254169369 : if (*this == in)
351 46210376 : return 1;
352 207958993 : gcc_checking_assert (compatible_p (in));
353 207958993 : if (m_val == in.m_val)
354 412 : return 1;
355 207958581 : if (!in.m_val)
356 10945 : 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 207947636 : if (!m_val && quality () == AFDO)
360 0 : return (sreal)1 / (sreal)in.m_val;
361 207947636 : 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 27063642 : 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 27063642 : if (*num == *den)
377 : return;
378 : /* Scaling to zero is always zero. */
379 20863488 : if (*num == zero ())
380 105035 : 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 41504371 : if (den->force_nonzero () == *den
386 20745918 : && num->quality () != AFDO)
387 20745918 : return;
388 : /* Force both to non-zero so we do not push profiles to 0 when
389 : both num == 0 and den == 0. */
390 12535 : *den = den->force_nonzero ();
391 12535 : *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 26252688 : profile_count::combine_with_ipa_count (profile_count ipa)
402 : {
403 26252688 : if (!initialized_p ())
404 18691 : return *this;
405 26233997 : ipa = ipa.ipa ();
406 26233997 : if (ipa.nonzero_p ())
407 111 : return ipa;
408 27300001 : if (!ipa.initialized_p () || *this == zero ())
409 26233806 : 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 6830043 : profile_count::combine_with_ipa_count_within (profile_count ipa,
421 : profile_count ipa2)
422 : {
423 6830043 : profile_count ret;
424 6830043 : if (!initialized_p ())
425 847766 : return *this;
426 6186508 : if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
427 204231 : 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 5778046 : if (ipa.nonzero_p ()
435 5778046 : && ipa2.ipa ().initialized_p ())
436 0 : ipa = ipa2.ipa ();
437 5778046 : ret = combine_with_ipa_count (ipa);
438 : }
439 5982277 : gcc_checking_assert (ret.compatible_p (ipa2));
440 5982277 : 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 18398173551 : profile_count::from_gcov_type (gcov_type v, profile_quality quality)
449 : {
450 18398173551 : profile_count ret;
451 18398173551 : gcc_checking_assert (v >= 0);
452 18398173551 : 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 18398173551 : ret.m_val = MIN (v, (gcov_type)max_count);
457 18398173551 : ret.m_quality = quality;
458 18398173551 : 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 1311965 : 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 33805 : if (*this == other || count1 == count2
474 1345784 : || (count2 == profile_count::zero ()
475 14 : && !(count1 == profile_count::zero ())))
476 1278174 : return *this;
477 34393 : if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
478 602 : return other;
479 33836 : else if (count1.nonzero_p () || count2.nonzero_p ())
480 33189 : return *this * count1.probability_in (count1 + count2)
481 66378 : + 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 49530367 : profile_probability::to_sreal () const
490 : {
491 49530367 : gcc_checking_assert (initialized_p ());
492 49530367 : 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 3939747 : profile_count::operator* (const sreal &num) const
553 : {
554 3939747 : if (m_val == 0)
555 846513 : return *this;
556 3093234 : if (!initialized_p ())
557 0 : return uninitialized ();
558 3093234 : sreal scaled = num * m_val;
559 3093234 : gcc_checking_assert (scaled >= 0);
560 3093234 : profile_count ret;
561 3093234 : if (scaled > max_count)
562 : ret.m_val = max_count;
563 : else
564 3093234 : ret.m_val = scaled.to_nearest_int ();
565 3093234 : ret.m_quality = MIN (m_quality, ADJUSTED);
566 3093234 : 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 24683617 : profile_count::force_nonzero () const
578 : {
579 24683617 : if (!initialized_p ())
580 3905153 : return *this;
581 20778464 : 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 20778464 : gcov_unsigned_t small = profile_info ? profile_info->cutoff / 2 + 1
590 : : 1;
591 20778464 : if (ret.m_val < small)
592 : {
593 32436 : ret.m_val = small;
594 32436 : ret.m_quality = MIN (m_quality, ADJUSTED);
595 : }
596 20778464 : return ret;
597 : }
|
