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 61891 : get_hot_bb_threshold ()
127 : {
128 61891 : if (min_count == -1)
129 : {
130 101 : const int hot_frac = param_hot_bb_count_fraction;
131 202 : const gcov_type min_hot_count
132 : = hot_frac
133 101 : ? profile_info->sum_max / hot_frac
134 : : (gcov_type)profile_count::max_count;
135 101 : set_hot_bb_threshold (min_hot_count);
136 101 : if (dump_file)
137 22 : fprintf (dump_file, "Setting hotness threshold to %" PRId64 ".\n",
138 : min_hot_count);
139 : }
140 61891 : return min_count;
141 : }
142 :
143 : /* Set the threshold for hot BB counts. */
144 :
145 : void
146 361 : set_hot_bb_threshold (gcov_type min)
147 : {
148 361 : min_count = min;
149 361 : }
150 :
151 : /* Return TRUE if COUNT is considered to be hot in function FUN. */
152 :
153 : bool
154 1008386502 : maybe_hot_count_p (struct function *fun, profile_count count)
155 : {
156 1008386502 : if (!count.initialized_p ())
157 : return true;
158 917837224 : if (count.ipa () == profile_count::zero ())
159 4469260 : return false;
160 913367964 : if (!count.ipa_p ())
161 : {
162 913262688 : struct cgraph_node *node = cgraph_node::get (fun->decl);
163 913262688 : if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
164 : {
165 913262688 : if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
166 : return false;
167 913197855 : if (node->frequency == NODE_FREQUENCY_HOT)
168 : return true;
169 : }
170 913193902 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
171 : return true;
172 912992898 : if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
173 912992898 : && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
174 21316490 : return false;
175 891676408 : if (count * param_hot_bb_frequency_fraction
176 891676408 : < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
177 : return false;
178 : return true;
179 : }
180 : /* Code executed at most once is not hot. */
181 105276 : if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
182 : return false;
183 61670 : 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 998311582 : maybe_hot_bb_p (struct function *fun, const_basic_block bb)
191 : {
192 998311582 : gcc_checking_assert (fun);
193 998311582 : 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 9378217 : maybe_hot_edge_p (edge e)
201 : {
202 9378217 : 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 54502968 : probably_never_executed (struct function *fun, profile_count count)
210 : {
211 54502968 : gcc_checking_assert (fun);
212 54502968 : if (count.ipa () == profile_count::zero ())
213 1501038 : 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 53001930 : if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
220 : {
221 3413 : const int unlikely_frac = param_unlikely_bb_count_fraction;
222 3413 : if (count * unlikely_frac >= profile_info->runs)
223 : return false;
224 : return true;
225 : }
226 3059 : if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
227 52998625 : && (cgraph_node::get (fun->decl)->frequency
228 52995566 : == 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 17339042 : probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
237 : {
238 17339042 : 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 118554903 : unlikely_executed_edge_p (edge e)
245 : {
246 120280392 : return (e->src->count == profile_count::zero ()
247 116408868 : || e->probability == profile_probability::never ())
248 111629054 : || (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 111071928 : || ((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 39254529 : probably_never_executed_edge_p (struct function *fun, edge e)
258 : {
259 39254529 : if (unlikely_executed_edge_p (e))
260 : return true;
261 37163926 : 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 2454353952 : optimize_function_for_size_p (struct function *fun)
268 : {
269 2454353952 : if (!fun || !fun->decl)
270 197484950 : return optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
271 2352161111 : cgraph_node *n = cgraph_node::get (fun->decl);
272 2352161111 : if (n)
273 2307578157 : 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 227448148 : optimize_function_for_speed_p (struct function *fun)
281 : {
282 227448148 : 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 981328680 : optimize_bb_for_size_p (const_basic_block bb)
299 : {
300 981328680 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
301 :
302 1949748269 : if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
303 26042807 : ret = OPTIMIZE_SIZE_MAX;
304 981328680 : if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun, bb))
305 : ret = OPTIMIZE_SIZE_BALANCED;
306 981328680 : return ret;
307 : }
308 :
309 : /* Return TRUE if basic block BB should be optimized for speed. */
310 :
311 : bool
312 928462121 : optimize_bb_for_speed_p (const_basic_block bb)
313 : {
314 928462121 : 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 5287954 : bb_optimization_type (const_basic_block bb)
321 : {
322 5287954 : return (optimize_bb_for_speed_p (bb)
323 5287954 : ? OPTIMIZE_FOR_SPEED
324 5287954 : : OPTIMIZE_FOR_SIZE);
325 : }
326 :
327 : /* Return TRUE if edge E should be optimized for size. */
328 :
329 : optimize_size_level
330 9788331 : optimize_edge_for_size_p (edge e)
331 : {
332 9788331 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
333 :
334 9788331 : if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
335 : ret = OPTIMIZE_SIZE_MAX;
336 9582785 : if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
337 : ret = OPTIMIZE_SIZE_BALANCED;
338 9788331 : return ret;
339 : }
340 :
341 : /* Return TRUE if edge E should be optimized for speed. */
342 :
343 : bool
344 4285832 : optimize_edge_for_speed_p (edge e)
345 : {
346 4285832 : 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 219925525 : optimize_insn_for_size_p (void)
353 : {
354 219925525 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
355 219925525 : if (ret < OPTIMIZE_SIZE_BALANCED && !crtl->maybe_hot_insn_p)
356 219925525 : ret = OPTIMIZE_SIZE_BALANCED;
357 219925525 : return ret;
358 : }
359 :
360 : /* Return TRUE if the current function is optimized for speed. */
361 :
362 : bool
363 85614086 : optimize_insn_for_speed_p (void)
364 : {
365 85614086 : 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 751139 : optimize_loop_for_size_p (class loop *loop)
383 : {
384 751139 : return optimize_bb_for_size_p (loop->header);
385 : }
386 :
387 : /* Return TRUE if LOOP should be optimized for speed. */
388 :
389 : bool
390 15404264 : optimize_loop_for_speed_p (class loop *loop)
391 : {
392 15404264 : 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 1282967 : optimize_loop_nest_for_speed_p (class loop *loop)
399 : {
400 1282967 : class loop *l = loop;
401 1282967 : if (optimize_loop_for_speed_p (loop))
402 : return true;
403 35169 : l = loop->inner;
404 47546 : while (l && l != loop)
405 : {
406 13806 : if (optimize_loop_for_speed_p (l))
407 : return true;
408 12377 : if (l->inner)
409 : l = l->inner;
410 8283 : else if (l->next)
411 : l = l->next;
412 : else
413 : {
414 19522 : while (l != loop && !l->next)
415 11641 : l = loop_outer (l);
416 7881 : 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 17207 : optimize_loop_nest_for_size_p (class loop *loop)
427 : {
428 17207 : enum optimize_size_level ret = optimize_loop_for_size_p (loop);
429 17207 : class loop *l = loop;
430 :
431 17207 : l = loop->inner;
432 17479 : while (l && l != loop)
433 : {
434 16731 : if (ret == OPTIMIZE_SIZE_NO)
435 : break;
436 272 : ret = MIN (optimize_loop_for_size_p (l), ret);
437 272 : if (l->inner)
438 : l = l->inner;
439 263 : else if (l->next)
440 : l = l->next;
441 : else
442 : {
443 321 : while (l != loop && !l->next)
444 163 : l = loop_outer (l);
445 158 : if (l != loop)
446 4 : l = l->next;
447 : }
448 : }
449 17207 : return ret;
450 : }
451 :
452 : /* Return true if edge E is likely to be well predictable by branch
453 : predictor. */
454 :
455 : bool
456 5722088 : predictable_edge_p (edge e)
457 : {
458 5722088 : if (!e->probability.initialized_p ())
459 : return false;
460 5721323 : if ((e->probability.to_reg_br_prob_base ()
461 5721323 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100)
462 5721323 : || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
463 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100))
464 622750 : return true;
465 : return false;
466 : }
467 :
468 :
469 : /* Set RTL expansion for BB profile. */
470 :
471 : void
472 78706179 : rtl_profile_for_bb (basic_block bb)
473 : {
474 78706179 : crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
475 78706179 : }
476 :
477 : /* Set RTL expansion for edge profile. */
478 :
479 : void
480 10965 : rtl_profile_for_edge (edge e)
481 : {
482 10965 : crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
483 10965 : }
484 :
485 : /* Set RTL expansion to default mode (i.e. when profile info is not known). */
486 : void
487 14200964 : default_rtl_profile (void)
488 : {
489 14200964 : crtl->maybe_hot_insn_p = true;
490 14200964 : }
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 3178752 : gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
537 : {
538 3178752 : struct edge_prediction *i;
539 3178752 : edge_prediction **preds = bb_predictions->get (bb);
540 :
541 3178752 : if (!preds)
542 : return false;
543 :
544 1585948 : for (i = *preds; i; i = i->ep_next)
545 824964 : 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 1092958 : edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
555 : {
556 1092958 : struct edge_prediction *i;
557 1092958 : basic_block bb = e->src;
558 1092958 : edge_prediction **preds = bb_predictions->get (bb);
559 1092958 : if (!preds)
560 : return false;
561 :
562 136241 : int probability = predictor_info[(int) predictor].hitrate;
563 :
564 136241 : if (taken != TAKEN)
565 136071 : probability = REG_BR_PROB_BASE - probability;
566 :
567 4850029 : for (i = *preds; i; i = i->ep_next)
568 4718221 : if (i->ep_predictor == predictor
569 4581662 : && i->ep_edge == e
570 4433 : && 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 87297 : predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
593 : {
594 87297 : gcc_assert (any_condjump_p (insn));
595 87297 : if (!flag_guess_branch_prob)
596 : return;
597 :
598 174494 : add_reg_note (insn, REG_BR_PRED,
599 87247 : 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 87297 : predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
608 : enum prediction taken)
609 : {
610 87297 : int probability = predictor_info[(int) predictor].hitrate;
611 87297 : gcc_assert (probability != PROB_UNINITIALIZED);
612 :
613 87297 : if (taken != TAKEN)
614 5791 : probability = REG_BR_PROB_BASE - probability;
615 :
616 87297 : predict_insn (insn, predictor, probability);
617 87297 : }
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 6141862 : gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
642 : {
643 6141862 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
644 6141862 : && EDGE_COUNT (e->src->succs) > 1
645 6141862 : && flag_guess_branch_prob
646 12283724 : && optimize)
647 : {
648 6141862 : struct edge_prediction *i = XNEW (struct edge_prediction);
649 6141862 : edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
650 :
651 6141862 : i->ep_next = preds;
652 6141862 : preds = i;
653 6141862 : i->ep_probability = probability;
654 6141862 : i->ep_predictor = predictor;
655 6141862 : i->ep_edge = e;
656 : }
657 6141862 : }
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 2828028 : filter_predictions (edge_prediction **preds,
665 : bool (*filter) (edge_prediction *, void *), void *data)
666 : {
667 2828028 : if (!bb_predictions)
668 : return;
669 :
670 2828028 : if (preds)
671 : {
672 : struct edge_prediction **prediction = preds;
673 : struct edge_prediction *next;
674 :
675 7835095 : while (*prediction)
676 : {
677 5007067 : if ((*filter) (*prediction, data))
678 4499322 : prediction = &((*prediction)->ep_next);
679 : else
680 : {
681 507745 : next = (*prediction)->ep_next;
682 507745 : free (*prediction);
683 507745 : *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 83560565 : remove_predictions_associated_with_edge (edge e)
702 : {
703 83560565 : 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 11372821 : clear_bb_predictions (basic_block bb)
714 : {
715 11372821 : edge_prediction **preds = bb_predictions->get (bb);
716 11372821 : struct edge_prediction *pred, *next;
717 :
718 11372821 : if (!preds)
719 : return;
720 :
721 9189927 : for (pred = *preds; pred; pred = next)
722 : {
723 5634117 : next = pred->ep_next;
724 5634117 : free (pred);
725 : }
726 3555810 : *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 1137176 : can_predict_insn_p (const rtx_insn *insn)
734 : {
735 1137176 : return (JUMP_P (insn)
736 339544 : && any_condjump_p (insn)
737 1476194 : && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
738 : }
739 :
740 : /* Predict edge E by given predictor if possible. */
741 :
742 : void
743 5051747 : predict_edge_def (edge e, enum br_predictor predictor,
744 : enum prediction taken)
745 : {
746 5051747 : int probability = predictor_info[(int) predictor].hitrate;
747 :
748 5051747 : if (taken != TAKEN)
749 4069136 : probability = REG_BR_PROB_BASE - probability;
750 :
751 5051747 : predict_edge (e, predictor, probability);
752 5051747 : }
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 12727802 : invert_br_probabilities (rtx insn)
759 : {
760 12727802 : rtx note;
761 :
762 37643679 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
763 24915877 : if (REG_NOTE_KIND (note) == REG_BR_PROB)
764 25308096 : XINT (note, 0) = profile_probability::from_reg_br_prob_note
765 12654048 : (XINT (note, 0)).invert ().to_reg_br_prob_note ();
766 12261829 : 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 12727802 : }
770 :
771 : /* Dump information about the branch prediction to the output file. */
772 :
773 : static void
774 12012096 : 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 12012096 : edge e = ep_edge;
779 12012096 : edge_iterator ei;
780 :
781 12012096 : if (!file)
782 12010229 : 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 173019304 : unlikely_executed_stmt_p (gimple *stmt)
833 : {
834 173019304 : 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 12281668 : if (gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE)
840 12237132 : || gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE_TRAP)
841 24518794 : || gimple_call_builtin_p (stmt, BUILT_IN_TRAP))
842 77800 : 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 12203868 : if (gimple_bb (stmt)->count.reliable_p ()
854 181633658 : && 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 12203577 : if (gimple_call_fntype (stmt)
859 11695961 : && lookup_attribute ("cold",
860 11695961 : TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
861 12203577 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
862 : return true;
863 12203577 : tree decl = gimple_call_fndecl (stmt);
864 12203577 : if (!decl)
865 : return false;
866 11461472 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
867 11461472 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
868 : return true;
869 :
870 11157650 : cgraph_node *n = cgraph_node::get (decl);
871 11157650 : if (!n)
872 : return false;
873 :
874 11151437 : availability avail;
875 11151437 : n = n->ultimate_alias_target (&avail);
876 11151437 : if (avail < AVAIL_AVAILABLE)
877 : return false;
878 3226052 : if (!n->analyzed
879 3226012 : || n->decl == current_function_decl)
880 : return false;
881 3207892 : return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
882 : }
883 :
884 : /* Return true if BB is unlikely executed. */
885 :
886 : static bool
887 32402767 : unlikely_executed_bb_p (basic_block bb)
888 : {
889 32402767 : if (bb->count == profile_count::zero ())
890 0 : return true;
891 32402767 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
892 : return false;
893 64805534 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
894 195776633 : !gsi_end_p (gsi); gsi_next (&gsi))
895 : {
896 173019304 : if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
897 : return true;
898 172624205 : 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 8482491 : set_even_probabilities (basic_block bb,
913 : hash_set<edge> *unlikely_edges = NULL,
914 : hash_set<edge_prediction *> *likely_edges = NULL)
915 : {
916 8482491 : unsigned nedges = 0, unlikely_count = 0;
917 8482491 : edge e = NULL;
918 8482491 : edge_iterator ei;
919 8482491 : profile_probability all = profile_probability::always ();
920 :
921 18589331 : FOR_EACH_EDGE (e, ei, bb->succs)
922 10106840 : if (e->probability.initialized_p ())
923 9086823 : all -= e->probability;
924 1020017 : else if (!unlikely_executed_edge_p (e))
925 : {
926 613960 : nedges++;
927 613960 : 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 8482491 : unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
936 8482491 : if (unlikely_count == nedges)
937 : {
938 7978695 : unlikely_edges = NULL;
939 7978695 : unlikely_count = 0;
940 : }
941 :
942 : /* If we have one likely edge, then use its probability and distribute
943 : remaining probabilities as even. */
944 8482491 : if (likely_count == 1)
945 : {
946 11379 : FOR_EACH_EDGE (e, ei, bb->succs)
947 7590 : 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 8478702 : unsigned scale = nedges - unlikely_count;
979 18577952 : FOR_EACH_EDGE (e, ei, bb->succs)
980 10099250 : if (e->probability.initialized_p ())
981 : ;
982 1019993 : else if (!unlikely_executed_edge_p (e))
983 : {
984 613936 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
985 5098 : e->probability = profile_probability::very_unlikely ();
986 : else
987 608838 : e->probability = (all / scale).guessed ();
988 : }
989 : else
990 406057 : e->probability = profile_probability::never ();
991 : }
992 8482491 : }
993 :
994 : /* Add REG_BR_PROB note to JUMP with PROB. */
995 :
996 : void
997 5227630 : add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
998 : {
999 5227630 : gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
1000 5227630 : add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
1001 5227630 : }
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 568588 : combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
1008 : {
1009 568588 : rtx prob_note;
1010 568588 : rtx *pnote;
1011 568588 : rtx note;
1012 568588 : int best_probability = PROB_EVEN;
1013 568588 : enum br_predictor best_predictor = END_PREDICTORS;
1014 568588 : int combined_probability = REG_BR_PROB_BASE / 2;
1015 568588 : int d;
1016 568588 : bool first_match = false;
1017 568588 : bool found = false;
1018 :
1019 568588 : if (!can_predict_insn_p (insn))
1020 : {
1021 399079 : set_even_probabilities (bb);
1022 399079 : return;
1023 : }
1024 :
1025 169509 : prob_note = find_reg_note (insn, REG_BR_PROB, 0);
1026 169509 : pnote = ®_NOTES (insn);
1027 169509 : 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 256756 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1034 87247 : if (REG_NOTE_KIND (note) == REG_BR_PRED)
1035 : {
1036 87247 : enum br_predictor predictor = ((enum br_predictor)
1037 87247 : INTVAL (XEXP (XEXP (note, 0), 0)));
1038 87247 : int probability = INTVAL (XEXP (XEXP (note, 0), 1));
1039 :
1040 87247 : found = true;
1041 87247 : if (best_predictor > predictor
1042 87247 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1043 87247 : best_probability = probability, best_predictor = predictor;
1044 :
1045 87247 : d = (combined_probability * probability
1046 87247 : + (REG_BR_PROB_BASE - combined_probability)
1047 87247 : * (REG_BR_PROB_BASE - probability));
1048 :
1049 : /* Use int64_t math to avoid overflows of 32bit integers. */
1050 87247 : 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 87247 : combined_probability = ((((int64_t) combined_probability)
1055 87247 : * probability
1056 87247 : * 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 169509 : if (best_predictor != END_PREDICTORS)
1064 269 : first_match = true;
1065 :
1066 169509 : if (!found)
1067 82262 : dump_prediction (dump_file, PRED_NO_PREDICTION,
1068 : combined_probability, bb);
1069 : else
1070 : {
1071 87247 : if (!first_match)
1072 86978 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
1073 : bb, !first_match ? REASON_NONE : REASON_IGNORED);
1074 : else
1075 269 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
1076 : bb, first_match ? REASON_NONE : REASON_IGNORED);
1077 : }
1078 :
1079 169509 : if (first_match)
1080 269 : combined_probability = best_probability;
1081 169509 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1082 :
1083 426265 : while (*pnote)
1084 : {
1085 87247 : if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1086 : {
1087 87247 : enum br_predictor predictor = ((enum br_predictor)
1088 87247 : INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1089 87247 : int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1090 :
1091 87247 : dump_prediction (dump_file, predictor, probability, bb,
1092 87247 : (!first_match || best_predictor == predictor)
1093 87247 : ? REASON_NONE : REASON_IGNORED);
1094 87247 : *pnote = XEXP (*pnote, 1);
1095 : }
1096 : else
1097 0 : pnote = &XEXP (*pnote, 1);
1098 : }
1099 :
1100 169509 : if (!prob_note)
1101 : {
1102 169509 : profile_probability p
1103 169509 : = profile_probability::from_reg_br_prob_base (combined_probability);
1104 169509 : 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 169509 : if (!single_succ_p (bb))
1109 : {
1110 169509 : BRANCH_EDGE (bb)->probability = p;
1111 169509 : FALLTHRU_EDGE (bb)->probability
1112 339018 : = 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 12749332 : predictor_hash::hash (const edge_prediction *p)
1141 : {
1142 12749332 : inchash::hash hstate;
1143 12749332 : hstate.add_int (p->ep_predictor);
1144 :
1145 12749332 : int prob = p->ep_probability;
1146 12749332 : if (prob > REG_BR_PROB_BASE / 2)
1147 1644082 : prob = REG_BR_PROB_BASE - prob;
1148 :
1149 12749332 : hstate.add_int (prob);
1150 :
1151 12749332 : 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 2936642 : predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1159 : {
1160 2936642 : return (p1->ep_predictor == p2->ep_predictor
1161 2936642 : && (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 5007059 : not_removed_prediction_p (edge_prediction *p, void *data)
1172 : {
1173 5007059 : hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1174 5007059 : 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 3289353 : prune_predictions_for_bb (basic_block bb)
1189 : {
1190 3289353 : edge_prediction **preds = bb_predictions->get (bb);
1191 :
1192 3289353 : if (preds)
1193 : {
1194 2828024 : hash_table <predictor_hash_traits> s (13);
1195 2828024 : hash_set <edge_prediction *> remove;
1196 :
1197 : /* Step 1: identify predictors that should be removed. */
1198 7835083 : for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1199 : {
1200 5007059 : edge_prediction *existing = s.find (pred);
1201 5007059 : if (existing)
1202 : {
1203 256239 : 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 256239 : else if (pred->ep_edge != existing->ep_edge
1214 256239 : && pred->ep_probability == existing->ep_probability
1215 256239 : && pred->ep_probability != REG_BR_PROB_BASE / 2)
1216 : {
1217 : /* Remove both predictors as they predict the same
1218 : for both edges. */
1219 253901 : dump_prediction (dump_file, existing->ep_predictor,
1220 : pred->ep_probability, bb,
1221 : REASON_EDGE_PAIR_DUPLICATE,
1222 : existing->ep_edge);
1223 253901 : dump_prediction (dump_file, pred->ep_predictor,
1224 : pred->ep_probability, bb,
1225 : REASON_EDGE_PAIR_DUPLICATE,
1226 : pred->ep_edge);
1227 :
1228 253901 : remove.add (existing);
1229 253901 : remove.add (pred);
1230 : }
1231 : }
1232 :
1233 5007059 : edge_prediction **slot2 = s.find_slot (pred, INSERT);
1234 5007059 : *slot2 = pred;
1235 : }
1236 :
1237 : /* Step 2: Remove predictors. */
1238 2828024 : filter_predictions (preds, not_removed_prediction_p, &remove);
1239 2828024 : }
1240 3289353 : }
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 11372821 : combine_predictions_for_bb (basic_block bb, bool dry_run)
1248 : {
1249 11372821 : int best_probability = PROB_EVEN;
1250 11372821 : enum br_predictor best_predictor = END_PREDICTORS;
1251 11372821 : int combined_probability = REG_BR_PROB_BASE / 2;
1252 11372821 : int d;
1253 11372821 : bool first_match = false;
1254 11372821 : bool found = false;
1255 11372821 : struct edge_prediction *pred;
1256 11372821 : int nedges = 0;
1257 11372821 : edge e, first = NULL, second = NULL;
1258 11372821 : edge_iterator ei;
1259 11372821 : int nzero = 0;
1260 11372821 : int nunknown = 0;
1261 :
1262 27259812 : FOR_EACH_EDGE (e, ei, bb->succs)
1263 : {
1264 15886991 : if (!unlikely_executed_edge_p (e))
1265 : {
1266 13555790 : nedges ++;
1267 13555790 : if (first && !second)
1268 : second = e;
1269 10243904 : if (!first)
1270 10156233 : first = e;
1271 : }
1272 2331201 : else if (!e->probability.initialized_p ())
1273 26181 : e->probability = profile_probability::never ();
1274 15886991 : if (!e->probability.initialized_p ())
1275 6082184 : nunknown++;
1276 9804807 : else if (e->probability == profile_probability::never ())
1277 2210559 : 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 11372821 : if (nedges != 2)
1294 : {
1295 8083468 : hash_set<edge> unlikely_edges (4);
1296 8083468 : 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 8083468 : edge_prediction **preds = bb_predictions->get (bb);
1302 8083468 : if (preds)
1303 1862589 : for (pred = *preds; pred; pred = pred->ep_next)
1304 : {
1305 1134803 : if (pred->ep_probability <= PROB_VERY_UNLIKELY
1306 1126183 : || pred->ep_predictor == PRED_COLD_LABEL)
1307 8685 : unlikely_edges.add (pred->ep_edge);
1308 1126118 : else if (pred->ep_probability >= PROB_VERY_LIKELY
1309 1125489 : || pred->ep_predictor == PRED_BUILTIN_EXPECT
1310 1122331 : || pred->ep_predictor == PRED_HOT_LABEL)
1311 3790 : 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 8087257 : for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
1317 8091046 : it != likely_edges.end (); ++it)
1318 3790 : if (unlikely_edges.contains ((*it)->ep_edge))
1319 : {
1320 1 : likely_edges.empty ();
1321 8083469 : unlikely_edges.empty ();
1322 : break;
1323 : }
1324 :
1325 8083468 : if (!dry_run)
1326 8083412 : set_even_probabilities (bb, &unlikely_edges, &likely_edges);
1327 8083468 : clear_bb_predictions (bb);
1328 8083468 : 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 8083468 : return;
1347 8083468 : }
1348 :
1349 3289353 : if (dump_file)
1350 583 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1351 :
1352 3289353 : prune_predictions_for_bb (bb);
1353 :
1354 3289353 : edge_prediction **preds = bb_predictions->get (bb);
1355 :
1356 3289353 : if (preds)
1357 : {
1358 : /* We implement "first match" heuristics and use probability guessed
1359 : by predictor with smallest index. */
1360 7327338 : for (pred = *preds; pred; pred = pred->ep_next)
1361 : {
1362 4499314 : enum br_predictor predictor = pred->ep_predictor;
1363 4499314 : int probability = pred->ep_probability;
1364 :
1365 4499314 : if (pred->ep_edge != first)
1366 1191795 : probability = REG_BR_PROB_BASE - probability;
1367 :
1368 4499314 : found = true;
1369 : /* First match heuristics would be widly confused if we predicted
1370 : both directions. */
1371 4499314 : if (best_predictor > predictor
1372 4312062 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1373 : {
1374 : struct edge_prediction *pred2;
1375 : int prob = probability;
1376 :
1377 2860426 : for (pred2 = (struct edge_prediction *) *preds;
1378 4216567 : pred2; pred2 = pred2->ep_next)
1379 2860426 : 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 2860426 : prob = probability2;
1394 : }
1395 1356141 : if (!pred2)
1396 4499314 : best_probability = prob, best_predictor = predictor;
1397 : }
1398 :
1399 4499314 : d = (combined_probability * probability
1400 4499314 : + (REG_BR_PROB_BASE - combined_probability)
1401 4499314 : * (REG_BR_PROB_BASE - probability));
1402 :
1403 : /* Use int64_t math to avoid overflows of 32bit integers. */
1404 4499314 : 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 4499314 : combined_probability = ((((int64_t) combined_probability)
1409 4499314 : * probability
1410 4499314 : * 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 2828024 : if (best_predictor != END_PREDICTORS)
1419 1259516 : first_match = true;
1420 :
1421 3289353 : if (!found)
1422 529464 : dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1423 : else
1424 : {
1425 2759889 : if (!first_match)
1426 1500373 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1427 : !first_match ? REASON_NONE : REASON_IGNORED);
1428 : else
1429 1259516 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1430 : first_match ? REASON_NONE : REASON_IGNORED);
1431 : }
1432 :
1433 3289353 : if (first_match)
1434 1259516 : combined_probability = best_probability;
1435 3289353 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1436 :
1437 3289353 : if (preds)
1438 : {
1439 7327338 : for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1440 : {
1441 4499314 : enum br_predictor predictor = pred->ep_predictor;
1442 4499314 : int probability = pred->ep_probability;
1443 :
1444 4499314 : dump_prediction (dump_file, predictor, probability, bb,
1445 4499314 : (!first_match || best_predictor == predictor)
1446 4499314 : ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1447 : }
1448 : }
1449 3289353 : clear_bb_predictions (bb);
1450 :
1451 :
1452 : /* If we have only one successor which is unknown, we can compute missing
1453 : probability. */
1454 3289353 : if (nunknown == 1)
1455 : {
1456 1242 : profile_probability prob = profile_probability::always ();
1457 1242 : edge missing = NULL;
1458 :
1459 3726 : FOR_EACH_EDGE (e, ei, bb->succs)
1460 2484 : if (e->probability.initialized_p ())
1461 1242 : prob -= e->probability;
1462 1242 : else if (missing == NULL)
1463 : missing = e;
1464 : else
1465 0 : gcc_unreachable ();
1466 1242 : missing->probability = prob;
1467 : }
1468 : /* If nothing is unknown, we have nothing to update. */
1469 3655539 : else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1470 : ;
1471 2920683 : else if (!dry_run)
1472 : {
1473 2920683 : first->probability
1474 2920683 : = profile_probability::from_reg_br_prob_base (combined_probability);
1475 2920683 : 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 9341 : strips_small_constant (tree t1, tree t2)
1489 : {
1490 9341 : tree ret = NULL;
1491 9341 : int value = 0;
1492 :
1493 9341 : if (!t1)
1494 : return NULL;
1495 9341 : else if (TREE_CODE (t1) == SSA_NAME)
1496 : ret = t1;
1497 1088 : else if (tree_fits_shwi_p (t1))
1498 93 : value = tree_to_shwi (t1);
1499 : else
1500 : return NULL;
1501 :
1502 8346 : if (!t2)
1503 : return ret;
1504 8346 : else if (tree_fits_shwi_p (t2))
1505 7790 : 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 8062 : 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 234045 : get_base_value (tree t)
1525 : {
1526 234045 : if (TREE_CODE (t) == SSA_NAME)
1527 : return t;
1528 :
1529 11064 : if (!BINARY_CLASS_P (t))
1530 : return NULL;
1531 :
1532 9341 : switch (TREE_OPERAND_LENGTH (t))
1533 : {
1534 0 : case 1:
1535 0 : return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1536 9341 : case 2:
1537 9341 : return strips_small_constant (TREE_OPERAND (t, 0),
1538 18682 : 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 862694 : 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 862694 : tree op0, op1, bound, base;
1557 862694 : affine_iv iv0, iv1;
1558 862694 : enum tree_code code;
1559 862694 : tree step;
1560 :
1561 862694 : code = gimple_cond_code (stmt);
1562 862694 : *loop_invariant = NULL;
1563 :
1564 862694 : switch (code)
1565 : {
1566 861832 : case GT_EXPR:
1567 861832 : case GE_EXPR:
1568 861832 : case NE_EXPR:
1569 861832 : case LT_EXPR:
1570 861832 : case LE_EXPR:
1571 861832 : case EQ_EXPR:
1572 861832 : break;
1573 :
1574 : default:
1575 : return false;
1576 : }
1577 :
1578 861832 : op0 = gimple_cond_lhs (stmt);
1579 861832 : op1 = gimple_cond_rhs (stmt);
1580 :
1581 861832 : if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1582 861813 : || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1583 : return false;
1584 1696792 : if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1585 : return false;
1586 1003594 : if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1587 : return false;
1588 482752 : if (TREE_CODE (iv0.step) != INTEGER_CST
1589 479971 : || TREE_CODE (iv1.step) != INTEGER_CST)
1590 : return false;
1591 545110 : if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1592 531575 : || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1593 13733 : return false;
1594 :
1595 459679 : if (integer_zerop (iv0.step))
1596 : {
1597 58163 : if (code != NE_EXPR && code != EQ_EXPR)
1598 42459 : code = invert_tree_comparison (code, false);
1599 58163 : bound = iv0.base;
1600 58163 : base = iv1.base;
1601 58163 : if (tree_fits_shwi_p (iv1.step))
1602 : step = iv1.step;
1603 : else
1604 : return false;
1605 : }
1606 : else
1607 : {
1608 401516 : bound = iv1.base;
1609 401516 : base = iv0.base;
1610 401516 : if (tree_fits_shwi_p (iv0.step))
1611 : step = iv0.step;
1612 : else
1613 : return false;
1614 : }
1615 :
1616 453052 : if (TREE_CODE (bound) != INTEGER_CST)
1617 158883 : bound = get_base_value (bound);
1618 158883 : if (!bound)
1619 : return false;
1620 451309 : if (TREE_CODE (base) != INTEGER_CST)
1621 75162 : base = get_base_value (base);
1622 75162 : if (!base)
1623 : return false;
1624 :
1625 449421 : *loop_invariant = bound;
1626 449421 : *compare_code = code;
1627 449421 : *loop_step = step;
1628 449421 : *loop_iv_base = base;
1629 449421 : return true;
1630 : }
1631 :
1632 : /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1633 :
1634 : static bool
1635 6958 : expr_coherent_p (tree t1, tree t2)
1636 : {
1637 6958 : gimple *stmt;
1638 6958 : tree ssa_name_1 = NULL;
1639 6958 : tree ssa_name_2 = NULL;
1640 :
1641 6958 : gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1642 6958 : gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1643 :
1644 6958 : 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 6072304 : predicted_by_loop_heuristics_p (basic_block bb)
1683 : {
1684 6072304 : struct edge_prediction *i;
1685 6072304 : edge_prediction **preds = bb_predictions->get (bb);
1686 :
1687 6072304 : if (!preds)
1688 : return false;
1689 :
1690 2124095 : for (i = *preds; i; i = i->ep_next)
1691 1810485 : if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1692 1810485 : || 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 2024195 : 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 2024195 : tree compare_var, compare_base;
1723 2024195 : enum tree_code compare_code;
1724 2024195 : tree compare_step_var;
1725 2024195 : edge then_edge;
1726 2024195 : edge_iterator ei;
1727 :
1728 2024195 : if (predicted_by_loop_heuristics_p (bb))
1729 2022598 : return;
1730 :
1731 4308625 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1732 257285 : if (!stmt)
1733 : return;
1734 257285 : 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 11263 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
1743 11263 : 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 11166 : if (compare_code == NE_EXPR)
1749 : {
1750 1663 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1751 1663 : return;
1752 : }
1753 9503 : 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 4696 : 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 4121 : if (tree_fits_shwi_p (loop_bound_var)
1765 2725 : && tree_fits_shwi_p (compare_var)
1766 2588 : && tree_fits_shwi_p (compare_base))
1767 : {
1768 2524 : int probability;
1769 2524 : wi::overflow_type overflow;
1770 2524 : bool overall_overflow = false;
1771 2524 : widest_int compare_count, tem;
1772 :
1773 : /* (loop_bound - base) / compare_step */
1774 2524 : tem = wi::sub (wi::to_widest (loop_bound_var),
1775 5048 : wi::to_widest (compare_base), SIGNED, &overflow);
1776 2524 : overall_overflow |= overflow;
1777 2524 : widest_int loop_count = wi::div_trunc (tem,
1778 2524 : wi::to_widest (compare_step_var),
1779 2524 : SIGNED, &overflow);
1780 2524 : overall_overflow |= overflow;
1781 :
1782 2524 : if (!wi::neg_p (wi::to_widest (compare_step_var))
1783 2524 : ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1784 : {
1785 : /* (loop_bound - compare_bound) / compare_step */
1786 371 : tem = wi::sub (wi::to_widest (loop_bound_var),
1787 742 : wi::to_widest (compare_var), SIGNED, &overflow);
1788 371 : overall_overflow |= overflow;
1789 371 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1790 371 : SIGNED, &overflow);
1791 371 : overall_overflow |= overflow;
1792 : }
1793 : else
1794 : {
1795 : /* (compare_bound - base) / compare_step */
1796 2153 : tem = wi::sub (wi::to_widest (compare_var),
1797 4306 : wi::to_widest (compare_base), SIGNED, &overflow);
1798 2153 : overall_overflow |= overflow;
1799 2153 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1800 2153 : SIGNED, &overflow);
1801 2153 : overall_overflow |= overflow;
1802 : }
1803 2524 : if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1804 2136 : ++compare_count;
1805 2524 : if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1806 175 : ++loop_count;
1807 2524 : if (wi::neg_p (compare_count))
1808 766 : compare_count = 0;
1809 2524 : if (wi::neg_p (loop_count))
1810 801 : loop_count = 0;
1811 2524 : if (loop_count == 0)
1812 : probability = 0;
1813 1708 : else if (wi::cmps (compare_count, loop_count) == 1)
1814 : probability = REG_BR_PROB_BASE;
1815 : else
1816 : {
1817 1664 : tem = compare_count * REG_BR_PROB_BASE;
1818 1664 : tem = wi::udiv_trunc (tem, loop_count);
1819 1664 : probability = tem.to_uhwi ();
1820 : }
1821 :
1822 : /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1823 2524 : if (!overall_overflow)
1824 2524 : predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1825 :
1826 2524 : return;
1827 2524 : }
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 830597 : predict_extra_loop_exits (class loop *loop, edge exit_edge)
1907 : {
1908 830597 : unsigned i;
1909 830597 : bool check_value_one;
1910 830597 : gimple *lhs_def_stmt;
1911 830597 : gphi *phi_stmt;
1912 830597 : tree cmp_rhs, cmp_lhs;
1913 :
1914 1661194 : gcond *cmp_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1915 817106 : if (!cmp_stmt)
1916 : return;
1917 :
1918 817106 : cmp_rhs = gimple_cond_rhs (cmp_stmt);
1919 817106 : cmp_lhs = gimple_cond_lhs (cmp_stmt);
1920 817106 : if (!TREE_CONSTANT (cmp_rhs)
1921 817106 : || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1922 602002 : return;
1923 215104 : 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 215104 : check_value_one = (((integer_onep (cmp_rhs))
1930 215104 : ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1931 215104 : ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1932 :
1933 215104 : lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1934 215104 : if (!lhs_def_stmt)
1935 : return;
1936 :
1937 215104 : phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1938 : if (!phi_stmt)
1939 : return;
1940 :
1941 222845 : for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1942 : {
1943 150044 : edge e1;
1944 150044 : edge_iterator ei;
1945 150044 : tree val = gimple_phi_arg_def (phi_stmt, i);
1946 150044 : edge e = gimple_phi_arg_edge (phi_stmt, i);
1947 :
1948 150044 : if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1949 135390 : continue;
1950 40173 : if ((check_value_one ^ integer_onep (val)) == 1)
1951 19904 : continue;
1952 20269 : if (EDGE_COUNT (e->src->succs) != 1)
1953 : {
1954 5615 : predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1955 : loop);
1956 5615 : continue;
1957 : }
1958 :
1959 31892 : FOR_EACH_EDGE (e1, ei, e->src->preds)
1960 17238 : 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 271740 : predict_loops (void)
1970 : {
1971 271740 : basic_block bb;
1972 271740 : hash_set <class loop *> with_recursion(10);
1973 :
1974 5462600 : FOR_EACH_BB_FN (bb, cfun)
1975 : {
1976 5190860 : gimple_stmt_iterator gsi;
1977 5190860 : tree decl;
1978 :
1979 34496306 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1980 24114586 : if (is_gimple_call (gsi_stmt (gsi))
1981 2222647 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1982 26153457 : && recursive_call_p (current_function_decl, decl))
1983 : {
1984 5863 : class loop *loop = bb->loop_father;
1985 12063 : while (loop && !with_recursion.add (loop))
1986 6200 : 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 1460520 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1993 : {
1994 645300 : basic_block bb, *bbs;
1995 645300 : unsigned j, n_exits = 0;
1996 645300 : class tree_niter_desc niter_desc;
1997 645300 : edge ex;
1998 645300 : class nb_iter_bound *nb_iter;
1999 645300 : enum tree_code loop_bound_code = ERROR_MARK;
2000 645300 : tree loop_bound_step = NULL;
2001 645300 : tree loop_bound_var = NULL;
2002 645300 : tree loop_iv_base = NULL;
2003 645300 : gcond *stmt = NULL;
2004 645300 : bool recursion = with_recursion.contains (loop);
2005 :
2006 645300 : auto_vec<edge> exits = get_loop_exit_edges (loop);
2007 2323378 : FOR_EACH_VEC_ELT (exits, j, ex)
2008 1032778 : if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
2009 877695 : n_exits ++;
2010 645300 : if (!n_exits)
2011 16011 : continue;
2012 :
2013 629289 : 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 629560 : && 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 629560 : && 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 1645879 : FOR_EACH_VEC_ELT (exits, j, ex)
2031 : {
2032 1016590 : tree niter = NULL;
2033 1016590 : HOST_WIDE_INT nitercst;
2034 1016590 : int max = param_max_predicted_iterations;
2035 1016590 : int probability;
2036 1016590 : enum br_predictor predictor;
2037 1016590 : widest_int nit;
2038 :
2039 1016590 : if (unlikely_executed_edge_p (ex)
2040 1016590 : || (ex->flags & EDGE_ABNORMAL_CALL))
2041 138895 : continue;
2042 : /* Loop heuristics do not expect exit conditional to be inside
2043 : inner loop. We predict from innermost to outermost loop. */
2044 877695 : if (predicted_by_loop_heuristics_p (ex->src))
2045 : {
2046 47098 : 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 47098 : continue;
2051 : }
2052 830597 : predict_extra_loop_exits (loop, ex);
2053 :
2054 830597 : if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
2055 437493 : niter = niter_desc.niter;
2056 437493 : if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
2057 555407 : niter = loop_niter_by_eval (loop, ex);
2058 336 : if (dump_file && (dump_flags & TDF_DETAILS)
2059 830868 : && 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 830597 : if (TREE_CODE (niter) == INTEGER_CST)
2069 : {
2070 288064 : if (tree_fits_uhwi_p (niter)
2071 288064 : && max
2072 576122 : && compare_tree_int (niter, max - 1) == -1)
2073 205214 : nitercst = tree_to_uhwi (niter) + 1;
2074 : else
2075 82850 : 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 542533 : else if (n_exits == 1
2082 542533 : && 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 1079465 : else if (n_exits == 1
2094 253045 : && likely_max_stmt_executions (loop, &nit)
2095 685827 : && wi::ltu_p (nit,
2096 286204 : 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 5583 : nitercst = nit.to_shwi ();
2104 5583 : predictor = PRED_LOOP_ITERATIONS_MAX;
2105 : }
2106 : else
2107 : {
2108 536941 : 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 536941 : continue;
2112 : }
2113 :
2114 293656 : 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 293656 : if (nitercst == 0)
2120 6 : continue;
2121 :
2122 293650 : probability = RDIV (REG_BR_PROB_BASE, nitercst);
2123 293650 : predict_edge (ex, predictor, probability);
2124 1016590 : }
2125 :
2126 : /* Find information about loop bound variables. */
2127 888199 : for (nb_iter = loop->bounds; nb_iter;
2128 258910 : nb_iter = nb_iter->next)
2129 387545 : if (nb_iter->stmt
2130 387545 : && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2131 : {
2132 128635 : stmt = as_a <gcond *> (nb_iter->stmt);
2133 128635 : break;
2134 : }
2135 629289 : if (!stmt)
2136 1001308 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (loop->header));
2137 128635 : if (stmt)
2138 605409 : 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 629289 : bbs = get_loop_body (loop);
2145 :
2146 3808041 : for (j = 0; j < loop->num_nodes; j++)
2147 : {
2148 3178752 : edge e;
2149 3178752 : edge_iterator ei;
2150 :
2151 3178752 : 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 3178752 : if (predicted_by_p (bb, PRED_CONTINUE))
2158 : {
2159 8338 : if (dump_file && (dump_flags & TDF_DETAILS))
2160 0 : fprintf (dump_file, "BB %i predicted by continue.\n",
2161 : bb->index);
2162 8338 : continue;
2163 : }
2164 :
2165 : /* If we already used more reliable loop exit predictors, do not
2166 : bother with PRED_LOOP_EXIT. */
2167 3170414 : 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 5146318 : int probability = ((REG_BR_PROB_BASE
2184 2573159 : - predictor_info
2185 : [recursion
2186 2573159 : ? PRED_LOOP_EXIT_WITH_RECURSION
2187 2573159 : : PRED_LOOP_EXIT].hitrate)
2188 2573159 : / n_exits);
2189 2573159 : if (probability < HITRATE (2))
2190 : probability = HITRATE (2);
2191 6247813 : FOR_EACH_EDGE (e, ei, bb->succs)
2192 3674654 : if (e->dest->index < NUM_FIXED_BLOCKS
2193 3674654 : || !flow_bb_inside_loop_p (loop, e->dest))
2194 : {
2195 656721 : 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 1306619 : predict_edge (e,
2200 : recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2201 : : PRED_LOOP_EXIT, probability);
2202 : }
2203 : }
2204 3170414 : if (loop_bound_var)
2205 2024195 : predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2206 : loop_bound_code,
2207 2024195 : 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 629289 : if (loop_outer (loop)->num)
2217 : {
2218 134324 : basic_block bb = NULL;
2219 134324 : edge preheader_edge = loop_preheader_edge (loop);
2220 :
2221 134324 : if (single_pred_p (preheader_edge->src)
2222 246446 : && single_succ_p (preheader_edge->src))
2223 112122 : 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 134324 : gcond *stmt
2238 268648 : = safe_dyn_cast <gcond *> (*gsi_last_bb (preheader_edge->src));
2239 109661 : if (stmt
2240 109661 : && gimple_cond_code (stmt) == NE_EXPR
2241 35460 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2242 35460 : && integer_zerop (gimple_cond_rhs (stmt)))
2243 : {
2244 14872 : gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2245 14872 : if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2246 6369 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt))
2247 15728 : && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2248 856 : call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2249 14872 : 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 15702 : && 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 134302 : if (!dominated_by_p (CDI_DOMINATORS,
2259 134302 : loop_outer (loop)->latch, loop->header))
2260 56463 : 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 629289 : free (bbs);
2282 917042 : }
2283 271740 : }
2284 :
2285 : /* Attempt to predict probabilities of BB outgoing edges using local
2286 : properties. */
2287 : static void
2288 568588 : bb_estimate_probability_locally (basic_block bb)
2289 : {
2290 568588 : rtx_insn *last_insn = BB_END (bb);
2291 568588 : rtx cond;
2292 :
2293 568588 : if (! can_predict_insn_p (last_insn))
2294 : return;
2295 169509 : cond = get_condition (last_insn, NULL, false, false);
2296 169509 : 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 146395 : if (COMPARISON_P (cond)
2303 146395 : && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2304 144895 : || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2305 : {
2306 1501 : if (GET_CODE (cond) == EQ)
2307 33 : predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2308 1468 : 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 144894 : 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 21845 : case EQ:
2326 21845 : 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 21845 : 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 21845 : else if (XEXP (cond, 1) == const0_rtx
2335 509 : || XEXP (cond, 0) == const0_rtx)
2336 : ;
2337 : else
2338 509 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2339 : break;
2340 :
2341 84220 : case NE:
2342 84220 : 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 84220 : 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 84220 : else if (XEXP (cond, 1) == const0_rtx
2351 78918 : || XEXP (cond, 0) == const0_rtx)
2352 : ;
2353 : else
2354 78918 : 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 5197 : case LE:
2366 5197 : case LT:
2367 5197 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2368 0 : || XEXP (cond, 1) == constm1_rtx)
2369 5197 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2370 : break;
2371 :
2372 5576 : case GE:
2373 5576 : case GT:
2374 5576 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2375 5509 : || XEXP (cond, 1) == constm1_rtx)
2376 2250 : 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 568588 : guess_outgoing_edge_probabilities (basic_block bb)
2387 : {
2388 568588 : bb_estimate_probability_locally (bb);
2389 568588 : combine_predictions_for_insn (BB_END (bb), bb);
2390 568588 : }
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 15970632 : 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 15970632 : gimple *def;
2403 :
2404 : /* Reset returned probability value. */
2405 15970632 : *probability = -1;
2406 15970632 : *predictor = PRED_UNCONDITIONAL;
2407 :
2408 15970632 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2409 : {
2410 10186460 : if (TREE_CONSTANT (op0))
2411 : return op0;
2412 :
2413 10184609 : if (code == IMAGPART_EXPR)
2414 : {
2415 51404 : if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2416 : {
2417 49795 : def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2418 49795 : if (is_gimple_call (def)
2419 47660 : && gimple_call_internal_p (def)
2420 97397 : && (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 10179019 : if (code != SSA_NAME)
2432 : return NULL_TREE;
2433 :
2434 7956810 : def = SSA_NAME_DEF_STMT (op0);
2435 :
2436 : /* If we were already here, break the infinite cycle. */
2437 7956810 : bool existed_p;
2438 7956810 : expected_value *res
2439 7956810 : = &ssa_expected_value->get_or_insert (SSA_NAME_VERSION (op0),
2440 : &existed_p);
2441 7956810 : if (existed_p)
2442 : {
2443 1662358 : *probability = res->probability;
2444 1662358 : *predictor = res->predictor;
2445 1662358 : return res->val;
2446 : }
2447 6294452 : res->val = NULL_TREE;
2448 6294452 : res->predictor = *predictor;
2449 6294452 : res->probability = *probability;
2450 :
2451 6294452 : if (gphi *phi = dyn_cast <gphi *> (def))
2452 : {
2453 : /* All the arguments of the PHI node must have the same constant
2454 : length. */
2455 905108 : int i, n = gimple_phi_num_args (phi);
2456 905108 : tree val = NULL;
2457 905108 : 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 1817655 : for (i = 0; i < n && !has_nonzero_edge; i++)
2462 : {
2463 912547 : tree arg = PHI_ARG_DEF (phi, i);
2464 912547 : if (arg == PHI_RESULT (phi))
2465 0 : continue;
2466 912547 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2467 923592 : if (!cnt.initialized_p () || cnt.nonzero_p ())
2468 : has_nonzero_edge = true;
2469 : }
2470 :
2471 1483018 : for (i = 0; i < n; i++)
2472 : {
2473 1480012 : tree arg = PHI_ARG_DEF (phi, i);
2474 1480012 : enum br_predictor predictor2;
2475 :
2476 : /* Skip self-referring parameters, since they does not change
2477 : expected value. */
2478 1480012 : if (arg == PHI_RESULT (phi))
2479 577903 : continue;
2480 :
2481 : /* Skip edges which we already predicted as executing
2482 : zero times. */
2483 1480012 : if (has_nonzero_edge)
2484 : {
2485 1475308 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2486 1475308 : if (cnt.initialized_p () && !cnt.nonzero_p ())
2487 217 : continue;
2488 : }
2489 1479795 : HOST_WIDE_INT probability2;
2490 1479795 : tree new_val = expr_expected_value (arg, &predictor2,
2491 : &probability2);
2492 : /* If we know nothing about value, give up. */
2493 1479795 : if (!new_val)
2494 902102 : return NULL;
2495 :
2496 : /* If this is a first edge, trust its prediction. */
2497 644919 : if (!val)
2498 : {
2499 569997 : val = new_val;
2500 569997 : *predictor = predictor2;
2501 569997 : *probability = probability2;
2502 569997 : continue;
2503 : }
2504 : /* If there are two different values, give up. */
2505 74922 : if (!operand_equal_p (val, new_val, false))
2506 : return NULL;
2507 :
2508 7696 : int p1 = get_predictor_value (*predictor, *probability);
2509 7696 : 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 7696 : if (*predictor == predictor2 && p1 == p2)
2513 7689 : 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 3006 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2526 3006 : res->val = val;
2527 3006 : res->predictor = *predictor;
2528 3006 : res->probability = *probability;
2529 3006 : return val;
2530 : }
2531 5389344 : if (is_gimple_assign (def))
2532 : {
2533 4124122 : if (gimple_assign_lhs (def) != op0)
2534 : return NULL;
2535 :
2536 4124122 : 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 4124122 : if (val)
2542 : {
2543 46944 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2544 46944 : res->val = val;
2545 46944 : res->predictor = *predictor;
2546 46944 : res->probability = *probability;
2547 : }
2548 4124122 : return val;
2549 : }
2550 :
2551 1265222 : if (is_gimple_call (def))
2552 : {
2553 872519 : tree decl = gimple_call_fndecl (def);
2554 872519 : if (!decl)
2555 : {
2556 78136 : if (gimple_call_internal_p (def)
2557 78136 : && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2558 : {
2559 32315 : gcc_assert (gimple_call_num_args (def) == 3);
2560 32315 : tree val = gimple_call_arg (def, 0);
2561 32315 : if (TREE_CONSTANT (val))
2562 : return val;
2563 32315 : tree val2 = gimple_call_arg (def, 2);
2564 32315 : gcc_assert (TREE_CODE (val2) == INTEGER_CST
2565 : && tree_fits_uhwi_p (val2)
2566 : && tree_to_uhwi (val2) < END_PREDICTORS);
2567 32315 : *predictor = (enum br_predictor) tree_to_uhwi (val2);
2568 32315 : if (*predictor == PRED_BUILTIN_EXPECT)
2569 8748 : *probability
2570 8748 : = HITRATE (param_builtin_expect_probability);
2571 32315 : val = gimple_call_arg (def, 1);
2572 32315 : res->val = val;
2573 32315 : res->predictor = *predictor;
2574 32315 : res->probability = *probability;
2575 32315 : return val;
2576 : }
2577 : return NULL;
2578 : }
2579 :
2580 794383 : if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2581 : {
2582 12096 : if (predictor)
2583 12096 : *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 12096 : tree val = fold_convert (type, boolean_true_node);
2589 12096 : res->val = val;
2590 12096 : res->predictor = *predictor;
2591 12096 : res->probability = *probability;
2592 12096 : return val;
2593 : }
2594 :
2595 782287 : if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2596 428953 : switch (DECL_FUNCTION_CODE (decl))
2597 : {
2598 80480 : case BUILT_IN_EXPECT:
2599 80480 : {
2600 80480 : tree val;
2601 80480 : if (gimple_call_num_args (def) != 2)
2602 : return NULL;
2603 80480 : val = gimple_call_arg (def, 0);
2604 80480 : if (TREE_CONSTANT (val))
2605 : return val;
2606 80480 : *predictor = PRED_BUILTIN_EXPECT;
2607 80480 : *probability
2608 80480 : = HITRATE (param_builtin_expect_probability);
2609 80480 : val = gimple_call_arg (def, 1);
2610 80480 : res->val = val;
2611 80480 : res->predictor = *predictor;
2612 80480 : res->probability = *probability;
2613 80480 : 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 1948 : case BUILT_IN_REALLOC:
2684 1948 : case BUILT_IN_GOMP_REALLOC:
2685 1948 : if (predictor)
2686 1948 : *predictor = PRED_MALLOC_NONNULL;
2687 : /* FIXME: This is wrong and we need to convert the logic
2688 : to value ranges. */
2689 1948 : res->val = fold_convert (type, boolean_true_node);
2690 1948 : res->predictor = *predictor;
2691 1948 : res->probability = *probability;
2692 1948 : return res->val;
2693 : default:
2694 : break;
2695 : }
2696 : }
2697 :
2698 1087371 : return NULL;
2699 : }
2700 :
2701 5784172 : if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2702 : {
2703 5374909 : tree res;
2704 5374909 : tree nop0 = op0;
2705 5374909 : 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 5374909 : if (TREE_CODE (op0) != INTEGER_CST)
2711 : {
2712 : /* See if expected value of op0 is good enough to determine the result. */
2713 5350904 : nop0 = expr_expected_value (op0, predictor, probability);
2714 5350904 : if (nop0
2715 144901 : && (res = fold_build2 (code, type, nop0, op1)) != NULL
2716 5495805 : && 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 5211723 : if (!nop0)
2725 5230008 : nop0 = op0;
2726 : }
2727 5235728 : enum br_predictor predictor2 = PRED_UNCONDITIONAL;
2728 5235728 : HOST_WIDE_INT probability2 = -1;
2729 5235728 : if (TREE_CODE (op1) != INTEGER_CST)
2730 : {
2731 : /* See if expected value of op1 is good enough to determine the result. */
2732 1603344 : nop1 = expr_expected_value (op1, &predictor2, &probability2);
2733 1603344 : if (nop1
2734 225711 : && (res = fold_build2 (code, type, op0, nop1)) != NULL
2735 1829055 : && 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 1603287 : if (!nop1)
2743 5010017 : 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 5235671 : 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 409263 : if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2785 : {
2786 408151 : tree res;
2787 408151 : op0 = expr_expected_value (op0, predictor, probability);
2788 408151 : if (!op0)
2789 : return NULL;
2790 37277 : res = fold_build1 (code, type, op0);
2791 37277 : 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 8868595 : expr_expected_value (tree expr, enum br_predictor *predictor,
2808 : HOST_WIDE_INT *probability)
2809 : {
2810 8868595 : enum tree_code code;
2811 8868595 : tree op0, op1;
2812 :
2813 8868595 : if (TREE_CONSTANT (expr))
2814 : {
2815 867755 : *predictor = PRED_UNCONDITIONAL;
2816 867755 : *probability = -1;
2817 867755 : return expr;
2818 : }
2819 :
2820 8000840 : extract_ops_from_tree (expr, &code, &op0, &op1);
2821 8000840 : return expr_expected_value_1 (TREE_TYPE (expr),
2822 8000840 : 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 152930 : get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2831 : {
2832 152930 : switch (predictor)
2833 : {
2834 89572 : case PRED_BUILTIN_EXPECT:
2835 89572 : case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2836 89572 : case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
2837 89572 : case PRED_COMBINED_VALUE_PREDICTIONS:
2838 89572 : gcc_assert (probability != -1);
2839 : return probability;
2840 63358 : default:
2841 63358 : gcc_assert (probability == -1);
2842 63358 : return predictor_info[(int) predictor].hitrate;
2843 : }
2844 : }
2845 :
2846 : /* Predict using opcode of the last statement in basic block. */
2847 : static void
2848 11372821 : tree_predict_by_opcode (basic_block bb)
2849 : {
2850 11372821 : edge then_edge;
2851 11372821 : tree op0, op1;
2852 11372821 : tree type;
2853 11372821 : tree val;
2854 11372821 : enum tree_code cmp;
2855 11372821 : edge_iterator ei;
2856 11372821 : enum br_predictor predictor;
2857 11372821 : HOST_WIDE_INT probability;
2858 :
2859 11372821 : gimple *stmt = *gsi_last_bb (bb);
2860 11372821 : if (!stmt)
2861 7527151 : return;
2862 :
2863 10907209 : if (gswitch *sw = dyn_cast <gswitch *> (stmt))
2864 : {
2865 26401 : tree index = gimple_switch_index (sw);
2866 26401 : tree val = expr_expected_value (index, &predictor, &probability);
2867 26401 : 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 10907209 : if (gimple_code (stmt) != GIMPLE_COND)
2883 : return;
2884 3976146 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
2885 3976146 : if (then_edge->flags & EDGE_TRUE_VALUE)
2886 : break;
2887 3845670 : op0 = gimple_cond_lhs (stmt);
2888 3845670 : op1 = gimple_cond_rhs (stmt);
2889 3845670 : cmp = gimple_cond_code (stmt);
2890 3845670 : type = TREE_TYPE (op0);
2891 3845670 : val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1,
2892 : &predictor, &probability);
2893 3845670 : if (val && TREE_CODE (val) == INTEGER_CST)
2894 : {
2895 137216 : HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2896 137216 : if (integer_zerop (val))
2897 111433 : prob = REG_BR_PROB_BASE - prob;
2898 137216 : 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 3845670 : if (POINTER_TYPE_P (type))
2904 : {
2905 561975 : if (cmp == EQ_EXPR)
2906 227340 : predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2907 334635 : else if (cmp == NE_EXPR)
2908 315539 : 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 3283695 : switch (cmp)
2917 : {
2918 884899 : case EQ_EXPR:
2919 884899 : 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 884899 : 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 872451 : else if (integer_zerop (op0) || integer_zerop (op1))
2928 : ;
2929 : else
2930 344447 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2931 : break;
2932 :
2933 1567054 : case NE_EXPR:
2934 1567054 : 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 1567054 : 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 1451258 : else if (integer_zerop (op0)
2943 1451258 : || integer_zerop (op1))
2944 : ;
2945 : else
2946 529215 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2947 : break;
2948 :
2949 2299 : case ORDERED_EXPR:
2950 2299 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2951 2299 : break;
2952 :
2953 2575 : case UNORDERED_EXPR:
2954 2575 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2955 2575 : break;
2956 :
2957 343620 : case LE_EXPR:
2958 343620 : case LT_EXPR:
2959 343620 : if (integer_zerop (op1)
2960 281451 : || integer_onep (op1)
2961 274302 : || integer_all_onesp (op1)
2962 274247 : || real_zerop (op1)
2963 271045 : || real_onep (op1)
2964 614160 : || real_minus_onep (op1))
2965 73084 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2966 : break;
2967 :
2968 475934 : case GE_EXPR:
2969 475934 : case GT_EXPR:
2970 475934 : if (integer_zerop (op1)
2971 412785 : || integer_onep (op1)
2972 401080 : || integer_all_onesp (op1)
2973 400806 : || real_zerop (op1)
2974 399261 : || real_onep (op1)
2975 874420 : || real_minus_onep (op1))
2976 77472 : 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 828190 : is_exit_with_zero_arg (const gimple *stmt)
2988 : {
2989 : /* This is not exit, _exit or _Exit. */
2990 828190 : if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2991 824334 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2992 1652502 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2993 : return false;
2994 :
2995 : /* Argument is an interger zero. */
2996 3878 : 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 701257 : return_prediction (tree val, enum prediction *prediction)
3003 : {
3004 : /* VOID. */
3005 701257 : if (!val)
3006 : return PRED_NO_PREDICTION;
3007 : /* Different heuristics for pointers and scalars. */
3008 701257 : if (POINTER_TYPE_P (TREE_TYPE (val)))
3009 : {
3010 : /* NULL is usually not returned. */
3011 141415 : if (integer_zerop (val))
3012 : {
3013 32246 : *prediction = NOT_TAKEN;
3014 32246 : return PRED_NULL_RETURN;
3015 : }
3016 : }
3017 559842 : else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
3018 : {
3019 : /* Negative return values are often used to indicate
3020 : errors. */
3021 458041 : if (TREE_CODE (val) == INTEGER_CST
3022 458041 : && tree_int_cst_sgn (val) < 0)
3023 : {
3024 12680 : *prediction = NOT_TAKEN;
3025 12680 : 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 445361 : if (TREE_CONSTANT (val)
3031 445361 : && (!integer_zerop (val) && !integer_onep (val)))
3032 : {
3033 74490 : *prediction = NOT_TAKEN;
3034 74490 : 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 62534 : zero_one_minusone (gphi *phi, int limit)
3046 : {
3047 62534 : int phi_num_args = gimple_phi_num_args (phi);
3048 62534 : int ret = 0;
3049 209340 : for (int i = 0; i < phi_num_args; i++)
3050 : {
3051 157175 : tree t = PHI_ARG_DEF (phi, i);
3052 157175 : if (TREE_CODE (t) != INTEGER_CST)
3053 71459 : continue;
3054 85716 : wide_int w = wi::to_wide (t);
3055 85716 : if (w == -1)
3056 5250 : ret |= 1;
3057 80466 : else if (w == 0)
3058 40130 : ret |= 2;
3059 40336 : else if (w == 1)
3060 29967 : ret |= 4;
3061 : else
3062 10369 : return 0;
3063 85716 : }
3064 119820 : for (int i = 0; i < phi_num_args; i++)
3065 : {
3066 102986 : tree t = PHI_ARG_DEF (phi, i);
3067 102986 : if (TREE_CODE (t) == INTEGER_CST)
3068 65932 : continue;
3069 37054 : if (TREE_CODE (t) != SSA_NAME)
3070 : return 0;
3071 37054 : gimple *g = SSA_NAME_DEF_STMT (t);
3072 37054 : if (gimple_code (g) == GIMPLE_PHI && limit > 0)
3073 12379 : if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
3074 : {
3075 443 : ret |= r;
3076 443 : continue;
3077 : }
3078 36611 : if (!is_gimple_assign (g))
3079 : return 0;
3080 13317 : if (gimple_assign_cast_p (g))
3081 : {
3082 3507 : tree rhs1 = gimple_assign_rhs1 (g);
3083 3507 : if (TREE_CODE (rhs1) != SSA_NAME
3084 3507 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
3085 3429 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
3086 4788 : || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3087 : return 0;
3088 1280 : ret |= (2 | 4);
3089 1280 : continue;
3090 1280 : }
3091 9810 : 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 2410822 : apply_return_prediction (void)
3102 : {
3103 2410822 : greturn *return_stmt = NULL;
3104 2410822 : tree return_val;
3105 2410822 : edge e;
3106 2410822 : gphi *phi;
3107 2410822 : int phi_num_args, i;
3108 2410822 : enum br_predictor pred;
3109 2410822 : enum prediction direction;
3110 2410822 : edge_iterator ei;
3111 :
3112 2473842 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3113 : {
3114 4951889 : if (greturn *last = safe_dyn_cast <greturn *> (*gsi_last_bb (e->src)))
3115 : {
3116 : return_stmt = last;
3117 : break;
3118 : }
3119 : }
3120 2410822 : if (!e)
3121 2232239 : return;
3122 2381787 : return_val = gimple_return_retval (return_stmt);
3123 2381787 : if (!return_val)
3124 : return;
3125 1341191 : if (TREE_CODE (return_val) != SSA_NAME
3126 987788 : || !SSA_NAME_DEF_STMT (return_val)
3127 2328979 : || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
3128 : return;
3129 179187 : phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
3130 179187 : phi_num_args = gimple_phi_num_args (phi);
3131 179187 : 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 356890 : if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
3140 126572 : && !TYPE_UNSIGNED (TREE_TYPE (return_val))
3141 229342 : && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
3142 50155 : if (int r = zero_one_minusone (phi, 3))
3143 16391 : 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 573358 : for (i = 1; i < phi_num_args; i++)
3150 426299 : if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
3151 : break;
3152 178583 : if (i != phi_num_args)
3153 127295 : for (i = 0; i < phi_num_args; i++)
3154 : {
3155 95771 : pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
3156 95771 : if (pred != PRED_NO_PREDICTION)
3157 50237 : 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 2410822 : tree_bb_level_predictions (void)
3168 : {
3169 2410822 : basic_block bb;
3170 2410822 : bool has_return_edges = false;
3171 2410822 : edge e;
3172 2410822 : edge_iterator ei;
3173 :
3174 2480020 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3175 2449706 : if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3176 : {
3177 : has_return_edges = true;
3178 : break;
3179 : }
3180 :
3181 2410822 : apply_return_prediction ();
3182 :
3183 13644863 : FOR_EACH_BB_FN (bb, cfun)
3184 : {
3185 11234041 : gimple_stmt_iterator gsi;
3186 :
3187 89276447 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3188 : {
3189 66808365 : gimple *stmt = gsi_stmt (gsi);
3190 66808365 : tree decl;
3191 :
3192 66808365 : if (is_gimple_call (stmt))
3193 : {
3194 6091686 : if (gimple_call_noreturn_p (stmt)
3195 892112 : && has_return_edges
3196 6919876 : && !is_exit_with_zero_arg (stmt))
3197 825652 : predict_paths_leading_to (bb, PRED_NORETURN,
3198 : NOT_TAKEN);
3199 6091686 : decl = gimple_call_fndecl (stmt);
3200 6091686 : if (decl
3201 11807642 : && lookup_attribute ("cold",
3202 5715956 : DECL_ATTRIBUTES (decl)))
3203 516357 : predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3204 : NOT_TAKEN);
3205 6091686 : if (decl && recursive_call_p (current_function_decl, decl))
3206 9681 : predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3207 : NOT_TAKEN);
3208 : }
3209 60716679 : else if (gimple_code (stmt) == GIMPLE_PREDICT)
3210 : {
3211 455526 : 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 2410822 : }
3219 :
3220 : /* Callback for hash_map::traverse, asserts that the pointer map is
3221 : empty. */
3222 :
3223 : bool
3224 3555786 : assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3225 : void *)
3226 : {
3227 3555786 : gcc_assert (!value);
3228 3555786 : 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 11372821 : tree_estimate_probability_bb (basic_block bb, bool local_only)
3236 : {
3237 11372821 : edge e;
3238 11372821 : edge_iterator ei;
3239 :
3240 27259812 : 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 12548396 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3245 12548380 : && !local_only
3246 12380409 : && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3247 24119885 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3248 : {
3249 6392356 : 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 36432477 : for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
3256 23647765 : gsi_next (&bi))
3257 : {
3258 26059309 : gimple *stmt = gsi_stmt (bi);
3259 26059309 : if (is_gimple_call (stmt)
3260 3029913 : && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
3261 : /* Constant and pure calls are hardly used to signalize
3262 : something exceptional. */
3263 28821111 : && gimple_has_side_effects (stmt))
3264 : {
3265 2411544 : if (gimple_call_fndecl (stmt))
3266 2349422 : predict_edge_def (e, PRED_CALL, NOT_TAKEN);
3267 62122 : else if (virtual_method_call_p (gimple_call_fn (stmt)))
3268 12722 : predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
3269 : else
3270 49400 : predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
3271 : break;
3272 : }
3273 : }
3274 : }
3275 : }
3276 11372821 : tree_predict_by_opcode (bb);
3277 11372821 : }
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 2410822 : tree_estimate_probability (bool dry_run)
3286 : {
3287 2410822 : basic_block bb;
3288 :
3289 2410822 : connect_infinite_loops_to_exit ();
3290 : /* We use loop_niter_by_eval, which requires that the loops have
3291 : preheaders. */
3292 2410822 : create_preheaders (CP_SIMPLE_PREHEADERS);
3293 2410822 : calculate_dominance_info (CDI_POST_DOMINATORS);
3294 : /* Decide which edges are known to be unlikely. This improves later
3295 : branch prediction. */
3296 2410822 : if (!dry_run)
3297 2410810 : determine_unlikely_bbs ();
3298 :
3299 2410822 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3300 2410822 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3301 :
3302 2410822 : tree_bb_level_predictions ();
3303 2410822 : record_loop_exits ();
3304 :
3305 4821644 : if (number_of_loops (cfun) > 1)
3306 271740 : predict_loops ();
3307 :
3308 13644863 : FOR_EACH_BB_FN (bb, cfun)
3309 11234041 : tree_estimate_probability_bb (bb, false);
3310 :
3311 13644863 : FOR_EACH_BB_FN (bb, cfun)
3312 11234041 : combine_predictions_for_bb (bb, dry_run);
3313 :
3314 2410822 : if (flag_checking)
3315 5966580 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3316 :
3317 4821644 : delete bb_predictions;
3318 2410822 : bb_predictions = NULL;
3319 4821644 : delete ssa_expected_value;
3320 2410822 : ssa_expected_value = NULL;
3321 :
3322 2410822 : if (!dry_run
3323 2410810 : && profile_status_for_fn (cfun) != PROFILE_READ)
3324 2410810 : estimate_bb_frequencies ();
3325 2410822 : free_dominance_info (CDI_POST_DOMINATORS);
3326 2410822 : remove_fake_exit_edges ();
3327 2410822 : }
3328 :
3329 : /* Set edge->probability for each successor edge of BB. */
3330 : void
3331 138780 : tree_guess_outgoing_edge_probabilities (basic_block bb)
3332 : {
3333 138780 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3334 138780 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3335 138780 : tree_estimate_probability_bb (bb, true);
3336 138780 : combine_predictions_for_bb (bb, false);
3337 138780 : if (flag_checking)
3338 138780 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3339 277560 : delete bb_predictions;
3340 138780 : bb_predictions = NULL;
3341 277560 : delete ssa_expected_value;
3342 138780 : ssa_expected_value = NULL;
3343 138780 : }
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 1065100 : maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3359 : {
3360 1065100 : if (edge_predicted_by_p (e, pred, taken))
3361 : return;
3362 1060675 : if (pred == PRED_LOOP_GUARD
3363 1060675 : && 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 1060667 : 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 1060667 : 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 2359154 : 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 2359154 : edge e;
3384 2359154 : edge_iterator ei;
3385 2359154 : basic_block son;
3386 :
3387 : /* If we exited the loop or CUR is unconditional in the loop, there is
3388 : nothing to do. */
3389 2359154 : if (in_loop
3390 2359154 : && (!flow_bb_inside_loop_p (in_loop, cur)
3391 72889 : || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3392 11063 : return;
3393 :
3394 : /* We are looking for all edges forming edge cut induced by
3395 : set of all blocks postdominated by BB. */
3396 5223518 : FOR_EACH_EDGE (e, ei, cur->preds)
3397 2875427 : if (e->src->index >= NUM_FIXED_BLOCKS
3398 2875427 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3399 : {
3400 2222292 : edge e2;
3401 2222292 : edge_iterator ei2;
3402 2222292 : bool found = false;
3403 :
3404 : /* Ignore fake edges and eh, we predict them as not taken anyway. */
3405 2222292 : if (unlikely_executed_edge_p (e))
3406 1161740 : continue;
3407 1060552 : 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 1931844 : FOR_EACH_EDGE (e2, ei2, e->src->succs)
3412 1903593 : if (e2 != e
3413 1067352 : && !unlikely_executed_edge_p (e2)
3414 1041157 : && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3415 2938574 : && (!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 1060552 : if (found)
3429 1032301 : maybe_predict_edge (e, pred, taken);
3430 28251 : else if (bitmap_set_bit (visited, e->src->index))
3431 28207 : predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3432 : }
3433 2348091 : for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3434 2803292 : son;
3435 455201 : son = next_dom_son (CDI_POST_DOMINATORS, son))
3436 455201 : 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 1807216 : predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3444 : enum prediction taken, class loop *in_loop)
3445 : {
3446 1807216 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3447 1807216 : }
3448 :
3449 : /* Like predict_paths_leading_to but take edge instead of basic block. */
3450 :
3451 : static void
3452 101329 : predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3453 : enum prediction taken, class loop *in_loop)
3454 : {
3455 101329 : bool has_nonloop_edge = false;
3456 101329 : edge_iterator ei;
3457 101329 : edge e2;
3458 :
3459 101329 : basic_block bb = e->src;
3460 190506 : FOR_EACH_EDGE (e2, ei, bb->succs)
3461 121976 : if (e2->dest != e->src && e2->dest != e->dest
3462 44497 : && !unlikely_executed_edge_p (e2)
3463 163867 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3464 : {
3465 : has_nonloop_edge = true;
3466 : break;
3467 : }
3468 :
3469 101329 : if (!has_nonloop_edge)
3470 68530 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3471 : else
3472 32799 : maybe_predict_edge (e, pred, taken);
3473 101329 : }
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 3258497 : propagate_freq (basic_block head, bitmap tovisit,
3513 : sreal max_cyclic_prob)
3514 : {
3515 3258497 : basic_block bb;
3516 3258497 : basic_block last;
3517 3258497 : unsigned i;
3518 3258497 : edge e;
3519 3258497 : basic_block nextbb;
3520 3258497 : 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 26603571 : EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3525 : {
3526 23345074 : edge_iterator ei;
3527 23345074 : int count = 0;
3528 :
3529 23345074 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
3530 :
3531 52030109 : FOR_EACH_EDGE (e, ei, bb->preds)
3532 : {
3533 28685035 : bool visit = bitmap_bit_p (tovisit, e->src->index);
3534 :
3535 28685035 : if (visit && !(e->flags & EDGE_DFS_BACK))
3536 26012552 : count++;
3537 1884664 : 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 23345074 : BLOCK_INFO (bb)->npredecessors = count;
3543 : /* When function never returns, we will never process exit block. */
3544 23345074 : if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3545 0 : bb->count = profile_count::zero ();
3546 : }
3547 :
3548 3258497 : BLOCK_INFO (head)->frequency = 1;
3549 3258497 : last = head;
3550 26603571 : for (bb = head; bb; bb = nextbb)
3551 : {
3552 23345074 : edge_iterator ei;
3553 23345074 : sreal cyclic_probability = 0;
3554 23345074 : sreal frequency = 0;
3555 :
3556 23345074 : nextbb = BLOCK_INFO (bb)->next;
3557 23345074 : BLOCK_INFO (bb)->next = NULL;
3558 :
3559 : /* Compute frequency of basic block. */
3560 23345074 : if (bb != head)
3561 : {
3562 20086577 : if (flag_checking)
3563 47195288 : FOR_EACH_EDGE (e, ei, bb->preds)
3564 27109100 : gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3565 : || (e->flags & EDGE_DFS_BACK));
3566 :
3567 47196238 : FOR_EACH_EDGE (e, ei, bb->preds)
3568 27109661 : if (EDGE_INFO (e)->back_edge)
3569 1092031 : cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3570 26017630 : 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 26012552 : sreal tmp = e->probability.initialized_p () ?
3575 26012552 : e->probability.to_sreal () : 0;
3576 26012552 : frequency += tmp * BLOCK_INFO (e->src)->frequency;
3577 : }
3578 :
3579 20086577 : if (cyclic_probability == 0)
3580 : {
3581 19021797 : BLOCK_INFO (bb)->frequency = frequency;
3582 : }
3583 : else
3584 : {
3585 1064780 : if (cyclic_probability > max_cyclic_prob)
3586 : {
3587 9784 : 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 9784 : cyclic_probability = max_cyclic_prob;
3596 : }
3597 1054996 : 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 1064780 : BLOCK_INFO (bb)->frequency = frequency
3604 1064780 : / (sreal (1) - cyclic_probability);
3605 1064780 : if (dump_file)
3606 363 : fprintf (dump_file, " to %f\n",
3607 363 : BLOCK_INFO (bb)->frequency.to_double ());
3608 : }
3609 : }
3610 :
3611 23345074 : bitmap_clear_bit (tovisit, bb->index);
3612 :
3613 23345074 : e = find_edge (bb, head);
3614 23345074 : if (e)
3615 : {
3616 : /* FIXME: Graphite is producing edges with no profile. Once
3617 : this is fixed, drop this. */
3618 787555 : sreal tmp = e->probability.initialized_p () ?
3619 787555 : e->probability.to_sreal () : 0;
3620 787555 : EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3621 : }
3622 :
3623 : /* Propagate to successor blocks. */
3624 52593948 : FOR_EACH_EDGE (e, ei, bb->succs)
3625 29248874 : if (!(e->flags & EDGE_DFS_BACK)
3626 27362979 : && BLOCK_INFO (e->dest)->npredecessors)
3627 : {
3628 26012552 : BLOCK_INFO (e->dest)->npredecessors--;
3629 26012552 : if (!BLOCK_INFO (e->dest)->npredecessors)
3630 : {
3631 20086577 : if (!nextbb)
3632 : nextbb = e->dest;
3633 : else
3634 7586926 : BLOCK_INFO (last)->next = e->dest;
3635 :
3636 : last = e->dest;
3637 : }
3638 : }
3639 : }
3640 3258497 : }
3641 :
3642 : /* Estimate frequencies in loops at same nest level. */
3643 :
3644 : static void
3645 1093921 : estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3646 : {
3647 1093921 : class loop *loop;
3648 :
3649 1881476 : for (loop = first_loop; loop; loop = loop->next)
3650 : {
3651 787555 : edge e;
3652 787555 : basic_block *bbs;
3653 787555 : unsigned i;
3654 787555 : auto_bitmap tovisit;
3655 :
3656 787555 : estimate_loops_at_level (loop->inner, max_cyclic_prob);
3657 :
3658 : /* Find current loop back edge and mark it. */
3659 787555 : e = loop_latch_edge (loop);
3660 787555 : EDGE_INFO (e)->back_edge = 1;
3661 :
3662 787555 : bbs = get_loop_body (loop);
3663 5907813 : for (i = 0; i < loop->num_nodes; i++)
3664 4332703 : bitmap_set_bit (tovisit, bbs[i]->index);
3665 787555 : free (bbs);
3666 787555 : propagate_freq (loop->header, tovisit, max_cyclic_prob);
3667 787555 : }
3668 1093921 : }
3669 :
3670 : /* Propagates frequencies through structure of loops. */
3671 :
3672 : static void
3673 2470942 : estimate_loops (void)
3674 : {
3675 2470942 : auto_bitmap tovisit;
3676 2470942 : basic_block bb;
3677 7412826 : sreal max_cyclic_prob = (sreal)1
3678 2470942 : - (sreal)1 / (param_max_predicted_iterations + 1);
3679 :
3680 : /* Start by estimating the frequencies in the loops. */
3681 4941884 : if (number_of_loops (cfun) > 1)
3682 306366 : estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3683 :
3684 : /* Now propagate the frequencies through all the blocks. */
3685 21483313 : FOR_ALL_BB_FN (bb, cfun)
3686 : {
3687 19012371 : bitmap_set_bit (tovisit, bb->index);
3688 : }
3689 2470942 : propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3690 2470942 : }
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 609 : handle_missing_profiles (void)
3778 : {
3779 609 : const int unlikely_frac = param_unlikely_bb_count_fraction;
3780 609 : struct cgraph_node *node;
3781 609 : 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 3439 : FOR_EACH_DEFINED_FUNCTION (node)
3786 : {
3787 2830 : struct cgraph_edge *e;
3788 2830 : profile_count call_count = profile_count::zero ();
3789 2830 : gcov_type max_tp_first_run = 0;
3790 2830 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3791 :
3792 2830 : if (node->count.ipa ().nonzero_p ())
3793 365 : continue;
3794 4709 : for (e = node->callers; e; e = e->next_caller)
3795 2244 : 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 2244 : 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 2465 : if (!node->tp_first_run && max_tp_first_run)
3806 4 : node->tp_first_run = max_tp_first_run + 1;
3807 :
3808 2465 : if (call_count > 0
3809 6 : && fn && fn->cfg
3810 2471 : && 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 609 : 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 609 : }
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 1718759 : update_max_bb_count (void)
3848 : {
3849 1718759 : profile_count true_count_max = profile_count::uninitialized ();
3850 1718759 : basic_block bb;
3851 :
3852 36077318 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3853 34358559 : true_count_max = profile_count::max_prefer_initialized (true_count_max, bb->count);
3854 :
3855 1718759 : cfun->cfg->count_max = true_count_max;
3856 :
3857 1718759 : 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 283923 : expensive_function_p (int threshold)
3867 : {
3868 283923 : 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 447175 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3873 : return true;
3874 :
3875 243569 : profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3876 243569 : profile_count sum = profile_count::zero ();
3877 3015056 : FOR_EACH_BB_FN (bb, cfun)
3878 : {
3879 2934739 : rtx_insn *insn;
3880 :
3881 2934739 : 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 44863508 : FOR_BB_INSNS (bb, insn)
3890 42092021 : if (active_insn_p (insn))
3891 : {
3892 17171111 : sum += bb->count;
3893 17171111 : 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 7219345 : propagate_unlikely_bbs_forward (void)
3906 : {
3907 7219345 : auto_vec<basic_block, 64> worklist;
3908 7219345 : basic_block bb;
3909 7219345 : edge_iterator ei;
3910 7219345 : edge e;
3911 :
3912 7236511 : if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3913 : {
3914 7202179 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3915 7202179 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3916 :
3917 77960146 : while (worklist.length () > 0)
3918 : {
3919 63555788 : bb = worklist.pop ();
3920 141828245 : FOR_EACH_EDGE (e, ei, bb->succs)
3921 79984712 : if (!(e->count () == profile_count::zero ())
3922 94426225 : && !(e->dest->count == profile_count::zero ())
3923 71841745 : && !e->dest->aux)
3924 : {
3925 56353609 : e->dest->aux = (void *)(size_t) 1;
3926 56353609 : worklist.safe_push (e->dest);
3927 : }
3928 : }
3929 : }
3930 :
3931 74656549 : FOR_ALL_BB_FN (bb, cfun)
3932 : {
3933 67437204 : if (!bb->aux)
3934 : {
3935 7762156 : if (!(bb->count == profile_count::zero ())
3936 391484 : && (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 3881416 : bb->count = profile_count::zero ();
3941 : }
3942 : else
3943 63555788 : bb->aux = NULL;
3944 : }
3945 7219345 : }
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 5912439 : determine_unlikely_bbs ()
3954 : {
3955 5912439 : basic_block bb;
3956 5912439 : auto_vec<basic_block, 64> worklist;
3957 5912439 : edge_iterator ei;
3958 5912439 : edge e;
3959 :
3960 40200631 : FOR_EACH_BB_FN (bb, cfun)
3961 : {
3962 68181285 : if (!(bb->count == profile_count::zero ())
3963 32402767 : && unlikely_executed_bb_p (bb))
3964 : {
3965 395099 : if (dump_file && (dump_flags & TDF_DETAILS))
3966 0 : fprintf (dump_file, "Basic block %i is locally unlikely\n",
3967 : bb->index);
3968 395099 : bb->count = profile_count::zero ();
3969 : }
3970 :
3971 82445532 : FOR_EACH_EDGE (e, ei, bb->succs)
3972 90099008 : if (!(e->probability == profile_probability::never ())
3973 48157340 : && unlikely_executed_edge_p (e))
3974 : {
3975 2022446 : 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 2022446 : e->probability = profile_probability::never ();
3979 : }
3980 :
3981 34288192 : gcc_checking_assert (!bb->aux);
3982 : }
3983 5912439 : propagate_unlikely_bbs_forward ();
3984 :
3985 5912439 : auto_vec<int, 64> nsuccs;
3986 5912439 : nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
3987 52025509 : FOR_ALL_BB_FN (bb, cfun)
3988 54581163 : if (!(bb->count == profile_count::zero ())
3989 43454597 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3990 : {
3991 37644977 : nsuccs[bb->index] = 0;
3992 89452881 : FOR_EACH_EDGE (e, ei, bb->succs)
3993 51807904 : if (!(e->probability == profile_probability::never ())
3994 100035635 : && !(e->dest->count == profile_count::zero ()))
3995 47163073 : nsuccs[bb->index]++;
3996 37644977 : if (!nsuccs[bb->index])
3997 1509241 : worklist.safe_push (bb);
3998 : }
3999 7448124 : while (worklist.length () > 0)
4000 : {
4001 1535685 : bb = worklist.pop ();
4002 1535685 : if (bb->count == profile_count::zero ())
4003 0 : continue;
4004 1535685 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4005 : {
4006 1527158 : bool found = false;
4007 3054316 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
4008 2660699 : !gsi_end_p (gsi); gsi_next (&gsi))
4009 2631335 : 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 2631335 : || (is_gimple_call (gsi_stmt (gsi))
4014 621209 : && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
4015 : {
4016 : found = true;
4017 : break;
4018 : }
4019 1527158 : if (found)
4020 1497794 : continue;
4021 : }
4022 37891 : 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 37891 : bb->count = profile_count::zero ();
4027 80404 : FOR_EACH_EDGE (e, ei, bb->preds)
4028 42513 : if (!(e->probability == profile_probability::never ()))
4029 : {
4030 41505 : if (!(e->src->count == profile_count::zero ()))
4031 : {
4032 41503 : gcc_checking_assert (nsuccs[e->src->index] > 0);
4033 41503 : nsuccs[e->src->index]--;
4034 41503 : if (!nsuccs[e->src->index])
4035 26444 : worklist.safe_push (e->src);
4036 : }
4037 : }
4038 : }
4039 : /* Finally all edges from non-0 regions to 0 are unlikely. */
4040 52025509 : FOR_ALL_BB_FN (bb, cfun)
4041 : {
4042 48809434 : if (!(bb->count == profile_count::zero ()))
4043 95170306 : FOR_EACH_EDGE (e, ei, bb->succs)
4044 51753600 : if (!(e->probability == profile_probability::never ())
4045 99915095 : && e->dest->count == profile_count::zero ())
4046 : {
4047 521260 : 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 521260 : e->probability = profile_probability::never ();
4052 : }
4053 :
4054 46113070 : edge other = NULL;
4055 :
4056 89127715 : FOR_EACH_EDGE (e, ei, bb->succs)
4057 53797224 : if (e->probability == profile_probability::never ())
4058 : ;
4059 47069173 : else if (other)
4060 : {
4061 : other = NULL;
4062 : break;
4063 : }
4064 : else
4065 : other = e;
4066 46113070 : if (other
4067 46113070 : && !(other->probability == profile_probability::always ()))
4068 : {
4069 8306134 : 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 8306134 : other->probability = profile_probability::always ();
4073 : }
4074 : }
4075 5912443 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
4076 22203 : cgraph_node::get (current_function_decl)->count = profile_count::zero ();
4077 5912439 : }
4078 :
4079 : /* Estimate and propagate basic block frequencies using the given branch
4080 : probabilities. */
4081 :
4082 : static void
4083 2470942 : estimate_bb_frequencies ()
4084 : {
4085 2470942 : basic_block bb;
4086 2470942 : sreal freq_max;
4087 :
4088 2470942 : determine_unlikely_bbs ();
4089 :
4090 2470942 : mark_dfs_back_edges ();
4091 :
4092 2470942 : 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 2470942 : alloc_aux_for_blocks (sizeof (block_info));
4097 2470942 : alloc_aux_for_edges (sizeof (edge_prob_info));
4098 21483313 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4099 : {
4100 19012371 : edge e;
4101 19012371 : edge_iterator ei;
4102 :
4103 41549129 : 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 22536758 : if (e->probability.initialized_p ())
4108 22536726 : EDGE_INFO (e)->back_edge_prob
4109 22536726 : = 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 2470942 : estimate_loops ();
4119 :
4120 2470942 : freq_max = 0;
4121 16541429 : FOR_EACH_BB_FN (bb, cfun)
4122 14070487 : if (freq_max < BLOCK_INFO (bb)->frequency)
4123 3123843 : 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 2470942 : freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
4130 2470942 : if (freq_max < 16)
4131 74 : freq_max = 16;
4132 2470942 : profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
4133 2470942 : cfun->cfg->count_max = profile_count::uninitialized ();
4134 21483313 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4135 : {
4136 19012371 : sreal tmp = BLOCK_INFO (bb)->frequency;
4137 19012371 : if (tmp >= 1)
4138 : {
4139 11147015 : gimple_stmt_iterator gsi;
4140 11147015 : 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 71960078 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4147 49671548 : if (is_gimple_call (gsi_stmt (gsi))
4148 2949533 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
4149 52320158 : && recursive_call_p (current_function_decl, decl))
4150 : {
4151 5500 : 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 5500 : tmp = (sreal)9 / (sreal)10;
4156 5500 : break;
4157 : }
4158 : }
4159 19012371 : tmp = tmp * freq_max;
4160 19012371 : 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 20254843 : if (!(bb->count == profile_count::zero ()))
4165 17769899 : bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
4166 19012371 : cfun->cfg->count_max
4167 19012371 : = profile_count::max_prefer_initialized (cfun->cfg->count_max,
4168 : bb->count);
4169 : }
4170 :
4171 2470942 : free_aux_for_blocks ();
4172 2470942 : free_aux_for_edges ();
4173 2470942 : compute_function_frequency ();
4174 2470942 : }
4175 :
4176 : /* Decide whether function is hot, cold or unlikely executed. */
4177 : void
4178 2500764 : compute_function_frequency (void)
4179 : {
4180 2500764 : basic_block bb;
4181 2500764 : struct cgraph_node *node = cgraph_node::get (current_function_decl);
4182 :
4183 2500764 : if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4184 2500764 : || MAIN_NAME_P (DECL_NAME (current_function_decl)))
4185 92658 : node->only_called_at_startup = true;
4186 2500764 : if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4187 1217 : node->only_called_at_exit = true;
4188 :
4189 2500764 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4190 : {
4191 2491779 : int flags = flags_from_decl_or_type (current_function_decl);
4192 2491779 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4193 : != NULL)
4194 617 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4195 2491162 : else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
4196 : != NULL)
4197 60 : node->frequency = NODE_FREQUENCY_HOT;
4198 2491102 : else if (flags & ECF_NORETURN)
4199 1978 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4200 2489124 : else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4201 79123 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4202 2410001 : else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4203 2410001 : || DECL_STATIC_DESTRUCTOR (current_function_decl))
4204 13946 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4205 2491779 : return;
4206 : }
4207 :
4208 8985 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4209 8985 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4210 : == NULL)
4211 8977 : warn_function_cold (current_function_decl);
4212 8985 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4213 8618 : return;
4214 957 : FOR_EACH_BB_FN (bb, cfun)
4215 : {
4216 844 : if (maybe_hot_bb_p (cfun, bb))
4217 : {
4218 254 : node->frequency = NODE_FREQUENCY_HOT;
4219 254 : return;
4220 : }
4221 590 : if (!probably_never_executed_bb_p (cfun, bb))
4222 536 : node->frequency = NODE_FREQUENCY_NORMAL;
4223 : }
4224 : }
4225 :
4226 : /* Build PREDICT_EXPR. */
4227 : tree
4228 1869446 : build_predict_expr (enum br_predictor predictor, enum prediction taken)
4229 : {
4230 1869446 : tree t = build1 (PREDICT_EXPR, void_type_node,
4231 1869446 : build_int_cst (integer_type_node, predictor));
4232 1869446 : SET_PREDICT_EXPR_OUTCOME (t, taken);
4233 1869446 : return t;
4234 : }
4235 :
4236 : const char *
4237 1251 : predictor_name (enum br_predictor predictor)
4238 : {
4239 1251 : 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 288047 : pass_profile (gcc::context *ctxt)
4263 576094 : : gimple_opt_pass (pass_data_profile, ctxt)
4264 : {}
4265 :
4266 : /* opt_pass methods: */
4267 2411726 : 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 2410696 : pass_profile::execute (function *fun)
4274 : {
4275 2410696 : unsigned nb_loops;
4276 :
4277 2410696 : if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4278 : return 0;
4279 :
4280 2410658 : loop_optimizer_init (LOOPS_NORMAL);
4281 2410658 : if (dump_file && (dump_flags & TDF_DETAILS))
4282 2 : flow_loops_dump (dump_file, NULL, 0);
4283 :
4284 2410658 : nb_loops = number_of_loops (fun);
4285 2410658 : if (nb_loops > 1)
4286 271583 : scev_initialize ();
4287 :
4288 2410658 : tree_estimate_probability (false);
4289 2410658 : cfun->cfg->full_profile = true;
4290 :
4291 2410658 : if (nb_loops > 1)
4292 271583 : scev_finalize ();
4293 :
4294 2410658 : loop_optimizer_finalize ();
4295 2410658 : if (dump_file && (dump_flags & TDF_DETAILS))
4296 2 : gimple_dump_cfg (dump_file, dump_flags);
4297 2410658 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4298 2410658 : profile_status_for_fn (fun) = PROFILE_GUESSED;
4299 2410658 : 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 288047 : make_pass_profile (gcc::context *ctxt)
4314 : {
4315 288047 : 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 365951 : 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 3453512 : strip_predict_hints (function *fun, bool early)
4340 : {
4341 3453512 : basic_block bb;
4342 3453512 : gimple *ass_stmt;
4343 3453512 : tree var;
4344 3453512 : bool changed = false;
4345 :
4346 26453001 : FOR_EACH_BB_FN (bb, fun)
4347 : {
4348 22999489 : gimple_stmt_iterator bi;
4349 200924461 : for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4350 : {
4351 154925483 : gimple *stmt = gsi_stmt (bi);
4352 :
4353 154925483 : if (gimple_code (stmt) == GIMPLE_PREDICT)
4354 : {
4355 1088125 : if (!early
4356 576392 : || strip_predictor_early (gimple_predict_predictor (stmt)))
4357 : {
4358 511733 : gsi_remove (&bi, true);
4359 511733 : changed = true;
4360 511733 : continue;
4361 : }
4362 : }
4363 154349091 : else if (is_gimple_call (stmt))
4364 : {
4365 12152376 : tree fndecl = gimple_call_fndecl (stmt);
4366 :
4367 12152376 : if (!early
4368 12152376 : && ((fndecl != NULL_TREE
4369 5844375 : && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4370 144879 : && gimple_call_num_args (stmt) == 2)
4371 : || (fndecl != NULL_TREE
4372 5699496 : && fndecl_built_in_p (fndecl,
4373 : BUILT_IN_EXPECT_WITH_PROBABILITY)
4374 18 : && gimple_call_num_args (stmt) == 3)
4375 6048625 : || (gimple_call_internal_p (stmt)
4376 170061 : && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4377 : {
4378 178303 : var = gimple_call_lhs (stmt);
4379 178303 : changed = true;
4380 178303 : if (var)
4381 : {
4382 178302 : ass_stmt
4383 178302 : = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4384 178302 : gsi_replace (&bi, ass_stmt, true);
4385 : }
4386 : else
4387 : {
4388 1 : gsi_remove (&bi, true);
4389 1 : continue;
4390 : }
4391 : }
4392 : }
4393 154413749 : gsi_next (&bi);
4394 : }
4395 : }
4396 3453512 : 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 864141 : pass_strip_predict_hints (gcc::context *ctxt)
4418 1728282 : : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4419 : {}
4420 :
4421 : /* opt_pass methods: */
4422 576094 : opt_pass * clone () final override
4423 : {
4424 576094 : return new pass_strip_predict_hints (m_ctxt);
4425 : }
4426 864141 : void set_pass_param (unsigned int n, bool param) final override
4427 : {
4428 864141 : gcc_assert (n == 0);
4429 864141 : early_p = param;
4430 864141 : }
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 3453512 : pass_strip_predict_hints::execute (function *fun)
4441 : {
4442 3453512 : return strip_predict_hints (fun, early_p);
4443 : }
4444 :
4445 : } // anon namespace
4446 :
4447 : gimple_opt_pass *
4448 288047 : make_pass_strip_predict_hints (gcc::context *ctxt)
4449 : {
4450 288047 : 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 1091067 : 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 1091067 : if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4465 1091067 : && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4466 : return;
4467 :
4468 :
4469 : /* See if everything is OK and update count_max. */
4470 1090819 : basic_block bb;
4471 1090819 : bool inconsistency_found = false;
4472 1090819 : bool uninitialized_probablity_found = false;
4473 1090819 : bool uninitialized_count_found = false;
4474 1090819 : bool feedback_found = false;
4475 :
4476 1090819 : cfun->cfg->count_max = profile_count::uninitialized ();
4477 15092689 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4478 : {
4479 14001870 : cfun->cfg->count_max
4480 14001870 : = profile_count::max_prefer_initialized (cfun->cfg->count_max,
4481 : bb->count);
4482 26494416 : 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 14001870 : 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 14001870 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4494 : && (!uninitialized_probablity_found || !inconsistency_found))
4495 : {
4496 12911051 : profile_count sum = profile_count::zero ();
4497 12911051 : edge e;
4498 12911051 : edge_iterator ei;
4499 :
4500 30350201 : FOR_EACH_EDGE (e, ei, bb->preds)
4501 : {
4502 17439150 : sum += e->count ();
4503 : /* Uninitialized probability may be result of inlining or an
4504 : omision in an optimization pass. */
4505 17439150 : 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 12911051 : if (sum.differs_from_p (bb->count))
4514 : {
4515 188980 : 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 1090819 : if (!inconsistency_found
4526 1030723 : && (!uninitialized_count_found || uninitialized_probablity_found)
4527 2121542 : && !cfun->cfg->count_max.very_large_p ())
4528 : {
4529 : /* Propagating zero counts should be safe and may
4530 : help hot/cold splitting. */
4531 1030678 : determine_unlikely_bbs ();
4532 1030678 : if (dump_file)
4533 31 : fprintf (dump_file, "Profile is consistent\n");
4534 1030678 : 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 60141 : 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 60132 : loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4567 60132 : connect_infinite_loops_to_exit ();
4568 60132 : estimate_bb_frequencies ();
4569 60132 : remove_fake_exit_edges ();
4570 60132 : loop_optimizer_finalize ();
4571 60132 : 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 576094 : pass_rebuild_frequencies (gcc::context *ctxt)
4596 1152188 : : gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4597 : {}
4598 :
4599 : /* opt_pass methods: */
4600 288047 : opt_pass * clone () final override
4601 : {
4602 288047 : 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 1041865 : unsigned int execute (function *) final override
4611 : {
4612 1041865 : rebuild_frequencies ();
4613 1041865 : 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 288047 : make_pass_rebuild_frequencies (gcc::context *ctxt)
4625 : {
4626 288047 : 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 580074 : force_edge_cold (edge e, bool impossible)
4670 : {
4671 580074 : profile_count count_sum = profile_count::zero ();
4672 580074 : profile_probability prob_sum = profile_probability::never ();
4673 580074 : edge_iterator ei;
4674 580074 : edge e2;
4675 580074 : bool uninitialized_exit = false;
4676 :
4677 : /* When branch probability guesses are not known, then do nothing. */
4678 580320 : if (!impossible && !e->count ().initialized_p ())
4679 1977 : return;
4680 :
4681 580074 : 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 580074 : if (e->probability <= goal
4686 54404 : && (!impossible || e->count () == profile_count::zero ()))
4687 1164 : return;
4688 1736265 : FOR_EACH_EDGE (e2, ei, e->src->succs)
4689 1157355 : if (e2 != e)
4690 : {
4691 578445 : if (e->flags & EDGE_FAKE)
4692 0 : continue;
4693 578445 : if (e2->count ().initialized_p ())
4694 578231 : count_sum += e2->count ();
4695 578445 : if (e2->probability.initialized_p ())
4696 578231 : 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 578910 : if (uninitialized_exit)
4704 214 : e->probability = goal;
4705 : /* If there are other edges out of e->src, redistribute probabilitity
4706 : there. */
4707 578696 : else if (prob_sum > profile_probability::never ())
4708 : {
4709 577566 : 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 577566 : set_edge_probability_and_rescale_others (e, goal);
4719 577566 : if (current_ir_type () != IR_GIMPLE
4720 577566 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4721 148798 : 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 1130 : if (prob_sum == profile_probability::never ())
4728 893 : e->probability = profile_probability::always ();
4729 : else
4730 : {
4731 237 : if (impossible)
4732 237 : 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 1130 : if (current_ir_type () != IR_GIMPLE
4738 1130 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4739 39 : update_br_prob_note (e->src);
4740 1130 : if (e->src->count == profile_count::zero ())
4741 141 : return;
4742 1978 : if (count_sum == profile_count::zero () && impossible)
4743 : {
4744 718 : bool found = false;
4745 718 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4746 : ;
4747 688 : else if (current_ir_type () == IR_GIMPLE)
4748 1376 : for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4749 2629 : !gsi_end_p (gsi); gsi_next (&gsi))
4750 : {
4751 1987 : 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 688 : if (!found)
4761 : {
4762 672 : 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 672 : e->src->count = profile_count::zero ();
4767 1427 : FOR_EACH_EDGE (e2, ei, e->src->preds)
4768 755 : 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 634 : if (!(prob_sum > profile_probability::never ())
4779 317 : && 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 260 : && 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. */
|
