Branch data Line data Source code
1 : : /* Profile counter container type.
2 : : Copyright (C) 2017-2024 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 : 36129 : profile_quality_as_string (enum profile_quality quality)
54 : : {
55 : 36129 : return profile_quality_names[quality];
56 : : }
57 : :
58 : : /* Parse VALUE as profile quality and return true when a valid QUALITY. */
59 : :
60 : : bool
61 : 356 : parse_profile_quality (const char *value, profile_quality *quality)
62 : : {
63 : 2078 : for (unsigned i = 0; i < ARRAY_SIZE (profile_quality_names); i++)
64 : 1957 : 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 : 81443 : profile_count::dump (FILE *f, struct function *fun) const
91 : : {
92 : 81443 : if (!initialized_p ())
93 : 22 : fprintf (f, "uninitialized");
94 : 133978 : else if (fun && initialized_p ()
95 : 52557 : && fun->cfg
96 : 133978 : && ENTRY_BLOCK_PTR_FOR_FN (fun)->count.initialized_p ())
97 : 52557 : fprintf (f, "%" PRId64 " (%s, freq %.4f)", m_val,
98 : 52557 : profile_quality_display_names[m_quality],
99 : 105114 : to_sreal_scale (ENTRY_BLOCK_PTR_FOR_FN (fun)->count).to_double ());
100 : : else
101 : 28864 : fprintf (f, "%" PRId64 " (%s)", m_val,
102 : 28864 : profile_quality_display_names[m_quality]);
103 : 81443 : }
104 : :
105 : : /* Dump THIS to stderr. */
106 : :
107 : : void
108 : 0 : profile_count::debug () const
109 : : {
110 : 0 : dump (stderr, cfun);
111 : 0 : fprintf (stderr, "\n");
112 : 0 : }
113 : :
114 : : /* Return true if THIS differs from OTHER; tolerate small differences. */
115 : :
116 : : bool
117 : 49034946 : profile_count::differs_from_p (profile_count other) const
118 : : {
119 : 49034946 : gcc_checking_assert (compatible_p (other));
120 : 49034946 : if (!initialized_p () || !other.initialized_p ())
121 : 51 : return initialized_p () != other.initialized_p ();
122 : 49034895 : if ((uint64_t)m_val - (uint64_t)other.m_val < 100
123 : 825579 : || (uint64_t)other.m_val - (uint64_t)m_val < 100)
124 : : return false;
125 : 245392 : if (!other.m_val)
126 : : return true;
127 : 244328 : uint64_t ratio;
128 : 244328 : safe_scale_64bit (m_val, 100, other.m_val, &ratio);
129 : 244328 : return ratio < 99 || ratio > 101;
130 : : }
131 : :
132 : : /* Stream THIS from IB. */
133 : :
134 : : profile_count
135 : 1503279 : profile_count::stream_in (class lto_input_block *ib)
136 : : {
137 : 1503279 : profile_count ret;
138 : 1503279 : ret.m_val = streamer_read_gcov_count (ib);
139 : 1503279 : ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
140 : 1503279 : return ret;
141 : : }
142 : :
143 : : /* Stream THIS to OB. */
144 : :
145 : : void
146 : 884142 : profile_count::stream_out (struct output_block *ob)
147 : : {
148 : 884142 : streamer_write_gcov_count (ob, m_val);
149 : 884142 : streamer_write_uhwi (ob, m_quality);
150 : 884142 : }
151 : :
152 : : /* Stream THIS to OB. */
153 : :
154 : : void
155 : 1028146 : profile_count::stream_out (struct lto_output_stream *ob)
156 : : {
157 : 1028146 : streamer_write_gcov_count_stream (ob, m_val);
158 : 1028146 : streamer_write_uhwi_stream (ob, m_quality);
159 : 1028146 : }
160 : :
161 : :
162 : : /* Output THIS to BUFFER. */
163 : :
164 : : void
165 : 59340 : profile_probability::dump (char *buffer) const
166 : : {
167 : 59340 : if (!initialized_p ())
168 : 0 : sprintf (buffer, "uninitialized");
169 : : else
170 : : {
171 : : /* Make difference between 0.00 as a roundoff error and actual 0.
172 : : Similarly for 1. */
173 : 59340 : if (m_val == 0)
174 : 3055 : buffer += sprintf (buffer, "never");
175 : 56285 : else if (m_val == max_probability)
176 : 21165 : buffer += sprintf (buffer, "always");
177 : : else
178 : 35120 : buffer += sprintf (buffer, "%3.1f%%", (double)m_val * 100 / max_probability);
179 : :
180 : 59340 : if (m_quality == ADJUSTED)
181 : 5383 : sprintf (buffer, " (adjusted)");
182 : 53957 : else if (m_quality == AFDO)
183 : 0 : sprintf (buffer, " (auto FDO)");
184 : 53957 : else if (m_quality == GUESSED)
185 : 31341 : sprintf (buffer, " (guessed)");
186 : : }
187 : 59340 : }
188 : :
189 : : /* Dump THIS to F. */
190 : :
191 : : void
192 : 59326 : profile_probability::dump (FILE *f) const
193 : : {
194 : 59326 : char buffer[64];
195 : 59326 : dump (buffer);
196 : 59326 : fputs (buffer, f);
197 : 59326 : }
198 : :
199 : : /* Dump THIS to stderr. */
200 : :
201 : : void
202 : 0 : profile_probability::debug () const
203 : : {
204 : 0 : dump (stderr);
205 : 0 : fprintf (stderr, "\n");
206 : 0 : }
207 : :
208 : : /* Return true if THIS differs from OTHER; tolerate small differences. */
209 : :
210 : : bool
211 : 11097 : profile_probability::differs_from_p (profile_probability other) const
212 : : {
213 : 11097 : if (!initialized_p () || !other.initialized_p ())
214 : : return false;
215 : 11097 : if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
216 : 14 : || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
217 : : return false;
218 : 0 : if (!other.m_val)
219 : : return true;
220 : 0 : int64_t ratio = (int64_t)m_val * 100 / other.m_val;
221 : 0 : return ratio < 99 || ratio > 101;
222 : : }
223 : :
224 : : /* Return true if THIS differs significantly from OTHER. */
225 : :
226 : : bool
227 : 203584 : profile_probability::differs_lot_from_p (profile_probability other) const
228 : : {
229 : 203584 : if (!initialized_p () || !other.initialized_p ())
230 : : return false;
231 : 203499 : uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
232 : 203499 : return d > max_probability / 2;
233 : : }
234 : :
235 : : /* Stream THIS from IB. */
236 : :
237 : : profile_probability
238 : 840394 : profile_probability::stream_in (class lto_input_block *ib)
239 : : {
240 : 840394 : profile_probability ret;
241 : 840394 : ret.m_val = streamer_read_uhwi (ib);
242 : 840394 : ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
243 : 840394 : return ret;
244 : : }
245 : :
246 : : /* Stream THIS to OB. */
247 : :
248 : : void
249 : 1007785 : profile_probability::stream_out (struct output_block *ob)
250 : : {
251 : 1007785 : streamer_write_uhwi (ob, m_val);
252 : 1007785 : streamer_write_uhwi (ob, m_quality);
253 : 1007785 : }
254 : :
255 : : /* Stream THIS to OB. */
256 : :
257 : : void
258 : 0 : profile_probability::stream_out (struct lto_output_stream *ob)
259 : : {
260 : 0 : streamer_write_uhwi_stream (ob, m_val);
261 : 0 : streamer_write_uhwi_stream (ob, m_quality);
262 : 0 : }
263 : :
264 : : /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
265 : :
266 : : bool
267 : 531397 : slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
268 : : {
269 : 531397 : FIXED_WIDE_INT (128) tmp = a;
270 : 531397 : wi::overflow_type overflow;
271 : 531397 : tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
272 : 531397 : gcc_checking_assert (!overflow);
273 : 531397 : if (wi::fits_uhwi_p (tmp))
274 : : {
275 : 530218 : *res = tmp.to_uhwi ();
276 : 530218 : return true;
277 : : }
278 : 1179 : *res = (uint64_t) -1;
279 : 1179 : 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 : :
285 : : int
286 : 939651509 : profile_count::to_frequency (struct function *fun) const
287 : : {
288 : 939651509 : if (!initialized_p ())
289 : : return BB_FREQ_MAX;
290 : 938063362 : if (*this == zero ())
291 : 14589156 : return 0;
292 : 923474206 : STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
293 : 923474206 : gcc_assert (fun->cfg->count_max.initialized_p ());
294 : 923474206 : profile_probability prob = probability_in (fun->cfg->count_max);
295 : 923474206 : if (!prob.initialized_p ())
296 : : return REG_BR_PROB_BASE;
297 : 923473818 : 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 : :
304 : : int
305 : 192516 : profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
306 : : {
307 : 192516 : if (!initialized_p () || !entry_bb_count.initialized_p ())
308 : : return CGRAPH_FREQ_BASE;
309 : 188187 : if (*this == zero ())
310 : 142 : return 0;
311 : 188045 : gcc_checking_assert (entry_bb_count.initialized_p ());
312 : 188045 : uint64_t scale;
313 : 188045 : gcc_checking_assert (compatible_p (entry_bb_count));
314 : 376090 : if (!safe_scale_64bit (!entry_bb_count.m_val ? m_val + 1 : m_val,
315 : 188045 : CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), &scale))
316 : : return CGRAPH_FREQ_MAX;
317 : 188045 : return MIN (scale, CGRAPH_FREQ_MAX);
318 : : }
319 : :
320 : : /* Return THIS/IN as sreal value. */
321 : :
322 : : sreal
323 : 264895418 : profile_count::to_sreal_scale (profile_count in, bool *known) const
324 : : {
325 : 290685711 : if (*this == zero ()
326 : 25790293 : && !(in == zero ()))
327 : : {
328 : 25627307 : if (known)
329 : 5 : *known = true;
330 : 25627307 : return 0;
331 : : }
332 : 239268111 : if (!initialized_p () || !in.initialized_p ())
333 : : {
334 : 35000926 : if (known)
335 : 18 : *known = false;
336 : 35000926 : return 1;
337 : : }
338 : 204267185 : if (known)
339 : 7474272 : *known = in.m_val != 0;
340 : 204267185 : if (*this == in)
341 : 31203637 : return 1;
342 : 173063548 : gcc_checking_assert (compatible_p (in));
343 : 173063548 : if (m_val == in.m_val)
344 : 284 : return 1;
345 : 173063264 : if (!in.m_val)
346 : 9831 : return m_val * 4;
347 : 173053433 : 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 : :
357 : : void
358 : 22062060 : profile_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 : 22062060 : if (*num == *den)
363 : : return;
364 : : /* Scaling to zero is always zero. */
365 : 16599287 : if (*num == zero ())
366 : 74342 : return;
367 : : /* If den is non-zero we are safe. */
368 : 16524945 : if (den->force_nonzero () == *den)
369 : 16505122 : return;
370 : : /* Force both to non-zero so we do not push profiles to 0 when
371 : : both num == 0 and den == 0. */
372 : 19823 : *den = den->force_nonzero ();
373 : 19823 : *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 : :
382 : : profile_count
383 : 22578524 : profile_count::combine_with_ipa_count (profile_count ipa)
384 : : {
385 : 22578524 : if (!initialized_p ())
386 : 14935 : return *this;
387 : 22563589 : ipa = ipa.ipa ();
388 : 22563589 : if (ipa.nonzero_p ())
389 : 78 : return ipa;
390 : 23129543 : if (!ipa.initialized_p () || *this == zero ())
391 : 22563451 : return *this;
392 : 60 : if (ipa == zero ())
393 : 26 : return this->global0 ();
394 : 34 : return this->global0adjusted ();
395 : : }
396 : :
397 : : /* Sae as profile_count::combine_with_ipa_count but within function with count
398 : : IPA2. */
399 : : profile_count
400 : 5336016 : profile_count::combine_with_ipa_count_within (profile_count ipa,
401 : : profile_count ipa2)
402 : : {
403 : 5336016 : profile_count ret;
404 : 5336016 : if (!initialized_p ())
405 : 729854 : return *this;
406 : 4694319 : if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
407 : 88157 : ret = ipa;
408 : : else
409 : 4518005 : ret = combine_with_ipa_count (ipa);
410 : 4606162 : gcc_checking_assert (ret.compatible_p (ipa2));
411 : 4606162 : 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 : :
418 : : profile_count
419 : 12852829241 : profile_count::from_gcov_type (gcov_type v, profile_quality quality)
420 : : {
421 : 12852829241 : profile_count ret;
422 : 12852829241 : gcc_checking_assert (v >= 0);
423 : 12852829241 : if (dump_file && v >= (gcov_type)max_count)
424 : 0 : fprintf (dump_file,
425 : : "Capping gcov count %" PRId64 " to max_count %" PRId64 "\n",
426 : : (int64_t) v, (int64_t) max_count);
427 : 12852829241 : ret.m_val = MIN (v, (gcov_type)max_count);
428 : 12852829241 : ret.m_quality = quality;
429 : 12852829241 : 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 : :
436 : : profile_probability
437 : 1154049 : profile_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 : 1163390 : if (*this == other || count1 == count2
445 : 28956 : || (count2 == profile_count::zero ()
446 : 14 : && !(count1 == profile_count::zero ())))
447 : 1125121 : return *this;
448 : 29528 : if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
449 : 600 : return other;
450 : 30753 : else if (count1.nonzero_p () || count2.nonzero_p ())
451 : 28328 : return *this * count1.probability_in (count1 + count2)
452 : 56656 : + other * count2.probability_in (count1 + count2);
453 : : else
454 : 0 : return *this * even () + other * even ();
455 : : }
456 : :
457 : : /* Return probability as sreal in range [0, 1]. */
458 : :
459 : : sreal
460 : 42545657 : profile_probability::to_sreal () const
461 : : {
462 : 42545657 : gcc_checking_assert (initialized_p ());
463 : 42545657 : return ((sreal)m_val) >> (n_bits - 2);
464 : : }
465 : :
466 : : /* Compute square root. */
467 : :
468 : : profile_probability
469 : 2167 : profile_probability::sqrt () const
470 : : {
471 : 2167 : if (!initialized_p () || *this == never () || *this == always ())
472 : 0 : return *this;
473 : 2167 : profile_probability ret = *this;
474 : 2167 : ret.m_quality = MIN (ret.m_quality, ADJUSTED);
475 : 2167 : uint32_t min_range = m_val;
476 : 2167 : uint32_t max_range = max_probability;
477 : 2167 : if (!m_val)
478 : 0 : max_range = 0;
479 : 2167 : if (m_val == max_probability)
480 : 0 : min_range = max_probability;
481 : 54175 : while (min_range != max_range)
482 : : {
483 : 52008 : uint32_t val = (min_range + max_range) / 2;
484 : 52008 : uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
485 : 52008 : if (val2 == m_val)
486 : : min_range = max_range = m_val;
487 : 52008 : else if (val2 > m_val)
488 : 19503 : max_range = val - 1;
489 : 32505 : else if (val2 < m_val)
490 : 32505 : min_range = val + 1;
491 : : }
492 : 2167 : ret.m_val = min_range;
493 : 2167 : return ret;
494 : : }
495 : :
496 : : /* Compute n-th power of THIS. */
497 : :
498 : : profile_probability
499 : 0 : profile_probability::pow (int n) const
500 : : {
501 : 0 : if (n == 1 || !initialized_p ())
502 : 0 : return *this;
503 : 0 : if (!n)
504 : 0 : return profile_probability::always ();
505 : 0 : if (!nonzero_p ()
506 : 0 : || !(profile_probability::always () - *this).nonzero_p ())
507 : 0 : return *this;
508 : 0 : profile_probability ret = profile_probability::always ();
509 : 0 : profile_probability v = *this;
510 : 0 : int p = 1;
511 : 0 : while (true)
512 : : {
513 : 0 : if (n & p)
514 : 0 : ret = ret * v;
515 : 0 : p <<= 1;
516 : 0 : if (p > n)
517 : : break;
518 : 0 : v = v * v;
519 : : }
520 : 0 : return ret;
521 : : }
|
