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 | 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 F. */ |
88 | |
89 | void |
90 | profile_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 | |
107 | void |
108 | profile_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 | |
116 | bool |
117 | profile_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 | |
134 | profile_count |
135 | profile_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 | |
145 | void |
146 | profile_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 | |
154 | void |
155 | profile_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 | |
164 | void |
165 | profile_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 | |
191 | void |
192 | profile_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 | |
201 | void |
202 | profile_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 | |
210 | bool |
211 | profile_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 | |
226 | bool |
227 | profile_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 | |
237 | profile_probability |
238 | profile_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 | |
248 | void |
249 | profile_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 | |
257 | void |
258 | profile_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 | |
266 | bool |
267 | slow_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 | |
285 | int |
286 | profile_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 | |
304 | int |
305 | profile_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 | |
322 | sreal |
323 | profile_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 | |
357 | void |
358 | 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 | 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 | |
382 | profile_count |
383 | profile_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. */ |
399 | profile_count |
400 | profile_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 | |
418 | profile_count |
419 | profile_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 | |
436 | profile_probability |
437 | 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 | 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 | |
459 | sreal |
460 | profile_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 | |
468 | profile_probability |
469 | profile_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 | |
498 | profile_probability |
499 | profile_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 | |