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