Line data Source code
1 : /* Branch prediction routines for the GNU compiler.
2 : Copyright (C) 2000-2026 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 57219 : get_hot_bb_threshold ()
127 : {
128 57219 : 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 57219 : return min_count;
141 : }
142 :
143 : /* Set the threshold for hot BB counts. */
144 :
145 : void
146 360 : set_hot_bb_threshold (gcov_type min)
147 : {
148 360 : min_count = min;
149 360 : }
150 :
151 : /* Return TRUE if COUNT is considered to be hot in function FUN. */
152 :
153 : bool
154 1025713096 : maybe_hot_count_p (struct function *fun, profile_count count)
155 : {
156 1025713096 : if (!count.initialized_p ())
157 : return true;
158 935050287 : if (count.ipa () == profile_count::zero ())
159 4554072 : return false;
160 930496215 : if (!count.ipa_p ())
161 : {
162 930398774 : struct cgraph_node *node = cgraph_node::get (fun->decl);
163 930398774 : if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
164 : {
165 930398774 : if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
166 : return false;
167 930333941 : if (node->frequency == NODE_FREQUENCY_HOT)
168 : return true;
169 : }
170 930329849 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
171 : return true;
172 930126508 : if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
173 930126508 : && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
174 21681427 : return false;
175 908445081 : if (count * param_hot_bb_frequency_fraction
176 908445081 : < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
177 : return false;
178 : return true;
179 : }
180 : /* Code executed at most once is not hot. */
181 97441 : if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
182 : return false;
183 57005 : 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 1015524397 : maybe_hot_bb_p (struct function *fun, const_basic_block bb)
191 : {
192 1015524397 : gcc_checking_assert (fun);
193 1015524397 : 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 9469081 : maybe_hot_edge_p (edge e)
201 : {
202 9469081 : 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 56374972 : probably_never_executed (struct function *fun, profile_count count)
210 : {
211 56374972 : gcc_checking_assert (fun);
212 56374972 : if (count.ipa () == profile_count::zero ())
213 1523500 : 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 54851472 : if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
220 : {
221 3324 : const int unlikely_frac = param_unlikely_bb_count_fraction;
222 3324 : if (count * unlikely_frac >= profile_info->runs)
223 : return false;
224 : return true;
225 : }
226 3168 : if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
227 54848256 : && (cgraph_node::get (fun->decl)->frequency
228 54845088 : == 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 17459437 : probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
237 : {
238 17459437 : 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 120843812 : unlikely_executed_edge_p (edge e)
245 : {
246 122681234 : return (e->src->count == profile_count::zero ()
247 118661747 : || e->probability == profile_probability::never ())
248 113818021 : || (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 113257628 : || ((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 41047610 : probably_never_executed_edge_p (struct function *fun, edge e)
258 : {
259 41047610 : if (unlikely_executed_edge_p (e))
260 : return true;
261 38915535 : 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 2477115851 : optimize_function_for_size_p (struct function *fun)
268 : {
269 2477115851 : if (!fun || !fun->decl)
270 197980484 : return optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
271 2374679822 : cgraph_node *n = cgraph_node::get (fun->decl);
272 2374679822 : if (n)
273 2329896156 : 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 228609451 : optimize_function_for_speed_p (struct function *fun)
281 : {
282 228609451 : 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 999157884 : optimize_bb_for_size_p (const_basic_block bb)
299 : {
300 999157884 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
301 :
302 1985926868 : if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
303 26880467 : ret = OPTIMIZE_SIZE_MAX;
304 999157884 : if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun, bb))
305 : ret = OPTIMIZE_SIZE_BALANCED;
306 999157884 : return ret;
307 : }
308 :
309 : /* Return TRUE if basic block BB should be optimized for speed. */
310 :
311 : bool
312 932983159 : optimize_bb_for_speed_p (const_basic_block bb)
313 : {
314 932983159 : 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 5311001 : bb_optimization_type (const_basic_block bb)
321 : {
322 5311001 : return (optimize_bb_for_speed_p (bb)
323 5311001 : ? OPTIMIZE_FOR_SPEED
324 5311001 : : OPTIMIZE_FOR_SIZE);
325 : }
326 :
327 : /* Return TRUE if edge E should be optimized for size. */
328 :
329 : optimize_size_level
330 9893300 : optimize_edge_for_size_p (edge e)
331 : {
332 9893300 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
333 :
334 9893300 : if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
335 : ret = OPTIMIZE_SIZE_MAX;
336 9675626 : if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
337 : ret = OPTIMIZE_SIZE_BALANCED;
338 9893300 : return ret;
339 : }
340 :
341 : /* Return TRUE if edge E should be optimized for speed. */
342 :
343 : bool
344 4339961 : optimize_edge_for_speed_p (edge e)
345 : {
346 4339961 : 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 219867638 : optimize_insn_for_size_p (void)
353 : {
354 219867638 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
355 219867638 : if (ret < OPTIMIZE_SIZE_BALANCED && !crtl->maybe_hot_insn_p)
356 219867638 : ret = OPTIMIZE_SIZE_BALANCED;
357 219867638 : return ret;
358 : }
359 :
360 : /* Return TRUE if the current function is optimized for speed. */
361 :
362 : bool
363 85752174 : optimize_insn_for_speed_p (void)
364 : {
365 85752174 : 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 7192 : insn_optimization_type ()
373 : {
374 7192 : return (optimize_insn_for_speed_p ()
375 7192 : ? OPTIMIZE_FOR_SPEED
376 7192 : : OPTIMIZE_FOR_SIZE);
377 : }
378 :
379 : /* Return TRUE if LOOP should be optimized for size. */
380 :
381 : optimize_size_level
382 752833 : optimize_loop_for_size_p (class loop *loop)
383 : {
384 752833 : return optimize_bb_for_size_p (loop->header);
385 : }
386 :
387 : /* Return TRUE if LOOP should be optimized for speed. */
388 :
389 : bool
390 15362868 : optimize_loop_for_speed_p (class loop *loop)
391 : {
392 15362868 : 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 1212920 : optimize_loop_nest_for_speed_p (class loop *loop)
399 : {
400 1212920 : class loop *l = loop;
401 1212920 : if (optimize_loop_for_speed_p (loop))
402 : return true;
403 35217 : l = loop->inner;
404 47600 : while (l && l != loop)
405 : {
406 13812 : if (optimize_loop_for_speed_p (l))
407 : return true;
408 12383 : if (l->inner)
409 : l = l->inner;
410 8289 : else if (l->next)
411 : l = l->next;
412 : else
413 : {
414 19534 : while (l != loop && !l->next)
415 11647 : l = loop_outer (l);
416 7887 : 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 17170 : optimize_loop_nest_for_size_p (class loop *loop)
427 : {
428 17170 : enum optimize_size_level ret = optimize_loop_for_size_p (loop);
429 17170 : class loop *l = loop;
430 :
431 17170 : l = loop->inner;
432 17444 : while (l && l != loop)
433 : {
434 16696 : if (ret == OPTIMIZE_SIZE_NO)
435 : break;
436 274 : ret = MIN (optimize_loop_for_size_p (l), ret);
437 274 : if (l->inner)
438 : l = l->inner;
439 265 : else if (l->next)
440 : l = l->next;
441 : else
442 : {
443 325 : while (l != loop && !l->next)
444 165 : l = loop_outer (l);
445 160 : if (l != loop)
446 4 : l = l->next;
447 : }
448 : }
449 17170 : return ret;
450 : }
451 :
452 : /* Return true if edge E is likely to be well predictable by branch
453 : predictor. */
454 :
455 : bool
456 5760086 : predictable_edge_p (edge e)
457 : {
458 5760086 : if (!e->probability.initialized_p ())
459 : return false;
460 5759319 : if ((e->probability.to_reg_br_prob_base ()
461 5759319 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100)
462 5759319 : || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
463 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100))
464 622788 : return true;
465 : return false;
466 : }
467 :
468 :
469 : /* Set RTL expansion for BB profile. */
470 :
471 : void
472 79163765 : rtl_profile_for_bb (basic_block bb)
473 : {
474 79163765 : crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
475 79163765 : }
476 :
477 : /* Set RTL expansion for edge profile. */
478 :
479 : void
480 11617 : rtl_profile_for_edge (edge e)
481 : {
482 11617 : crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
483 11617 : }
484 :
485 : /* Set RTL expansion to default mode (i.e. when profile info is not known). */
486 : void
487 14270151 : default_rtl_profile (void)
488 : {
489 14270151 : crtl->maybe_hot_insn_p = true;
490 14270151 : }
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 3182571 : gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
537 : {
538 3182571 : struct edge_prediction *i;
539 3182571 : edge_prediction **preds = bb_predictions->get (bb);
540 :
541 3182571 : if (!preds)
542 : return false;
543 :
544 1585580 : for (i = *preds; i; i = i->ep_next)
545 824761 : 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 1095381 : edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
555 : {
556 1095381 : struct edge_prediction *i;
557 1095381 : basic_block bb = e->src;
558 1095381 : edge_prediction **preds = bb_predictions->get (bb);
559 1095381 : if (!preds)
560 : return false;
561 :
562 136517 : int probability = predictor_info[(int) predictor].hitrate;
563 :
564 136517 : if (taken != TAKEN)
565 136347 : probability = REG_BR_PROB_BASE - probability;
566 :
567 4850630 : for (i = *preds; i; i = i->ep_next)
568 4718518 : if (i->ep_predictor == predictor
569 4581839 : && i->ep_edge == e
570 4405 : && 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 88180 : predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
593 : {
594 88180 : gcc_assert (any_condjump_p (insn));
595 88180 : if (!flag_guess_branch_prob)
596 : return;
597 :
598 176262 : add_reg_note (insn, REG_BR_PRED,
599 88131 : 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 88180 : predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
608 : enum prediction taken)
609 : {
610 88180 : int probability = predictor_info[(int) predictor].hitrate;
611 88180 : gcc_assert (probability != PROB_UNINITIALIZED);
612 :
613 88180 : if (taken != TAKEN)
614 5864 : probability = REG_BR_PROB_BASE - probability;
615 :
616 88180 : predict_insn (insn, predictor, probability);
617 88180 : }
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 6171444 : gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
642 : {
643 6171444 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
644 6171444 : && EDGE_COUNT (e->src->succs) > 1
645 6171444 : && flag_guess_branch_prob
646 12342888 : && optimize)
647 : {
648 6171444 : struct edge_prediction *i = XNEW (struct edge_prediction);
649 6171444 : edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
650 :
651 6171444 : i->ep_next = preds;
652 6171444 : preds = i;
653 6171444 : i->ep_probability = probability;
654 6171444 : i->ep_predictor = predictor;
655 6171444 : i->ep_edge = e;
656 : }
657 6171444 : }
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 2838053 : filter_predictions (edge_prediction **preds,
665 : bool (*filter) (edge_prediction *, void *), void *data)
666 : {
667 2838053 : if (!bb_predictions)
668 : return;
669 :
670 2838053 : if (preds)
671 : {
672 : struct edge_prediction **prediction = preds;
673 : struct edge_prediction *next;
674 :
675 7862794 : while (*prediction)
676 : {
677 5024741 : if ((*filter) (*prediction, data))
678 4514134 : prediction = &((*prediction)->ep_next);
679 : else
680 : {
681 510607 : next = (*prediction)->ep_next;
682 510607 : free (*prediction);
683 510607 : *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 84334472 : remove_predictions_associated_with_edge (edge e)
702 : {
703 84334472 : 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 11437229 : clear_bb_predictions (basic_block bb)
714 : {
715 11437229 : edge_prediction **preds = bb_predictions->get (bb);
716 11437229 : struct edge_prediction *pred, *next;
717 :
718 11437229 : if (!preds)
719 : return;
720 :
721 9234002 : for (pred = *preds; pred; pred = next)
722 : {
723 5660837 : next = pred->ep_next;
724 5660837 : free (pred);
725 : }
726 3573165 : *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 1146658 : can_predict_insn_p (const rtx_insn *insn)
734 : {
735 1146658 : return (JUMP_P (insn)
736 341404 : && any_condjump_p (insn)
737 1487536 : && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
738 : }
739 :
740 : /* Predict edge E by given predictor if possible. */
741 :
742 : void
743 5075936 : predict_edge_def (edge e, enum br_predictor predictor,
744 : enum prediction taken)
745 : {
746 5075936 : int probability = predictor_info[(int) predictor].hitrate;
747 :
748 5075936 : if (taken != TAKEN)
749 4090773 : probability = REG_BR_PROB_BASE - probability;
750 :
751 5075936 : predict_edge (e, predictor, probability);
752 5075936 : }
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 12804368 : invert_br_probabilities (rtx insn)
759 : {
760 12804368 : rtx note;
761 :
762 37867322 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
763 25062954 : if (REG_NOTE_KIND (note) == REG_BR_PROB)
764 25449566 : XINT (note, 0) = profile_probability::from_reg_br_prob_note
765 12724783 : (XINT (note, 0)).invert ().to_reg_br_prob_note ();
766 12338171 : 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 12804368 : }
770 :
771 : /* Dump information about the branch prediction to the output file. */
772 :
773 : static void
774 12055672 : 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 12055672 : edge e = ep_edge;
779 12055672 : edge_iterator ei;
780 :
781 12055672 : if (!file)
782 12053805 : return;
783 :
784 1867 : if (e == NULL)
785 1247 : FOR_EACH_EDGE (e, ei, bb->succs)
786 1247 : if (! (e->flags & EDGE_FALLTHRU))
787 : break;
788 :
789 1867 : char edge_info_str[128];
790 1867 : if (ep_edge)
791 620 : sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
792 620 : ep_edge->dest->index);
793 : else
794 1247 : edge_info_str[0] = '\0';
795 :
796 1867 : fprintf (file, " %s heuristics%s%s: %.2f%%",
797 1867 : predictor_info[predictor].name,
798 1867 : edge_info_str, reason_messages[reason],
799 1867 : probability * 100.0 / REG_BR_PROB_BASE);
800 :
801 1867 : if (bb->count.initialized_p ())
802 : {
803 264 : fprintf (file, " exec ");
804 264 : bb->count.dump (file);
805 264 : if (e && e->count ().initialized_p () && bb->count.to_gcov_type ())
806 : {
807 183 : fprintf (file, " hit ");
808 183 : e->count ().dump (file);
809 366 : fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
810 183 : / bb->count.to_gcov_type ());
811 : }
812 : }
813 :
814 1867 : 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 1867 : if (dump_file && (dump_flags & TDF_DETAILS)
819 1116 : && bb->count.precise_p ()
820 1890 : && 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 174569507 : unlikely_executed_stmt_p (gimple *stmt)
833 : {
834 174569507 : 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 12358090 : if (gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE)
840 12312933 : || gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE_TRAP)
841 24671017 : || gimple_call_builtin_p (stmt, BUILT_IN_TRAP))
842 78421 : return true;
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 12279669 : if (gimple_bb (stmt)->count.reliable_p ()
854 183216179 : && gimple_bb (stmt)->count.nonzero_p ())
855 : return false;
856 : /* NORETURN attribute alone is not strong enough: exit() may be quite
857 : likely executed once during program run. */
858 12279404 : if (gimple_call_fntype (stmt)
859 11770628 : && lookup_attribute ("cold",
860 11770628 : TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
861 12279404 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
862 : return true;
863 12279404 : tree decl = gimple_call_fndecl (stmt);
864 12279404 : if (!decl)
865 : return false;
866 11535235 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
867 11535235 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
868 : return true;
869 :
870 11230448 : cgraph_node *n = cgraph_node::get (decl);
871 11230448 : if (!n)
872 : return false;
873 :
874 11224238 : availability avail;
875 11224238 : n = n->ultimate_alias_target (&avail);
876 11224238 : if (avail < AVAIL_AVAILABLE)
877 : return false;
878 3268081 : if (!n->analyzed
879 3268041 : || n->decl == current_function_decl)
880 : return false;
881 3249789 : return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
882 : }
883 :
884 : /* Return true if BB is unlikely executed. */
885 :
886 : static bool
887 32588814 : unlikely_executed_bb_p (basic_block bb)
888 : {
889 32588814 : if (bb->count == profile_count::zero ())
890 0 : return true;
891 32588814 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
892 : return false;
893 65177628 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
894 197451982 : !gsi_end_p (gsi); gsi_next (&gsi))
895 : {
896 174569507 : if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
897 : return true;
898 174172645 : 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 8539131 : set_even_probabilities (basic_block bb,
913 : hash_set<edge> *unlikely_edges = NULL,
914 : hash_set<edge_prediction *> *likely_edges = NULL)
915 : {
916 8539131 : unsigned nedges = 0, unlikely_count = 0;
917 8539131 : edge e = NULL;
918 8539131 : edge_iterator ei;
919 8539131 : profile_probability all = profile_probability::always ();
920 :
921 18716755 : FOR_EACH_EDGE (e, ei, bb->succs)
922 10177624 : if (e->probability.initialized_p ())
923 9149587 : all -= e->probability;
924 1028037 : else if (!unlikely_executed_edge_p (e))
925 : {
926 618128 : nedges++;
927 618128 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
928 : {
929 5099 : all -= profile_probability::very_unlikely ();
930 5099 : unlikely_count++;
931 : }
932 : }
933 :
934 : /* Make the distribution even if all edges are unlikely. */
935 8539131 : unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
936 8539131 : if (unlikely_count == nedges)
937 : {
938 8031481 : unlikely_edges = NULL;
939 8031481 : unlikely_count = 0;
940 : }
941 :
942 : /* If we have one likely edge, then use its probability and distribute
943 : remaining probabilities as even. */
944 8539131 : if (likely_count == 1)
945 : {
946 11358 : FOR_EACH_EDGE (e, ei, bb->succs)
947 7576 : 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 8535349 : unsigned scale = nedges - unlikely_count;
979 18705397 : FOR_EACH_EDGE (e, ei, bb->succs)
980 10170048 : if (e->probability.initialized_p ())
981 : ;
982 1028013 : else if (!unlikely_executed_edge_p (e))
983 : {
984 618104 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
985 5098 : e->probability = profile_probability::very_unlikely ();
986 : else
987 613006 : e->probability = (all / scale).guessed ();
988 : }
989 : else
990 409909 : e->probability = profile_probability::never ();
991 : }
992 8539131 : }
993 :
994 : /* Add REG_BR_PROB note to JUMP with PROB. */
995 :
996 : void
997 5258096 : add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
998 : {
999 5258096 : gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
1000 5258096 : add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
1001 5258096 : }
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 573329 : combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
1008 : {
1009 573329 : rtx prob_note;
1010 573329 : rtx *pnote;
1011 573329 : rtx note;
1012 573329 : int best_probability = PROB_EVEN;
1013 573329 : enum br_predictor best_predictor = END_PREDICTORS;
1014 573329 : int combined_probability = REG_BR_PROB_BASE / 2;
1015 573329 : int d;
1016 573329 : bool first_match = false;
1017 573329 : bool found = false;
1018 :
1019 573329 : if (!can_predict_insn_p (insn))
1020 : {
1021 402890 : set_even_probabilities (bb);
1022 402890 : return;
1023 : }
1024 :
1025 170439 : prob_note = find_reg_note (insn, REG_BR_PROB, 0);
1026 170439 : pnote = ®_NOTES (insn);
1027 170439 : 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 258570 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1034 88131 : if (REG_NOTE_KIND (note) == REG_BR_PRED)
1035 : {
1036 88131 : enum br_predictor predictor = ((enum br_predictor)
1037 88131 : INTVAL (XEXP (XEXP (note, 0), 0)));
1038 88131 : int probability = INTVAL (XEXP (XEXP (note, 0), 1));
1039 :
1040 88131 : found = true;
1041 88131 : if (best_predictor > predictor
1042 88131 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1043 88131 : best_probability = probability, best_predictor = predictor;
1044 :
1045 88131 : d = (combined_probability * probability
1046 88131 : + (REG_BR_PROB_BASE - combined_probability)
1047 88131 : * (REG_BR_PROB_BASE - probability));
1048 :
1049 : /* Use int64_t math to avoid overflows of 32bit integers. */
1050 88131 : 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 88131 : combined_probability = ((((int64_t) combined_probability)
1055 88131 : * probability
1056 88131 : * REG_BR_PROB_BASE + (d / 2)) / d);
1057 : }
1058 :
1059 : /* Decide which heuristic to use. In case we didn't match anything,
1060 : use no_prediction heuristic, in case we did match, use either
1061 : first match or Dempster-Shaffer theory depending on the flags. */
1062 :
1063 170439 : if (best_predictor != END_PREDICTORS)
1064 237 : first_match = true;
1065 :
1066 170439 : if (!found)
1067 82308 : dump_prediction (dump_file, PRED_NO_PREDICTION,
1068 : combined_probability, bb);
1069 : else
1070 : {
1071 88131 : if (!first_match)
1072 87894 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
1073 : bb, !first_match ? REASON_NONE : REASON_IGNORED);
1074 : else
1075 237 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
1076 : bb, first_match ? REASON_NONE : REASON_IGNORED);
1077 : }
1078 :
1079 170439 : if (first_match)
1080 237 : combined_probability = best_probability;
1081 170439 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1082 :
1083 429009 : while (*pnote)
1084 : {
1085 88131 : if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1086 : {
1087 88131 : enum br_predictor predictor = ((enum br_predictor)
1088 88131 : INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1089 88131 : int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1090 :
1091 88131 : dump_prediction (dump_file, predictor, probability, bb,
1092 88131 : (!first_match || best_predictor == predictor)
1093 88131 : ? REASON_NONE : REASON_IGNORED);
1094 88131 : *pnote = XEXP (*pnote, 1);
1095 : }
1096 : else
1097 0 : pnote = &XEXP (*pnote, 1);
1098 : }
1099 :
1100 170439 : if (!prob_note)
1101 : {
1102 170439 : profile_probability p
1103 170439 : = profile_probability::from_reg_br_prob_base (combined_probability);
1104 170439 : add_reg_br_prob_note (insn, p);
1105 :
1106 : /* Save the prediction into CFG in case we are seeing non-degenerated
1107 : conditional jump. */
1108 170439 : if (!single_succ_p (bb))
1109 : {
1110 170439 : BRANCH_EDGE (bb)->probability = p;
1111 170439 : FALLTHRU_EDGE (bb)->probability
1112 340878 : = BRANCH_EDGE (bb)->probability.invert ();
1113 : }
1114 : }
1115 0 : else if (!single_succ_p (bb))
1116 : {
1117 0 : profile_probability prob = profile_probability::from_reg_br_prob_note
1118 0 : (XINT (prob_note, 0));
1119 :
1120 0 : BRANCH_EDGE (bb)->probability = prob;
1121 0 : FALLTHRU_EDGE (bb)->probability = prob.invert ();
1122 : }
1123 : else
1124 0 : single_succ_edge (bb)->probability = profile_probability::always ();
1125 : }
1126 :
1127 : /* Edge prediction hash traits. */
1128 :
1129 : struct predictor_hash: pointer_hash <edge_prediction>
1130 : {
1131 :
1132 : static inline hashval_t hash (const edge_prediction *);
1133 : static inline bool equal (const edge_prediction *, const edge_prediction *);
1134 : };
1135 :
1136 : /* Calculate hash value of an edge prediction P based on predictor and
1137 : normalized probability. */
1138 :
1139 : inline hashval_t
1140 12795140 : predictor_hash::hash (const edge_prediction *p)
1141 : {
1142 12795140 : inchash::hash hstate;
1143 12795140 : hstate.add_int (p->ep_predictor);
1144 :
1145 12795140 : int prob = p->ep_probability;
1146 12795140 : if (prob > REG_BR_PROB_BASE / 2)
1147 1648138 : prob = REG_BR_PROB_BASE - prob;
1148 :
1149 12795140 : hstate.add_int (prob);
1150 :
1151 12795140 : return hstate.end ();
1152 : }
1153 :
1154 : /* Return true whether edge predictions P1 and P2 use the same predictor and
1155 : have equal (or opposed probability). */
1156 :
1157 : inline bool
1158 2947332 : predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1159 : {
1160 2947332 : return (p1->ep_predictor == p2->ep_predictor
1161 2947332 : && (p1->ep_probability == p2->ep_probability
1162 0 : || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1163 : }
1164 :
1165 : struct predictor_hash_traits: predictor_hash,
1166 : typed_noop_remove <edge_prediction *> {};
1167 :
1168 : /* Return true if edge prediction P is not in DATA hash set. */
1169 :
1170 : static bool
1171 5024733 : not_removed_prediction_p (edge_prediction *p, void *data)
1172 : {
1173 5024733 : hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1174 5024733 : return !remove->contains (p);
1175 : }
1176 :
1177 : /* Prune predictions for a basic block BB. Currently we do following
1178 : clean-up steps:
1179 :
1180 : 1) remove duplicate prediction that is guessed with the same probability
1181 : (different than 1/2) to both edge
1182 : 2) remove duplicates for a prediction that belongs with the same probability
1183 : to a single edge
1184 :
1185 : */
1186 :
1187 : static void
1188 3300932 : prune_predictions_for_bb (basic_block bb)
1189 : {
1190 3300932 : edge_prediction **preds = bb_predictions->get (bb);
1191 :
1192 3300932 : if (preds)
1193 : {
1194 2838049 : hash_table <predictor_hash_traits> s (13);
1195 2838049 : hash_set <edge_prediction *> remove;
1196 :
1197 : /* Step 1: identify predictors that should be removed. */
1198 7862782 : for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1199 : {
1200 5024733 : edge_prediction *existing = s.find (pred);
1201 5024733 : if (existing)
1202 : {
1203 257670 : if (pred->ep_edge == existing->ep_edge
1204 0 : && pred->ep_probability == existing->ep_probability)
1205 : {
1206 : /* Remove a duplicate predictor. */
1207 0 : dump_prediction (dump_file, pred->ep_predictor,
1208 : pred->ep_probability, bb,
1209 : REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1210 :
1211 0 : remove.add (pred);
1212 : }
1213 257670 : else if (pred->ep_edge != existing->ep_edge
1214 257670 : && pred->ep_probability == existing->ep_probability
1215 257670 : && pred->ep_probability != REG_BR_PROB_BASE / 2)
1216 : {
1217 : /* Remove both predictors as they predict the same
1218 : for both edges. */
1219 255332 : dump_prediction (dump_file, existing->ep_predictor,
1220 : pred->ep_probability, bb,
1221 : REASON_EDGE_PAIR_DUPLICATE,
1222 : existing->ep_edge);
1223 255332 : dump_prediction (dump_file, pred->ep_predictor,
1224 : pred->ep_probability, bb,
1225 : REASON_EDGE_PAIR_DUPLICATE,
1226 : pred->ep_edge);
1227 :
1228 255332 : remove.add (existing);
1229 255332 : remove.add (pred);
1230 : }
1231 : }
1232 :
1233 5024733 : edge_prediction **slot2 = s.find_slot (pred, INSERT);
1234 5024733 : *slot2 = pred;
1235 : }
1236 :
1237 : /* Step 2: Remove predictors. */
1238 2838049 : filter_predictions (preds, not_removed_prediction_p, &remove);
1239 2838049 : }
1240 3300932 : }
1241 :
1242 : /* Combine predictions into single probability and store them into CFG.
1243 : Remove now useless prediction entries.
1244 : If DRY_RUN is set, only produce dumps and do not modify profile. */
1245 :
1246 : static void
1247 11437229 : combine_predictions_for_bb (basic_block bb, bool dry_run)
1248 : {
1249 11437229 : int best_probability = PROB_EVEN;
1250 11437229 : enum br_predictor best_predictor = END_PREDICTORS;
1251 11437229 : int combined_probability = REG_BR_PROB_BASE / 2;
1252 11437229 : int d;
1253 11437229 : bool first_match = false;
1254 11437229 : bool found = false;
1255 11437229 : struct edge_prediction *pred;
1256 11437229 : int nedges = 0;
1257 11437229 : edge e, first = NULL, second = NULL;
1258 11437229 : edge_iterator ei;
1259 11437229 : int nzero = 0;
1260 11437229 : int nunknown = 0;
1261 :
1262 27410546 : FOR_EACH_EDGE (e, ei, bb->succs)
1263 : {
1264 15973317 : if (!unlikely_executed_edge_p (e))
1265 : {
1266 13623482 : nedges ++;
1267 13623482 : if (first && !second)
1268 : second = e;
1269 10299935 : if (!first)
1270 10212032 : first = e;
1271 : }
1272 2349835 : else if (!e->probability.initialized_p ())
1273 26197 : e->probability = profile_probability::never ();
1274 15973317 : if (!e->probability.initialized_p ())
1275 6101249 : nunknown++;
1276 9872068 : else if (e->probability == profile_probability::never ())
1277 2229096 : nzero++;
1278 : }
1279 :
1280 : /* When there is no successor or only one choice, prediction is easy.
1281 :
1282 : When we have a basic block with more than 2 successors, the situation
1283 : is more complicated as DS theory cannot be used literally.
1284 : More precisely, let's assume we predicted edge e1 with probability p1,
1285 : thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1286 : need to find probability of e.g. m1({b2}), which we don't know.
1287 : The only approximation is to equally distribute 1-p1 to all edges
1288 : different from b1.
1289 :
1290 : According to numbers we've got from SPEC2006 benchark, there's only
1291 : one interesting reliable predictor (noreturn call), which can be
1292 : handled with a bit easier approach. */
1293 11437229 : if (nedges != 2)
1294 : {
1295 8136297 : hash_set<edge> unlikely_edges (4);
1296 8136297 : hash_set<edge_prediction *> likely_edges (4);
1297 :
1298 : /* Identify all edges that have a probability close to very unlikely.
1299 : Doing the approach for very unlikely doesn't worth for doing as
1300 : there's no such probability in SPEC2006 benchmark. */
1301 8136297 : edge_prediction **preds = bb_predictions->get (bb);
1302 8136297 : if (preds)
1303 1881827 : for (pred = *preds; pred; pred = pred->ep_next)
1304 : {
1305 1146711 : if (pred->ep_probability <= PROB_VERY_UNLIKELY
1306 1138091 : || pred->ep_predictor == PRED_COLD_LABEL)
1307 8685 : unlikely_edges.add (pred->ep_edge);
1308 1138026 : else if (pred->ep_probability >= PROB_VERY_LIKELY
1309 1137397 : || pred->ep_predictor == PRED_BUILTIN_EXPECT
1310 1134246 : || pred->ep_predictor == PRED_HOT_LABEL)
1311 3783 : likely_edges.add (pred);
1312 : }
1313 :
1314 : /* It can happen that an edge is both in likely_edges and unlikely_edges.
1315 : Clear both sets in that situation. */
1316 8140079 : for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
1317 8143861 : it != likely_edges.end (); ++it)
1318 3783 : if (unlikely_edges.contains ((*it)->ep_edge))
1319 : {
1320 1 : likely_edges.empty ();
1321 8136298 : unlikely_edges.empty ();
1322 : break;
1323 : }
1324 :
1325 8136297 : if (!dry_run)
1326 8136241 : set_even_probabilities (bb, &unlikely_edges, &likely_edges);
1327 8136297 : clear_bb_predictions (bb);
1328 8136297 : if (dump_file)
1329 : {
1330 1222 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1331 1222 : if (unlikely_edges.is_empty ())
1332 1220 : fprintf (dump_file,
1333 : "%i edges in bb %i predicted to even probabilities\n",
1334 : nedges, bb->index);
1335 : else
1336 : {
1337 2 : fprintf (dump_file,
1338 : "%i edges in bb %i predicted with some unlikely edges\n",
1339 : nedges, bb->index);
1340 11 : FOR_EACH_EDGE (e, ei, bb->succs)
1341 9 : if (!unlikely_executed_edge_p (e))
1342 9 : dump_prediction (dump_file, PRED_COMBINED,
1343 : e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1344 : }
1345 : }
1346 8136297 : return;
1347 8136297 : }
1348 :
1349 3300932 : if (dump_file)
1350 583 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1351 :
1352 3300932 : prune_predictions_for_bb (bb);
1353 :
1354 3300932 : edge_prediction **preds = bb_predictions->get (bb);
1355 :
1356 3300932 : if (preds)
1357 : {
1358 : /* We implement "first match" heuristics and use probability guessed
1359 : by predictor with smallest index. */
1360 7352175 : for (pred = *preds; pred; pred = pred->ep_next)
1361 : {
1362 4514126 : enum br_predictor predictor = pred->ep_predictor;
1363 4514126 : int probability = pred->ep_probability;
1364 :
1365 4514126 : if (pred->ep_edge != first)
1366 1194461 : probability = REG_BR_PROB_BASE - probability;
1367 :
1368 4514126 : found = true;
1369 : /* First match heuristics would be widly confused if we predicted
1370 : both directions. */
1371 4514126 : if (best_predictor > predictor
1372 4325608 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1373 : {
1374 : struct edge_prediction *pred2;
1375 : int prob = probability;
1376 :
1377 2864493 : for (pred2 = (struct edge_prediction *) *preds;
1378 4223452 : pred2; pred2 = pred2->ep_next)
1379 2864493 : if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1380 : {
1381 0 : int probability2 = pred2->ep_probability;
1382 :
1383 0 : if (pred2->ep_edge != first)
1384 0 : probability2 = REG_BR_PROB_BASE - probability2;
1385 :
1386 0 : if ((probability < REG_BR_PROB_BASE / 2) !=
1387 0 : (probability2 < REG_BR_PROB_BASE / 2))
1388 : break;
1389 :
1390 : /* If the same predictor later gave better result, go for it! */
1391 0 : if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1392 0 : || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1393 2864493 : prob = probability2;
1394 : }
1395 1358959 : if (!pred2)
1396 4514126 : best_probability = prob, best_predictor = predictor;
1397 : }
1398 :
1399 4514126 : d = (combined_probability * probability
1400 4514126 : + (REG_BR_PROB_BASE - combined_probability)
1401 4514126 : * (REG_BR_PROB_BASE - probability));
1402 :
1403 : /* Use int64_t math to avoid overflows of 32bit integers. */
1404 4514126 : if (d == 0)
1405 : /* If one probability is 0% and one 100%, avoid division by zero. */
1406 : combined_probability = REG_BR_PROB_BASE / 2;
1407 : else
1408 4514126 : combined_probability = ((((int64_t) combined_probability)
1409 4514126 : * probability
1410 4514126 : * REG_BR_PROB_BASE + (d / 2)) / d);
1411 : }
1412 : }
1413 :
1414 : /* Decide which heuristic to use. In case we didn't match anything,
1415 : use no_prediction heuristic, in case we did match, use either
1416 : first match or Dempster-Shaffer theory depending on the flags. */
1417 :
1418 2838049 : if (best_predictor != END_PREDICTORS)
1419 1262370 : first_match = true;
1420 :
1421 3300932 : if (!found)
1422 531418 : dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1423 : else
1424 : {
1425 2769514 : if (!first_match)
1426 1507144 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1427 : !first_match ? REASON_NONE : REASON_IGNORED);
1428 : else
1429 1262370 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1430 : first_match ? REASON_NONE : REASON_IGNORED);
1431 : }
1432 :
1433 3300932 : if (first_match)
1434 1262370 : combined_probability = best_probability;
1435 3300932 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1436 :
1437 3300932 : if (preds)
1438 : {
1439 7352175 : for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1440 : {
1441 4514126 : enum br_predictor predictor = pred->ep_predictor;
1442 4514126 : int probability = pred->ep_probability;
1443 :
1444 4514126 : dump_prediction (dump_file, predictor, probability, bb,
1445 4514126 : (!first_match || best_predictor == predictor)
1446 4514126 : ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1447 : }
1448 : }
1449 3300932 : clear_bb_predictions (bb);
1450 :
1451 :
1452 : /* If we have only one successor which is unknown, we can compute missing
1453 : probability. */
1454 3300932 : if (nunknown == 1)
1455 : {
1456 1233 : profile_probability prob = profile_probability::always ();
1457 1233 : edge missing = NULL;
1458 :
1459 3699 : FOR_EACH_EDGE (e, ei, bb->succs)
1460 2466 : if (e->probability.initialized_p ())
1461 1233 : prob -= e->probability;
1462 1233 : else if (missing == NULL)
1463 : missing = e;
1464 : else
1465 0 : gcc_unreachable ();
1466 1233 : missing->probability = prob;
1467 : }
1468 : /* If nothing is unknown, we have nothing to update. */
1469 3669382 : else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1470 : ;
1471 2930016 : else if (!dry_run)
1472 : {
1473 2930016 : first->probability
1474 2930016 : = profile_probability::from_reg_br_prob_base (combined_probability);
1475 2930016 : second->probability = first->probability.invert ();
1476 : }
1477 : }
1478 :
1479 : /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1480 : Return the SSA_NAME if the condition satisfies, NULL otherwise.
1481 :
1482 : T1 and T2 should be one of the following cases:
1483 : 1. T1 is SSA_NAME, T2 is NULL
1484 : 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1485 : 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1486 :
1487 : static tree
1488 9398 : strips_small_constant (tree t1, tree t2)
1489 : {
1490 9398 : tree ret = NULL;
1491 9398 : int value = 0;
1492 :
1493 9398 : if (!t1)
1494 : return NULL;
1495 9398 : else if (TREE_CODE (t1) == SSA_NAME)
1496 : ret = t1;
1497 1092 : else if (tree_fits_shwi_p (t1))
1498 93 : value = tree_to_shwi (t1);
1499 : else
1500 : return NULL;
1501 :
1502 8399 : if (!t2)
1503 : return ret;
1504 8399 : else if (tree_fits_shwi_p (t2))
1505 7843 : value = tree_to_shwi (t2);
1506 556 : else if (TREE_CODE (t2) == SSA_NAME)
1507 : {
1508 377 : if (ret)
1509 : return NULL;
1510 : else
1511 : ret = t2;
1512 : }
1513 :
1514 8115 : if (value <= 4 && value >= -4)
1515 : return ret;
1516 : else
1517 629 : return NULL;
1518 : }
1519 :
1520 : /* Return the SSA_NAME in T or T's operands.
1521 : Return NULL if SSA_NAME cannot be found. */
1522 :
1523 : static tree
1524 234809 : get_base_value (tree t)
1525 : {
1526 234809 : if (TREE_CODE (t) == SSA_NAME)
1527 : return t;
1528 :
1529 11121 : if (!BINARY_CLASS_P (t))
1530 : return NULL;
1531 :
1532 9398 : switch (TREE_OPERAND_LENGTH (t))
1533 : {
1534 0 : case 1:
1535 0 : return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1536 9398 : case 2:
1537 9398 : return strips_small_constant (TREE_OPERAND (t, 0),
1538 18796 : TREE_OPERAND (t, 1));
1539 : default:
1540 : return NULL;
1541 : }
1542 : }
1543 :
1544 : /* Check the compare STMT in LOOP. If it compares an induction
1545 : variable to a loop invariant, return true, and save
1546 : LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1547 : Otherwise return false and set LOOP_INVAIANT to NULL. */
1548 :
1549 : static bool
1550 864009 : is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop,
1551 : tree *loop_invariant,
1552 : enum tree_code *compare_code,
1553 : tree *loop_step,
1554 : tree *loop_iv_base)
1555 : {
1556 864009 : tree op0, op1, bound, base;
1557 864009 : affine_iv iv0, iv1;
1558 864009 : enum tree_code code;
1559 864009 : tree step;
1560 :
1561 864009 : code = gimple_cond_code (stmt);
1562 864009 : *loop_invariant = NULL;
1563 :
1564 864009 : switch (code)
1565 : {
1566 863135 : case GT_EXPR:
1567 863135 : case GE_EXPR:
1568 863135 : case NE_EXPR:
1569 863135 : case LT_EXPR:
1570 863135 : case LE_EXPR:
1571 863135 : case EQ_EXPR:
1572 863135 : break;
1573 :
1574 : default:
1575 : return false;
1576 : }
1577 :
1578 863135 : op0 = gimple_cond_lhs (stmt);
1579 863135 : op1 = gimple_cond_rhs (stmt);
1580 :
1581 863135 : if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1582 863116 : || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1583 : return false;
1584 1699430 : if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1585 : return false;
1586 1004968 : if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1587 : return false;
1588 483357 : if (TREE_CODE (iv0.step) != INTEGER_CST
1589 480576 : || TREE_CODE (iv1.step) != INTEGER_CST)
1590 : return false;
1591 546237 : if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1592 532473 : || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1593 13962 : return false;
1594 :
1595 460055 : if (integer_zerop (iv0.step))
1596 : {
1597 58456 : if (code != NE_EXPR && code != EQ_EXPR)
1598 42452 : code = invert_tree_comparison (code, false);
1599 58456 : bound = iv0.base;
1600 58456 : base = iv1.base;
1601 58456 : if (tree_fits_shwi_p (iv1.step))
1602 : step = iv1.step;
1603 : else
1604 : return false;
1605 : }
1606 : else
1607 : {
1608 401599 : bound = iv1.base;
1609 401599 : base = iv0.base;
1610 401599 : if (tree_fits_shwi_p (iv0.step))
1611 : step = iv0.step;
1612 : else
1613 : return false;
1614 : }
1615 :
1616 453406 : if (TREE_CODE (bound) != INTEGER_CST)
1617 159274 : bound = get_base_value (bound);
1618 159274 : if (!bound)
1619 : return false;
1620 451659 : if (TREE_CODE (base) != INTEGER_CST)
1621 75535 : base = get_base_value (base);
1622 75535 : if (!base)
1623 : return false;
1624 :
1625 449771 : *loop_invariant = bound;
1626 449771 : *compare_code = code;
1627 449771 : *loop_step = step;
1628 449771 : *loop_iv_base = base;
1629 449771 : return true;
1630 : }
1631 :
1632 : /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1633 :
1634 : static bool
1635 6944 : expr_coherent_p (tree t1, tree t2)
1636 : {
1637 6944 : gimple *stmt;
1638 6944 : tree ssa_name_1 = NULL;
1639 6944 : tree ssa_name_2 = NULL;
1640 :
1641 6944 : gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1642 6944 : gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1643 :
1644 6944 : if (t1 == t2)
1645 : return true;
1646 :
1647 2972 : if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1648 : return true;
1649 1742 : if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1650 : return false;
1651 :
1652 : /* Check to see if t1 is expressed/defined with t2. */
1653 318 : stmt = SSA_NAME_DEF_STMT (t1);
1654 318 : gcc_assert (stmt != NULL);
1655 318 : if (is_gimple_assign (stmt))
1656 : {
1657 194 : ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1658 194 : if (ssa_name_1 && ssa_name_1 == t2)
1659 : return true;
1660 : }
1661 :
1662 : /* Check to see if t2 is expressed/defined with t1. */
1663 318 : stmt = SSA_NAME_DEF_STMT (t2);
1664 318 : gcc_assert (stmt != NULL);
1665 318 : if (is_gimple_assign (stmt))
1666 : {
1667 194 : ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1668 194 : if (ssa_name_2 && ssa_name_2 == t1)
1669 : return true;
1670 : }
1671 :
1672 : /* Compare if t1 and t2's def_stmts are identical. */
1673 318 : if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1674 : return true;
1675 : else
1676 : return false;
1677 : }
1678 :
1679 : /* Return true if E is predicted by one of loop heuristics. */
1680 :
1681 : static bool
1682 6078938 : predicted_by_loop_heuristics_p (basic_block bb)
1683 : {
1684 6078938 : struct edge_prediction *i;
1685 6078938 : edge_prediction **preds = bb_predictions->get (bb);
1686 :
1687 6078938 : if (!preds)
1688 : return false;
1689 :
1690 2125051 : for (i = *preds; i; i = i->ep_next)
1691 1811079 : if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1692 1811079 : || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1693 : || i->ep_predictor == PRED_LOOP_ITERATIONS
1694 : || i->ep_predictor == PRED_LOOP_EXIT
1695 : || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1696 : || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1697 : return true;
1698 : return false;
1699 : }
1700 :
1701 : /* Predict branch probability of BB when BB contains a branch that compares
1702 : an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1703 : loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1704 :
1705 : E.g.
1706 : for (int i = 0; i < bound; i++) {
1707 : if (i < bound - 2)
1708 : computation_1();
1709 : else
1710 : computation_2();
1711 : }
1712 :
1713 : In this loop, we will predict the branch inside the loop to be taken. */
1714 :
1715 : static void
1716 2026276 : predict_iv_comparison (class loop *loop, basic_block bb,
1717 : tree loop_bound_var,
1718 : tree loop_iv_base_var,
1719 : enum tree_code loop_bound_code,
1720 : int loop_bound_step)
1721 : {
1722 2026276 : tree compare_var, compare_base;
1723 2026276 : enum tree_code compare_code;
1724 2026276 : tree compare_step_var;
1725 2026276 : edge then_edge;
1726 2026276 : edge_iterator ei;
1727 :
1728 2026276 : if (predicted_by_loop_heuristics_p (bb))
1729 2024679 : return;
1730 :
1731 4313154 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1732 257884 : if (!stmt)
1733 : return;
1734 257884 : if (!is_comparison_with_loop_invariant_p (stmt,
1735 : loop, &compare_var,
1736 : &compare_code,
1737 : &compare_step_var,
1738 : &compare_base))
1739 : return;
1740 :
1741 : /* Find the taken edge. */
1742 11249 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
1743 11249 : if (then_edge->flags & EDGE_TRUE_VALUE)
1744 : break;
1745 :
1746 : /* When comparing an IV to a loop invariant, NE is more likely to be
1747 : taken while EQ is more likely to be not-taken. */
1748 11152 : if (compare_code == NE_EXPR)
1749 : {
1750 1663 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1751 1663 : return;
1752 : }
1753 9489 : else if (compare_code == EQ_EXPR)
1754 : {
1755 4807 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1756 4807 : return;
1757 : }
1758 :
1759 4682 : if (!expr_coherent_p (loop_iv_base_var, compare_base))
1760 : return;
1761 :
1762 : /* If loop bound, base and compare bound are all constants, we can
1763 : calculate the probability directly. */
1764 4107 : if (tree_fits_shwi_p (loop_bound_var)
1765 2711 : && tree_fits_shwi_p (compare_var)
1766 2574 : && tree_fits_shwi_p (compare_base))
1767 : {
1768 2510 : int probability;
1769 2510 : wi::overflow_type overflow;
1770 2510 : bool overall_overflow = false;
1771 2510 : widest_int compare_count, tem;
1772 :
1773 : /* (loop_bound - base) / compare_step */
1774 2510 : tem = wi::sub (wi::to_widest (loop_bound_var),
1775 5020 : wi::to_widest (compare_base), SIGNED, &overflow);
1776 2510 : overall_overflow |= overflow;
1777 2510 : widest_int loop_count = wi::div_trunc (tem,
1778 2510 : wi::to_widest (compare_step_var),
1779 2510 : SIGNED, &overflow);
1780 2510 : overall_overflow |= overflow;
1781 :
1782 2510 : if (!wi::neg_p (wi::to_widest (compare_step_var))
1783 2510 : ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1784 : {
1785 : /* (loop_bound - compare_bound) / compare_step */
1786 359 : tem = wi::sub (wi::to_widest (loop_bound_var),
1787 718 : wi::to_widest (compare_var), SIGNED, &overflow);
1788 359 : overall_overflow |= overflow;
1789 359 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1790 359 : SIGNED, &overflow);
1791 359 : overall_overflow |= overflow;
1792 : }
1793 : else
1794 : {
1795 : /* (compare_bound - base) / compare_step */
1796 2151 : tem = wi::sub (wi::to_widest (compare_var),
1797 4302 : wi::to_widest (compare_base), SIGNED, &overflow);
1798 2151 : overall_overflow |= overflow;
1799 2151 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1800 2151 : SIGNED, &overflow);
1801 2151 : overall_overflow |= overflow;
1802 : }
1803 2510 : if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1804 2134 : ++compare_count;
1805 2510 : if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1806 175 : ++loop_count;
1807 2510 : if (wi::neg_p (compare_count))
1808 766 : compare_count = 0;
1809 2510 : if (wi::neg_p (loop_count))
1810 801 : loop_count = 0;
1811 2510 : if (loop_count == 0)
1812 : probability = 0;
1813 1694 : else if (wi::cmps (compare_count, loop_count) == 1)
1814 : probability = REG_BR_PROB_BASE;
1815 : else
1816 : {
1817 1650 : tem = compare_count * REG_BR_PROB_BASE;
1818 1650 : tem = wi::udiv_trunc (tem, loop_count);
1819 1650 : probability = tem.to_uhwi ();
1820 : }
1821 :
1822 : /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1823 2510 : if (!overall_overflow)
1824 2510 : predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1825 :
1826 2510 : return;
1827 2510 : }
1828 :
1829 1597 : if (expr_coherent_p (loop_bound_var, compare_var))
1830 : {
1831 932 : if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1832 809 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1833 801 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1834 131 : else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1835 113 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1836 98 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1837 33 : else if (loop_bound_code == NE_EXPR)
1838 : {
1839 : /* If the loop backedge condition is "(i != bound)", we do
1840 : the comparison based on the step of IV:
1841 : * step < 0 : backedge condition is like (i > bound)
1842 : * step > 0 : backedge condition is like (i < bound) */
1843 8 : gcc_assert (loop_bound_step != 0);
1844 8 : if (loop_bound_step > 0
1845 8 : && (compare_code == LT_EXPR
1846 8 : || compare_code == LE_EXPR))
1847 7 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1848 1 : else if (loop_bound_step < 0
1849 0 : && (compare_code == GT_EXPR
1850 0 : || compare_code == GE_EXPR))
1851 0 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1852 : else
1853 1 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1854 : }
1855 : else
1856 : /* The branch is predicted not-taken if loop_bound_code is
1857 : opposite with compare_code. */
1858 25 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1859 : }
1860 665 : else if (expr_coherent_p (loop_iv_base_var, compare_var))
1861 : {
1862 : /* For cases like:
1863 : for (i = s; i < h; i++)
1864 : if (i > s + 2) ....
1865 : The branch should be predicted taken. */
1866 163 : if (loop_bound_step > 0
1867 153 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1868 62 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1869 101 : else if (loop_bound_step < 0
1870 10 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1871 10 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1872 : else
1873 91 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1874 : }
1875 : }
1876 :
1877 : /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1878 : exits are resulted from short-circuit conditions that will generate an
1879 : if_tmp. E.g.:
1880 :
1881 : if (foo() || global > 10)
1882 : break;
1883 :
1884 : This will be translated into:
1885 :
1886 : BB3:
1887 : loop header...
1888 : BB4:
1889 : if foo() goto BB6 else goto BB5
1890 : BB5:
1891 : if global > 10 goto BB6 else goto BB7
1892 : BB6:
1893 : goto BB7
1894 : BB7:
1895 : iftmp = (PHI 0(BB5), 1(BB6))
1896 : if iftmp == 1 goto BB8 else goto BB3
1897 : BB8:
1898 : outside of the loop...
1899 :
1900 : The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1901 : From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1902 : exits. This function takes BB7->BB8 as input, and finds out the extra loop
1903 : exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1904 :
1905 : static void
1906 831291 : predict_extra_loop_exits (class loop *loop, edge exit_edge)
1907 : {
1908 831291 : unsigned i;
1909 831291 : bool check_value_one;
1910 831291 : gimple *lhs_def_stmt;
1911 831291 : gphi *phi_stmt;
1912 831291 : tree cmp_rhs, cmp_lhs;
1913 :
1914 1662582 : gcond *cmp_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1915 817898 : if (!cmp_stmt)
1916 : return;
1917 :
1918 817898 : cmp_rhs = gimple_cond_rhs (cmp_stmt);
1919 817898 : cmp_lhs = gimple_cond_lhs (cmp_stmt);
1920 817898 : if (!TREE_CONSTANT (cmp_rhs)
1921 817898 : || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1922 602513 : return;
1923 215385 : if (TREE_CODE (cmp_lhs) != SSA_NAME)
1924 : return;
1925 :
1926 : /* If check_value_one is true, only the phi_args with value '1' will lead
1927 : to loop exit. Otherwise, only the phi_args with value '0' will lead to
1928 : loop exit. */
1929 215385 : check_value_one = (((integer_onep (cmp_rhs))
1930 215385 : ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1931 215385 : ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1932 :
1933 215385 : lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1934 215385 : if (!lhs_def_stmt)
1935 : return;
1936 :
1937 215385 : phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1938 : if (!phi_stmt)
1939 : return;
1940 :
1941 222929 : for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1942 : {
1943 150100 : edge e1;
1944 150100 : edge_iterator ei;
1945 150100 : tree val = gimple_phi_arg_def (phi_stmt, i);
1946 150100 : edge e = gimple_phi_arg_edge (phi_stmt, i);
1947 :
1948 150100 : if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1949 135559 : continue;
1950 39958 : if ((check_value_one ^ integer_onep (val)) == 1)
1951 19808 : continue;
1952 20150 : if (EDGE_COUNT (e->src->succs) != 1)
1953 : {
1954 5609 : predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1955 : loop);
1956 5609 : continue;
1957 : }
1958 :
1959 31666 : FOR_EACH_EDGE (e1, ei, e->src->preds)
1960 17125 : predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1961 : loop);
1962 : }
1963 : }
1964 :
1965 :
1966 : /* Predict edge probabilities by exploiting loop structure. */
1967 :
1968 : static void
1969 272553 : predict_loops (void)
1970 : {
1971 272553 : basic_block bb;
1972 272553 : hash_set <class loop *> with_recursion(10);
1973 :
1974 5477050 : FOR_EACH_BB_FN (bb, cfun)
1975 : {
1976 5204497 : gimple_stmt_iterator gsi;
1977 5204497 : tree decl;
1978 :
1979 34619501 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1980 24210507 : if (is_gimple_call (gsi_stmt (gsi))
1981 2230146 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1982 26256057 : && recursive_call_p (current_function_decl, decl))
1983 : {
1984 5905 : class loop *loop = bb->loop_father;
1985 12189 : while (loop && !with_recursion.add (loop))
1986 6284 : loop = loop_outer (loop);
1987 : }
1988 : }
1989 :
1990 : /* Try to predict out blocks in a loop that are not part of a
1991 : natural loop. */
1992 1463668 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1993 : {
1994 646009 : basic_block bb, *bbs;
1995 646009 : unsigned j, n_exits = 0;
1996 646009 : class tree_niter_desc niter_desc;
1997 646009 : edge ex;
1998 646009 : class nb_iter_bound *nb_iter;
1999 646009 : enum tree_code loop_bound_code = ERROR_MARK;
2000 646009 : tree loop_bound_step = NULL;
2001 646009 : tree loop_bound_var = NULL;
2002 646009 : tree loop_iv_base = NULL;
2003 646009 : gcond *stmt = NULL;
2004 646009 : bool recursion = with_recursion.contains (loop);
2005 :
2006 646009 : auto_vec<edge> exits = get_loop_exit_edges (loop);
2007 2326821 : FOR_EACH_VEC_ELT (exits, j, ex)
2008 1034803 : if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
2009 878401 : n_exits ++;
2010 646009 : if (!n_exits)
2011 16009 : continue;
2012 :
2013 630000 : if (dump_file && (dump_flags & TDF_DETAILS))
2014 542 : fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
2015 : loop->num, recursion ? " (with recursion)" : "", n_exits);
2016 331 : if (dump_file && (dump_flags & TDF_DETAILS)
2017 630271 : && max_loop_iterations_int (loop) >= 0)
2018 : {
2019 201 : fprintf (dump_file,
2020 : "Loop %d iterates at most %i times.\n", loop->num,
2021 201 : (int)max_loop_iterations_int (loop));
2022 : }
2023 331 : if (dump_file && (dump_flags & TDF_DETAILS)
2024 630271 : && likely_max_loop_iterations_int (loop) >= 0)
2025 : {
2026 201 : fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
2027 201 : loop->num, (int)likely_max_loop_iterations_int (loop));
2028 : }
2029 :
2030 1648617 : FOR_EACH_VEC_ELT (exits, j, ex)
2031 : {
2032 1018617 : tree niter = NULL;
2033 1018617 : HOST_WIDE_INT nitercst;
2034 1018617 : int max = param_max_predicted_iterations;
2035 1018617 : int probability;
2036 1018617 : enum br_predictor predictor;
2037 1018617 : widest_int nit;
2038 :
2039 1018617 : if (unlikely_executed_edge_p (ex)
2040 1018617 : || (ex->flags & EDGE_ABNORMAL_CALL))
2041 140216 : continue;
2042 : /* Loop heuristics do not expect exit conditional to be inside
2043 : inner loop. We predict from innermost to outermost loop. */
2044 878401 : if (predicted_by_loop_heuristics_p (ex->src))
2045 : {
2046 47110 : if (dump_file && (dump_flags & TDF_DETAILS))
2047 0 : fprintf (dump_file, "Skipping exit %i->%i because "
2048 : "it is already predicted.\n",
2049 0 : ex->src->index, ex->dest->index);
2050 47110 : continue;
2051 : }
2052 831291 : predict_extra_loop_exits (loop, ex);
2053 :
2054 831291 : if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
2055 437366 : niter = niter_desc.niter;
2056 437366 : if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
2057 556248 : niter = loop_niter_by_eval (loop, ex);
2058 336 : if (dump_file && (dump_flags & TDF_DETAILS)
2059 831562 : && TREE_CODE (niter) == INTEGER_CST)
2060 : {
2061 190 : fprintf (dump_file, "Exit %i->%i %d iterates ",
2062 190 : ex->src->index, ex->dest->index,
2063 : loop->num);
2064 190 : print_generic_expr (dump_file, niter, TDF_SLIM);
2065 190 : fprintf (dump_file, " times.\n");
2066 : }
2067 :
2068 831291 : if (TREE_CODE (niter) == INTEGER_CST)
2069 : {
2070 287884 : if (tree_fits_uhwi_p (niter)
2071 287884 : && max
2072 575762 : && compare_tree_int (niter, max - 1) == -1)
2073 205082 : nitercst = tree_to_uhwi (niter) + 1;
2074 : else
2075 82802 : nitercst = max;
2076 : predictor = PRED_LOOP_ITERATIONS;
2077 : }
2078 : /* If we have just one exit and we can derive some information about
2079 : the number of iterations of the loop from the statements inside
2080 : the loop, use it to predict this exit. */
2081 543407 : else if (n_exits == 1
2082 543407 : && estimated_stmt_executions (loop, &nit))
2083 : {
2084 9 : if (wi::gtu_p (nit, max))
2085 1 : nitercst = max;
2086 : else
2087 8 : nitercst = nit.to_shwi ();
2088 : predictor = PRED_LOOP_ITERATIONS_GUESSED;
2089 : }
2090 : /* If we have likely upper bound, trust it for very small iteration
2091 : counts. Such loops would otherwise get mispredicted by standard
2092 : LOOP_EXIT heuristics. */
2093 1081219 : else if (n_exits == 1
2094 253888 : && likely_max_stmt_executions (loop, &nit)
2095 686788 : && wi::ltu_p (nit,
2096 286378 : RDIV (REG_BR_PROB_BASE,
2097 : REG_BR_PROB_BASE
2098 : - predictor_info
2099 : [recursion
2100 : ? PRED_LOOP_EXIT_WITH_RECURSION
2101 : : PRED_LOOP_EXIT].hitrate)))
2102 : {
2103 5577 : nitercst = nit.to_shwi ();
2104 5577 : predictor = PRED_LOOP_ITERATIONS_MAX;
2105 : }
2106 : else
2107 : {
2108 537821 : if (dump_file && (dump_flags & TDF_DETAILS))
2109 79 : fprintf (dump_file, "Nothing known about exit %i->%i.\n",
2110 79 : ex->src->index, ex->dest->index);
2111 537821 : continue;
2112 : }
2113 :
2114 293470 : if (dump_file && (dump_flags & TDF_DETAILS))
2115 192 : fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
2116 192 : (int)nitercst, predictor_info[predictor].name);
2117 : /* If the prediction for number of iterations is zero, do not
2118 : predict the exit edges. */
2119 293470 : if (nitercst == 0)
2120 6 : continue;
2121 :
2122 293464 : probability = RDIV (REG_BR_PROB_BASE, nitercst);
2123 293464 : predict_edge (ex, predictor, probability);
2124 1018617 : }
2125 :
2126 : /* Find information about loop bound variables. */
2127 888783 : for (nb_iter = loop->bounds; nb_iter;
2128 258783 : nb_iter = nb_iter->next)
2129 387468 : if (nb_iter->stmt
2130 387468 : && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2131 : {
2132 128685 : stmt = as_a <gcond *> (nb_iter->stmt);
2133 128685 : break;
2134 : }
2135 630000 : if (!stmt)
2136 1002630 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (loop->header));
2137 128685 : if (stmt)
2138 606125 : is_comparison_with_loop_invariant_p (stmt, loop,
2139 : &loop_bound_var,
2140 : &loop_bound_code,
2141 : &loop_bound_step,
2142 : &loop_iv_base);
2143 :
2144 630000 : bbs = get_loop_body (loop);
2145 :
2146 3812571 : for (j = 0; j < loop->num_nodes; j++)
2147 : {
2148 3182571 : edge e;
2149 3182571 : edge_iterator ei;
2150 :
2151 3182571 : bb = bbs[j];
2152 :
2153 : /* Bypass loop heuristics on continue statement. These
2154 : statements construct loops via "non-loop" constructs
2155 : in the source language and are better to be handled
2156 : separately. */
2157 3182571 : if (predicted_by_p (bb, PRED_CONTINUE))
2158 : {
2159 8310 : if (dump_file && (dump_flags & TDF_DETAILS))
2160 0 : fprintf (dump_file, "BB %i predicted by continue.\n",
2161 : bb->index);
2162 8310 : continue;
2163 : }
2164 :
2165 : /* If we already used more reliable loop exit predictors, do not
2166 : bother with PRED_LOOP_EXIT. */
2167 3174261 : if (!predicted_by_loop_heuristics_p (bb))
2168 : {
2169 : /* For loop with many exits we don't want to predict all exits
2170 : with the pretty large probability, because if all exits are
2171 : considered in row, the loop would be predicted to iterate
2172 : almost never. The code to divide probability by number of
2173 : exits is very rough. It should compute the number of exits
2174 : taken in each patch through function (not the overall number
2175 : of exits that might be a lot higher for loops with wide switch
2176 : statements in them) and compute n-th square root.
2177 :
2178 : We limit the minimal probability by 2% to avoid
2179 : EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2180 : as this was causing regression in perl benchmark containing such
2181 : a wide loop. */
2182 :
2183 5154770 : int probability = ((REG_BR_PROB_BASE
2184 2577385 : - predictor_info
2185 : [recursion
2186 2577385 : ? PRED_LOOP_EXIT_WITH_RECURSION
2187 2577385 : : PRED_LOOP_EXIT].hitrate)
2188 2577385 : / n_exits);
2189 2577385 : if (probability < HITRATE (2))
2190 : probability = HITRATE (2);
2191 6259268 : FOR_EACH_EDGE (e, ei, bb->succs)
2192 3681883 : if (e->dest->index < NUM_FIXED_BLOCKS
2193 3681883 : || !flow_bb_inside_loop_p (loop, e->dest))
2194 : {
2195 658924 : if (dump_file && (dump_flags & TDF_DETAILS))
2196 89 : fprintf (dump_file,
2197 : "Predicting exit %i->%i with prob %i.\n",
2198 89 : e->src->index, e->dest->index, probability);
2199 1310983 : predict_edge (e,
2200 : recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2201 : : PRED_LOOP_EXIT, probability);
2202 : }
2203 : }
2204 3174261 : if (loop_bound_var)
2205 2026276 : predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2206 : loop_bound_code,
2207 2026276 : tree_to_shwi (loop_bound_step));
2208 : }
2209 :
2210 : /* In the following code
2211 : for (loop1)
2212 : if (cond)
2213 : for (loop2)
2214 : body;
2215 : guess that cond is unlikely. */
2216 630000 : if (loop_outer (loop)->num)
2217 : {
2218 134206 : basic_block bb = NULL;
2219 134206 : edge preheader_edge = loop_preheader_edge (loop);
2220 :
2221 134206 : if (single_pred_p (preheader_edge->src)
2222 246225 : && single_succ_p (preheader_edge->src))
2223 112019 : preheader_edge = single_pred_edge (preheader_edge->src);
2224 :
2225 : /* Pattern match fortran loop preheader:
2226 : _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2227 : _17 = (logical(kind=4)) _16;
2228 : if (_17 != 0)
2229 : goto <bb 11>;
2230 : else
2231 : goto <bb 13>;
2232 :
2233 : Loop guard branch prediction says nothing about duplicated loop
2234 : headers produced by fortran frontend and in this case we want
2235 : to predict paths leading to this preheader. */
2236 :
2237 134206 : gcond *stmt
2238 268412 : = safe_dyn_cast <gcond *> (*gsi_last_bb (preheader_edge->src));
2239 109565 : if (stmt
2240 109565 : && gimple_cond_code (stmt) == NE_EXPR
2241 35444 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2242 35444 : && integer_zerop (gimple_cond_rhs (stmt)))
2243 : {
2244 14860 : gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2245 14860 : if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2246 6359 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt))
2247 15716 : && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2248 856 : call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2249 14860 : if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2250 830 : && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2251 830 : && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2252 15690 : && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2253 : == PRED_FORTRAN_LOOP_PREHEADER)
2254 22 : bb = preheader_edge->src;
2255 : }
2256 22 : if (!bb)
2257 : {
2258 134184 : if (!dominated_by_p (CDI_DOMINATORS,
2259 134184 : loop_outer (loop)->latch, loop->header))
2260 56411 : predict_paths_leading_to_edge (loop_preheader_edge (loop),
2261 : recursion
2262 : ? PRED_LOOP_GUARD_WITH_RECURSION
2263 : : PRED_LOOP_GUARD,
2264 : NOT_TAKEN,
2265 : loop_outer (loop));
2266 : }
2267 : else
2268 : {
2269 22 : if (!dominated_by_p (CDI_DOMINATORS,
2270 22 : loop_outer (loop)->latch, bb))
2271 0 : predict_paths_leading_to (bb,
2272 : recursion
2273 : ? PRED_LOOP_GUARD_WITH_RECURSION
2274 : : PRED_LOOP_GUARD,
2275 : NOT_TAKEN,
2276 : loop_outer (loop));
2277 : }
2278 : }
2279 :
2280 : /* Free basic blocks from get_loop_body. */
2281 630000 : free (bbs);
2282 918562 : }
2283 272553 : }
2284 :
2285 : /* Attempt to predict probabilities of BB outgoing edges using local
2286 : properties. */
2287 : static void
2288 573329 : bb_estimate_probability_locally (basic_block bb)
2289 : {
2290 573329 : rtx_insn *last_insn = BB_END (bb);
2291 573329 : rtx cond;
2292 :
2293 573329 : if (! can_predict_insn_p (last_insn))
2294 : return;
2295 170439 : cond = get_condition (last_insn, NULL, false, false);
2296 170439 : if (! cond)
2297 : return;
2298 :
2299 : /* Try "pointer heuristic."
2300 : A comparison ptr == 0 is predicted as false.
2301 : Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2302 147598 : if (COMPARISON_P (cond)
2303 147598 : && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2304 146090 : || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2305 : {
2306 1509 : if (GET_CODE (cond) == EQ)
2307 33 : predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2308 1476 : else if (GET_CODE (cond) == NE)
2309 19 : predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2310 : }
2311 : else
2312 :
2313 : /* Try "opcode heuristic."
2314 : EQ tests are usually false and NE tests are usually true. Also,
2315 : most quantities are positive, so we can make the appropriate guesses
2316 : about signed comparisons against zero. */
2317 146089 : switch (GET_CODE (cond))
2318 : {
2319 0 : case CONST_INT:
2320 : /* Unconditional branch. */
2321 0 : predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2322 0 : cond == const0_rtx ? NOT_TAKEN : TAKEN);
2323 0 : break;
2324 :
2325 22003 : case EQ:
2326 22003 : case UNEQ:
2327 : /* Floating point comparisons appears to behave in a very
2328 : unpredictable way because of special role of = tests in
2329 : FP code. */
2330 22003 : if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2331 : ;
2332 : /* Comparisons with 0 are often used for booleans and there is
2333 : nothing useful to predict about them. */
2334 22003 : else if (XEXP (cond, 1) == const0_rtx
2335 578 : || XEXP (cond, 0) == const0_rtx)
2336 : ;
2337 : else
2338 578 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2339 : break;
2340 :
2341 85049 : case NE:
2342 85049 : case LTGT:
2343 : /* Floating point comparisons appears to behave in a very
2344 : unpredictable way because of special role of = tests in
2345 : FP code. */
2346 85049 : if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2347 : ;
2348 : /* Comparisons with 0 are often used for booleans and there is
2349 : nothing useful to predict about them. */
2350 85049 : else if (XEXP (cond, 1) == const0_rtx
2351 79763 : || XEXP (cond, 0) == const0_rtx)
2352 : ;
2353 : else
2354 79763 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2355 : break;
2356 :
2357 0 : case ORDERED:
2358 0 : predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2359 0 : break;
2360 :
2361 52 : case UNORDERED:
2362 52 : predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2363 52 : break;
2364 :
2365 5201 : case LE:
2366 5201 : case LT:
2367 5201 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2368 0 : || XEXP (cond, 1) == constm1_rtx)
2369 5201 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2370 : break;
2371 :
2372 5599 : case GE:
2373 5599 : case GT:
2374 5599 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2375 5532 : || XEXP (cond, 1) == constm1_rtx)
2376 2248 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2377 : break;
2378 :
2379 : default:
2380 : break;
2381 : }
2382 : }
2383 :
2384 : /* Set edge->probability for each successor edge of BB. */
2385 : void
2386 573329 : guess_outgoing_edge_probabilities (basic_block bb)
2387 : {
2388 573329 : bb_estimate_probability_locally (bb);
2389 573329 : combine_predictions_for_insn (BB_END (bb), bb);
2390 573329 : }
2391 :
2392 : static tree expr_expected_value (tree, enum br_predictor *predictor,
2393 : HOST_WIDE_INT *probability);
2394 :
2395 : /* Helper function for expr_expected_value. */
2396 :
2397 : static tree
2398 16028164 : expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2399 : tree op1, enum br_predictor *predictor,
2400 : HOST_WIDE_INT *probability)
2401 : {
2402 16028164 : gimple *def;
2403 :
2404 : /* Reset returned probability value. */
2405 16028164 : *probability = -1;
2406 16028164 : *predictor = PRED_UNCONDITIONAL;
2407 :
2408 16028164 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2409 : {
2410 10222486 : if (TREE_CONSTANT (op0))
2411 : return op0;
2412 :
2413 10218950 : if (code == IMAGPART_EXPR)
2414 : {
2415 51399 : if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2416 : {
2417 49790 : def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2418 49790 : if (is_gimple_call (def)
2419 47652 : && gimple_call_internal_p (def)
2420 97386 : && (gimple_call_internal_fn (def)
2421 : == IFN_ATOMIC_COMPARE_EXCHANGE))
2422 : {
2423 : /* Assume that any given atomic operation has low contention,
2424 : and thus the compare-and-swap operation succeeds. */
2425 5590 : *predictor = PRED_COMPARE_AND_SWAP;
2426 5590 : return build_one_cst (TREE_TYPE (op0));
2427 : }
2428 : }
2429 : }
2430 :
2431 10213360 : if (code != SSA_NAME)
2432 : return NULL_TREE;
2433 :
2434 7983829 : def = SSA_NAME_DEF_STMT (op0);
2435 :
2436 : /* If we were already here, break the infinite cycle. */
2437 7983829 : bool existed_p;
2438 7983829 : expected_value *res
2439 7983829 : = &ssa_expected_value->get_or_insert (SSA_NAME_VERSION (op0),
2440 : &existed_p);
2441 7983829 : if (existed_p)
2442 : {
2443 1666410 : *probability = res->probability;
2444 1666410 : *predictor = res->predictor;
2445 1666410 : return res->val;
2446 : }
2447 6317419 : res->val = NULL_TREE;
2448 6317419 : res->predictor = *predictor;
2449 6317419 : res->probability = *probability;
2450 :
2451 6317419 : if (gphi *phi = dyn_cast <gphi *> (def))
2452 : {
2453 : /* All the arguments of the PHI node must have the same constant
2454 : length. */
2455 905725 : int i, n = gimple_phi_num_args (phi);
2456 905725 : tree val = NULL;
2457 905725 : bool has_nonzero_edge = false;
2458 :
2459 : /* If we already proved that given edge is unlikely, we do not need
2460 : to handle merging of the probabilities. */
2461 1818895 : for (i = 0; i < n && !has_nonzero_edge; i++)
2462 : {
2463 913170 : tree arg = PHI_ARG_DEF (phi, i);
2464 913170 : if (arg == PHI_RESULT (phi))
2465 0 : continue;
2466 913170 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2467 924221 : if (!cnt.initialized_p () || cnt.nonzero_p ())
2468 : has_nonzero_edge = true;
2469 : }
2470 :
2471 1483593 : for (i = 0; i < n; i++)
2472 : {
2473 1480585 : tree arg = PHI_ARG_DEF (phi, i);
2474 1480585 : enum br_predictor predictor2;
2475 :
2476 : /* Skip self-referring parameters, since they does not change
2477 : expected value. */
2478 1480585 : if (arg == PHI_RESULT (phi))
2479 577861 : continue;
2480 :
2481 : /* Skip edges which we already predicted as executing
2482 : zero times. */
2483 1480585 : if (has_nonzero_edge)
2484 : {
2485 1475881 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2486 1475881 : if (cnt.initialized_p () && !cnt.nonzero_p ())
2487 219 : continue;
2488 : }
2489 1480366 : HOST_WIDE_INT probability2;
2490 1480366 : tree new_val = expr_expected_value (arg, &predictor2,
2491 : &probability2);
2492 : /* If we know nothing about value, give up. */
2493 1480366 : if (!new_val)
2494 902717 : return NULL;
2495 :
2496 : /* If this is a first edge, trust its prediction. */
2497 644667 : if (!val)
2498 : {
2499 569949 : val = new_val;
2500 569949 : *predictor = predictor2;
2501 569949 : *probability = probability2;
2502 569949 : continue;
2503 : }
2504 : /* If there are two different values, give up. */
2505 74718 : if (!operand_equal_p (val, new_val, false))
2506 : return NULL;
2507 :
2508 7700 : int p1 = get_predictor_value (*predictor, *probability);
2509 7700 : int p2 = get_predictor_value (predictor2, probability2);
2510 : /* If both predictors agree, it does not matter from which
2511 : edge we enter the basic block. */
2512 7700 : if (*predictor == predictor2 && p1 == p2)
2513 7693 : continue;
2514 : /* The general case has no precise solution, since we do not
2515 : know probabilities of incomming edges, yet.
2516 : Still if value is predicted over all incomming edges, we
2517 : can hope it will be indeed the case. Conservatively
2518 : downgrade prediction quality (so first match merging is not
2519 : performed) and take least successful prediction. */
2520 :
2521 7 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI;
2522 7 : *probability = MIN (p1, p2);
2523 : }
2524 :
2525 3008 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2526 3008 : res->val = val;
2527 3008 : res->predictor = *predictor;
2528 3008 : res->probability = *probability;
2529 3008 : return val;
2530 : }
2531 5411694 : if (is_gimple_assign (def))
2532 : {
2533 4138823 : if (gimple_assign_lhs (def) != op0)
2534 : return NULL;
2535 :
2536 4138823 : tree val = expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2537 : gimple_assign_rhs1 (def),
2538 : gimple_assign_rhs_code (def),
2539 : gimple_assign_rhs2 (def),
2540 : predictor, probability);
2541 4138823 : if (val)
2542 : {
2543 49355 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2544 49355 : res->val = val;
2545 49355 : res->predictor = *predictor;
2546 49355 : res->probability = *probability;
2547 : }
2548 4138823 : return val;
2549 : }
2550 :
2551 1272871 : if (is_gimple_call (def))
2552 : {
2553 876388 : tree decl = gimple_call_fndecl (def);
2554 876388 : if (!decl)
2555 : {
2556 78936 : if (gimple_call_internal_p (def)
2557 78936 : && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2558 : {
2559 33110 : gcc_assert (gimple_call_num_args (def) == 3);
2560 33110 : tree val = gimple_call_arg (def, 0);
2561 33110 : if (TREE_CONSTANT (val))
2562 : return val;
2563 33110 : tree val2 = gimple_call_arg (def, 2);
2564 33110 : gcc_assert (TREE_CODE (val2) == INTEGER_CST
2565 : && tree_fits_uhwi_p (val2)
2566 : && tree_to_uhwi (val2) < END_PREDICTORS);
2567 33110 : *predictor = (enum br_predictor) tree_to_uhwi (val2);
2568 33110 : if (*predictor == PRED_BUILTIN_EXPECT)
2569 8748 : *probability
2570 8748 : = HITRATE (param_builtin_expect_probability);
2571 33110 : val = gimple_call_arg (def, 1);
2572 33110 : res->val = val;
2573 33110 : res->predictor = *predictor;
2574 33110 : res->probability = *probability;
2575 33110 : return val;
2576 : }
2577 : return NULL;
2578 : }
2579 :
2580 797452 : if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2581 : {
2582 12092 : if (predictor)
2583 12092 : *predictor = PRED_MALLOC_NONNULL;
2584 : /* FIXME: This is wrong and we need to convert the logic
2585 : to value ranges. This makes predictor to assume that
2586 : malloc always returns (size_t)1 which is not the same
2587 : as returning non-NULL. */
2588 12092 : tree val = fold_convert (type, boolean_true_node);
2589 12092 : res->val = val;
2590 12092 : res->predictor = *predictor;
2591 12092 : res->probability = *probability;
2592 12092 : return val;
2593 : }
2594 :
2595 785360 : if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2596 430138 : switch (DECL_FUNCTION_CODE (decl))
2597 : {
2598 81260 : case BUILT_IN_EXPECT:
2599 81260 : {
2600 81260 : tree val;
2601 81260 : if (gimple_call_num_args (def) != 2)
2602 : return NULL;
2603 81260 : val = gimple_call_arg (def, 0);
2604 81260 : if (TREE_CONSTANT (val))
2605 : return val;
2606 81260 : *predictor = PRED_BUILTIN_EXPECT;
2607 81260 : *probability
2608 81260 : = HITRATE (param_builtin_expect_probability);
2609 81260 : val = gimple_call_arg (def, 1);
2610 81260 : res->val = val;
2611 81260 : res->predictor = *predictor;
2612 81260 : res->probability = *probability;
2613 81260 : return val;
2614 : }
2615 19 : case BUILT_IN_EXPECT_WITH_PROBABILITY:
2616 19 : {
2617 19 : tree val;
2618 19 : if (gimple_call_num_args (def) != 3)
2619 : return NULL;
2620 19 : val = gimple_call_arg (def, 0);
2621 19 : if (TREE_CONSTANT (val))
2622 : {
2623 0 : res->val = val;
2624 0 : res->predictor = *predictor;
2625 0 : res->probability = *probability;
2626 0 : return val;
2627 : }
2628 : /* Compute final probability as:
2629 : probability * REG_BR_PROB_BASE. */
2630 19 : tree prob = gimple_call_arg (def, 2);
2631 19 : tree t = TREE_TYPE (prob);
2632 19 : tree base = build_int_cst (integer_type_node,
2633 : REG_BR_PROB_BASE);
2634 19 : base = build_real_from_int_cst (t, base);
2635 19 : tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2636 : MULT_EXPR, t, prob, base);
2637 19 : if (TREE_CODE (r) != REAL_CST)
2638 : {
2639 1 : error_at (gimple_location (def),
2640 : "probability %qE must be "
2641 : "constant floating-point expression", prob);
2642 1 : return NULL;
2643 : }
2644 18 : HOST_WIDE_INT probi
2645 18 : = real_to_integer (TREE_REAL_CST_PTR (r));
2646 18 : if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2647 : {
2648 17 : *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2649 17 : *probability = probi;
2650 : }
2651 : else
2652 1 : error_at (gimple_location (def),
2653 : "probability %qE is outside "
2654 : "the range [0.0, 1.0]", prob);
2655 :
2656 18 : val = gimple_call_arg (def, 1);
2657 18 : res->val = val;
2658 18 : res->predictor = *predictor;
2659 18 : res->probability = *probability;
2660 18 : return val;
2661 : }
2662 :
2663 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2664 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2665 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2666 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2667 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2668 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2669 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2670 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2671 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2672 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2673 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2674 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2675 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2676 : /* Assume that any given atomic operation has low contention,
2677 : and thus the compare-and-swap operation succeeds. */
2678 5172 : *predictor = PRED_COMPARE_AND_SWAP;
2679 5172 : res->val = boolean_true_node;
2680 5172 : res->predictor = *predictor;
2681 5172 : res->probability = *probability;
2682 5172 : return boolean_true_node;
2683 1946 : case BUILT_IN_REALLOC:
2684 1946 : case BUILT_IN_GOMP_REALLOC:
2685 1946 : if (predictor)
2686 1946 : *predictor = PRED_MALLOC_NONNULL;
2687 : /* FIXME: This is wrong and we need to convert the logic
2688 : to value ranges. */
2689 1946 : res->val = fold_convert (type, boolean_true_node);
2690 1946 : res->predictor = *predictor;
2691 1946 : res->probability = *probability;
2692 1946 : return res->val;
2693 : default:
2694 : break;
2695 : }
2696 : }
2697 :
2698 1093446 : return NULL;
2699 : }
2700 :
2701 5805678 : if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2702 : {
2703 5395182 : tree res;
2704 5395182 : tree nop0 = op0;
2705 5395182 : tree nop1 = op1;
2706 :
2707 : /* First handle situation where single op is enough to determine final
2708 : value. In this case we can do better job by avoiding the prediction
2709 : merging. */
2710 5395182 : if (TREE_CODE (op0) != INTEGER_CST)
2711 : {
2712 : /* See if expected value of op0 is good enough to determine the result. */
2713 5371081 : nop0 = expr_expected_value (op0, predictor, probability);
2714 5371081 : if (nop0
2715 148384 : && (res = fold_build2 (code, type, nop0, op1)) != NULL
2716 5519465 : && TREE_CODE (res) == INTEGER_CST)
2717 : /* We are now getting conservative probability. Consider for
2718 : example:
2719 : op0 * op1
2720 : If op0 is 0 with probability p, then we will ignore the
2721 : posibility that op0 != 0 and op1 == 0. It does not seem to be
2722 : worthwhile to downgrade prediciton quality for this. */
2723 : return res;
2724 5228510 : if (!nop0)
2725 5246798 : nop0 = op0;
2726 : }
2727 5252611 : enum br_predictor predictor2 = PRED_UNCONDITIONAL;
2728 5252611 : HOST_WIDE_INT probability2 = -1;
2729 5252611 : if (TREE_CODE (op1) != INTEGER_CST)
2730 : {
2731 : /* See if expected value of op1 is good enough to determine the result. */
2732 1608194 : nop1 = expr_expected_value (op1, &predictor2, &probability2);
2733 1608194 : if (nop1
2734 225892 : && (res = fold_build2 (code, type, op0, nop1)) != NULL
2735 1834086 : && TREE_CODE (res) == INTEGER_CST)
2736 : {
2737 : /* Similarly as above we now get conservative probability. */
2738 57 : *predictor = predictor2;
2739 57 : *probability = probability2;
2740 57 : return res;
2741 : }
2742 1608137 : if (!nop1)
2743 5026719 : nop1 = op1;
2744 : }
2745 : /* We already checked if folding one of arguments to constant is good
2746 : enough. Consequently failing to fold both means that we will not
2747 : succeed determining the value. */
2748 5252554 : if (nop0 == op0 || nop1 == op1)
2749 : return NULL;
2750 : /* Finally see if we have two known values. */
2751 236 : res = fold_build2 (code, type, nop0, nop1);
2752 236 : if (TREE_CODE (res) == INTEGER_CST)
2753 : {
2754 161 : HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2755 161 : HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2756 :
2757 : /* If one of predictions is sure, such as PRED_UNCONDITIONAL, we
2758 : can ignore it. */
2759 161 : if (p2 == PROB_ALWAYS)
2760 : return res;
2761 141 : if (p1 == PROB_ALWAYS)
2762 : {
2763 1 : *predictor = predictor2;
2764 1 : *probability = probability2;
2765 1 : return res;
2766 : }
2767 : /* Combine binary predictions.
2768 : Since we do not know about independence of predictors, we
2769 : can not determine value precisely. */
2770 140 : *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2771 : /* If we no longer track useful information, give up. */
2772 140 : if (!*probability)
2773 : return NULL;
2774 : /* Otherwise mark that prediction is a result of combining
2775 : different heuristics, since we do not want it to participate
2776 : in first match merging. It is no longer reliable since
2777 : we do not know if the probabilities are indpenendet. */
2778 140 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS;
2779 :
2780 140 : return res;
2781 : }
2782 : return NULL;
2783 : }
2784 410496 : if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2785 : {
2786 409384 : tree res;
2787 409384 : op0 = expr_expected_value (op0, predictor, probability);
2788 409384 : if (!op0)
2789 : return NULL;
2790 38003 : res = fold_build1 (code, type, op0);
2791 38003 : if (TREE_CONSTANT (res))
2792 : return res;
2793 : return NULL;
2794 : }
2795 : return NULL;
2796 : }
2797 :
2798 : /* Return constant EXPR will likely have at execution time, NULL if unknown.
2799 : The function is used by builtin_expect branch predictor so the evidence
2800 : must come from this construct and additional possible constant folding.
2801 :
2802 : We may want to implement more involved value guess (such as value range
2803 : propagation based prediction), but such tricks shall go to new
2804 : implementation. */
2805 :
2806 : static tree
2807 8895502 : expr_expected_value (tree expr, enum br_predictor *predictor,
2808 : HOST_WIDE_INT *probability)
2809 : {
2810 8895502 : enum tree_code code;
2811 8895502 : tree op0, op1;
2812 :
2813 8895502 : if (TREE_CONSTANT (expr))
2814 : {
2815 867647 : *predictor = PRED_UNCONDITIONAL;
2816 867647 : *probability = -1;
2817 867647 : return expr;
2818 : }
2819 :
2820 8027855 : extract_ops_from_tree (expr, &code, &op0, &op1);
2821 8027855 : return expr_expected_value_1 (TREE_TYPE (expr),
2822 8027855 : op0, code, op1, predictor, probability);
2823 : }
2824 :
2825 :
2826 : /* Return probability of a PREDICTOR. If the predictor has variable
2827 : probability return passed PROBABILITY. */
2828 :
2829 : static HOST_WIDE_INT
2830 156328 : get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2831 : {
2832 156328 : switch (predictor)
2833 : {
2834 90352 : case PRED_BUILTIN_EXPECT:
2835 90352 : case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2836 90352 : case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
2837 90352 : case PRED_COMBINED_VALUE_PREDICTIONS:
2838 90352 : gcc_assert (probability != -1);
2839 : return probability;
2840 65976 : default:
2841 65976 : gcc_assert (probability == -1);
2842 65976 : return predictor_info[(int) predictor].hitrate;
2843 : }
2844 : }
2845 :
2846 : /* Predict using opcode of the last statement in basic block. */
2847 : static void
2848 11437229 : tree_predict_by_opcode (basic_block bb)
2849 : {
2850 11437229 : edge then_edge;
2851 11437229 : tree op0, op1;
2852 11437229 : tree type;
2853 11437229 : tree val;
2854 11437229 : enum tree_code cmp;
2855 11437229 : edge_iterator ei;
2856 11437229 : enum br_predictor predictor;
2857 11437229 : HOST_WIDE_INT probability;
2858 :
2859 11437229 : gimple *stmt = *gsi_last_bb (bb);
2860 11437229 : if (!stmt)
2861 7575743 : return;
2862 :
2863 10969337 : if (gswitch *sw = dyn_cast <gswitch *> (stmt))
2864 : {
2865 26477 : tree index = gimple_switch_index (sw);
2866 26477 : tree val = expr_expected_value (index, &predictor, &probability);
2867 26477 : if (val && TREE_CODE (val) == INTEGER_CST)
2868 : {
2869 4 : edge e = find_taken_edge_switch_expr (sw, val);
2870 4 : if (predictor == PRED_BUILTIN_EXPECT)
2871 : {
2872 4 : int percent = param_builtin_expect_probability;
2873 4 : gcc_assert (percent >= 0 && percent <= 100);
2874 4 : predict_edge (e, PRED_BUILTIN_EXPECT,
2875 4 : HITRATE (percent));
2876 : }
2877 : else
2878 0 : predict_edge_def (e, predictor, TAKEN);
2879 : }
2880 : }
2881 :
2882 10969337 : if (gimple_code (stmt) != GIMPLE_COND)
2883 : return;
2884 3992359 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
2885 3992359 : if (then_edge->flags & EDGE_TRUE_VALUE)
2886 : break;
2887 3861486 : op0 = gimple_cond_lhs (stmt);
2888 3861486 : op1 = gimple_cond_rhs (stmt);
2889 3861486 : cmp = gimple_cond_code (stmt);
2890 3861486 : type = TREE_TYPE (op0);
2891 3861486 : val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1,
2892 : &predictor, &probability);
2893 3861486 : if (val && TREE_CODE (val) == INTEGER_CST)
2894 : {
2895 140606 : HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2896 140606 : if (integer_zerop (val))
2897 114832 : prob = REG_BR_PROB_BASE - prob;
2898 140606 : predict_edge (then_edge, predictor, prob);
2899 : }
2900 : /* Try "pointer heuristic."
2901 : A comparison ptr == 0 is predicted as false.
2902 : Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2903 3861486 : if (POINTER_TYPE_P (type))
2904 : {
2905 565118 : if (cmp == EQ_EXPR)
2906 228561 : predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2907 336557 : else if (cmp == NE_EXPR)
2908 317427 : predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2909 : }
2910 : else
2911 :
2912 : /* Try "opcode heuristic."
2913 : EQ tests are usually false and NE tests are usually true. Also,
2914 : most quantities are positive, so we can make the appropriate guesses
2915 : about signed comparisons against zero. */
2916 3296368 : switch (cmp)
2917 : {
2918 886178 : case EQ_EXPR:
2919 886178 : case UNEQ_EXPR:
2920 : /* Floating point comparisons appears to behave in a very
2921 : unpredictable way because of special role of = tests in
2922 : FP code. */
2923 886178 : if (FLOAT_TYPE_P (type))
2924 : ;
2925 : /* Comparisons with 0 are often used for booleans and there is
2926 : nothing useful to predict about them. */
2927 873679 : else if (integer_zerop (op0) || integer_zerop (op1))
2928 : ;
2929 : else
2930 346137 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2931 : break;
2932 :
2933 1572780 : case NE_EXPR:
2934 1572780 : case LTGT_EXPR:
2935 : /* Floating point comparisons appears to behave in a very
2936 : unpredictable way because of special role of = tests in
2937 : FP code. */
2938 1572780 : if (FLOAT_TYPE_P (type))
2939 : ;
2940 : /* Comparisons with 0 are often used for booleans and there is
2941 : nothing useful to predict about them. */
2942 1456993 : else if (integer_zerop (op0)
2943 1456993 : || integer_zerop (op1))
2944 : ;
2945 : else
2946 529840 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2947 : break;
2948 :
2949 2305 : case ORDERED_EXPR:
2950 2305 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2951 2305 : break;
2952 :
2953 2586 : case UNORDERED_EXPR:
2954 2586 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2955 2586 : break;
2956 :
2957 345388 : case LE_EXPR:
2958 345388 : case LT_EXPR:
2959 345388 : if (integer_zerop (op1)
2960 282669 : || integer_onep (op1)
2961 275465 : || integer_all_onesp (op1)
2962 275410 : || real_zerop (op1)
2963 272161 : || real_onep (op1)
2964 617044 : || real_minus_onep (op1))
2965 73736 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2966 : break;
2967 :
2968 479749 : case GE_EXPR:
2969 479749 : case GT_EXPR:
2970 479749 : if (integer_zerop (op1)
2971 416635 : || integer_onep (op1)
2972 404966 : || integer_all_onesp (op1)
2973 404692 : || real_zerop (op1)
2974 403144 : || real_onep (op1)
2975 882068 : || real_minus_onep (op1))
2976 77454 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2977 : break;
2978 :
2979 : default:
2980 : break;
2981 : }
2982 : }
2983 :
2984 : /* Returns TRUE if the STMT is exit(0) like statement. */
2985 :
2986 : static bool
2987 833056 : is_exit_with_zero_arg (const gimple *stmt)
2988 : {
2989 : /* This is not exit, _exit or _Exit. */
2990 833056 : if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2991 829178 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2992 1662212 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2993 : return false;
2994 :
2995 : /* Argument is an interger zero. */
2996 3900 : return integer_zerop (gimple_call_arg (stmt, 0));
2997 : }
2998 :
2999 : /* Try to guess whether the value of return means error code. */
3000 :
3001 : static enum br_predictor
3002 706064 : return_prediction (tree val, enum prediction *prediction)
3003 : {
3004 : /* VOID. */
3005 706064 : if (!val)
3006 : return PRED_NO_PREDICTION;
3007 : /* Different heuristics for pointers and scalars. */
3008 706064 : if (POINTER_TYPE_P (TREE_TYPE (val)))
3009 : {
3010 : /* NULL is usually not returned. */
3011 143777 : if (integer_zerop (val))
3012 : {
3013 32936 : *prediction = NOT_TAKEN;
3014 32936 : return PRED_NULL_RETURN;
3015 : }
3016 : }
3017 562287 : else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
3018 : {
3019 : /* Negative return values are often used to indicate
3020 : errors. */
3021 460372 : if (TREE_CODE (val) == INTEGER_CST
3022 460372 : && tree_int_cst_sgn (val) < 0)
3023 : {
3024 12862 : *prediction = NOT_TAKEN;
3025 12862 : return PRED_NEGATIVE_RETURN;
3026 : }
3027 : /* Constant return values seems to be commonly taken.
3028 : Zero/one often represent booleans so exclude them from the
3029 : heuristics. */
3030 447510 : if (TREE_CONSTANT (val)
3031 447510 : && (!integer_zerop (val) && !integer_onep (val)))
3032 : {
3033 75065 : *prediction = NOT_TAKEN;
3034 75065 : return PRED_CONST_RETURN;
3035 : }
3036 : }
3037 : return PRED_NO_PREDICTION;
3038 : }
3039 :
3040 : /* Return zero if phi result could have values other than -1, 0 or 1,
3041 : otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
3042 : values are used or likely. */
3043 :
3044 : static int
3045 62651 : zero_one_minusone (gphi *phi, int limit)
3046 : {
3047 62651 : int phi_num_args = gimple_phi_num_args (phi);
3048 62651 : int ret = 0;
3049 209704 : for (int i = 0; i < phi_num_args; i++)
3050 : {
3051 157468 : tree t = PHI_ARG_DEF (phi, i);
3052 157468 : if (TREE_CODE (t) != INTEGER_CST)
3053 71610 : continue;
3054 85858 : wide_int w = wi::to_wide (t);
3055 85858 : if (w == -1)
3056 5297 : ret |= 1;
3057 80561 : else if (w == 0)
3058 40146 : ret |= 2;
3059 40415 : else if (w == 1)
3060 30000 : ret |= 4;
3061 : else
3062 10415 : return 0;
3063 85858 : }
3064 119932 : for (int i = 0; i < phi_num_args; i++)
3065 : {
3066 103064 : tree t = PHI_ARG_DEF (phi, i);
3067 103064 : if (TREE_CODE (t) == INTEGER_CST)
3068 65937 : continue;
3069 37127 : if (TREE_CODE (t) != SSA_NAME)
3070 : return 0;
3071 37127 : gimple *g = SSA_NAME_DEF_STMT (t);
3072 37127 : if (gimple_code (g) == GIMPLE_PHI && limit > 0)
3073 12362 : if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
3074 : {
3075 465 : ret |= r;
3076 465 : continue;
3077 : }
3078 36662 : if (!is_gimple_assign (g))
3079 : return 0;
3080 13420 : if (gimple_assign_cast_p (g))
3081 : {
3082 3521 : tree rhs1 = gimple_assign_rhs1 (g);
3083 3521 : if (TREE_CODE (rhs1) != SSA_NAME
3084 3521 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
3085 3443 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
3086 4816 : || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3087 : return 0;
3088 1294 : ret |= (2 | 4);
3089 1294 : continue;
3090 1294 : }
3091 9899 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
3092 : return 0;
3093 0 : ret |= (2 | 4);
3094 : }
3095 : return ret;
3096 : }
3097 :
3098 : /* Find the basic block with return expression and look up for possible
3099 : return value trying to apply RETURN_PREDICTION heuristics. */
3100 : static void
3101 2434738 : apply_return_prediction (void)
3102 : {
3103 2434738 : greturn *return_stmt = NULL;
3104 2434738 : tree return_val;
3105 2434738 : edge e;
3106 2434738 : gphi *phi;
3107 2434738 : int phi_num_args, i;
3108 2434738 : enum br_predictor pred;
3109 2434738 : enum prediction direction;
3110 2434738 : edge_iterator ei;
3111 :
3112 2497900 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3113 : {
3114 4999992 : if (greturn *last = safe_dyn_cast <greturn *> (*gsi_last_bb (e->src)))
3115 : {
3116 : return_stmt = last;
3117 : break;
3118 : }
3119 : }
3120 2434738 : if (!e)
3121 2254651 : return;
3122 2405623 : return_val = gimple_return_retval (return_stmt);
3123 2405623 : if (!return_val)
3124 : return;
3125 1354570 : if (TREE_CODE (return_val) != SSA_NAME
3126 999132 : || !SSA_NAME_DEF_STMT (return_val)
3127 2353702 : || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
3128 : return;
3129 180691 : phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
3130 180691 : phi_num_args = gimple_phi_num_args (phi);
3131 180691 : pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
3132 :
3133 : /* Avoid the case where the function returns -1, 0 and 1 values and
3134 : nothing else. Those could be qsort etc. comparison functions
3135 : where the negative return isn't less probable than positive.
3136 : For this require that the function returns at least -1 or 1
3137 : or -1 and a boolean value or comparison result, so that functions
3138 : returning just -1 and 0 are treated as if -1 represents error value. */
3139 359898 : if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
3140 127247 : && !TYPE_UNSIGNED (TREE_TYPE (return_val))
3141 230980 : && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
3142 50289 : if (int r = zero_one_minusone (phi, 3))
3143 16403 : if ((r & (1 | 4)) == (1 | 4))
3144 : return;
3145 :
3146 : /* Avoid the degenerate case where all return values form the function
3147 : belongs to same category (ie they are all positive constants)
3148 : so we can hardly say something about them. */
3149 575738 : for (i = 1; i < phi_num_args; i++)
3150 427787 : if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
3151 : break;
3152 180087 : if (i != phi_num_args)
3153 129722 : for (i = 0; i < phi_num_args; i++)
3154 : {
3155 97586 : pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
3156 97586 : if (pred != PRED_NO_PREDICTION)
3157 51048 : predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
3158 : direction);
3159 : }
3160 : }
3161 :
3162 : /* Look for basic block that contains unlikely to happen events
3163 : (such as noreturn calls) and mark all paths leading to execution
3164 : of this basic blocks as unlikely. */
3165 :
3166 : static void
3167 2434738 : tree_bb_level_predictions (void)
3168 : {
3169 2434738 : basic_block bb;
3170 2434738 : bool has_return_edges = false;
3171 2434738 : edge e;
3172 2434738 : edge_iterator ei;
3173 :
3174 2504122 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3175 2473706 : if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3176 : {
3177 : has_return_edges = true;
3178 : break;
3179 : }
3180 :
3181 2434738 : apply_return_prediction ();
3182 :
3183 13733171 : FOR_EACH_BB_FN (bb, cfun)
3184 : {
3185 11298433 : gimple_stmt_iterator gsi;
3186 :
3187 89897490 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3188 : {
3189 67300624 : gimple *stmt = gsi_stmt (gsi);
3190 67300624 : tree decl;
3191 :
3192 67300624 : if (is_gimple_call (stmt))
3193 : {
3194 6130254 : if (gimple_call_noreturn_p (stmt)
3195 897122 : && has_return_edges
3196 6963310 : && !is_exit_with_zero_arg (stmt))
3197 830520 : predict_paths_leading_to (bb, PRED_NORETURN,
3198 : NOT_TAKEN);
3199 6130254 : decl = gimple_call_fndecl (stmt);
3200 6130254 : if (decl
3201 11883784 : && lookup_attribute ("cold",
3202 5753530 : DECL_ATTRIBUTES (decl)))
3203 520446 : predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3204 : NOT_TAKEN);
3205 6130254 : if (decl && recursive_call_p (current_function_decl, decl))
3206 9725 : predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3207 : NOT_TAKEN);
3208 : }
3209 61170370 : else if (gimple_code (stmt) == GIMPLE_PREDICT)
3210 : {
3211 456567 : predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
3212 : gimple_predict_outcome (stmt));
3213 : /* Keep GIMPLE_PREDICT around so early inlining will propagate
3214 : hints to callers. */
3215 : }
3216 : }
3217 : }
3218 2434738 : }
3219 :
3220 : /* Callback for hash_map::traverse, asserts that the pointer map is
3221 : empty. */
3222 :
3223 : bool
3224 3573141 : assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3225 : void *)
3226 : {
3227 3573141 : gcc_assert (!value);
3228 3573141 : return true;
3229 : }
3230 :
3231 : /* Predict branch probabilities and estimate profile for basic block BB.
3232 : When LOCAL_ONLY is set do not use any global properties of CFG. */
3233 :
3234 : static void
3235 11437229 : tree_estimate_probability_bb (basic_block bb, bool local_only)
3236 : {
3237 11437229 : edge e;
3238 11437229 : edge_iterator ei;
3239 :
3240 27410546 : FOR_EACH_EDGE (e, ei, bb->succs)
3241 : {
3242 : /* Look for block we are guarding (ie we dominate it,
3243 : but it doesn't postdominate us). */
3244 12603876 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3245 12603860 : && !local_only
3246 12435869 : && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3247 24242362 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3248 : {
3249 6424926 : gimple_stmt_iterator bi;
3250 :
3251 : /* The call heuristic claims that a guarded function call
3252 : is improbable. This is because such calls are often used
3253 : to signal exceptional situations such as printing error
3254 : messages. */
3255 36654879 : for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
3256 23805027 : gsi_next (&bi))
3257 : {
3258 26232222 : gimple *stmt = gsi_stmt (bi);
3259 26232222 : if (is_gimple_call (stmt)
3260 3050079 : && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
3261 : /* Constant and pure calls are hardly used to signalize
3262 : something exceptional. */
3263 29011139 : && gimple_has_side_effects (stmt))
3264 : {
3265 2427195 : if (gimple_call_fndecl (stmt))
3266 2364956 : predict_edge_def (e, PRED_CALL, NOT_TAKEN);
3267 62239 : else if (virtual_method_call_p (gimple_call_fn (stmt)))
3268 12788 : predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
3269 : else
3270 49451 : predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
3271 : break;
3272 : }
3273 : }
3274 : }
3275 : }
3276 11437229 : tree_predict_by_opcode (bb);
3277 11437229 : }
3278 :
3279 : /* Predict branch probabilities and estimate profile of the tree CFG.
3280 : This function can be called from the loop optimizers to recompute
3281 : the profile information.
3282 : If DRY_RUN is set, do not modify CFG and only produce dump files. */
3283 :
3284 : void
3285 2434738 : tree_estimate_probability (bool dry_run)
3286 : {
3287 2434738 : basic_block bb;
3288 :
3289 2434738 : connect_infinite_loops_to_exit ();
3290 : /* We use loop_niter_by_eval, which requires that the loops have
3291 : preheaders. */
3292 2434738 : create_preheaders (CP_SIMPLE_PREHEADERS);
3293 2434738 : calculate_dominance_info (CDI_POST_DOMINATORS);
3294 : /* Decide which edges are known to be unlikely. This improves later
3295 : branch prediction. */
3296 2434738 : if (!dry_run)
3297 2434726 : determine_unlikely_bbs ();
3298 :
3299 2434738 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3300 2434738 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3301 :
3302 2434738 : tree_bb_level_predictions ();
3303 2434738 : record_loop_exits ();
3304 :
3305 4869476 : if (number_of_loops (cfun) > 1)
3306 272553 : predict_loops ();
3307 :
3308 13733171 : FOR_EACH_BB_FN (bb, cfun)
3309 11298433 : tree_estimate_probability_bb (bb, false);
3310 :
3311 13733171 : FOR_EACH_BB_FN (bb, cfun)
3312 11298433 : combine_predictions_for_bb (bb, dry_run);
3313 :
3314 2434738 : if (flag_checking)
3315 6007851 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3316 :
3317 4869476 : delete bb_predictions;
3318 2434738 : bb_predictions = NULL;
3319 4869476 : delete ssa_expected_value;
3320 2434738 : ssa_expected_value = NULL;
3321 :
3322 2434738 : if (!dry_run
3323 2434726 : && profile_status_for_fn (cfun) != PROFILE_READ)
3324 2434726 : estimate_bb_frequencies ();
3325 2434738 : free_dominance_info (CDI_POST_DOMINATORS);
3326 2434738 : remove_fake_exit_edges ();
3327 2434738 : }
3328 :
3329 : /* Set edge->probability for each successor edge of BB. */
3330 : void
3331 138796 : tree_guess_outgoing_edge_probabilities (basic_block bb)
3332 : {
3333 138796 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3334 138796 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3335 138796 : tree_estimate_probability_bb (bb, true);
3336 138796 : combine_predictions_for_bb (bb, false);
3337 138796 : if (flag_checking)
3338 138796 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3339 277592 : delete bb_predictions;
3340 138796 : bb_predictions = NULL;
3341 277592 : delete ssa_expected_value;
3342 138796 : ssa_expected_value = NULL;
3343 138796 : }
3344 :
3345 : /* Filter function predicate that returns true for a edge predicate P
3346 : if its edge is equal to DATA. */
3347 :
3348 : static bool
3349 8 : not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
3350 : {
3351 8 : return p->ep_edge != (edge)data || p->ep_predictor != PRED_LOOP_GUARD;
3352 : }
3353 :
3354 : /* Predict edge E with PRED unless it is already predicted by some predictor
3355 : considered equivalent. */
3356 :
3357 : static void
3358 1067535 : maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3359 : {
3360 1067535 : if (edge_predicted_by_p (e, pred, taken))
3361 : return;
3362 1063138 : if (pred == PRED_LOOP_GUARD
3363 1063138 : && edge_predicted_by_p (e, PRED_LOOP_GUARD_WITH_RECURSION, taken))
3364 : return;
3365 : /* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3366 1063130 : if (pred == PRED_LOOP_GUARD_WITH_RECURSION)
3367 : {
3368 15 : edge_prediction **preds = bb_predictions->get (e->src);
3369 15 : if (preds)
3370 4 : filter_predictions (preds, not_loop_guard_equal_edge_p, e);
3371 : }
3372 1063130 : predict_edge_def (e, pred, taken);
3373 : }
3374 : /* Predict edges to successors of CUR whose sources are not postdominated by
3375 : BB by PRED and recurse to all postdominators. */
3376 :
3377 : static void
3378 2369937 : predict_paths_for_bb (basic_block cur, basic_block bb,
3379 : enum br_predictor pred,
3380 : enum prediction taken,
3381 : bitmap visited, class loop *in_loop = NULL)
3382 : {
3383 2369937 : edge e;
3384 2369937 : edge_iterator ei;
3385 2369937 : basic_block son;
3386 :
3387 : /* If we exited the loop or CUR is unconditional in the loop, there is
3388 : nothing to do. */
3389 2369937 : if (in_loop
3390 2369937 : && (!flow_bb_inside_loop_p (in_loop, cur)
3391 72847 : || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3392 10983 : return;
3393 :
3394 : /* We are looking for all edges forming edge cut induced by
3395 : set of all blocks postdominated by BB. */
3396 5245313 : FOR_EACH_EDGE (e, ei, cur->preds)
3397 2886359 : if (e->src->index >= NUM_FIXED_BLOCKS
3398 2886359 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3399 : {
3400 2233163 : edge e2;
3401 2233163 : edge_iterator ei2;
3402 2233163 : bool found = false;
3403 :
3404 : /* Ignore fake edges and eh, we predict them as not taken anyway. */
3405 2233163 : if (unlikely_executed_edge_p (e))
3406 1170079 : continue;
3407 1063084 : gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3408 :
3409 : /* See if there is an edge from e->src that is not abnormal
3410 : and does not lead to BB and does not exit the loop. */
3411 1937285 : FOR_EACH_EDGE (e2, ei2, e->src->succs)
3412 1908505 : if (e2 != e
3413 1069884 : && !unlikely_executed_edge_p (e2)
3414 1043167 : && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3415 2945496 : && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3416 : {
3417 : found = true;
3418 : break;
3419 : }
3420 :
3421 : /* If there is non-abnormal path leaving e->src, predict edge
3422 : using predictor. Otherwise we need to look for paths
3423 : leading to e->src.
3424 :
3425 : The second may lead to infinite loop in the case we are predicitng
3426 : regions that are only reachable by abnormal edges. We simply
3427 : prevent visiting given BB twice. */
3428 1063084 : if (found)
3429 1034304 : maybe_predict_edge (e, pred, taken);
3430 28780 : else if (bitmap_set_bit (visited, e->src->index))
3431 28736 : predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3432 : }
3433 2358954 : for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3434 2814133 : son;
3435 455179 : son = next_dom_son (CDI_POST_DOMINATORS, son))
3436 455179 : predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3437 : }
3438 :
3439 : /* Sets branch probabilities according to PREDiction and
3440 : FLAGS. */
3441 :
3442 : static void
3443 1817258 : predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3444 : enum prediction taken, class loop *in_loop)
3445 : {
3446 1817258 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3447 1817258 : }
3448 :
3449 : /* Like predict_paths_leading_to but take edge instead of basic block. */
3450 :
3451 : static void
3452 101995 : predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3453 : enum prediction taken, class loop *in_loop)
3454 : {
3455 101995 : bool has_nonloop_edge = false;
3456 101995 : edge_iterator ei;
3457 101995 : edge e2;
3458 :
3459 101995 : basic_block bb = e->src;
3460 191480 : FOR_EACH_EDGE (e2, ei, bb->succs)
3461 122716 : if (e2->dest != e->src && e2->dest != e->dest
3462 44897 : && !unlikely_executed_edge_p (e2)
3463 164963 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3464 : {
3465 : has_nonloop_edge = true;
3466 : break;
3467 : }
3468 :
3469 101995 : if (!has_nonloop_edge)
3470 68764 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3471 : else
3472 33231 : maybe_predict_edge (e, pred, taken);
3473 101995 : }
3474 :
3475 : /* This is used to carry information about basic blocks. It is
3476 : attached to the AUX field of the standard CFG block. */
3477 :
3478 : class block_info
3479 : {
3480 : public:
3481 : /* Estimated frequency of execution of basic_block. */
3482 : sreal frequency;
3483 :
3484 : /* To keep queue of basic blocks to process. */
3485 : basic_block next;
3486 :
3487 : /* Number of predecessors we need to visit first. */
3488 : int npredecessors;
3489 : };
3490 :
3491 : /* Similar information for edges. */
3492 : class edge_prob_info
3493 : {
3494 : public:
3495 : /* In case edge is a loopback edge, the probability edge will be reached
3496 : in case header is. Estimated number of iterations of the loop can be
3497 : then computed as 1 / (1 - back_edge_prob). */
3498 : sreal back_edge_prob;
3499 : /* True if the edge is a loopback edge in the natural loop. */
3500 : unsigned int back_edge:1;
3501 : };
3502 :
3503 : #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3504 : #undef EDGE_INFO
3505 : #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3506 :
3507 : /* Helper function for estimate_bb_frequencies.
3508 : Propagate the frequencies in blocks marked in
3509 : TOVISIT, starting in HEAD. */
3510 :
3511 : static void
3512 3284822 : propagate_freq (basic_block head, bitmap tovisit,
3513 : sreal max_cyclic_prob)
3514 : {
3515 3284822 : basic_block bb;
3516 3284822 : basic_block last;
3517 3284822 : unsigned i;
3518 3284822 : edge e;
3519 3284822 : basic_block nextbb;
3520 3284822 : bitmap_iterator bi;
3521 :
3522 : /* For each basic block we need to visit count number of his predecessors
3523 : we need to visit first. */
3524 26831628 : EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3525 : {
3526 23546806 : edge_iterator ei;
3527 23546806 : int count = 0;
3528 :
3529 23546806 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
3530 :
3531 52476201 : FOR_EACH_EDGE (e, ei, bb->preds)
3532 : {
3533 28929395 : bool visit = bitmap_bit_p (tovisit, e->src->index);
3534 :
3535 28929395 : if (visit && !(e->flags & EDGE_DFS_BACK))
3536 26251125 : count++;
3537 1888528 : else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3538 3 : fprintf (dump_file,
3539 : "Irreducible region hit, ignoring edge to %i->%i\n",
3540 3 : e->src->index, bb->index);
3541 : }
3542 23546806 : BLOCK_INFO (bb)->npredecessors = count;
3543 : /* When function never returns, we will never process exit block. */
3544 23546806 : if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3545 0 : bb->count = profile_count::zero ();
3546 : }
3547 :
3548 3284822 : BLOCK_INFO (head)->frequency = 1;
3549 3284822 : last = head;
3550 26831628 : for (bb = head; bb; bb = nextbb)
3551 : {
3552 23546806 : edge_iterator ei;
3553 23546806 : sreal cyclic_probability = 0;
3554 23546806 : sreal frequency = 0;
3555 :
3556 23546806 : nextbb = BLOCK_INFO (bb)->next;
3557 23546806 : BLOCK_INFO (bb)->next = NULL;
3558 :
3559 : /* Compute frequency of basic block. */
3560 23546806 : if (bb != head)
3561 : {
3562 20261984 : if (flag_checking)
3563 47611209 : FOR_EACH_EDGE (e, ei, bb->preds)
3564 27349614 : gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3565 : || (e->flags & EDGE_DFS_BACK));
3566 :
3567 47612159 : FOR_EACH_EDGE (e, ei, bb->preds)
3568 27350175 : if (EDGE_INFO (e)->back_edge)
3569 1093997 : cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3570 26256178 : else if (!(e->flags & EDGE_DFS_BACK))
3571 : {
3572 : /* FIXME: Graphite is producing edges with no profile. Once
3573 : this is fixed, drop this. */
3574 26251125 : sreal tmp = e->probability.initialized_p () ?
3575 26251125 : e->probability.to_sreal () : 0;
3576 26251125 : frequency += tmp * BLOCK_INFO (e->src)->frequency;
3577 : }
3578 :
3579 20261984 : if (cyclic_probability == 0)
3580 : {
3581 19195304 : BLOCK_INFO (bb)->frequency = frequency;
3582 : }
3583 : else
3584 : {
3585 1066680 : if (cyclic_probability > max_cyclic_prob)
3586 : {
3587 9781 : if (dump_file)
3588 252 : fprintf (dump_file,
3589 : "cyclic probability of bb %i is %f (capped to %f)"
3590 : "; turning freq %f",
3591 : bb->index, cyclic_probability.to_double (),
3592 : max_cyclic_prob.to_double (),
3593 : frequency.to_double ());
3594 :
3595 9781 : cyclic_probability = max_cyclic_prob;
3596 : }
3597 1056899 : else if (dump_file)
3598 111 : fprintf (dump_file,
3599 : "cyclic probability of bb %i is %f; turning freq %f",
3600 : bb->index, cyclic_probability.to_double (),
3601 : frequency.to_double ());
3602 :
3603 1066680 : BLOCK_INFO (bb)->frequency = frequency
3604 1066680 : / (sreal (1) - cyclic_probability);
3605 1066680 : if (dump_file)
3606 363 : fprintf (dump_file, " to %f\n",
3607 363 : BLOCK_INFO (bb)->frequency.to_double ());
3608 : }
3609 : }
3610 :
3611 23546806 : bitmap_clear_bit (tovisit, bb->index);
3612 :
3613 23546806 : e = find_edge (bb, head);
3614 23546806 : if (e)
3615 : {
3616 : /* FIXME: Graphite is producing edges with no profile. Once
3617 : this is fixed, drop this. */
3618 789478 : sreal tmp = e->probability.initialized_p () ?
3619 789478 : e->probability.to_sreal () : 0;
3620 789478 : EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3621 : }
3622 :
3623 : /* Propagate to successor blocks. */
3624 53048219 : FOR_EACH_EDGE (e, ei, bb->succs)
3625 29501413 : if (!(e->flags & EDGE_DFS_BACK)
3626 27611659 : && BLOCK_INFO (e->dest)->npredecessors)
3627 : {
3628 26251125 : BLOCK_INFO (e->dest)->npredecessors--;
3629 26251125 : if (!BLOCK_INFO (e->dest)->npredecessors)
3630 : {
3631 20261984 : if (!nextbb)
3632 : nextbb = e->dest;
3633 : else
3634 7660454 : BLOCK_INFO (last)->next = e->dest;
3635 :
3636 : last = e->dest;
3637 : }
3638 : }
3639 : }
3640 3284822 : }
3641 :
3642 : /* Estimate frequencies in loops at same nest level. */
3643 :
3644 : static void
3645 1096966 : estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3646 : {
3647 1096966 : class loop *loop;
3648 :
3649 1886444 : for (loop = first_loop; loop; loop = loop->next)
3650 : {
3651 789478 : edge e;
3652 789478 : basic_block *bbs;
3653 789478 : unsigned i;
3654 789478 : auto_bitmap tovisit;
3655 :
3656 789478 : estimate_loops_at_level (loop->inner, max_cyclic_prob);
3657 :
3658 : /* Find current loop back edge and mark it. */
3659 789478 : e = loop_latch_edge (loop);
3660 789478 : EDGE_INFO (e)->back_edge = 1;
3661 :
3662 789478 : bbs = get_loop_body (loop);
3663 5934955 : for (i = 0; i < loop->num_nodes; i++)
3664 4355999 : bitmap_set_bit (tovisit, bbs[i]->index);
3665 789478 : free (bbs);
3666 789478 : propagate_freq (loop->header, tovisit, max_cyclic_prob);
3667 789478 : }
3668 1096966 : }
3669 :
3670 : /* Propagates frequencies through structure of loops. */
3671 :
3672 : static void
3673 2495344 : estimate_loops (void)
3674 : {
3675 2495344 : auto_bitmap tovisit;
3676 2495344 : basic_block bb;
3677 7486032 : sreal max_cyclic_prob = (sreal)1
3678 2495344 : - (sreal)1 / (param_max_predicted_iterations + 1);
3679 :
3680 : /* Start by estimating the frequencies in the loops. */
3681 4990688 : if (number_of_loops (cfun) > 1)
3682 307488 : estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3683 :
3684 : /* Now propagate the frequencies through all the blocks. */
3685 21686151 : FOR_ALL_BB_FN (bb, cfun)
3686 : {
3687 19190807 : bitmap_set_bit (tovisit, bb->index);
3688 : }
3689 2495344 : propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3690 2495344 : }
3691 :
3692 : /* Drop the profile for NODE to guessed, and update its frequency based on
3693 : whether it is expected to be hot given the CALL_COUNT. */
3694 :
3695 : static void
3696 0 : drop_profile (struct cgraph_node *node, profile_count call_count)
3697 : {
3698 0 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3699 : /* In the case where this was called by another function with a
3700 : dropped profile, call_count will be 0. Since there are no
3701 : non-zero call counts to this function, we don't know for sure
3702 : whether it is hot, and therefore it will be marked normal below. */
3703 0 : bool hot = maybe_hot_count_p (NULL, call_count);
3704 :
3705 0 : if (dump_file)
3706 0 : fprintf (dump_file,
3707 : "Dropping 0 profile for %s. %s based on calls.\n",
3708 : node->dump_name (),
3709 : hot ? "Function is hot" : "Function is normal");
3710 : /* We only expect to miss profiles for functions that are reached
3711 : via non-zero call edges in cases where the function may have
3712 : been linked from another module or library (COMDATs and extern
3713 : templates). See the comments below for handle_missing_profiles.
3714 : Also, only warn in cases where the missing counts exceed the
3715 : number of training runs. In certain cases with an execv followed
3716 : by a no-return call the profile for the no-return call is not
3717 : dumped and there can be a mismatch. */
3718 0 : if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3719 0 : && call_count > profile_info->runs)
3720 : {
3721 0 : if (flag_profile_correction)
3722 : {
3723 0 : if (dump_file)
3724 0 : fprintf (dump_file,
3725 : "Missing counts for called function %s\n",
3726 : node->dump_name ());
3727 : }
3728 : else
3729 0 : warning (0, "Missing counts for called function %s",
3730 : node->dump_name ());
3731 : }
3732 :
3733 0 : basic_block bb;
3734 0 : if (opt_for_fn (node->decl, flag_guess_branch_prob))
3735 : {
3736 0 : bool clear_zeros
3737 0 : = !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3738 0 : FOR_ALL_BB_FN (bb, fn)
3739 0 : if (clear_zeros || !(bb->count == profile_count::zero ()))
3740 0 : bb->count = bb->count.guessed_local ();
3741 0 : fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3742 : }
3743 : else
3744 : {
3745 0 : FOR_ALL_BB_FN (bb, fn)
3746 0 : bb->count = profile_count::uninitialized ();
3747 0 : fn->cfg->count_max = profile_count::uninitialized ();
3748 : }
3749 :
3750 0 : struct cgraph_edge *e;
3751 0 : for (e = node->callees; e; e = e->next_callee)
3752 0 : e->count = gimple_bb (e->call_stmt)->count;
3753 0 : for (e = node->indirect_calls; e; e = e->next_callee)
3754 0 : e->count = gimple_bb (e->call_stmt)->count;
3755 0 : node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3756 :
3757 0 : profile_status_for_fn (fn)
3758 0 : = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3759 0 : node->frequency
3760 0 : = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3761 0 : }
3762 :
3763 : /* In the case of COMDAT routines, multiple object files will contain the same
3764 : function and the linker will select one for the binary. In that case
3765 : all the other copies from the profile instrument binary will be missing
3766 : profile counts. Look for cases where this happened, due to non-zero
3767 : call counts going to 0-count functions, and drop the profile to guessed
3768 : so that we can use the estimated probabilities and avoid optimizing only
3769 : for size.
3770 :
3771 : The other case where the profile may be missing is when the routine
3772 : is not going to be emitted to the object file, e.g. for "extern template"
3773 : class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3774 : all other cases of non-zero calls to 0-count functions. */
3775 :
3776 : void
3777 604 : handle_missing_profiles (void)
3778 : {
3779 604 : const int unlikely_frac = param_unlikely_bb_count_fraction;
3780 604 : struct cgraph_node *node;
3781 604 : auto_vec<struct cgraph_node *, 64> worklist;
3782 :
3783 : /* See if 0 count function has non-0 count callers. In this case we
3784 : lost some profile. Drop its function profile to PROFILE_GUESSED. */
3785 3393 : FOR_EACH_DEFINED_FUNCTION (node)
3786 : {
3787 2789 : struct cgraph_edge *e;
3788 2789 : profile_count call_count = profile_count::zero ();
3789 2789 : gcov_type max_tp_first_run = 0;
3790 2789 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3791 :
3792 2789 : if (node->count.ipa ().nonzero_p ())
3793 345 : continue;
3794 4667 : for (e = node->callers; e; e = e->next_caller)
3795 2223 : if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3796 : {
3797 8 : call_count = call_count + e->count.ipa ();
3798 :
3799 8 : if (e->caller->tp_first_run > max_tp_first_run)
3800 2223 : max_tp_first_run = e->caller->tp_first_run;
3801 : }
3802 :
3803 : /* If time profile is missing, let assign the maximum that comes from
3804 : caller functions. */
3805 2444 : if (!node->tp_first_run && max_tp_first_run)
3806 4 : node->tp_first_run = max_tp_first_run + 1;
3807 :
3808 2444 : if (call_count > 0
3809 6 : && fn && fn->cfg
3810 2450 : && call_count * unlikely_frac >= profile_info->runs)
3811 : {
3812 0 : drop_profile (node, call_count);
3813 0 : worklist.safe_push (node);
3814 : }
3815 : }
3816 :
3817 : /* Propagate the profile dropping to other 0-count COMDATs that are
3818 : potentially called by COMDATs we already dropped the profile on. */
3819 604 : while (worklist.length () > 0)
3820 : {
3821 0 : struct cgraph_edge *e;
3822 :
3823 0 : node = worklist.pop ();
3824 0 : for (e = node->callees; e; e = e->next_caller)
3825 : {
3826 0 : struct cgraph_node *callee = e->callee;
3827 0 : struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3828 :
3829 0 : if (!(e->count.ipa () == profile_count::zero ())
3830 0 : && callee->count.ipa ().nonzero_p ())
3831 0 : continue;
3832 0 : if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3833 0 : && fn && fn->cfg
3834 0 : && profile_status_for_fn (fn) == PROFILE_READ)
3835 : {
3836 0 : drop_profile (node, profile_count::zero ());
3837 0 : worklist.safe_push (callee);
3838 : }
3839 : }
3840 : }
3841 604 : }
3842 :
3843 : /* Convert counts measured by profile driven feedback to frequencies.
3844 : Return nonzero iff there was any nonzero execution count. */
3845 :
3846 : bool
3847 1736122 : update_max_bb_count (void)
3848 : {
3849 1736122 : profile_count true_count_max = profile_count::uninitialized ();
3850 1736122 : basic_block bb;
3851 :
3852 36551751 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3853 34815629 : true_count_max = profile_count::max_prefer_initialized (true_count_max, bb->count);
3854 :
3855 1736122 : cfun->cfg->count_max = true_count_max;
3856 :
3857 1736122 : return true_count_max.ipa ().nonzero_p ();
3858 : }
3859 :
3860 : /* Return true if function is likely to be expensive, so there is no point to
3861 : optimize performance of prologue, epilogue or do inlining at the expense
3862 : of code size growth. THRESHOLD is the limit of number of instructions
3863 : function can execute at average to be still considered not expensive. */
3864 :
3865 : bool
3866 285068 : expensive_function_p (int threshold)
3867 : {
3868 285068 : basic_block bb;
3869 :
3870 : /* If profile was scaled in a way entry block has count 0, then the function
3871 : is deifnitly taking a lot of time. */
3872 448792 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3873 : return true;
3874 :
3875 244596 : profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3876 244596 : profile_count sum = profile_count::zero ();
3877 3042433 : FOR_EACH_BB_FN (bb, cfun)
3878 : {
3879 2961561 : rtx_insn *insn;
3880 :
3881 2961561 : if (!bb->count.initialized_p ())
3882 : {
3883 2 : if (dump_file)
3884 0 : fprintf (dump_file, "Function is considered expensive because"
3885 : " count of bb %i is not initialized\n", bb->index);
3886 2 : return true;
3887 : }
3888 :
3889 45401379 : FOR_BB_INSNS (bb, insn)
3890 42603542 : if (active_insn_p (insn))
3891 : {
3892 17294682 : sum += bb->count;
3893 17294682 : if (sum > limit)
3894 : return true;
3895 : }
3896 : }
3897 :
3898 : return false;
3899 : }
3900 :
3901 : /* All basic blocks that are reachable only from unlikely basic blocks are
3902 : unlikely. */
3903 :
3904 : void
3905 7276515 : propagate_unlikely_bbs_forward (void)
3906 : {
3907 7276515 : auto_vec<basic_block, 64> worklist;
3908 7276515 : basic_block bb;
3909 7276515 : edge_iterator ei;
3910 7276515 : edge e;
3911 :
3912 7293843 : if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3913 : {
3914 7259187 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3915 7259187 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3916 :
3917 78496408 : while (worklist.length () > 0)
3918 : {
3919 63978034 : bb = worklist.pop ();
3920 142780850 : FOR_EACH_EDGE (e, ei, bb->succs)
3921 80535858 : if (!(e->count () == profile_count::zero ())
3922 95060503 : && !(e->dest->count == profile_count::zero ())
3923 72308563 : && !e->dest->aux)
3924 : {
3925 56718847 : e->dest->aux = (void *)(size_t) 1;
3926 56718847 : worklist.safe_push (e->dest);
3927 : }
3928 : }
3929 : }
3930 :
3931 75190616 : FOR_ALL_BB_FN (bb, cfun)
3932 : {
3933 67914101 : if (!bb->aux)
3934 : {
3935 7871458 : if (!(bb->count == profile_count::zero ())
3936 396236 : && (dump_file && (dump_flags & TDF_DETAILS)))
3937 676 : fprintf (dump_file,
3938 : "Basic block %i is marked unlikely by forward prop\n",
3939 : bb->index);
3940 3936067 : bb->count = profile_count::zero ();
3941 : }
3942 : else
3943 63978034 : bb->aux = NULL;
3944 : }
3945 7276515 : }
3946 :
3947 : /* Determine basic blocks/edges that are known to be unlikely executed and set
3948 : their counters to zero.
3949 : This is done with first identifying obviously unlikely BBs/edges and then
3950 : propagating in both directions. */
3951 :
3952 : static void
3953 5964867 : determine_unlikely_bbs ()
3954 : {
3955 5964867 : basic_block bb;
3956 5964867 : auto_vec<basic_block, 64> worklist;
3957 5964867 : edge_iterator ei;
3958 5964867 : edge e;
3959 :
3960 40466504 : FOR_EACH_BB_FN (bb, cfun)
3961 : {
3962 68606412 : if (!(bb->count == profile_count::zero ())
3963 32588814 : && unlikely_executed_bb_p (bb))
3964 : {
3965 396862 : if (dump_file && (dump_flags & TDF_DETAILS))
3966 0 : fprintf (dump_file, "Basic block %i is locally unlikely\n",
3967 : bb->index);
3968 396862 : bb->count = profile_count::zero ();
3969 : }
3970 :
3971 82958108 : FOR_EACH_EDGE (e, ei, bb->succs)
3972 90625278 : if (!(e->probability == profile_probability::never ())
3973 48456471 : && unlikely_executed_edge_p (e))
3974 : {
3975 2044574 : if (dump_file && (dump_flags & TDF_DETAILS))
3976 26 : fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3977 26 : bb->index, e->dest->index);
3978 2044574 : e->probability = profile_probability::never ();
3979 : }
3980 :
3981 34501637 : gcc_checking_assert (!bb->aux);
3982 : }
3983 5964867 : propagate_unlikely_bbs_forward ();
3984 :
3985 5964867 : auto_vec<int, 64> nsuccs;
3986 5964867 : nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
3987 52396238 : FOR_ALL_BB_FN (bb, cfun)
3988 54984638 : if (!(bb->count == profile_count::zero ())
3989 43739826 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3990 : {
3991 37878104 : nsuccs[bb->index] = 0;
3992 90006737 : FOR_EACH_EDGE (e, ei, bb->succs)
3993 52128633 : if (!(e->probability == profile_probability::never ())
3994 100637578 : && !(e->dest->count == profile_count::zero ()))
3995 47440497 : nsuccs[bb->index]++;
3996 37878104 : if (!nsuccs[bb->index])
3997 1511725 : worklist.safe_push (bb);
3998 : }
3999 7504144 : while (worklist.length () > 0)
4000 : {
4001 1539277 : bb = worklist.pop ();
4002 1539277 : if (bb->count == profile_count::zero ())
4003 0 : continue;
4004 1539277 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4005 : {
4006 1530712 : bool found = false;
4007 3061424 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
4008 2682110 : !gsi_end_p (gsi); gsi_next (&gsi))
4009 2651572 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
4010 : /* stmt_can_terminate_bb_p special cases noreturns because it
4011 : assumes that fake edges are created. We want to know that
4012 : noreturn alone does not imply BB to be unlikely. */
4013 2651572 : || (is_gimple_call (gsi_stmt (gsi))
4014 621170 : && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
4015 : {
4016 : found = true;
4017 : break;
4018 : }
4019 1530712 : if (found)
4020 1500174 : continue;
4021 : }
4022 39103 : if (dump_file && (dump_flags & TDF_DETAILS))
4023 0 : fprintf (dump_file,
4024 : "Basic block %i is marked unlikely by backward prop\n",
4025 : bb->index);
4026 39103 : bb->count = profile_count::zero ();
4027 83472 : FOR_EACH_EDGE (e, ei, bb->preds)
4028 44369 : if (!(e->probability == profile_probability::never ()))
4029 : {
4030 43317 : if (!(e->src->count == profile_count::zero ()))
4031 : {
4032 43315 : gcc_checking_assert (nsuccs[e->src->index] > 0);
4033 43315 : nsuccs[e->src->index]--;
4034 43315 : if (!nsuccs[e->src->index])
4035 27552 : worklist.safe_push (e->src);
4036 : }
4037 : }
4038 : }
4039 : /* Finally all edges from non-0 regions to 0 are unlikely. */
4040 52396238 : FOR_ALL_BB_FN (bb, cfun)
4041 : {
4042 49162019 : if (!(bb->count == profile_count::zero ()))
4043 95773172 : FOR_EACH_EDGE (e, ei, bb->succs)
4044 52072449 : if (!(e->probability == profile_probability::never ())
4045 100511623 : && e->dest->count == profile_count::zero ())
4046 : {
4047 523263 : if (dump_file && (dump_flags & TDF_DETAILS))
4048 0 : fprintf (dump_file, "Edge %i->%i is unlikely because "
4049 : "it enters unlikely block\n",
4050 : bb->index, e->dest->index);
4051 523263 : e->probability = profile_probability::never ();
4052 : }
4053 :
4054 46431371 : edge other = NULL;
4055 :
4056 89750972 : FOR_EACH_EDGE (e, ei, bb->succs)
4057 54148106 : if (e->probability == profile_probability::never ())
4058 : ;
4059 47346072 : else if (other)
4060 : {
4061 : other = NULL;
4062 : break;
4063 : }
4064 : else
4065 : other = e;
4066 46431371 : if (other
4067 46431371 : && !(other->probability == profile_probability::always ()))
4068 : {
4069 8364867 : if (dump_file && (dump_flags & TDF_DETAILS))
4070 6 : fprintf (dump_file, "Edge %i->%i is locally likely\n",
4071 6 : bb->index, other->dest->index);
4072 8364867 : other->probability = profile_probability::always ();
4073 : }
4074 : }
4075 5964888 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
4076 22363 : cgraph_node::get (current_function_decl)->count = profile_count::zero ();
4077 5964867 : }
4078 :
4079 : /* Estimate and propagate basic block frequencies using the given branch
4080 : probabilities. */
4081 :
4082 : static void
4083 2495344 : estimate_bb_frequencies ()
4084 : {
4085 2495344 : basic_block bb;
4086 2495344 : sreal freq_max;
4087 :
4088 2495344 : determine_unlikely_bbs ();
4089 :
4090 2495344 : mark_dfs_back_edges ();
4091 :
4092 2495344 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
4093 : profile_probability::always ();
4094 :
4095 : /* Set up block info for each basic block. */
4096 2495344 : alloc_aux_for_blocks (sizeof (block_info));
4097 2495344 : alloc_aux_for_edges (sizeof (edge_prob_info));
4098 21686151 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4099 : {
4100 19190807 : edge e;
4101 19190807 : edge_iterator ei;
4102 :
4103 41940323 : FOR_EACH_EDGE (e, ei, bb->succs)
4104 : {
4105 : /* FIXME: Graphite is producing edges with no profile. Once
4106 : this is fixed, drop this. */
4107 22749516 : if (e->probability.initialized_p ())
4108 22749484 : EDGE_INFO (e)->back_edge_prob
4109 22749484 : = e->probability.to_sreal ();
4110 : else
4111 : /* back_edge_prob = 0.5 */
4112 32 : EDGE_INFO (e)->back_edge_prob = sreal (1, -1);
4113 : }
4114 : }
4115 :
4116 : /* First compute frequencies locally for each loop from innermost
4117 : to outermost to examine frequencies for back edges. */
4118 2495344 : estimate_loops ();
4119 :
4120 2495344 : freq_max = 0;
4121 16695463 : FOR_EACH_BB_FN (bb, cfun)
4122 14200119 : if (freq_max < BLOCK_INFO (bb)->frequency)
4123 3151052 : freq_max = BLOCK_INFO (bb)->frequency;
4124 :
4125 : /* Scaling frequencies up to maximal profile count may result in
4126 : frequent overflows especially when inlining loops.
4127 : Small scaling results in unnecesary precision loss. Stay in
4128 : the half of the (exponential) range. */
4129 2495344 : freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
4130 2495344 : if (freq_max < 16)
4131 74 : freq_max = 16;
4132 2495344 : profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
4133 2495344 : cfun->cfg->count_max = profile_count::uninitialized ();
4134 21686151 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4135 : {
4136 19190807 : sreal tmp = BLOCK_INFO (bb)->frequency;
4137 19190807 : if (tmp >= 1)
4138 : {
4139 11244007 : gimple_stmt_iterator gsi;
4140 11244007 : tree decl;
4141 :
4142 : /* Self recursive calls can not have frequency greater than 1
4143 : or program will never terminate. This will result in an
4144 : inconsistent bb profile but it is better than greatly confusing
4145 : IPA cost metrics. */
4146 72640283 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4147 50157853 : if (is_gimple_call (gsi_stmt (gsi))
4148 2968935 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
4149 52825324 : && recursive_call_p (current_function_decl, decl))
4150 : {
4151 5584 : if (dump_file)
4152 0 : fprintf (dump_file, "Dropping frequency of recursive call"
4153 : " in bb %i from %f\n", bb->index,
4154 : tmp.to_double ());
4155 5584 : tmp = (sreal)9 / (sreal)10;
4156 5584 : break;
4157 : }
4158 : }
4159 19190807 : tmp = tmp * freq_max;
4160 19190807 : profile_count count = profile_count::from_gcov_type (tmp.to_nearest_int ());
4161 :
4162 : /* If we have profile feedback in which this function was never
4163 : executed, then preserve this info. */
4164 20456780 : if (!(bb->count == profile_count::zero ()))
4165 17924834 : bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
4166 19190807 : cfun->cfg->count_max
4167 19190807 : = profile_count::max_prefer_initialized (cfun->cfg->count_max,
4168 : bb->count);
4169 : }
4170 :
4171 2495344 : free_aux_for_blocks ();
4172 2495344 : free_aux_for_edges ();
4173 2495344 : compute_function_frequency ();
4174 2495344 : }
4175 :
4176 : /* Decide whether function is hot, cold or unlikely executed. */
4177 : void
4178 2525425 : compute_function_frequency (void)
4179 : {
4180 2525425 : basic_block bb;
4181 2525425 : struct cgraph_node *node = cgraph_node::get (current_function_decl);
4182 :
4183 2525425 : if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4184 2525425 : || MAIN_NAME_P (DECL_NAME (current_function_decl)))
4185 92729 : node->only_called_at_startup = true;
4186 2525425 : if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4187 1216 : node->only_called_at_exit = true;
4188 :
4189 2525425 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4190 : {
4191 2516422 : int flags = flags_from_decl_or_type (current_function_decl);
4192 2516422 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4193 : != NULL)
4194 615 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4195 2515807 : else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
4196 : != NULL)
4197 60 : node->frequency = NODE_FREQUENCY_HOT;
4198 2515747 : else if (flags & ECF_NORETURN)
4199 1978 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4200 2513769 : else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4201 79184 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4202 2434585 : else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4203 2434585 : || DECL_STATIC_DESTRUCTOR (current_function_decl))
4204 13963 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4205 2516422 : return;
4206 : }
4207 :
4208 9003 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4209 9003 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4210 : == NULL)
4211 8995 : warn_function_cold (current_function_decl);
4212 9003 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4213 8657 : return;
4214 928 : FOR_EACH_BB_FN (bb, cfun)
4215 : {
4216 817 : if (maybe_hot_bb_p (cfun, bb))
4217 : {
4218 235 : node->frequency = NODE_FREQUENCY_HOT;
4219 235 : return;
4220 : }
4221 582 : if (!probably_never_executed_bb_p (cfun, bb))
4222 528 : node->frequency = NODE_FREQUENCY_NORMAL;
4223 : }
4224 : }
4225 :
4226 : /* Build PREDICT_EXPR. */
4227 : tree
4228 1876524 : build_predict_expr (enum br_predictor predictor, enum prediction taken)
4229 : {
4230 1876524 : tree t = build1 (PREDICT_EXPR, void_type_node,
4231 1876524 : build_int_cst (integer_type_node, predictor));
4232 1876524 : SET_PREDICT_EXPR_OUTCOME (t, taken);
4233 1876524 : return t;
4234 : }
4235 :
4236 : const char *
4237 1242 : predictor_name (enum br_predictor predictor)
4238 : {
4239 1242 : return predictor_info[predictor].name;
4240 : }
4241 :
4242 : /* Predict branch probabilities and estimate profile of the tree CFG. */
4243 :
4244 : namespace {
4245 :
4246 : const pass_data pass_data_profile =
4247 : {
4248 : GIMPLE_PASS, /* type */
4249 : "profile_estimate", /* name */
4250 : OPTGROUP_NONE, /* optinfo_flags */
4251 : TV_BRANCH_PROB, /* tv_id */
4252 : PROP_cfg, /* properties_required */
4253 : 0, /* properties_provided */
4254 : 0, /* properties_destroyed */
4255 : 0, /* todo_flags_start */
4256 : 0, /* todo_flags_finish */
4257 : };
4258 :
4259 : class pass_profile : public gimple_opt_pass
4260 : {
4261 : public:
4262 288775 : pass_profile (gcc::context *ctxt)
4263 577550 : : gimple_opt_pass (pass_data_profile, ctxt)
4264 : {}
4265 :
4266 : /* opt_pass methods: */
4267 2435642 : bool gate (function *) final override { return flag_guess_branch_prob; }
4268 : unsigned int execute (function *) final override;
4269 :
4270 : }; // class pass_profile
4271 :
4272 : unsigned int
4273 2434612 : pass_profile::execute (function *fun)
4274 : {
4275 2434612 : unsigned nb_loops;
4276 :
4277 2434612 : if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4278 : return 0;
4279 :
4280 2434574 : loop_optimizer_init (LOOPS_NORMAL);
4281 2434574 : if (dump_file && (dump_flags & TDF_DETAILS))
4282 2 : flow_loops_dump (dump_file, NULL, 0);
4283 :
4284 2434574 : nb_loops = number_of_loops (fun);
4285 2434574 : if (nb_loops > 1)
4286 272396 : scev_initialize ();
4287 :
4288 2434574 : tree_estimate_probability (false);
4289 2434574 : cfun->cfg->full_profile = true;
4290 :
4291 2434574 : if (nb_loops > 1)
4292 272396 : scev_finalize ();
4293 :
4294 2434574 : loop_optimizer_finalize ();
4295 2434574 : if (dump_file && (dump_flags & TDF_DETAILS))
4296 2 : gimple_dump_cfg (dump_file, dump_flags);
4297 2434574 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4298 2434574 : profile_status_for_fn (fun) = PROFILE_GUESSED;
4299 2434574 : if (dump_file && (dump_flags & TDF_DETAILS))
4300 : {
4301 2 : sreal iterations;
4302 7 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
4303 1 : if (expected_loop_iterations_by_profile (loop, &iterations))
4304 1 : fprintf (dump_file, "Loop %d got predicted to iterate %f times.\n",
4305 2 : loop->num, iterations.to_double ());
4306 : }
4307 : return 0;
4308 : }
4309 :
4310 : } // anon namespace
4311 :
4312 : gimple_opt_pass *
4313 288775 : make_pass_profile (gcc::context *ctxt)
4314 : {
4315 288775 : return new pass_profile (ctxt);
4316 : }
4317 :
4318 : /* Return true when PRED predictor should be removed after early
4319 : tree passes. Most of the predictors are beneficial to survive
4320 : as early inlining can also distribute then into caller's bodies. */
4321 :
4322 : static bool
4323 367042 : strip_predictor_early (enum br_predictor pred)
4324 : {
4325 0 : switch (pred)
4326 : {
4327 : case PRED_TREE_EARLY_RETURN:
4328 : return true;
4329 0 : default:
4330 0 : return false;
4331 : }
4332 : }
4333 :
4334 : /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4335 : we no longer need. EARLY is set to true when called from early
4336 : optimizations. */
4337 :
4338 : unsigned int
4339 3481499 : strip_predict_hints (function *fun, bool early)
4340 : {
4341 3481499 : basic_block bb;
4342 3481499 : gimple *ass_stmt;
4343 3481499 : tree var;
4344 3481499 : bool changed = false;
4345 :
4346 26644856 : FOR_EACH_BB_FN (bb, fun)
4347 : {
4348 23163357 : gimple_stmt_iterator bi;
4349 202896409 : for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4350 : {
4351 156569695 : gimple *stmt = gsi_stmt (bi);
4352 :
4353 156569695 : if (gimple_code (stmt) == GIMPLE_PREDICT)
4354 : {
4355 1090100 : if (!early
4356 577342 : || strip_predictor_early (gimple_predict_predictor (stmt)))
4357 : {
4358 512758 : gsi_remove (&bi, true);
4359 512758 : changed = true;
4360 512758 : continue;
4361 : }
4362 : }
4363 155992353 : else if (is_gimple_call (stmt))
4364 : {
4365 12237499 : tree fndecl = gimple_call_fndecl (stmt);
4366 :
4367 12237499 : if (!early
4368 12237499 : && ((fndecl != NULL_TREE
4369 5889750 : && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4370 145743 : && gimple_call_num_args (stmt) == 2)
4371 : || (fndecl != NULL_TREE
4372 5744007 : && fndecl_built_in_p (fndecl,
4373 : BUILT_IN_EXPECT_WITH_PROBABILITY)
4374 18 : && gimple_call_num_args (stmt) == 3)
4375 6094427 : || (gimple_call_internal_p (stmt)
4376 170848 : && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4377 : {
4378 180070 : var = gimple_call_lhs (stmt);
4379 180070 : changed = true;
4380 180070 : if (var)
4381 : {
4382 180069 : ass_stmt
4383 180069 : = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4384 180069 : gsi_replace (&bi, ass_stmt, true);
4385 : }
4386 : else
4387 : {
4388 1 : gsi_remove (&bi, true);
4389 1 : continue;
4390 : }
4391 : }
4392 : }
4393 156056936 : gsi_next (&bi);
4394 : }
4395 : }
4396 3481499 : return changed ? TODO_cleanup_cfg : 0;
4397 : }
4398 :
4399 : namespace {
4400 :
4401 : const pass_data pass_data_strip_predict_hints =
4402 : {
4403 : GIMPLE_PASS, /* type */
4404 : "*strip_predict_hints", /* name */
4405 : OPTGROUP_NONE, /* optinfo_flags */
4406 : TV_BRANCH_PROB, /* tv_id */
4407 : PROP_cfg, /* properties_required */
4408 : 0, /* properties_provided */
4409 : 0, /* properties_destroyed */
4410 : 0, /* todo_flags_start */
4411 : 0, /* todo_flags_finish */
4412 : };
4413 :
4414 : class pass_strip_predict_hints : public gimple_opt_pass
4415 : {
4416 : public:
4417 866325 : pass_strip_predict_hints (gcc::context *ctxt)
4418 1732650 : : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4419 : {}
4420 :
4421 : /* opt_pass methods: */
4422 577550 : opt_pass * clone () final override
4423 : {
4424 577550 : return new pass_strip_predict_hints (m_ctxt);
4425 : }
4426 866325 : void set_pass_param (unsigned int n, bool param) final override
4427 : {
4428 866325 : gcc_assert (n == 0);
4429 866325 : early_p = param;
4430 866325 : }
4431 :
4432 : unsigned int execute (function *) final override;
4433 :
4434 : private:
4435 : bool early_p;
4436 :
4437 : }; // class pass_strip_predict_hints
4438 :
4439 : unsigned int
4440 3481499 : pass_strip_predict_hints::execute (function *fun)
4441 : {
4442 3481499 : return strip_predict_hints (fun, early_p);
4443 : }
4444 :
4445 : } // anon namespace
4446 :
4447 : gimple_opt_pass *
4448 288775 : make_pass_strip_predict_hints (gcc::context *ctxt)
4449 : {
4450 288775 : return new pass_strip_predict_hints (ctxt);
4451 : }
4452 :
4453 : /* Rebuild function frequencies. Passes are in general expected to
4454 : maintain profile by hand, however in some cases this is not possible:
4455 : for example when inlining several functions with loops freuqencies might run
4456 : out of scale and thus needs to be recomputed. */
4457 :
4458 : void
4459 1095663 : rebuild_frequencies (void)
4460 : {
4461 : /* If we have no profile, do nothing. Note that after inlining
4462 : profile_status_for_fn may not represent the actual presence/absence of
4463 : profile. */
4464 1095663 : if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4465 1095663 : && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4466 : return;
4467 :
4468 :
4469 : /* See if everything is OK and update count_max. */
4470 1095415 : basic_block bb;
4471 1095415 : bool inconsistency_found = false;
4472 1095415 : bool uninitialized_probablity_found = false;
4473 1095415 : bool uninitialized_count_found = false;
4474 1095415 : bool feedback_found = false;
4475 :
4476 1095415 : cfun->cfg->count_max = profile_count::uninitialized ();
4477 15191138 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4478 : {
4479 14095723 : cfun->cfg->count_max
4480 14095723 : = profile_count::max_prefer_initialized (cfun->cfg->count_max,
4481 : bb->count);
4482 26664924 : if (bb->count.nonzero_p () && bb->count.quality () >= AFDO)
4483 : feedback_found = true;
4484 : /* Uninitialized count may be result of inlining or an omision in an
4485 : optimization pass. */
4486 14095723 : if (!bb->count.initialized_p ())
4487 : {
4488 18 : uninitialized_count_found = true;
4489 18 : if (dump_file)
4490 0 : fprintf (dump_file, "BB %i has uninitialized count\n",
4491 : bb->index);
4492 : }
4493 14095723 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4494 : && (!uninitialized_probablity_found || !inconsistency_found))
4495 : {
4496 13000308 : profile_count sum = profile_count::zero ();
4497 13000308 : edge e;
4498 13000308 : edge_iterator ei;
4499 :
4500 30559584 : FOR_EACH_EDGE (e, ei, bb->preds)
4501 : {
4502 17559276 : sum += e->count ();
4503 : /* Uninitialized probability may be result of inlining or an
4504 : omision in an optimization pass. */
4505 17559276 : if (!e->probability.initialized_p ())
4506 : {
4507 36 : if (dump_file)
4508 0 : fprintf (dump_file,
4509 : "Edge %i->%i has uninitialized probability\n",
4510 0 : e->src->index, e->dest->index);
4511 : }
4512 : }
4513 13000308 : if (sum.differs_from_p (bb->count))
4514 : {
4515 191376 : if (dump_file)
4516 18 : fprintf (dump_file,
4517 : "BB %i has invalid sum of incomming counts\n",
4518 : bb->index);
4519 : inconsistency_found = true;
4520 : }
4521 : }
4522 : }
4523 :
4524 : /* If everything is OK, do not re-propagate frequencies. */
4525 1095415 : if (!inconsistency_found
4526 1034833 : && (!uninitialized_count_found || uninitialized_probablity_found)
4527 2130248 : && !cfun->cfg->count_max.very_large_p ())
4528 : {
4529 : /* Propagating zero counts should be safe and may
4530 : help hot/cold splitting. */
4531 1034788 : determine_unlikely_bbs ();
4532 1034788 : if (dump_file)
4533 31 : fprintf (dump_file, "Profile is consistent\n");
4534 1034788 : return;
4535 : }
4536 : /* Do not re-propagate if we have profile feedback. Even if the profile is
4537 : inconsistent from previous transofrmations, it is probably more realistic
4538 : for hot part of the program than result of repropagating.
4539 :
4540 : Consider example where we previously has
4541 :
4542 : if (test)
4543 : then [large probability for true]
4544 :
4545 : and we later proved that test is always 0. In this case, if profile was
4546 : read correctly, we must have duplicated the conditional (for example by
4547 : inlining) in to a context where test is false. From profile feedback
4548 : we know that most executions if the conditionals were true, so the
4549 : important copy is not the one we look on.
4550 :
4551 : Propagating from probabilities would make profile look consistent, but
4552 : because probablities after code duplication may not be representative
4553 : for a given run, we would only propagate the error further. */
4554 60627 : if (feedback_found && !uninitialized_count_found)
4555 : {
4556 : /* Propagating zero counts should be safe and may
4557 : help hot/cold splitting. */
4558 9 : determine_unlikely_bbs ();
4559 9 : if (dump_file)
4560 0 : fprintf (dump_file,
4561 : "Profile is inconsistent but read from profile feedback;"
4562 : " not rebuilding\n");
4563 9 : return;
4564 : }
4565 :
4566 60618 : loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4567 60618 : connect_infinite_loops_to_exit ();
4568 60618 : estimate_bb_frequencies ();
4569 60618 : remove_fake_exit_edges ();
4570 60618 : loop_optimizer_finalize ();
4571 60618 : if (dump_file)
4572 5 : fprintf (dump_file, "Rebuilt basic block counts\n");
4573 :
4574 : return;
4575 : }
4576 :
4577 : namespace {
4578 :
4579 : const pass_data pass_data_rebuild_frequencies =
4580 : {
4581 : GIMPLE_PASS, /* type */
4582 : "rebuild_frequencies", /* name */
4583 : OPTGROUP_NONE, /* optinfo_flags */
4584 : TV_REBUILD_FREQUENCIES, /* tv_id */
4585 : PROP_cfg, /* properties_required */
4586 : 0, /* properties_provided */
4587 : 0, /* properties_destroyed */
4588 : 0, /* todo_flags_start */
4589 : 0, /* todo_flags_finish */
4590 : };
4591 :
4592 : class pass_rebuild_frequencies : public gimple_opt_pass
4593 : {
4594 : public:
4595 577550 : pass_rebuild_frequencies (gcc::context *ctxt)
4596 1155100 : : gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4597 : {}
4598 :
4599 : /* opt_pass methods: */
4600 288775 : opt_pass * clone () final override
4601 : {
4602 288775 : return new pass_rebuild_frequencies (m_ctxt);
4603 : }
4604 0 : void set_pass_param (unsigned int n, bool param) final override
4605 : {
4606 0 : gcc_assert (n == 0);
4607 0 : early_p = param;
4608 0 : }
4609 :
4610 1045936 : unsigned int execute (function *) final override
4611 : {
4612 1045936 : rebuild_frequencies ();
4613 1045936 : return 0;
4614 : }
4615 :
4616 : private:
4617 : bool early_p;
4618 :
4619 : }; // class pass_rebuild_frequencies
4620 :
4621 : } // anon namespace
4622 :
4623 : gimple_opt_pass *
4624 288775 : make_pass_rebuild_frequencies (gcc::context *ctxt)
4625 : {
4626 288775 : return new pass_rebuild_frequencies (ctxt);
4627 : }
4628 :
4629 : /* Perform a dry run of the branch prediction pass and report comparsion of
4630 : the predicted and real profile into the dump file. */
4631 :
4632 : void
4633 12 : report_predictor_hitrates (void)
4634 : {
4635 12 : unsigned nb_loops;
4636 :
4637 12 : loop_optimizer_init (LOOPS_NORMAL);
4638 12 : if (dump_file && (dump_flags & TDF_DETAILS))
4639 12 : flow_loops_dump (dump_file, NULL, 0);
4640 :
4641 12 : nb_loops = number_of_loops (cfun);
4642 12 : if (nb_loops > 1)
4643 5 : scev_initialize ();
4644 :
4645 12 : tree_estimate_probability (true);
4646 :
4647 12 : if (nb_loops > 1)
4648 5 : scev_finalize ();
4649 :
4650 12 : loop_optimizer_finalize ();
4651 12 : }
4652 :
4653 : /* Force edge E to be cold.
4654 : If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4655 : keep low probability to represent possible error in a guess. This is used
4656 : i.e. in case we predict loop to likely iterate given number of times but
4657 : we are not 100% sure.
4658 :
4659 : This function locally updates profile without attempt to keep global
4660 : consistency which cannot be reached in full generality without full profile
4661 : rebuild from probabilities alone. Doing so is not necessarily a good idea
4662 : because frequencies and counts may be more realistic then probabilities.
4663 :
4664 : In some cases (such as for elimination of early exits during full loop
4665 : unrolling) the caller can ensure that profile will get consistent
4666 : afterwards. */
4667 :
4668 : void
4669 576050 : force_edge_cold (edge e, bool impossible)
4670 : {
4671 576050 : profile_count count_sum = profile_count::zero ();
4672 576050 : profile_probability prob_sum = profile_probability::never ();
4673 576050 : edge_iterator ei;
4674 576050 : edge e2;
4675 576050 : bool uninitialized_exit = false;
4676 :
4677 : /* When branch probability guesses are not known, then do nothing. */
4678 576296 : if (!impossible && !e->count ().initialized_p ())
4679 2036 : return;
4680 :
4681 576050 : profile_probability goal = (impossible ? profile_probability::never ()
4682 246 : : profile_probability::very_unlikely ());
4683 :
4684 : /* If edge is already improbably or cold, just return. */
4685 576050 : if (e->probability <= goal
4686 55220 : && (!impossible || e->count () == profile_count::zero ()))
4687 1170 : return;
4688 1724123 : FOR_EACH_EDGE (e2, ei, e->src->succs)
4689 1149243 : if (e2 != e)
4690 : {
4691 574363 : if (e->flags & EDGE_FAKE)
4692 0 : continue;
4693 574363 : if (e2->count ().initialized_p ())
4694 574162 : count_sum += e2->count ();
4695 574363 : if (e2->probability.initialized_p ())
4696 574162 : prob_sum += e2->probability;
4697 : else
4698 : uninitialized_exit = true;
4699 : }
4700 :
4701 : /* If we are not guessing profiles but have some other edges out,
4702 : just assume the control flow goes elsewhere. */
4703 574880 : if (uninitialized_exit)
4704 201 : e->probability = goal;
4705 : /* If there are other edges out of e->src, redistribute probabilitity
4706 : there. */
4707 574679 : else if (prob_sum > profile_probability::never ())
4708 : {
4709 573507 : if (dump_file && (dump_flags & TDF_DETAILS))
4710 : {
4711 998 : fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4712 : "probability to other edges. Original probability: ",
4713 998 : e->src->index, e->dest->index,
4714 : impossible ? "impossible" : "cold");
4715 998 : e->probability.dump (dump_file);
4716 998 : fprintf (dump_file, "\n");
4717 : }
4718 573507 : set_edge_probability_and_rescale_others (e, goal);
4719 573507 : if (current_ir_type () != IR_GIMPLE
4720 573507 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4721 144963 : update_br_prob_note (e->src);
4722 : }
4723 : /* If all edges out of e->src are unlikely, the basic block itself
4724 : is unlikely. */
4725 : else
4726 : {
4727 1172 : if (prob_sum == profile_probability::never ())
4728 946 : e->probability = profile_probability::always ();
4729 : else
4730 : {
4731 226 : if (impossible)
4732 226 : e->probability = profile_probability::never ();
4733 : /* If BB has some edges out that are not impossible, we cannot
4734 : assume that BB itself is. */
4735 : impossible = false;
4736 : }
4737 1172 : if (current_ir_type () != IR_GIMPLE
4738 1172 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4739 28 : update_br_prob_note (e->src);
4740 1172 : if (e->src->count == profile_count::zero ())
4741 168 : return;
4742 2008 : if (count_sum == profile_count::zero () && impossible)
4743 : {
4744 744 : bool found = false;
4745 744 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4746 : ;
4747 714 : else if (current_ir_type () == IR_GIMPLE)
4748 1428 : for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4749 2720 : !gsi_end_p (gsi); gsi_next (&gsi))
4750 : {
4751 2052 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4752 : {
4753 : found = true;
4754 : break;
4755 : }
4756 : }
4757 : /* FIXME: Implement RTL path. */
4758 : else
4759 : found = true;
4760 714 : if (!found)
4761 : {
4762 698 : if (dump_file && (dump_flags & TDF_DETAILS))
4763 0 : fprintf (dump_file,
4764 : "Making bb %i impossible and dropping count to 0.\n",
4765 0 : e->src->index);
4766 698 : e->src->count = profile_count::zero ();
4767 1479 : FOR_EACH_EDGE (e2, ei, e->src->preds)
4768 781 : force_edge_cold (e2, impossible);
4769 : return;
4770 : }
4771 : }
4772 :
4773 : /* If we did not adjusting, the source basic block has no likely edeges
4774 : leaving other direction. In that case force that bb cold, too.
4775 : This in general is difficult task to do, but handle special case when
4776 : BB has only one predecestor. This is common case when we are updating
4777 : after loop transforms. */
4778 612 : if (!(prob_sum > profile_probability::never ())
4779 306 : && count_sum == profile_count::zero ()
4780 140 : && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4781 58 : > (impossible ? 0 : 1))
4782 : {
4783 57 : int old_frequency = e->src->count.to_frequency (cfun);
4784 57 : if (dump_file && (dump_flags & TDF_DETAILS))
4785 0 : fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4786 : impossible ? "impossible" : "cold");
4787 57 : int new_frequency = MIN (e->src->count.to_frequency (cfun),
4788 : impossible ? 0 : 1);
4789 0 : if (impossible)
4790 28 : e->src->count = profile_count::zero ();
4791 : else
4792 29 : e->src->count = e->count ().apply_scale (new_frequency,
4793 : old_frequency);
4794 57 : force_edge_cold (single_pred_edge (e->src), impossible);
4795 : }
4796 2 : else if (dump_file && (dump_flags & TDF_DETAILS)
4797 249 : && maybe_hot_bb_p (cfun, e->src))
4798 0 : fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4799 : impossible ? "impossible" : "cold");
4800 : }
4801 : }
4802 :
4803 : #if CHECKING_P
4804 :
4805 : namespace selftest {
4806 :
4807 : /* Test that value range of predictor values defined in predict.def is
4808 : within range (50, 100]. */
4809 :
4810 : struct branch_predictor
4811 : {
4812 : const char *name;
4813 : int probability;
4814 : };
4815 :
4816 : #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4817 :
4818 : static void
4819 4 : test_prediction_value_range ()
4820 : {
4821 4 : branch_predictor predictors[] = {
4822 : #include "predict.def"
4823 : { NULL, PROB_UNINITIALIZED }
4824 : };
4825 :
4826 216 : for (unsigned i = 0; predictors[i].name != NULL; i++)
4827 : {
4828 212 : if (predictors[i].probability == PROB_UNINITIALIZED)
4829 28 : continue;
4830 :
4831 184 : unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4832 212 : ASSERT_TRUE (p >= 50 && p <= 100);
4833 : }
4834 4 : }
4835 :
4836 : #undef DEF_PREDICTOR
4837 :
4838 : /* Run all of the selfests within this file. */
4839 :
4840 : void
4841 4 : predict_cc_tests ()
4842 : {
4843 4 : test_prediction_value_range ();
4844 4 : }
4845 :
4846 : } // namespace selftest
4847 : #endif /* CHECKING_P. */
|
