111
|
1 /* Profile counter container type.
|
131
|
2 Copyright (C) 2017-2018 Free Software Foundation, Inc.
|
111
|
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 #ifndef GCC_PROFILE_COUNT_H
|
|
22 #define GCC_PROFILE_COUNT_H
|
|
23
|
131
|
24 struct function;
|
|
25 class profile_count;
|
|
26
|
111
|
27 /* Quality of the profile count. Because gengtype does not support enums
|
|
28 inside of classes, this is in global namespace. */
|
|
29 enum profile_quality {
|
131
|
30 /* Uninitialized value. */
|
|
31 profile_uninitialized,
|
|
32 /* Profile is based on static branch prediction heuristics and may
|
|
33 or may not match reality. It is local to function and can not be compared
|
|
34 inter-procedurally. Never used by probabilities (they are always local).
|
|
35 */
|
|
36 profile_guessed_local,
|
|
37 /* Profile was read by feedback and was 0, we used local heuristics to guess
|
|
38 better. This is the case of functions not run in profile fedback.
|
|
39 Never used by probabilities. */
|
|
40 profile_guessed_global0,
|
|
41
|
|
42 /* Same as profile_guessed_global0 but global count is adjusted 0. */
|
|
43 profile_guessed_global0adjusted,
|
|
44
|
111
|
45 /* Profile is based on static branch prediction heuristics. It may or may
|
131
|
46 not reflect the reality but it can be compared interprocedurally
|
|
47 (for example, we inlined function w/o profile feedback into function
|
|
48 with feedback and propagated from that).
|
|
49 Never used by probablities. */
|
|
50 profile_guessed,
|
111
|
51 /* Profile was determined by autofdo. */
|
131
|
52 profile_afdo,
|
111
|
53 /* Profile was originally based on feedback but it was adjusted
|
|
54 by code duplicating optimization. It may not precisely reflect the
|
|
55 particular code path. */
|
131
|
56 profile_adjusted,
|
111
|
57 /* Profile was read from profile feedback or determined by accurate static
|
|
58 method. */
|
131
|
59 profile_precise
|
111
|
60 };
|
|
61
|
131
|
62 extern const char *profile_quality_as_string (enum profile_quality);
|
|
63
|
111
|
64 /* The base value for branch probability notes and edge probabilities. */
|
|
65 #define REG_BR_PROB_BASE 10000
|
|
66
|
|
67 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
|
|
68
|
|
69 bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res);
|
|
70
|
|
71 /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
|
|
72
|
|
73 inline bool
|
|
74 safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
|
|
75 {
|
|
76 #if (GCC_VERSION >= 5000)
|
|
77 uint64_t tmp;
|
|
78 if (!__builtin_mul_overflow (a, b, &tmp)
|
|
79 && !__builtin_add_overflow (tmp, c/2, &tmp))
|
|
80 {
|
|
81 *res = tmp / c;
|
|
82 return true;
|
|
83 }
|
|
84 if (c == 1)
|
|
85 {
|
|
86 *res = (uint64_t) -1;
|
|
87 return false;
|
|
88 }
|
|
89 #else
|
|
90 if (a < ((uint64_t)1 << 31)
|
|
91 && b < ((uint64_t)1 << 31)
|
|
92 && c < ((uint64_t)1 << 31))
|
|
93 {
|
|
94 *res = (a * b + (c / 2)) / c;
|
|
95 return true;
|
|
96 }
|
|
97 #endif
|
|
98 return slow_safe_scale_64bit (a, b, c, res);
|
|
99 }
|
|
100
|
|
101 /* Data type to hold probabilities. It implements fixed point arithmetics
|
|
102 with capping so probability is always in range [0,1] and scaling requiring
|
|
103 values greater than 1 needs to be represented otherwise.
|
|
104
|
|
105 In addition to actual value the quality of profile is tracked and propagated
|
|
106 through all operations. Special value UNINITIALIZED is used for probabilities
|
|
107 that has not been determined yet (for example bacause of
|
|
108 -fno-guess-branch-probability)
|
|
109
|
|
110 Typically probabilities are derived from profile feedback (via
|
|
111 probability_in_gcov_type), autoFDO or guessed statically and then propagated
|
|
112 thorough the compilation.
|
|
113
|
|
114 Named probabilities are available:
|
|
115 - never (0 probability)
|
|
116 - guessed_never
|
|
117 - very_unlikely (1/2000 probability)
|
|
118 - unlikely (1/5 probablity)
|
|
119 - even (1/2 probability)
|
|
120 - likely (4/5 probability)
|
|
121 - very_likely (1999/2000 probability)
|
|
122 - guessed_always
|
|
123 - always
|
|
124
|
|
125 Named probabilities except for never/always are assumed to be statically
|
|
126 guessed and thus not necessarily accurate. The difference between never
|
|
127 and guessed_never is that the first one should be used only in case that
|
|
128 well behaving program will very likely not execute the "never" path.
|
|
129 For example if the path is going to abort () call or it exception handling.
|
|
130
|
|
131 Always and guessed_always probabilities are symmetric.
|
|
132
|
|
133 For legacy code we support conversion to/from REG_BR_PROB_BASE based fixpoint
|
|
134 integer arithmetics. Once the code is converted to branch probabilities,
|
|
135 these conversions will probably go away because they are lossy.
|
|
136 */
|
|
137
|
|
138 class GTY((user)) profile_probability
|
|
139 {
|
131
|
140 static const int n_bits = 29;
|
111
|
141 /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that
|
|
142 will lead to harder multiplication sequences. */
|
|
143 static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2);
|
|
144 static const uint32_t uninitialized_probability
|
|
145 = ((uint32_t) 1 << (n_bits - 1)) - 1;
|
|
146
|
131
|
147 uint32_t m_val : 29;
|
|
148 enum profile_quality m_quality : 3;
|
111
|
149
|
|
150 friend class profile_count;
|
|
151 public:
|
|
152
|
|
153 /* Named probabilities. */
|
|
154 static profile_probability never ()
|
|
155 {
|
|
156 profile_probability ret;
|
|
157 ret.m_val = 0;
|
|
158 ret.m_quality = profile_precise;
|
|
159 return ret;
|
|
160 }
|
|
161 static profile_probability guessed_never ()
|
|
162 {
|
|
163 profile_probability ret;
|
|
164 ret.m_val = 0;
|
|
165 ret.m_quality = profile_guessed;
|
|
166 return ret;
|
|
167 }
|
|
168 static profile_probability very_unlikely ()
|
|
169 {
|
|
170 /* Be consistent with PROB_VERY_UNLIKELY in predict.h. */
|
|
171 profile_probability r
|
131
|
172 = profile_probability::guessed_always ().apply_scale (1, 2000);
|
111
|
173 r.m_val--;
|
|
174 return r;
|
|
175 }
|
|
176 static profile_probability unlikely ()
|
|
177 {
|
|
178 /* Be consistent with PROB_VERY_LIKELY in predict.h. */
|
|
179 profile_probability r
|
131
|
180 = profile_probability::guessed_always ().apply_scale (1, 5);
|
111
|
181 r.m_val--;
|
|
182 return r;
|
|
183 }
|
|
184 static profile_probability even ()
|
|
185 {
|
131
|
186 return profile_probability::guessed_always ().apply_scale (1, 2);
|
111
|
187 }
|
|
188 static profile_probability very_likely ()
|
|
189 {
|
|
190 return profile_probability::always () - very_unlikely ();
|
|
191 }
|
|
192 static profile_probability likely ()
|
|
193 {
|
|
194 return profile_probability::always () - unlikely ();
|
|
195 }
|
|
196 static profile_probability guessed_always ()
|
|
197 {
|
|
198 profile_probability ret;
|
|
199 ret.m_val = max_probability;
|
|
200 ret.m_quality = profile_guessed;
|
|
201 return ret;
|
|
202 }
|
|
203 static profile_probability always ()
|
|
204 {
|
|
205 profile_probability ret;
|
|
206 ret.m_val = max_probability;
|
|
207 ret.m_quality = profile_precise;
|
|
208 return ret;
|
|
209 }
|
|
210 /* Probabilities which has not been initialized. Either because
|
|
211 initialization did not happen yet or because profile is unknown. */
|
|
212 static profile_probability uninitialized ()
|
|
213 {
|
|
214 profile_probability c;
|
|
215 c.m_val = uninitialized_probability;
|
|
216 c.m_quality = profile_guessed;
|
|
217 return c;
|
|
218 }
|
|
219
|
|
220
|
|
221 /* Return true if value has been initialized. */
|
|
222 bool initialized_p () const
|
|
223 {
|
|
224 return m_val != uninitialized_probability;
|
|
225 }
|
|
226 /* Return true if value can be trusted. */
|
|
227 bool reliable_p () const
|
|
228 {
|
|
229 return m_quality >= profile_adjusted;
|
|
230 }
|
|
231
|
|
232 /* Conversion from and to REG_BR_PROB_BASE integer fixpoint arithmetics.
|
|
233 this is mostly to support legacy code and should go away. */
|
|
234 static profile_probability from_reg_br_prob_base (int v)
|
|
235 {
|
|
236 profile_probability ret;
|
|
237 gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE);
|
|
238 ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE);
|
|
239 ret.m_quality = profile_guessed;
|
|
240 return ret;
|
|
241 }
|
|
242 int to_reg_br_prob_base () const
|
|
243 {
|
|
244 gcc_checking_assert (initialized_p ());
|
|
245 return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability);
|
|
246 }
|
|
247
|
|
248 /* Conversion to and from RTL representation of profile probabilities. */
|
|
249 static profile_probability from_reg_br_prob_note (int v)
|
|
250 {
|
|
251 profile_probability ret;
|
131
|
252 ret.m_val = ((unsigned int)v) / 8;
|
|
253 ret.m_quality = (enum profile_quality)(v & 7);
|
111
|
254 return ret;
|
|
255 }
|
|
256 int to_reg_br_prob_note () const
|
|
257 {
|
|
258 gcc_checking_assert (initialized_p ());
|
131
|
259 int ret = m_val * 8 + m_quality;
|
111
|
260 gcc_checking_assert (profile_probability::from_reg_br_prob_note (ret)
|
|
261 == *this);
|
|
262 return ret;
|
|
263 }
|
|
264
|
|
265 /* Return VAL1/VAL2. */
|
|
266 static profile_probability probability_in_gcov_type
|
|
267 (gcov_type val1, gcov_type val2)
|
|
268 {
|
|
269 profile_probability ret;
|
|
270 gcc_checking_assert (val1 >= 0 && val2 > 0);
|
|
271 if (val1 > val2)
|
|
272 ret.m_val = max_probability;
|
|
273 else
|
|
274 {
|
|
275 uint64_t tmp;
|
|
276 safe_scale_64bit (val1, max_probability, val2, &tmp);
|
|
277 gcc_checking_assert (tmp <= max_probability);
|
|
278 ret.m_val = tmp;
|
|
279 }
|
|
280 ret.m_quality = profile_precise;
|
|
281 return ret;
|
|
282 }
|
|
283
|
|
284 /* Basic operations. */
|
|
285 bool operator== (const profile_probability &other) const
|
|
286 {
|
|
287 return m_val == other.m_val && m_quality == other.m_quality;
|
|
288 }
|
|
289 profile_probability operator+ (const profile_probability &other) const
|
|
290 {
|
|
291 if (other == profile_probability::never ())
|
|
292 return *this;
|
|
293 if (*this == profile_probability::never ())
|
|
294 return other;
|
|
295 if (!initialized_p () || !other.initialized_p ())
|
|
296 return profile_probability::uninitialized ();
|
|
297
|
|
298 profile_probability ret;
|
|
299 ret.m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability);
|
|
300 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
301 return ret;
|
|
302 }
|
|
303 profile_probability &operator+= (const profile_probability &other)
|
|
304 {
|
|
305 if (other == profile_probability::never ())
|
|
306 return *this;
|
|
307 if (*this == profile_probability::never ())
|
|
308 {
|
|
309 *this = other;
|
|
310 return *this;
|
|
311 }
|
|
312 if (!initialized_p () || !other.initialized_p ())
|
|
313 return *this = profile_probability::uninitialized ();
|
|
314 else
|
|
315 {
|
|
316 m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability);
|
|
317 m_quality = MIN (m_quality, other.m_quality);
|
|
318 }
|
|
319 return *this;
|
|
320 }
|
|
321 profile_probability operator- (const profile_probability &other) const
|
|
322 {
|
|
323 if (*this == profile_probability::never ()
|
|
324 || other == profile_probability::never ())
|
|
325 return *this;
|
|
326 if (!initialized_p () || !other.initialized_p ())
|
|
327 return profile_probability::uninitialized ();
|
|
328 profile_probability ret;
|
|
329 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
|
|
330 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
331 return ret;
|
|
332 }
|
|
333 profile_probability &operator-= (const profile_probability &other)
|
|
334 {
|
|
335 if (*this == profile_probability::never ()
|
|
336 || other == profile_probability::never ())
|
|
337 return *this;
|
|
338 if (!initialized_p () || !other.initialized_p ())
|
|
339 return *this = profile_probability::uninitialized ();
|
|
340 else
|
|
341 {
|
|
342 m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
|
|
343 m_quality = MIN (m_quality, other.m_quality);
|
|
344 }
|
|
345 return *this;
|
|
346 }
|
|
347 profile_probability operator* (const profile_probability &other) const
|
|
348 {
|
|
349 if (*this == profile_probability::never ()
|
|
350 || other == profile_probability::never ())
|
|
351 return profile_probability::never ();
|
|
352 if (!initialized_p () || !other.initialized_p ())
|
|
353 return profile_probability::uninitialized ();
|
|
354 profile_probability ret;
|
|
355 ret.m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability);
|
131
|
356 ret.m_quality = MIN (MIN (m_quality, other.m_quality), profile_adjusted);
|
111
|
357 return ret;
|
|
358 }
|
|
359 profile_probability &operator*= (const profile_probability &other)
|
|
360 {
|
|
361 if (*this == profile_probability::never ()
|
|
362 || other == profile_probability::never ())
|
|
363 return *this = profile_probability::never ();
|
|
364 if (!initialized_p () || !other.initialized_p ())
|
|
365 return *this = profile_probability::uninitialized ();
|
|
366 else
|
|
367 {
|
|
368 m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability);
|
131
|
369 m_quality = MIN (MIN (m_quality, other.m_quality), profile_adjusted);
|
111
|
370 }
|
|
371 return *this;
|
|
372 }
|
|
373 profile_probability operator/ (const profile_probability &other) const
|
|
374 {
|
|
375 if (*this == profile_probability::never ())
|
|
376 return profile_probability::never ();
|
|
377 if (!initialized_p () || !other.initialized_p ())
|
|
378 return profile_probability::uninitialized ();
|
|
379 profile_probability ret;
|
131
|
380 /* If we get probability above 1, mark it as unreliable and return 1. */
|
111
|
381 if (m_val >= other.m_val)
|
131
|
382 {
|
|
383 ret.m_val = max_probability;
|
|
384 ret.m_quality = MIN (MIN (m_quality, other.m_quality),
|
|
385 profile_guessed);
|
|
386 return ret;
|
|
387 }
|
111
|
388 else if (!m_val)
|
|
389 ret.m_val = 0;
|
|
390 else
|
|
391 {
|
|
392 gcc_checking_assert (other.m_val);
|
|
393 ret.m_val = MIN (RDIV ((uint64_t)m_val * max_probability,
|
|
394 other.m_val),
|
|
395 max_probability);
|
|
396 }
|
131
|
397 ret.m_quality = MIN (MIN (m_quality, other.m_quality), profile_adjusted);
|
111
|
398 return ret;
|
|
399 }
|
|
400 profile_probability &operator/= (const profile_probability &other)
|
|
401 {
|
|
402 if (*this == profile_probability::never ())
|
|
403 return *this = profile_probability::never ();
|
|
404 if (!initialized_p () || !other.initialized_p ())
|
|
405 return *this = profile_probability::uninitialized ();
|
|
406 else
|
|
407 {
|
131
|
408 /* If we get probability above 1, mark it as unreliable
|
|
409 and return 1. */
|
111
|
410 if (m_val > other.m_val)
|
131
|
411 {
|
|
412 m_val = max_probability;
|
|
413 m_quality = MIN (MIN (m_quality, other.m_quality),
|
|
414 profile_guessed);
|
|
415 return *this;
|
|
416 }
|
111
|
417 else if (!m_val)
|
|
418 ;
|
|
419 else
|
|
420 {
|
|
421 gcc_checking_assert (other.m_val);
|
|
422 m_val = MIN (RDIV ((uint64_t)m_val * max_probability,
|
|
423 other.m_val),
|
|
424 max_probability);
|
|
425 }
|
131
|
426 m_quality = MIN (MIN (m_quality, other.m_quality), profile_adjusted);
|
111
|
427 }
|
|
428 return *this;
|
|
429 }
|
|
430
|
131
|
431 /* Split *THIS (ORIG) probability into 2 probabilities, such that
|
|
432 the returned one (FIRST) is *THIS * CPROB and *THIS is
|
|
433 adjusted (SECOND) so that FIRST + FIRST.invert () * SECOND
|
|
434 == ORIG. This is useful e.g. when splitting a conditional
|
|
435 branch like:
|
|
436 if (cond)
|
|
437 goto lab; // ORIG probability
|
|
438 into
|
|
439 if (cond1)
|
|
440 goto lab; // FIRST = ORIG * CPROB probability
|
|
441 if (cond2)
|
|
442 goto lab; // SECOND probability
|
|
443 such that the overall probability of jumping to lab remains
|
|
444 the same. CPROB gives the relative probability between the
|
|
445 branches. */
|
|
446 profile_probability split (const profile_probability &cprob)
|
|
447 {
|
|
448 profile_probability ret = *this * cprob;
|
|
449 /* The following is equivalent to:
|
|
450 *this = cprob.invert () * *this / ret.invert (); */
|
|
451 *this = (*this - ret) / ret.invert ();
|
|
452 return ret;
|
|
453 }
|
|
454
|
111
|
455 gcov_type apply (gcov_type val) const
|
|
456 {
|
|
457 if (*this == profile_probability::uninitialized ())
|
|
458 return val / 2;
|
|
459 return RDIV (val * m_val, max_probability);
|
|
460 }
|
|
461
|
|
462 /* Return 1-*THIS. */
|
|
463 profile_probability invert () const
|
|
464 {
|
|
465 return profile_probability::always() - *this;
|
|
466 }
|
|
467
|
|
468 /* Return THIS with quality dropped to GUESSED. */
|
|
469 profile_probability guessed () const
|
|
470 {
|
|
471 profile_probability ret = *this;
|
|
472 ret.m_quality = profile_guessed;
|
|
473 return ret;
|
|
474 }
|
|
475
|
|
476 /* Return THIS with quality dropped to AFDO. */
|
|
477 profile_probability afdo () const
|
|
478 {
|
|
479 profile_probability ret = *this;
|
|
480 ret.m_quality = profile_afdo;
|
|
481 return ret;
|
|
482 }
|
|
483
|
|
484 /* Return *THIS * NUM / DEN. */
|
|
485 profile_probability apply_scale (int64_t num, int64_t den) const
|
|
486 {
|
|
487 if (*this == profile_probability::never ())
|
|
488 return *this;
|
|
489 if (!initialized_p ())
|
|
490 return profile_probability::uninitialized ();
|
|
491 profile_probability ret;
|
|
492 uint64_t tmp;
|
|
493 safe_scale_64bit (m_val, num, den, &tmp);
|
|
494 ret.m_val = MIN (tmp, max_probability);
|
|
495 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
496 return ret;
|
|
497 }
|
|
498
|
|
499 /* Return true when the probability of edge is reliable.
|
|
500
|
|
501 The profile guessing code is good at predicting branch outcome (ie.
|
|
502 taken/not taken), that is predicted right slightly over 75% of time.
|
|
503 It is however notoriously poor on predicting the probability itself.
|
|
504 In general the profile appear a lot flatter (with probabilities closer
|
|
505 to 50%) than the reality so it is bad idea to use it to drive optimization
|
|
506 such as those disabling dynamic branch prediction for well predictable
|
|
507 branches.
|
|
508
|
|
509 There are two exceptions - edges leading to noreturn edges and edges
|
|
510 predicted by number of iterations heuristics are predicted well. This macro
|
|
511 should be able to distinguish those, but at the moment it simply check for
|
|
512 noreturn heuristic that is only one giving probability over 99% or bellow
|
|
513 1%. In future we might want to propagate reliability information across the
|
|
514 CFG if we find this information useful on multiple places. */
|
|
515
|
|
516 bool probably_reliable_p () const
|
|
517 {
|
|
518 if (m_quality >= profile_adjusted)
|
|
519 return true;
|
|
520 if (!initialized_p ())
|
|
521 return false;
|
|
522 return m_val < max_probability / 100
|
|
523 || m_val > max_probability - max_probability / 100;
|
|
524 }
|
|
525
|
|
526 /* Return false if profile_probability is bogus. */
|
|
527 bool verify () const
|
|
528 {
|
131
|
529 gcc_checking_assert (m_quality != profile_uninitialized);
|
111
|
530 if (m_val == uninitialized_probability)
|
|
531 return m_quality == profile_guessed;
|
131
|
532 else if (m_quality < profile_guessed)
|
|
533 return false;
|
|
534 return m_val <= max_probability;
|
111
|
535 }
|
|
536
|
|
537 /* Comparsions are three-state and conservative. False is returned if
|
|
538 the inequality can not be decided. */
|
|
539 bool operator< (const profile_probability &other) const
|
|
540 {
|
|
541 return initialized_p () && other.initialized_p () && m_val < other.m_val;
|
|
542 }
|
|
543 bool operator> (const profile_probability &other) const
|
|
544 {
|
|
545 return initialized_p () && other.initialized_p () && m_val > other.m_val;
|
|
546 }
|
|
547
|
|
548 bool operator<= (const profile_probability &other) const
|
|
549 {
|
|
550 return initialized_p () && other.initialized_p () && m_val <= other.m_val;
|
|
551 }
|
|
552 bool operator>= (const profile_probability &other) const
|
|
553 {
|
|
554 return initialized_p () && other.initialized_p () && m_val >= other.m_val;
|
|
555 }
|
|
556
|
|
557 /* Output THIS to F. */
|
|
558 void dump (FILE *f) const;
|
|
559
|
|
560 /* Print THIS to stderr. */
|
|
561 void debug () const;
|
|
562
|
|
563 /* Return true if THIS is known to differ significantly from OTHER. */
|
|
564 bool differs_from_p (profile_probability other) const;
|
|
565 /* Return if difference is greater than 50%. */
|
|
566 bool differs_lot_from_p (profile_probability other) const;
|
131
|
567 /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
|
|
568 happens with COUNT2 probablity. Return probablity that either *THIS or
|
|
569 OTHER happens. */
|
|
570 profile_probability combine_with_count (profile_count count1,
|
|
571 profile_probability other,
|
|
572 profile_count count2) const;
|
111
|
573
|
|
574 /* LTO streaming support. */
|
|
575 static profile_probability stream_in (struct lto_input_block *);
|
|
576 void stream_out (struct output_block *);
|
|
577 void stream_out (struct lto_output_stream *);
|
|
578 };
|
|
579
|
131
|
580 /* Main data type to hold profile counters in GCC. Profile counts originate
|
|
581 either from profile feedback, static profile estimation or both. We do not
|
|
582 perform whole program profile propagation and thus profile estimation
|
|
583 counters are often local to function, while counters from profile feedback
|
|
584 (or special cases of profile estimation) can be used inter-procedurally.
|
|
585
|
|
586 There are 3 basic types
|
|
587 1) local counters which are result of intra-procedural static profile
|
|
588 estimation.
|
|
589 2) ipa counters which are result of profile feedback or special case
|
|
590 of static profile estimation (such as in function main).
|
|
591 3) counters which counts as 0 inter-procedurally (beause given function
|
|
592 was never run in train feedback) but they hold local static profile
|
|
593 estimate.
|
|
594
|
|
595 Counters of type 1 and 3 can not be mixed with counters of different type
|
|
596 within operation (because whole function should use one type of counter)
|
|
597 with exception that global zero mix in most operations where outcome is
|
|
598 well defined.
|
|
599
|
|
600 To take local counter and use it inter-procedurally use ipa member function
|
|
601 which strips information irelevant at the inter-procedural level.
|
|
602
|
|
603 Counters are 61bit integers representing number of executions during the
|
|
604 train run or normalized frequency within the function.
|
|
605
|
111
|
606 As the profile is maintained during the compilation, many adjustments are
|
|
607 made. Not all transformations can be made precisely, most importantly
|
|
608 when code is being duplicated. It also may happen that part of CFG has
|
|
609 profile counts known while other do not - for example when LTO optimizing
|
|
610 partly profiled program or when profile was lost due to COMDAT merging.
|
|
611
|
|
612 For this reason profile_count tracks more information than
|
|
613 just unsigned integer and it is also ready for profile mismatches.
|
|
614 The API of this data type represent operations that are natural
|
|
615 on profile counts - sum, difference and operation with scales and
|
|
616 probabilities. All operations are safe by never getting negative counts
|
|
617 and they do end up in uninitialized scale if any of the parameters is
|
|
618 uninitialized.
|
|
619
|
|
620 All comparsions that are three state and handling of probabilities. Thus
|
|
621 a < b is not equal to !(a >= b).
|
|
622
|
|
623 The following pre-defined counts are available:
|
|
624
|
|
625 profile_count::zero () for code that is known to execute zero times at
|
|
626 runtime (this can be detected statically i.e. for paths leading to
|
|
627 abort ();
|
|
628 profile_count::one () for code that is known to execute once (such as
|
|
629 main () function
|
|
630 profile_count::uninitialized () for unknown execution count.
|
|
631
|
|
632 */
|
|
633
|
131
|
634 class sreal;
|
|
635
|
111
|
636 class GTY(()) profile_count
|
|
637 {
|
131
|
638 public:
|
111
|
639 /* Use 62bit to hold basic block counters. Should be at least
|
|
640 64bit. Although a counter cannot be negative, we use a signed
|
|
641 type to hold various extra stages. */
|
|
642
|
131
|
643 static const int n_bits = 61;
|
|
644 private:
|
111
|
645 static const uint64_t max_count = ((uint64_t) 1 << n_bits) - 2;
|
|
646 static const uint64_t uninitialized_count = ((uint64_t) 1 << n_bits) - 1;
|
|
647
|
|
648 uint64_t m_val : n_bits;
|
131
|
649 enum profile_quality m_quality : 3;
|
|
650
|
|
651 /* Return true if both values can meaningfully appear in single function
|
|
652 body. We have either all counters in function local or global, otherwise
|
|
653 operations between them are not really defined well. */
|
|
654 bool compatible_p (const profile_count other) const
|
|
655 {
|
|
656 if (!initialized_p () || !other.initialized_p ())
|
|
657 return true;
|
|
658 if (*this == profile_count::zero ()
|
|
659 || other == profile_count::zero ())
|
|
660 return true;
|
|
661 return ipa_p () == other.ipa_p ();
|
|
662 }
|
111
|
663 public:
|
|
664
|
|
665 /* Used for counters which are expected to be never executed. */
|
|
666 static profile_count zero ()
|
|
667 {
|
|
668 return from_gcov_type (0);
|
|
669 }
|
131
|
670 static profile_count adjusted_zero ()
|
|
671 {
|
|
672 profile_count c;
|
|
673 c.m_val = 0;
|
|
674 c.m_quality = profile_adjusted;
|
|
675 return c;
|
|
676 }
|
111
|
677 static profile_count guessed_zero ()
|
|
678 {
|
|
679 profile_count c;
|
|
680 c.m_val = 0;
|
|
681 c.m_quality = profile_guessed;
|
|
682 return c;
|
|
683 }
|
|
684 static profile_count one ()
|
|
685 {
|
|
686 return from_gcov_type (1);
|
|
687 }
|
|
688 /* Value of counters which has not been initialized. Either because
|
|
689 initialization did not happen yet or because profile is unknown. */
|
|
690 static profile_count uninitialized ()
|
|
691 {
|
|
692 profile_count c;
|
|
693 c.m_val = uninitialized_count;
|
131
|
694 c.m_quality = profile_guessed_local;
|
111
|
695 return c;
|
|
696 }
|
|
697
|
|
698 /* Conversion to gcov_type is lossy. */
|
|
699 gcov_type to_gcov_type () const
|
|
700 {
|
|
701 gcc_checking_assert (initialized_p ());
|
|
702 return m_val;
|
|
703 }
|
|
704
|
|
705 /* Return true if value has been initialized. */
|
|
706 bool initialized_p () const
|
|
707 {
|
|
708 return m_val != uninitialized_count;
|
|
709 }
|
|
710 /* Return true if value can be trusted. */
|
|
711 bool reliable_p () const
|
|
712 {
|
|
713 return m_quality >= profile_adjusted;
|
|
714 }
|
131
|
715 /* Return true if vlaue can be operated inter-procedurally. */
|
|
716 bool ipa_p () const
|
|
717 {
|
|
718 return !initialized_p () || m_quality >= profile_guessed_global0;
|
|
719 }
|
|
720 /* Return true if quality of profile is precise. */
|
|
721 bool precise_p () const
|
|
722 {
|
|
723 return m_quality == profile_precise;
|
|
724 }
|
|
725
|
|
726 /* Get the quality of the count. */
|
|
727 enum profile_quality quality () const { return m_quality; }
|
111
|
728
|
|
729 /* When merging basic blocks, the two different profile counts are unified.
|
|
730 Return true if this can be done without losing info about profile.
|
|
731 The only case we care about here is when first BB contains something
|
|
732 that makes it terminate in a way not visible in CFG. */
|
|
733 bool ok_for_merging (profile_count other) const
|
|
734 {
|
|
735 if (m_quality < profile_adjusted
|
|
736 || other.m_quality < profile_adjusted)
|
|
737 return true;
|
|
738 return !(other < *this);
|
|
739 }
|
|
740
|
|
741 /* When merging two BBs with different counts, pick common count that looks
|
|
742 most representative. */
|
|
743 profile_count merge (profile_count other) const
|
|
744 {
|
|
745 if (*this == other || !other.initialized_p ()
|
|
746 || m_quality > other.m_quality)
|
|
747 return *this;
|
|
748 if (other.m_quality > m_quality
|
|
749 || other > *this)
|
|
750 return other;
|
|
751 return *this;
|
|
752 }
|
|
753
|
|
754 /* Basic operations. */
|
|
755 bool operator== (const profile_count &other) const
|
|
756 {
|
|
757 return m_val == other.m_val && m_quality == other.m_quality;
|
|
758 }
|
|
759 profile_count operator+ (const profile_count &other) const
|
|
760 {
|
|
761 if (other == profile_count::zero ())
|
|
762 return *this;
|
|
763 if (*this == profile_count::zero ())
|
|
764 return other;
|
|
765 if (!initialized_p () || !other.initialized_p ())
|
|
766 return profile_count::uninitialized ();
|
|
767
|
|
768 profile_count ret;
|
131
|
769 gcc_checking_assert (compatible_p (other));
|
111
|
770 ret.m_val = m_val + other.m_val;
|
|
771 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
772 return ret;
|
|
773 }
|
|
774 profile_count &operator+= (const profile_count &other)
|
|
775 {
|
|
776 if (other == profile_count::zero ())
|
|
777 return *this;
|
|
778 if (*this == profile_count::zero ())
|
|
779 {
|
|
780 *this = other;
|
|
781 return *this;
|
|
782 }
|
|
783 if (!initialized_p () || !other.initialized_p ())
|
|
784 return *this = profile_count::uninitialized ();
|
|
785 else
|
|
786 {
|
131
|
787 gcc_checking_assert (compatible_p (other));
|
111
|
788 m_val += other.m_val;
|
|
789 m_quality = MIN (m_quality, other.m_quality);
|
|
790 }
|
|
791 return *this;
|
|
792 }
|
|
793 profile_count operator- (const profile_count &other) const
|
|
794 {
|
|
795 if (*this == profile_count::zero () || other == profile_count::zero ())
|
|
796 return *this;
|
|
797 if (!initialized_p () || !other.initialized_p ())
|
|
798 return profile_count::uninitialized ();
|
131
|
799 gcc_checking_assert (compatible_p (other));
|
111
|
800 profile_count ret;
|
|
801 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
|
|
802 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
803 return ret;
|
|
804 }
|
|
805 profile_count &operator-= (const profile_count &other)
|
|
806 {
|
|
807 if (*this == profile_count::zero () || other == profile_count::zero ())
|
|
808 return *this;
|
|
809 if (!initialized_p () || !other.initialized_p ())
|
|
810 return *this = profile_count::uninitialized ();
|
|
811 else
|
|
812 {
|
131
|
813 gcc_checking_assert (compatible_p (other));
|
111
|
814 m_val = m_val >= other.m_val ? m_val - other.m_val: 0;
|
|
815 m_quality = MIN (m_quality, other.m_quality);
|
|
816 }
|
|
817 return *this;
|
|
818 }
|
|
819
|
|
820 /* Return false if profile_count is bogus. */
|
|
821 bool verify () const
|
|
822 {
|
131
|
823 gcc_checking_assert (m_quality != profile_uninitialized);
|
|
824 return m_val != uninitialized_count || m_quality == profile_guessed_local;
|
111
|
825 }
|
|
826
|
|
827 /* Comparsions are three-state and conservative. False is returned if
|
|
828 the inequality can not be decided. */
|
|
829 bool operator< (const profile_count &other) const
|
|
830 {
|
131
|
831 if (!initialized_p () || !other.initialized_p ())
|
|
832 return false;
|
|
833 if (*this == profile_count::zero ())
|
|
834 return !(other == profile_count::zero ());
|
|
835 if (other == profile_count::zero ())
|
|
836 return false;
|
|
837 gcc_checking_assert (compatible_p (other));
|
|
838 return m_val < other.m_val;
|
111
|
839 }
|
|
840 bool operator> (const profile_count &other) const
|
|
841 {
|
131
|
842 if (!initialized_p () || !other.initialized_p ())
|
|
843 return false;
|
|
844 if (*this == profile_count::zero ())
|
|
845 return false;
|
|
846 if (other == profile_count::zero ())
|
|
847 return !(*this == profile_count::zero ());
|
|
848 gcc_checking_assert (compatible_p (other));
|
111
|
849 return initialized_p () && other.initialized_p () && m_val > other.m_val;
|
|
850 }
|
|
851 bool operator< (const gcov_type other) const
|
|
852 {
|
131
|
853 gcc_checking_assert (ipa_p ());
|
111
|
854 gcc_checking_assert (other >= 0);
|
|
855 return initialized_p () && m_val < (uint64_t) other;
|
|
856 }
|
|
857 bool operator> (const gcov_type other) const
|
|
858 {
|
131
|
859 gcc_checking_assert (ipa_p ());
|
111
|
860 gcc_checking_assert (other >= 0);
|
|
861 return initialized_p () && m_val > (uint64_t) other;
|
|
862 }
|
|
863
|
|
864 bool operator<= (const profile_count &other) const
|
|
865 {
|
131
|
866 if (!initialized_p () || !other.initialized_p ())
|
|
867 return false;
|
|
868 if (*this == profile_count::zero ())
|
|
869 return true;
|
|
870 if (other == profile_count::zero ())
|
|
871 return (*this == profile_count::zero ());
|
|
872 gcc_checking_assert (compatible_p (other));
|
|
873 return m_val <= other.m_val;
|
111
|
874 }
|
|
875 bool operator>= (const profile_count &other) const
|
|
876 {
|
131
|
877 if (!initialized_p () || !other.initialized_p ())
|
|
878 return false;
|
|
879 if (other == profile_count::zero ())
|
|
880 return true;
|
|
881 if (*this == profile_count::zero ())
|
|
882 return !(other == profile_count::zero ());
|
|
883 gcc_checking_assert (compatible_p (other));
|
|
884 return m_val >= other.m_val;
|
111
|
885 }
|
|
886 bool operator<= (const gcov_type other) const
|
|
887 {
|
131
|
888 gcc_checking_assert (ipa_p ());
|
111
|
889 gcc_checking_assert (other >= 0);
|
|
890 return initialized_p () && m_val <= (uint64_t) other;
|
|
891 }
|
|
892 bool operator>= (const gcov_type other) const
|
|
893 {
|
131
|
894 gcc_checking_assert (ipa_p ());
|
111
|
895 gcc_checking_assert (other >= 0);
|
|
896 return initialized_p () && m_val >= (uint64_t) other;
|
|
897 }
|
131
|
898 /* Return true when value is not zero and can be used for scaling.
|
|
899 This is different from *this > 0 because that requires counter to
|
|
900 be IPA. */
|
|
901 bool nonzero_p () const
|
|
902 {
|
|
903 return initialized_p () && m_val != 0;
|
|
904 }
|
|
905
|
|
906 /* Make counter forcingly nonzero. */
|
|
907 profile_count force_nonzero () const
|
|
908 {
|
|
909 if (!initialized_p ())
|
|
910 return *this;
|
|
911 profile_count ret = *this;
|
|
912 if (ret.m_val == 0)
|
|
913 {
|
|
914 ret.m_val = 1;
|
|
915 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
916 }
|
|
917 return ret;
|
|
918 }
|
|
919
|
|
920 profile_count max (profile_count other) const
|
|
921 {
|
|
922 if (!initialized_p ())
|
|
923 return other;
|
|
924 if (!other.initialized_p ())
|
|
925 return *this;
|
|
926 if (*this == profile_count::zero ())
|
|
927 return other;
|
|
928 if (other == profile_count::zero ())
|
|
929 return *this;
|
|
930 gcc_checking_assert (compatible_p (other));
|
|
931 if (m_val < other.m_val || (m_val == other.m_val
|
|
932 && m_quality < other.m_quality))
|
|
933 return other;
|
|
934 return *this;
|
|
935 }
|
111
|
936
|
|
937 /* PROB is a probability in scale 0...REG_BR_PROB_BASE. Scale counter
|
|
938 accordingly. */
|
|
939 profile_count apply_probability (int prob) const
|
|
940 {
|
|
941 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
|
|
942 if (m_val == 0)
|
|
943 return *this;
|
|
944 if (!initialized_p ())
|
|
945 return profile_count::uninitialized ();
|
|
946 profile_count ret;
|
|
947 ret.m_val = RDIV (m_val * prob, REG_BR_PROB_BASE);
|
|
948 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
949 return ret;
|
|
950 }
|
|
951
|
|
952 /* Scale counter according to PROB. */
|
|
953 profile_count apply_probability (profile_probability prob) const
|
|
954 {
|
|
955 if (*this == profile_count::zero ())
|
|
956 return *this;
|
|
957 if (prob == profile_probability::never ())
|
|
958 return profile_count::zero ();
|
|
959 if (!initialized_p ())
|
|
960 return profile_count::uninitialized ();
|
|
961 profile_count ret;
|
|
962 uint64_t tmp;
|
|
963 safe_scale_64bit (m_val, prob.m_val, profile_probability::max_probability,
|
|
964 &tmp);
|
|
965 ret.m_val = tmp;
|
|
966 ret.m_quality = MIN (m_quality, prob.m_quality);
|
|
967 return ret;
|
|
968 }
|
|
969 /* Return *THIS * NUM / DEN. */
|
|
970 profile_count apply_scale (int64_t num, int64_t den) const
|
|
971 {
|
|
972 if (m_val == 0)
|
|
973 return *this;
|
|
974 if (!initialized_p ())
|
|
975 return profile_count::uninitialized ();
|
|
976 profile_count ret;
|
|
977 uint64_t tmp;
|
|
978
|
|
979 gcc_checking_assert (num >= 0 && den > 0);
|
|
980 safe_scale_64bit (m_val, num, den, &tmp);
|
|
981 ret.m_val = MIN (tmp, max_count);
|
|
982 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
983 return ret;
|
|
984 }
|
|
985 profile_count apply_scale (profile_count num, profile_count den) const
|
|
986 {
|
131
|
987 if (*this == profile_count::zero ())
|
111
|
988 return *this;
|
131
|
989 if (num == profile_count::zero ())
|
111
|
990 return num;
|
|
991 if (!initialized_p () || !num.initialized_p () || !den.initialized_p ())
|
|
992 return profile_count::uninitialized ();
|
|
993 if (num == den)
|
|
994 return *this;
|
131
|
995 gcc_checking_assert (den.m_val);
|
111
|
996
|
|
997 profile_count ret;
|
|
998 uint64_t val;
|
|
999 safe_scale_64bit (m_val, num.m_val, den.m_val, &val);
|
|
1000 ret.m_val = MIN (val, max_count);
|
131
|
1001 ret.m_quality = MIN (MIN (MIN (m_quality, profile_adjusted),
|
|
1002 num.m_quality), den.m_quality);
|
|
1003 if (num.ipa_p () && !ret.ipa_p ())
|
|
1004 ret.m_quality = MIN (num.m_quality, profile_guessed);
|
|
1005 return ret;
|
|
1006 }
|
|
1007
|
|
1008 /* Return THIS with quality dropped to GUESSED_LOCAL. */
|
|
1009 profile_count guessed_local () const
|
|
1010 {
|
|
1011 profile_count ret = *this;
|
|
1012 if (!initialized_p ())
|
|
1013 return *this;
|
|
1014 ret.m_quality = profile_guessed_local;
|
|
1015 return ret;
|
|
1016 }
|
|
1017
|
|
1018 /* We know that profile is globally 0 but keep local profile if present. */
|
|
1019 profile_count global0 () const
|
|
1020 {
|
|
1021 profile_count ret = *this;
|
|
1022 if (!initialized_p ())
|
|
1023 return *this;
|
|
1024 ret.m_quality = profile_guessed_global0;
|
|
1025 return ret;
|
|
1026 }
|
|
1027
|
|
1028 /* We know that profile is globally adjusted 0 but keep local profile
|
|
1029 if present. */
|
|
1030 profile_count global0adjusted () const
|
|
1031 {
|
|
1032 profile_count ret = *this;
|
|
1033 if (!initialized_p ())
|
|
1034 return *this;
|
|
1035 ret.m_quality = profile_guessed_global0adjusted;
|
111
|
1036 return ret;
|
|
1037 }
|
|
1038
|
|
1039 /* Return THIS with quality dropped to GUESSED. */
|
|
1040 profile_count guessed () const
|
|
1041 {
|
|
1042 profile_count ret = *this;
|
131
|
1043 ret.m_quality = MIN (ret.m_quality, profile_guessed);
|
111
|
1044 return ret;
|
|
1045 }
|
|
1046
|
131
|
1047 /* Return variant of profile counte which is always safe to compare
|
|
1048 acorss functions. */
|
|
1049 profile_count ipa () const
|
|
1050 {
|
|
1051 if (m_quality > profile_guessed_global0adjusted)
|
|
1052 return *this;
|
|
1053 if (m_quality == profile_guessed_global0)
|
|
1054 return profile_count::zero ();
|
|
1055 if (m_quality == profile_guessed_global0adjusted)
|
|
1056 return profile_count::adjusted_zero ();
|
|
1057 return profile_count::uninitialized ();
|
|
1058 }
|
|
1059
|
111
|
1060 /* Return THIS with quality dropped to AFDO. */
|
|
1061 profile_count afdo () const
|
|
1062 {
|
|
1063 profile_count ret = *this;
|
|
1064 ret.m_quality = profile_afdo;
|
|
1065 return ret;
|
|
1066 }
|
|
1067
|
|
1068 /* Return probability of event with counter THIS within event with counter
|
|
1069 OVERALL. */
|
|
1070 profile_probability probability_in (const profile_count overall) const
|
|
1071 {
|
131
|
1072 if (*this == profile_count::zero ()
|
|
1073 && !(overall == profile_count::zero ()))
|
111
|
1074 return profile_probability::never ();
|
|
1075 if (!initialized_p () || !overall.initialized_p ()
|
|
1076 || !overall.m_val)
|
|
1077 return profile_probability::uninitialized ();
|
131
|
1078 if (*this == overall && m_quality == profile_precise)
|
|
1079 return profile_probability::always ();
|
111
|
1080 profile_probability ret;
|
131
|
1081 gcc_checking_assert (compatible_p (overall));
|
|
1082
|
|
1083 if (overall.m_val < m_val)
|
|
1084 {
|
|
1085 ret.m_val = profile_probability::max_probability;
|
|
1086 ret.m_quality = profile_guessed;
|
|
1087 return ret;
|
|
1088 }
|
111
|
1089 else
|
|
1090 ret.m_val = RDIV (m_val * profile_probability::max_probability,
|
|
1091 overall.m_val);
|
131
|
1092 ret.m_quality = MIN (MAX (MIN (m_quality, overall.m_quality),
|
|
1093 profile_guessed), profile_adjusted);
|
111
|
1094 return ret;
|
|
1095 }
|
|
1096
|
131
|
1097 int to_frequency (struct function *fun) const;
|
|
1098 int to_cgraph_frequency (profile_count entry_bb_count) const;
|
|
1099 sreal to_sreal_scale (profile_count in, bool *known = NULL) const;
|
|
1100
|
111
|
1101 /* Output THIS to F. */
|
|
1102 void dump (FILE *f) const;
|
|
1103
|
|
1104 /* Print THIS to stderr. */
|
|
1105 void debug () const;
|
|
1106
|
|
1107 /* Return true if THIS is known to differ significantly from OTHER. */
|
|
1108 bool differs_from_p (profile_count other) const;
|
|
1109
|
131
|
1110 /* We want to scale profile across function boundary from NUM to DEN.
|
|
1111 Take care of the side case when NUM and DEN are zeros of incompatible
|
|
1112 kinds. */
|
|
1113 static void adjust_for_ipa_scaling (profile_count *num, profile_count *den);
|
|
1114
|
|
1115 /* THIS is a count of bb which is known to be executed IPA times.
|
|
1116 Combine this information into bb counter. This means returning IPA
|
|
1117 if it is nonzero, not changing anything if IPA is uninitialized
|
|
1118 and if IPA is zero, turning THIS into corresponding local profile with
|
|
1119 global0. */
|
|
1120 profile_count combine_with_ipa_count (profile_count ipa);
|
|
1121
|
|
1122 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
|
|
1123 Conversions back and forth are used to read the coverage and get it
|
|
1124 into internal representation. */
|
|
1125 static profile_count from_gcov_type (gcov_type v);
|
|
1126
|
111
|
1127 /* LTO streaming support. */
|
|
1128 static profile_count stream_in (struct lto_input_block *);
|
|
1129 void stream_out (struct output_block *);
|
|
1130 void stream_out (struct lto_output_stream *);
|
|
1131 };
|
|
1132 #endif
|