1/* Profile counter container type.
2 Copyright (C) 2017-2024 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
38const 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
52const char *
53profile_quality_as_string (enum profile_quality quality)
54{
55 return profile_quality_names[quality];
56}
57
58/* Parse VALUE as profile quality and return true when a valid QUALITY. */
59
60bool
61parse_profile_quality (const char *value, profile_quality *quality)
62{
63 for (unsigned i = 0; i < ARRAY_SIZE (profile_quality_names); i++)
64 if (strcmp (s1: profile_quality_names[i], s2: value) == 0)
65 {
66 *quality = (profile_quality)i;
67 return true;
68 }
69
70 return false;
71}
72
73/* Display names from profile_quality enum values. */
74
75const 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
89void
90profile_count::dump (FILE *f, struct function *fun) const
91{
92 if (!initialized_p ())
93 fprintf (stream: f, format: "uninitialized");
94 else if (fun && initialized_p ()
95 && fun->cfg
96 && ENTRY_BLOCK_PTR_FOR_FN (fun)->count.initialized_p ())
97 fprintf (stream: f, format: "%" PRId64 " (%s, freq %.4f)", m_val,
98 profile_quality_display_names[m_quality],
99 to_sreal_scale (ENTRY_BLOCK_PTR_FOR_FN (fun)->count).to_double ());
100 else
101 fprintf (stream: f, format: "%" PRId64 " (%s)", m_val,
102 profile_quality_display_names[m_quality]);
103}
104
105/* Dump THIS to stderr. */
106
107void
108profile_count::debug () const
109{
110 dump (stderr, cfun);
111 fprintf (stderr, format: "\n");
112}
113
114/* Return true if THIS differs from OTHER; tolerate small differences. */
115
116bool
117profile_count::differs_from_p (profile_count other) const
118{
119 gcc_checking_assert (compatible_p (other));
120 if (!initialized_p () || !other.initialized_p ())
121 return initialized_p () != other.initialized_p ();
122 if ((uint64_t)m_val - (uint64_t)other.m_val < 100
123 || (uint64_t)other.m_val - (uint64_t)m_val < 100)
124 return false;
125 if (!other.m_val)
126 return true;
127 uint64_t ratio;
128 safe_scale_64bit (a: m_val, b: 100, c: other.m_val, res: &ratio);
129 return ratio < 99 || ratio > 101;
130}
131
132/* Stream THIS from IB. */
133
134profile_count
135profile_count::stream_in (class lto_input_block *ib)
136{
137 profile_count ret;
138 ret.m_val = streamer_read_gcov_count (ib);
139 ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
140 return ret;
141}
142
143/* Stream THIS to OB. */
144
145void
146profile_count::stream_out (struct output_block *ob)
147{
148 streamer_write_gcov_count (ob, m_val);
149 streamer_write_uhwi (ob, m_quality);
150}
151
152/* Stream THIS to OB. */
153
154void
155profile_count::stream_out (struct lto_output_stream *ob)
156{
157 streamer_write_gcov_count_stream (ob, m_val);
158 streamer_write_uhwi_stream (ob, m_quality);
159}
160
161
162/* Output THIS to BUFFER. */
163
164void
165profile_probability::dump (char *buffer) const
166{
167 if (!initialized_p ())
168 sprintf (s: buffer, format: "uninitialized");
169 else
170 {
171 /* Make difference between 0.00 as a roundoff error and actual 0.
172 Similarly for 1. */
173 if (m_val == 0)
174 buffer += sprintf (s: buffer, format: "never");
175 else if (m_val == max_probability)
176 buffer += sprintf (s: buffer, format: "always");
177 else
178 buffer += sprintf (s: buffer, format: "%3.1f%%", (double)m_val * 100 / max_probability);
179
180 if (m_quality == ADJUSTED)
181 sprintf (s: buffer, format: " (adjusted)");
182 else if (m_quality == AFDO)
183 sprintf (s: buffer, format: " (auto FDO)");
184 else if (m_quality == GUESSED)
185 sprintf (s: buffer, format: " (guessed)");
186 }
187}
188
189/* Dump THIS to F. */
190
191void
192profile_probability::dump (FILE *f) const
193{
194 char buffer[64];
195 dump (buffer);
196 fputs (s: buffer, stream: f);
197}
198
199/* Dump THIS to stderr. */
200
201void
202profile_probability::debug () const
203{
204 dump (stderr);
205 fprintf (stderr, format: "\n");
206}
207
208/* Return true if THIS differs from OTHER; tolerate small differences. */
209
210bool
211profile_probability::differs_from_p (profile_probability other) const
212{
213 if (!initialized_p () || !other.initialized_p ())
214 return false;
215 if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
216 || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
217 return false;
218 if (!other.m_val)
219 return true;
220 int64_t ratio = (int64_t)m_val * 100 / other.m_val;
221 return ratio < 99 || ratio > 101;
222}
223
224/* Return true if THIS differs significantly from OTHER. */
225
226bool
227profile_probability::differs_lot_from_p (profile_probability other) const
228{
229 if (!initialized_p () || !other.initialized_p ())
230 return false;
231 uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
232 return d > max_probability / 2;
233}
234
235/* Stream THIS from IB. */
236
237profile_probability
238profile_probability::stream_in (class lto_input_block *ib)
239{
240 profile_probability ret;
241 ret.m_val = streamer_read_uhwi (ib);
242 ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
243 return ret;
244}
245
246/* Stream THIS to OB. */
247
248void
249profile_probability::stream_out (struct output_block *ob)
250{
251 streamer_write_uhwi (ob, m_val);
252 streamer_write_uhwi (ob, m_quality);
253}
254
255/* Stream THIS to OB. */
256
257void
258profile_probability::stream_out (struct lto_output_stream *ob)
259{
260 streamer_write_uhwi_stream (ob, m_val);
261 streamer_write_uhwi_stream (ob, m_quality);
262}
263
264/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
265
266bool
267slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
268{
269 FIXED_WIDE_INT (128) tmp = a;
270 wi::overflow_type overflow;
271 tmp = wi::udiv_floor (x: wi::umul (x: tmp, y: b, overflow: &overflow) + (c / 2), y: c);
272 gcc_checking_assert (!overflow);
273 if (wi::fits_uhwi_p (x: tmp))
274 {
275 *res = tmp.to_uhwi ();
276 return true;
277 }
278 *res = (uint64_t) -1;
279 return false;
280}
281
282/* Return count as frequency within FUN scaled in range 0 to REG_FREQ_MAX
283 Used for legacy code and should not be used anymore. */
284
285int
286profile_count::to_frequency (struct function *fun) const
287{
288 if (!initialized_p ())
289 return BB_FREQ_MAX;
290 if (*this == zero ())
291 return 0;
292 STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
293 gcc_assert (fun->cfg->count_max.initialized_p ());
294 profile_probability prob = probability_in (overall: fun->cfg->count_max);
295 if (!prob.initialized_p ())
296 return REG_BR_PROB_BASE;
297 return prob.to_reg_br_prob_base ();
298}
299
300/* Return count as frequency within FUN scaled in range 0 to CGRAPH_FREQ_MAX
301 where CGRAPH_FREQ_BASE means that count equals to entry block count.
302 Used for legacy code and should not be used anymore. */
303
304int
305profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
306{
307 if (!initialized_p () || !entry_bb_count.initialized_p ())
308 return CGRAPH_FREQ_BASE;
309 if (*this == zero ())
310 return 0;
311 gcc_checking_assert (entry_bb_count.initialized_p ());
312 uint64_t scale;
313 gcc_checking_assert (compatible_p (entry_bb_count));
314 if (!safe_scale_64bit (a: !entry_bb_count.m_val ? m_val + 1 : m_val,
315 CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), res: &scale))
316 return CGRAPH_FREQ_MAX;
317 return MIN (scale, CGRAPH_FREQ_MAX);
318}
319
320/* Return THIS/IN as sreal value. */
321
322sreal
323profile_count::to_sreal_scale (profile_count in, bool *known) const
324{
325 if (*this == zero ()
326 && !(in == zero ()))
327 {
328 if (known)
329 *known = true;
330 return 0;
331 }
332 if (!initialized_p () || !in.initialized_p ())
333 {
334 if (known)
335 *known = false;
336 return 1;
337 }
338 if (known)
339 *known = in.m_val != 0;
340 if (*this == in)
341 return 1;
342 gcc_checking_assert (compatible_p (in));
343 if (m_val == in.m_val)
344 return 1;
345 if (!in.m_val)
346 return m_val * 4;
347 return (sreal)m_val / (sreal)in.m_val;
348}
349
350/* We want to scale profile across function boundary from NUM to DEN.
351 Take care of the side case when DEN is zeros. We still want to behave
352 sanely here which means
353 - scale to profile_count::zero () if NUM is profile_count::zero
354 - do not affect anything if NUM == DEN
355 - preserve counter value but adjust quality in other cases. */
356
357void
358profile_count::adjust_for_ipa_scaling (profile_count *num,
359 profile_count *den)
360{
361 /* Scaling is no-op if NUM and DEN are the same. */
362 if (*num == *den)
363 return;
364 /* Scaling to zero is always zero. */
365 if (*num == zero ())
366 return;
367 /* If den is non-zero we are safe. */
368 if (den->force_nonzero () == *den)
369 return;
370 /* Force both to non-zero so we do not push profiles to 0 when
371 both num == 0 and den == 0. */
372 *den = den->force_nonzero ();
373 *num = num->force_nonzero ();
374}
375
376/* THIS is a count of bb which is known to be executed IPA times.
377 Combine this information into bb counter. This means returning IPA
378 if it is nonzero, not changing anything if IPA is uninitialized
379 and if IPA is zero, turning THIS into corresponding local profile with
380 global0. */
381
382profile_count
383profile_count::combine_with_ipa_count (profile_count ipa)
384{
385 if (!initialized_p ())
386 return *this;
387 ipa = ipa.ipa ();
388 if (ipa.nonzero_p ())
389 return ipa;
390 if (!ipa.initialized_p () || *this == zero ())
391 return *this;
392 if (ipa == zero ())
393 return this->global0 ();
394 return this->global0adjusted ();
395}
396
397/* Sae as profile_count::combine_with_ipa_count but within function with count
398 IPA2. */
399profile_count
400profile_count::combine_with_ipa_count_within (profile_count ipa,
401 profile_count ipa2)
402{
403 profile_count ret;
404 if (!initialized_p ())
405 return *this;
406 if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
407 ret = ipa;
408 else
409 ret = combine_with_ipa_count (ipa);
410 gcc_checking_assert (ret.compatible_p (ipa2));
411 return ret;
412}
413
414/* The profiling runtime uses gcov_type, which is usually 64bit integer.
415 Conversions back and forth are used to read the coverage and get it
416 into internal representation. */
417
418profile_count
419profile_count::from_gcov_type (gcov_type v, profile_quality quality)
420 {
421 profile_count ret;
422 gcc_checking_assert (v >= 0);
423 if (dump_file && v >= (gcov_type)max_count)
424 fprintf (stream: dump_file,
425 format: "Capping gcov count %" PRId64 " to max_count %" PRId64 "\n",
426 (int64_t) v, (int64_t) max_count);
427 ret.m_val = MIN (v, (gcov_type)max_count);
428 ret.m_quality = quality;
429 return ret;
430 }
431
432/* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
433 happens with COUNT2 probability. Return probability that either *THIS or
434 OTHER happens. */
435
436profile_probability
437profile_probability::combine_with_count (profile_count count1,
438 profile_probability other,
439 profile_count count2) const
440{
441 /* If probabilities are same, we are done.
442 If counts are nonzero we can distribute accordingly. In remaining
443 cases just average the values and hope for the best. */
444 if (*this == other || count1 == count2
445 || (count2 == profile_count::zero ()
446 && !(count1 == profile_count::zero ())))
447 return *this;
448 if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
449 return other;
450 else if (count1.nonzero_p () || count2.nonzero_p ())
451 return *this * count1.probability_in (overall: count1 + count2)
452 + other * count2.probability_in (overall: count1 + count2);
453 else
454 return *this * even () + other * even ();
455}
456
457/* Return probability as sreal in range [0, 1]. */
458
459sreal
460profile_probability::to_sreal () const
461{
462 gcc_checking_assert (initialized_p ());
463 return ((sreal)m_val) >> (n_bits - 2);
464}
465
466/* Compute square root. */
467
468profile_probability
469profile_probability::sqrt () const
470{
471 if (!initialized_p () || *this == never () || *this == always ())
472 return *this;
473 profile_probability ret = *this;
474 ret.m_quality = MIN (ret.m_quality, ADJUSTED);
475 uint32_t min_range = m_val;
476 uint32_t max_range = max_probability;
477 if (!m_val)
478 max_range = 0;
479 if (m_val == max_probability)
480 min_range = max_probability;
481 while (min_range != max_range)
482 {
483 uint32_t val = (min_range + max_range) / 2;
484 uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
485 if (val2 == m_val)
486 min_range = max_range = m_val;
487 else if (val2 > m_val)
488 max_range = val - 1;
489 else if (val2 < m_val)
490 min_range = val + 1;
491 }
492 ret.m_val = min_range;
493 return ret;
494}
495
496/* Compute n-th power of THIS. */
497
498profile_probability
499profile_probability::pow (int n) const
500{
501 if (n == 1 || !initialized_p ())
502 return *this;
503 if (!n)
504 return profile_probability::always ();
505 if (!nonzero_p ()
506 || !(profile_probability::always () - *this).nonzero_p ())
507 return *this;
508 profile_probability ret = profile_probability::always ();
509 profile_probability v = *this;
510 int p = 1;
511 while (true)
512 {
513 if (n & p)
514 ret = ret * v;
515 p <<= 1;
516 if (p > n)
517 break;
518 v = v * v;
519 }
520 return ret;
521}
522

source code of gcc/profile-count.cc