Branch data Line data Source code
1 : : /* Profile counter container type.
2 : : Copyright (C) 2017-2025 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 : :
36 : : /* Names from profile_quality enum values. */
37 : :
38 : : const char *profile_quality_names[] =
39 : : {
40 : : "uninitialized",
41 : : "guessed_local",
42 : : "guessed_global0",
43 : : "guessed_global0adjusted",
44 : : "guessed",
45 : : "afdo",
46 : : "adjusted",
47 : : "precise"
48 : : };
49 : :
50 : : /* Get a string describing QUALITY. */
51 : :
52 : : const char *
53 : 51236 : profile_quality_as_string (enum profile_quality quality)
54 : : {
55 : 51236 : return profile_quality_names[quality];
56 : : }
57 : :
58 : : /* Parse VALUE as profile quality and return true when a valid QUALITY. */
59 : :
60 : : bool
61 : 384 : parse_profile_quality (const char *value, profile_quality *quality)
62 : : {
63 : 2330 : for (unsigned i = 0; i < ARRAY_SIZE (profile_quality_names); i++)
64 : 2181 : if (strcmp (profile_quality_names[i], value) == 0)
65 : : {
66 : 235 : *quality = (profile_quality)i;
67 : 235 : return true;
68 : : }
69 : :
70 : : return false;
71 : : }
72 : :
73 : : /* Display names from profile_quality enum values. */
74 : :
75 : : const char *profile_quality_display_names[] =
76 : : {
77 : : NULL,
78 : : "estimated locally",
79 : : "estimated locally, globally 0",
80 : : "estimated locally, globally 0 adjusted",
81 : : "guessed",
82 : : "auto FDO",
83 : : "adjusted",
84 : : "precise"
85 : : };
86 : :
87 : : /* Dump THIS to F. */
88 : :
89 : : void
90 : 79447 : profile_count::dump (FILE *f, struct function *fun) const
91 : : {
92 : 79447 : if (!initialized_p ())
93 : 17 : fprintf (f, "uninitialized");
94 : 131389 : else if (fun && initialized_p ()
95 : 51959 : && fun->cfg
96 : 131389 : && ENTRY_BLOCK_PTR_FOR_FN (fun)->count.initialized_p ())
97 : : {
98 : 51959 : if (compatible_p (ENTRY_BLOCK_PTR_FOR_FN (fun)->count))
99 : 51959 : fprintf (f, "%" PRId64 " (%s, freq %.4f)", m_val,
100 : 51959 : profile_quality_display_names[m_quality],
101 : : to_sreal_scale
102 : 103918 : (ENTRY_BLOCK_PTR_FOR_FN (fun)->count).to_double ());
103 : : else
104 : 0 : fprintf (f, "%" PRId64 " (%s, incompatible with entry block count)",
105 : 0 : m_val, profile_quality_display_names[m_quality]);
106 : : }
107 : : else
108 : 27471 : fprintf (f, "%" PRId64 " (%s)", m_val,
109 : 27471 : profile_quality_display_names[m_quality]);
110 : 79447 : }
111 : :
112 : : /* Dump THIS to stderr. */
113 : :
114 : : void
115 : 0 : profile_count::debug () const
116 : : {
117 : 0 : dump (stderr, cfun);
118 : 0 : fprintf (stderr, "\n");
119 : 0 : }
120 : :
121 : : /* Return true if THIS differs from OTHER; tolerate small differences. */
122 : :
123 : : bool
124 : 53475851 : profile_count::differs_from_p (profile_count other) const
125 : : {
126 : 53475851 : gcc_checking_assert (compatible_p (other));
127 : 53475851 : if (!initialized_p () || !other.initialized_p ())
128 : 51 : return initialized_p () != other.initialized_p ();
129 : 53475800 : if ((uint64_t)m_val - (uint64_t)other.m_val < 100
130 : 972763 : || (uint64_t)other.m_val - (uint64_t)m_val < 100)
131 : : return false;
132 : 305280 : if (!other.m_val)
133 : : return true;
134 : 304448 : uint64_t ratio;
135 : 304448 : safe_scale_64bit (m_val, 100, other.m_val, &ratio);
136 : 304448 : return ratio < 99 || ratio > 101;
137 : : }
138 : :
139 : : /* Stream THIS from IB. */
140 : :
141 : : profile_count
142 : 1535866 : profile_count::stream_in (class lto_input_block *ib)
143 : : {
144 : 1535866 : profile_count ret;
145 : 1535866 : ret.m_val = streamer_read_gcov_count (ib);
146 : 1535866 : ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
147 : 1535866 : return ret;
148 : : }
149 : :
150 : : /* Stream THIS to OB. */
151 : :
152 : : void
153 : 902731 : profile_count::stream_out (struct output_block *ob)
154 : : {
155 : 902731 : streamer_write_gcov_count (ob, m_val);
156 : 902731 : streamer_write_uhwi (ob, m_quality);
157 : 902731 : }
158 : :
159 : : /* Stream THIS to OB. */
160 : :
161 : : void
162 : 1046802 : profile_count::stream_out (struct lto_output_stream *ob)
163 : : {
164 : 1046802 : streamer_write_gcov_count_stream (ob, m_val);
165 : 1046802 : streamer_write_uhwi_stream (ob, m_quality);
166 : 1046802 : }
167 : :
168 : :
169 : : /* Output THIS to BUFFER. */
170 : :
171 : : void
172 : 59044 : profile_probability::dump (char *buffer) const
173 : : {
174 : 59044 : if (!initialized_p ())
175 : 0 : sprintf (buffer, "uninitialized");
176 : : else
177 : : {
178 : : /* Make difference between 0.00 as a roundoff error and actual 0.
179 : : Similarly for 1. */
180 : 59044 : if (m_val == 0)
181 : 2976 : buffer += sprintf (buffer, "never");
182 : 56068 : else if (m_val == max_probability)
183 : 20331 : buffer += sprintf (buffer, "always");
184 : : else
185 : 35737 : buffer += sprintf (buffer, "%3.1f%%", (double)m_val * 100 / max_probability);
186 : :
187 : 59044 : if (m_quality == ADJUSTED)
188 : 5357 : sprintf (buffer, " (adjusted)");
189 : 53687 : else if (m_quality == AFDO)
190 : 0 : sprintf (buffer, " (auto FDO)");
191 : 53687 : else if (m_quality == GUESSED)
192 : 31847 : sprintf (buffer, " (guessed)");
193 : : }
194 : 59044 : }
195 : :
196 : : /* Dump THIS to F. */
197 : :
198 : : void
199 : 59030 : profile_probability::dump (FILE *f) const
200 : : {
201 : 59030 : char buffer[64];
202 : 59030 : dump (buffer);
203 : 59030 : fputs (buffer, f);
204 : 59030 : }
205 : :
206 : : /* Dump THIS to stderr. */
207 : :
208 : : void
209 : 0 : profile_probability::debug () const
210 : : {
211 : 0 : dump (stderr);
212 : 0 : fprintf (stderr, "\n");
213 : 0 : }
214 : :
215 : : /* Return true if THIS differs from OTHER; tolerate small differences. */
216 : :
217 : : bool
218 : 10917 : profile_probability::differs_from_p (profile_probability other) const
219 : : {
220 : 10917 : if (!initialized_p () || !other.initialized_p ())
221 : : return false;
222 : 10917 : if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
223 : 14 : || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
224 : : return false;
225 : 0 : if (!other.m_val)
226 : : return true;
227 : 0 : int64_t ratio = (int64_t)m_val * 100 / other.m_val;
228 : 0 : return ratio < 99 || ratio > 101;
229 : : }
230 : :
231 : : /* Return true if THIS differs significantly from OTHER. */
232 : :
233 : : bool
234 : 236735 : profile_probability::differs_lot_from_p (profile_probability other) const
235 : : {
236 : 236735 : if (!initialized_p () || !other.initialized_p ())
237 : : return false;
238 : 236627 : uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
239 : 236627 : return d > max_probability / 2;
240 : : }
241 : :
242 : : /* Stream THIS from IB. */
243 : :
244 : : profile_probability
245 : 854715 : profile_probability::stream_in (class lto_input_block *ib)
246 : : {
247 : 854715 : profile_probability ret;
248 : 854715 : ret.m_val = streamer_read_uhwi (ib);
249 : 854715 : ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
250 : 854715 : return ret;
251 : : }
252 : :
253 : : /* Stream THIS to OB. */
254 : :
255 : : void
256 : 1026338 : profile_probability::stream_out (struct output_block *ob)
257 : : {
258 : 1026338 : streamer_write_uhwi (ob, m_val);
259 : 1026338 : streamer_write_uhwi (ob, m_quality);
260 : 1026338 : }
261 : :
262 : : /* Stream THIS to OB. */
263 : :
264 : : void
265 : 0 : profile_probability::stream_out (struct lto_output_stream *ob)
266 : : {
267 : 0 : streamer_write_uhwi_stream (ob, m_val);
268 : 0 : streamer_write_uhwi_stream (ob, m_quality);
269 : 0 : }
270 : :
271 : : /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
272 : :
273 : : bool
274 : 583103 : slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
275 : : {
276 : 583103 : FIXED_WIDE_INT (128) tmp = a;
277 : 583103 : wi::overflow_type overflow;
278 : 583103 : tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
279 : 583103 : gcc_checking_assert (!overflow);
280 : 583103 : if (wi::fits_uhwi_p (tmp))
281 : : {
282 : 581816 : *res = tmp.to_uhwi ();
283 : 581816 : return true;
284 : : }
285 : 1287 : *res = (uint64_t) -1;
286 : 1287 : return false;
287 : : }
288 : :
289 : : /* Return count as frequency within FUN scaled in range 0 to REG_FREQ_MAX
290 : : Used for legacy code and should not be used anymore. */
291 : :
292 : : int
293 : 1099285826 : profile_count::to_frequency (struct function *fun) const
294 : : {
295 : 1099285826 : if (!initialized_p ())
296 : : return BB_FREQ_MAX;
297 : 1097497249 : if (*this == zero ())
298 : 15986627 : return 0;
299 : 1081510622 : STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
300 : 1081510622 : gcc_assert (fun->cfg->count_max.initialized_p ());
301 : 1081510622 : profile_probability prob = probability_in (fun->cfg->count_max);
302 : 1081510622 : if (!prob.initialized_p ())
303 : : return REG_BR_PROB_BASE;
304 : 1081510234 : return prob.to_reg_br_prob_base ();
305 : : }
306 : :
307 : : /* Return count as frequency within FUN scaled in range 0 to CGRAPH_FREQ_MAX
308 : : where CGRAPH_FREQ_BASE means that count equals to entry block count.
309 : : Used for legacy code and should not be used anymore. */
310 : :
311 : : int
312 : 187693 : profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
313 : : {
314 : 187693 : if (!initialized_p () || !entry_bb_count.initialized_p ())
315 : : return CGRAPH_FREQ_BASE;
316 : 184319 : if (*this == zero ())
317 : 176 : return 0;
318 : 184143 : gcc_checking_assert (entry_bb_count.initialized_p ());
319 : 184143 : uint64_t scale;
320 : 184143 : gcc_checking_assert (compatible_p (entry_bb_count));
321 : 368286 : if (!safe_scale_64bit (!entry_bb_count.m_val ? m_val + 1 : m_val,
322 : 184143 : CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), &scale))
323 : : return CGRAPH_FREQ_MAX;
324 : 184143 : return MIN (scale, CGRAPH_FREQ_MAX);
325 : : }
326 : :
327 : : /* Return THIS/IN as sreal value. */
328 : :
329 : : sreal
330 : 305495668 : profile_count::to_sreal_scale (profile_count in, bool *known) const
331 : : {
332 : 327436856 : if (*this == zero ()
333 : 21941188 : && !(in == zero ()))
334 : : {
335 : 21721107 : if (known)
336 : 5 : *known = true;
337 : 21721107 : return 0;
338 : : }
339 : 283774561 : if (!initialized_p () || !in.initialized_p ())
340 : : {
341 : 38166692 : if (known)
342 : 14 : *known = false;
343 : 38166692 : return 1;
344 : : }
345 : 245607869 : if (known)
346 : 8750579 : *known = in.m_val != 0;
347 : 245607869 : if (*this == in)
348 : 46220164 : return 1;
349 : 199387705 : gcc_checking_assert (compatible_p (in));
350 : 199387705 : if (m_val == in.m_val)
351 : 427 : return 1;
352 : 199387278 : if (!in.m_val)
353 : 10572 : return m_val * 4;
354 : : /* Auto-FDO 0 really just means that we have no samples.
355 : : Treat it as small non-zero frequency. */
356 : 199376706 : if (!m_val && quality () == AFDO)
357 : 0 : return (sreal)1 / (sreal)in.m_val;
358 : 199376706 : return (sreal)m_val / (sreal)in.m_val;
359 : : }
360 : :
361 : : /* We want to scale profile across function boundary from NUM to DEN.
362 : : Take care of the side case when DEN is zeros. We still want to behave
363 : : sanely here which means
364 : : - scale to profile_count::zero () if NUM is profile_count::zero
365 : : - do not affect anything if NUM == DEN
366 : : - preserve counter value but adjust quality in other cases. */
367 : :
368 : : void
369 : 26504197 : profile_count::adjust_for_ipa_scaling (profile_count *num,
370 : : profile_count *den)
371 : : {
372 : : /* Scaling is no-op if NUM and DEN are the same. */
373 : 26504197 : if (*num == *den)
374 : : return;
375 : : /* Scaling to zero is always zero. */
376 : 20336812 : if (*num == zero ())
377 : 97239 : return;
378 : : /* If den is non-zero we are safe.
379 : : However take care of zeros in AFDO profiles since
380 : : they simply means that no useful samples were collected.
381 : : Called function still may contain important loop. */
382 : 40437242 : if (den->force_nonzero () == *den
383 : 20197669 : && num->quality () != AFDO)
384 : 20197669 : return;
385 : : /* Force both to non-zero so we do not push profiles to 0 when
386 : : both num == 0 and den == 0. */
387 : 41904 : *den = den->force_nonzero ();
388 : 41904 : *num = num->force_nonzero ();
389 : : }
390 : :
391 : : /* THIS is a count of bb which is known to be executed IPA times.
392 : : Combine this information into bb counter. This means returning IPA
393 : : if it is nonzero, not changing anything if IPA is uninitialized
394 : : and if IPA is zero, turning THIS into corresponding local profile with
395 : : global0. */
396 : :
397 : : profile_count
398 : 25760568 : profile_count::combine_with_ipa_count (profile_count ipa)
399 : : {
400 : 25760568 : if (!initialized_p ())
401 : 18340 : return *this;
402 : 25742228 : ipa = ipa.ipa ();
403 : 25742228 : if (ipa.nonzero_p ())
404 : 108 : return ipa;
405 : 26684993 : if (!ipa.initialized_p () || *this == zero ())
406 : 25742037 : return *this;
407 : 83 : if (ipa == zero ())
408 : 44 : return this->global0 ();
409 : 39 : return this->global0adjusted ();
410 : : }
411 : :
412 : : /* Same as profile_count::combine_with_ipa_count but within function with count
413 : : IPA2. */
414 : : profile_count
415 : 6480803 : profile_count::combine_with_ipa_count_within (profile_count ipa,
416 : : profile_count ipa2)
417 : : {
418 : 6480803 : profile_count ret;
419 : 6480803 : if (!initialized_p ())
420 : 796816 : return *this;
421 : 5892863 : if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
422 : 208876 : ret = ipa;
423 : : else
424 : : {
425 : : /* For inconsistent profiles we may end up having ipa2 of GLOBAL0
426 : : while ipa is non-zero (i.e. non-zero IPA counters within function
427 : : executed 0 times). Be sure we produce GLOBAL0 as well
428 : : so counters remain compatible. */
429 : 5475111 : if (ipa.nonzero_p ()
430 : 5475111 : && ipa2.ipa ().initialized_p ())
431 : 0 : ipa = ipa2.ipa ();
432 : 5475111 : ret = combine_with_ipa_count (ipa);
433 : : }
434 : 5683987 : gcc_checking_assert (ret.compatible_p (ipa2));
435 : 5683987 : return ret;
436 : : }
437 : :
438 : : /* The profiling runtime uses gcov_type, which is usually 64bit integer.
439 : : Conversions back and forth are used to read the coverage and get it
440 : : into internal representation. */
441 : :
442 : : profile_count
443 : 18133725081 : profile_count::from_gcov_type (gcov_type v, profile_quality quality)
444 : : {
445 : 18133725081 : profile_count ret;
446 : 18133725081 : gcc_checking_assert (v >= 0);
447 : 18133725081 : if (dump_file && v >= (gcov_type)max_count)
448 : 0 : fprintf (dump_file,
449 : : "Capping gcov count %" PRId64 " to max_count %" PRId64 "\n",
450 : : (int64_t) v, (int64_t) max_count);
451 : 18133725081 : ret.m_val = MIN (v, (gcov_type)max_count);
452 : 18133725081 : ret.m_quality = quality;
453 : 18133725081 : return ret;
454 : : }
455 : :
456 : : /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
457 : : happens with COUNT2 probability. Return probability that either *THIS or
458 : : OTHER happens. */
459 : :
460 : : profile_probability
461 : 1327580 : profile_probability::combine_with_count (profile_count count1,
462 : : profile_probability other,
463 : : profile_count count2) const
464 : : {
465 : : /* If probabilities are same, we are done.
466 : : If counts are nonzero we can distribute accordingly. In remaining
467 : : cases just average the values and hope for the best. */
468 : 1340876 : if (*this == other || count1 == count2
469 : 42061 : || (count2 == profile_count::zero ()
470 : 40 : && !(count1 == profile_count::zero ())))
471 : 1285599 : return *this;
472 : 42595 : if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
473 : 614 : return other;
474 : 44363 : else if (count1.nonzero_p () || count2.nonzero_p ())
475 : 41367 : return *this * count1.probability_in (count1 + count2)
476 : 82734 : + other * count2.probability_in (count1 + count2);
477 : : else
478 : 0 : return *this * even () + other * even ();
479 : : }
480 : :
481 : : /* Return probability as sreal in range [0, 1]. */
482 : :
483 : : sreal
484 : 48250827 : profile_probability::to_sreal () const
485 : : {
486 : 48250827 : gcc_checking_assert (initialized_p ());
487 : 48250827 : return ((sreal)m_val) >> (n_bits - 2);
488 : : }
489 : :
490 : : /* Compute square root. */
491 : :
492 : : profile_probability
493 : 2443 : profile_probability::sqrt () const
494 : : {
495 : 2443 : if (!initialized_p () || *this == never () || *this == always ())
496 : 0 : return *this;
497 : 2443 : profile_probability ret = *this;
498 : 2443 : ret.m_quality = MIN (ret.m_quality, ADJUSTED);
499 : 2443 : uint32_t min_range = m_val;
500 : 2443 : uint32_t max_range = max_probability;
501 : 2443 : if (!m_val)
502 : 0 : max_range = 0;
503 : 2443 : if (m_val == max_probability)
504 : 0 : min_range = max_probability;
505 : 61075 : while (min_range != max_range)
506 : : {
507 : 58632 : uint32_t val = (min_range + max_range) / 2;
508 : 58632 : uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
509 : 58632 : if (val2 == m_val)
510 : : min_range = max_range = m_val;
511 : 58632 : else if (val2 > m_val)
512 : 21987 : max_range = val - 1;
513 : 36645 : else if (val2 < m_val)
514 : 36645 : min_range = val + 1;
515 : : }
516 : 2443 : ret.m_val = min_range;
517 : 2443 : return ret;
518 : : }
519 : :
520 : : /* Compute n-th power of THIS. */
521 : :
522 : : profile_probability
523 : 0 : profile_probability::pow (int n) const
524 : : {
525 : 0 : if (n == 1 || !initialized_p ())
526 : 0 : return *this;
527 : 0 : if (!n)
528 : 0 : return profile_probability::always ();
529 : 0 : if (!nonzero_p ()
530 : 0 : || !(profile_probability::always () - *this).nonzero_p ())
531 : 0 : return *this;
532 : 0 : profile_probability ret = profile_probability::always ();
533 : 0 : profile_probability v = *this;
534 : 0 : int p = 1;
535 : 0 : while (true)
536 : : {
537 : 0 : if (n & p)
538 : 0 : ret = ret * v;
539 : 0 : p <<= 1;
540 : 0 : if (p > n)
541 : : break;
542 : 0 : v = v * v;
543 : : }
544 : 0 : return ret;
545 : : }
546 : : profile_count
547 : 4201714 : profile_count::operator* (const sreal &num) const
548 : : {
549 : 4201714 : if (m_val == 0)
550 : 969097 : return *this;
551 : 3232617 : if (!initialized_p ())
552 : 0 : return uninitialized ();
553 : 3232617 : sreal scaled = num * m_val;
554 : 3232617 : gcc_checking_assert (scaled >= 0);
555 : 3232617 : profile_count ret;
556 : 3232617 : if (m_val > max_count)
557 : : ret.m_val = max_count;
558 : : else
559 : 3232617 : ret.m_val = scaled.to_nearest_int ();
560 : 3232617 : ret.m_quality = MIN (m_quality, ADJUSTED);
561 : 3232617 : return ret;
562 : : }
563 : :
564 : : profile_count
565 : 0 : profile_count::operator*= (const sreal &num)
566 : : {
567 : 0 : return *this * num;
568 : : }
|
