Branch data Line data Source code
1 : : /* Branch prediction routines for the GNU compiler.
2 : : Copyright (C) 2000-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : /* References:
21 : :
22 : : [1] "Branch Prediction for Free"
23 : : Ball and Larus; PLDI '93.
24 : : [2] "Static Branch Frequency and Program Profile Analysis"
25 : : Wu and Larus; MICRO-27.
26 : : [3] "Corpus-based Static Branch Prediction"
27 : : Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
28 : :
29 : : #include "config.h"
30 : : #include "system.h"
31 : : #include "coretypes.h"
32 : : #include "backend.h"
33 : : #include "rtl.h"
34 : : #include "tree.h"
35 : : #include "gimple.h"
36 : : #include "cfghooks.h"
37 : : #include "tree-pass.h"
38 : : #include "ssa.h"
39 : : #include "memmodel.h"
40 : : #include "emit-rtl.h"
41 : : #include "cgraph.h"
42 : : #include "coverage.h"
43 : : #include "diagnostic-core.h"
44 : : #include "gimple-predict.h"
45 : : #include "fold-const.h"
46 : : #include "calls.h"
47 : : #include "cfganal.h"
48 : : #include "profile.h"
49 : : #include "sreal.h"
50 : : #include "cfgloop.h"
51 : : #include "gimple-iterator.h"
52 : : #include "tree-cfg.h"
53 : : #include "tree-ssa-loop-niter.h"
54 : : #include "tree-ssa-loop.h"
55 : : #include "tree-scalar-evolution.h"
56 : : #include "ipa-utils.h"
57 : : #include "gimple-pretty-print.h"
58 : : #include "selftest.h"
59 : : #include "cfgrtl.h"
60 : : #include "stringpool.h"
61 : : #include "attribs.h"
62 : :
63 : : /* Enum with reasons why a predictor is ignored. */
64 : :
65 : : enum predictor_reason
66 : : {
67 : : REASON_NONE,
68 : : REASON_IGNORED,
69 : : REASON_SINGLE_EDGE_DUPLICATE,
70 : : REASON_EDGE_PAIR_DUPLICATE
71 : : };
72 : :
73 : : /* String messages for the aforementioned enum. */
74 : :
75 : : static const char *reason_messages[] = {"", " (ignored)",
76 : : " (single edge duplicate)", " (edge pair duplicate)"};
77 : :
78 : :
79 : : static void combine_predictions_for_insn (rtx_insn *, basic_block);
80 : : static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
81 : : enum predictor_reason, edge);
82 : : static void predict_paths_leading_to (basic_block, enum br_predictor,
83 : : enum prediction,
84 : : class loop *in_loop = NULL);
85 : : static void predict_paths_leading_to_edge (edge, enum br_predictor,
86 : : enum prediction,
87 : : class loop *in_loop = NULL);
88 : : static bool can_predict_insn_p (const rtx_insn *);
89 : : static HOST_WIDE_INT get_predictor_value (br_predictor, HOST_WIDE_INT);
90 : : static void determine_unlikely_bbs ();
91 : : static void estimate_bb_frequencies ();
92 : :
93 : : /* Information we hold about each branch predictor.
94 : : Filled using information from predict.def. */
95 : :
96 : : struct predictor_info
97 : : {
98 : : const char *const name; /* Name used in the debugging dumps. */
99 : : const int hitrate; /* Expected hitrate used by
100 : : predict_insn_def call. */
101 : : const int flags;
102 : : };
103 : :
104 : : /* Use given predictor without Dempster-Shaffer theory if it matches
105 : : using first_match heuristics. */
106 : : #define PRED_FLAG_FIRST_MATCH 1
107 : :
108 : : /* Recompute hitrate in percent to our representation. */
109 : :
110 : : #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
111 : :
112 : : #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
113 : : static const struct predictor_info predictor_info[]= {
114 : : #include "predict.def"
115 : :
116 : : /* Upper bound on predictors. */
117 : : {NULL, 0, 0}
118 : : };
119 : : #undef DEF_PREDICTOR
120 : :
121 : : static gcov_type min_count = -1;
122 : :
123 : : /* Determine the threshold for hot BB counts. */
124 : :
125 : : gcov_type
126 : 56537 : get_hot_bb_threshold ()
127 : : {
128 : 56537 : if (min_count == -1)
129 : : {
130 : 100 : const int hot_frac = param_hot_bb_count_fraction;
131 : 200 : const gcov_type min_hot_count
132 : : = hot_frac
133 : 100 : ? profile_info->sum_max / hot_frac
134 : : : (gcov_type)profile_count::max_count;
135 : 100 : set_hot_bb_threshold (min_hot_count);
136 : 100 : if (dump_file)
137 : 21 : fprintf (dump_file, "Setting hotness threshold to %" PRId64 ".\n",
138 : : min_hot_count);
139 : : }
140 : 56537 : return min_count;
141 : : }
142 : :
143 : : /* Set the threshold for hot BB counts. */
144 : :
145 : : void
146 : 269 : set_hot_bb_threshold (gcov_type min)
147 : : {
148 : 269 : min_count = min;
149 : 269 : }
150 : :
151 : : /* Return TRUE if COUNT is considered to be hot in function FUN. */
152 : :
153 : : bool
154 : 1038722344 : maybe_hot_count_p (struct function *fun, profile_count count)
155 : : {
156 : 1038722344 : if (!count.initialized_p ())
157 : : return true;
158 : 948127736 : if (count.ipa () == profile_count::zero ())
159 : 4590214 : return false;
160 : 943537522 : if (!count.ipa_p ())
161 : : {
162 : 943440690 : struct cgraph_node *node = cgraph_node::get (fun->decl);
163 : 943440690 : if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
164 : : {
165 : 943440690 : if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
166 : : return false;
167 : 943391460 : if (node->frequency == NODE_FREQUENCY_HOT)
168 : : return true;
169 : : }
170 : 943387368 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
171 : : return true;
172 : 943177715 : if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
173 : 943177715 : && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
174 : 21654681 : return false;
175 : 921523034 : if (count * param_hot_bb_frequency_fraction
176 : 921523034 : < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
177 : : return false;
178 : : return true;
179 : : }
180 : : /* Code executed at most once is not hot. */
181 : 96832 : if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
182 : : return false;
183 : 56323 : return (count >= get_hot_bb_threshold ());
184 : : }
185 : :
186 : : /* Return true if basic block BB of function FUN can be CPU intensive
187 : : and should thus be optimized for maximum performance. */
188 : :
189 : : bool
190 : 1028282868 : maybe_hot_bb_p (struct function *fun, const_basic_block bb)
191 : : {
192 : 1028282868 : gcc_checking_assert (fun);
193 : 1028282868 : return maybe_hot_count_p (fun, bb->count);
194 : : }
195 : :
196 : : /* Return true if edge E can be CPU intensive and should thus be optimized
197 : : for maximum performance. */
198 : :
199 : : bool
200 : 9670581 : maybe_hot_edge_p (edge e)
201 : : {
202 : 9670581 : return maybe_hot_count_p (cfun, e->count ());
203 : : }
204 : :
205 : : /* Return true if COUNT is considered to be never executed in function FUN
206 : : or if function FUN is considered so in the static profile. */
207 : :
208 : : static bool
209 : 56324066 : probably_never_executed (struct function *fun, profile_count count)
210 : : {
211 : 56324066 : gcc_checking_assert (fun);
212 : 56324066 : if (count.ipa () == profile_count::zero ())
213 : 1607039 : return true;
214 : : /* Do not trust adjusted counts. This will make us to drop int cold section
215 : : code with low execution count as a result of inlining. These low counts
216 : : are not safe even with read profile and may lead us to dropping
217 : : code which actually gets executed into cold section of binary that is not
218 : : desirable. */
219 : 54717027 : if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
220 : : {
221 : 3353 : const int unlikely_frac = param_unlikely_bb_count_fraction;
222 : 3353 : if (count * unlikely_frac >= profile_info->runs)
223 : : return false;
224 : : return true;
225 : : }
226 : 3130 : if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
227 : 54713782 : && (cgraph_node::get (fun->decl)->frequency
228 : 54710652 : == NODE_FREQUENCY_UNLIKELY_EXECUTED))
229 : : return true;
230 : : return false;
231 : : }
232 : :
233 : : /* Return true if basic block BB of function FUN is probably never executed. */
234 : :
235 : : bool
236 : 17542601 : probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
237 : : {
238 : 17542601 : return probably_never_executed (fun, bb->count);
239 : : }
240 : :
241 : : /* Return true if edge E is unlikely executed for obvious reasons. */
242 : :
243 : : static bool
244 : 111525851 : unlikely_executed_edge_p (edge e)
245 : : {
246 : 112769118 : return (e->src->count == profile_count::zero ()
247 : 109930074 : || e->probability == profile_probability::never ())
248 : 105004011 : || (e->flags & EDGE_FAKE)
249 : : /* If we read profile and know EH edge is executed, trust it.
250 : : Otherwise we consider EH edges never executed. */
251 : 104148934 : || ((e->flags & EDGE_EH) && !e->probability.reliable_p ());
252 : : }
253 : :
254 : : /* Return true if edge E of function FUN is probably never executed. */
255 : :
256 : : bool
257 : 41012690 : probably_never_executed_edge_p (struct function *fun, edge e)
258 : : {
259 : 41012690 : if (unlikely_executed_edge_p (e))
260 : : return true;
261 : 38781465 : return probably_never_executed (fun, e->count ());
262 : : }
263 : :
264 : : /* Return true if function FUN should always be optimized for size. */
265 : :
266 : : optimize_size_level
267 : 2496184577 : optimize_function_for_size_p (struct function *fun)
268 : : {
269 : 2496184577 : if (!fun || !fun->decl)
270 : 195944600 : return optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
271 : 2394825564 : cgraph_node *n = cgraph_node::get (fun->decl);
272 : 2394825564 : if (n)
273 : 2352291272 : return n->optimize_for_size_p ();
274 : : return OPTIMIZE_SIZE_NO;
275 : : }
276 : :
277 : : /* Return true if function FUN should always be optimized for speed. */
278 : :
279 : : bool
280 : 228094847 : optimize_function_for_speed_p (struct function *fun)
281 : : {
282 : 228094847 : return !optimize_function_for_size_p (fun);
283 : : }
284 : :
285 : : /* Return the optimization type that should be used for function FUN. */
286 : :
287 : : optimization_type
288 : 0 : function_optimization_type (struct function *fun)
289 : : {
290 : 0 : return (optimize_function_for_speed_p (fun)
291 : 0 : ? OPTIMIZE_FOR_SPEED
292 : 0 : : OPTIMIZE_FOR_SIZE);
293 : : }
294 : :
295 : : /* Return TRUE if basic block BB should be optimized for size. */
296 : :
297 : : optimize_size_level
298 : 1010018732 : optimize_bb_for_size_p (const_basic_block bb)
299 : : {
300 : 1010018732 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
301 : :
302 : 2008909528 : if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
303 : 27104074 : ret = OPTIMIZE_SIZE_MAX;
304 : 1010018732 : if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun, bb))
305 : : ret = OPTIMIZE_SIZE_BALANCED;
306 : 1010018732 : return ret;
307 : : }
308 : :
309 : : /* Return TRUE if basic block BB should be optimized for speed. */
310 : :
311 : : bool
312 : 943095653 : optimize_bb_for_speed_p (const_basic_block bb)
313 : : {
314 : 943095653 : return !optimize_bb_for_size_p (bb);
315 : : }
316 : :
317 : : /* Return the optimization type that should be used for basic block BB. */
318 : :
319 : : optimization_type
320 : 5351895 : bb_optimization_type (const_basic_block bb)
321 : : {
322 : 5351895 : return (optimize_bb_for_speed_p (bb)
323 : 5351895 : ? OPTIMIZE_FOR_SPEED
324 : 5351895 : : OPTIMIZE_FOR_SIZE);
325 : : }
326 : :
327 : : /* Return TRUE if edge E should be optimized for size. */
328 : :
329 : : optimize_size_level
330 : 10242430 : optimize_edge_for_size_p (edge e)
331 : : {
332 : 10242430 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
333 : :
334 : 10242430 : if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
335 : : ret = OPTIMIZE_SIZE_MAX;
336 : 9877174 : if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
337 : : ret = OPTIMIZE_SIZE_BALANCED;
338 : 10242430 : return ret;
339 : : }
340 : :
341 : : /* Return TRUE if edge E should be optimized for speed. */
342 : :
343 : : bool
344 : 4261744 : optimize_edge_for_speed_p (edge e)
345 : : {
346 : 4261744 : return !optimize_edge_for_size_p (e);
347 : : }
348 : :
349 : : /* Return TRUE if the current function is optimized for size. */
350 : :
351 : : optimize_size_level
352 : 217893323 : optimize_insn_for_size_p (void)
353 : : {
354 : 217893323 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
355 : 217893323 : if (ret < OPTIMIZE_SIZE_BALANCED && !crtl->maybe_hot_insn_p)
356 : 217893323 : ret = OPTIMIZE_SIZE_BALANCED;
357 : 217893323 : return ret;
358 : : }
359 : :
360 : : /* Return TRUE if the current function is optimized for speed. */
361 : :
362 : : bool
363 : 85916382 : optimize_insn_for_speed_p (void)
364 : : {
365 : 85916382 : return !optimize_insn_for_size_p ();
366 : : }
367 : :
368 : : /* Return the optimization type that should be used for the current
369 : : instruction. */
370 : :
371 : : optimization_type
372 : 7152 : insn_optimization_type ()
373 : : {
374 : 7152 : return (optimize_insn_for_speed_p ()
375 : 7152 : ? OPTIMIZE_FOR_SPEED
376 : 7152 : : OPTIMIZE_FOR_SIZE);
377 : : }
378 : :
379 : : /* Return TRUE if LOOP should be optimized for size. */
380 : :
381 : : optimize_size_level
382 : 757314 : optimize_loop_for_size_p (class loop *loop)
383 : : {
384 : 757314 : return optimize_bb_for_size_p (loop->header);
385 : : }
386 : :
387 : : /* Return TRUE if LOOP should be optimized for speed. */
388 : :
389 : : bool
390 : 15353054 : optimize_loop_for_speed_p (class loop *loop)
391 : : {
392 : 15353054 : return optimize_bb_for_speed_p (loop->header);
393 : : }
394 : :
395 : : /* Return TRUE if nest rooted at LOOP should be optimized for speed. */
396 : :
397 : : bool
398 : 1196937 : optimize_loop_nest_for_speed_p (class loop *loop)
399 : : {
400 : 1196937 : class loop *l = loop;
401 : 1196937 : if (optimize_loop_for_speed_p (loop))
402 : : return true;
403 : 36104 : l = loop->inner;
404 : 48275 : while (l && l != loop)
405 : : {
406 : 13552 : if (optimize_loop_for_speed_p (l))
407 : : return true;
408 : 12171 : if (l->inner)
409 : : l = l->inner;
410 : 8084 : else if (l->next)
411 : : l = l->next;
412 : : else
413 : : {
414 : 19465 : while (l != loop && !l->next)
415 : 11616 : l = loop_outer (l);
416 : 7849 : if (l != loop)
417 : 52 : l = l->next;
418 : : }
419 : : }
420 : : return false;
421 : : }
422 : :
423 : : /* Return TRUE if nest rooted at LOOP should be optimized for size. */
424 : :
425 : : optimize_size_level
426 : 16644 : optimize_loop_nest_for_size_p (class loop *loop)
427 : : {
428 : 16644 : enum optimize_size_level ret = optimize_loop_for_size_p (loop);
429 : 16644 : class loop *l = loop;
430 : :
431 : 16644 : l = loop->inner;
432 : 16922 : while (l && l != loop)
433 : : {
434 : 16167 : if (ret == OPTIMIZE_SIZE_NO)
435 : : break;
436 : 278 : ret = MIN (optimize_loop_for_size_p (l), ret);
437 : 278 : if (l->inner)
438 : : l = l->inner;
439 : 269 : else if (l->next)
440 : : l = l->next;
441 : : else
442 : : {
443 : 341 : while (l != loop && !l->next)
444 : 173 : l = loop_outer (l);
445 : 168 : if (l != loop)
446 : 4 : l = l->next;
447 : : }
448 : : }
449 : 16644 : return ret;
450 : : }
451 : :
452 : : /* Return true if edge E is likely to be well predictable by branch
453 : : predictor. */
454 : :
455 : : bool
456 : 5922412 : predictable_edge_p (edge e)
457 : : {
458 : 5922412 : if (!e->probability.initialized_p ())
459 : : return false;
460 : 5921630 : if ((e->probability.to_reg_br_prob_base ()
461 : 5921630 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100)
462 : 5921630 : || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
463 : : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100))
464 : 627994 : return true;
465 : : return false;
466 : : }
467 : :
468 : :
469 : : /* Set RTL expansion for BB profile. */
470 : :
471 : : void
472 : 80170249 : rtl_profile_for_bb (basic_block bb)
473 : : {
474 : 80170249 : crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
475 : 80170249 : }
476 : :
477 : : /* Set RTL expansion for edge profile. */
478 : :
479 : : void
480 : 10186 : rtl_profile_for_edge (edge e)
481 : : {
482 : 10186 : crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
483 : 10186 : }
484 : :
485 : : /* Set RTL expansion to default mode (i.e. when profile info is not known). */
486 : : void
487 : 14339982 : default_rtl_profile (void)
488 : : {
489 : 14339982 : crtl->maybe_hot_insn_p = true;
490 : 14339982 : }
491 : :
492 : : /* Return true if the one of outgoing edges is already predicted by
493 : : PREDICTOR. */
494 : :
495 : : bool
496 : 0 : rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
497 : : {
498 : 0 : rtx note;
499 : 0 : if (!INSN_P (BB_END (bb)))
500 : : return false;
501 : 0 : for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
502 : 0 : if (REG_NOTE_KIND (note) == REG_BR_PRED
503 : 0 : && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
504 : : return true;
505 : : return false;
506 : : }
507 : :
508 : : /* Structure representing predictions in tree level. */
509 : :
510 : : struct edge_prediction {
511 : : struct edge_prediction *ep_next;
512 : : edge ep_edge;
513 : : enum br_predictor ep_predictor;
514 : : int ep_probability;
515 : : };
516 : :
517 : : /* This map contains for a basic block the list of predictions for the
518 : : outgoing edges. */
519 : :
520 : : static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
521 : :
522 : : /* Global cache for expr_expected_value. */
523 : :
524 : : struct expected_value
525 : : {
526 : : tree val;
527 : : enum br_predictor predictor;
528 : : HOST_WIDE_INT probability;
529 : : };
530 : : static hash_map<int_hash<unsigned, 0>, expected_value> *ssa_expected_value;
531 : :
532 : : /* Return true if the one of outgoing edges is already predicted by
533 : : PREDICTOR. */
534 : :
535 : : bool
536 : 3245866 : gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
537 : : {
538 : 3245866 : struct edge_prediction *i;
539 : 3245866 : edge_prediction **preds = bb_predictions->get (bb);
540 : :
541 : 3245866 : if (!preds)
542 : : return false;
543 : :
544 : 1625312 : for (i = *preds; i; i = i->ep_next)
545 : 848327 : if (i->ep_predictor == predictor)
546 : : return true;
547 : : return false;
548 : : }
549 : :
550 : : /* Return true if the one of outgoing edges is already predicted by
551 : : PREDICTOR for edge E predicted as TAKEN. */
552 : :
553 : : bool
554 : 1421723 : edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
555 : : {
556 : 1421723 : struct edge_prediction *i;
557 : 1421723 : basic_block bb = e->src;
558 : 1421723 : edge_prediction **preds = bb_predictions->get (bb);
559 : 1421723 : if (!preds)
560 : : return false;
561 : :
562 : 308426 : int probability = predictor_info[(int) predictor].hitrate;
563 : :
564 : 308426 : if (taken != TAKEN)
565 : 308191 : probability = REG_BR_PROB_BASE - probability;
566 : :
567 : 5200890 : for (i = *preds; i; i = i->ep_next)
568 : 4896807 : if (i->ep_predictor == predictor
569 : 4581951 : && i->ep_edge == e
570 : 4343 : && i->ep_probability == probability)
571 : : return true;
572 : : return false;
573 : : }
574 : :
575 : : /* Same predicate as above, working on edges. */
576 : : bool
577 : 0 : edge_probability_reliable_p (const_edge e)
578 : : {
579 : 0 : return e->probability.probably_reliable_p ();
580 : : }
581 : :
582 : : /* Same predicate as edge_probability_reliable_p, working on notes. */
583 : : bool
584 : 0 : br_prob_note_reliable_p (const_rtx note)
585 : : {
586 : 0 : gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
587 : 0 : return profile_probability::from_reg_br_prob_note
588 : 0 : (XINT (note, 0)).probably_reliable_p ();
589 : : }
590 : :
591 : : static void
592 : 84729 : predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
593 : : {
594 : 84729 : gcc_assert (any_condjump_p (insn));
595 : 84729 : if (!flag_guess_branch_prob)
596 : : return;
597 : :
598 : 169364 : add_reg_note (insn, REG_BR_PRED,
599 : 84682 : gen_rtx_CONCAT (VOIDmode,
600 : : GEN_INT ((int) predictor),
601 : : GEN_INT ((int) probability)));
602 : : }
603 : :
604 : : /* Predict insn by given predictor. */
605 : :
606 : : void
607 : 84729 : predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
608 : : enum prediction taken)
609 : : {
610 : 84729 : int probability = predictor_info[(int) predictor].hitrate;
611 : 84729 : gcc_assert (probability != PROB_UNINITIALIZED);
612 : :
613 : 84729 : if (taken != TAKEN)
614 : 5998 : probability = REG_BR_PROB_BASE - probability;
615 : :
616 : 84729 : predict_insn (insn, predictor, probability);
617 : 84729 : }
618 : :
619 : : /* Predict edge E with given probability if possible. */
620 : :
621 : : void
622 : 0 : rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
623 : : {
624 : 0 : rtx_insn *last_insn;
625 : 0 : last_insn = BB_END (e->src);
626 : :
627 : : /* We can store the branch prediction information only about
628 : : conditional jumps. */
629 : 0 : if (!any_condjump_p (last_insn))
630 : : return;
631 : :
632 : : /* We always store probability of branching. */
633 : 0 : if (e->flags & EDGE_FALLTHRU)
634 : 0 : probability = REG_BR_PROB_BASE - probability;
635 : :
636 : 0 : predict_insn (last_insn, predictor, probability);
637 : : }
638 : :
639 : : /* Predict edge E with the given PROBABILITY. */
640 : : void
641 : 6588362 : gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
642 : : {
643 : 6588362 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
644 : 6588362 : && EDGE_COUNT (e->src->succs) > 1
645 : 6588362 : && flag_guess_branch_prob
646 : 13176724 : && optimize)
647 : : {
648 : 6588362 : struct edge_prediction *i = XNEW (struct edge_prediction);
649 : 6588362 : edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
650 : :
651 : 6588362 : i->ep_next = preds;
652 : 6588362 : preds = i;
653 : 6588362 : i->ep_probability = probability;
654 : 6588362 : i->ep_predictor = predictor;
655 : 6588362 : i->ep_edge = e;
656 : : }
657 : 6588362 : }
658 : :
659 : : /* Filter edge predictions PREDS by a function FILTER: if FILTER return false
660 : : the prediction is removed.
661 : : DATA are passed to the filter function. */
662 : :
663 : : static void
664 : 3017788 : filter_predictions (edge_prediction **preds,
665 : : bool (*filter) (edge_prediction *, void *), void *data)
666 : : {
667 : 3017788 : if (!bb_predictions)
668 : : return;
669 : :
670 : 3017788 : if (preds)
671 : : {
672 : : struct edge_prediction **prediction = preds;
673 : : struct edge_prediction *next;
674 : :
675 : 8434708 : while (*prediction)
676 : : {
677 : 5416920 : if ((*filter) (*prediction, data))
678 : 4910625 : prediction = &((*prediction)->ep_next);
679 : : else
680 : : {
681 : 506295 : next = (*prediction)->ep_next;
682 : 506295 : free (*prediction);
683 : 506295 : *prediction = next;
684 : : }
685 : : }
686 : : }
687 : : }
688 : :
689 : : /* Filter function predicate that returns true for a edge predicate P
690 : : if its edge is equal to DATA. */
691 : :
692 : : static bool
693 : 0 : not_equal_edge_p (edge_prediction *p, void *data)
694 : : {
695 : 0 : return p->ep_edge != (edge)data;
696 : : }
697 : :
698 : : /* Remove all predictions on given basic block that are attached
699 : : to edge E. */
700 : : void
701 : 84829591 : remove_predictions_associated_with_edge (edge e)
702 : : {
703 : 84829591 : if (!bb_predictions)
704 : : return;
705 : :
706 : 0 : edge_prediction **preds = bb_predictions->get (e->src);
707 : 0 : filter_predictions (preds, not_equal_edge_p, e);
708 : : }
709 : :
710 : : /* Clears the list of predictions stored for BB. */
711 : :
712 : : static void
713 : 11684594 : clear_bb_predictions (basic_block bb)
714 : : {
715 : 11684594 : edge_prediction **preds = bb_predictions->get (bb);
716 : 11684594 : struct edge_prediction *pred, *next;
717 : :
718 : 11684594 : if (!preds)
719 : : return;
720 : :
721 : 9840244 : for (pred = *preds; pred; pred = next)
722 : : {
723 : 6082067 : next = pred->ep_next;
724 : 6082067 : free (pred);
725 : : }
726 : 3758177 : *preds = NULL;
727 : : }
728 : :
729 : : /* Return true when we can store prediction on insn INSN.
730 : : At the moment we represent predictions only on conditional
731 : : jumps, not at computed jump or other complicated cases. */
732 : : static bool
733 : 1125834 : can_predict_insn_p (const rtx_insn *insn)
734 : : {
735 : 1125834 : return (JUMP_P (insn)
736 : 294498 : && any_condjump_p (insn)
737 : 1419826 : && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
738 : : }
739 : :
740 : : /* Predict edge E by given predictor if possible. */
741 : :
742 : : void
743 : 5453876 : predict_edge_def (edge e, enum br_predictor predictor,
744 : : enum prediction taken)
745 : : {
746 : 5453876 : int probability = predictor_info[(int) predictor].hitrate;
747 : :
748 : 5453876 : if (taken != TAKEN)
749 : 4458017 : probability = REG_BR_PROB_BASE - probability;
750 : :
751 : 5453876 : predict_edge (e, predictor, probability);
752 : 5453876 : }
753 : :
754 : : /* Invert all branch predictions or probability notes in the INSN. This needs
755 : : to be done each time we invert the condition used by the jump. */
756 : :
757 : : void
758 : 12839936 : invert_br_probabilities (rtx insn)
759 : : {
760 : 12839936 : rtx note;
761 : :
762 : 37984209 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
763 : 25144273 : if (REG_NOTE_KIND (note) == REG_BR_PROB)
764 : 25519856 : XINT (note, 0) = profile_probability::from_reg_br_prob_note
765 : 12759928 : (XINT (note, 0)).invert ().to_reg_br_prob_note ();
766 : 12384345 : else if (REG_NOTE_KIND (note) == REG_BR_PRED)
767 : 0 : XEXP (XEXP (note, 0), 1)
768 : 0 : = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
769 : 12839936 : }
770 : :
771 : : /* Dump information about the branch prediction to the output file. */
772 : :
773 : : static void
774 : 12720250 : dump_prediction (FILE *file, enum br_predictor predictor, int probability,
775 : : basic_block bb, enum predictor_reason reason = REASON_NONE,
776 : : edge ep_edge = NULL)
777 : : {
778 : 12720250 : edge e = ep_edge;
779 : 12720250 : edge_iterator ei;
780 : :
781 : 12720250 : if (!file)
782 : 12718414 : return;
783 : :
784 : 1836 : if (e == NULL)
785 : 1231 : FOR_EACH_EDGE (e, ei, bb->succs)
786 : 1231 : if (! (e->flags & EDGE_FALLTHRU))
787 : : break;
788 : :
789 : 1836 : char edge_info_str[128];
790 : 1836 : if (ep_edge)
791 : 605 : sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
792 : 605 : ep_edge->dest->index);
793 : : else
794 : 1231 : edge_info_str[0] = '\0';
795 : :
796 : 1836 : fprintf (file, " %s heuristics%s%s: %.2f%%",
797 : 1836 : predictor_info[predictor].name,
798 : 1836 : edge_info_str, reason_messages[reason],
799 : 1836 : probability * 100.0 / REG_BR_PROB_BASE);
800 : :
801 : 1836 : if (bb->count.initialized_p ())
802 : : {
803 : 247 : fprintf (file, " exec ");
804 : 247 : bb->count.dump (file);
805 : 247 : if (e && e->count ().initialized_p () && bb->count.to_gcov_type ())
806 : : {
807 : 166 : fprintf (file, " hit ");
808 : 166 : e->count ().dump (file);
809 : 332 : fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
810 : 166 : / bb->count.to_gcov_type ());
811 : : }
812 : : }
813 : :
814 : 1836 : fprintf (file, "\n");
815 : :
816 : : /* Print output that be easily read by analyze_brprob.py script. We are
817 : : interested only in counts that are read from GCDA files. */
818 : 1836 : if (dump_file && (dump_flags & TDF_DETAILS)
819 : 1105 : && bb->count.precise_p ()
820 : 1859 : && reason == REASON_NONE)
821 : : {
822 : 15 : fprintf (file, ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
823 : : predictor_info[predictor].name,
824 : 30 : bb->count.to_gcov_type (), e->count ().to_gcov_type (),
825 : : probability * 100.0 / REG_BR_PROB_BASE);
826 : : }
827 : : }
828 : :
829 : : /* Return true if STMT is known to be unlikely executed. */
830 : :
831 : : static bool
832 : 130611323 : unlikely_executed_stmt_p (gimple *stmt)
833 : : {
834 : 130611323 : if (!is_gimple_call (stmt))
835 : : return false;
836 : :
837 : : /* Those calls are inserted by optimizers when code is known to be
838 : : unreachable or undefined. */
839 : 9609458 : if (gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE)
840 : 9206083 : || gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE_TRAP)
841 : 18815529 : || gimple_call_builtin_p (stmt, BUILT_IN_TRAP))
842 : 472259 : return false;
843 : :
844 : : /* Checks below do not need to be fully reliable. Cold attribute may be
845 : : misplaced by user and in the presence of comdat we may result in call to
846 : : function with 0 profile having non-zero profile.
847 : :
848 : : We later detect that profile is lost and will drop the profile of the
849 : : comdat.
850 : :
851 : : So if we think profile count is reliable, do not try to apply these
852 : : heuristics. */
853 : 9137199 : if (gimple_bb (stmt)->count.reliable_p ()
854 : 9137199 : && gimple_bb (stmt)->count.nonzero_p ())
855 : 0 : return gimple_bb (stmt)->count == profile_count::zero ();
856 : : /* NORETURN attribute alone is not strong enough: exit() may be quite
857 : : likely executed once during program run. */
858 : 9137199 : if (gimple_call_fntype (stmt)
859 : 8767144 : && lookup_attribute ("cold",
860 : 8767144 : TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
861 : 9137199 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
862 : : return true;
863 : 9137199 : tree decl = gimple_call_fndecl (stmt);
864 : 9137199 : if (!decl)
865 : : return false;
866 : 8598583 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
867 : 8598583 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
868 : : return true;
869 : :
870 : 8304777 : cgraph_node *n = cgraph_node::get (decl);
871 : 8304777 : if (!n)
872 : : return false;
873 : :
874 : 8302008 : availability avail;
875 : 8302008 : n = n->ultimate_alias_target (&avail);
876 : 8302008 : if (avail < AVAIL_AVAILABLE)
877 : : return false;
878 : 2860065 : if (!n->analyzed
879 : 2860063 : || n->decl == current_function_decl)
880 : : return false;
881 : 2845892 : return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
882 : : }
883 : :
884 : : /* Return true if BB is unlikely executed. */
885 : :
886 : : static bool
887 : 24856481 : unlikely_executed_bb_p (basic_block bb)
888 : : {
889 : 24856481 : if (bb->count == profile_count::zero ())
890 : 0 : return true;
891 : 24856481 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
892 : : return false;
893 : 49712962 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
894 : 148185534 : !gsi_end_p (gsi); gsi_next (&gsi))
895 : : {
896 : 130611323 : if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
897 : : return true;
898 : 130299614 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
899 : : return false;
900 : : }
901 : : return false;
902 : : }
903 : :
904 : : /* We cannot predict the probabilities of outgoing edges of bb. Set them
905 : : evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
906 : : even probability for all edges not mentioned in the set. These edges
907 : : are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
908 : : if we have exactly one likely edge, make the other edges predicted
909 : : as not probable. */
910 : :
911 : : static void
912 : 8638148 : set_even_probabilities (basic_block bb,
913 : : hash_set<edge> *unlikely_edges = NULL,
914 : : hash_set<edge_prediction *> *likely_edges = NULL)
915 : : {
916 : 8638148 : unsigned nedges = 0, unlikely_count = 0;
917 : 8638148 : edge e = NULL;
918 : 8638148 : edge_iterator ei;
919 : 8638148 : profile_probability all = profile_probability::always ();
920 : :
921 : 18871453 : FOR_EACH_EDGE (e, ei, bb->succs)
922 : 10233305 : if (e->probability.initialized_p ())
923 : 9151446 : all -= e->probability;
924 : 1081859 : else if (!unlikely_executed_edge_p (e))
925 : : {
926 : 659556 : nedges++;
927 : 659556 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
928 : : {
929 : 10536 : all -= profile_probability::very_unlikely ();
930 : 10536 : unlikely_count++;
931 : : }
932 : : }
933 : :
934 : : /* Make the distribution even if all edges are unlikely. */
935 : 8638148 : unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
936 : 8638148 : if (unlikely_count == nedges)
937 : : {
938 : 8113912 : unlikely_edges = NULL;
939 : 8113912 : unlikely_count = 0;
940 : : }
941 : :
942 : : /* If we have one likely edge, then use its probability and distribute
943 : : remaining probabilities as even. */
944 : 8638148 : if (likely_count == 1)
945 : : {
946 : 2964 : FOR_EACH_EDGE (e, ei, bb->succs)
947 : 1980 : if (e->probability.initialized_p ())
948 : : ;
949 : 24 : else if (!unlikely_executed_edge_p (e))
950 : : {
951 : 24 : edge_prediction *prediction = *likely_edges->begin ();
952 : 24 : int p = prediction->ep_probability;
953 : 24 : profile_probability prob
954 : 24 : = profile_probability::from_reg_br_prob_base (p);
955 : :
956 : 24 : if (prediction->ep_edge == e)
957 : 6 : e->probability = prob;
958 : 18 : else if (unlikely_edges != NULL && unlikely_edges->contains (e))
959 : 1 : e->probability = profile_probability::very_unlikely ();
960 : : else
961 : : {
962 : 17 : profile_probability remainder = prob.invert ();
963 : 17 : remainder -= (profile_probability::very_unlikely ()
964 : 34 : * unlikely_count);
965 : 17 : int count = nedges - unlikely_count - 1;
966 : 17 : gcc_assert (count >= 0);
967 : :
968 : 17 : e->probability = remainder / count;
969 : : }
970 : : }
971 : : else
972 : 0 : e->probability = profile_probability::never ();
973 : : }
974 : : else
975 : : {
976 : : /* Make all unlikely edges unlikely and the rest will have even
977 : : probability. */
978 : 8637164 : unsigned scale = nedges - unlikely_count;
979 : 18868489 : FOR_EACH_EDGE (e, ei, bb->succs)
980 : 10231325 : if (e->probability.initialized_p ())
981 : : ;
982 : 1081835 : else if (!unlikely_executed_edge_p (e))
983 : : {
984 : 659532 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
985 : 10535 : e->probability = profile_probability::very_unlikely ();
986 : : else
987 : 648997 : e->probability = (all / scale).guessed ();
988 : : }
989 : : else
990 : 422303 : e->probability = profile_probability::never ();
991 : : }
992 : 8638148 : }
993 : :
994 : : /* Add REG_BR_PROB note to JUMP with PROB. */
995 : :
996 : : void
997 : 5272174 : add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
998 : : {
999 : 5272174 : gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
1000 : 5272174 : add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
1001 : 5272174 : }
1002 : :
1003 : : /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
1004 : : note if not already present. Remove now useless REG_BR_PRED notes. */
1005 : :
1006 : : static void
1007 : 562917 : combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
1008 : : {
1009 : 562917 : rtx prob_note;
1010 : 562917 : rtx *pnote;
1011 : 562917 : rtx note;
1012 : 562917 : int best_probability = PROB_EVEN;
1013 : 562917 : enum br_predictor best_predictor = END_PREDICTORS;
1014 : 562917 : int combined_probability = REG_BR_PROB_BASE / 2;
1015 : 562917 : int d;
1016 : 562917 : bool first_match = false;
1017 : 562917 : bool found = false;
1018 : :
1019 : 562917 : if (!can_predict_insn_p (insn))
1020 : : {
1021 : 415921 : set_even_probabilities (bb);
1022 : 415921 : return;
1023 : : }
1024 : :
1025 : 146996 : prob_note = find_reg_note (insn, REG_BR_PROB, 0);
1026 : 146996 : pnote = ®_NOTES (insn);
1027 : 146996 : if (dump_file)
1028 : 36 : fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
1029 : : bb->index);
1030 : :
1031 : : /* We implement "first match" heuristics and use probability guessed
1032 : : by predictor with smallest index. */
1033 : 231678 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1034 : 84682 : if (REG_NOTE_KIND (note) == REG_BR_PRED)
1035 : : {
1036 : 84682 : enum br_predictor predictor = ((enum br_predictor)
1037 : 84682 : INTVAL (XEXP (XEXP (note, 0), 0)));
1038 : 84682 : int probability = INTVAL (XEXP (XEXP (note, 0), 1));
1039 : :
1040 : 84682 : found = true;
1041 : 84682 : if (best_predictor > predictor
1042 : 84682 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1043 : 84682 : best_probability = probability, best_predictor = predictor;
1044 : :
1045 : 84682 : d = (combined_probability * probability
1046 : 84682 : + (REG_BR_PROB_BASE - combined_probability)
1047 : 84682 : * (REG_BR_PROB_BASE - probability));
1048 : :
1049 : : /* Use FP math to avoid overflows of 32bit integers. */
1050 : 84682 : if (d == 0)
1051 : : /* If one probability is 0% and one 100%, avoid division by zero. */
1052 : : combined_probability = REG_BR_PROB_BASE / 2;
1053 : : else
1054 : 84682 : combined_probability = (((double) combined_probability) * probability
1055 : 84682 : * REG_BR_PROB_BASE / d + 0.5);
1056 : : }
1057 : :
1058 : : /* Decide which heuristic to use. In case we didn't match anything,
1059 : : use no_prediction heuristic, in case we did match, use either
1060 : : first match or Dempster-Shaffer theory depending on the flags. */
1061 : :
1062 : 146996 : if (best_predictor != END_PREDICTORS)
1063 : 215 : first_match = true;
1064 : :
1065 : 146996 : if (!found)
1066 : 62314 : dump_prediction (dump_file, PRED_NO_PREDICTION,
1067 : : combined_probability, bb);
1068 : : else
1069 : : {
1070 : 84682 : if (!first_match)
1071 : 84467 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
1072 : : bb, !first_match ? REASON_NONE : REASON_IGNORED);
1073 : : else
1074 : 215 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
1075 : : bb, first_match ? REASON_NONE : REASON_IGNORED);
1076 : : }
1077 : :
1078 : 146996 : if (first_match)
1079 : 215 : combined_probability = best_probability;
1080 : 146996 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1081 : :
1082 : 378674 : while (*pnote)
1083 : : {
1084 : 84682 : if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1085 : : {
1086 : 84682 : enum br_predictor predictor = ((enum br_predictor)
1087 : 84682 : INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1088 : 84682 : int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1089 : :
1090 : 84682 : dump_prediction (dump_file, predictor, probability, bb,
1091 : 84682 : (!first_match || best_predictor == predictor)
1092 : 84682 : ? REASON_NONE : REASON_IGNORED);
1093 : 84682 : *pnote = XEXP (*pnote, 1);
1094 : : }
1095 : : else
1096 : 0 : pnote = &XEXP (*pnote, 1);
1097 : : }
1098 : :
1099 : 146996 : if (!prob_note)
1100 : : {
1101 : 146996 : profile_probability p
1102 : 146996 : = profile_probability::from_reg_br_prob_base (combined_probability);
1103 : 146996 : add_reg_br_prob_note (insn, p);
1104 : :
1105 : : /* Save the prediction into CFG in case we are seeing non-degenerated
1106 : : conditional jump. */
1107 : 146996 : if (!single_succ_p (bb))
1108 : : {
1109 : 146996 : BRANCH_EDGE (bb)->probability = p;
1110 : 146996 : FALLTHRU_EDGE (bb)->probability
1111 : 293992 : = BRANCH_EDGE (bb)->probability.invert ();
1112 : : }
1113 : : }
1114 : 0 : else if (!single_succ_p (bb))
1115 : : {
1116 : 0 : profile_probability prob = profile_probability::from_reg_br_prob_note
1117 : 0 : (XINT (prob_note, 0));
1118 : :
1119 : 0 : BRANCH_EDGE (bb)->probability = prob;
1120 : 0 : FALLTHRU_EDGE (bb)->probability = prob.invert ();
1121 : : }
1122 : : else
1123 : 0 : single_succ_edge (bb)->probability = profile_probability::always ();
1124 : : }
1125 : :
1126 : : /* Edge prediction hash traits. */
1127 : :
1128 : : struct predictor_hash: pointer_hash <edge_prediction>
1129 : : {
1130 : :
1131 : : static inline hashval_t hash (const edge_prediction *);
1132 : : static inline bool equal (const edge_prediction *, const edge_prediction *);
1133 : : };
1134 : :
1135 : : /* Calculate hash value of an edge prediction P based on predictor and
1136 : : normalized probability. */
1137 : :
1138 : : inline hashval_t
1139 : 13695046 : predictor_hash::hash (const edge_prediction *p)
1140 : : {
1141 : 13695046 : inchash::hash hstate;
1142 : 13695046 : hstate.add_int (p->ep_predictor);
1143 : :
1144 : 13695046 : int prob = p->ep_probability;
1145 : 13695046 : if (prob > REG_BR_PROB_BASE / 2)
1146 : 1670080 : prob = REG_BR_PROB_BASE - prob;
1147 : :
1148 : 13695046 : hstate.add_int (prob);
1149 : :
1150 : 13695046 : return hstate.end ();
1151 : : }
1152 : :
1153 : : /* Return true whether edge predictions P1 and P2 use the same predictor and
1154 : : have equal (or opposed probability). */
1155 : :
1156 : : inline bool
1157 : 3160486 : predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1158 : : {
1159 : 3160486 : return (p1->ep_predictor == p2->ep_predictor
1160 : 3160486 : && (p1->ep_probability == p2->ep_probability
1161 : 0 : || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1162 : : }
1163 : :
1164 : : struct predictor_hash_traits: predictor_hash,
1165 : : typed_noop_remove <edge_prediction *> {};
1166 : :
1167 : : /* Return true if edge prediction P is not in DATA hash set. */
1168 : :
1169 : : static bool
1170 : 5416912 : not_removed_prediction_p (edge_prediction *p, void *data)
1171 : : {
1172 : 5416912 : hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1173 : 5416912 : return !remove->contains (p);
1174 : : }
1175 : :
1176 : : /* Prune predictions for a basic block BB. Currently we do following
1177 : : clean-up steps:
1178 : :
1179 : : 1) remove duplicate prediction that is guessed with the same probability
1180 : : (different than 1/2) to both edge
1181 : : 2) remove duplicates for a prediction that belongs with the same probability
1182 : : to a single edge
1183 : :
1184 : : */
1185 : :
1186 : : static void
1187 : 3462311 : prune_predictions_for_bb (basic_block bb)
1188 : : {
1189 : 3462311 : edge_prediction **preds = bb_predictions->get (bb);
1190 : :
1191 : 3462311 : if (preds)
1192 : : {
1193 : 3017784 : hash_table <predictor_hash_traits> s (13);
1194 : 3017784 : hash_set <edge_prediction *> remove;
1195 : :
1196 : : /* Step 1: identify predictors that should be removed. */
1197 : 8434696 : for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1198 : : {
1199 : 5416912 : edge_prediction *existing = s.find (pred);
1200 : 5416912 : if (existing)
1201 : : {
1202 : 255555 : if (pred->ep_edge == existing->ep_edge
1203 : 0 : && pred->ep_probability == existing->ep_probability)
1204 : : {
1205 : : /* Remove a duplicate predictor. */
1206 : 0 : dump_prediction (dump_file, pred->ep_predictor,
1207 : : pred->ep_probability, bb,
1208 : : REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1209 : :
1210 : 0 : remove.add (pred);
1211 : : }
1212 : 255555 : else if (pred->ep_edge != existing->ep_edge
1213 : 255555 : && pred->ep_probability == existing->ep_probability
1214 : 255555 : && pred->ep_probability != REG_BR_PROB_BASE / 2)
1215 : : {
1216 : : /* Remove both predictors as they predict the same
1217 : : for both edges. */
1218 : 253164 : dump_prediction (dump_file, existing->ep_predictor,
1219 : : pred->ep_probability, bb,
1220 : : REASON_EDGE_PAIR_DUPLICATE,
1221 : : existing->ep_edge);
1222 : 253164 : dump_prediction (dump_file, pred->ep_predictor,
1223 : : pred->ep_probability, bb,
1224 : : REASON_EDGE_PAIR_DUPLICATE,
1225 : : pred->ep_edge);
1226 : :
1227 : 253164 : remove.add (existing);
1228 : 253164 : remove.add (pred);
1229 : : }
1230 : : }
1231 : :
1232 : 5416912 : edge_prediction **slot2 = s.find_slot (pred, INSERT);
1233 : 5416912 : *slot2 = pred;
1234 : : }
1235 : :
1236 : : /* Step 2: Remove predictors. */
1237 : 3017784 : filter_predictions (preds, not_removed_prediction_p, &remove);
1238 : 3017784 : }
1239 : 3462311 : }
1240 : :
1241 : : /* Combine predictions into single probability and store them into CFG.
1242 : : Remove now useless prediction entries.
1243 : : If DRY_RUN is set, only produce dumps and do not modify profile. */
1244 : :
1245 : : static void
1246 : 11684594 : combine_predictions_for_bb (basic_block bb, bool dry_run)
1247 : : {
1248 : 11684594 : int best_probability = PROB_EVEN;
1249 : 11684594 : enum br_predictor best_predictor = END_PREDICTORS;
1250 : 11684594 : int combined_probability = REG_BR_PROB_BASE / 2;
1251 : 11684594 : int d;
1252 : 11684594 : bool first_match = false;
1253 : 11684594 : bool found = false;
1254 : 11684594 : struct edge_prediction *pred;
1255 : 11684594 : int nedges = 0;
1256 : 11684594 : edge e, first = NULL, second = NULL;
1257 : 11684594 : edge_iterator ei;
1258 : 11684594 : int nzero = 0;
1259 : 11684594 : int nunknown = 0;
1260 : :
1261 : 28008855 : FOR_EACH_EDGE (e, ei, bb->succs)
1262 : : {
1263 : 16324261 : if (!unlikely_executed_edge_p (e))
1264 : : {
1265 : 14054246 : nedges ++;
1266 : 14054246 : if (first && !second)
1267 : : second = e;
1268 : 10565457 : if (!first)
1269 : 10457156 : first = e;
1270 : : }
1271 : 2270015 : else if (!e->probability.initialized_p ())
1272 : 23826 : e->probability = profile_probability::never ();
1273 : 16324261 : if (!e->probability.initialized_p ())
1274 : 6313191 : nunknown++;
1275 : 10011070 : else if (e->probability == profile_probability::never ())
1276 : 2138311 : nzero++;
1277 : : }
1278 : :
1279 : : /* When there is no successor or only one choice, prediction is easy.
1280 : :
1281 : : When we have a basic block with more than 2 successors, the situation
1282 : : is more complicated as DS theory cannot be used literally.
1283 : : More precisely, let's assume we predicted edge e1 with probability p1,
1284 : : thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1285 : : need to find probability of e.g. m1({b2}), which we don't know.
1286 : : The only approximation is to equally distribute 1-p1 to all edges
1287 : : different from b1.
1288 : :
1289 : : According to numbers we've got from SPEC2006 benchark, there's only
1290 : : one interesting reliable predictor (noreturn call), which can be
1291 : : handled with a bit easier approach. */
1292 : 11684594 : if (nedges != 2)
1293 : : {
1294 : 8222283 : hash_set<edge> unlikely_edges (4);
1295 : 8222283 : hash_set<edge_prediction *> likely_edges (4);
1296 : :
1297 : : /* Identify all edges that have a probability close to very unlikely.
1298 : : Doing the approach for very unlikely doesn't worth for doing as
1299 : : there's no such probability in SPEC2006 benchmark. */
1300 : 8222283 : edge_prediction **preds = bb_predictions->get (bb);
1301 : 8222283 : if (preds)
1302 : 1911843 : for (pred = *preds; pred; pred = pred->ep_next)
1303 : : {
1304 : 1171450 : if (pred->ep_probability <= PROB_VERY_UNLIKELY
1305 : 1151802 : || pred->ep_predictor == PRED_COLD_LABEL)
1306 : 19761 : unlikely_edges.add (pred->ep_edge);
1307 : 1151689 : else if (pred->ep_probability >= PROB_VERY_LIKELY
1308 : 1151095 : || pred->ep_predictor == PRED_BUILTIN_EXPECT
1309 : 1150707 : || pred->ep_predictor == PRED_HOT_LABEL)
1310 : 985 : likely_edges.add (pred);
1311 : : }
1312 : :
1313 : : /* It can happen that an edge is both in likely_edges and unlikely_edges.
1314 : : Clear both sets in that situation. */
1315 : 8223267 : for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
1316 : 8224251 : it != likely_edges.end (); ++it)
1317 : 985 : if (unlikely_edges.contains ((*it)->ep_edge))
1318 : : {
1319 : 1 : likely_edges.empty ();
1320 : 8222284 : unlikely_edges.empty ();
1321 : : break;
1322 : : }
1323 : :
1324 : 8222283 : if (!dry_run)
1325 : 8222227 : set_even_probabilities (bb, &unlikely_edges, &likely_edges);
1326 : 8222283 : clear_bb_predictions (bb);
1327 : 8222283 : if (dump_file)
1328 : : {
1329 : 1282 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1330 : 1282 : if (unlikely_edges.is_empty ())
1331 : 1280 : fprintf (dump_file,
1332 : : "%i edges in bb %i predicted to even probabilities\n",
1333 : : nedges, bb->index);
1334 : : else
1335 : : {
1336 : 2 : fprintf (dump_file,
1337 : : "%i edges in bb %i predicted with some unlikely edges\n",
1338 : : nedges, bb->index);
1339 : 11 : FOR_EACH_EDGE (e, ei, bb->succs)
1340 : 9 : if (!unlikely_executed_edge_p (e))
1341 : 9 : dump_prediction (dump_file, PRED_COMBINED,
1342 : : e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1343 : : }
1344 : : }
1345 : 8222283 : return;
1346 : 8222283 : }
1347 : :
1348 : 3462311 : if (dump_file)
1349 : 575 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1350 : :
1351 : 3462311 : prune_predictions_for_bb (bb);
1352 : :
1353 : 3462311 : edge_prediction **preds = bb_predictions->get (bb);
1354 : :
1355 : 3462311 : if (preds)
1356 : : {
1357 : : /* We implement "first match" heuristics and use probability guessed
1358 : : by predictor with smallest index. */
1359 : 7928401 : for (pred = *preds; pred; pred = pred->ep_next)
1360 : : {
1361 : 4910617 : enum br_predictor predictor = pred->ep_predictor;
1362 : 4910617 : int probability = pred->ep_probability;
1363 : :
1364 : 4910617 : if (pred->ep_edge != first)
1365 : 1310338 : probability = REG_BR_PROB_BASE - probability;
1366 : :
1367 : 4910617 : found = true;
1368 : : /* First match heuristics would be widly confused if we predicted
1369 : : both directions. */
1370 : 4910617 : if (best_predictor > predictor
1371 : 4727355 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1372 : : {
1373 : : struct edge_prediction *pred2;
1374 : : int prob = probability;
1375 : :
1376 : 3672919 : for (pred2 = (struct edge_prediction *) *preds;
1377 : 5350204 : pred2; pred2 = pred2->ep_next)
1378 : 3672919 : if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1379 : : {
1380 : 0 : int probability2 = pred2->ep_probability;
1381 : :
1382 : 0 : if (pred2->ep_edge != first)
1383 : 0 : probability2 = REG_BR_PROB_BASE - probability2;
1384 : :
1385 : 0 : if ((probability < REG_BR_PROB_BASE / 2) !=
1386 : 0 : (probability2 < REG_BR_PROB_BASE / 2))
1387 : : break;
1388 : :
1389 : : /* If the same predictor later gave better result, go for it! */
1390 : 0 : if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1391 : 0 : || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1392 : 3672919 : prob = probability2;
1393 : : }
1394 : 1677285 : if (!pred2)
1395 : 4910617 : best_probability = prob, best_predictor = predictor;
1396 : : }
1397 : :
1398 : 4910617 : d = (combined_probability * probability
1399 : 4910617 : + (REG_BR_PROB_BASE - combined_probability)
1400 : 4910617 : * (REG_BR_PROB_BASE - probability));
1401 : :
1402 : : /* Use FP math to avoid overflows of 32bit integers. */
1403 : 4910617 : if (d == 0)
1404 : : /* If one probability is 0% and one 100%, avoid division by zero. */
1405 : : combined_probability = REG_BR_PROB_BASE / 2;
1406 : : else
1407 : 4910617 : combined_probability = (((double) combined_probability)
1408 : 4910617 : * probability
1409 : 4910617 : * REG_BR_PROB_BASE / d + 0.5);
1410 : : }
1411 : : }
1412 : :
1413 : : /* Decide which heuristic to use. In case we didn't match anything,
1414 : : use no_prediction heuristic, in case we did match, use either
1415 : : first match or Dempster-Shaffer theory depending on the flags. */
1416 : :
1417 : 3017784 : if (best_predictor != END_PREDICTORS)
1418 : 1417145 : first_match = true;
1419 : :
1420 : 3462311 : if (!found)
1421 : 519077 : dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1422 : : else
1423 : : {
1424 : 2943234 : if (!first_match)
1425 : 1526089 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1426 : : !first_match ? REASON_NONE : REASON_IGNORED);
1427 : : else
1428 : 1417145 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1429 : : first_match ? REASON_NONE : REASON_IGNORED);
1430 : : }
1431 : :
1432 : 3462311 : if (first_match)
1433 : 1417145 : combined_probability = best_probability;
1434 : 3462311 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1435 : :
1436 : 3462311 : if (preds)
1437 : : {
1438 : 7928401 : for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1439 : : {
1440 : 4910617 : enum br_predictor predictor = pred->ep_predictor;
1441 : 4910617 : int probability = pred->ep_probability;
1442 : :
1443 : 4910617 : dump_prediction (dump_file, predictor, probability, bb,
1444 : 4910617 : (!first_match || best_predictor == predictor)
1445 : 4910617 : ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1446 : : }
1447 : : }
1448 : 3462311 : clear_bb_predictions (bb);
1449 : :
1450 : :
1451 : : /* If we have only one successor which is unknown, we can compute missing
1452 : : probability. */
1453 : 3462311 : if (nunknown == 1)
1454 : : {
1455 : 1213 : profile_probability prob = profile_probability::always ();
1456 : 1213 : edge missing = NULL;
1457 : :
1458 : 3639 : FOR_EACH_EDGE (e, ei, bb->succs)
1459 : 2426 : if (e->probability.initialized_p ())
1460 : 1213 : prob -= e->probability;
1461 : 1213 : else if (missing == NULL)
1462 : : missing = e;
1463 : : else
1464 : 0 : gcc_unreachable ();
1465 : 1213 : missing->probability = prob;
1466 : : }
1467 : : /* If nothing is unknown, we have nothing to update. */
1468 : 3899955 : else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1469 : : ;
1470 : 3022241 : else if (!dry_run)
1471 : : {
1472 : 3022241 : first->probability
1473 : 3022241 : = profile_probability::from_reg_br_prob_base (combined_probability);
1474 : 3022241 : second->probability = first->probability.invert ();
1475 : : }
1476 : : }
1477 : :
1478 : : /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1479 : : Return the SSA_NAME if the condition satisfies, NULL otherwise.
1480 : :
1481 : : T1 and T2 should be one of the following cases:
1482 : : 1. T1 is SSA_NAME, T2 is NULL
1483 : : 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1484 : : 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1485 : :
1486 : : static tree
1487 : 9403 : strips_small_constant (tree t1, tree t2)
1488 : : {
1489 : 9403 : tree ret = NULL;
1490 : 9403 : int value = 0;
1491 : :
1492 : 9403 : if (!t1)
1493 : : return NULL;
1494 : 9403 : else if (TREE_CODE (t1) == SSA_NAME)
1495 : : ret = t1;
1496 : 1081 : else if (tree_fits_shwi_p (t1))
1497 : 89 : value = tree_to_shwi (t1);
1498 : : else
1499 : : return NULL;
1500 : :
1501 : 8411 : if (!t2)
1502 : : return ret;
1503 : 8411 : else if (tree_fits_shwi_p (t2))
1504 : 7868 : value = tree_to_shwi (t2);
1505 : 543 : else if (TREE_CODE (t2) == SSA_NAME)
1506 : : {
1507 : 363 : if (ret)
1508 : : return NULL;
1509 : : else
1510 : : ret = t2;
1511 : : }
1512 : :
1513 : 8137 : if (value <= 4 && value >= -4)
1514 : : return ret;
1515 : : else
1516 : 638 : return NULL;
1517 : : }
1518 : :
1519 : : /* Return the SSA_NAME in T or T's operands.
1520 : : Return NULL if SSA_NAME cannot be found. */
1521 : :
1522 : : static tree
1523 : 237535 : get_base_value (tree t)
1524 : : {
1525 : 237535 : if (TREE_CODE (t) == SSA_NAME)
1526 : : return t;
1527 : :
1528 : 12016 : if (!BINARY_CLASS_P (t))
1529 : : return NULL;
1530 : :
1531 : 9403 : switch (TREE_OPERAND_LENGTH (t))
1532 : : {
1533 : 0 : case 1:
1534 : 0 : return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1535 : 9403 : case 2:
1536 : 9403 : return strips_small_constant (TREE_OPERAND (t, 0),
1537 : 18806 : TREE_OPERAND (t, 1));
1538 : : default:
1539 : : return NULL;
1540 : : }
1541 : : }
1542 : :
1543 : : /* Check the compare STMT in LOOP. If it compares an induction
1544 : : variable to a loop invariant, return true, and save
1545 : : LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1546 : : Otherwise return false and set LOOP_INVAIANT to NULL. */
1547 : :
1548 : : static bool
1549 : 860487 : is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop,
1550 : : tree *loop_invariant,
1551 : : enum tree_code *compare_code,
1552 : : tree *loop_step,
1553 : : tree *loop_iv_base)
1554 : : {
1555 : 860487 : tree op0, op1, bound, base;
1556 : 860487 : affine_iv iv0, iv1;
1557 : 860487 : enum tree_code code;
1558 : 860487 : tree step;
1559 : :
1560 : 860487 : code = gimple_cond_code (stmt);
1561 : 860487 : *loop_invariant = NULL;
1562 : :
1563 : 860487 : switch (code)
1564 : : {
1565 : 859629 : case GT_EXPR:
1566 : 859629 : case GE_EXPR:
1567 : 859629 : case NE_EXPR:
1568 : 859629 : case LT_EXPR:
1569 : 859629 : case LE_EXPR:
1570 : 859629 : case EQ_EXPR:
1571 : 859629 : break;
1572 : :
1573 : : default:
1574 : : return false;
1575 : : }
1576 : :
1577 : 859629 : op0 = gimple_cond_lhs (stmt);
1578 : 859629 : op1 = gimple_cond_rhs (stmt);
1579 : :
1580 : 859629 : if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1581 : 859610 : || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1582 : : return false;
1583 : 1690226 : if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1584 : : return false;
1585 : 998436 : if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1586 : : return false;
1587 : 479311 : if (TREE_CODE (iv0.step) != INTEGER_CST
1588 : 476524 : || TREE_CODE (iv1.step) != INTEGER_CST)
1589 : : return false;
1590 : 543300 : if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1591 : 529784 : || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1592 : 13842 : return false;
1593 : :
1594 : 456181 : if (integer_zerop (iv0.step))
1595 : : {
1596 : 59761 : if (code != NE_EXPR && code != EQ_EXPR)
1597 : 42187 : code = invert_tree_comparison (code, false);
1598 : 59761 : bound = iv0.base;
1599 : 59761 : base = iv1.base;
1600 : 59761 : if (tree_fits_shwi_p (iv1.step))
1601 : : step = iv1.step;
1602 : : else
1603 : : return false;
1604 : : }
1605 : : else
1606 : : {
1607 : 396420 : bound = iv1.base;
1608 : 396420 : base = iv0.base;
1609 : 396420 : if (tree_fits_shwi_p (iv0.step))
1610 : : step = iv0.step;
1611 : : else
1612 : : return false;
1613 : : }
1614 : :
1615 : 449221 : if (TREE_CODE (bound) != INTEGER_CST)
1616 : 158711 : bound = get_base_value (bound);
1617 : 158711 : if (!bound)
1618 : : return false;
1619 : 447549 : if (TREE_CODE (base) != INTEGER_CST)
1620 : 78824 : base = get_base_value (base);
1621 : 78824 : if (!base)
1622 : : return false;
1623 : :
1624 : 444704 : *loop_invariant = bound;
1625 : 444704 : *compare_code = code;
1626 : 444704 : *loop_step = step;
1627 : 444704 : *loop_iv_base = base;
1628 : 444704 : return true;
1629 : : }
1630 : :
1631 : : /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1632 : :
1633 : : static bool
1634 : 6869 : expr_coherent_p (tree t1, tree t2)
1635 : : {
1636 : 6869 : gimple *stmt;
1637 : 6869 : tree ssa_name_1 = NULL;
1638 : 6869 : tree ssa_name_2 = NULL;
1639 : :
1640 : 6869 : gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1641 : 6869 : gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1642 : :
1643 : 6869 : if (t1 == t2)
1644 : : return true;
1645 : :
1646 : 2973 : if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1647 : : return true;
1648 : 1744 : if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1649 : : return false;
1650 : :
1651 : : /* Check to see if t1 is expressed/defined with t2. */
1652 : 320 : stmt = SSA_NAME_DEF_STMT (t1);
1653 : 320 : gcc_assert (stmt != NULL);
1654 : 320 : if (is_gimple_assign (stmt))
1655 : : {
1656 : 194 : ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1657 : 194 : if (ssa_name_1 && ssa_name_1 == t2)
1658 : : return true;
1659 : : }
1660 : :
1661 : : /* Check to see if t2 is expressed/defined with t1. */
1662 : 320 : stmt = SSA_NAME_DEF_STMT (t2);
1663 : 320 : gcc_assert (stmt != NULL);
1664 : 320 : if (is_gimple_assign (stmt))
1665 : : {
1666 : 194 : ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1667 : 194 : if (ssa_name_2 && ssa_name_2 == t1)
1668 : : return true;
1669 : : }
1670 : :
1671 : : /* Compare if t1 and t2's def_stmts are identical. */
1672 : 320 : if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1673 : : return true;
1674 : : else
1675 : : return false;
1676 : : }
1677 : :
1678 : : /* Return true if E is predicted by one of loop heuristics. */
1679 : :
1680 : : static bool
1681 : 6164285 : predicted_by_loop_heuristics_p (basic_block bb)
1682 : : {
1683 : 6164285 : struct edge_prediction *i;
1684 : 6164285 : edge_prediction **preds = bb_predictions->get (bb);
1685 : :
1686 : 6164285 : if (!preds)
1687 : : return false;
1688 : :
1689 : 2214688 : for (i = *preds; i; i = i->ep_next)
1690 : 1886570 : if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1691 : 1886570 : || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1692 : : || i->ep_predictor == PRED_LOOP_ITERATIONS
1693 : : || i->ep_predictor == PRED_LOOP_EXIT
1694 : : || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1695 : : || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1696 : : return true;
1697 : : return false;
1698 : : }
1699 : :
1700 : : /* Predict branch probability of BB when BB contains a branch that compares
1701 : : an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1702 : : loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1703 : :
1704 : : E.g.
1705 : : for (int i = 0; i < bound; i++) {
1706 : : if (i < bound - 2)
1707 : : computation_1();
1708 : : else
1709 : : computation_2();
1710 : : }
1711 : :
1712 : : In this loop, we will predict the branch inside the loop to be taken. */
1713 : :
1714 : : static void
1715 : 2035291 : predict_iv_comparison (class loop *loop, basic_block bb,
1716 : : tree loop_bound_var,
1717 : : tree loop_iv_base_var,
1718 : : enum tree_code loop_bound_code,
1719 : : int loop_bound_step)
1720 : : {
1721 : 2035291 : tree compare_var, compare_base;
1722 : 2035291 : enum tree_code compare_code;
1723 : 2035291 : tree compare_step_var;
1724 : 2035291 : edge then_edge;
1725 : 2035291 : edge_iterator ei;
1726 : :
1727 : 2035291 : if (predicted_by_loop_heuristics_p (bb))
1728 : 2033696 : return;
1729 : :
1730 : 4263218 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1731 : 254077 : if (!stmt)
1732 : : return;
1733 : 254077 : if (!is_comparison_with_loop_invariant_p (stmt,
1734 : : loop, &compare_var,
1735 : : &compare_code,
1736 : : &compare_step_var,
1737 : : &compare_base))
1738 : : return;
1739 : :
1740 : : /* Find the taken edge. */
1741 : 11062 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
1742 : 11062 : if (then_edge->flags & EDGE_TRUE_VALUE)
1743 : : break;
1744 : :
1745 : : /* When comparing an IV to a loop invariant, NE is more likely to be
1746 : : taken while EQ is more likely to be not-taken. */
1747 : 10964 : if (compare_code == NE_EXPR)
1748 : : {
1749 : 1617 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1750 : 1617 : return;
1751 : : }
1752 : 9347 : else if (compare_code == EQ_EXPR)
1753 : : {
1754 : 4738 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1755 : 4738 : return;
1756 : : }
1757 : :
1758 : 4609 : if (!expr_coherent_p (loop_iv_base_var, compare_base))
1759 : : return;
1760 : :
1761 : : /* If loop bound, base and compare bound are all constants, we can
1762 : : calculate the probability directly. */
1763 : 4032 : if (tree_fits_shwi_p (loop_bound_var)
1764 : 2642 : && tree_fits_shwi_p (compare_var)
1765 : 2505 : && tree_fits_shwi_p (compare_base))
1766 : : {
1767 : 2437 : int probability;
1768 : 2437 : wi::overflow_type overflow;
1769 : 2437 : bool overall_overflow = false;
1770 : 2437 : widest_int compare_count, tem;
1771 : :
1772 : : /* (loop_bound - base) / compare_step */
1773 : 2437 : tem = wi::sub (wi::to_widest (loop_bound_var),
1774 : 4874 : wi::to_widest (compare_base), SIGNED, &overflow);
1775 : 2437 : overall_overflow |= overflow;
1776 : 2437 : widest_int loop_count = wi::div_trunc (tem,
1777 : 2437 : wi::to_widest (compare_step_var),
1778 : 2437 : SIGNED, &overflow);
1779 : 2437 : overall_overflow |= overflow;
1780 : :
1781 : 2437 : if (!wi::neg_p (wi::to_widest (compare_step_var))
1782 : 2437 : ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1783 : : {
1784 : : /* (loop_bound - compare_bound) / compare_step */
1785 : 352 : tem = wi::sub (wi::to_widest (loop_bound_var),
1786 : 704 : wi::to_widest (compare_var), SIGNED, &overflow);
1787 : 352 : overall_overflow |= overflow;
1788 : 352 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1789 : 352 : SIGNED, &overflow);
1790 : 352 : overall_overflow |= overflow;
1791 : : }
1792 : : else
1793 : : {
1794 : : /* (compare_bound - base) / compare_step */
1795 : 2085 : tem = wi::sub (wi::to_widest (compare_var),
1796 : 4170 : wi::to_widest (compare_base), SIGNED, &overflow);
1797 : 2085 : overall_overflow |= overflow;
1798 : 2085 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1799 : 2085 : SIGNED, &overflow);
1800 : 2085 : overall_overflow |= overflow;
1801 : : }
1802 : 2437 : if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1803 : 2067 : ++compare_count;
1804 : 2437 : if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1805 : 164 : ++loop_count;
1806 : 2437 : if (wi::neg_p (compare_count))
1807 : 782 : compare_count = 0;
1808 : 2437 : if (wi::neg_p (loop_count))
1809 : 810 : loop_count = 0;
1810 : 2437 : if (loop_count == 0)
1811 : : probability = 0;
1812 : 1615 : else if (wi::cmps (compare_count, loop_count) == 1)
1813 : : probability = REG_BR_PROB_BASE;
1814 : : else
1815 : : {
1816 : 1571 : tem = compare_count * REG_BR_PROB_BASE;
1817 : 1571 : tem = wi::udiv_trunc (tem, loop_count);
1818 : 1571 : probability = tem.to_uhwi ();
1819 : : }
1820 : :
1821 : : /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1822 : 2437 : if (!overall_overflow)
1823 : 2437 : predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1824 : :
1825 : 2437 : return;
1826 : 2437 : }
1827 : :
1828 : 1595 : if (expr_coherent_p (loop_bound_var, compare_var))
1829 : : {
1830 : 930 : if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1831 : 803 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1832 : 795 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1833 : 135 : else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1834 : 113 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1835 : 98 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1836 : 37 : else if (loop_bound_code == NE_EXPR)
1837 : : {
1838 : : /* If the loop backedge condition is "(i != bound)", we do
1839 : : the comparison based on the step of IV:
1840 : : * step < 0 : backedge condition is like (i > bound)
1841 : : * step > 0 : backedge condition is like (i < bound) */
1842 : 12 : gcc_assert (loop_bound_step != 0);
1843 : 12 : if (loop_bound_step > 0
1844 : 12 : && (compare_code == LT_EXPR
1845 : 12 : || compare_code == LE_EXPR))
1846 : 11 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1847 : 1 : else if (loop_bound_step < 0
1848 : 0 : && (compare_code == GT_EXPR
1849 : 0 : || compare_code == GE_EXPR))
1850 : 0 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1851 : : else
1852 : 1 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1853 : : }
1854 : : else
1855 : : /* The branch is predicted not-taken if loop_bound_code is
1856 : : opposite with compare_code. */
1857 : 25 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1858 : : }
1859 : 665 : else if (expr_coherent_p (loop_iv_base_var, compare_var))
1860 : : {
1861 : : /* For cases like:
1862 : : for (i = s; i < h; i++)
1863 : : if (i > s + 2) ....
1864 : : The branch should be predicted taken. */
1865 : 163 : if (loop_bound_step > 0
1866 : 153 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1867 : 62 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1868 : 101 : else if (loop_bound_step < 0
1869 : 10 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1870 : 10 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1871 : : else
1872 : 91 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1873 : : }
1874 : : }
1875 : :
1876 : : /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1877 : : exits are resulted from short-circuit conditions that will generate an
1878 : : if_tmp. E.g.:
1879 : :
1880 : : if (foo() || global > 10)
1881 : : break;
1882 : :
1883 : : This will be translated into:
1884 : :
1885 : : BB3:
1886 : : loop header...
1887 : : BB4:
1888 : : if foo() goto BB6 else goto BB5
1889 : : BB5:
1890 : : if global > 10 goto BB6 else goto BB7
1891 : : BB6:
1892 : : goto BB7
1893 : : BB7:
1894 : : iftmp = (PHI 0(BB5), 1(BB6))
1895 : : if iftmp == 1 goto BB8 else goto BB3
1896 : : BB8:
1897 : : outside of the loop...
1898 : :
1899 : : The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1900 : : From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1901 : : exits. This function takes BB7->BB8 as input, and finds out the extra loop
1902 : : exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1903 : :
1904 : : static void
1905 : 842636 : predict_extra_loop_exits (class loop *loop, edge exit_edge)
1906 : : {
1907 : 842636 : unsigned i;
1908 : 842636 : bool check_value_one;
1909 : 842636 : gimple *lhs_def_stmt;
1910 : 842636 : gphi *phi_stmt;
1911 : 842636 : tree cmp_rhs, cmp_lhs;
1912 : :
1913 : 1685272 : gcond *cmp_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1914 : 828841 : if (!cmp_stmt)
1915 : : return;
1916 : :
1917 : 828841 : cmp_rhs = gimple_cond_rhs (cmp_stmt);
1918 : 828841 : cmp_lhs = gimple_cond_lhs (cmp_stmt);
1919 : 828841 : if (!TREE_CONSTANT (cmp_rhs)
1920 : 828841 : || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1921 : 611159 : return;
1922 : 217682 : if (TREE_CODE (cmp_lhs) != SSA_NAME)
1923 : : return;
1924 : :
1925 : : /* If check_value_one is true, only the phi_args with value '1' will lead
1926 : : to loop exit. Otherwise, only the phi_args with value '0' will lead to
1927 : : loop exit. */
1928 : 217682 : check_value_one = (((integer_onep (cmp_rhs))
1929 : 217682 : ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1930 : 217682 : ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1931 : :
1932 : 217682 : lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1933 : 217682 : if (!lhs_def_stmt)
1934 : : return;
1935 : :
1936 : 217682 : phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1937 : : if (!phi_stmt)
1938 : : return;
1939 : :
1940 : 225950 : for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1941 : : {
1942 : 152021 : edge e1;
1943 : 152021 : edge_iterator ei;
1944 : 152021 : tree val = gimple_phi_arg_def (phi_stmt, i);
1945 : 152021 : edge e = gimple_phi_arg_edge (phi_stmt, i);
1946 : :
1947 : 152021 : if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1948 : 138075 : continue;
1949 : 38752 : if ((check_value_one ^ integer_onep (val)) == 1)
1950 : 19025 : continue;
1951 : 19727 : if (EDGE_COUNT (e->src->succs) != 1)
1952 : : {
1953 : 5781 : predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1954 : : loop);
1955 : 5781 : continue;
1956 : : }
1957 : :
1958 : 30314 : FOR_EACH_EDGE (e1, ei, e->src->preds)
1959 : 16368 : predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1960 : : loop);
1961 : : }
1962 : : }
1963 : :
1964 : :
1965 : : /* Predict edge probabilities by exploiting loop structure. */
1966 : :
1967 : : static void
1968 : 275357 : predict_loops (void)
1969 : : {
1970 : 275357 : basic_block bb;
1971 : 275357 : hash_set <class loop *> with_recursion(10);
1972 : :
1973 : 5650307 : FOR_EACH_BB_FN (bb, cfun)
1974 : : {
1975 : 5374950 : gimple_stmt_iterator gsi;
1976 : 5374950 : tree decl;
1977 : :
1978 : 35766579 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1979 : 25016679 : if (is_gimple_call (gsi_stmt (gsi))
1980 : 2237240 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1981 : 27077756 : && recursive_call_p (current_function_decl, decl))
1982 : : {
1983 : 5927 : class loop *loop = bb->loop_father;
1984 : 12251 : while (loop && !with_recursion.add (loop))
1985 : 6324 : loop = loop_outer (loop);
1986 : : }
1987 : : }
1988 : :
1989 : : /* Try to predict out blocks in a loop that are not part of a
1990 : : natural loop. */
1991 : 1473869 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1992 : : {
1993 : 647798 : basic_block bb, *bbs;
1994 : 647798 : unsigned j, n_exits = 0;
1995 : 647798 : class tree_niter_desc niter_desc;
1996 : 647798 : edge ex;
1997 : 647798 : class nb_iter_bound *nb_iter;
1998 : 647798 : enum tree_code loop_bound_code = ERROR_MARK;
1999 : 647798 : tree loop_bound_step = NULL;
2000 : 647798 : tree loop_bound_var = NULL;
2001 : 647798 : tree loop_iv_base = NULL;
2002 : 647798 : gcond *stmt = NULL;
2003 : 647798 : bool recursion = with_recursion.contains (loop);
2004 : :
2005 : 647798 : auto_vec<edge> exits = get_loop_exit_edges (loop);
2006 : 2394605 : FOR_EACH_VEC_ELT (exits, j, ex)
2007 : 1099009 : if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
2008 : 891526 : n_exits ++;
2009 : 647798 : if (!n_exits)
2010 : 15724 : continue;
2011 : :
2012 : 632074 : if (dump_file && (dump_flags & TDF_DETAILS))
2013 : 538 : fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
2014 : : loop->num, recursion ? " (with recursion)" : "", n_exits);
2015 : 329 : if (dump_file && (dump_flags & TDF_DETAILS)
2016 : 632343 : && max_loop_iterations_int (loop) >= 0)
2017 : : {
2018 : 200 : fprintf (dump_file,
2019 : : "Loop %d iterates at most %i times.\n", loop->num,
2020 : 200 : (int)max_loop_iterations_int (loop));
2021 : : }
2022 : 329 : if (dump_file && (dump_flags & TDF_DETAILS)
2023 : 632343 : && likely_max_loop_iterations_int (loop) >= 0)
2024 : : {
2025 : 200 : fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
2026 : 200 : loop->num, (int)likely_max_loop_iterations_int (loop));
2027 : : }
2028 : :
2029 : 1715217 : FOR_EACH_VEC_ELT (exits, j, ex)
2030 : : {
2031 : 1083143 : tree niter = NULL;
2032 : 1083143 : HOST_WIDE_INT nitercst;
2033 : 1083143 : int max = param_max_predicted_iterations;
2034 : 1083143 : int probability;
2035 : 1083143 : enum br_predictor predictor;
2036 : 1083143 : widest_int nit;
2037 : :
2038 : 1083143 : if (unlikely_executed_edge_p (ex)
2039 : 1083143 : || (ex->flags & EDGE_ABNORMAL_CALL))
2040 : 191617 : continue;
2041 : : /* Loop heuristics do not expect exit conditional to be inside
2042 : : inner loop. We predict from innermost to outermost loop. */
2043 : 891526 : if (predicted_by_loop_heuristics_p (ex->src))
2044 : : {
2045 : 48890 : if (dump_file && (dump_flags & TDF_DETAILS))
2046 : 0 : fprintf (dump_file, "Skipping exit %i->%i because "
2047 : : "it is already predicted.\n",
2048 : 0 : ex->src->index, ex->dest->index);
2049 : 48890 : continue;
2050 : : }
2051 : 842636 : predict_extra_loop_exits (loop, ex);
2052 : :
2053 : 842636 : if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
2054 : 432894 : niter = niter_desc.niter;
2055 : 432894 : if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
2056 : 571283 : niter = loop_niter_by_eval (loop, ex);
2057 : 334 : if (dump_file && (dump_flags & TDF_DETAILS)
2058 : 842905 : && TREE_CODE (niter) == INTEGER_CST)
2059 : : {
2060 : 189 : fprintf (dump_file, "Exit %i->%i %d iterates ",
2061 : 189 : ex->src->index, ex->dest->index,
2062 : : loop->num);
2063 : 189 : print_generic_expr (dump_file, niter, TDF_SLIM);
2064 : 189 : fprintf (dump_file, " times.\n");
2065 : : }
2066 : :
2067 : 842636 : if (TREE_CODE (niter) == INTEGER_CST)
2068 : : {
2069 : 283202 : if (tree_fits_uhwi_p (niter)
2070 : 283202 : && max
2071 : 566398 : && compare_tree_int (niter, max - 1) == -1)
2072 : 200712 : nitercst = tree_to_uhwi (niter) + 1;
2073 : : else
2074 : 82490 : nitercst = max;
2075 : : predictor = PRED_LOOP_ITERATIONS;
2076 : : }
2077 : : /* If we have just one exit and we can derive some information about
2078 : : the number of iterations of the loop from the statements inside
2079 : : the loop, use it to predict this exit. */
2080 : 559434 : else if (n_exits == 1
2081 : 559434 : && estimated_stmt_executions (loop, &nit))
2082 : : {
2083 : 3 : if (wi::gtu_p (nit, max))
2084 : 1 : nitercst = max;
2085 : : else
2086 : 2 : nitercst = nit.to_shwi ();
2087 : : predictor = PRED_LOOP_ITERATIONS_GUESSED;
2088 : : }
2089 : : /* If we have likely upper bound, trust it for very small iteration
2090 : : counts. Such loops would otherwise get mispredicted by standard
2091 : : LOOP_EXIT heuristics. */
2092 : 1113338 : else if (n_exits == 1
2093 : 252663 : && likely_max_stmt_executions (loop, &nit)
2094 : 702480 : && wi::ltu_p (nit,
2095 : 285707 : RDIV (REG_BR_PROB_BASE,
2096 : : REG_BR_PROB_BASE
2097 : : - predictor_info
2098 : : [recursion
2099 : : ? PRED_LOOP_EXIT_WITH_RECURSION
2100 : : : PRED_LOOP_EXIT].hitrate)))
2101 : : {
2102 : 5524 : nitercst = nit.to_shwi ();
2103 : 5524 : predictor = PRED_LOOP_ITERATIONS_MAX;
2104 : : }
2105 : : else
2106 : : {
2107 : 553907 : if (dump_file && (dump_flags & TDF_DETAILS))
2108 : 78 : fprintf (dump_file, "Nothing known about exit %i->%i.\n",
2109 : 78 : ex->src->index, ex->dest->index);
2110 : 553907 : continue;
2111 : : }
2112 : :
2113 : 288729 : if (dump_file && (dump_flags & TDF_DETAILS))
2114 : 191 : fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
2115 : 191 : (int)nitercst, predictor_info[predictor].name);
2116 : : /* If the prediction for number of iterations is zero, do not
2117 : : predict the exit edges. */
2118 : 288729 : if (nitercst == 0)
2119 : 6 : continue;
2120 : :
2121 : 288723 : probability = RDIV (REG_BR_PROB_BASE, nitercst);
2122 : 288723 : predict_edge (ex, predictor, probability);
2123 : 1083143 : }
2124 : :
2125 : : /* Find information about loop bound variables. */
2126 : 885599 : for (nb_iter = loop->bounds; nb_iter;
2127 : 253525 : nb_iter = nb_iter->next)
2128 : 381125 : if (nb_iter->stmt
2129 : 381125 : && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2130 : : {
2131 : 127600 : stmt = as_a <gcond *> (nb_iter->stmt);
2132 : 127600 : break;
2133 : : }
2134 : 632074 : if (!stmt)
2135 : 1008948 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (loop->header));
2136 : 127600 : if (stmt)
2137 : 606410 : is_comparison_with_loop_invariant_p (stmt, loop,
2138 : : &loop_bound_var,
2139 : : &loop_bound_code,
2140 : : &loop_bound_step,
2141 : : &loop_iv_base);
2142 : :
2143 : 632074 : bbs = get_loop_body (loop);
2144 : :
2145 : 3877940 : for (j = 0; j < loop->num_nodes; j++)
2146 : : {
2147 : 3245866 : edge e;
2148 : 3245866 : edge_iterator ei;
2149 : :
2150 : 3245866 : bb = bbs[j];
2151 : :
2152 : : /* Bypass loop heuristics on continue statement. These
2153 : : statements construct loops via "non-loop" constructs
2154 : : in the source language and are better to be handled
2155 : : separately. */
2156 : 3245866 : if (predicted_by_p (bb, PRED_CONTINUE))
2157 : : {
2158 : 8398 : if (dump_file && (dump_flags & TDF_DETAILS))
2159 : 0 : fprintf (dump_file, "BB %i predicted by continue.\n",
2160 : : bb->index);
2161 : 8398 : continue;
2162 : : }
2163 : :
2164 : : /* If we already used more reliable loop exit predictors, do not
2165 : : bother with PRED_LOOP_EXIT. */
2166 : 3237468 : if (!predicted_by_loop_heuristics_p (bb))
2167 : : {
2168 : : /* For loop with many exits we don't want to predict all exits
2169 : : with the pretty large probability, because if all exits are
2170 : : considered in row, the loop would be predicted to iterate
2171 : : almost never. The code to divide probability by number of
2172 : : exits is very rough. It should compute the number of exits
2173 : : taken in each patch through function (not the overall number
2174 : : of exits that might be a lot higher for loops with wide switch
2175 : : statements in them) and compute n-th square root.
2176 : :
2177 : : We limit the minimal probability by 2% to avoid
2178 : : EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2179 : : as this was causing regression in perl benchmark containing such
2180 : : a wide loop. */
2181 : :
2182 : 5263440 : int probability = ((REG_BR_PROB_BASE
2183 : 2631720 : - predictor_info
2184 : : [recursion
2185 : 2631720 : ? PRED_LOOP_EXIT_WITH_RECURSION
2186 : 2631720 : : PRED_LOOP_EXIT].hitrate)
2187 : 2631720 : / n_exits);
2188 : 2631720 : if (probability < HITRATE (2))
2189 : : probability = HITRATE (2);
2190 : 6425356 : FOR_EACH_EDGE (e, ei, bb->succs)
2191 : 3793636 : if (e->dest->index < NUM_FIXED_BLOCKS
2192 : 3793636 : || !flow_bb_inside_loop_p (loop, e->dest))
2193 : : {
2194 : 713877 : if (dump_file && (dump_flags & TDF_DETAILS))
2195 : 89 : fprintf (dump_file,
2196 : : "Predicting exit %i->%i with prob %i.\n",
2197 : 89 : e->src->index, e->dest->index, probability);
2198 : 1420350 : predict_edge (e,
2199 : : recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2200 : : : PRED_LOOP_EXIT, probability);
2201 : : }
2202 : : }
2203 : 3237468 : if (loop_bound_var)
2204 : 2035291 : predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2205 : : loop_bound_code,
2206 : 2035291 : tree_to_shwi (loop_bound_step));
2207 : : }
2208 : :
2209 : : /* In the following code
2210 : : for (loop1)
2211 : : if (cond)
2212 : : for (loop2)
2213 : : body;
2214 : : guess that cond is unlikely. */
2215 : 632074 : if (loop_outer (loop)->num)
2216 : : {
2217 : 134510 : basic_block bb = NULL;
2218 : 134510 : edge preheader_edge = loop_preheader_edge (loop);
2219 : :
2220 : 134510 : if (single_pred_p (preheader_edge->src)
2221 : 245276 : && single_succ_p (preheader_edge->src))
2222 : 110766 : preheader_edge = single_pred_edge (preheader_edge->src);
2223 : :
2224 : : /* Pattern match fortran loop preheader:
2225 : : _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2226 : : _17 = (logical(kind=4)) _16;
2227 : : if (_17 != 0)
2228 : : goto <bb 11>;
2229 : : else
2230 : : goto <bb 13>;
2231 : :
2232 : : Loop guard branch prediction says nothing about duplicated loop
2233 : : headers produced by fortran frontend and in this case we want
2234 : : to predict paths leading to this preheader. */
2235 : :
2236 : 134510 : gcond *stmt
2237 : 269020 : = safe_dyn_cast <gcond *> (*gsi_last_bb (preheader_edge->src));
2238 : 107769 : if (stmt
2239 : 107769 : && gimple_cond_code (stmt) == NE_EXPR
2240 : 35242 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2241 : 35242 : && integer_zerop (gimple_cond_rhs (stmt)))
2242 : : {
2243 : 14846 : gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2244 : 14846 : if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2245 : 6134 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt))
2246 : 15699 : && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2247 : 853 : call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2248 : 14846 : if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2249 : 825 : && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2250 : 825 : && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2251 : 15671 : && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2252 : : == PRED_FORTRAN_LOOP_PREHEADER)
2253 : 18 : bb = preheader_edge->src;
2254 : : }
2255 : 18 : if (!bb)
2256 : : {
2257 : 134492 : if (!dominated_by_p (CDI_DOMINATORS,
2258 : 134492 : loop_outer (loop)->latch, loop->header))
2259 : 55449 : predict_paths_leading_to_edge (loop_preheader_edge (loop),
2260 : : recursion
2261 : : ? PRED_LOOP_GUARD_WITH_RECURSION
2262 : : : PRED_LOOP_GUARD,
2263 : : NOT_TAKEN,
2264 : : loop_outer (loop));
2265 : : }
2266 : : else
2267 : : {
2268 : 18 : if (!dominated_by_p (CDI_DOMINATORS,
2269 : 18 : loop_outer (loop)->latch, bb))
2270 : 0 : predict_paths_leading_to (bb,
2271 : : recursion
2272 : : ? PRED_LOOP_GUARD_WITH_RECURSION
2273 : : : PRED_LOOP_GUARD,
2274 : : NOT_TAKEN,
2275 : : loop_outer (loop));
2276 : : }
2277 : : }
2278 : :
2279 : : /* Free basic blocks from get_loop_body. */
2280 : 632074 : free (bbs);
2281 : 923155 : }
2282 : 275357 : }
2283 : :
2284 : : /* Attempt to predict probabilities of BB outgoing edges using local
2285 : : properties. */
2286 : : static void
2287 : 562917 : bb_estimate_probability_locally (basic_block bb)
2288 : : {
2289 : 562917 : rtx_insn *last_insn = BB_END (bb);
2290 : 562917 : rtx cond;
2291 : :
2292 : 562917 : if (! can_predict_insn_p (last_insn))
2293 : : return;
2294 : 146996 : cond = get_condition (last_insn, NULL, false, false);
2295 : 146996 : if (! cond)
2296 : : return;
2297 : :
2298 : : /* Try "pointer heuristic."
2299 : : A comparison ptr == 0 is predicted as false.
2300 : : Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2301 : 124104 : if (COMPARISON_P (cond)
2302 : 124104 : && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2303 : 124053 : || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2304 : : {
2305 : 52 : if (GET_CODE (cond) == EQ)
2306 : 27 : predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2307 : 25 : else if (GET_CODE (cond) == NE)
2308 : 19 : predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2309 : : }
2310 : : else
2311 : :
2312 : : /* Try "opcode heuristic."
2313 : : EQ tests are usually false and NE tests are usually true. Also,
2314 : : most quantities are positive, so we can make the appropriate guesses
2315 : : about signed comparisons against zero. */
2316 : 124052 : switch (GET_CODE (cond))
2317 : : {
2318 : 0 : case CONST_INT:
2319 : : /* Unconditional branch. */
2320 : 0 : predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2321 : 0 : cond == const0_rtx ? NOT_TAKEN : TAKEN);
2322 : 0 : break;
2323 : :
2324 : 20611 : case EQ:
2325 : 20611 : case UNEQ:
2326 : : /* Floating point comparisons appears to behave in a very
2327 : : unpredictable way because of special role of = tests in
2328 : : FP code. */
2329 : 20611 : if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2330 : : ;
2331 : : /* Comparisons with 0 are often used for booleans and there is
2332 : : nothing useful to predict about them. */
2333 : 20611 : else if (XEXP (cond, 1) == const0_rtx
2334 : 586 : || XEXP (cond, 0) == const0_rtx)
2335 : : ;
2336 : : else
2337 : 586 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2338 : : break;
2339 : :
2340 : 81531 : case NE:
2341 : 81531 : case LTGT:
2342 : : /* Floating point comparisons appears to behave in a very
2343 : : unpredictable way because of special role of = tests in
2344 : : FP code. */
2345 : 81531 : if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2346 : : ;
2347 : : /* Comparisons with 0 are often used for booleans and there is
2348 : : nothing useful to predict about them. */
2349 : 81531 : else if (XEXP (cond, 1) == const0_rtx
2350 : 76251 : || XEXP (cond, 0) == const0_rtx)
2351 : : ;
2352 : : else
2353 : 76251 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2354 : : break;
2355 : :
2356 : 0 : case ORDERED:
2357 : 0 : predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2358 : 0 : break;
2359 : :
2360 : 50 : case UNORDERED:
2361 : 50 : predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2362 : 50 : break;
2363 : :
2364 : 5335 : case LE:
2365 : 5335 : case LT:
2366 : 5335 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2367 : 0 : || XEXP (cond, 1) == constm1_rtx)
2368 : 5335 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2369 : : break;
2370 : :
2371 : 5611 : case GE:
2372 : 5611 : case GT:
2373 : 5611 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2374 : 5544 : || XEXP (cond, 1) == constm1_rtx)
2375 : 2199 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2376 : : break;
2377 : :
2378 : : default:
2379 : : break;
2380 : : }
2381 : : }
2382 : :
2383 : : /* Set edge->probability for each successor edge of BB. */
2384 : : void
2385 : 562917 : guess_outgoing_edge_probabilities (basic_block bb)
2386 : : {
2387 : 562917 : bb_estimate_probability_locally (bb);
2388 : 562917 : combine_predictions_for_insn (BB_END (bb), bb);
2389 : 562917 : }
2390 : :
2391 : : static tree expr_expected_value (tree, enum br_predictor *predictor,
2392 : : HOST_WIDE_INT *probability);
2393 : :
2394 : : /* Helper function for expr_expected_value. */
2395 : :
2396 : : static tree
2397 : 16050475 : expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2398 : : tree op1, enum br_predictor *predictor,
2399 : : HOST_WIDE_INT *probability)
2400 : : {
2401 : 16050475 : gimple *def;
2402 : :
2403 : : /* Reset returned probability value. */
2404 : 16050475 : *probability = -1;
2405 : 16050475 : *predictor = PRED_UNCONDITIONAL;
2406 : :
2407 : 16050475 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2408 : : {
2409 : 10245581 : if (TREE_CONSTANT (op0))
2410 : : return op0;
2411 : :
2412 : 10242379 : if (code == IMAGPART_EXPR)
2413 : : {
2414 : 51604 : if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2415 : : {
2416 : 49993 : def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2417 : 49993 : if (is_gimple_call (def)
2418 : 47860 : && gimple_call_internal_p (def)
2419 : 97797 : && (gimple_call_internal_fn (def)
2420 : : == IFN_ATOMIC_COMPARE_EXCHANGE))
2421 : : {
2422 : : /* Assume that any given atomic operation has low contention,
2423 : : and thus the compare-and-swap operation succeeds. */
2424 : 5521 : *predictor = PRED_COMPARE_AND_SWAP;
2425 : 5521 : return build_one_cst (TREE_TYPE (op0));
2426 : : }
2427 : : }
2428 : : }
2429 : :
2430 : 10236858 : if (code != SSA_NAME)
2431 : : return NULL_TREE;
2432 : :
2433 : 7991263 : def = SSA_NAME_DEF_STMT (op0);
2434 : :
2435 : : /* If we were already here, break the infinite cycle. */
2436 : 7991263 : bool existed_p;
2437 : 7991263 : expected_value *res
2438 : 7991263 : = &ssa_expected_value->get_or_insert (SSA_NAME_VERSION (op0),
2439 : : &existed_p);
2440 : 7991263 : if (existed_p)
2441 : : {
2442 : 1653088 : *probability = res->probability;
2443 : 1653088 : *predictor = res->predictor;
2444 : 1653088 : return res->val;
2445 : : }
2446 : 6338175 : res->val = NULL_TREE;
2447 : 6338175 : res->predictor = *predictor;
2448 : 6338175 : res->probability = *probability;
2449 : :
2450 : 6338175 : if (gphi *phi = dyn_cast <gphi *> (def))
2451 : : {
2452 : : /* All the arguments of the PHI node must have the same constant
2453 : : length. */
2454 : 921556 : int i, n = gimple_phi_num_args (phi);
2455 : 921556 : tree val = NULL;
2456 : 921556 : bool has_nonzero_edge = false;
2457 : :
2458 : : /* If we already proved that given edge is unlikely, we do not need
2459 : : to handle merging of the probabilities. */
2460 : 1849961 : for (i = 0; i < n && !has_nonzero_edge; i++)
2461 : : {
2462 : 928405 : tree arg = PHI_ARG_DEF (phi, i);
2463 : 928405 : if (arg == PHI_RESULT (phi))
2464 : 0 : continue;
2465 : 928405 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2466 : 938444 : if (!cnt.initialized_p () || cnt.nonzero_p ())
2467 : : has_nonzero_edge = true;
2468 : : }
2469 : :
2470 : 1496522 : for (i = 0; i < n; i++)
2471 : : {
2472 : 1493441 : tree arg = PHI_ARG_DEF (phi, i);
2473 : 1493441 : enum br_predictor predictor2;
2474 : :
2475 : : /* Skip self-referring parameters, since they does not change
2476 : : expected value. */
2477 : 1493441 : if (arg == PHI_RESULT (phi))
2478 : 574959 : continue;
2479 : :
2480 : : /* Skip edges which we already predicted as executing
2481 : : zero times. */
2482 : 1493441 : if (has_nonzero_edge)
2483 : : {
2484 : 1489266 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2485 : 1489266 : if (cnt.initialized_p () && !cnt.nonzero_p ())
2486 : 175 : continue;
2487 : : }
2488 : 1493266 : HOST_WIDE_INT probability2;
2489 : 1493266 : tree new_val = expr_expected_value (arg, &predictor2,
2490 : : &probability2);
2491 : : /* If we know nothing about value, give up. */
2492 : 1493266 : if (!new_val)
2493 : 918475 : return NULL;
2494 : :
2495 : : /* If this is a first edge, trust its prediction. */
2496 : 643719 : if (!val)
2497 : : {
2498 : 565540 : val = new_val;
2499 : 565540 : *predictor = predictor2;
2500 : 565540 : *probability = probability2;
2501 : 565540 : continue;
2502 : : }
2503 : : /* If there are two different values, give up. */
2504 : 78179 : if (!operand_equal_p (val, new_val, false))
2505 : : return NULL;
2506 : :
2507 : 9251 : int p1 = get_predictor_value (*predictor, *probability);
2508 : 9251 : int p2 = get_predictor_value (predictor2, probability2);
2509 : : /* If both predictors agree, it does not matter from which
2510 : : edge we enter the basic block. */
2511 : 9251 : if (*predictor == predictor2 && p1 == p2)
2512 : 9244 : continue;
2513 : : /* The general case has no precise solution, since we do not
2514 : : know probabilities of incomming edges, yet.
2515 : : Still if value is predicted over all incomming edges, we
2516 : : can hope it will be indeed the case. Conservatively
2517 : : downgrade prediction quality (so first match merging is not
2518 : : performed) and take least successful prediction. */
2519 : :
2520 : 7 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI;
2521 : 7 : *probability = MIN (p1, p2);
2522 : : }
2523 : :
2524 : 3081 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2525 : 3081 : res->val = val;
2526 : 3081 : res->predictor = *predictor;
2527 : 3081 : res->probability = *probability;
2528 : 3081 : return val;
2529 : : }
2530 : 5416619 : if (is_gimple_assign (def))
2531 : : {
2532 : 4161313 : if (gimple_assign_lhs (def) != op0)
2533 : : return NULL;
2534 : :
2535 : 4161313 : tree val = expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2536 : : gimple_assign_rhs1 (def),
2537 : : gimple_assign_rhs_code (def),
2538 : : gimple_assign_rhs2 (def),
2539 : : predictor, probability);
2540 : 4161313 : if (val)
2541 : : {
2542 : 47845 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2543 : 47845 : res->val = val;
2544 : 47845 : res->predictor = *predictor;
2545 : 47845 : res->probability = *probability;
2546 : : }
2547 : 4161313 : return val;
2548 : : }
2549 : :
2550 : 1255306 : if (is_gimple_call (def))
2551 : : {
2552 : 857229 : tree decl = gimple_call_fndecl (def);
2553 : 857229 : if (!decl)
2554 : : {
2555 : 77049 : if (gimple_call_internal_p (def)
2556 : 77049 : && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2557 : : {
2558 : 32151 : gcc_assert (gimple_call_num_args (def) == 3);
2559 : 32151 : tree val = gimple_call_arg (def, 0);
2560 : 32151 : if (TREE_CONSTANT (val))
2561 : : return val;
2562 : 32151 : tree val2 = gimple_call_arg (def, 2);
2563 : 32151 : gcc_assert (TREE_CODE (val2) == INTEGER_CST
2564 : : && tree_fits_uhwi_p (val2)
2565 : : && tree_to_uhwi (val2) < END_PREDICTORS);
2566 : 32151 : *predictor = (enum br_predictor) tree_to_uhwi (val2);
2567 : 32151 : if (*predictor == PRED_BUILTIN_EXPECT)
2568 : 8772 : *probability
2569 : 8772 : = HITRATE (param_builtin_expect_probability);
2570 : 32151 : val = gimple_call_arg (def, 1);
2571 : 32151 : res->val = val;
2572 : 32151 : res->predictor = *predictor;
2573 : 32151 : res->probability = *probability;
2574 : 32151 : return val;
2575 : : }
2576 : : return NULL;
2577 : : }
2578 : :
2579 : 780180 : if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2580 : : {
2581 : 11706 : if (predictor)
2582 : 11706 : *predictor = PRED_MALLOC_NONNULL;
2583 : : /* FIXME: This is wrong and we need to convert the logic
2584 : : to value ranges. This makes predictor to assume that
2585 : : malloc always returns (size_t)1 which is not the same
2586 : : as returning non-NULL. */
2587 : 11706 : tree val = fold_convert (type, boolean_true_node);
2588 : 11706 : res->val = val;
2589 : 11706 : res->predictor = *predictor;
2590 : 11706 : res->probability = *probability;
2591 : 11706 : return val;
2592 : : }
2593 : :
2594 : 768474 : if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2595 : 408769 : switch (DECL_FUNCTION_CODE (decl))
2596 : : {
2597 : 71446 : case BUILT_IN_EXPECT:
2598 : 71446 : {
2599 : 71446 : tree val;
2600 : 71446 : if (gimple_call_num_args (def) != 2)
2601 : : return NULL;
2602 : 71446 : val = gimple_call_arg (def, 0);
2603 : 71446 : if (TREE_CONSTANT (val))
2604 : : return val;
2605 : 71446 : *predictor = PRED_BUILTIN_EXPECT;
2606 : 71446 : *probability
2607 : 71446 : = HITRATE (param_builtin_expect_probability);
2608 : 71446 : val = gimple_call_arg (def, 1);
2609 : 71446 : res->val = val;
2610 : 71446 : res->predictor = *predictor;
2611 : 71446 : res->probability = *probability;
2612 : 71446 : return val;
2613 : : }
2614 : 19 : case BUILT_IN_EXPECT_WITH_PROBABILITY:
2615 : 19 : {
2616 : 19 : tree val;
2617 : 19 : if (gimple_call_num_args (def) != 3)
2618 : : return NULL;
2619 : 19 : val = gimple_call_arg (def, 0);
2620 : 19 : if (TREE_CONSTANT (val))
2621 : : {
2622 : 0 : res->val = val;
2623 : 0 : res->predictor = *predictor;
2624 : 0 : res->probability = *probability;
2625 : 0 : return val;
2626 : : }
2627 : : /* Compute final probability as:
2628 : : probability * REG_BR_PROB_BASE. */
2629 : 19 : tree prob = gimple_call_arg (def, 2);
2630 : 19 : tree t = TREE_TYPE (prob);
2631 : 19 : tree base = build_int_cst (integer_type_node,
2632 : : REG_BR_PROB_BASE);
2633 : 19 : base = build_real_from_int_cst (t, base);
2634 : 19 : tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2635 : : MULT_EXPR, t, prob, base);
2636 : 19 : if (TREE_CODE (r) != REAL_CST)
2637 : : {
2638 : 1 : error_at (gimple_location (def),
2639 : : "probability %qE must be "
2640 : : "constant floating-point expression", prob);
2641 : 1 : return NULL;
2642 : : }
2643 : 18 : HOST_WIDE_INT probi
2644 : 18 : = real_to_integer (TREE_REAL_CST_PTR (r));
2645 : 18 : if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2646 : : {
2647 : 17 : *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2648 : 17 : *probability = probi;
2649 : : }
2650 : : else
2651 : 1 : error_at (gimple_location (def),
2652 : : "probability %qE is outside "
2653 : : "the range [0.0, 1.0]", prob);
2654 : :
2655 : 18 : val = gimple_call_arg (def, 1);
2656 : 18 : res->val = val;
2657 : 18 : res->predictor = *predictor;
2658 : 18 : res->probability = *probability;
2659 : 18 : return val;
2660 : : }
2661 : :
2662 : 5275 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2663 : 5275 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2664 : 5275 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2665 : 5275 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2666 : 5275 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2667 : 5275 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2668 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2669 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2670 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2671 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2672 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2673 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2674 : 5275 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2675 : : /* Assume that any given atomic operation has low contention,
2676 : : and thus the compare-and-swap operation succeeds. */
2677 : 5275 : *predictor = PRED_COMPARE_AND_SWAP;
2678 : 5275 : res->val = boolean_true_node;
2679 : 5275 : res->predictor = *predictor;
2680 : 5275 : res->probability = *probability;
2681 : 5275 : return boolean_true_node;
2682 : 1902 : case BUILT_IN_REALLOC:
2683 : 1902 : case BUILT_IN_GOMP_REALLOC:
2684 : 1902 : if (predictor)
2685 : 1902 : *predictor = PRED_MALLOC_NONNULL;
2686 : : /* FIXME: This is wrong and we need to convert the logic
2687 : : to value ranges. */
2688 : 1902 : res->val = fold_convert (type, boolean_true_node);
2689 : 1902 : res->predictor = *predictor;
2690 : 1902 : res->probability = *probability;
2691 : 1902 : return res->val;
2692 : : default:
2693 : : break;
2694 : : }
2695 : : }
2696 : :
2697 : 1087909 : return NULL;
2698 : : }
2699 : :
2700 : 5804894 : if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2701 : : {
2702 : 5385847 : tree res;
2703 : 5385847 : tree nop0 = op0;
2704 : 5385847 : tree nop1 = op1;
2705 : :
2706 : : /* First handle situation where single op is enough to determine final
2707 : : value. In this case we can do better job by avoiding the prediction
2708 : : merging. */
2709 : 5385847 : if (TREE_CODE (op0) != INTEGER_CST)
2710 : : {
2711 : : /* See if expected value of op0 is good enough to determine the result. */
2712 : 5361792 : nop0 = expr_expected_value (op0, predictor, probability);
2713 : 5361792 : if (nop0
2714 : 137068 : && (res = fold_build2 (code, type, nop0, op1)) != NULL
2715 : 5498860 : && TREE_CODE (res) == INTEGER_CST)
2716 : : /* We are now getting conservative probability. Consider for
2717 : : example:
2718 : : op0 * op1
2719 : : If op0 is 0 with probability p, then we will ignore the
2720 : : posibility that op0 != 0 and op1 == 0. It does not seem to be
2721 : : worthwhile to downgrade prediciton quality for this. */
2722 : : return res;
2723 : 5230437 : if (!nop0)
2724 : 5248779 : nop0 = op0;
2725 : : }
2726 : 5254492 : enum br_predictor predictor2 = PRED_UNCONDITIONAL;
2727 : 5254492 : HOST_WIDE_INT probability2 = -1;
2728 : 5254492 : if (TREE_CODE (op1) != INTEGER_CST)
2729 : : {
2730 : : /* See if expected value of op1 is good enough to determine the result. */
2731 : 1603833 : nop1 = expr_expected_value (op1, &predictor2, &probability2);
2732 : 1603833 : if (nop1
2733 : 226110 : && (res = fold_build2 (code, type, op0, nop1)) != NULL
2734 : 1829943 : && TREE_CODE (res) == INTEGER_CST)
2735 : : {
2736 : : /* Similarly as above we now get conservative probability. */
2737 : 58 : *predictor = predictor2;
2738 : 58 : *probability = probability2;
2739 : 58 : return res;
2740 : : }
2741 : 1603775 : if (!nop1)
2742 : 5028382 : nop1 = op1;
2743 : : }
2744 : : /* We already checked if folding one of arguments to constant is good
2745 : : enough. Consequently failing to fold both means that we will not
2746 : : succeed determining the value. */
2747 : 5254434 : if (nop0 == op0 || nop1 == op1)
2748 : : return NULL;
2749 : : /* Finally see if we have two known values. */
2750 : 242 : res = fold_build2 (code, type, nop0, nop1);
2751 : 242 : if (TREE_CODE (res) == INTEGER_CST)
2752 : : {
2753 : 167 : HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2754 : 167 : HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2755 : :
2756 : : /* If one of predictions is sure, such as PRED_UNCONDITIONAL, we
2757 : : can ignore it. */
2758 : 167 : if (p2 == PROB_ALWAYS)
2759 : : return res;
2760 : 147 : if (p1 == PROB_ALWAYS)
2761 : : {
2762 : 1 : *predictor = predictor2;
2763 : 1 : *probability = probability2;
2764 : 1 : return res;
2765 : : }
2766 : : /* Combine binary predictions.
2767 : : Since we do not know about independence of predictors, we
2768 : : can not determine value precisely. */
2769 : 146 : *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2770 : : /* If we no longer track useful information, give up. */
2771 : 146 : if (!*probability)
2772 : : return NULL;
2773 : : /* Otherwise mark that prediction is a result of combining
2774 : : different heuristics, since we do not want it to participate
2775 : : in first match merging. It is no longer reliable since
2776 : : we do not know if the probabilities are indpenendet. */
2777 : 146 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS;
2778 : :
2779 : 146 : return res;
2780 : : }
2781 : : return NULL;
2782 : : }
2783 : 419047 : if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2784 : : {
2785 : 417877 : tree res;
2786 : 417877 : op0 = expr_expected_value (op0, predictor, probability);
2787 : 417877 : if (!op0)
2788 : : return NULL;
2789 : 36944 : res = fold_build1 (code, type, op0);
2790 : 36944 : if (TREE_CONSTANT (res))
2791 : : return res;
2792 : : return NULL;
2793 : : }
2794 : : return NULL;
2795 : : }
2796 : :
2797 : : /* Return constant EXPR will likely have at execution time, NULL if unknown.
2798 : : The function is used by builtin_expect branch predictor so the evidence
2799 : : must come from this construct and additional possible constant folding.
2800 : :
2801 : : We may want to implement more involved value guess (such as value range
2802 : : propagation based prediction), but such tricks shall go to new
2803 : : implementation. */
2804 : :
2805 : : static tree
2806 : 8906281 : expr_expected_value (tree expr, enum br_predictor *predictor,
2807 : : HOST_WIDE_INT *probability)
2808 : : {
2809 : 8906281 : enum tree_code code;
2810 : 8906281 : tree op0, op1;
2811 : :
2812 : 8906281 : if (TREE_CONSTANT (expr))
2813 : : {
2814 : 867202 : *predictor = PRED_UNCONDITIONAL;
2815 : 867202 : *probability = -1;
2816 : 867202 : return expr;
2817 : : }
2818 : :
2819 : 8039079 : extract_ops_from_tree (expr, &code, &op0, &op1);
2820 : 8039079 : return expr_expected_value_1 (TREE_TYPE (expr),
2821 : 8039079 : op0, code, op1, predictor, probability);
2822 : : }
2823 : :
2824 : :
2825 : : /* Return probability of a PREDICTOR. If the predictor has variable
2826 : : probability return passed PROBABILITY. */
2827 : :
2828 : : static HOST_WIDE_INT
2829 : 148281 : get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2830 : : {
2831 : 148281 : switch (predictor)
2832 : : {
2833 : 80564 : case PRED_BUILTIN_EXPECT:
2834 : 80564 : case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2835 : 80564 : case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
2836 : 80564 : case PRED_COMBINED_VALUE_PREDICTIONS:
2837 : 80564 : gcc_assert (probability != -1);
2838 : : return probability;
2839 : 67717 : default:
2840 : 67717 : gcc_assert (probability == -1);
2841 : 67717 : return predictor_info[(int) predictor].hitrate;
2842 : : }
2843 : : }
2844 : :
2845 : : /* Predict using opcode of the last statement in basic block. */
2846 : : static void
2847 : 11684594 : tree_predict_by_opcode (basic_block bb)
2848 : : {
2849 : 11684594 : edge then_edge;
2850 : 11684594 : tree op0, op1;
2851 : 11684594 : tree type;
2852 : 11684594 : tree val;
2853 : 11684594 : enum tree_code cmp;
2854 : 11684594 : edge_iterator ei;
2855 : 11684594 : enum br_predictor predictor;
2856 : 11684594 : HOST_WIDE_INT probability;
2857 : :
2858 : 11684594 : gimple *stmt = *gsi_last_bb (bb);
2859 : 11684594 : if (!stmt)
2860 : 7834511 : return;
2861 : :
2862 : 11151979 : if (gswitch *sw = dyn_cast <gswitch *> (stmt))
2863 : : {
2864 : 29513 : tree index = gimple_switch_index (sw);
2865 : 29513 : tree val = expr_expected_value (index, &predictor, &probability);
2866 : 29513 : if (val && TREE_CODE (val) == INTEGER_CST)
2867 : : {
2868 : 4 : edge e = find_taken_edge_switch_expr (sw, val);
2869 : 4 : if (predictor == PRED_BUILTIN_EXPECT)
2870 : : {
2871 : 4 : int percent = param_builtin_expect_probability;
2872 : 4 : gcc_assert (percent >= 0 && percent <= 100);
2873 : 4 : predict_edge (e, PRED_BUILTIN_EXPECT,
2874 : 4 : HITRATE (percent));
2875 : : }
2876 : : else
2877 : 0 : predict_edge_def (e, predictor, TAKEN);
2878 : : }
2879 : : }
2880 : :
2881 : 11151979 : if (gimple_code (stmt) != GIMPLE_COND)
2882 : : return;
2883 : 3986734 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
2884 : 3986734 : if (then_edge->flags & EDGE_TRUE_VALUE)
2885 : : break;
2886 : 3850083 : op0 = gimple_cond_lhs (stmt);
2887 : 3850083 : op1 = gimple_cond_rhs (stmt);
2888 : 3850083 : cmp = gimple_cond_code (stmt);
2889 : 3850083 : type = TREE_TYPE (op0);
2890 : 3850083 : val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1,
2891 : : &predictor, &probability);
2892 : 3850083 : if (val && TREE_CODE (val) == INTEGER_CST)
2893 : : {
2894 : 129445 : HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2895 : 129445 : if (integer_zerop (val))
2896 : 104120 : prob = REG_BR_PROB_BASE - prob;
2897 : 129445 : predict_edge (then_edge, predictor, prob);
2898 : : }
2899 : : /* Try "pointer heuristic."
2900 : : A comparison ptr == 0 is predicted as false.
2901 : : Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2902 : 3850083 : if (POINTER_TYPE_P (type))
2903 : : {
2904 : 571486 : if (cmp == EQ_EXPR)
2905 : 227384 : predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2906 : 344102 : else if (cmp == NE_EXPR)
2907 : 323335 : predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2908 : : }
2909 : : else
2910 : :
2911 : : /* Try "opcode heuristic."
2912 : : EQ tests are usually false and NE tests are usually true. Also,
2913 : : most quantities are positive, so we can make the appropriate guesses
2914 : : about signed comparisons against zero. */
2915 : 3278597 : switch (cmp)
2916 : : {
2917 : 885595 : case EQ_EXPR:
2918 : 885595 : case UNEQ_EXPR:
2919 : : /* Floating point comparisons appears to behave in a very
2920 : : unpredictable way because of special role of = tests in
2921 : : FP code. */
2922 : 885595 : if (FLOAT_TYPE_P (type))
2923 : : ;
2924 : : /* Comparisons with 0 are often used for booleans and there is
2925 : : nothing useful to predict about them. */
2926 : 874293 : else if (integer_zerop (op0) || integer_zerop (op1))
2927 : : ;
2928 : : else
2929 : 352296 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2930 : : break;
2931 : :
2932 : 1568759 : case NE_EXPR:
2933 : 1568759 : case LTGT_EXPR:
2934 : : /* Floating point comparisons appears to behave in a very
2935 : : unpredictable way because of special role of = tests in
2936 : : FP code. */
2937 : 1568759 : if (FLOAT_TYPE_P (type))
2938 : : ;
2939 : : /* Comparisons with 0 are often used for booleans and there is
2940 : : nothing useful to predict about them. */
2941 : 1453959 : else if (integer_zerop (op0)
2942 : 1453959 : || integer_zerop (op1))
2943 : : ;
2944 : : else
2945 : 531105 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2946 : : break;
2947 : :
2948 : 2305 : case ORDERED_EXPR:
2949 : 2305 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2950 : 2305 : break;
2951 : :
2952 : 2407 : case UNORDERED_EXPR:
2953 : 2407 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2954 : 2407 : break;
2955 : :
2956 : 344007 : case LE_EXPR:
2957 : 344007 : case LT_EXPR:
2958 : 344007 : if (integer_zerop (op1)
2959 : 281318 : || integer_onep (op1)
2960 : 274024 : || integer_all_onesp (op1)
2961 : 273968 : || real_zerop (op1)
2962 : 270802 : || real_onep (op1)
2963 : 614417 : || real_minus_onep (op1))
2964 : 73601 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2965 : : break;
2966 : :
2967 : 466649 : case GE_EXPR:
2968 : 466649 : case GT_EXPR:
2969 : 466649 : if (integer_zerop (op1)
2970 : 401644 : || integer_onep (op1)
2971 : 390397 : || integer_all_onesp (op1)
2972 : 390123 : || real_zerop (op1)
2973 : 388624 : || real_onep (op1)
2974 : 854448 : || real_minus_onep (op1))
2975 : 78874 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2976 : : break;
2977 : :
2978 : : default:
2979 : : break;
2980 : : }
2981 : : }
2982 : :
2983 : : /* Returns TRUE if the STMT is exit(0) like statement. */
2984 : :
2985 : : static bool
2986 : 815902 : is_exit_with_zero_arg (const gimple *stmt)
2987 : : {
2988 : : /* This is not exit, _exit or _Exit. */
2989 : 815902 : if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2990 : 812295 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2991 : 1628175 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2992 : : return false;
2993 : :
2994 : : /* Argument is an interger zero. */
2995 : 3629 : return integer_zerop (gimple_call_arg (stmt, 0));
2996 : : }
2997 : :
2998 : : /* Try to guess whether the value of return means error code. */
2999 : :
3000 : : static enum br_predictor
3001 : 652191 : return_prediction (tree val, enum prediction *prediction)
3002 : : {
3003 : : /* VOID. */
3004 : 652191 : if (!val)
3005 : : return PRED_NO_PREDICTION;
3006 : : /* Different heuristics for pointers and scalars. */
3007 : 652191 : if (POINTER_TYPE_P (TREE_TYPE (val)))
3008 : : {
3009 : : /* NULL is usually not returned. */
3010 : 140070 : if (integer_zerop (val))
3011 : : {
3012 : 27902 : *prediction = NOT_TAKEN;
3013 : 27902 : return PRED_NULL_RETURN;
3014 : : }
3015 : : }
3016 : 512121 : else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
3017 : : {
3018 : : /* Negative return values are often used to indicate
3019 : : errors. */
3020 : 410703 : if (TREE_CODE (val) == INTEGER_CST
3021 : 410703 : && tree_int_cst_sgn (val) < 0)
3022 : : {
3023 : 12034 : *prediction = NOT_TAKEN;
3024 : 12034 : return PRED_NEGATIVE_RETURN;
3025 : : }
3026 : : /* Constant return values seems to be commonly taken.
3027 : : Zero/one often represent booleans so exclude them from the
3028 : : heuristics. */
3029 : 398669 : if (TREE_CONSTANT (val)
3030 : 398669 : && (!integer_zerop (val) && !integer_onep (val)))
3031 : : {
3032 : 69361 : *prediction = NOT_TAKEN;
3033 : 69361 : return PRED_CONST_RETURN;
3034 : : }
3035 : : }
3036 : : return PRED_NO_PREDICTION;
3037 : : }
3038 : :
3039 : : /* Return zero if phi result could have values other than -1, 0 or 1,
3040 : : otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
3041 : : values are used or likely. */
3042 : :
3043 : : static int
3044 : 62715 : zero_one_minusone (gphi *phi, int limit)
3045 : : {
3046 : 62715 : int phi_num_args = gimple_phi_num_args (phi);
3047 : 62715 : int ret = 0;
3048 : 189950 : for (int i = 0; i < phi_num_args; i++)
3049 : : {
3050 : 137956 : tree t = PHI_ARG_DEF (phi, i);
3051 : 137956 : if (TREE_CODE (t) != INTEGER_CST)
3052 : 68343 : continue;
3053 : 69613 : wide_int w = wi::to_wide (t);
3054 : 69613 : if (w == -1)
3055 : 4273 : ret |= 1;
3056 : 65340 : else if (w == 0)
3057 : 34150 : ret |= 2;
3058 : 31190 : else if (w == 1)
3059 : 20469 : ret |= 4;
3060 : : else
3061 : 10721 : return 0;
3062 : 69613 : }
3063 : 107598 : for (int i = 0; i < phi_num_args; i++)
3064 : : {
3065 : 91016 : tree t = PHI_ARG_DEF (phi, i);
3066 : 91016 : if (TREE_CODE (t) == INTEGER_CST)
3067 : 53839 : continue;
3068 : 37177 : if (TREE_CODE (t) != SSA_NAME)
3069 : : return 0;
3070 : 37177 : gimple *g = SSA_NAME_DEF_STMT (t);
3071 : 37177 : if (gimple_code (g) == GIMPLE_PHI && limit > 0)
3072 : 12265 : if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
3073 : : {
3074 : 449 : ret |= r;
3075 : 449 : continue;
3076 : : }
3077 : 36728 : if (!is_gimple_assign (g))
3078 : : return 0;
3079 : 13795 : if (gimple_assign_cast_p (g))
3080 : : {
3081 : 3736 : tree rhs1 = gimple_assign_rhs1 (g);
3082 : 3736 : if (TREE_CODE (rhs1) != SSA_NAME
3083 : 3736 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
3084 : 3658 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
3085 : 5053 : || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3086 : : return 0;
3087 : 1316 : ret |= (2 | 4);
3088 : 1316 : continue;
3089 : 1316 : }
3090 : 10059 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
3091 : : return 0;
3092 : 0 : ret |= (2 | 4);
3093 : : }
3094 : : return ret;
3095 : : }
3096 : :
3097 : : /* Find the basic block with return expression and look up for possible
3098 : : return value trying to apply RETURN_PREDICTION heuristics. */
3099 : : static void
3100 : 2510856 : apply_return_prediction (void)
3101 : : {
3102 : 2510856 : greturn *return_stmt = NULL;
3103 : 2510856 : tree return_val;
3104 : 2510856 : edge e;
3105 : 2510856 : gphi *phi;
3106 : 2510856 : int phi_num_args, i;
3107 : 2510856 : enum br_predictor pred;
3108 : 2510856 : enum prediction direction;
3109 : 2510856 : edge_iterator ei;
3110 : :
3111 : 2574351 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3112 : : {
3113 : 5152557 : if (greturn *last = safe_dyn_cast <greturn *> (*gsi_last_bb (e->src)))
3114 : : {
3115 : : return_stmt = last;
3116 : : break;
3117 : : }
3118 : : }
3119 : 2510856 : if (!e)
3120 : 2329404 : return;
3121 : 2481402 : return_val = gimple_return_retval (return_stmt);
3122 : 2481402 : if (!return_val)
3123 : : return;
3124 : 1391190 : if (TREE_CODE (return_val) != SSA_NAME
3125 : 1004724 : || !SSA_NAME_DEF_STMT (return_val)
3126 : 2395914 : || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
3127 : : return;
3128 : 182046 : phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
3129 : 182046 : phi_num_args = gimple_phi_num_args (phi);
3130 : 182046 : pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
3131 : :
3132 : : /* Avoid the case where the function returns -1, 0 and 1 values and
3133 : : nothing else. Those could be qsort etc. comparison functions
3134 : : where the negative return isn't less probable than positive.
3135 : : For this require that the function returns at least -1 or 1
3136 : : or -1 and a boolean value or comparison result, so that functions
3137 : : returning just -1 and 0 are treated as if -1 represents error value. */
3138 : 362374 : if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
3139 : 127689 : && !TYPE_UNSIGNED (TREE_TYPE (return_val))
3140 : 232496 : && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
3141 : 50450 : if (int r = zero_one_minusone (phi, 3))
3142 : 16133 : if ((r & (1 | 4)) == (1 | 4))
3143 : : return;
3144 : :
3145 : : /* Avoid the degenerate case where all return values form the function
3146 : : belongs to same category (ie they are all positive constants)
3147 : : so we can hardly say something about them. */
3148 : 536710 : for (i = 1; i < phi_num_args; i++)
3149 : 386332 : if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
3150 : : break;
3151 : 181452 : if (i != phi_num_args)
3152 : 114887 : for (i = 0; i < phi_num_args; i++)
3153 : : {
3154 : 83813 : pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
3155 : 83813 : if (pred != PRED_NO_PREDICTION)
3156 : 40580 : predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
3157 : : direction);
3158 : : }
3159 : : }
3160 : :
3161 : : /* Look for basic block that contains unlikely to happen events
3162 : : (such as noreturn calls) and mark all paths leading to execution
3163 : : of this basic blocks as unlikely. */
3164 : :
3165 : : static void
3166 : 2510856 : tree_bb_level_predictions (void)
3167 : : {
3168 : 2510856 : basic_block bb;
3169 : 2510856 : bool has_return_edges = false;
3170 : 2510856 : edge e;
3171 : 2510856 : edge_iterator ei;
3172 : :
3173 : 2580469 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3174 : 2549744 : if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3175 : : {
3176 : : has_return_edges = true;
3177 : : break;
3178 : : }
3179 : :
3180 : 2510856 : apply_return_prediction ();
3181 : :
3182 : 14057257 : FOR_EACH_BB_FN (bb, cfun)
3183 : : {
3184 : 11546401 : gimple_stmt_iterator gsi;
3185 : :
3186 : 92330283 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3187 : : {
3188 : 69237481 : gimple *stmt = gsi_stmt (gsi);
3189 : 69237481 : tree decl;
3190 : :
3191 : 69237481 : if (is_gimple_call (stmt))
3192 : : {
3193 : 6101988 : if (gimple_call_noreturn_p (stmt)
3194 : 880236 : && has_return_edges
3195 : 6917890 : && !is_exit_with_zero_arg (stmt))
3196 : 813541 : predict_paths_leading_to (bb, PRED_NORETURN,
3197 : : NOT_TAKEN);
3198 : 6101988 : decl = gimple_call_fndecl (stmt);
3199 : 6101988 : if (decl
3200 : 11847405 : && lookup_attribute ("cold",
3201 : 5745417 : DECL_ATTRIBUTES (decl)))
3202 : 504285 : predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3203 : : NOT_TAKEN);
3204 : 6101988 : if (decl && recursive_call_p (current_function_decl, decl))
3205 : 9767 : predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3206 : : NOT_TAKEN);
3207 : : }
3208 : 63135493 : else if (gimple_code (stmt) == GIMPLE_PREDICT)
3209 : : {
3210 : 469109 : predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
3211 : : gimple_predict_outcome (stmt));
3212 : : /* Keep GIMPLE_PREDICT around so early inlining will propagate
3213 : : hints to callers. */
3214 : : }
3215 : : }
3216 : : }
3217 : 2510856 : }
3218 : :
3219 : : /* Callback for hash_map::traverse, asserts that the pointer map is
3220 : : empty. */
3221 : :
3222 : : bool
3223 : 3758153 : assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3224 : : void *)
3225 : : {
3226 : 3758153 : gcc_assert (!value);
3227 : 3758153 : return true;
3228 : : }
3229 : :
3230 : : /* Predict branch probabilities and estimate profile for basic block BB.
3231 : : When LOCAL_ONLY is set do not use any global properties of CFG. */
3232 : :
3233 : : static void
3234 : 11684594 : tree_estimate_probability_bb (basic_block bb, bool local_only)
3235 : : {
3236 : 11684594 : edge e;
3237 : 11684594 : edge_iterator ei;
3238 : :
3239 : 28008855 : FOR_EACH_EDGE (e, ei, bb->succs)
3240 : : {
3241 : : /* Look for block we are guarding (ie we dominate it,
3242 : : but it doesn't postdominate us). */
3243 : 12899165 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3244 : 12899150 : && !local_only
3245 : 12731903 : && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3246 : 24719103 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3247 : : {
3248 : 6545702 : gimple_stmt_iterator bi;
3249 : :
3250 : : /* The call heuristic claims that a guarded function call
3251 : : is improbable. This is because such calls are often used
3252 : : to signal exceptional situations such as printing error
3253 : : messages. */
3254 : 37506935 : for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
3255 : 24415531 : gsi_next (&bi))
3256 : : {
3257 : 26880754 : gimple *stmt = gsi_stmt (bi);
3258 : 26880754 : if (is_gimple_call (stmt)
3259 : 3064209 : && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
3260 : : /* Constant and pure calls are hardly used to signalize
3261 : : something exceptional. */
3262 : 29699036 : && gimple_has_side_effects (stmt))
3263 : : {
3264 : 2465223 : if (gimple_call_fndecl (stmt))
3265 : 2400574 : predict_edge_def (e, PRED_CALL, NOT_TAKEN);
3266 : 64649 : else if (virtual_method_call_p (gimple_call_fn (stmt)))
3267 : 14688 : predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
3268 : : else
3269 : 49961 : predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
3270 : : break;
3271 : : }
3272 : : }
3273 : : }
3274 : : }
3275 : 11684594 : tree_predict_by_opcode (bb);
3276 : 11684594 : }
3277 : :
3278 : : /* Predict branch probabilities and estimate profile of the tree CFG.
3279 : : This function can be called from the loop optimizers to recompute
3280 : : the profile information.
3281 : : If DRY_RUN is set, do not modify CFG and only produce dump files. */
3282 : :
3283 : : void
3284 : 2510856 : tree_estimate_probability (bool dry_run)
3285 : : {
3286 : 2510856 : basic_block bb;
3287 : :
3288 : 2510856 : connect_infinite_loops_to_exit ();
3289 : : /* We use loop_niter_by_eval, which requires that the loops have
3290 : : preheaders. */
3291 : 2510856 : create_preheaders (CP_SIMPLE_PREHEADERS);
3292 : 2510856 : calculate_dominance_info (CDI_POST_DOMINATORS);
3293 : : /* Decide which edges are known to be unlikely. This improves later
3294 : : branch prediction. */
3295 : 2510856 : if (!dry_run)
3296 : 2510844 : determine_unlikely_bbs ();
3297 : :
3298 : 2510856 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3299 : 2510856 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3300 : :
3301 : 2510856 : tree_bb_level_predictions ();
3302 : 2510856 : record_loop_exits ();
3303 : :
3304 : 5021712 : if (number_of_loops (cfun) > 1)
3305 : 275357 : predict_loops ();
3306 : :
3307 : 14057257 : FOR_EACH_BB_FN (bb, cfun)
3308 : 11546401 : tree_estimate_probability_bb (bb, false);
3309 : :
3310 : 14057257 : FOR_EACH_BB_FN (bb, cfun)
3311 : 11546401 : combine_predictions_for_bb (bb, dry_run);
3312 : :
3313 : 2510856 : if (flag_checking)
3314 : 6268981 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3315 : :
3316 : 5021712 : delete bb_predictions;
3317 : 2510856 : bb_predictions = NULL;
3318 : 5021712 : delete ssa_expected_value;
3319 : 2510856 : ssa_expected_value = NULL;
3320 : :
3321 : 2510856 : if (!dry_run
3322 : 2510844 : && profile_status_for_fn (cfun) != PROFILE_READ)
3323 : 2510844 : estimate_bb_frequencies ();
3324 : 2510856 : free_dominance_info (CDI_POST_DOMINATORS);
3325 : 2510856 : remove_fake_exit_edges ();
3326 : 2510856 : }
3327 : :
3328 : : /* Set edge->probability for each successor edge of BB. */
3329 : : void
3330 : 138193 : tree_guess_outgoing_edge_probabilities (basic_block bb)
3331 : : {
3332 : 138193 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3333 : 138193 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3334 : 138193 : tree_estimate_probability_bb (bb, true);
3335 : 138193 : combine_predictions_for_bb (bb, false);
3336 : 138193 : if (flag_checking)
3337 : 138193 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3338 : 276386 : delete bb_predictions;
3339 : 138193 : bb_predictions = NULL;
3340 : 276386 : delete ssa_expected_value;
3341 : 138193 : ssa_expected_value = NULL;
3342 : 138193 : }
3343 : :
3344 : : /* Filter function predicate that returns true for a edge predicate P
3345 : : if its edge is equal to DATA. */
3346 : :
3347 : : static bool
3348 : 8 : not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
3349 : : {
3350 : 8 : return p->ep_edge != (edge)data || p->ep_predictor != PRED_LOOP_GUARD;
3351 : : }
3352 : :
3353 : : /* Predict edge E with PRED unless it is already predicted by some predictor
3354 : : considered equivalent. */
3355 : :
3356 : : static void
3357 : 1394241 : maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3358 : : {
3359 : 1394241 : if (edge_predicted_by_p (e, pred, taken))
3360 : : return;
3361 : 1389906 : if (pred == PRED_LOOP_GUARD
3362 : 1389906 : && edge_predicted_by_p (e, PRED_LOOP_GUARD_WITH_RECURSION, taken))
3363 : : return;
3364 : : /* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3365 : 1389898 : if (pred == PRED_LOOP_GUARD_WITH_RECURSION)
3366 : : {
3367 : 15 : edge_prediction **preds = bb_predictions->get (e->src);
3368 : 15 : if (preds)
3369 : 4 : filter_predictions (preds, not_loop_guard_equal_edge_p, e);
3370 : : }
3371 : 1389898 : predict_edge_def (e, pred, taken);
3372 : : }
3373 : : /* Predict edges to successors of CUR whose sources are not postdominated by
3374 : : BB by PRED and recurse to all postdominators. */
3375 : :
3376 : : static void
3377 : 2348349 : predict_paths_for_bb (basic_block cur, basic_block bb,
3378 : : enum br_predictor pred,
3379 : : enum prediction taken,
3380 : : bitmap visited, class loop *in_loop = NULL)
3381 : : {
3382 : 2348349 : edge e;
3383 : 2348349 : edge_iterator ei;
3384 : 2348349 : basic_block son;
3385 : :
3386 : : /* If we exited the loop or CUR is unconditional in the loop, there is
3387 : : nothing to do. */
3388 : 2348349 : if (in_loop
3389 : 2348349 : && (!flow_bb_inside_loop_p (in_loop, cur)
3390 : 72102 : || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3391 : 10409 : return;
3392 : :
3393 : : /* We are looking for all edges forming edge cut induced by
3394 : : set of all blocks postdominated by BB. */
3395 : 5194025 : FOR_EACH_EDGE (e, ei, cur->preds)
3396 : 2856085 : if (e->src->index >= NUM_FIXED_BLOCKS
3397 : 2856085 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3398 : : {
3399 : 2196314 : edge e2;
3400 : 2196314 : edge_iterator ei2;
3401 : 2196314 : bool found = false;
3402 : :
3403 : : /* Ignore fake edges and eh, we predict them as not taken anyway. */
3404 : 2196314 : if (unlikely_executed_edge_p (e))
3405 : 803160 : continue;
3406 : 1393154 : gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3407 : :
3408 : : /* See if there is an edge from e->src that is not abnormal
3409 : : and does not lead to BB and does not exit the loop. */
3410 : 2507989 : FOR_EACH_EDGE (e2, ei2, e->src->succs)
3411 : 2479349 : if (e2 != e
3412 : 1401633 : && !unlikely_executed_edge_p (e2)
3413 : 1373535 : && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3414 : 3846709 : && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3415 : : {
3416 : : found = true;
3417 : : break;
3418 : : }
3419 : :
3420 : : /* If there is non-abnormal path leaving e->src, predict edge
3421 : : using predictor. Otherwise we need to look for paths
3422 : : leading to e->src.
3423 : :
3424 : : The second may lead to infinite loop in the case we are predicitng
3425 : : regions that are only reachable by abnormal edges. We simply
3426 : : prevent visiting given BB twice. */
3427 : 1393154 : if (found)
3428 : 1364514 : maybe_predict_edge (e, pred, taken);
3429 : 28640 : else if (bitmap_set_bit (visited, e->src->index))
3430 : 28602 : predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3431 : : }
3432 : 2337940 : for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3433 : 2800251 : son;
3434 : 462311 : son = next_dom_son (CDI_POST_DOMINATORS, son))
3435 : 462311 : predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3436 : : }
3437 : :
3438 : : /* Sets branch probabilities according to PREDiction and
3439 : : FLAGS. */
3440 : :
3441 : : static void
3442 : 1796702 : predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3443 : : enum prediction taken, class loop *in_loop)
3444 : : {
3445 : 1796702 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3446 : 1796702 : }
3447 : :
3448 : : /* Like predict_paths_leading_to but take edge instead of basic block. */
3449 : :
3450 : : static void
3451 : 90461 : predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3452 : : enum prediction taken, class loop *in_loop)
3453 : : {
3454 : 90461 : bool has_nonloop_edge = false;
3455 : 90461 : edge_iterator ei;
3456 : 90461 : edge e2;
3457 : :
3458 : 90461 : basic_block bb = e->src;
3459 : 167919 : FOR_EACH_EDGE (e2, ei, bb->succs)
3460 : 107185 : if (e2->dest != e->src && e2->dest != e->dest
3461 : 38953 : && !unlikely_executed_edge_p (e2)
3462 : 145579 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3463 : : {
3464 : : has_nonloop_edge = true;
3465 : : break;
3466 : : }
3467 : :
3468 : 90461 : if (!has_nonloop_edge)
3469 : 60734 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3470 : : else
3471 : 29727 : maybe_predict_edge (e, pred, taken);
3472 : 90461 : }
3473 : :
3474 : : /* This is used to carry information about basic blocks. It is
3475 : : attached to the AUX field of the standard CFG block. */
3476 : :
3477 : : class block_info
3478 : : {
3479 : : public:
3480 : : /* Estimated frequency of execution of basic_block. */
3481 : : sreal frequency;
3482 : :
3483 : : /* To keep queue of basic blocks to process. */
3484 : : basic_block next;
3485 : :
3486 : : /* Number of predecessors we need to visit first. */
3487 : : int npredecessors;
3488 : : };
3489 : :
3490 : : /* Similar information for edges. */
3491 : : class edge_prob_info
3492 : : {
3493 : : public:
3494 : : /* In case edge is a loopback edge, the probability edge will be reached
3495 : : in case header is. Estimated number of iterations of the loop can be
3496 : : then computed as 1 / (1 - back_edge_prob). */
3497 : : sreal back_edge_prob;
3498 : : /* True if the edge is a loopback edge in the natural loop. */
3499 : : unsigned int back_edge:1;
3500 : : };
3501 : :
3502 : : #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3503 : : #undef EDGE_INFO
3504 : : #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3505 : :
3506 : : /* Helper function for estimate_bb_frequencies.
3507 : : Propagate the frequencies in blocks marked in
3508 : : TOVISIT, starting in HEAD. */
3509 : :
3510 : : static void
3511 : 3356236 : propagate_freq (basic_block head, bitmap tovisit,
3512 : : sreal max_cyclic_prob)
3513 : : {
3514 : 3356236 : basic_block bb;
3515 : 3356236 : basic_block last;
3516 : 3356236 : unsigned i;
3517 : 3356236 : edge e;
3518 : 3356236 : basic_block nextbb;
3519 : 3356236 : bitmap_iterator bi;
3520 : :
3521 : : /* For each basic block we need to visit count number of his predecessors
3522 : : we need to visit first. */
3523 : 26941756 : EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3524 : : {
3525 : 23585520 : edge_iterator ei;
3526 : 23585520 : int count = 0;
3527 : :
3528 : 23585520 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
3529 : :
3530 : 52324333 : FOR_EACH_EDGE (e, ei, bb->preds)
3531 : : {
3532 : 28738813 : bool visit = bitmap_bit_p (tovisit, e->src->index);
3533 : :
3534 : 28738813 : if (visit && !(e->flags & EDGE_DFS_BACK))
3535 : 26069837 : count++;
3536 : 1881040 : else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3537 : 3 : fprintf (dump_file,
3538 : : "Irreducible region hit, ignoring edge to %i->%i\n",
3539 : 3 : e->src->index, bb->index);
3540 : : }
3541 : 23585520 : BLOCK_INFO (bb)->npredecessors = count;
3542 : : /* When function never returns, we will never process exit block. */
3543 : 23585520 : if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3544 : 0 : bb->count = profile_count::zero ();
3545 : : }
3546 : :
3547 : 3356236 : BLOCK_INFO (head)->frequency = 1;
3548 : 3356236 : last = head;
3549 : 26941756 : for (bb = head; bb; bb = nextbb)
3550 : : {
3551 : 23585520 : edge_iterator ei;
3552 : 23585520 : sreal cyclic_probability = 0;
3553 : 23585520 : sreal frequency = 0;
3554 : :
3555 : 23585520 : nextbb = BLOCK_INFO (bb)->next;
3556 : 23585520 : BLOCK_INFO (bb)->next = NULL;
3557 : :
3558 : : /* Compute frequency of basic block. */
3559 : 23585520 : if (bb != head)
3560 : : {
3561 : 20229284 : if (flag_checking)
3562 : 47391675 : FOR_EACH_EDGE (e, ei, bb->preds)
3563 : 27162780 : gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3564 : : || (e->flags & EDGE_DFS_BACK));
3565 : :
3566 : 47392625 : FOR_EACH_EDGE (e, ei, bb->preds)
3567 : 27163341 : if (EDGE_INFO (e)->back_edge)
3568 : 1088593 : cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3569 : 26074748 : else if (!(e->flags & EDGE_DFS_BACK))
3570 : : {
3571 : : /* FIXME: Graphite is producing edges with no profile. Once
3572 : : this is fixed, drop this. */
3573 : 26069837 : sreal tmp = e->probability.initialized_p () ?
3574 : 26069837 : e->probability.to_sreal () : 0;
3575 : 26069837 : frequency += tmp * BLOCK_INFO (e->src)->frequency;
3576 : : }
3577 : :
3578 : 20229284 : if (cyclic_probability == 0)
3579 : : {
3580 : 19167774 : BLOCK_INFO (bb)->frequency = frequency;
3581 : : }
3582 : : else
3583 : : {
3584 : 1061510 : if (cyclic_probability > max_cyclic_prob)
3585 : : {
3586 : 9506 : if (dump_file)
3587 : 249 : fprintf (dump_file,
3588 : : "cyclic probability of bb %i is %f (capped to %f)"
3589 : : "; turning freq %f",
3590 : : bb->index, cyclic_probability.to_double (),
3591 : : max_cyclic_prob.to_double (),
3592 : : frequency.to_double ());
3593 : :
3594 : 9506 : cyclic_probability = max_cyclic_prob;
3595 : : }
3596 : 1052004 : else if (dump_file)
3597 : 111 : fprintf (dump_file,
3598 : : "cyclic probability of bb %i is %f; turning freq %f",
3599 : : bb->index, cyclic_probability.to_double (),
3600 : : frequency.to_double ());
3601 : :
3602 : 1061510 : BLOCK_INFO (bb)->frequency = frequency
3603 : 1061510 : / (sreal (1) - cyclic_probability);
3604 : 1061510 : if (dump_file)
3605 : 360 : fprintf (dump_file, " to %f\n",
3606 : 360 : BLOCK_INFO (bb)->frequency.to_double ());
3607 : : }
3608 : : }
3609 : :
3610 : 23585520 : bitmap_clear_bit (tovisit, bb->index);
3611 : :
3612 : 23585520 : e = find_edge (bb, head);
3613 : 23585520 : if (e)
3614 : : {
3615 : : /* FIXME: Graphite is producing edges with no profile. Once
3616 : : this is fixed, drop this. */
3617 : 787536 : sreal tmp = e->probability.initialized_p () ?
3618 : 787536 : e->probability.to_sreal () : 0;
3619 : 787536 : EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3620 : : }
3621 : :
3622 : : /* Propagate to successor blocks. */
3623 : 52945252 : FOR_EACH_EDGE (e, ei, bb->succs)
3624 : 29359732 : if (!(e->flags & EDGE_DFS_BACK)
3625 : 27477889 : && BLOCK_INFO (e->dest)->npredecessors)
3626 : : {
3627 : 26069837 : BLOCK_INFO (e->dest)->npredecessors--;
3628 : 26069837 : if (!BLOCK_INFO (e->dest)->npredecessors)
3629 : : {
3630 : 20229284 : if (!nextbb)
3631 : : nextbb = e->dest;
3632 : : else
3633 : 7562440 : BLOCK_INFO (last)->next = e->dest;
3634 : :
3635 : : last = e->dest;
3636 : : }
3637 : : }
3638 : : }
3639 : 3356236 : }
3640 : :
3641 : : /* Estimate frequencies in loops at same nest level. */
3642 : :
3643 : : static void
3644 : 1096935 : estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3645 : : {
3646 : 1096935 : class loop *loop;
3647 : :
3648 : 1884471 : for (loop = first_loop; loop; loop = loop->next)
3649 : : {
3650 : 787536 : edge e;
3651 : 787536 : basic_block *bbs;
3652 : 787536 : unsigned i;
3653 : 787536 : auto_bitmap tovisit;
3654 : :
3655 : 787536 : estimate_loops_at_level (loop->inner, max_cyclic_prob);
3656 : :
3657 : : /* Find current loop back edge and mark it. */
3658 : 787536 : e = loop_latch_edge (loop);
3659 : 787536 : EDGE_INFO (e)->back_edge = 1;
3660 : :
3661 : 787536 : bbs = get_loop_body (loop);
3662 : 5910221 : for (i = 0; i < loop->num_nodes; i++)
3663 : 4335149 : bitmap_set_bit (tovisit, bbs[i]->index);
3664 : 787536 : free (bbs);
3665 : 787536 : propagate_freq (loop->header, tovisit, max_cyclic_prob);
3666 : 787536 : }
3667 : 1096935 : }
3668 : :
3669 : : /* Propagates frequencies through structure of loops. */
3670 : :
3671 : : static void
3672 : 2568700 : estimate_loops (void)
3673 : : {
3674 : 2568700 : auto_bitmap tovisit;
3675 : 2568700 : basic_block bb;
3676 : 7706100 : sreal max_cyclic_prob = (sreal)1
3677 : 2568700 : - (sreal)1 / (param_max_predicted_iterations + 1);
3678 : :
3679 : : /* Start by estimating the frequencies in the loops. */
3680 : 5137400 : if (number_of_loops (cfun) > 1)
3681 : 309399 : estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3682 : :
3683 : : /* Now propagate the frequencies through all the blocks. */
3684 : 21819071 : FOR_ALL_BB_FN (bb, cfun)
3685 : : {
3686 : 19250371 : bitmap_set_bit (tovisit, bb->index);
3687 : : }
3688 : 2568700 : propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3689 : 2568700 : }
3690 : :
3691 : : /* Drop the profile for NODE to guessed, and update its frequency based on
3692 : : whether it is expected to be hot given the CALL_COUNT. */
3693 : :
3694 : : static void
3695 : 0 : drop_profile (struct cgraph_node *node, profile_count call_count)
3696 : : {
3697 : 0 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3698 : : /* In the case where this was called by another function with a
3699 : : dropped profile, call_count will be 0. Since there are no
3700 : : non-zero call counts to this function, we don't know for sure
3701 : : whether it is hot, and therefore it will be marked normal below. */
3702 : 0 : bool hot = maybe_hot_count_p (NULL, call_count);
3703 : :
3704 : 0 : if (dump_file)
3705 : 0 : fprintf (dump_file,
3706 : : "Dropping 0 profile for %s. %s based on calls.\n",
3707 : : node->dump_name (),
3708 : : hot ? "Function is hot" : "Function is normal");
3709 : : /* We only expect to miss profiles for functions that are reached
3710 : : via non-zero call edges in cases where the function may have
3711 : : been linked from another module or library (COMDATs and extern
3712 : : templates). See the comments below for handle_missing_profiles.
3713 : : Also, only warn in cases where the missing counts exceed the
3714 : : number of training runs. In certain cases with an execv followed
3715 : : by a no-return call the profile for the no-return call is not
3716 : : dumped and there can be a mismatch. */
3717 : 0 : if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3718 : 0 : && call_count > profile_info->runs)
3719 : : {
3720 : 0 : if (flag_profile_correction)
3721 : : {
3722 : 0 : if (dump_file)
3723 : 0 : fprintf (dump_file,
3724 : : "Missing counts for called function %s\n",
3725 : : node->dump_name ());
3726 : : }
3727 : : else
3728 : 0 : warning (0, "Missing counts for called function %s",
3729 : : node->dump_name ());
3730 : : }
3731 : :
3732 : 0 : basic_block bb;
3733 : 0 : if (opt_for_fn (node->decl, flag_guess_branch_prob))
3734 : : {
3735 : 0 : bool clear_zeros
3736 : 0 : = !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3737 : 0 : FOR_ALL_BB_FN (bb, fn)
3738 : 0 : if (clear_zeros || !(bb->count == profile_count::zero ()))
3739 : 0 : bb->count = bb->count.guessed_local ();
3740 : 0 : fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3741 : : }
3742 : : else
3743 : : {
3744 : 0 : FOR_ALL_BB_FN (bb, fn)
3745 : 0 : bb->count = profile_count::uninitialized ();
3746 : 0 : fn->cfg->count_max = profile_count::uninitialized ();
3747 : : }
3748 : :
3749 : 0 : struct cgraph_edge *e;
3750 : 0 : for (e = node->callees; e; e = e->next_callee)
3751 : 0 : e->count = gimple_bb (e->call_stmt)->count;
3752 : 0 : for (e = node->indirect_calls; e; e = e->next_callee)
3753 : 0 : e->count = gimple_bb (e->call_stmt)->count;
3754 : 0 : node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3755 : :
3756 : 0 : profile_status_for_fn (fn)
3757 : 0 : = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3758 : 0 : node->frequency
3759 : 0 : = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3760 : 0 : }
3761 : :
3762 : : /* In the case of COMDAT routines, multiple object files will contain the same
3763 : : function and the linker will select one for the binary. In that case
3764 : : all the other copies from the profile instrument binary will be missing
3765 : : profile counts. Look for cases where this happened, due to non-zero
3766 : : call counts going to 0-count functions, and drop the profile to guessed
3767 : : so that we can use the estimated probabilities and avoid optimizing only
3768 : : for size.
3769 : :
3770 : : The other case where the profile may be missing is when the routine
3771 : : is not going to be emitted to the object file, e.g. for "extern template"
3772 : : class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3773 : : all other cases of non-zero calls to 0-count functions. */
3774 : :
3775 : : void
3776 : 594 : handle_missing_profiles (void)
3777 : : {
3778 : 594 : const int unlikely_frac = param_unlikely_bb_count_fraction;
3779 : 594 : struct cgraph_node *node;
3780 : 594 : auto_vec<struct cgraph_node *, 64> worklist;
3781 : :
3782 : : /* See if 0 count function has non-0 count callers. In this case we
3783 : : lost some profile. Drop its function profile to PROFILE_GUESSED. */
3784 : 3368 : FOR_EACH_DEFINED_FUNCTION (node)
3785 : : {
3786 : 2774 : struct cgraph_edge *e;
3787 : 2774 : profile_count call_count = profile_count::zero ();
3788 : 2774 : gcov_type max_tp_first_run = 0;
3789 : 2774 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3790 : :
3791 : 2774 : if (node->count.ipa ().nonzero_p ())
3792 : 345 : continue;
3793 : 4663 : for (e = node->callers; e; e = e->next_caller)
3794 : 2234 : if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3795 : : {
3796 : 8 : call_count = call_count + e->count.ipa ();
3797 : :
3798 : 8 : if (e->caller->tp_first_run > max_tp_first_run)
3799 : 2234 : max_tp_first_run = e->caller->tp_first_run;
3800 : : }
3801 : :
3802 : : /* If time profile is missing, let assign the maximum that comes from
3803 : : caller functions. */
3804 : 2429 : if (!node->tp_first_run && max_tp_first_run)
3805 : 4 : node->tp_first_run = max_tp_first_run + 1;
3806 : :
3807 : 2429 : if (call_count > 0
3808 : 6 : && fn && fn->cfg
3809 : 2435 : && call_count * unlikely_frac >= profile_info->runs)
3810 : : {
3811 : 0 : drop_profile (node, call_count);
3812 : 0 : worklist.safe_push (node);
3813 : : }
3814 : : }
3815 : :
3816 : : /* Propagate the profile dropping to other 0-count COMDATs that are
3817 : : potentially called by COMDATs we already dropped the profile on. */
3818 : 594 : while (worklist.length () > 0)
3819 : : {
3820 : 0 : struct cgraph_edge *e;
3821 : :
3822 : 0 : node = worklist.pop ();
3823 : 0 : for (e = node->callees; e; e = e->next_caller)
3824 : : {
3825 : 0 : struct cgraph_node *callee = e->callee;
3826 : 0 : struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3827 : :
3828 : 0 : if (!(e->count.ipa () == profile_count::zero ())
3829 : 0 : && callee->count.ipa ().nonzero_p ())
3830 : 0 : continue;
3831 : 0 : if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3832 : 0 : && fn && fn->cfg
3833 : 0 : && profile_status_for_fn (fn) == PROFILE_READ)
3834 : : {
3835 : 0 : drop_profile (node, profile_count::zero ());
3836 : 0 : worklist.safe_push (callee);
3837 : : }
3838 : : }
3839 : : }
3840 : 594 : }
3841 : :
3842 : : /* Convert counts measured by profile driven feedback to frequencies.
3843 : : Return nonzero iff there was any nonzero execution count. */
3844 : :
3845 : : bool
3846 : 1793971 : update_max_bb_count (void)
3847 : : {
3848 : 1793971 : profile_count true_count_max = profile_count::uninitialized ();
3849 : 1793971 : basic_block bb;
3850 : :
3851 : 37298538 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3852 : 35504567 : true_count_max = true_count_max.max (bb->count);
3853 : :
3854 : 1793971 : cfun->cfg->count_max = true_count_max;
3855 : :
3856 : 1793971 : return true_count_max.ipa ().nonzero_p ();
3857 : : }
3858 : :
3859 : : /* Return true if function is likely to be expensive, so there is no point to
3860 : : optimize performance of prologue, epilogue or do inlining at the expense
3861 : : of code size growth. THRESHOLD is the limit of number of instructions
3862 : : function can execute at average to be still considered not expensive. */
3863 : :
3864 : : bool
3865 : 291153 : expensive_function_p (int threshold)
3866 : : {
3867 : 291153 : basic_block bb;
3868 : :
3869 : : /* If profile was scaled in a way entry block has count 0, then the function
3870 : : is deifnitly taking a lot of time. */
3871 : 457794 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3872 : : return true;
3873 : :
3874 : 250388 : profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3875 : 250388 : profile_count sum = profile_count::zero ();
3876 : 3273837 : FOR_EACH_BB_FN (bb, cfun)
3877 : : {
3878 : 3190090 : rtx_insn *insn;
3879 : :
3880 : 3190090 : if (!bb->count.initialized_p ())
3881 : : {
3882 : 2 : if (dump_file)
3883 : 0 : fprintf (dump_file, "Function is considered expensive because"
3884 : : " count of bb %i is not initialized\n", bb->index);
3885 : 2 : return true;
3886 : : }
3887 : :
3888 : 48943103 : FOR_BB_INSNS (bb, insn)
3889 : 45919654 : if (active_insn_p (insn))
3890 : : {
3891 : 18314660 : sum += bb->count;
3892 : 18314660 : if (sum > limit)
3893 : : return true;
3894 : : }
3895 : : }
3896 : :
3897 : : return false;
3898 : : }
3899 : :
3900 : : /* All basic blocks that are reachable only from unlikely basic blocks are
3901 : : unlikely. */
3902 : :
3903 : : void
3904 : 6387823 : propagate_unlikely_bbs_forward (void)
3905 : : {
3906 : 6387823 : auto_vec<basic_block, 64> worklist;
3907 : 6387823 : basic_block bb;
3908 : 6387823 : edge_iterator ei;
3909 : 6387823 : edge e;
3910 : :
3911 : 6398056 : if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3912 : : {
3913 : 6377590 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3914 : 6377590 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3915 : :
3916 : 67558051 : while (worklist.length () > 0)
3917 : : {
3918 : 54802871 : bb = worklist.pop ();
3919 : 121431089 : FOR_EACH_EDGE (e, ei, bb->succs)
3920 : 67770748 : if (!(e->count () == profile_count::zero ())
3921 : 79895479 : && !(e->dest->count == profile_count::zero ())
3922 : 61122600 : && !e->dest->aux)
3923 : : {
3924 : 48425281 : e->dest->aux = (void *)(size_t) 1;
3925 : 48425281 : worklist.safe_push (e->dest);
3926 : : }
3927 : : }
3928 : : }
3929 : :
3930 : 63927400 : FOR_ALL_BB_FN (bb, cfun)
3931 : : {
3932 : 57539577 : if (!bb->aux)
3933 : : {
3934 : 5472663 : if (!(bb->count == profile_count::zero ())
3935 : 418159 : && (dump_file && (dump_flags & TDF_DETAILS)))
3936 : 749 : fprintf (dump_file,
3937 : : "Basic block %i is marked unlikely by forward prop\n",
3938 : : bb->index);
3939 : 2736706 : bb->count = profile_count::zero ();
3940 : : }
3941 : : else
3942 : 54802871 : bb->aux = NULL;
3943 : : }
3944 : 6387823 : }
3945 : :
3946 : : /* Determine basic blocks/edges that are known to be unlikely executed and set
3947 : : their counters to zero.
3948 : : This is done with first identifying obviously unlikely BBs/edges and then
3949 : : propagating in both directions. */
3950 : :
3951 : : static void
3952 : 5079544 : determine_unlikely_bbs ()
3953 : : {
3954 : 5079544 : basic_block bb;
3955 : 5079544 : auto_vec<basic_block, 64> worklist;
3956 : 5079544 : edge_iterator ei;
3957 : 5079544 : edge e;
3958 : :
3959 : 30738855 : FOR_EACH_BB_FN (bb, cfun)
3960 : : {
3961 : 51006913 : if (!(bb->count == profile_count::zero ())
3962 : 24856481 : && unlikely_executed_bb_p (bb))
3963 : : {
3964 : 311709 : if (dump_file && (dump_flags & TDF_DETAILS))
3965 : 0 : fprintf (dump_file, "Basic block %i is locally unlikely\n",
3966 : : bb->index);
3967 : 311709 : bb->count = profile_count::zero ();
3968 : : }
3969 : :
3970 : 61871124 : FOR_EACH_EDGE (e, ei, bb->succs)
3971 : 67802659 : if (!(e->probability == profile_probability::never ())
3972 : 36211813 : && unlikely_executed_edge_p (e))
3973 : : {
3974 : 2036911 : if (dump_file && (dump_flags & TDF_DETAILS))
3975 : 27 : fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3976 : 27 : bb->index, e->dest->index);
3977 : 2036911 : e->probability = profile_probability::never ();
3978 : : }
3979 : :
3980 : 25659311 : gcc_checking_assert (!bb->aux);
3981 : : }
3982 : 5079544 : propagate_unlikely_bbs_forward ();
3983 : :
3984 : 5079544 : auto_vec<int, 64> nsuccs;
3985 : 5079544 : nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
3986 : 40897943 : FOR_ALL_BB_FN (bb, cfun)
3987 : 42304812 : if (!(bb->count == profile_count::zero ())
3988 : 34336748 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3989 : : {
3990 : 29331986 : nsuccs[bb->index] = 0;
3991 : 69096771 : FOR_EACH_EDGE (e, ei, bb->succs)
3992 : 39764785 : if (!(e->probability == profile_probability::never ())
3993 : 76716435 : && !(e->dest->count == profile_count::zero ()))
3994 : 36063748 : nsuccs[bb->index]++;
3995 : 29331986 : if (!nsuccs[bb->index])
3996 : 1509480 : worklist.safe_push (bb);
3997 : : }
3998 : 6599374 : while (worklist.length () > 0)
3999 : : {
4000 : 1519830 : bb = worklist.pop ();
4001 : 1519830 : if (bb->count == profile_count::zero ())
4002 : 0 : continue;
4003 : 1519830 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4004 : : {
4005 : 1512727 : bool found = false;
4006 : 3025454 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
4007 : 2292787 : !gsi_end_p (gsi); gsi_next (&gsi))
4008 : 2281916 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
4009 : : /* stmt_can_terminate_bb_p special cases noreturns because it
4010 : : assumes that fake edges are created. We want to know that
4011 : : noreturn alone does not imply BB to be unlikely. */
4012 : 2281916 : || (is_gimple_call (gsi_stmt (gsi))
4013 : 899188 : && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
4014 : : {
4015 : : found = true;
4016 : : break;
4017 : : }
4018 : 1512727 : if (found)
4019 : 1501856 : continue;
4020 : : }
4021 : 17974 : if (dump_file && (dump_flags & TDF_DETAILS))
4022 : 0 : fprintf (dump_file,
4023 : : "Basic block %i is marked unlikely by backward prop\n",
4024 : : bb->index);
4025 : 17974 : bb->count = profile_count::zero ();
4026 : 33874 : FOR_EACH_EDGE (e, ei, bb->preds)
4027 : 15900 : if (!(e->probability == profile_probability::never ()))
4028 : : {
4029 : 15101 : if (!(e->src->count == profile_count::zero ()))
4030 : : {
4031 : 15101 : gcc_checking_assert (nsuccs[e->src->index] > 0);
4032 : 15101 : nsuccs[e->src->index]--;
4033 : 15101 : if (!nsuccs[e->src->index])
4034 : 10350 : worklist.safe_push (e->src);
4035 : : }
4036 : : }
4037 : : }
4038 : : /* Finally all edges from non-0 regions to 0 are unlikely. */
4039 : 40897943 : FOR_ALL_BB_FN (bb, cfun)
4040 : : {
4041 : 37318024 : if (!(bb->count == profile_count::zero ()))
4042 : 74060428 : FOR_EACH_EDGE (e, ei, bb->succs)
4043 : 39741654 : if (!(e->probability == profile_probability::never ())
4044 : 76289539 : && e->dest->count == profile_count::zero ())
4045 : : {
4046 : 436018 : if (dump_file && (dump_flags & TDF_DETAILS))
4047 : 0 : fprintf (dump_file, "Edge %i->%i is unlikely because "
4048 : : "it enters unlikely block\n",
4049 : : bb->index, e->dest->index);
4050 : 436018 : e->probability = profile_probability::never ();
4051 : : }
4052 : :
4053 : 35818399 : edge other = NULL;
4054 : :
4055 : 68841463 : FOR_EACH_EDGE (e, ei, bb->succs)
4056 : 41038011 : if (e->probability == profile_probability::never ())
4057 : : ;
4058 : 35988062 : else if (other)
4059 : : {
4060 : : other = NULL;
4061 : : break;
4062 : : }
4063 : : else
4064 : : other = e;
4065 : 35818399 : if (other
4066 : 35818399 : && !(other->probability == profile_probability::always ()))
4067 : : {
4068 : 8460781 : if (dump_file && (dump_flags & TDF_DETAILS))
4069 : 6 : fprintf (dump_file, "Edge %i->%i is locally likely\n",
4070 : 6 : bb->index, other->dest->index);
4071 : 8460781 : other->probability = profile_probability::always ();
4072 : : }
4073 : : }
4074 : 5079544 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
4075 : 14111 : cgraph_node::get (current_function_decl)->count = profile_count::zero ();
4076 : 5079544 : }
4077 : :
4078 : : /* Estimate and propagate basic block frequencies using the given branch
4079 : : probabilities. */
4080 : :
4081 : : static void
4082 : 2568700 : estimate_bb_frequencies ()
4083 : : {
4084 : 2568700 : basic_block bb;
4085 : 2568700 : sreal freq_max;
4086 : :
4087 : 2568700 : determine_unlikely_bbs ();
4088 : :
4089 : 2568700 : mark_dfs_back_edges ();
4090 : :
4091 : 2568700 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
4092 : : profile_probability::always ();
4093 : :
4094 : : /* Set up block info for each basic block. */
4095 : 2568700 : alloc_aux_for_blocks (sizeof (block_info));
4096 : 2568700 : alloc_aux_for_edges (sizeof (edge_prob_info));
4097 : 21819071 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4098 : : {
4099 : 19250371 : edge e;
4100 : 19250371 : edge_iterator ei;
4101 : :
4102 : 41873956 : FOR_EACH_EDGE (e, ei, bb->succs)
4103 : : {
4104 : : /* FIXME: Graphite is producing edges with no profile. Once
4105 : : this is fixed, drop this. */
4106 : 22623585 : if (e->probability.initialized_p ())
4107 : 22623553 : EDGE_INFO (e)->back_edge_prob
4108 : 22623553 : = e->probability.to_sreal ();
4109 : : else
4110 : : /* back_edge_prob = 0.5 */
4111 : 32 : EDGE_INFO (e)->back_edge_prob = sreal (1, -1);
4112 : : }
4113 : : }
4114 : :
4115 : : /* First compute frequencies locally for each loop from innermost
4116 : : to outermost to examine frequencies for back edges. */
4117 : 2568700 : estimate_loops ();
4118 : :
4119 : 2568700 : freq_max = 0;
4120 : 16681671 : FOR_EACH_BB_FN (bb, cfun)
4121 : 14112971 : if (freq_max < BLOCK_INFO (bb)->frequency)
4122 : 3221807 : freq_max = BLOCK_INFO (bb)->frequency;
4123 : :
4124 : : /* Scaling frequencies up to maximal profile count may result in
4125 : : frequent overflows especially when inlining loops.
4126 : : Small scaling results in unnecesary precision loss. Stay in
4127 : : the half of the (exponential) range. */
4128 : 2568700 : freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
4129 : 2568700 : if (freq_max < 16)
4130 : 74 : freq_max = 16;
4131 : 2568700 : profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
4132 : 2568700 : cfun->cfg->count_max = profile_count::uninitialized ();
4133 : 21819071 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4134 : : {
4135 : 19250371 : sreal tmp = BLOCK_INFO (bb)->frequency;
4136 : 19250371 : if (tmp >= 1)
4137 : : {
4138 : 11128880 : gimple_stmt_iterator gsi;
4139 : 11128880 : tree decl;
4140 : :
4141 : : /* Self recursive calls can not have frequency greater than 1
4142 : : or program will never terminate. This will result in an
4143 : : inconsistent bb profile but it is better than greatly confusing
4144 : : IPA cost metrics. */
4145 : 69113804 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4146 : 46861722 : if (is_gimple_call (gsi_stmt (gsi))
4147 : 2835419 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
4148 : 49413980 : && recursive_call_p (current_function_decl, decl))
4149 : : {
4150 : 5678 : if (dump_file)
4151 : 0 : fprintf (dump_file, "Dropping frequency of recursive call"
4152 : : " in bb %i from %f\n", bb->index,
4153 : : tmp.to_double ());
4154 : 5678 : tmp = (sreal)9 / (sreal)10;
4155 : 5678 : break;
4156 : : }
4157 : : }
4158 : 19250371 : tmp = tmp * freq_max;
4159 : 19250371 : profile_count count = profile_count::from_gcov_type (tmp.to_nearest_int ());
4160 : :
4161 : : /* If we have profile feedback in which this function was never
4162 : : executed, then preserve this info. */
4163 : 20102774 : if (!(bb->count == profile_count::zero ()))
4164 : 18397968 : bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
4165 : 19250371 : cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4166 : : }
4167 : :
4168 : 2568700 : free_aux_for_blocks ();
4169 : 2568700 : free_aux_for_edges ();
4170 : 2568700 : compute_function_frequency ();
4171 : 2568700 : }
4172 : :
4173 : : /* Decide whether function is hot, cold or unlikely executed. */
4174 : : void
4175 : 2596583 : compute_function_frequency (void)
4176 : : {
4177 : 2596583 : basic_block bb;
4178 : 2596583 : struct cgraph_node *node = cgraph_node::get (current_function_decl);
4179 : :
4180 : 2596583 : if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4181 : 2596583 : || MAIN_NAME_P (DECL_NAME (current_function_decl)))
4182 : 91041 : node->only_called_at_startup = true;
4183 : 2596583 : if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4184 : 1209 : node->only_called_at_exit = true;
4185 : :
4186 : 2596583 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4187 : : {
4188 : 2589001 : int flags = flags_from_decl_or_type (current_function_decl);
4189 : 2589001 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4190 : : != NULL)
4191 : 317 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4192 : 2588684 : else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
4193 : : != NULL)
4194 : 60 : node->frequency = NODE_FREQUENCY_HOT;
4195 : 2588624 : else if (flags & ECF_NORETURN)
4196 : 1973 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4197 : 2586651 : else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4198 : 77727 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4199 : 2508924 : else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4200 : 2508924 : || DECL_STATIC_DESTRUCTOR (current_function_decl))
4201 : 13775 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4202 : 2589001 : return;
4203 : : }
4204 : :
4205 : 7582 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4206 : 7582 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4207 : : == NULL)
4208 : 7578 : warn_function_cold (current_function_decl);
4209 : 7582 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4210 : 7236 : return;
4211 : 930 : FOR_EACH_BB_FN (bb, cfun)
4212 : : {
4213 : 819 : if (maybe_hot_bb_p (cfun, bb))
4214 : : {
4215 : 235 : node->frequency = NODE_FREQUENCY_HOT;
4216 : 235 : return;
4217 : : }
4218 : 584 : if (!probably_never_executed_bb_p (cfun, bb))
4219 : 528 : node->frequency = NODE_FREQUENCY_NORMAL;
4220 : : }
4221 : : }
4222 : :
4223 : : /* Build PREDICT_EXPR. */
4224 : : tree
4225 : 816762 : build_predict_expr (enum br_predictor predictor, enum prediction taken)
4226 : : {
4227 : 816762 : tree t = build1 (PREDICT_EXPR, void_type_node,
4228 : 816762 : build_int_cst (integer_type_node, predictor));
4229 : 816762 : SET_PREDICT_EXPR_OUTCOME (t, taken);
4230 : 816762 : return t;
4231 : : }
4232 : :
4233 : : const char *
4234 : 648 : predictor_name (enum br_predictor predictor)
4235 : : {
4236 : 648 : return predictor_info[predictor].name;
4237 : : }
4238 : :
4239 : : /* Predict branch probabilities and estimate profile of the tree CFG. */
4240 : :
4241 : : namespace {
4242 : :
4243 : : const pass_data pass_data_profile =
4244 : : {
4245 : : GIMPLE_PASS, /* type */
4246 : : "profile_estimate", /* name */
4247 : : OPTGROUP_NONE, /* optinfo_flags */
4248 : : TV_BRANCH_PROB, /* tv_id */
4249 : : PROP_cfg, /* properties_required */
4250 : : 0, /* properties_provided */
4251 : : 0, /* properties_destroyed */
4252 : : 0, /* todo_flags_start */
4253 : : 0, /* todo_flags_finish */
4254 : : };
4255 : :
4256 : : class pass_profile : public gimple_opt_pass
4257 : : {
4258 : : public:
4259 : 285689 : pass_profile (gcc::context *ctxt)
4260 : 571378 : : gimple_opt_pass (pass_data_profile, ctxt)
4261 : : {}
4262 : :
4263 : : /* opt_pass methods: */
4264 : 2511775 : bool gate (function *) final override { return flag_guess_branch_prob; }
4265 : : unsigned int execute (function *) final override;
4266 : :
4267 : : }; // class pass_profile
4268 : :
4269 : : unsigned int
4270 : 2510730 : pass_profile::execute (function *fun)
4271 : : {
4272 : 2510730 : unsigned nb_loops;
4273 : :
4274 : 2510730 : if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4275 : : return 0;
4276 : :
4277 : 2510692 : loop_optimizer_init (LOOPS_NORMAL);
4278 : 2510692 : if (dump_file && (dump_flags & TDF_DETAILS))
4279 : 2 : flow_loops_dump (dump_file, NULL, 0);
4280 : :
4281 : 2510692 : nb_loops = number_of_loops (fun);
4282 : 2510692 : if (nb_loops > 1)
4283 : 275200 : scev_initialize ();
4284 : :
4285 : 2510692 : tree_estimate_probability (false);
4286 : 2510692 : cfun->cfg->full_profile = true;
4287 : :
4288 : 2510692 : if (nb_loops > 1)
4289 : 275200 : scev_finalize ();
4290 : :
4291 : 2510692 : loop_optimizer_finalize ();
4292 : 2510692 : if (dump_file && (dump_flags & TDF_DETAILS))
4293 : 2 : gimple_dump_cfg (dump_file, dump_flags);
4294 : 2510692 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4295 : 2510692 : profile_status_for_fn (fun) = PROFILE_GUESSED;
4296 : 2510692 : if (dump_file && (dump_flags & TDF_DETAILS))
4297 : : {
4298 : 2 : sreal iterations;
4299 : 7 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
4300 : 1 : if (expected_loop_iterations_by_profile (loop, &iterations))
4301 : 1 : fprintf (dump_file, "Loop %d got predicted to iterate %f times.\n",
4302 : 2 : loop->num, iterations.to_double ());
4303 : : }
4304 : : return 0;
4305 : : }
4306 : :
4307 : : } // anon namespace
4308 : :
4309 : : gimple_opt_pass *
4310 : 285689 : make_pass_profile (gcc::context *ctxt)
4311 : : {
4312 : 285689 : return new pass_profile (ctxt);
4313 : : }
4314 : :
4315 : : /* Return true when PRED predictor should be removed after early
4316 : : tree passes. Most of the predictors are beneficial to survive
4317 : : as early inlining can also distribute then into caller's bodies. */
4318 : :
4319 : : static bool
4320 : 380398 : strip_predictor_early (enum br_predictor pred)
4321 : : {
4322 : 0 : switch (pred)
4323 : : {
4324 : : case PRED_TREE_EARLY_RETURN:
4325 : : return true;
4326 : 0 : default:
4327 : 0 : return false;
4328 : : }
4329 : : }
4330 : :
4331 : : /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4332 : : we no longer need. EARLY is set to true when called from early
4333 : : optimizations. */
4334 : :
4335 : : unsigned int
4336 : 3557057 : strip_predict_hints (function *fun, bool early)
4337 : : {
4338 : 3557057 : basic_block bb;
4339 : 3557057 : gimple *ass_stmt;
4340 : 3557057 : tree var;
4341 : 3557057 : bool changed = false;
4342 : :
4343 : 26992446 : FOR_EACH_BB_FN (bb, fun)
4344 : : {
4345 : 23435389 : gimple_stmt_iterator bi;
4346 : 205675497 : for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4347 : : {
4348 : 158804719 : gimple *stmt = gsi_stmt (bi);
4349 : :
4350 : 158804719 : if (gimple_code (stmt) == GIMPLE_PREDICT)
4351 : : {
4352 : 1126762 : if (!early
4353 : 597502 : || strip_predictor_early (gimple_predict_predictor (stmt)))
4354 : : {
4355 : 529260 : gsi_remove (&bi, true);
4356 : 529260 : changed = true;
4357 : 529260 : continue;
4358 : : }
4359 : : }
4360 : 158207217 : else if (is_gimple_call (stmt))
4361 : : {
4362 : 12097698 : tree fndecl = gimple_call_fndecl (stmt);
4363 : :
4364 : 12097698 : if (!early
4365 : 12097698 : && ((fndecl != NULL_TREE
4366 : 5798801 : && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4367 : 117009 : && gimple_call_num_args (stmt) == 2)
4368 : : || (fndecl != NULL_TREE
4369 : 5681792 : && fndecl_built_in_p (fndecl,
4370 : : BUILT_IN_EXPECT_WITH_PROBABILITY)
4371 : 18 : && gimple_call_num_args (stmt) == 3)
4372 : 6011004 : || (gimple_call_internal_p (stmt)
4373 : 142603 : && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4374 : : {
4375 : 150239 : var = gimple_call_lhs (stmt);
4376 : 150239 : changed = true;
4377 : 150239 : if (var)
4378 : : {
4379 : 150238 : ass_stmt
4380 : 150238 : = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4381 : 150238 : gsi_replace (&bi, ass_stmt, true);
4382 : : }
4383 : : else
4384 : : {
4385 : 1 : gsi_remove (&bi, true);
4386 : 1 : continue;
4387 : : }
4388 : : }
4389 : : }
4390 : 158275458 : gsi_next (&bi);
4391 : : }
4392 : : }
4393 : 3557057 : return changed ? TODO_cleanup_cfg : 0;
4394 : : }
4395 : :
4396 : : namespace {
4397 : :
4398 : : const pass_data pass_data_strip_predict_hints =
4399 : : {
4400 : : GIMPLE_PASS, /* type */
4401 : : "*strip_predict_hints", /* name */
4402 : : OPTGROUP_NONE, /* optinfo_flags */
4403 : : TV_BRANCH_PROB, /* tv_id */
4404 : : PROP_cfg, /* properties_required */
4405 : : 0, /* properties_provided */
4406 : : 0, /* properties_destroyed */
4407 : : 0, /* todo_flags_start */
4408 : : 0, /* todo_flags_finish */
4409 : : };
4410 : :
4411 : : class pass_strip_predict_hints : public gimple_opt_pass
4412 : : {
4413 : : public:
4414 : 857067 : pass_strip_predict_hints (gcc::context *ctxt)
4415 : 1714134 : : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4416 : : {}
4417 : :
4418 : : /* opt_pass methods: */
4419 : 571378 : opt_pass * clone () final override
4420 : : {
4421 : 571378 : return new pass_strip_predict_hints (m_ctxt);
4422 : : }
4423 : 857067 : void set_pass_param (unsigned int n, bool param) final override
4424 : : {
4425 : 857067 : gcc_assert (n == 0);
4426 : 857067 : early_p = param;
4427 : 857067 : }
4428 : :
4429 : : unsigned int execute (function *) final override;
4430 : :
4431 : : private:
4432 : : bool early_p;
4433 : :
4434 : : }; // class pass_strip_predict_hints
4435 : :
4436 : : unsigned int
4437 : 3557057 : pass_strip_predict_hints::execute (function *fun)
4438 : : {
4439 : 3557057 : return strip_predict_hints (fun, early_p);
4440 : : }
4441 : :
4442 : : } // anon namespace
4443 : :
4444 : : gimple_opt_pass *
4445 : 285689 : make_pass_strip_predict_hints (gcc::context *ctxt)
4446 : : {
4447 : 285689 : return new pass_strip_predict_hints (ctxt);
4448 : : }
4449 : :
4450 : : /* Rebuild function frequencies. Passes are in general expected to
4451 : : maintain profile by hand, however in some cases this is not possible:
4452 : : for example when inlining several functions with loops freuqencies might run
4453 : : out of scale and thus needs to be recomputed. */
4454 : :
4455 : : void
4456 : 1095409 : rebuild_frequencies (void)
4457 : : {
4458 : : /* If we have no profile, do nothing. Note that after inlining
4459 : : profile_status_for_fn may not represent the actual presence/absence of
4460 : : profile. */
4461 : 1095409 : if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4462 : 1095409 : && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4463 : : return;
4464 : :
4465 : :
4466 : : /* See if everything is OK and update count_max. */
4467 : 1095161 : basic_block bb;
4468 : 1095161 : bool inconsistency_found = false;
4469 : 1095161 : bool uninitialized_probablity_found = false;
4470 : 1095161 : bool uninitialized_count_found = false;
4471 : 1095161 : bool feedback_found = false;
4472 : :
4473 : 1095161 : cfun->cfg->count_max = profile_count::uninitialized ();
4474 : 15349448 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4475 : : {
4476 : 14254287 : cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4477 : 27298003 : if (bb->count.nonzero_p () && bb->count.quality () >= AFDO)
4478 : : feedback_found = true;
4479 : : /* Uninitialized count may be result of inlining or an omision in an
4480 : : optimization pass. */
4481 : 14254287 : if (!bb->count.initialized_p ())
4482 : : {
4483 : 22 : uninitialized_count_found = true;
4484 : 22 : if (dump_file)
4485 : 0 : fprintf (dump_file, "BB %i has uninitialized count\n",
4486 : : bb->index);
4487 : : }
4488 : 14254287 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4489 : : && (!uninitialized_probablity_found || !inconsistency_found))
4490 : : {
4491 : 13159126 : profile_count sum = profile_count::zero ();
4492 : 13159126 : edge e;
4493 : 13159126 : edge_iterator ei;
4494 : :
4495 : 30948220 : FOR_EACH_EDGE (e, ei, bb->preds)
4496 : : {
4497 : 17789094 : sum += e->count ();
4498 : : /* Uninitialized probability may be result of inlining or an
4499 : : omision in an optimization pass. */
4500 : 17789094 : if (!e->probability.initialized_p ())
4501 : : {
4502 : 36 : if (dump_file)
4503 : 0 : fprintf (dump_file,
4504 : : "Edge %i->%i has uninitialized probability\n",
4505 : 0 : e->src->index, e->dest->index);
4506 : : }
4507 : : }
4508 : 13159126 : if (sum.differs_from_p (bb->count))
4509 : : {
4510 : 184251 : if (dump_file)
4511 : 6 : fprintf (dump_file,
4512 : : "BB %i has invalid sum of incomming counts\n",
4513 : : bb->index);
4514 : : inconsistency_found = true;
4515 : : }
4516 : : }
4517 : : }
4518 : :
4519 : : /* If everything is OK, do not re-propagate frequencies. */
4520 : 1095161 : if (!inconsistency_found
4521 : 1037399 : && (!uninitialized_count_found || uninitialized_probablity_found)
4522 : 2132560 : && !cfun->cfg->count_max.very_large_p ())
4523 : : {
4524 : 1037296 : if (dump_file)
4525 : 33 : fprintf (dump_file, "Profile is consistent\n");
4526 : 1037296 : return;
4527 : : }
4528 : : /* Do not re-propagate if we have profile feedback. Even if the profile is
4529 : : inconsistent from previous transofrmations, it is probably more realistic
4530 : : for hot part of the program than result of repropagating.
4531 : :
4532 : : Consider example where we previously has
4533 : :
4534 : : if (test)
4535 : : then [large probability for true]
4536 : :
4537 : : and we later proved that test is always 0. In this case, if profile was
4538 : : read correctly, we must have duplicated the conditional (for example by
4539 : : inlining) in to a context where test is false. From profile feedback
4540 : : we know that most executions if the conditionals were true, so the
4541 : : important copy is not the one we look on.
4542 : :
4543 : : Propagating from probabilities would make profile look consistent, but
4544 : : because probablities after code duplication may not be representative
4545 : : for a given run, we would only propagate the error further. */
4546 : 57865 : if (feedback_found && !uninitialized_count_found)
4547 : : {
4548 : 9 : if (dump_file)
4549 : 0 : fprintf (dump_file,
4550 : : "Profile is inconsistent but read from profile feedback;"
4551 : : " not rebuilding\n");
4552 : 9 : return;
4553 : : }
4554 : :
4555 : 57856 : loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4556 : 57856 : connect_infinite_loops_to_exit ();
4557 : 57856 : estimate_bb_frequencies ();
4558 : 57856 : remove_fake_exit_edges ();
4559 : 57856 : loop_optimizer_finalize ();
4560 : 57856 : if (dump_file)
4561 : 3 : fprintf (dump_file, "Rebuilt basic block counts\n");
4562 : :
4563 : : return;
4564 : : }
4565 : :
4566 : : namespace {
4567 : :
4568 : : const pass_data pass_data_rebuild_frequencies =
4569 : : {
4570 : : GIMPLE_PASS, /* type */
4571 : : "rebuild_frequencies", /* name */
4572 : : OPTGROUP_NONE, /* optinfo_flags */
4573 : : TV_REBUILD_FREQUENCIES, /* tv_id */
4574 : : PROP_cfg, /* properties_required */
4575 : : 0, /* properties_provided */
4576 : : 0, /* properties_destroyed */
4577 : : 0, /* todo_flags_start */
4578 : : 0, /* todo_flags_finish */
4579 : : };
4580 : :
4581 : : class pass_rebuild_frequencies : public gimple_opt_pass
4582 : : {
4583 : : public:
4584 : 571378 : pass_rebuild_frequencies (gcc::context *ctxt)
4585 : 1142756 : : gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4586 : : {}
4587 : :
4588 : : /* opt_pass methods: */
4589 : 285689 : opt_pass * clone () final override
4590 : : {
4591 : 285689 : return new pass_rebuild_frequencies (m_ctxt);
4592 : : }
4593 : 0 : void set_pass_param (unsigned int n, bool param) final override
4594 : : {
4595 : 0 : gcc_assert (n == 0);
4596 : 0 : early_p = param;
4597 : 0 : }
4598 : :
4599 : 1045355 : unsigned int execute (function *) final override
4600 : : {
4601 : 1045355 : rebuild_frequencies ();
4602 : 1045355 : return 0;
4603 : : }
4604 : :
4605 : : private:
4606 : : bool early_p;
4607 : :
4608 : : }; // class pass_rebuild_frequencies
4609 : :
4610 : : } // anon namespace
4611 : :
4612 : : gimple_opt_pass *
4613 : 285689 : make_pass_rebuild_frequencies (gcc::context *ctxt)
4614 : : {
4615 : 285689 : return new pass_rebuild_frequencies (ctxt);
4616 : : }
4617 : :
4618 : : /* Perform a dry run of the branch prediction pass and report comparsion of
4619 : : the predicted and real profile into the dump file. */
4620 : :
4621 : : void
4622 : 12 : report_predictor_hitrates (void)
4623 : : {
4624 : 12 : unsigned nb_loops;
4625 : :
4626 : 12 : loop_optimizer_init (LOOPS_NORMAL);
4627 : 12 : if (dump_file && (dump_flags & TDF_DETAILS))
4628 : 12 : flow_loops_dump (dump_file, NULL, 0);
4629 : :
4630 : 12 : nb_loops = number_of_loops (cfun);
4631 : 12 : if (nb_loops > 1)
4632 : 5 : scev_initialize ();
4633 : :
4634 : 12 : tree_estimate_probability (true);
4635 : :
4636 : 12 : if (nb_loops > 1)
4637 : 5 : scev_finalize ();
4638 : :
4639 : 12 : loop_optimizer_finalize ();
4640 : 12 : }
4641 : :
4642 : : /* Force edge E to be cold.
4643 : : If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4644 : : keep low probability to represent possible error in a guess. This is used
4645 : : i.e. in case we predict loop to likely iterate given number of times but
4646 : : we are not 100% sure.
4647 : :
4648 : : This function locally updates profile without attempt to keep global
4649 : : consistency which cannot be reached in full generality without full profile
4650 : : rebuild from probabilities alone. Doing so is not necessarily a good idea
4651 : : because frequencies and counts may be more realistic then probabilities.
4652 : :
4653 : : In some cases (such as for elimination of early exits during full loop
4654 : : unrolling) the caller can ensure that profile will get consistent
4655 : : afterwards. */
4656 : :
4657 : : void
4658 : 556980 : force_edge_cold (edge e, bool impossible)
4659 : : {
4660 : 556980 : profile_count count_sum = profile_count::zero ();
4661 : 556980 : profile_probability prob_sum = profile_probability::never ();
4662 : 556980 : edge_iterator ei;
4663 : 556980 : edge e2;
4664 : 556980 : bool uninitialized_exit = false;
4665 : :
4666 : : /* When branch probability guesses are not known, then do nothing. */
4667 : 557212 : if (!impossible && !e->count ().initialized_p ())
4668 : 2302 : return;
4669 : :
4670 : 556980 : profile_probability goal = (impossible ? profile_probability::never ()
4671 : 232 : : profile_probability::very_unlikely ());
4672 : :
4673 : : /* If edge is already improbably or cold, just return. */
4674 : 556980 : if (e->probability <= goal
4675 : 49766 : && (!impossible || e->count () == profile_count::zero ()))
4676 : 1579 : return;
4677 : 1665778 : FOR_EACH_EDGE (e2, ei, e->src->succs)
4678 : 1110377 : if (e2 != e)
4679 : : {
4680 : 554976 : if (e->flags & EDGE_FAKE)
4681 : 0 : continue;
4682 : 554976 : if (e2->count ().initialized_p ())
4683 : 554769 : count_sum += e2->count ();
4684 : 554976 : if (e2->probability.initialized_p ())
4685 : 554769 : prob_sum += e2->probability;
4686 : : else
4687 : : uninitialized_exit = true;
4688 : : }
4689 : :
4690 : : /* If we are not guessing profiles but have some other edges out,
4691 : : just assume the control flow goes elsewhere. */
4692 : 555401 : if (uninitialized_exit)
4693 : 207 : e->probability = goal;
4694 : : /* If there are other edges out of e->src, redistribute probabilitity
4695 : : there. */
4696 : 555194 : else if (prob_sum > profile_probability::never ())
4697 : : {
4698 : 554195 : if (dump_file && (dump_flags & TDF_DETAILS))
4699 : : {
4700 : 998 : fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4701 : : "probability to other edges. Original probability: ",
4702 : 998 : e->src->index, e->dest->index,
4703 : : impossible ? "impossible" : "cold");
4704 : 998 : e->probability.dump (dump_file);
4705 : 998 : fprintf (dump_file, "\n");
4706 : : }
4707 : 554195 : set_edge_probability_and_rescale_others (e, goal);
4708 : 554195 : if (current_ir_type () != IR_GIMPLE
4709 : 554195 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4710 : 142498 : update_br_prob_note (e->src);
4711 : : }
4712 : : /* If all edges out of e->src are unlikely, the basic block itself
4713 : : is unlikely. */
4714 : : else
4715 : : {
4716 : 999 : if (prob_sum == profile_probability::never ())
4717 : 779 : e->probability = profile_probability::always ();
4718 : : else
4719 : : {
4720 : 220 : if (impossible)
4721 : 220 : e->probability = profile_probability::never ();
4722 : : /* If BB has some edges out that are not impossible, we cannot
4723 : : assume that BB itself is. */
4724 : : impossible = false;
4725 : : }
4726 : 999 : if (current_ir_type () != IR_GIMPLE
4727 : 999 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4728 : 42 : update_br_prob_note (e->src);
4729 : 999 : if (e->src->count == profile_count::zero ())
4730 : 157 : return;
4731 : 1684 : if (count_sum == profile_count::zero () && impossible)
4732 : : {
4733 : 600 : bool found = false;
4734 : 600 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4735 : : ;
4736 : 573 : else if (current_ir_type () == IR_GIMPLE)
4737 : 1146 : for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4738 : 2393 : !gsi_end_p (gsi); gsi_next (&gsi))
4739 : : {
4740 : 1854 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4741 : : {
4742 : : found = true;
4743 : : break;
4744 : : }
4745 : : }
4746 : : /* FIXME: Implement RTL path. */
4747 : : else
4748 : : found = true;
4749 : 573 : if (!found)
4750 : : {
4751 : 566 : if (dump_file && (dump_flags & TDF_DETAILS))
4752 : 0 : fprintf (dump_file,
4753 : : "Making bb %i impossible and dropping count to 0.\n",
4754 : 0 : e->src->index);
4755 : 566 : e->src->count = profile_count::zero ();
4756 : 1204 : FOR_EACH_EDGE (e2, ei, e->src->preds)
4757 : 638 : force_edge_cold (e2, impossible);
4758 : : return;
4759 : : }
4760 : : }
4761 : :
4762 : : /* If we did not adjusting, the source basic block has no likely edeges
4763 : : leaving other direction. In that case force that bb cold, too.
4764 : : This in general is difficult task to do, but handle special case when
4765 : : BB has only one predecestor. This is common case when we are updating
4766 : : after loop transforms. */
4767 : 552 : if (!(prob_sum > profile_probability::never ())
4768 : 276 : && count_sum == profile_count::zero ()
4769 : 98 : && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4770 : 40 : > (impossible ? 0 : 1))
4771 : : {
4772 : 39 : int old_frequency = e->src->count.to_frequency (cfun);
4773 : 39 : if (dump_file && (dump_flags & TDF_DETAILS))
4774 : 0 : fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4775 : : impossible ? "impossible" : "cold");
4776 : 39 : int new_frequency = MIN (e->src->count.to_frequency (cfun),
4777 : : impossible ? 0 : 1);
4778 : 0 : if (impossible)
4779 : 16 : e->src->count = profile_count::zero ();
4780 : : else
4781 : 23 : e->src->count = e->count ().apply_scale (new_frequency,
4782 : : old_frequency);
4783 : 39 : force_edge_cold (single_pred_edge (e->src), impossible);
4784 : : }
4785 : 2 : else if (dump_file && (dump_flags & TDF_DETAILS)
4786 : 237 : && maybe_hot_bb_p (cfun, e->src))
4787 : 0 : fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4788 : : impossible ? "impossible" : "cold");
4789 : : }
4790 : : }
4791 : :
4792 : : #if CHECKING_P
4793 : :
4794 : : namespace selftest {
4795 : :
4796 : : /* Test that value range of predictor values defined in predict.def is
4797 : : within range (50, 100]. */
4798 : :
4799 : : struct branch_predictor
4800 : : {
4801 : : const char *name;
4802 : : int probability;
4803 : : };
4804 : :
4805 : : #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4806 : :
4807 : : static void
4808 : 4 : test_prediction_value_range ()
4809 : : {
4810 : 4 : branch_predictor predictors[] = {
4811 : : #include "predict.def"
4812 : : { NULL, PROB_UNINITIALIZED }
4813 : : };
4814 : :
4815 : 216 : for (unsigned i = 0; predictors[i].name != NULL; i++)
4816 : : {
4817 : 212 : if (predictors[i].probability == PROB_UNINITIALIZED)
4818 : 28 : continue;
4819 : :
4820 : 184 : unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4821 : 212 : ASSERT_TRUE (p >= 50 && p <= 100);
4822 : : }
4823 : 4 : }
4824 : :
4825 : : #undef DEF_PREDICTOR
4826 : :
4827 : : /* Run all of the selfests within this file. */
4828 : :
4829 : : void
4830 : 4 : predict_cc_tests ()
4831 : : {
4832 : 4 : test_prediction_value_range ();
4833 : 4 : }
4834 : :
4835 : : } // namespace selftest
4836 : : #endif /* CHECKING_P. */
|
