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

source code of gcc/profile-count.cc