1 | /* Profile counter container type. |
2 | Copyright (C) 2017-2023 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 | profile_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 | |
60 | bool |
61 | parse_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 | |
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 BUFFER. */ |
88 | |
89 | void |
90 | profile_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 | |
107 | void |
108 | profile_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 | |
117 | void |
118 | profile_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 | |
126 | bool |
127 | profile_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 | |
144 | profile_count |
145 | profile_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 | |
155 | void |
156 | profile_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 | |
164 | void |
165 | profile_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 | |
174 | void |
175 | profile_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 | |
201 | void |
202 | profile_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 | |
211 | void |
212 | profile_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 | |
220 | bool |
221 | profile_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 | |
236 | bool |
237 | profile_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 | |
247 | profile_probability |
248 | profile_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 | |
258 | void |
259 | profile_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 | |
267 | void |
268 | profile_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 | |
276 | bool |
277 | slow_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 | |
295 | int |
296 | profile_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 | |
314 | int |
315 | profile_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 | |
332 | sreal |
333 | profile_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 | |
367 | void |
368 | profile_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 | |
392 | profile_count |
393 | profile_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. */ |
409 | profile_count |
410 | profile_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 | |
428 | profile_count |
429 | profile_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 | |
446 | profile_probability |
447 | profile_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 | |
469 | sreal |
470 | profile_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 | |
478 | profile_probability |
479 | profile_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 | |
508 | profile_probability |
509 | profile_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 | |