|
111
|
1 /* Profile counter container type.
|
|
|
2 Copyright (C) 2017 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 #ifndef GCC_PROFILE_COUNT_H
|
|
|
22 #define GCC_PROFILE_COUNT_H
|
|
|
23
|
|
|
24 /* Quality of the profile count. Because gengtype does not support enums
|
|
|
25 inside of classes, this is in global namespace. */
|
|
|
26 enum profile_quality {
|
|
|
27 /* Profile is based on static branch prediction heuristics. It may or may
|
|
|
28 not reflect the reality. */
|
|
|
29 profile_guessed = 0,
|
|
|
30 /* Profile was determined by autofdo. */
|
|
|
31 profile_afdo = 1,
|
|
|
32 /* Profile was originally based on feedback but it was adjusted
|
|
|
33 by code duplicating optimization. It may not precisely reflect the
|
|
|
34 particular code path. */
|
|
|
35 profile_adjusted = 2,
|
|
|
36 /* Profile was read from profile feedback or determined by accurate static
|
|
|
37 method. */
|
|
|
38 profile_precise = 3
|
|
|
39 };
|
|
|
40
|
|
|
41 /* The base value for branch probability notes and edge probabilities. */
|
|
|
42 #define REG_BR_PROB_BASE 10000
|
|
|
43
|
|
|
44 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
|
|
|
45
|
|
|
46 bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res);
|
|
|
47
|
|
|
48 /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
|
|
|
49
|
|
|
50 inline bool
|
|
|
51 safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
|
|
|
52 {
|
|
|
53 #if (GCC_VERSION >= 5000)
|
|
|
54 uint64_t tmp;
|
|
|
55 if (!__builtin_mul_overflow (a, b, &tmp)
|
|
|
56 && !__builtin_add_overflow (tmp, c/2, &tmp))
|
|
|
57 {
|
|
|
58 *res = tmp / c;
|
|
|
59 return true;
|
|
|
60 }
|
|
|
61 if (c == 1)
|
|
|
62 {
|
|
|
63 *res = (uint64_t) -1;
|
|
|
64 return false;
|
|
|
65 }
|
|
|
66 #else
|
|
|
67 if (a < ((uint64_t)1 << 31)
|
|
|
68 && b < ((uint64_t)1 << 31)
|
|
|
69 && c < ((uint64_t)1 << 31))
|
|
|
70 {
|
|
|
71 *res = (a * b + (c / 2)) / c;
|
|
|
72 return true;
|
|
|
73 }
|
|
|
74 #endif
|
|
|
75 return slow_safe_scale_64bit (a, b, c, res);
|
|
|
76 }
|
|
|
77
|
|
|
78 /* Data type to hold probabilities. It implements fixed point arithmetics
|
|
|
79 with capping so probability is always in range [0,1] and scaling requiring
|
|
|
80 values greater than 1 needs to be represented otherwise.
|
|
|
81
|
|
|
82 In addition to actual value the quality of profile is tracked and propagated
|
|
|
83 through all operations. Special value UNINITIALIZED is used for probabilities
|
|
|
84 that has not been determined yet (for example bacause of
|
|
|
85 -fno-guess-branch-probability)
|
|
|
86
|
|
|
87 Typically probabilities are derived from profile feedback (via
|
|
|
88 probability_in_gcov_type), autoFDO or guessed statically and then propagated
|
|
|
89 thorough the compilation.
|
|
|
90
|
|
|
91 Named probabilities are available:
|
|
|
92 - never (0 probability)
|
|
|
93 - guessed_never
|
|
|
94 - very_unlikely (1/2000 probability)
|
|
|
95 - unlikely (1/5 probablity)
|
|
|
96 - even (1/2 probability)
|
|
|
97 - likely (4/5 probability)
|
|
|
98 - very_likely (1999/2000 probability)
|
|
|
99 - guessed_always
|
|
|
100 - always
|
|
|
101
|
|
|
102 Named probabilities except for never/always are assumed to be statically
|
|
|
103 guessed and thus not necessarily accurate. The difference between never
|
|
|
104 and guessed_never is that the first one should be used only in case that
|
|
|
105 well behaving program will very likely not execute the "never" path.
|
|
|
106 For example if the path is going to abort () call or it exception handling.
|
|
|
107
|
|
|
108 Always and guessed_always probabilities are symmetric.
|
|
|
109
|
|
|
110 For legacy code we support conversion to/from REG_BR_PROB_BASE based fixpoint
|
|
|
111 integer arithmetics. Once the code is converted to branch probabilities,
|
|
|
112 these conversions will probably go away because they are lossy.
|
|
|
113 */
|
|
|
114
|
|
|
115 class GTY((user)) profile_probability
|
|
|
116 {
|
|
|
117 static const int n_bits = 30;
|
|
|
118 /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that
|
|
|
119 will lead to harder multiplication sequences. */
|
|
|
120 static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2);
|
|
|
121 static const uint32_t uninitialized_probability
|
|
|
122 = ((uint32_t) 1 << (n_bits - 1)) - 1;
|
|
|
123
|
|
|
124 uint32_t m_val : 30;
|
|
|
125 enum profile_quality m_quality : 2;
|
|
|
126
|
|
|
127 friend class profile_count;
|
|
|
128 public:
|
|
|
129
|
|
|
130 /* Named probabilities. */
|
|
|
131 static profile_probability never ()
|
|
|
132 {
|
|
|
133 profile_probability ret;
|
|
|
134 ret.m_val = 0;
|
|
|
135 ret.m_quality = profile_precise;
|
|
|
136 return ret;
|
|
|
137 }
|
|
|
138 static profile_probability guessed_never ()
|
|
|
139 {
|
|
|
140 profile_probability ret;
|
|
|
141 ret.m_val = 0;
|
|
|
142 ret.m_quality = profile_guessed;
|
|
|
143 return ret;
|
|
|
144 }
|
|
|
145 static profile_probability very_unlikely ()
|
|
|
146 {
|
|
|
147 /* Be consistent with PROB_VERY_UNLIKELY in predict.h. */
|
|
|
148 profile_probability r
|
|
|
149 = profile_probability::always ().apply_scale (1, 2000);
|
|
|
150 r.m_val--;
|
|
|
151 return r;
|
|
|
152 }
|
|
|
153 static profile_probability unlikely ()
|
|
|
154 {
|
|
|
155 /* Be consistent with PROB_VERY_LIKELY in predict.h. */
|
|
|
156 profile_probability r
|
|
|
157 = profile_probability::always ().apply_scale (1, 5);
|
|
|
158 r.m_val--;
|
|
|
159 return r;
|
|
|
160 }
|
|
|
161 static profile_probability even ()
|
|
|
162 {
|
|
|
163 return profile_probability::always ().apply_scale (1, 2);
|
|
|
164 }
|
|
|
165 static profile_probability very_likely ()
|
|
|
166 {
|
|
|
167 return profile_probability::always () - very_unlikely ();
|
|
|
168 }
|
|
|
169 static profile_probability likely ()
|
|
|
170 {
|
|
|
171 return profile_probability::always () - unlikely ();
|
|
|
172 }
|
|
|
173 static profile_probability guessed_always ()
|
|
|
174 {
|
|
|
175 profile_probability ret;
|
|
|
176 ret.m_val = max_probability;
|
|
|
177 ret.m_quality = profile_guessed;
|
|
|
178 return ret;
|
|
|
179 }
|
|
|
180 static profile_probability always ()
|
|
|
181 {
|
|
|
182 profile_probability ret;
|
|
|
183 ret.m_val = max_probability;
|
|
|
184 ret.m_quality = profile_precise;
|
|
|
185 return ret;
|
|
|
186 }
|
|
|
187 /* Probabilities which has not been initialized. Either because
|
|
|
188 initialization did not happen yet or because profile is unknown. */
|
|
|
189 static profile_probability uninitialized ()
|
|
|
190 {
|
|
|
191 profile_probability c;
|
|
|
192 c.m_val = uninitialized_probability;
|
|
|
193 c.m_quality = profile_guessed;
|
|
|
194 return c;
|
|
|
195 }
|
|
|
196
|
|
|
197
|
|
|
198 /* Return true if value has been initialized. */
|
|
|
199 bool initialized_p () const
|
|
|
200 {
|
|
|
201 return m_val != uninitialized_probability;
|
|
|
202 }
|
|
|
203 /* Return true if value can be trusted. */
|
|
|
204 bool reliable_p () const
|
|
|
205 {
|
|
|
206 return m_quality >= profile_adjusted;
|
|
|
207 }
|
|
|
208
|
|
|
209 /* Conversion from and to REG_BR_PROB_BASE integer fixpoint arithmetics.
|
|
|
210 this is mostly to support legacy code and should go away. */
|
|
|
211 static profile_probability from_reg_br_prob_base (int v)
|
|
|
212 {
|
|
|
213 profile_probability ret;
|
|
|
214 gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE);
|
|
|
215 ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE);
|
|
|
216 ret.m_quality = profile_guessed;
|
|
|
217 return ret;
|
|
|
218 }
|
|
|
219 int to_reg_br_prob_base () const
|
|
|
220 {
|
|
|
221 gcc_checking_assert (initialized_p ());
|
|
|
222 return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability);
|
|
|
223 }
|
|
|
224
|
|
|
225 /* Conversion to and from RTL representation of profile probabilities. */
|
|
|
226 static profile_probability from_reg_br_prob_note (int v)
|
|
|
227 {
|
|
|
228 profile_probability ret;
|
|
|
229 ret.m_val = ((unsigned int)v) / 4;
|
|
|
230 ret.m_quality = (enum profile_quality)(v & 3);
|
|
|
231 return ret;
|
|
|
232 }
|
|
|
233 int to_reg_br_prob_note () const
|
|
|
234 {
|
|
|
235 gcc_checking_assert (initialized_p ());
|
|
|
236 int ret = m_val * 4 + m_quality;
|
|
|
237 gcc_checking_assert (profile_probability::from_reg_br_prob_note (ret)
|
|
|
238 == *this);
|
|
|
239 return ret;
|
|
|
240 }
|
|
|
241
|
|
|
242 /* Return VAL1/VAL2. */
|
|
|
243 static profile_probability probability_in_gcov_type
|
|
|
244 (gcov_type val1, gcov_type val2)
|
|
|
245 {
|
|
|
246 profile_probability ret;
|
|
|
247 gcc_checking_assert (val1 >= 0 && val2 > 0);
|
|
|
248 if (val1 > val2)
|
|
|
249 ret.m_val = max_probability;
|
|
|
250 else
|
|
|
251 {
|
|
|
252 uint64_t tmp;
|
|
|
253 safe_scale_64bit (val1, max_probability, val2, &tmp);
|
|
|
254 gcc_checking_assert (tmp <= max_probability);
|
|
|
255 ret.m_val = tmp;
|
|
|
256 }
|
|
|
257 ret.m_quality = profile_precise;
|
|
|
258 return ret;
|
|
|
259 }
|
|
|
260
|
|
|
261 /* Basic operations. */
|
|
|
262 bool operator== (const profile_probability &other) const
|
|
|
263 {
|
|
|
264 return m_val == other.m_val && m_quality == other.m_quality;
|
|
|
265 }
|
|
|
266 profile_probability operator+ (const profile_probability &other) const
|
|
|
267 {
|
|
|
268 if (other == profile_probability::never ())
|
|
|
269 return *this;
|
|
|
270 if (*this == profile_probability::never ())
|
|
|
271 return other;
|
|
|
272 if (!initialized_p () || !other.initialized_p ())
|
|
|
273 return profile_probability::uninitialized ();
|
|
|
274
|
|
|
275 profile_probability ret;
|
|
|
276 ret.m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability);
|
|
|
277 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
278 return ret;
|
|
|
279 }
|
|
|
280 profile_probability &operator+= (const profile_probability &other)
|
|
|
281 {
|
|
|
282 if (other == profile_probability::never ())
|
|
|
283 return *this;
|
|
|
284 if (*this == profile_probability::never ())
|
|
|
285 {
|
|
|
286 *this = other;
|
|
|
287 return *this;
|
|
|
288 }
|
|
|
289 if (!initialized_p () || !other.initialized_p ())
|
|
|
290 return *this = profile_probability::uninitialized ();
|
|
|
291 else
|
|
|
292 {
|
|
|
293 m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability);
|
|
|
294 m_quality = MIN (m_quality, other.m_quality);
|
|
|
295 }
|
|
|
296 return *this;
|
|
|
297 }
|
|
|
298 profile_probability operator- (const profile_probability &other) const
|
|
|
299 {
|
|
|
300 if (*this == profile_probability::never ()
|
|
|
301 || other == profile_probability::never ())
|
|
|
302 return *this;
|
|
|
303 if (!initialized_p () || !other.initialized_p ())
|
|
|
304 return profile_probability::uninitialized ();
|
|
|
305 profile_probability ret;
|
|
|
306 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
|
|
|
307 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
308 return ret;
|
|
|
309 }
|
|
|
310 profile_probability &operator-= (const profile_probability &other)
|
|
|
311 {
|
|
|
312 if (*this == profile_probability::never ()
|
|
|
313 || other == profile_probability::never ())
|
|
|
314 return *this;
|
|
|
315 if (!initialized_p () || !other.initialized_p ())
|
|
|
316 return *this = profile_probability::uninitialized ();
|
|
|
317 else
|
|
|
318 {
|
|
|
319 m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
|
|
|
320 m_quality = MIN (m_quality, other.m_quality);
|
|
|
321 }
|
|
|
322 return *this;
|
|
|
323 }
|
|
|
324 profile_probability operator* (const profile_probability &other) const
|
|
|
325 {
|
|
|
326 if (*this == profile_probability::never ()
|
|
|
327 || other == profile_probability::never ())
|
|
|
328 return profile_probability::never ();
|
|
|
329 if (!initialized_p () || !other.initialized_p ())
|
|
|
330 return profile_probability::uninitialized ();
|
|
|
331 profile_probability ret;
|
|
|
332 ret.m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability);
|
|
|
333 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
334 return ret;
|
|
|
335 }
|
|
|
336 profile_probability &operator*= (const profile_probability &other)
|
|
|
337 {
|
|
|
338 if (*this == profile_probability::never ()
|
|
|
339 || other == profile_probability::never ())
|
|
|
340 return *this = profile_probability::never ();
|
|
|
341 if (!initialized_p () || !other.initialized_p ())
|
|
|
342 return *this = profile_probability::uninitialized ();
|
|
|
343 else
|
|
|
344 {
|
|
|
345 m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability);
|
|
|
346 m_quality = MIN (m_quality, other.m_quality);
|
|
|
347 }
|
|
|
348 return *this;
|
|
|
349 }
|
|
|
350 profile_probability operator/ (const profile_probability &other) const
|
|
|
351 {
|
|
|
352 if (*this == profile_probability::never ())
|
|
|
353 return profile_probability::never ();
|
|
|
354 if (!initialized_p () || !other.initialized_p ())
|
|
|
355 return profile_probability::uninitialized ();
|
|
|
356 profile_probability ret;
|
|
|
357 if (m_val >= other.m_val)
|
|
|
358 ret.m_val = max_probability;
|
|
|
359 else if (!m_val)
|
|
|
360 ret.m_val = 0;
|
|
|
361 else
|
|
|
362 {
|
|
|
363 gcc_checking_assert (other.m_val);
|
|
|
364 ret.m_val = MIN (RDIV ((uint64_t)m_val * max_probability,
|
|
|
365 other.m_val),
|
|
|
366 max_probability);
|
|
|
367 }
|
|
|
368 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
369 return ret;
|
|
|
370 }
|
|
|
371 profile_probability &operator/= (const profile_probability &other)
|
|
|
372 {
|
|
|
373 if (*this == profile_probability::never ())
|
|
|
374 return *this = profile_probability::never ();
|
|
|
375 if (!initialized_p () || !other.initialized_p ())
|
|
|
376 return *this = profile_probability::uninitialized ();
|
|
|
377 else
|
|
|
378 {
|
|
|
379 if (m_val > other.m_val)
|
|
|
380 m_val = max_probability;
|
|
|
381 else if (!m_val)
|
|
|
382 ;
|
|
|
383 else
|
|
|
384 {
|
|
|
385 gcc_checking_assert (other.m_val);
|
|
|
386 m_val = MIN (RDIV ((uint64_t)m_val * max_probability,
|
|
|
387 other.m_val),
|
|
|
388 max_probability);
|
|
|
389 }
|
|
|
390 m_quality = MIN (m_quality, other.m_quality);
|
|
|
391 }
|
|
|
392 return *this;
|
|
|
393 }
|
|
|
394
|
|
|
395 gcov_type apply (gcov_type val) const
|
|
|
396 {
|
|
|
397 if (*this == profile_probability::uninitialized ())
|
|
|
398 return val / 2;
|
|
|
399 return RDIV (val * m_val, max_probability);
|
|
|
400 }
|
|
|
401
|
|
|
402 /* Return 1-*THIS. */
|
|
|
403 profile_probability invert () const
|
|
|
404 {
|
|
|
405 return profile_probability::always() - *this;
|
|
|
406 }
|
|
|
407
|
|
|
408 /* Return THIS with quality dropped to GUESSED. */
|
|
|
409 profile_probability guessed () const
|
|
|
410 {
|
|
|
411 profile_probability ret = *this;
|
|
|
412 ret.m_quality = profile_guessed;
|
|
|
413 return ret;
|
|
|
414 }
|
|
|
415
|
|
|
416 /* Return THIS with quality dropped to AFDO. */
|
|
|
417 profile_probability afdo () const
|
|
|
418 {
|
|
|
419 profile_probability ret = *this;
|
|
|
420 ret.m_quality = profile_afdo;
|
|
|
421 return ret;
|
|
|
422 }
|
|
|
423
|
|
|
424 profile_probability combine_with_freq (int freq1, profile_probability other,
|
|
|
425 int freq2) const
|
|
|
426 {
|
|
|
427 profile_probability ret;
|
|
|
428
|
|
|
429 if (*this == profile_probability::uninitialized ()
|
|
|
430 || other == profile_probability::uninitialized ())
|
|
|
431 return profile_probability::uninitialized ();
|
|
|
432
|
|
|
433 gcc_checking_assert (freq1 >= 0 && freq2 >= 0);
|
|
|
434 if (!freq1 && !freq2)
|
|
|
435 {
|
|
|
436 ret.m_val = (m_val + other.m_val) / 2;
|
|
|
437 }
|
|
|
438 else
|
|
|
439 ret.m_val = RDIV (m_val * (uint64_t) freq1
|
|
|
440 + other.m_val * (uint64_t) freq2, freq1 + freq2);
|
|
|
441 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
442 return ret;
|
|
|
443 }
|
|
|
444
|
|
|
445 /* Return *THIS * NUM / DEN. */
|
|
|
446 profile_probability apply_scale (int64_t num, int64_t den) const
|
|
|
447 {
|
|
|
448 if (*this == profile_probability::never ())
|
|
|
449 return *this;
|
|
|
450 if (!initialized_p ())
|
|
|
451 return profile_probability::uninitialized ();
|
|
|
452 profile_probability ret;
|
|
|
453 uint64_t tmp;
|
|
|
454 safe_scale_64bit (m_val, num, den, &tmp);
|
|
|
455 ret.m_val = MIN (tmp, max_probability);
|
|
|
456 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
|
457 return ret;
|
|
|
458 }
|
|
|
459
|
|
|
460 /* Return true when the probability of edge is reliable.
|
|
|
461
|
|
|
462 The profile guessing code is good at predicting branch outcome (ie.
|
|
|
463 taken/not taken), that is predicted right slightly over 75% of time.
|
|
|
464 It is however notoriously poor on predicting the probability itself.
|
|
|
465 In general the profile appear a lot flatter (with probabilities closer
|
|
|
466 to 50%) than the reality so it is bad idea to use it to drive optimization
|
|
|
467 such as those disabling dynamic branch prediction for well predictable
|
|
|
468 branches.
|
|
|
469
|
|
|
470 There are two exceptions - edges leading to noreturn edges and edges
|
|
|
471 predicted by number of iterations heuristics are predicted well. This macro
|
|
|
472 should be able to distinguish those, but at the moment it simply check for
|
|
|
473 noreturn heuristic that is only one giving probability over 99% or bellow
|
|
|
474 1%. In future we might want to propagate reliability information across the
|
|
|
475 CFG if we find this information useful on multiple places. */
|
|
|
476
|
|
|
477 bool probably_reliable_p () const
|
|
|
478 {
|
|
|
479 if (m_quality >= profile_adjusted)
|
|
|
480 return true;
|
|
|
481 if (!initialized_p ())
|
|
|
482 return false;
|
|
|
483 return m_val < max_probability / 100
|
|
|
484 || m_val > max_probability - max_probability / 100;
|
|
|
485 }
|
|
|
486
|
|
|
487 /* Return false if profile_probability is bogus. */
|
|
|
488 bool verify () const
|
|
|
489 {
|
|
|
490 if (m_val == uninitialized_probability)
|
|
|
491 return m_quality == profile_guessed;
|
|
|
492 else
|
|
|
493 return m_val <= max_probability;
|
|
|
494 }
|
|
|
495
|
|
|
496 /* Comparsions are three-state and conservative. False is returned if
|
|
|
497 the inequality can not be decided. */
|
|
|
498 bool operator< (const profile_probability &other) const
|
|
|
499 {
|
|
|
500 return initialized_p () && other.initialized_p () && m_val < other.m_val;
|
|
|
501 }
|
|
|
502 bool operator> (const profile_probability &other) const
|
|
|
503 {
|
|
|
504 return initialized_p () && other.initialized_p () && m_val > other.m_val;
|
|
|
505 }
|
|
|
506
|
|
|
507 bool operator<= (const profile_probability &other) const
|
|
|
508 {
|
|
|
509 return initialized_p () && other.initialized_p () && m_val <= other.m_val;
|
|
|
510 }
|
|
|
511 bool operator>= (const profile_probability &other) const
|
|
|
512 {
|
|
|
513 return initialized_p () && other.initialized_p () && m_val >= other.m_val;
|
|
|
514 }
|
|
|
515
|
|
|
516 /* Output THIS to F. */
|
|
|
517 void dump (FILE *f) const;
|
|
|
518
|
|
|
519 /* Print THIS to stderr. */
|
|
|
520 void debug () const;
|
|
|
521
|
|
|
522 /* Return true if THIS is known to differ significantly from OTHER. */
|
|
|
523 bool differs_from_p (profile_probability other) const;
|
|
|
524 /* Return if difference is greater than 50%. */
|
|
|
525 bool differs_lot_from_p (profile_probability other) const;
|
|
|
526
|
|
|
527 /* LTO streaming support. */
|
|
|
528 static profile_probability stream_in (struct lto_input_block *);
|
|
|
529 void stream_out (struct output_block *);
|
|
|
530 void stream_out (struct lto_output_stream *);
|
|
|
531 };
|
|
|
532
|
|
|
533 /* Main data type to hold profile counters in GCC. In most cases profile
|
|
|
534 counts originate from profile feedback. They are 64bit integers
|
|
|
535 representing number of executions during the train run.
|
|
|
536 As the profile is maintained during the compilation, many adjustments are
|
|
|
537 made. Not all transformations can be made precisely, most importantly
|
|
|
538 when code is being duplicated. It also may happen that part of CFG has
|
|
|
539 profile counts known while other do not - for example when LTO optimizing
|
|
|
540 partly profiled program or when profile was lost due to COMDAT merging.
|
|
|
541
|
|
|
542 For this reason profile_count tracks more information than
|
|
|
543 just unsigned integer and it is also ready for profile mismatches.
|
|
|
544 The API of this data type represent operations that are natural
|
|
|
545 on profile counts - sum, difference and operation with scales and
|
|
|
546 probabilities. All operations are safe by never getting negative counts
|
|
|
547 and they do end up in uninitialized scale if any of the parameters is
|
|
|
548 uninitialized.
|
|
|
549
|
|
|
550 All comparsions that are three state and handling of probabilities. Thus
|
|
|
551 a < b is not equal to !(a >= b).
|
|
|
552
|
|
|
553 The following pre-defined counts are available:
|
|
|
554
|
|
|
555 profile_count::zero () for code that is known to execute zero times at
|
|
|
556 runtime (this can be detected statically i.e. for paths leading to
|
|
|
557 abort ();
|
|
|
558 profile_count::one () for code that is known to execute once (such as
|
|
|
559 main () function
|
|
|
560 profile_count::uninitialized () for unknown execution count.
|
|
|
561
|
|
|
562 */
|
|
|
563
|
|
|
564 class GTY(()) profile_count
|
|
|
565 {
|
|
|
566 /* Use 62bit to hold basic block counters. Should be at least
|
|
|
567 64bit. Although a counter cannot be negative, we use a signed
|
|
|
568 type to hold various extra stages. */
|
|
|
569
|
|
|
570 static const int n_bits = 62;
|
|
|
571 static const uint64_t max_count = ((uint64_t) 1 << n_bits) - 2;
|
|
|
572 static const uint64_t uninitialized_count = ((uint64_t) 1 << n_bits) - 1;
|
|
|
573
|
|
|
574 uint64_t m_val : n_bits;
|
|
|
575 enum profile_quality m_quality : 2;
|
|
|
576 public:
|
|
|
577
|
|
|
578 /* Used for counters which are expected to be never executed. */
|
|
|
579 static profile_count zero ()
|
|
|
580 {
|
|
|
581 return from_gcov_type (0);
|
|
|
582 }
|
|
|
583 static profile_count guessed_zero ()
|
|
|
584 {
|
|
|
585 profile_count c;
|
|
|
586 c.m_val = 0;
|
|
|
587 c.m_quality = profile_guessed;
|
|
|
588 return c;
|
|
|
589 }
|
|
|
590 static profile_count one ()
|
|
|
591 {
|
|
|
592 return from_gcov_type (1);
|
|
|
593 }
|
|
|
594 /* Value of counters which has not been initialized. Either because
|
|
|
595 initialization did not happen yet or because profile is unknown. */
|
|
|
596 static profile_count uninitialized ()
|
|
|
597 {
|
|
|
598 profile_count c;
|
|
|
599 c.m_val = uninitialized_count;
|
|
|
600 c.m_quality = profile_guessed;
|
|
|
601 return c;
|
|
|
602 }
|
|
|
603
|
|
|
604 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
|
|
|
605 Conversions back and forth are used to read the coverage and get it
|
|
|
606 into internal representation. */
|
|
|
607 static profile_count from_gcov_type (gcov_type v)
|
|
|
608 {
|
|
|
609 profile_count ret;
|
|
|
610 gcc_checking_assert (v >= 0 && (uint64_t) v <= max_count);
|
|
|
611 ret.m_val = v;
|
|
|
612 ret.m_quality = profile_precise;
|
|
|
613 return ret;
|
|
|
614 }
|
|
|
615
|
|
|
616 /* Conversion to gcov_type is lossy. */
|
|
|
617 gcov_type to_gcov_type () const
|
|
|
618 {
|
|
|
619 gcc_checking_assert (initialized_p ());
|
|
|
620 return m_val;
|
|
|
621 }
|
|
|
622
|
|
|
623 /* Return true if value has been initialized. */
|
|
|
624 bool initialized_p () const
|
|
|
625 {
|
|
|
626 return m_val != uninitialized_count;
|
|
|
627 }
|
|
|
628 /* Return true if value can be trusted. */
|
|
|
629 bool reliable_p () const
|
|
|
630 {
|
|
|
631 return m_quality >= profile_adjusted;
|
|
|
632 }
|
|
|
633
|
|
|
634 /* When merging basic blocks, the two different profile counts are unified.
|
|
|
635 Return true if this can be done without losing info about profile.
|
|
|
636 The only case we care about here is when first BB contains something
|
|
|
637 that makes it terminate in a way not visible in CFG. */
|
|
|
638 bool ok_for_merging (profile_count other) const
|
|
|
639 {
|
|
|
640 if (m_quality < profile_adjusted
|
|
|
641 || other.m_quality < profile_adjusted)
|
|
|
642 return true;
|
|
|
643 return !(other < *this);
|
|
|
644 }
|
|
|
645
|
|
|
646 /* When merging two BBs with different counts, pick common count that looks
|
|
|
647 most representative. */
|
|
|
648 profile_count merge (profile_count other) const
|
|
|
649 {
|
|
|
650 if (*this == other || !other.initialized_p ()
|
|
|
651 || m_quality > other.m_quality)
|
|
|
652 return *this;
|
|
|
653 if (other.m_quality > m_quality
|
|
|
654 || other > *this)
|
|
|
655 return other;
|
|
|
656 return *this;
|
|
|
657 }
|
|
|
658
|
|
|
659 /* Basic operations. */
|
|
|
660 bool operator== (const profile_count &other) const
|
|
|
661 {
|
|
|
662 return m_val == other.m_val && m_quality == other.m_quality;
|
|
|
663 }
|
|
|
664 profile_count operator+ (const profile_count &other) const
|
|
|
665 {
|
|
|
666 if (other == profile_count::zero ())
|
|
|
667 return *this;
|
|
|
668 if (*this == profile_count::zero ())
|
|
|
669 return other;
|
|
|
670 if (!initialized_p () || !other.initialized_p ())
|
|
|
671 return profile_count::uninitialized ();
|
|
|
672
|
|
|
673 profile_count ret;
|
|
|
674 ret.m_val = m_val + other.m_val;
|
|
|
675 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
676 return ret;
|
|
|
677 }
|
|
|
678 profile_count &operator+= (const profile_count &other)
|
|
|
679 {
|
|
|
680 if (other == profile_count::zero ())
|
|
|
681 return *this;
|
|
|
682 if (*this == profile_count::zero ())
|
|
|
683 {
|
|
|
684 *this = other;
|
|
|
685 return *this;
|
|
|
686 }
|
|
|
687 if (!initialized_p () || !other.initialized_p ())
|
|
|
688 return *this = profile_count::uninitialized ();
|
|
|
689 else
|
|
|
690 {
|
|
|
691 m_val += other.m_val;
|
|
|
692 m_quality = MIN (m_quality, other.m_quality);
|
|
|
693 }
|
|
|
694 return *this;
|
|
|
695 }
|
|
|
696 profile_count operator- (const profile_count &other) const
|
|
|
697 {
|
|
|
698 if (*this == profile_count::zero () || other == profile_count::zero ())
|
|
|
699 return *this;
|
|
|
700 if (!initialized_p () || !other.initialized_p ())
|
|
|
701 return profile_count::uninitialized ();
|
|
|
702 profile_count ret;
|
|
|
703 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
|
|
|
704 ret.m_quality = MIN (m_quality, other.m_quality);
|
|
|
705 return ret;
|
|
|
706 }
|
|
|
707 profile_count &operator-= (const profile_count &other)
|
|
|
708 {
|
|
|
709 if (*this == profile_count::zero () || other == profile_count::zero ())
|
|
|
710 return *this;
|
|
|
711 if (!initialized_p () || !other.initialized_p ())
|
|
|
712 return *this = profile_count::uninitialized ();
|
|
|
713 else
|
|
|
714 {
|
|
|
715 m_val = m_val >= other.m_val ? m_val - other.m_val: 0;
|
|
|
716 m_quality = MIN (m_quality, other.m_quality);
|
|
|
717 }
|
|
|
718 return *this;
|
|
|
719 }
|
|
|
720
|
|
|
721 /* Return false if profile_count is bogus. */
|
|
|
722 bool verify () const
|
|
|
723 {
|
|
|
724 return m_val != uninitialized_count || m_quality == profile_guessed;
|
|
|
725 }
|
|
|
726
|
|
|
727 /* Comparsions are three-state and conservative. False is returned if
|
|
|
728 the inequality can not be decided. */
|
|
|
729 bool operator< (const profile_count &other) const
|
|
|
730 {
|
|
|
731 return initialized_p () && other.initialized_p () && m_val < other.m_val;
|
|
|
732 }
|
|
|
733 bool operator> (const profile_count &other) const
|
|
|
734 {
|
|
|
735 return initialized_p () && other.initialized_p () && m_val > other.m_val;
|
|
|
736 }
|
|
|
737 bool operator< (const gcov_type other) const
|
|
|
738 {
|
|
|
739 gcc_checking_assert (other >= 0);
|
|
|
740 return initialized_p () && m_val < (uint64_t) other;
|
|
|
741 }
|
|
|
742 bool operator> (const gcov_type other) const
|
|
|
743 {
|
|
|
744 gcc_checking_assert (other >= 0);
|
|
|
745 return initialized_p () && m_val > (uint64_t) other;
|
|
|
746 }
|
|
|
747
|
|
|
748 bool operator<= (const profile_count &other) const
|
|
|
749 {
|
|
|
750 return initialized_p () && other.initialized_p () && m_val <= other.m_val;
|
|
|
751 }
|
|
|
752 bool operator>= (const profile_count &other) const
|
|
|
753 {
|
|
|
754 return initialized_p () && other.initialized_p () && m_val >= other.m_val;
|
|
|
755 }
|
|
|
756 bool operator<= (const gcov_type other) const
|
|
|
757 {
|
|
|
758 gcc_checking_assert (other >= 0);
|
|
|
759 return initialized_p () && m_val <= (uint64_t) other;
|
|
|
760 }
|
|
|
761 bool operator>= (const gcov_type other) const
|
|
|
762 {
|
|
|
763 gcc_checking_assert (other >= 0);
|
|
|
764 return initialized_p () && m_val >= (uint64_t) other;
|
|
|
765 }
|
|
|
766
|
|
|
767 /* PROB is a probability in scale 0...REG_BR_PROB_BASE. Scale counter
|
|
|
768 accordingly. */
|
|
|
769 profile_count apply_probability (int prob) const
|
|
|
770 {
|
|
|
771 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
|
|
|
772 if (m_val == 0)
|
|
|
773 return *this;
|
|
|
774 if (!initialized_p ())
|
|
|
775 return profile_count::uninitialized ();
|
|
|
776 profile_count ret;
|
|
|
777 ret.m_val = RDIV (m_val * prob, REG_BR_PROB_BASE);
|
|
|
778 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
|
779 return ret;
|
|
|
780 }
|
|
|
781
|
|
|
782 /* Scale counter according to PROB. */
|
|
|
783 profile_count apply_probability (profile_probability prob) const
|
|
|
784 {
|
|
|
785 if (*this == profile_count::zero ())
|
|
|
786 return *this;
|
|
|
787 if (prob == profile_probability::never ())
|
|
|
788 return profile_count::zero ();
|
|
|
789 if (!initialized_p ())
|
|
|
790 return profile_count::uninitialized ();
|
|
|
791 profile_count ret;
|
|
|
792 uint64_t tmp;
|
|
|
793 safe_scale_64bit (m_val, prob.m_val, profile_probability::max_probability,
|
|
|
794 &tmp);
|
|
|
795 ret.m_val = tmp;
|
|
|
796 ret.m_quality = MIN (m_quality, prob.m_quality);
|
|
|
797 return ret;
|
|
|
798 }
|
|
|
799 /* Return *THIS * NUM / DEN. */
|
|
|
800 profile_count apply_scale (int64_t num, int64_t den) const
|
|
|
801 {
|
|
|
802 if (m_val == 0)
|
|
|
803 return *this;
|
|
|
804 if (!initialized_p ())
|
|
|
805 return profile_count::uninitialized ();
|
|
|
806 profile_count ret;
|
|
|
807 uint64_t tmp;
|
|
|
808
|
|
|
809 gcc_checking_assert (num >= 0 && den > 0);
|
|
|
810 safe_scale_64bit (m_val, num, den, &tmp);
|
|
|
811 ret.m_val = MIN (tmp, max_count);
|
|
|
812 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
|
813 return ret;
|
|
|
814 }
|
|
|
815 profile_count apply_scale (profile_count num, profile_count den) const
|
|
|
816 {
|
|
|
817 if (m_val == 0)
|
|
|
818 return *this;
|
|
|
819 if (num.m_val == 0)
|
|
|
820 return num;
|
|
|
821 if (!initialized_p () || !num.initialized_p () || !den.initialized_p ())
|
|
|
822 return profile_count::uninitialized ();
|
|
|
823 gcc_checking_assert (den > 0);
|
|
|
824 if (num == den)
|
|
|
825 return *this;
|
|
|
826
|
|
|
827 profile_count ret;
|
|
|
828 uint64_t val;
|
|
|
829 safe_scale_64bit (m_val, num.m_val, den.m_val, &val);
|
|
|
830 ret.m_val = MIN (val, max_count);
|
|
|
831 ret.m_quality = MIN (m_quality, profile_adjusted);
|
|
|
832 return ret;
|
|
|
833 }
|
|
|
834
|
|
|
835 /* Return THIS with quality dropped to GUESSED. */
|
|
|
836 profile_count guessed () const
|
|
|
837 {
|
|
|
838 profile_count ret = *this;
|
|
|
839 ret.m_quality = profile_guessed;
|
|
|
840 return ret;
|
|
|
841 }
|
|
|
842
|
|
|
843 /* Return THIS with quality dropped to AFDO. */
|
|
|
844 profile_count afdo () const
|
|
|
845 {
|
|
|
846 profile_count ret = *this;
|
|
|
847 ret.m_quality = profile_afdo;
|
|
|
848 return ret;
|
|
|
849 }
|
|
|
850
|
|
|
851 /* Return probability of event with counter THIS within event with counter
|
|
|
852 OVERALL. */
|
|
|
853 profile_probability probability_in (const profile_count overall) const
|
|
|
854 {
|
|
|
855 if (!m_val)
|
|
|
856 return profile_probability::never ();
|
|
|
857 if (!initialized_p () || !overall.initialized_p ()
|
|
|
858 || !overall.m_val)
|
|
|
859 return profile_probability::uninitialized ();
|
|
|
860 profile_probability ret;
|
|
|
861 if (overall < m_val)
|
|
|
862 ret.m_val = profile_probability::max_probability;
|
|
|
863 else
|
|
|
864 ret.m_val = RDIV (m_val * profile_probability::max_probability,
|
|
|
865 overall.m_val);
|
|
|
866 ret.m_quality = MIN (m_quality, overall.m_quality);
|
|
|
867 return ret;
|
|
|
868 }
|
|
|
869
|
|
|
870 /* Output THIS to F. */
|
|
|
871 void dump (FILE *f) const;
|
|
|
872
|
|
|
873 /* Print THIS to stderr. */
|
|
|
874 void debug () const;
|
|
|
875
|
|
|
876 /* Return true if THIS is known to differ significantly from OTHER. */
|
|
|
877 bool differs_from_p (profile_count other) const;
|
|
|
878
|
|
|
879 /* LTO streaming support. */
|
|
|
880 static profile_count stream_in (struct lto_input_block *);
|
|
|
881 void stream_out (struct output_block *);
|
|
|
882 void stream_out (struct lto_output_stream *);
|
|
|
883 };
|
|
|
884 #endif
|
