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 57206 : get_hot_bb_threshold ()
127 : {
128 57206 : if (min_count == -1)
129 : {
130 100 : const int hot_frac = param_hot_bb_count_fraction;
131 200 : const gcov_type min_hot_count
132 : = hot_frac
133 100 : ? profile_info->sum_max / hot_frac
134 : : (gcov_type)profile_count::max_count;
135 100 : set_hot_bb_threshold (min_hot_count);
136 100 : if (dump_file)
137 21 : fprintf (dump_file, "Setting hotness threshold to %" PRId64 ".\n",
138 : min_hot_count);
139 : }
140 57206 : return min_count;
141 : }
142 :
143 : /* Set the threshold for hot BB counts. */
144 :
145 : void
146 360 : set_hot_bb_threshold (gcov_type min)
147 : {
148 360 : min_count = min;
149 360 : }
150 :
151 : /* Return TRUE if COUNT is considered to be hot in function FUN. */
152 :
153 : bool
154 1028338194 : maybe_hot_count_p (struct function *fun, profile_count count)
155 : {
156 1028338194 : if (!count.initialized_p ())
157 : return true;
158 937022921 : if (count.ipa () == profile_count::zero ())
159 4342779 : return false;
160 932680142 : if (!count.ipa_p ())
161 : {
162 932582666 : struct cgraph_node *node = cgraph_node::get (fun->decl);
163 932582666 : if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
164 : {
165 932582666 : if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
166 : return false;
167 932522289 : if (node->frequency == NODE_FREQUENCY_HOT)
168 : return true;
169 : }
170 932518197 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
171 : return true;
172 932314856 : if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
173 932314856 : && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
174 21608787 : return false;
175 910706069 : if (count * param_hot_bb_frequency_fraction
176 910706069 : < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
177 : return false;
178 : return true;
179 : }
180 : /* Code executed at most once is not hot. */
181 97476 : if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
182 : return false;
183 56991 : 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 1018175025 : maybe_hot_bb_p (struct function *fun, const_basic_block bb)
191 : {
192 1018175025 : gcc_checking_assert (fun);
193 1018175025 : 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 9560064 : maybe_hot_edge_p (edge e)
201 : {
202 9560064 : 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 56713013 : probably_never_executed (struct function *fun, profile_count count)
210 : {
211 56713013 : gcc_checking_assert (fun);
212 56713013 : if (count.ipa () == profile_count::zero ())
213 1494894 : 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 55218119 : if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
220 : {
221 3325 : const int unlikely_frac = param_unlikely_bb_count_fraction;
222 3325 : if (count * unlikely_frac >= profile_info->runs)
223 : return false;
224 : return true;
225 : }
226 3166 : if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
227 55214902 : && (cgraph_node::get (fun->decl)->frequency
228 55211736 : == 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 17410439 : probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
237 : {
238 17410439 : 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 121170050 : unlikely_executed_edge_p (edge e)
245 : {
246 123008874 : return (e->src->count == profile_count::zero ()
247 119036894 : || e->probability == profile_probability::never ())
248 114279228 : || (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 113725892 : || ((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 41360825 : probably_never_executed_edge_p (struct function *fun, edge e)
258 : {
259 41360825 : if (unlikely_executed_edge_p (e))
260 : return true;
261 39302574 : 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 2495793072 : optimize_function_for_size_p (struct function *fun)
268 : {
269 2495793072 : if (!fun || !fun->decl)
270 197986738 : return optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
271 2393365725 : cgraph_node *n = cgraph_node::get (fun->decl);
272 2393365725 : if (n)
273 2338807972 : 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 239094953 : optimize_function_for_speed_p (struct function *fun)
281 : {
282 239094953 : 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 1000793880 : optimize_bb_for_size_p (const_basic_block bb)
299 : {
300 1000793880 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
301 :
302 1989212054 : if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
303 26098085 : ret = OPTIMIZE_SIZE_MAX;
304 1000793880 : if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun, bb))
305 : ret = OPTIMIZE_SIZE_BALANCED;
306 1000793880 : return ret;
307 : }
308 :
309 : /* Return TRUE if basic block BB should be optimized for speed. */
310 :
311 : bool
312 935253519 : optimize_bb_for_speed_p (const_basic_block bb)
313 : {
314 935253519 : 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 5364999 : bb_optimization_type (const_basic_block bb)
321 : {
322 5364999 : return (optimize_bb_for_speed_p (bb)
323 5364999 : ? OPTIMIZE_FOR_SPEED
324 5364999 : : OPTIMIZE_FOR_SIZE);
325 : }
326 :
327 : /* Return TRUE if edge E should be optimized for size. */
328 :
329 : optimize_size_level
330 9962081 : optimize_edge_for_size_p (edge e)
331 : {
332 9962081 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
333 :
334 9962081 : if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
335 : ret = OPTIMIZE_SIZE_MAX;
336 9765934 : if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
337 : ret = OPTIMIZE_SIZE_BALANCED;
338 9962081 : return ret;
339 : }
340 :
341 : /* Return TRUE if edge E should be optimized for speed. */
342 :
343 : bool
344 4345921 : optimize_edge_for_speed_p (edge e)
345 : {
346 4345921 : 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 220750983 : optimize_insn_for_size_p (void)
353 : {
354 220750983 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
355 220750983 : if (ret < OPTIMIZE_SIZE_BALANCED && !crtl->maybe_hot_insn_p)
356 220750983 : ret = OPTIMIZE_SIZE_BALANCED;
357 220750983 : return ret;
358 : }
359 :
360 : /* Return TRUE if the current function is optimized for speed. */
361 :
362 : bool
363 86153514 : optimize_insn_for_speed_p (void)
364 : {
365 86153514 : 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 754545 : optimize_loop_for_size_p (class loop *loop)
383 : {
384 754545 : return optimize_bb_for_size_p (loop->header);
385 : }
386 :
387 : /* Return TRUE if LOOP should be optimized for speed. */
388 :
389 : bool
390 15415232 : optimize_loop_for_speed_p (class loop *loop)
391 : {
392 15415232 : 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 1218268 : optimize_loop_nest_for_speed_p (class loop *loop)
399 : {
400 1218268 : class loop *l = loop;
401 1218268 : if (optimize_loop_for_speed_p (loop))
402 : return true;
403 35097 : l = loop->inner;
404 47478 : while (l && l != loop)
405 : {
406 13807 : if (optimize_loop_for_speed_p (l))
407 : return true;
408 12381 : if (l->inner)
409 : l = l->inner;
410 8288 : else if (l->next)
411 : l = l->next;
412 : else
413 : {
414 19534 : while (l != loop && !l->next)
415 11647 : l = loop_outer (l);
416 7887 : if (l != loop)
417 52 : l = l->next;
418 : }
419 : }
420 : return false;
421 : }
422 :
423 : /* Return TRUE if nest rooted at LOOP should be optimized for size. */
424 :
425 : optimize_size_level
426 17133 : optimize_loop_nest_for_size_p (class loop *loop)
427 : {
428 17133 : enum optimize_size_level ret = optimize_loop_for_size_p (loop);
429 17133 : class loop *l = loop;
430 :
431 17133 : l = loop->inner;
432 17407 : while (l && l != loop)
433 : {
434 16659 : if (ret == OPTIMIZE_SIZE_NO)
435 : break;
436 274 : ret = MIN (optimize_loop_for_size_p (l), ret);
437 274 : if (l->inner)
438 : l = l->inner;
439 265 : else if (l->next)
440 : l = l->next;
441 : else
442 : {
443 325 : while (l != loop && !l->next)
444 165 : l = loop_outer (l);
445 160 : if (l != loop)
446 4 : l = l->next;
447 : }
448 : }
449 17133 : return ret;
450 : }
451 :
452 : /* Return true if edge E is likely to be well predictable by branch
453 : predictor. */
454 :
455 : bool
456 5802673 : predictable_edge_p (edge e)
457 : {
458 5802673 : if (!e->probability.initialized_p ())
459 : return false;
460 5801906 : if ((e->probability.to_reg_br_prob_base ()
461 5801906 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100)
462 5801906 : || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
463 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100))
464 625558 : return true;
465 : return false;
466 : }
467 :
468 :
469 : /* Set RTL expansion for BB profile. */
470 :
471 : void
472 79276361 : rtl_profile_for_bb (basic_block bb)
473 : {
474 79276361 : crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
475 79276361 : }
476 :
477 : /* Set RTL expansion for edge profile. */
478 :
479 : void
480 11602 : rtl_profile_for_edge (edge e)
481 : {
482 11602 : crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
483 11602 : }
484 :
485 : /* Set RTL expansion to default mode (i.e. when profile info is not known). */
486 : void
487 14231624 : default_rtl_profile (void)
488 : {
489 14231624 : crtl->maybe_hot_insn_p = true;
490 14231624 : }
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 3181848 : gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
537 : {
538 3181848 : struct edge_prediction *i;
539 3181848 : edge_prediction **preds = bb_predictions->get (bb);
540 :
541 3181848 : if (!preds)
542 : return false;
543 :
544 1583917 : for (i = *preds; i; i = i->ep_next)
545 823846 : 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 1093911 : edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
555 : {
556 1093911 : struct edge_prediction *i;
557 1093911 : basic_block bb = e->src;
558 1093911 : edge_prediction **preds = bb_predictions->get (bb);
559 1093911 : if (!preds)
560 : return false;
561 :
562 136075 : int probability = predictor_info[(int) predictor].hitrate;
563 :
564 136075 : if (taken != TAKEN)
565 135905 : probability = REG_BR_PROB_BASE - probability;
566 :
567 4849725 : for (i = *preds; i; i = i->ep_next)
568 4718052 : if (i->ep_predictor == predictor
569 4581680 : && i->ep_edge == e
570 4402 : && 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 86719 : predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
593 : {
594 86719 : gcc_assert (any_condjump_p (insn));
595 86719 : if (!flag_guess_branch_prob)
596 : return;
597 :
598 173344 : add_reg_note (insn, REG_BR_PRED,
599 86672 : 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 86719 : predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
608 : enum prediction taken)
609 : {
610 86719 : int probability = predictor_info[(int) predictor].hitrate;
611 86719 : gcc_assert (probability != PROB_UNINITIALIZED);
612 :
613 86719 : if (taken != TAKEN)
614 5864 : probability = REG_BR_PROB_BASE - probability;
615 :
616 86719 : predict_insn (insn, predictor, probability);
617 86719 : }
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 6159203 : gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
642 : {
643 6159203 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
644 6159203 : && EDGE_COUNT (e->src->succs) > 1
645 6159203 : && flag_guess_branch_prob
646 12318406 : && optimize)
647 : {
648 6159203 : struct edge_prediction *i = XNEW (struct edge_prediction);
649 6159203 : edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
650 :
651 6159203 : i->ep_next = preds;
652 6159203 : preds = i;
653 6159203 : i->ep_probability = probability;
654 6159203 : i->ep_predictor = predictor;
655 6159203 : i->ep_edge = e;
656 : }
657 6159203 : }
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 2845800 : filter_predictions (edge_prediction **preds,
665 : bool (*filter) (edge_prediction *, void *), void *data)
666 : {
667 2845800 : if (!bb_predictions)
668 : return;
669 :
670 2845800 : if (preds)
671 : {
672 : struct edge_prediction **prediction = preds;
673 : struct edge_prediction *next;
674 :
675 7869001 : while (*prediction)
676 : {
677 5023201 : if ((*filter) (*prediction, data))
678 4514946 : prediction = &((*prediction)->ep_next);
679 : else
680 : {
681 508255 : next = (*prediction)->ep_next;
682 508255 : free (*prediction);
683 508255 : *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 83979014 : remove_predictions_associated_with_edge (edge e)
702 : {
703 83979014 : 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 11421731 : clear_bb_predictions (basic_block bb)
714 : {
715 11421731 : edge_prediction **preds = bb_predictions->get (bb);
716 11421731 : struct edge_prediction *pred, *next;
717 :
718 11421731 : if (!preds)
719 : return;
720 :
721 9224872 : for (pred = *preds; pred; pred = next)
722 : {
723 5650948 : next = pred->ep_next;
724 5650948 : free (pred);
725 : }
726 3573924 : *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 1125314 : can_predict_insn_p (const rtx_insn *insn)
734 : {
735 1125314 : return (JUMP_P (insn)
736 335052 : && any_condjump_p (insn)
737 1459856 : && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
738 : }
739 :
740 : /* Predict edge E by given predictor if possible. */
741 :
742 : void
743 5065134 : predict_edge_def (edge e, enum br_predictor predictor,
744 : enum prediction taken)
745 : {
746 5065134 : int probability = predictor_info[(int) predictor].hitrate;
747 :
748 5065134 : if (taken != TAKEN)
749 4081149 : probability = REG_BR_PROB_BASE - probability;
750 :
751 5065134 : predict_edge (e, predictor, probability);
752 5065134 : }
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 12817448 : invert_br_probabilities (rtx insn)
759 : {
760 12817448 : rtx note;
761 :
762 37907264 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
763 25089816 : if (REG_NOTE_KIND (note) == REG_BR_PROB)
764 25475182 : XINT (note, 0) = profile_probability::from_reg_br_prob_note
765 12737591 : (XINT (note, 0)).invert ().to_reg_br_prob_note ();
766 12352225 : 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 12817448 : }
770 :
771 : /* Dump information about the branch prediction to the output file. */
772 :
773 : static void
774 12069461 : 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 12069461 : edge e = ep_edge;
779 12069461 : edge_iterator ei;
780 :
781 12069461 : if (!file)
782 12067594 : 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 173892183 : unlikely_executed_stmt_p (gimple *stmt)
833 : {
834 173892183 : 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 12294202 : if (gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE)
840 12248064 : || gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE_TRAP)
841 24542260 : || gimple_call_builtin_p (stmt, BUILT_IN_TRAP))
842 79394 : 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 12214808 : if (gimple_bb (stmt)->count.reliable_p ()
854 182482136 : && 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 12214542 : if (gimple_call_fntype (stmt)
859 11706304 : && lookup_attribute ("cold",
860 11706304 : TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
861 12214542 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
862 : return true;
863 12214542 : tree decl = gimple_call_fndecl (stmt);
864 12214542 : if (!decl)
865 : return false;
866 11466717 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
867 11466717 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
868 : return true;
869 :
870 11163553 : cgraph_node *n = cgraph_node::get (decl);
871 11163553 : if (!n)
872 : return false;
873 :
874 11157357 : availability avail;
875 11157357 : n = n->ultimate_alias_target (&avail);
876 11157357 : if (avail < AVAIL_AVAILABLE)
877 : return false;
878 3260273 : if (!n->analyzed
879 3260233 : || n->decl == current_function_decl)
880 : return false;
881 3242297 : return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
882 : }
883 :
884 : /* Return true if BB is unlikely executed. */
885 :
886 : static bool
887 32552403 : unlikely_executed_bb_p (basic_block bb)
888 : {
889 32552403 : if (bb->count == profile_count::zero ())
890 0 : return true;
891 32552403 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
892 : return false;
893 65104806 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
894 196783587 : !gsi_end_p (gsi); gsi_next (&gsi))
895 : {
896 173892183 : if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
897 : return true;
898 173494976 : 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 8504567 : set_even_probabilities (basic_block bb,
913 : hash_set<edge> *unlikely_edges = NULL,
914 : hash_set<edge_prediction *> *likely_edges = NULL)
915 : {
916 8504567 : unsigned nedges = 0, unlikely_count = 0;
917 8504567 : edge e = NULL;
918 8504567 : edge_iterator ei;
919 8504567 : profile_probability all = profile_probability::always ();
920 :
921 18640443 : FOR_EACH_EDGE (e, ei, bb->succs)
922 10135876 : if (e->probability.initialized_p ())
923 9114133 : all -= e->probability;
924 1021743 : else if (!unlikely_executed_edge_p (e))
925 : {
926 619580 : nedges++;
927 619580 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
928 : {
929 5097 : all -= profile_probability::very_unlikely ();
930 5097 : unlikely_count++;
931 : }
932 : }
933 :
934 : /* Make the distribution even if all edges are unlikely. */
935 8504567 : unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
936 8504567 : if (unlikely_count == nedges)
937 : {
938 8002849 : unlikely_edges = NULL;
939 8002849 : unlikely_count = 0;
940 : }
941 :
942 : /* If we have one likely edge, then use its probability and distribute
943 : remaining probabilities as even. */
944 8504567 : if (likely_count == 1)
945 : {
946 11358 : FOR_EACH_EDGE (e, ei, bb->succs)
947 7576 : if (e->probability.initialized_p ())
948 : ;
949 24 : else if (!unlikely_executed_edge_p (e))
950 : {
951 24 : edge_prediction *prediction = *likely_edges->begin ();
952 24 : int p = prediction->ep_probability;
953 24 : profile_probability prob
954 24 : = profile_probability::from_reg_br_prob_base (p);
955 :
956 24 : if (prediction->ep_edge == e)
957 6 : e->probability = prob;
958 18 : else if (unlikely_edges != NULL && unlikely_edges->contains (e))
959 1 : e->probability = profile_probability::very_unlikely ();
960 : else
961 : {
962 17 : profile_probability remainder = prob.invert ();
963 17 : remainder -= (profile_probability::very_unlikely ()
964 34 : * unlikely_count);
965 17 : int count = nedges - unlikely_count - 1;
966 17 : gcc_assert (count >= 0);
967 :
968 17 : e->probability = remainder / count;
969 : }
970 : }
971 : else
972 0 : e->probability = profile_probability::never ();
973 : }
974 : else
975 : {
976 : /* Make all unlikely edges unlikely and the rest will have even
977 : probability. */
978 8500785 : unsigned scale = nedges - unlikely_count;
979 18629085 : FOR_EACH_EDGE (e, ei, bb->succs)
980 10128300 : if (e->probability.initialized_p ())
981 : ;
982 1021719 : else if (!unlikely_executed_edge_p (e))
983 : {
984 619556 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
985 5096 : e->probability = profile_probability::very_unlikely ();
986 : else
987 614460 : e->probability = (all / scale).guessed ();
988 : }
989 : else
990 402163 : e->probability = profile_probability::never ();
991 : }
992 8504567 : }
993 :
994 : /* Add REG_BR_PROB note to JUMP with PROB. */
995 :
996 : void
997 5269025 : add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
998 : {
999 5269025 : gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
1000 5269025 : add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
1001 5269025 : }
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 562657 : combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
1008 : {
1009 562657 : rtx prob_note;
1010 562657 : rtx *pnote;
1011 562657 : rtx note;
1012 562657 : int best_probability = PROB_EVEN;
1013 562657 : enum br_predictor best_predictor = END_PREDICTORS;
1014 562657 : int combined_probability = REG_BR_PROB_BASE / 2;
1015 562657 : int d;
1016 562657 : bool first_match = false;
1017 562657 : bool found = false;
1018 :
1019 562657 : if (!can_predict_insn_p (insn))
1020 : {
1021 395386 : set_even_probabilities (bb);
1022 395386 : return;
1023 : }
1024 :
1025 167271 : prob_note = find_reg_note (insn, REG_BR_PROB, 0);
1026 167271 : pnote = ®_NOTES (insn);
1027 167271 : 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 253943 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1034 86672 : if (REG_NOTE_KIND (note) == REG_BR_PRED)
1035 : {
1036 86672 : enum br_predictor predictor = ((enum br_predictor)
1037 86672 : INTVAL (XEXP (XEXP (note, 0), 0)));
1038 86672 : int probability = INTVAL (XEXP (XEXP (note, 0), 1));
1039 :
1040 86672 : found = true;
1041 86672 : if (best_predictor > predictor
1042 86672 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1043 86672 : best_probability = probability, best_predictor = predictor;
1044 :
1045 86672 : d = (combined_probability * probability
1046 86672 : + (REG_BR_PROB_BASE - combined_probability)
1047 86672 : * (REG_BR_PROB_BASE - probability));
1048 :
1049 : /* Use int64_t math to avoid overflows of 32bit integers. */
1050 86672 : 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 86672 : combined_probability = ((((int64_t) combined_probability)
1055 86672 : * probability
1056 86672 : * 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 167271 : if (best_predictor != END_PREDICTORS)
1064 236 : first_match = true;
1065 :
1066 167271 : if (!found)
1067 80599 : dump_prediction (dump_file, PRED_NO_PREDICTION,
1068 : combined_probability, bb);
1069 : else
1070 : {
1071 86672 : if (!first_match)
1072 86436 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
1073 : bb, !first_match ? REASON_NONE : REASON_IGNORED);
1074 : else
1075 236 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
1076 : bb, first_match ? REASON_NONE : REASON_IGNORED);
1077 : }
1078 :
1079 167271 : if (first_match)
1080 236 : combined_probability = best_probability;
1081 167271 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1082 :
1083 421214 : while (*pnote)
1084 : {
1085 86672 : if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1086 : {
1087 86672 : enum br_predictor predictor = ((enum br_predictor)
1088 86672 : INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1089 86672 : int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1090 :
1091 86672 : dump_prediction (dump_file, predictor, probability, bb,
1092 86672 : (!first_match || best_predictor == predictor)
1093 86672 : ? REASON_NONE : REASON_IGNORED);
1094 86672 : *pnote = XEXP (*pnote, 1);
1095 : }
1096 : else
1097 0 : pnote = &XEXP (*pnote, 1);
1098 : }
1099 :
1100 167271 : if (!prob_note)
1101 : {
1102 167271 : profile_probability p
1103 167271 : = profile_probability::from_reg_br_prob_base (combined_probability);
1104 167271 : 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 167271 : if (!single_succ_p (bb))
1109 : {
1110 167271 : BRANCH_EDGE (bb)->probability = p;
1111 167271 : FALLTHRU_EDGE (bb)->probability
1112 334542 : = 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 12774874 : predictor_hash::hash (const edge_prediction *p)
1141 : {
1142 12774874 : inchash::hash hstate;
1143 12774874 : hstate.add_int (p->ep_predictor);
1144 :
1145 12774874 : int prob = p->ep_probability;
1146 12774874 : if (prob > REG_BR_PROB_BASE / 2)
1147 1645186 : prob = REG_BR_PROB_BASE - prob;
1148 :
1149 12774874 : hstate.add_int (prob);
1150 :
1151 12774874 : 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 2929090 : predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1159 : {
1160 2929090 : return (p1->ep_predictor == p2->ep_predictor
1161 2929090 : && (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 5023193 : not_removed_prediction_p (edge_prediction *p, void *data)
1172 : {
1173 5023193 : hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1174 5023193 : 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 3312494 : prune_predictions_for_bb (basic_block bb)
1189 : {
1190 3312494 : edge_prediction **preds = bb_predictions->get (bb);
1191 :
1192 3312494 : if (preds)
1193 : {
1194 2845796 : hash_table <predictor_hash_traits> s (13);
1195 2845796 : hash_set <edge_prediction *> remove;
1196 :
1197 : /* Step 1: identify predictors that should be removed. */
1198 7868989 : for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1199 : {
1200 5023193 : edge_prediction *existing = s.find (pred);
1201 5023193 : if (existing)
1202 : {
1203 256558 : 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 256558 : else if (pred->ep_edge != existing->ep_edge
1214 256558 : && pred->ep_probability == existing->ep_probability
1215 256558 : && pred->ep_probability != REG_BR_PROB_BASE / 2)
1216 : {
1217 : /* Remove both predictors as they predict the same
1218 : for both edges. */
1219 254156 : dump_prediction (dump_file, existing->ep_predictor,
1220 : pred->ep_probability, bb,
1221 : REASON_EDGE_PAIR_DUPLICATE,
1222 : existing->ep_edge);
1223 254156 : dump_prediction (dump_file, pred->ep_predictor,
1224 : pred->ep_probability, bb,
1225 : REASON_EDGE_PAIR_DUPLICATE,
1226 : pred->ep_edge);
1227 :
1228 254156 : remove.add (existing);
1229 254156 : remove.add (pred);
1230 : }
1231 : }
1232 :
1233 5023193 : edge_prediction **slot2 = s.find_slot (pred, INSERT);
1234 5023193 : *slot2 = pred;
1235 : }
1236 :
1237 : /* Step 2: Remove predictors. */
1238 2845796 : filter_predictions (preds, not_removed_prediction_p, &remove);
1239 2845796 : }
1240 3312494 : }
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 11421731 : combine_predictions_for_bb (basic_block bb, bool dry_run)
1248 : {
1249 11421731 : int best_probability = PROB_EVEN;
1250 11421731 : enum br_predictor best_predictor = END_PREDICTORS;
1251 11421731 : int combined_probability = REG_BR_PROB_BASE / 2;
1252 11421731 : int d;
1253 11421731 : bool first_match = false;
1254 11421731 : bool found = false;
1255 11421731 : struct edge_prediction *pred;
1256 11421731 : int nedges = 0;
1257 11421731 : edge e, first = NULL, second = NULL;
1258 11421731 : edge_iterator ei;
1259 11421731 : int nzero = 0;
1260 11421731 : int nunknown = 0;
1261 :
1262 27391423 : FOR_EACH_EDGE (e, ei, bb->succs)
1263 : {
1264 15969692 : if (!unlikely_executed_edge_p (e))
1265 : {
1266 13636137 : nedges ++;
1267 13636137 : if (first && !second)
1268 : second = e;
1269 10299766 : if (!first)
1270 10205705 : first = e;
1271 : }
1272 2333555 : else if (!e->probability.initialized_p ())
1273 26057 : e->probability = profile_probability::never ();
1274 15969692 : if (!e->probability.initialized_p ())
1275 6129907 : nunknown++;
1276 9839785 : else if (e->probability == profile_probability::never ())
1277 2212768 : 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 11421731 : if (nedges != 2)
1294 : {
1295 8109237 : hash_set<edge> unlikely_edges (4);
1296 8109237 : 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 8109237 : edge_prediction **preds = bb_predictions->get (bb);
1302 8109237 : if (preds)
1303 1864138 : for (pred = *preds; pred; pred = pred->ep_next)
1304 : {
1305 1136010 : if (pred->ep_probability <= PROB_VERY_UNLIKELY
1306 1127392 : || pred->ep_predictor == PRED_COLD_LABEL)
1307 8683 : unlikely_edges.add (pred->ep_edge);
1308 1127327 : else if (pred->ep_probability >= PROB_VERY_LIKELY
1309 1126698 : || pred->ep_predictor == PRED_BUILTIN_EXPECT
1310 1123547 : || pred->ep_predictor == PRED_HOT_LABEL)
1311 3783 : likely_edges.add (pred);
1312 : }
1313 :
1314 : /* It can happen that an edge is both in likely_edges and unlikely_edges.
1315 : Clear both sets in that situation. */
1316 8113019 : for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
1317 8116801 : it != likely_edges.end (); ++it)
1318 3783 : if (unlikely_edges.contains ((*it)->ep_edge))
1319 : {
1320 1 : likely_edges.empty ();
1321 8109238 : unlikely_edges.empty ();
1322 : break;
1323 : }
1324 :
1325 8109237 : if (!dry_run)
1326 8109181 : set_even_probabilities (bb, &unlikely_edges, &likely_edges);
1327 8109237 : clear_bb_predictions (bb);
1328 8109237 : 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 8109237 : return;
1347 8109237 : }
1348 :
1349 3312494 : if (dump_file)
1350 583 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1351 :
1352 3312494 : prune_predictions_for_bb (bb);
1353 :
1354 3312494 : edge_prediction **preds = bb_predictions->get (bb);
1355 :
1356 3312494 : if (preds)
1357 : {
1358 : /* We implement "first match" heuristics and use probability guessed
1359 : by predictor with smallest index. */
1360 7360734 : for (pred = *preds; pred; pred = pred->ep_next)
1361 : {
1362 4514938 : enum br_predictor predictor = pred->ep_predictor;
1363 4514938 : int probability = pred->ep_probability;
1364 :
1365 4514938 : if (pred->ep_edge != first)
1366 1193587 : probability = REG_BR_PROB_BASE - probability;
1367 :
1368 4514938 : found = true;
1369 : /* First match heuristics would be widly confused if we predicted
1370 : both directions. */
1371 4514938 : if (best_predictor > predictor
1372 4327644 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1373 : {
1374 : struct edge_prediction *pred2;
1375 : int prob = probability;
1376 :
1377 2859358 : for (pred2 = (struct edge_prediction *) *preds;
1378 4217703 : pred2; pred2 = pred2->ep_next)
1379 2859358 : 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 2859358 : prob = probability2;
1394 : }
1395 1358345 : if (!pred2)
1396 4514938 : best_probability = prob, best_predictor = predictor;
1397 : }
1398 :
1399 4514938 : d = (combined_probability * probability
1400 4514938 : + (REG_BR_PROB_BASE - combined_probability)
1401 4514938 : * (REG_BR_PROB_BASE - probability));
1402 :
1403 : /* Use int64_t math to avoid overflows of 32bit integers. */
1404 4514938 : 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 4514938 : combined_probability = ((((int64_t) combined_probability)
1409 4514938 : * probability
1410 4514938 : * 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 2845796 : if (best_predictor != END_PREDICTORS)
1419 1261925 : first_match = true;
1420 :
1421 3312494 : if (!found)
1422 536061 : dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1423 : else
1424 : {
1425 2776433 : if (!first_match)
1426 1514508 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1427 : !first_match ? REASON_NONE : REASON_IGNORED);
1428 : else
1429 1261925 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1430 : first_match ? REASON_NONE : REASON_IGNORED);
1431 : }
1432 :
1433 3312494 : if (first_match)
1434 1261925 : combined_probability = best_probability;
1435 3312494 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1436 :
1437 3312494 : if (preds)
1438 : {
1439 7360734 : for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1440 : {
1441 4514938 : enum br_predictor predictor = pred->ep_predictor;
1442 4514938 : int probability = pred->ep_probability;
1443 :
1444 4514938 : dump_prediction (dump_file, predictor, probability, bb,
1445 4514938 : (!first_match || best_predictor == predictor)
1446 4514938 : ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1447 : }
1448 : }
1449 3312494 : clear_bb_predictions (bb);
1450 :
1451 :
1452 : /* If we have only one successor which is unknown, we can compute missing
1453 : probability. */
1454 3312494 : if (nunknown == 1)
1455 : {
1456 1233 : profile_probability prob = profile_probability::always ();
1457 1233 : edge missing = NULL;
1458 :
1459 3699 : FOR_EACH_EDGE (e, ei, bb->succs)
1460 2466 : if (e->probability.initialized_p ())
1461 1233 : prob -= e->probability;
1462 1233 : else if (missing == NULL)
1463 : missing = e;
1464 : else
1465 0 : gcc_unreachable ();
1466 1233 : missing->probability = prob;
1467 : }
1468 : /* If nothing is unknown, we have nothing to update. */
1469 3682524 : else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1470 : ;
1471 2939998 : else if (!dry_run)
1472 : {
1473 2939998 : first->probability
1474 2939998 : = profile_probability::from_reg_br_prob_base (combined_probability);
1475 2939998 : 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 9344 : strips_small_constant (tree t1, tree t2)
1489 : {
1490 9344 : tree ret = NULL;
1491 9344 : int value = 0;
1492 :
1493 9344 : if (!t1)
1494 : return NULL;
1495 9344 : else if (TREE_CODE (t1) == SSA_NAME)
1496 : ret = t1;
1497 1092 : else if (tree_fits_shwi_p (t1))
1498 93 : value = tree_to_shwi (t1);
1499 : else
1500 : return NULL;
1501 :
1502 8345 : if (!t2)
1503 : return ret;
1504 8345 : else if (tree_fits_shwi_p (t2))
1505 7796 : value = tree_to_shwi (t2);
1506 549 : else if (TREE_CODE (t2) == SSA_NAME)
1507 : {
1508 370 : if (ret)
1509 : return NULL;
1510 : else
1511 : ret = t2;
1512 : }
1513 :
1514 8068 : 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 235011 : get_base_value (tree t)
1525 : {
1526 235011 : if (TREE_CODE (t) == SSA_NAME)
1527 : return t;
1528 :
1529 11588 : if (!BINARY_CLASS_P (t))
1530 : return NULL;
1531 :
1532 9344 : switch (TREE_OPERAND_LENGTH (t))
1533 : {
1534 0 : case 1:
1535 0 : return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1536 9344 : case 2:
1537 9344 : return strips_small_constant (TREE_OPERAND (t, 0),
1538 18688 : 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 863023 : 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 863023 : tree op0, op1, bound, base;
1557 863023 : affine_iv iv0, iv1;
1558 863023 : enum tree_code code;
1559 863023 : tree step;
1560 :
1561 863023 : code = gimple_cond_code (stmt);
1562 863023 : *loop_invariant = NULL;
1563 :
1564 863023 : switch (code)
1565 : {
1566 862149 : case GT_EXPR:
1567 862149 : case GE_EXPR:
1568 862149 : case NE_EXPR:
1569 862149 : case LT_EXPR:
1570 862149 : case LE_EXPR:
1571 862149 : case EQ_EXPR:
1572 862149 : break;
1573 :
1574 : default:
1575 : return false;
1576 : }
1577 :
1578 862149 : op0 = gimple_cond_lhs (stmt);
1579 862149 : op1 = gimple_cond_rhs (stmt);
1580 :
1581 862149 : if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1582 862130 : || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1583 : return false;
1584 1696880 : if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1585 : return false;
1586 1003862 : if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1587 : return false;
1588 482604 : if (TREE_CODE (iv0.step) != INTEGER_CST
1589 479823 : || TREE_CODE (iv1.step) != INTEGER_CST)
1590 : return false;
1591 545500 : if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1592 531791 : || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1593 13907 : return false;
1594 :
1595 459359 : if (integer_zerop (iv0.step))
1596 : {
1597 58525 : if (code != NE_EXPR && code != EQ_EXPR)
1598 42839 : code = invert_tree_comparison (code, false);
1599 58525 : bound = iv0.base;
1600 58525 : base = iv1.base;
1601 58525 : if (tree_fits_shwi_p (iv1.step))
1602 : step = iv1.step;
1603 : else
1604 : return false;
1605 : }
1606 : else
1607 : {
1608 400834 : bound = iv1.base;
1609 400834 : base = iv0.base;
1610 400834 : if (tree_fits_shwi_p (iv0.step))
1611 : step = iv0.step;
1612 : else
1613 : return false;
1614 : }
1615 :
1616 452618 : if (TREE_CODE (bound) != INTEGER_CST)
1617 159223 : bound = get_base_value (bound);
1618 159223 : if (!bound)
1619 : return false;
1620 450871 : if (TREE_CODE (base) != INTEGER_CST)
1621 75788 : base = get_base_value (base);
1622 75788 : if (!base)
1623 : return false;
1624 :
1625 448469 : *loop_invariant = bound;
1626 448469 : *compare_code = code;
1627 448469 : *loop_step = step;
1628 448469 : *loop_iv_base = base;
1629 448469 : return true;
1630 : }
1631 :
1632 : /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1633 :
1634 : static bool
1635 6944 : expr_coherent_p (tree t1, tree t2)
1636 : {
1637 6944 : gimple *stmt;
1638 6944 : tree ssa_name_1 = NULL;
1639 6944 : tree ssa_name_2 = NULL;
1640 :
1641 6944 : gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1642 6944 : gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1643 :
1644 6944 : if (t1 == t2)
1645 : return true;
1646 :
1647 2972 : if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1648 : return true;
1649 1742 : if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1650 : return false;
1651 :
1652 : /* Check to see if t1 is expressed/defined with t2. */
1653 318 : stmt = SSA_NAME_DEF_STMT (t1);
1654 318 : gcc_assert (stmt != NULL);
1655 318 : if (is_gimple_assign (stmt))
1656 : {
1657 194 : ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1658 194 : if (ssa_name_1 && ssa_name_1 == t2)
1659 : return true;
1660 : }
1661 :
1662 : /* Check to see if t2 is expressed/defined with t1. */
1663 318 : stmt = SSA_NAME_DEF_STMT (t2);
1664 318 : gcc_assert (stmt != NULL);
1665 318 : if (is_gimple_assign (stmt))
1666 : {
1667 194 : ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1668 194 : if (ssa_name_2 && ssa_name_2 == t1)
1669 : return true;
1670 : }
1671 :
1672 : /* Compare if t1 and t2's def_stmts are identical. */
1673 318 : if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1674 : return true;
1675 : else
1676 : return false;
1677 : }
1678 :
1679 : /* Return true if E is predicted by one of loop heuristics. */
1680 :
1681 : static bool
1682 6073597 : predicted_by_loop_heuristics_p (basic_block bb)
1683 : {
1684 6073597 : struct edge_prediction *i;
1685 6073597 : edge_prediction **preds = bb_predictions->get (bb);
1686 :
1687 6073597 : if (!preds)
1688 : return false;
1689 :
1690 2122155 : for (i = *preds; i; i = i->ep_next)
1691 1807946 : if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1692 1807946 : || 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 2021655 : 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 2021655 : tree compare_var, compare_base;
1723 2021655 : enum tree_code compare_code;
1724 2021655 : tree compare_step_var;
1725 2021655 : edge then_edge;
1726 2021655 : edge_iterator ei;
1727 :
1728 2021655 : if (predicted_by_loop_heuristics_p (bb))
1729 2020058 : return;
1730 :
1731 4303747 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1732 257257 : if (!stmt)
1733 : return;
1734 257257 : 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 11243 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
1743 11243 : 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 11146 : if (compare_code == NE_EXPR)
1749 : {
1750 1663 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1751 1663 : return;
1752 : }
1753 9483 : else if (compare_code == EQ_EXPR)
1754 : {
1755 4801 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1756 4801 : return;
1757 : }
1758 :
1759 4682 : if (!expr_coherent_p (loop_iv_base_var, compare_base))
1760 : return;
1761 :
1762 : /* If loop bound, base and compare bound are all constants, we can
1763 : calculate the probability directly. */
1764 4107 : if (tree_fits_shwi_p (loop_bound_var)
1765 2711 : && tree_fits_shwi_p (compare_var)
1766 2574 : && tree_fits_shwi_p (compare_base))
1767 : {
1768 2510 : int probability;
1769 2510 : wi::overflow_type overflow;
1770 2510 : bool overall_overflow = false;
1771 2510 : widest_int compare_count, tem;
1772 :
1773 : /* (loop_bound - base) / compare_step */
1774 2510 : tem = wi::sub (wi::to_widest (loop_bound_var),
1775 5020 : wi::to_widest (compare_base), SIGNED, &overflow);
1776 2510 : overall_overflow |= overflow;
1777 2510 : widest_int loop_count = wi::div_trunc (tem,
1778 2510 : wi::to_widest (compare_step_var),
1779 2510 : SIGNED, &overflow);
1780 2510 : overall_overflow |= overflow;
1781 :
1782 2510 : if (!wi::neg_p (wi::to_widest (compare_step_var))
1783 2510 : ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1784 : {
1785 : /* (loop_bound - compare_bound) / compare_step */
1786 359 : tem = wi::sub (wi::to_widest (loop_bound_var),
1787 718 : wi::to_widest (compare_var), SIGNED, &overflow);
1788 359 : overall_overflow |= overflow;
1789 359 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1790 359 : SIGNED, &overflow);
1791 359 : overall_overflow |= overflow;
1792 : }
1793 : else
1794 : {
1795 : /* (compare_bound - base) / compare_step */
1796 2151 : tem = wi::sub (wi::to_widest (compare_var),
1797 4302 : wi::to_widest (compare_base), SIGNED, &overflow);
1798 2151 : overall_overflow |= overflow;
1799 2151 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1800 2151 : SIGNED, &overflow);
1801 2151 : overall_overflow |= overflow;
1802 : }
1803 2510 : if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1804 2134 : ++compare_count;
1805 2510 : if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1806 175 : ++loop_count;
1807 2510 : if (wi::neg_p (compare_count))
1808 766 : compare_count = 0;
1809 2510 : if (wi::neg_p (loop_count))
1810 801 : loop_count = 0;
1811 2510 : if (loop_count == 0)
1812 : probability = 0;
1813 1694 : else if (wi::cmps (compare_count, loop_count) == 1)
1814 : probability = REG_BR_PROB_BASE;
1815 : else
1816 : {
1817 1650 : tem = compare_count * REG_BR_PROB_BASE;
1818 1650 : tem = wi::udiv_trunc (tem, loop_count);
1819 1650 : probability = tem.to_uhwi ();
1820 : }
1821 :
1822 : /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1823 2510 : if (!overall_overflow)
1824 2510 : predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1825 :
1826 2510 : return;
1827 2510 : }
1828 :
1829 1597 : if (expr_coherent_p (loop_bound_var, compare_var))
1830 : {
1831 932 : if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1832 809 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1833 801 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1834 131 : else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1835 113 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1836 98 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1837 33 : else if (loop_bound_code == NE_EXPR)
1838 : {
1839 : /* If the loop backedge condition is "(i != bound)", we do
1840 : the comparison based on the step of IV:
1841 : * step < 0 : backedge condition is like (i > bound)
1842 : * step > 0 : backedge condition is like (i < bound) */
1843 8 : gcc_assert (loop_bound_step != 0);
1844 8 : if (loop_bound_step > 0
1845 8 : && (compare_code == LT_EXPR
1846 8 : || compare_code == LE_EXPR))
1847 7 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1848 1 : else if (loop_bound_step < 0
1849 0 : && (compare_code == GT_EXPR
1850 0 : || compare_code == GE_EXPR))
1851 0 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1852 : else
1853 1 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1854 : }
1855 : else
1856 : /* The branch is predicted not-taken if loop_bound_code is
1857 : opposite with compare_code. */
1858 25 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1859 : }
1860 665 : else if (expr_coherent_p (loop_iv_base_var, compare_var))
1861 : {
1862 : /* For cases like:
1863 : for (i = s; i < h; i++)
1864 : if (i > s + 2) ....
1865 : The branch should be predicted taken. */
1866 163 : if (loop_bound_step > 0
1867 153 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1868 62 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1869 101 : else if (loop_bound_step < 0
1870 10 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1871 10 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1872 : else
1873 91 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1874 : }
1875 : }
1876 :
1877 : /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1878 : exits are resulted from short-circuit conditions that will generate an
1879 : if_tmp. E.g.:
1880 :
1881 : if (foo() || global > 10)
1882 : break;
1883 :
1884 : This will be translated into:
1885 :
1886 : BB3:
1887 : loop header...
1888 : BB4:
1889 : if foo() goto BB6 else goto BB5
1890 : BB5:
1891 : if global > 10 goto BB6 else goto BB7
1892 : BB6:
1893 : goto BB7
1894 : BB7:
1895 : iftmp = (PHI 0(BB5), 1(BB6))
1896 : if iftmp == 1 goto BB8 else goto BB3
1897 : BB8:
1898 : outside of the loop...
1899 :
1900 : The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1901 : From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1902 : exits. This function takes BB7->BB8 as input, and finds out the extra loop
1903 : exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1904 :
1905 : static void
1906 831377 : predict_extra_loop_exits (class loop *loop, edge exit_edge)
1907 : {
1908 831377 : unsigned i;
1909 831377 : bool check_value_one;
1910 831377 : gimple *lhs_def_stmt;
1911 831377 : gphi *phi_stmt;
1912 831377 : tree cmp_rhs, cmp_lhs;
1913 :
1914 1662754 : gcond *cmp_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1915 817984 : if (!cmp_stmt)
1916 : return;
1917 :
1918 817984 : cmp_rhs = gimple_cond_rhs (cmp_stmt);
1919 817984 : cmp_lhs = gimple_cond_lhs (cmp_stmt);
1920 817984 : if (!TREE_CONSTANT (cmp_rhs)
1921 817984 : || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1922 603062 : return;
1923 214922 : 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 214922 : check_value_one = (((integer_onep (cmp_rhs))
1930 214922 : ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1931 214922 : ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1932 :
1933 214922 : lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1934 214922 : if (!lhs_def_stmt)
1935 : return;
1936 :
1937 214922 : phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1938 : if (!phi_stmt)
1939 : return;
1940 :
1941 222597 : for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1942 : {
1943 149900 : edge e1;
1944 149900 : edge_iterator ei;
1945 149900 : tree val = gimple_phi_arg_def (phi_stmt, i);
1946 149900 : edge e = gimple_phi_arg_edge (phi_stmt, i);
1947 :
1948 149900 : if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1949 135476 : continue;
1950 39879 : if ((check_value_one ^ integer_onep (val)) == 1)
1951 19727 : continue;
1952 20152 : if (EDGE_COUNT (e->src->succs) != 1)
1953 : {
1954 5728 : predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1955 : loop);
1956 5728 : continue;
1957 : }
1958 :
1959 31422 : FOR_EACH_EDGE (e1, ei, e->src->preds)
1960 16998 : 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 272555 : predict_loops (void)
1970 : {
1971 272555 : basic_block bb;
1972 272555 : hash_set <class loop *> with_recursion(10);
1973 :
1974 5508483 : FOR_EACH_BB_FN (bb, cfun)
1975 : {
1976 5235928 : gimple_stmt_iterator gsi;
1977 5235928 : tree decl;
1978 :
1979 34882520 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1980 24410664 : if (is_gimple_call (gsi_stmt (gsi))
1981 2233229 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1982 26459406 : && recursive_call_p (current_function_decl, decl))
1983 : {
1984 5812 : class loop *loop = bb->loop_father;
1985 11915 : while (loop && !with_recursion.add (loop))
1986 6103 : 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 1463240 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1993 : {
1994 645575 : basic_block bb, *bbs;
1995 645575 : unsigned j, n_exits = 0;
1996 645575 : class tree_niter_desc niter_desc;
1997 645575 : edge ex;
1998 645575 : class nb_iter_bound *nb_iter;
1999 645575 : enum tree_code loop_bound_code = ERROR_MARK;
2000 645575 : tree loop_bound_step = NULL;
2001 645575 : tree loop_bound_var = NULL;
2002 645575 : tree loop_iv_base = NULL;
2003 645575 : gcond *stmt = NULL;
2004 645575 : bool recursion = with_recursion.contains (loop);
2005 :
2006 645575 : auto_vec<edge> exits = get_loop_exit_edges (loop);
2007 2325084 : FOR_EACH_VEC_ELT (exits, j, ex)
2008 1033934 : if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
2009 878404 : n_exits ++;
2010 645575 : if (!n_exits)
2011 15995 : continue;
2012 :
2013 629580 : 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 629851 : && 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 629851 : && 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 1647342 : FOR_EACH_VEC_ELT (exits, j, ex)
2031 : {
2032 1017762 : tree niter = NULL;
2033 1017762 : HOST_WIDE_INT nitercst;
2034 1017762 : int max = param_max_predicted_iterations;
2035 1017762 : int probability;
2036 1017762 : enum br_predictor predictor;
2037 1017762 : widest_int nit;
2038 :
2039 1017762 : if (unlikely_executed_edge_p (ex)
2040 1017762 : || (ex->flags & EDGE_ABNORMAL_CALL))
2041 139358 : continue;
2042 : /* Loop heuristics do not expect exit conditional to be inside
2043 : inner loop. We predict from innermost to outermost loop. */
2044 878404 : if (predicted_by_loop_heuristics_p (ex->src))
2045 : {
2046 47027 : 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 47027 : continue;
2051 : }
2052 831377 : predict_extra_loop_exits (loop, ex);
2053 :
2054 831377 : if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
2055 437479 : niter = niter_desc.niter;
2056 437479 : if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
2057 557219 : niter = loop_niter_by_eval (loop, ex);
2058 336 : if (dump_file && (dump_flags & TDF_DETAILS)
2059 831648 : && 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 831377 : if (TREE_CODE (niter) == INTEGER_CST)
2069 : {
2070 286909 : if (tree_fits_uhwi_p (niter)
2071 286909 : && max
2072 573812 : && compare_tree_int (niter, max - 1) == -1)
2073 204128 : nitercst = tree_to_uhwi (niter) + 1;
2074 : else
2075 82781 : 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 544468 : else if (n_exits == 1
2082 544468 : && 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 1083342 : else if (n_exits == 1
2094 254171 : && likely_max_stmt_executions (loop, &nit)
2095 688559 : && wi::ltu_p (nit,
2096 287798 : 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 5576 : nitercst = nit.to_shwi ();
2104 5576 : predictor = PRED_LOOP_ITERATIONS_MAX;
2105 : }
2106 : else
2107 : {
2108 538883 : 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 538883 : continue;
2112 : }
2113 :
2114 292494 : 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 292494 : if (nitercst == 0)
2120 6 : continue;
2121 :
2122 292488 : probability = RDIV (REG_BR_PROB_BASE, nitercst);
2123 292488 : predict_edge (ex, predictor, probability);
2124 1017762 : }
2125 :
2126 : /* Find information about loop bound variables. */
2127 888468 : for (nb_iter = loop->bounds; nb_iter;
2128 258888 : nb_iter = nb_iter->next)
2129 388406 : if (nb_iter->stmt
2130 388406 : && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2131 : {
2132 129518 : stmt = as_a <gcond *> (nb_iter->stmt);
2133 129518 : break;
2134 : }
2135 629580 : if (!stmt)
2136 1000124 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (loop->header));
2137 129518 : if (stmt)
2138 605766 : 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 629580 : bbs = get_loop_body (loop);
2145 :
2146 3811428 : for (j = 0; j < loop->num_nodes; j++)
2147 : {
2148 3181848 : edge e;
2149 3181848 : edge_iterator ei;
2150 :
2151 3181848 : 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 3181848 : if (predicted_by_p (bb, PRED_CONTINUE))
2158 : {
2159 8310 : if (dump_file && (dump_flags & TDF_DETAILS))
2160 0 : fprintf (dump_file, "BB %i predicted by continue.\n",
2161 : bb->index);
2162 8310 : continue;
2163 : }
2164 :
2165 : /* If we already used more reliable loop exit predictors, do not
2166 : bother with PRED_LOOP_EXIT. */
2167 3173538 : 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 5155142 : int probability = ((REG_BR_PROB_BASE
2184 2577571 : - predictor_info
2185 : [recursion
2186 2577571 : ? PRED_LOOP_EXIT_WITH_RECURSION
2187 2577571 : : PRED_LOOP_EXIT].hitrate)
2188 2577571 : / n_exits);
2189 2577571 : if (probability < HITRATE (2))
2190 : probability = HITRATE (2);
2191 6260096 : FOR_EACH_EDGE (e, ei, bb->succs)
2192 3682525 : if (e->dest->index < NUM_FIXED_BLOCKS
2193 3682525 : || !flow_bb_inside_loop_p (loop, e->dest))
2194 : {
2195 659192 : 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 1311607 : predict_edge (e,
2200 : recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2201 : : PRED_LOOP_EXIT, probability);
2202 : }
2203 : }
2204 3173538 : if (loop_bound_var)
2205 2021655 : predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2206 : loop_bound_code,
2207 2021655 : 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 629580 : if (loop_outer (loop)->num)
2217 : {
2218 134297 : basic_block bb = NULL;
2219 134297 : edge preheader_edge = loop_preheader_edge (loop);
2220 :
2221 134297 : if (single_pred_p (preheader_edge->src)
2222 246355 : && single_succ_p (preheader_edge->src))
2223 112058 : 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 134297 : gcond *stmt
2238 268594 : = safe_dyn_cast <gcond *> (*gsi_last_bb (preheader_edge->src));
2239 109604 : if (stmt
2240 109604 : && gimple_cond_code (stmt) == NE_EXPR
2241 35538 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2242 35538 : && integer_zerop (gimple_cond_rhs (stmt)))
2243 : {
2244 14961 : gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2245 14961 : if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2246 6338 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt))
2247 15817 : && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2248 856 : call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2249 14961 : 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 15791 : && 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 134275 : if (!dominated_by_p (CDI_DOMINATORS,
2259 134275 : loop_outer (loop)->latch, loop->header))
2260 56387 : 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 629580 : free (bbs);
2282 918130 : }
2283 272555 : }
2284 :
2285 : /* Attempt to predict probabilities of BB outgoing edges using local
2286 : properties. */
2287 : static void
2288 562657 : bb_estimate_probability_locally (basic_block bb)
2289 : {
2290 562657 : rtx_insn *last_insn = BB_END (bb);
2291 562657 : rtx cond;
2292 :
2293 562657 : if (! can_predict_insn_p (last_insn))
2294 : return;
2295 167271 : cond = get_condition (last_insn, NULL, false, false);
2296 167271 : 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 144431 : if (COMPARISON_P (cond)
2303 144431 : && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2304 142926 : || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2305 : {
2306 1506 : if (GET_CODE (cond) == EQ)
2307 33 : predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2308 1473 : 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 142925 : 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 21169 : case EQ:
2326 21169 : 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 21169 : 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 21169 : else if (XEXP (cond, 1) == const0_rtx
2335 578 : || XEXP (cond, 0) == const0_rtx)
2336 : ;
2337 : else
2338 578 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2339 : break;
2340 :
2341 83591 : case NE:
2342 83591 : 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 83591 : 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 83591 : else if (XEXP (cond, 1) == const0_rtx
2351 78305 : || XEXP (cond, 0) == const0_rtx)
2352 : ;
2353 : else
2354 78305 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2355 : break;
2356 :
2357 0 : case ORDERED:
2358 0 : predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2359 0 : break;
2360 :
2361 52 : case UNORDERED:
2362 52 : predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2363 52 : break;
2364 :
2365 5201 : case LE:
2366 5201 : case LT:
2367 5201 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2368 0 : || XEXP (cond, 1) == constm1_rtx)
2369 5201 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2370 : break;
2371 :
2372 5556 : case GE:
2373 5556 : case GT:
2374 5556 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2375 5489 : || XEXP (cond, 1) == constm1_rtx)
2376 2248 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2377 : break;
2378 :
2379 : default:
2380 : break;
2381 : }
2382 : }
2383 :
2384 : /* Set edge->probability for each successor edge of BB. */
2385 : void
2386 562657 : guess_outgoing_edge_probabilities (basic_block bb)
2387 : {
2388 562657 : bb_estimate_probability_locally (bb);
2389 562657 : combine_predictions_for_insn (BB_END (bb), bb);
2390 562657 : }
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 16065081 : 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 16065081 : gimple *def;
2403 :
2404 : /* Reset returned probability value. */
2405 16065081 : *probability = -1;
2406 16065081 : *predictor = PRED_UNCONDITIONAL;
2407 :
2408 16065081 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2409 : {
2410 10245283 : if (TREE_CONSTANT (op0))
2411 : return op0;
2412 :
2413 10241763 : if (code == IMAGPART_EXPR)
2414 : {
2415 51407 : if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2416 : {
2417 49798 : def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2418 49798 : if (is_gimple_call (def)
2419 47660 : && gimple_call_internal_p (def)
2420 97402 : && (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 10236173 : if (code != SSA_NAME)
2432 : return NULL_TREE;
2433 :
2434 8001172 : def = SSA_NAME_DEF_STMT (op0);
2435 :
2436 : /* If we were already here, break the infinite cycle. */
2437 8001172 : bool existed_p;
2438 8001172 : expected_value *res
2439 8001172 : = &ssa_expected_value->get_or_insert (SSA_NAME_VERSION (op0),
2440 : &existed_p);
2441 8001172 : if (existed_p)
2442 : {
2443 1672342 : *probability = res->probability;
2444 1672342 : *predictor = res->predictor;
2445 1672342 : return res->val;
2446 : }
2447 6328830 : res->val = NULL_TREE;
2448 6328830 : res->predictor = *predictor;
2449 6328830 : res->probability = *probability;
2450 :
2451 6328830 : if (gphi *phi = dyn_cast <gphi *> (def))
2452 : {
2453 : /* All the arguments of the PHI node must have the same constant
2454 : length. */
2455 910653 : int i, n = gimple_phi_num_args (phi);
2456 910653 : tree val = NULL;
2457 910653 : 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 1828746 : for (i = 0; i < n && !has_nonzero_edge; i++)
2462 : {
2463 918093 : tree arg = PHI_ARG_DEF (phi, i);
2464 918093 : if (arg == PHI_RESULT (phi))
2465 0 : continue;
2466 918093 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2467 929134 : if (!cnt.initialized_p () || cnt.nonzero_p ())
2468 : has_nonzero_edge = true;
2469 : }
2470 :
2471 1488972 : for (i = 0; i < n; i++)
2472 : {
2473 1485964 : tree arg = PHI_ARG_DEF (phi, i);
2474 1485964 : enum br_predictor predictor2;
2475 :
2476 : /* Skip self-referring parameters, since they does not change
2477 : expected value. */
2478 1485964 : if (arg == PHI_RESULT (phi))
2479 578312 : continue;
2480 :
2481 : /* Skip edges which we already predicted as executing
2482 : zero times. */
2483 1485964 : if (has_nonzero_edge)
2484 : {
2485 1481265 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2486 1481265 : if (cnt.initialized_p () && !cnt.nonzero_p ())
2487 219 : continue;
2488 : }
2489 1485745 : HOST_WIDE_INT probability2;
2490 1485745 : tree new_val = expr_expected_value (arg, &predictor2,
2491 : &probability2);
2492 : /* If we know nothing about value, give up. */
2493 1485745 : if (!new_val)
2494 907645 : return NULL;
2495 :
2496 : /* If this is a first edge, trust its prediction. */
2497 645937 : if (!val)
2498 : {
2499 569632 : val = new_val;
2500 569632 : *predictor = predictor2;
2501 569632 : *probability = probability2;
2502 569632 : continue;
2503 : }
2504 : /* If there are two different values, give up. */
2505 76305 : if (!operand_equal_p (val, new_val, false))
2506 : return NULL;
2507 :
2508 8468 : int p1 = get_predictor_value (*predictor, *probability);
2509 8468 : 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 8468 : if (*predictor == predictor2 && p1 == p2)
2513 8461 : continue;
2514 : /* The general case has no precise solution, since we do not
2515 : know probabilities of incomming edges, yet.
2516 : Still if value is predicted over all incomming edges, we
2517 : can hope it will be indeed the case. Conservatively
2518 : downgrade prediction quality (so first match merging is not
2519 : performed) and take least successful prediction. */
2520 :
2521 7 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI;
2522 7 : *probability = MIN (p1, p2);
2523 : }
2524 :
2525 3008 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2526 3008 : res->val = val;
2527 3008 : res->predictor = *predictor;
2528 3008 : res->probability = *probability;
2529 3008 : return val;
2530 : }
2531 5418177 : if (is_gimple_assign (def))
2532 : {
2533 4147641 : if (gimple_assign_lhs (def) != op0)
2534 : return NULL;
2535 :
2536 4147641 : 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 4147641 : if (val)
2542 : {
2543 49255 : res = ssa_expected_value->get (SSA_NAME_VERSION (op0));
2544 49255 : res->val = val;
2545 49255 : res->predictor = *predictor;
2546 49255 : res->probability = *probability;
2547 : }
2548 4147641 : return val;
2549 : }
2550 :
2551 1270536 : if (is_gimple_call (def))
2552 : {
2553 875318 : tree decl = gimple_call_fndecl (def);
2554 875318 : if (!decl)
2555 : {
2556 78849 : if (gimple_call_internal_p (def)
2557 78849 : && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2558 : {
2559 33031 : gcc_assert (gimple_call_num_args (def) == 3);
2560 33031 : tree val = gimple_call_arg (def, 0);
2561 33031 : if (TREE_CONSTANT (val))
2562 : return val;
2563 33031 : tree val2 = gimple_call_arg (def, 2);
2564 33031 : gcc_assert (TREE_CODE (val2) == INTEGER_CST
2565 : && tree_fits_uhwi_p (val2)
2566 : && tree_to_uhwi (val2) < END_PREDICTORS);
2567 33031 : *predictor = (enum br_predictor) tree_to_uhwi (val2);
2568 33031 : if (*predictor == PRED_BUILTIN_EXPECT)
2569 8748 : *probability
2570 8748 : = HITRATE (param_builtin_expect_probability);
2571 33031 : val = gimple_call_arg (def, 1);
2572 33031 : res->val = val;
2573 33031 : res->predictor = *predictor;
2574 33031 : res->probability = *probability;
2575 33031 : return val;
2576 : }
2577 : return NULL;
2578 : }
2579 :
2580 796469 : if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2581 : {
2582 12032 : if (predictor)
2583 12032 : *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 12032 : tree val = fold_convert (type, boolean_true_node);
2589 12032 : res->val = val;
2590 12032 : res->predictor = *predictor;
2591 12032 : res->probability = *probability;
2592 12032 : return val;
2593 : }
2594 :
2595 784437 : if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2596 429294 : switch (DECL_FUNCTION_CODE (decl))
2597 : {
2598 80686 : case BUILT_IN_EXPECT:
2599 80686 : {
2600 80686 : tree val;
2601 80686 : if (gimple_call_num_args (def) != 2)
2602 : return NULL;
2603 80686 : val = gimple_call_arg (def, 0);
2604 80686 : if (TREE_CONSTANT (val))
2605 : return val;
2606 80686 : *predictor = PRED_BUILTIN_EXPECT;
2607 80686 : *probability
2608 80686 : = HITRATE (param_builtin_expect_probability);
2609 80686 : val = gimple_call_arg (def, 1);
2610 80686 : res->val = val;
2611 80686 : res->predictor = *predictor;
2612 80686 : res->probability = *probability;
2613 80686 : return val;
2614 : }
2615 19 : case BUILT_IN_EXPECT_WITH_PROBABILITY:
2616 19 : {
2617 19 : tree val;
2618 19 : if (gimple_call_num_args (def) != 3)
2619 : return NULL;
2620 19 : val = gimple_call_arg (def, 0);
2621 19 : if (TREE_CONSTANT (val))
2622 : {
2623 0 : res->val = val;
2624 0 : res->predictor = *predictor;
2625 0 : res->probability = *probability;
2626 0 : return val;
2627 : }
2628 : /* Compute final probability as:
2629 : probability * REG_BR_PROB_BASE. */
2630 19 : tree prob = gimple_call_arg (def, 2);
2631 19 : tree t = TREE_TYPE (prob);
2632 19 : tree base = build_int_cst (integer_type_node,
2633 : REG_BR_PROB_BASE);
2634 19 : base = build_real_from_int_cst (t, base);
2635 19 : tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2636 : MULT_EXPR, t, prob, base);
2637 19 : if (TREE_CODE (r) != REAL_CST)
2638 : {
2639 1 : error_at (gimple_location (def),
2640 : "probability %qE must be "
2641 : "constant floating-point expression", prob);
2642 1 : return NULL;
2643 : }
2644 18 : HOST_WIDE_INT probi
2645 18 : = real_to_integer (TREE_REAL_CST_PTR (r));
2646 18 : if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2647 : {
2648 17 : *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2649 17 : *probability = probi;
2650 : }
2651 : else
2652 1 : error_at (gimple_location (def),
2653 : "probability %qE is outside "
2654 : "the range [0.0, 1.0]", prob);
2655 :
2656 18 : val = gimple_call_arg (def, 1);
2657 18 : res->val = val;
2658 18 : res->predictor = *predictor;
2659 18 : res->probability = *probability;
2660 18 : return val;
2661 : }
2662 :
2663 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2664 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2665 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2666 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2667 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2668 5172 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2669 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2670 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2671 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2672 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2673 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2674 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2675 5172 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2676 : /* Assume that any given atomic operation has low contention,
2677 : and thus the compare-and-swap operation succeeds. */
2678 5172 : *predictor = PRED_COMPARE_AND_SWAP;
2679 5172 : res->val = boolean_true_node;
2680 5172 : res->predictor = *predictor;
2681 5172 : res->probability = *probability;
2682 5172 : return boolean_true_node;
2683 1946 : case BUILT_IN_REALLOC:
2684 1946 : case BUILT_IN_GOMP_REALLOC:
2685 1946 : if (predictor)
2686 1946 : *predictor = PRED_MALLOC_NONNULL;
2687 : /* FIXME: This is wrong and we need to convert the logic
2688 : to value ranges. */
2689 1946 : res->val = fold_convert (type, boolean_true_node);
2690 1946 : res->predictor = *predictor;
2691 1946 : res->probability = *probability;
2692 1946 : return res->val;
2693 : default:
2694 : break;
2695 : }
2696 : }
2697 :
2698 1091832 : return NULL;
2699 : }
2700 :
2701 5819798 : if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2702 : {
2703 5405484 : tree res;
2704 5405484 : tree nop0 = op0;
2705 5405484 : 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 5405484 : if (TREE_CODE (op0) != INTEGER_CST)
2711 : {
2712 : /* See if expected value of op0 is good enough to determine the result. */
2713 5381472 : nop0 = expr_expected_value (op0, predictor, probability);
2714 5381472 : if (nop0
2715 147653 : && (res = fold_build2 (code, type, nop0, op1)) != NULL
2716 5529125 : && 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 5239632 : if (!nop0)
2725 5257831 : nop0 = op0;
2726 : }
2727 5263644 : enum br_predictor predictor2 = PRED_UNCONDITIONAL;
2728 5263644 : HOST_WIDE_INT probability2 = -1;
2729 5263644 : if (TREE_CODE (op1) != INTEGER_CST)
2730 : {
2731 : /* See if expected value of op1 is good enough to determine the result. */
2732 1608150 : nop1 = expr_expected_value (op1, &predictor2, &probability2);
2733 1608150 : if (nop1
2734 226515 : && (res = fold_build2 (code, type, op0, nop1)) != NULL
2735 1834665 : && 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 1608093 : if (!nop1)
2743 5037129 : 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 5263587 : 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 414314 : if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2785 : {
2786 413202 : tree res;
2787 413202 : op0 = expr_expected_value (op0, predictor, probability);
2788 413202 : if (!op0)
2789 : return NULL;
2790 37919 : res = fold_build1 (code, type, op0);
2791 37919 : 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 8916380 : expr_expected_value (tree expr, enum br_predictor *predictor,
2808 : HOST_WIDE_INT *probability)
2809 : {
2810 8916380 : enum tree_code code;
2811 8916380 : tree op0, op1;
2812 :
2813 8916380 : if (TREE_CONSTANT (expr))
2814 : {
2815 869545 : *predictor = PRED_UNCONDITIONAL;
2816 869545 : *probability = -1;
2817 869545 : return expr;
2818 : }
2819 :
2820 8046835 : extract_ops_from_tree (expr, &code, &op0, &op1);
2821 8046835 : return expr_expected_value_1 (TREE_TYPE (expr),
2822 8046835 : 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 157133 : get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2831 : {
2832 157133 : switch (predictor)
2833 : {
2834 89778 : case PRED_BUILTIN_EXPECT:
2835 89778 : case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2836 89778 : case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
2837 89778 : case PRED_COMBINED_VALUE_PREDICTIONS:
2838 89778 : gcc_assert (probability != -1);
2839 : return probability;
2840 67355 : default:
2841 67355 : gcc_assert (probability == -1);
2842 67355 : return predictor_info[(int) predictor].hitrate;
2843 : }
2844 : }
2845 :
2846 : /* Predict using opcode of the last statement in basic block. */
2847 : static void
2848 11421731 : tree_predict_by_opcode (basic_block bb)
2849 : {
2850 11421731 : edge then_edge;
2851 11421731 : tree op0, op1;
2852 11421731 : tree type;
2853 11421731 : tree val;
2854 11421731 : enum tree_code cmp;
2855 11421731 : edge_iterator ei;
2856 11421731 : enum br_predictor predictor;
2857 11421731 : HOST_WIDE_INT probability;
2858 :
2859 11421731 : gimple *stmt = *gsi_last_bb (bb);
2860 11421731 : if (!stmt)
2861 7551126 : return;
2862 :
2863 10952590 : if (gswitch *sw = dyn_cast <gswitch *> (stmt))
2864 : {
2865 27811 : tree index = gimple_switch_index (sw);
2866 27811 : tree val = expr_expected_value (index, &predictor, &probability);
2867 27811 : 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 10952590 : if (gimple_code (stmt) != GIMPLE_COND)
2883 : return;
2884 4001918 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
2885 4001918 : if (then_edge->flags & EDGE_TRUE_VALUE)
2886 : break;
2887 3870605 : op0 = gimple_cond_lhs (stmt);
2888 3870605 : op1 = gimple_cond_rhs (stmt);
2889 3870605 : cmp = gimple_cond_code (stmt);
2890 3870605 : type = TREE_TYPE (op0);
2891 3870605 : val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1,
2892 : &predictor, &probability);
2893 3870605 : if (val && TREE_CODE (val) == INTEGER_CST)
2894 : {
2895 139875 : HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2896 139875 : if (integer_zerop (val))
2897 114269 : prob = REG_BR_PROB_BASE - prob;
2898 139875 : 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 3870605 : if (POINTER_TYPE_P (type))
2904 : {
2905 561840 : if (cmp == EQ_EXPR)
2906 227424 : predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2907 334416 : else if (cmp == NE_EXPR)
2908 315166 : 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 3308765 : switch (cmp)
2917 : {
2918 893620 : case EQ_EXPR:
2919 893620 : 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 893620 : 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 881122 : else if (integer_zerop (op0) || integer_zerop (op1))
2928 : ;
2929 : else
2930 351901 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2931 : break;
2932 :
2933 1578512 : case NE_EXPR:
2934 1578512 : 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 1578512 : 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 1462759 : else if (integer_zerop (op0)
2943 1462759 : || integer_zerop (op1))
2944 : ;
2945 : else
2946 530611 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2947 : break;
2948 :
2949 2305 : case ORDERED_EXPR:
2950 2305 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2951 2305 : break;
2952 :
2953 2586 : case UNORDERED_EXPR:
2954 2586 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2955 2586 : break;
2956 :
2957 344733 : case LE_EXPR:
2958 344733 : case LT_EXPR:
2959 344733 : if (integer_zerop (op1)
2960 283030 : || integer_onep (op1)
2961 275911 : || integer_all_onesp (op1)
2962 275856 : || real_zerop (op1)
2963 272695 : || real_onep (op1)
2964 616923 : || real_minus_onep (op1))
2965 72547 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2966 : break;
2967 :
2968 478859 : case GE_EXPR:
2969 478859 : case GT_EXPR:
2970 478859 : if (integer_zerop (op1)
2971 415227 : || integer_onep (op1)
2972 403646 : || integer_all_onesp (op1)
2973 403372 : || real_zerop (op1)
2974 401821 : || real_onep (op1)
2975 879943 : || real_minus_onep (op1))
2976 77799 : 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 829177 : is_exit_with_zero_arg (const gimple *stmt)
2988 : {
2989 : /* This is not exit, _exit or _Exit. */
2990 829177 : if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2991 825345 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2992 1654500 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2993 : return false;
2994 :
2995 : /* Argument is an interger zero. */
2996 3854 : 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 704529 : return_prediction (tree val, enum prediction *prediction)
3003 : {
3004 : /* VOID. */
3005 704529 : if (!val)
3006 : return PRED_NO_PREDICTION;
3007 : /* Different heuristics for pointers and scalars. */
3008 704529 : if (POINTER_TYPE_P (TREE_TYPE (val)))
3009 : {
3010 : /* NULL is usually not returned. */
3011 142498 : if (integer_zerop (val))
3012 : {
3013 31562 : *prediction = NOT_TAKEN;
3014 31562 : return PRED_NULL_RETURN;
3015 : }
3016 : }
3017 562031 : else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
3018 : {
3019 : /* Negative return values are often used to indicate
3020 : errors. */
3021 460116 : if (TREE_CODE (val) == INTEGER_CST
3022 460116 : && tree_int_cst_sgn (val) < 0)
3023 : {
3024 12912 : *prediction = NOT_TAKEN;
3025 12912 : 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 447204 : if (TREE_CONSTANT (val)
3031 447204 : && (!integer_zerop (val) && !integer_onep (val)))
3032 : {
3033 74600 : *prediction = NOT_TAKEN;
3034 74600 : 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 62644 : zero_one_minusone (gphi *phi, int limit)
3046 : {
3047 62644 : int phi_num_args = gimple_phi_num_args (phi);
3048 62644 : int ret = 0;
3049 209566 : for (int i = 0; i < phi_num_args; i++)
3050 : {
3051 157445 : tree t = PHI_ARG_DEF (phi, i);
3052 157445 : if (TREE_CODE (t) != INTEGER_CST)
3053 71454 : continue;
3054 85991 : wide_int w = wi::to_wide (t);
3055 85991 : if (w == -1)
3056 5295 : ret |= 1;
3057 80696 : else if (w == 0)
3058 40281 : ret |= 2;
3059 40415 : else if (w == 1)
3060 29892 : ret |= 4;
3061 : else
3062 10523 : return 0;
3063 85991 : }
3064 119776 : for (int i = 0; i < phi_num_args; i++)
3065 : {
3066 103013 : tree t = PHI_ARG_DEF (phi, i);
3067 103013 : if (TREE_CODE (t) == INTEGER_CST)
3068 65962 : continue;
3069 37051 : if (TREE_CODE (t) != SSA_NAME)
3070 : return 0;
3071 37051 : gimple *g = SSA_NAME_DEF_STMT (t);
3072 37051 : if (gimple_code (g) == GIMPLE_PHI && limit > 0)
3073 12318 : if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
3074 : {
3075 421 : ret |= r;
3076 421 : continue;
3077 : }
3078 36630 : if (!is_gimple_assign (g))
3079 : return 0;
3080 13489 : if (gimple_assign_cast_p (g))
3081 : {
3082 3503 : tree rhs1 = gimple_assign_rhs1 (g);
3083 3503 : if (TREE_CODE (rhs1) != SSA_NAME
3084 3503 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
3085 3425 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
3086 4776 : || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3087 : return 0;
3088 1272 : ret |= (2 | 4);
3089 1272 : continue;
3090 1272 : }
3091 9986 : 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 2403075 : apply_return_prediction (void)
3102 : {
3103 2403075 : greturn *return_stmt = NULL;
3104 2403075 : tree return_val;
3105 2403075 : edge e;
3106 2403075 : gphi *phi;
3107 2403075 : int phi_num_args, i;
3108 2403075 : enum br_predictor pred;
3109 2403075 : enum prediction direction;
3110 2403075 : edge_iterator ei;
3111 :
3112 2466253 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3113 : {
3114 4936602 : if (greturn *last = safe_dyn_cast <greturn *> (*gsi_last_bb (e->src)))
3115 : {
3116 : return_stmt = last;
3117 : break;
3118 : }
3119 : }
3120 2403075 : if (!e)
3121 2223926 : return;
3122 2373904 : return_val = gimple_return_retval (return_stmt);
3123 2373904 : if (!return_val)
3124 : return;
3125 1337871 : if (TREE_CODE (return_val) != SSA_NAME
3126 983315 : || !SSA_NAME_DEF_STMT (return_val)
3127 2321186 : || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
3128 : return;
3129 179753 : phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
3130 179753 : phi_num_args = gimple_phi_num_args (phi);
3131 179753 : 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 357950 : if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
3140 127003 : && !TYPE_UNSIGNED (TREE_TYPE (return_val))
3141 230079 : && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
3142 50326 : if (int r = zero_one_minusone (phi, 3))
3143 16342 : 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 576826 : for (i = 1; i < phi_num_args; i++)
3150 429035 : if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
3151 : break;
3152 179149 : if (i != phi_num_args)
3153 127099 : for (i = 0; i < phi_num_args; i++)
3154 : {
3155 95741 : pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
3156 95741 : if (pred != PRED_NO_PREDICTION)
3157 50034 : 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 2403075 : tree_bb_level_predictions (void)
3168 : {
3169 2403075 : basic_block bb;
3170 2403075 : bool has_return_edges = false;
3171 2403075 : edge e;
3172 2403075 : edge_iterator ei;
3173 :
3174 2472415 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3175 2441993 : if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3176 : {
3177 : has_return_edges = true;
3178 : break;
3179 : }
3180 :
3181 2403075 : apply_return_prediction ();
3182 :
3183 13685930 : FOR_EACH_BB_FN (bb, cfun)
3184 : {
3185 11282855 : gimple_stmt_iterator gsi;
3186 :
3187 89732576 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3188 : {
3189 67166866 : gimple *stmt = gsi_stmt (gsi);
3190 67166866 : tree decl;
3191 :
3192 67166866 : if (is_gimple_call (stmt))
3193 : {
3194 6095562 : if (gimple_call_noreturn_p (stmt)
3195 893305 : && has_return_edges
3196 6924739 : && !is_exit_with_zero_arg (stmt))
3197 826643 : predict_paths_leading_to (bb, PRED_NORETURN,
3198 : NOT_TAKEN);
3199 6095562 : decl = gimple_call_fndecl (stmt);
3200 6095562 : if (decl
3201 11813305 : && lookup_attribute ("cold",
3202 5717743 : DECL_ATTRIBUTES (decl)))
3203 516667 : predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3204 : NOT_TAKEN);
3205 6095562 : if (decl && recursive_call_p (current_function_decl, decl))
3206 9626 : predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3207 : NOT_TAKEN);
3208 : }
3209 61071304 : else if (gimple_code (stmt) == GIMPLE_PREDICT)
3210 : {
3211 459004 : 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 2403075 : }
3219 :
3220 : /* Callback for hash_map::traverse, asserts that the pointer map is
3221 : empty. */
3222 :
3223 : bool
3224 3573900 : assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3225 : void *)
3226 : {
3227 3573900 : gcc_assert (!value);
3228 3573900 : 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 11421731 : tree_estimate_probability_bb (basic_block bb, bool local_only)
3236 : {
3237 11421731 : edge e;
3238 11421731 : edge_iterator ei;
3239 :
3240 27391423 : 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 12639034 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3245 12639018 : && !local_only
3246 12470927 : && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3247 24250831 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3248 : {
3249 6435772 : 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 36702316 : for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
3256 23830772 : gsi_next (&bi))
3257 : {
3258 26246333 : gimple *stmt = gsi_stmt (bi);
3259 26246333 : if (is_gimple_call (stmt)
3260 3035920 : && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
3261 : /* Constant and pure calls are hardly used to signalize
3262 : something exceptional. */
3263 29012750 : && gimple_has_side_effects (stmt))
3264 : {
3265 2415561 : if (gimple_call_fndecl (stmt))
3266 2352808 : predict_edge_def (e, PRED_CALL, NOT_TAKEN);
3267 62753 : else if (virtual_method_call_p (gimple_call_fn (stmt)))
3268 13391 : predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
3269 : else
3270 49362 : predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
3271 : break;
3272 : }
3273 : }
3274 : }
3275 : }
3276 11421731 : tree_predict_by_opcode (bb);
3277 11421731 : }
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 2403075 : tree_estimate_probability (bool dry_run)
3286 : {
3287 2403075 : basic_block bb;
3288 :
3289 2403075 : connect_infinite_loops_to_exit ();
3290 : /* We use loop_niter_by_eval, which requires that the loops have
3291 : preheaders. */
3292 2403075 : create_preheaders (CP_SIMPLE_PREHEADERS);
3293 2403075 : calculate_dominance_info (CDI_POST_DOMINATORS);
3294 : /* Decide which edges are known to be unlikely. This improves later
3295 : branch prediction. */
3296 2403075 : if (!dry_run)
3297 2403063 : determine_unlikely_bbs ();
3298 :
3299 2403075 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3300 2403075 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3301 :
3302 2403075 : tree_bb_level_predictions ();
3303 2403075 : record_loop_exits ();
3304 :
3305 4806150 : if (number_of_loops (cfun) > 1)
3306 272555 : predict_loops ();
3307 :
3308 13685930 : FOR_EACH_BB_FN (bb, cfun)
3309 11282855 : tree_estimate_probability_bb (bb, false);
3310 :
3311 13685930 : FOR_EACH_BB_FN (bb, cfun)
3312 11282855 : combine_predictions_for_bb (bb, dry_run);
3313 :
3314 2403075 : if (flag_checking)
3315 5976947 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3316 :
3317 4806150 : delete bb_predictions;
3318 2403075 : bb_predictions = NULL;
3319 4806150 : delete ssa_expected_value;
3320 2403075 : ssa_expected_value = NULL;
3321 :
3322 2403075 : if (!dry_run
3323 2403063 : && profile_status_for_fn (cfun) != PROFILE_READ)
3324 2403063 : estimate_bb_frequencies ();
3325 2403075 : free_dominance_info (CDI_POST_DOMINATORS);
3326 2403075 : remove_fake_exit_edges ();
3327 2403075 : }
3328 :
3329 : /* Set edge->probability for each successor edge of BB. */
3330 : void
3331 138876 : tree_guess_outgoing_edge_probabilities (basic_block bb)
3332 : {
3333 138876 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3334 138876 : ssa_expected_value = new hash_map<int_hash<unsigned, 0>, expected_value>;
3335 138876 : tree_estimate_probability_bb (bb, true);
3336 138876 : combine_predictions_for_bb (bb, false);
3337 138876 : if (flag_checking)
3338 138876 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3339 277752 : delete bb_predictions;
3340 138876 : bb_predictions = NULL;
3341 277752 : delete ssa_expected_value;
3342 138876 : ssa_expected_value = NULL;
3343 138876 : }
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 1066077 : maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3359 : {
3360 1066077 : if (edge_predicted_by_p (e, pred, taken))
3361 : return;
3362 1061683 : if (pred == PRED_LOOP_GUARD
3363 1061683 : && 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 1061675 : 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 1061675 : 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 2365975 : 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 2365975 : edge e;
3384 2365975 : edge_iterator ei;
3385 2365975 : basic_block son;
3386 :
3387 : /* If we exited the loop or CUR is unconditional in the loop, there is
3388 : nothing to do. */
3389 2365975 : if (in_loop
3390 2365975 : && (!flow_bb_inside_loop_p (in_loop, cur)
3391 72827 : || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3392 10963 : return;
3393 :
3394 : /* We are looking for all edges forming edge cut induced by
3395 : set of all blocks postdominated by BB. */
3396 5239109 : FOR_EACH_EDGE (e, ei, cur->preds)
3397 2884097 : if (e->src->index >= NUM_FIXED_BLOCKS
3398 2884097 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3399 : {
3400 2227500 : edge e2;
3401 2227500 : edge_iterator ei2;
3402 2227500 : bool found = false;
3403 :
3404 : /* Ignore fake edges and eh, we predict them as not taken anyway. */
3405 2227500 : if (unlikely_executed_edge_p (e))
3406 1164864 : continue;
3407 1062636 : 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 1936930 : FOR_EACH_EDGE (e2, ei2, e->src->succs)
3412 1907961 : if (e2 != e
3413 1069436 : && !unlikely_executed_edge_p (e2)
3414 1042526 : && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3415 2944311 : && (!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 1062636 : if (found)
3429 1033667 : maybe_predict_edge (e, pred, taken);
3430 28969 : else if (bitmap_set_bit (visited, e->src->index))
3431 28925 : predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3432 : }
3433 2355012 : for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3434 2811571 : son;
3435 456559 : son = next_dom_son (CDI_POST_DOMINATORS, son))
3436 456559 : 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 1811940 : predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3444 : enum prediction taken, class loop *in_loop)
3445 : {
3446 1811940 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3447 1811940 : }
3448 :
3449 : /* Like predict_paths_leading_to but take edge instead of basic block. */
3450 :
3451 : static void
3452 100961 : predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3453 : enum prediction taken, class loop *in_loop)
3454 : {
3455 100961 : bool has_nonloop_edge = false;
3456 100961 : edge_iterator ei;
3457 100961 : edge e2;
3458 :
3459 100961 : basic_block bb = e->src;
3460 190056 : FOR_EACH_EDGE (e2, ei, bb->succs)
3461 121505 : if (e2->dest != e->src && e2->dest != e->dest
3462 43975 : && !unlikely_executed_edge_p (e2)
3463 162924 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3464 : {
3465 : has_nonloop_edge = true;
3466 : break;
3467 : }
3468 :
3469 100961 : if (!has_nonloop_edge)
3470 68551 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3471 : else
3472 32410 : maybe_predict_edge (e, pred, taken);
3473 100961 : }
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 3255541 : propagate_freq (basic_block head, bitmap tovisit,
3513 : sreal max_cyclic_prob)
3514 : {
3515 3255541 : basic_block bb;
3516 3255541 : basic_block last;
3517 3255541 : unsigned i;
3518 3255541 : edge e;
3519 3255541 : basic_block nextbb;
3520 3255541 : 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 26631222 : EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3525 : {
3526 23375681 : edge_iterator ei;
3527 23375681 : int count = 0;
3528 :
3529 23375681 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
3530 :
3531 52124773 : FOR_EACH_EDGE (e, ei, bb->preds)
3532 : {
3533 28749092 : bool visit = bitmap_bit_p (tovisit, e->src->index);
3534 :
3535 28749092 : if (visit && !(e->flags & EDGE_DFS_BACK))
3536 26064946 : count++;
3537 1892478 : 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 23375681 : BLOCK_INFO (bb)->npredecessors = count;
3543 : /* When function never returns, we will never process exit block. */
3544 23375681 : if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3545 0 : bb->count = profile_count::zero ();
3546 : }
3547 :
3548 3255541 : BLOCK_INFO (head)->frequency = 1;
3549 3255541 : last = head;
3550 26631222 : for (bb = head; bb; bb = nextbb)
3551 : {
3552 23375681 : edge_iterator ei;
3553 23375681 : sreal cyclic_probability = 0;
3554 23375681 : sreal frequency = 0;
3555 :
3556 23375681 : nextbb = BLOCK_INFO (bb)->next;
3557 23375681 : BLOCK_INFO (bb)->next = NULL;
3558 :
3559 : /* Compute frequency of basic block. */
3560 23375681 : if (bb != head)
3561 : {
3562 20120140 : if (flag_checking)
3563 47285208 : FOR_EACH_EDGE (e, ei, bb->preds)
3564 27165457 : gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3565 : || (e->flags & EDGE_DFS_BACK));
3566 :
3567 47286158 : FOR_EACH_EDGE (e, ei, bb->preds)
3568 27166018 : if (EDGE_INFO (e)->back_edge)
3569 1096019 : cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3570 26069999 : 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 26064946 : sreal tmp = e->probability.initialized_p () ?
3575 26064946 : e->probability.to_sreal () : 0;
3576 26064946 : frequency += tmp * BLOCK_INFO (e->src)->frequency;
3577 : }
3578 :
3579 20120140 : if (cyclic_probability == 0)
3580 : {
3581 19051279 : BLOCK_INFO (bb)->frequency = frequency;
3582 : }
3583 : else
3584 : {
3585 1068861 : if (cyclic_probability > max_cyclic_prob)
3586 : {
3587 9772 : 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 9772 : cyclic_probability = max_cyclic_prob;
3596 : }
3597 1059089 : 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 1068861 : BLOCK_INFO (bb)->frequency = frequency
3604 1068861 : / (sreal (1) - cyclic_probability);
3605 1068861 : if (dump_file)
3606 363 : fprintf (dump_file, " to %f\n",
3607 363 : BLOCK_INFO (bb)->frequency.to_double ());
3608 : }
3609 : }
3610 :
3611 23375681 : bitmap_clear_bit (tovisit, bb->index);
3612 :
3613 23375681 : e = find_edge (bb, head);
3614 23375681 : if (e)
3615 : {
3616 : /* FIXME: Graphite is producing edges with no profile. Once
3617 : this is fixed, drop this. */
3618 791406 : sreal tmp = e->probability.initialized_p () ?
3619 791406 : e->probability.to_sreal () : 0;
3620 791406 : EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3621 : }
3622 :
3623 : /* Propagate to successor blocks. */
3624 52682084 : FOR_EACH_EDGE (e, ei, bb->succs)
3625 29306403 : if (!(e->flags & EDGE_DFS_BACK)
3626 27412700 : && BLOCK_INFO (e->dest)->npredecessors)
3627 : {
3628 26064946 : BLOCK_INFO (e->dest)->npredecessors--;
3629 26064946 : if (!BLOCK_INFO (e->dest)->npredecessors)
3630 : {
3631 20120140 : if (!nextbb)
3632 : nextbb = e->dest;
3633 : else
3634 7588141 : BLOCK_INFO (last)->next = e->dest;
3635 :
3636 : last = e->dest;
3637 : }
3638 : }
3639 : }
3640 3255541 : }
3641 :
3642 : /* Estimate frequencies in loops at same nest level. */
3643 :
3644 : static void
3645 1099463 : estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3646 : {
3647 1099463 : class loop *loop;
3648 :
3649 1890869 : for (loop = first_loop; loop; loop = loop->next)
3650 : {
3651 791406 : edge e;
3652 791406 : basic_block *bbs;
3653 791406 : unsigned i;
3654 791406 : auto_bitmap tovisit;
3655 :
3656 791406 : estimate_loops_at_level (loop->inner, max_cyclic_prob);
3657 :
3658 : /* Find current loop back edge and mark it. */
3659 791406 : e = loop_latch_edge (loop);
3660 791406 : EDGE_INFO (e)->back_edge = 1;
3661 :
3662 791406 : bbs = get_loop_body (loop);
3663 5905286 : for (i = 0; i < loop->num_nodes; i++)
3664 4322474 : bitmap_set_bit (tovisit, bbs[i]->index);
3665 791406 : free (bbs);
3666 791406 : propagate_freq (loop->header, tovisit, max_cyclic_prob);
3667 791406 : }
3668 1099463 : }
3669 :
3670 : /* Propagates frequencies through structure of loops. */
3671 :
3672 : static void
3673 2464135 : estimate_loops (void)
3674 : {
3675 2464135 : auto_bitmap tovisit;
3676 2464135 : basic_block bb;
3677 7392405 : sreal max_cyclic_prob = (sreal)1
3678 2464135 : - (sreal)1 / (param_max_predicted_iterations + 1);
3679 :
3680 : /* Start by estimating the frequencies in the loops. */
3681 4928270 : if (number_of_loops (cfun) > 1)
3682 308057 : estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3683 :
3684 : /* Now propagate the frequencies through all the blocks. */
3685 21517342 : FOR_ALL_BB_FN (bb, cfun)
3686 : {
3687 19053207 : bitmap_set_bit (tovisit, bb->index);
3688 : }
3689 2464135 : propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3690 2464135 : }
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 605 : handle_missing_profiles (void)
3778 : {
3779 605 : const int unlikely_frac = param_unlikely_bb_count_fraction;
3780 605 : struct cgraph_node *node;
3781 605 : 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 3394 : FOR_EACH_DEFINED_FUNCTION (node)
3786 : {
3787 2789 : struct cgraph_edge *e;
3788 2789 : profile_count call_count = profile_count::zero ();
3789 2789 : gcov_type max_tp_first_run = 0;
3790 2789 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3791 :
3792 2789 : if (node->count.ipa ().nonzero_p ())
3793 346 : continue;
3794 4665 : for (e = node->callers; e; e = e->next_caller)
3795 2222 : 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 2222 : 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 2443 : if (!node->tp_first_run && max_tp_first_run)
3806 4 : node->tp_first_run = max_tp_first_run + 1;
3807 :
3808 2443 : if (call_count > 0
3809 6 : && fn && fn->cfg
3810 2449 : && 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 605 : 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 605 : }
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 1714103 : update_max_bb_count (void)
3848 : {
3849 1714103 : profile_count true_count_max = profile_count::uninitialized ();
3850 1714103 : basic_block bb;
3851 :
3852 36081969 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3853 34367866 : true_count_max = profile_count::max_prefer_initialized (true_count_max, bb->count);
3854 :
3855 1714103 : cfun->cfg->count_max = true_count_max;
3856 :
3857 1714103 : 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 285435 : expensive_function_p (int threshold)
3867 : {
3868 285435 : 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 449161 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3873 : return true;
3874 :
3875 244463 : profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3876 244463 : profile_count sum = profile_count::zero ();
3877 3090985 : FOR_EACH_BB_FN (bb, cfun)
3878 : {
3879 3010248 : rtx_insn *insn;
3880 :
3881 3010248 : 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 45735703 : FOR_BB_INSNS (bb, insn)
3890 42889181 : if (active_insn_p (insn))
3891 : {
3892 17550836 : sum += bb->count;
3893 17550836 : 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 7197655 : propagate_unlikely_bbs_forward (void)
3906 : {
3907 7197655 : auto_vec<basic_block, 64> worklist;
3908 7197655 : basic_block bb;
3909 7197655 : edge_iterator ei;
3910 7197655 : edge e;
3911 :
3912 7214637 : if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3913 : {
3914 7180673 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3915 7180673 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3916 :
3917 78068269 : while (worklist.length () > 0)
3918 : {
3919 63706923 : bb = worklist.pop ();
3920 142272695 : FOR_EACH_EDGE (e, ei, bb->succs)
3921 80297812 : if (!(e->count () == profile_count::zero ())
3922 94861126 : && !(e->dest->count == profile_count::zero ())
3923 72153055 : && !e->dest->aux)
3924 : {
3925 56526250 : e->dest->aux = (void *)(size_t) 1;
3926 56526250 : worklist.safe_push (e->dest);
3927 : }
3928 : }
3929 : }
3930 :
3931 74766259 : FOR_ALL_BB_FN (bb, cfun)
3932 : {
3933 67568604 : if (!bb->aux)
3934 : {
3935 7722686 : if (!(bb->count == profile_count::zero ())
3936 388273 : && (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 3861681 : bb->count = profile_count::zero ();
3941 : }
3942 : else
3943 63706923 : bb->aux = NULL;
3944 : }
3945 7197655 : }
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 5893244 : determine_unlikely_bbs ()
3954 : {
3955 5893244 : basic_block bb;
3956 5893244 : auto_vec<basic_block, 64> worklist;
3957 5893244 : edge_iterator ei;
3958 5893244 : edge e;
3959 :
3960 40327196 : FOR_EACH_BB_FN (bb, cfun)
3961 : {
3962 68470697 : if (!(bb->count == profile_count::zero ())
3963 32552403 : && unlikely_executed_bb_p (bb))
3964 : {
3965 397207 : if (dump_file && (dump_flags & TDF_DETAILS))
3966 0 : fprintf (dump_file, "Basic block %i is locally unlikely\n",
3967 : bb->index);
3968 397207 : bb->count = profile_count::zero ();
3969 : }
3970 :
3971 82831328 : FOR_EACH_EDGE (e, ei, bb->succs)
3972 90592104 : if (!(e->probability == profile_probability::never ())
3973 48397376 : && unlikely_executed_edge_p (e))
3974 : {
3975 2019224 : 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 2019224 : e->probability = profile_probability::never ();
3979 : }
3980 :
3981 34433952 : gcc_checking_assert (!bb->aux);
3982 : }
3983 5893244 : propagate_unlikely_bbs_forward ();
3984 :
3985 5893244 : auto_vec<int, 64> nsuccs;
3986 5893244 : nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
3987 52113684 : FOR_ALL_BB_FN (bb, cfun)
3988 54665486 : if (!(bb->count == profile_count::zero ())
3989 43566093 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3990 : {
3991 37775394 : nsuccs[bb->index] = 0;
3992 89807600 : FOR_EACH_EDGE (e, ei, bb->succs)
3993 52032206 : if (!(e->probability == profile_probability::never ())
3994 100495957 : && !(e->dest->count == profile_count::zero ()))
3995 47395237 : nsuccs[bb->index]++;
3996 37775394 : if (!nsuccs[bb->index])
3997 1503055 : worklist.safe_push (bb);
3998 : }
3999 7418868 : while (worklist.length () > 0)
4000 : {
4001 1525624 : bb = worklist.pop ();
4002 1525624 : if (bb->count == profile_count::zero ())
4003 0 : continue;
4004 1525624 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4005 : {
4006 1516943 : bool found = false;
4007 3033886 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
4008 2590381 : !gsi_end_p (gsi); gsi_next (&gsi))
4009 2565127 : 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 2565127 : || (is_gimple_call (gsi_stmt (gsi))
4014 619051 : && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
4015 : {
4016 : found = true;
4017 : break;
4018 : }
4019 1516943 : if (found)
4020 1491689 : continue;
4021 : }
4022 33935 : 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 33935 : bb->count = profile_count::zero ();
4027 69994 : FOR_EACH_EDGE (e, ei, bb->preds)
4028 36059 : if (!(e->probability == profile_probability::never ()))
4029 : {
4030 35259 : if (!(e->src->count == profile_count::zero ()))
4031 : {
4032 35257 : gcc_checking_assert (nsuccs[e->src->index] > 0);
4033 35257 : nsuccs[e->src->index]--;
4034 35257 : if (!nsuccs[e->src->index])
4035 22569 : worklist.safe_push (e->src);
4036 : }
4037 : }
4038 : }
4039 : /* Finally all edges from non-0 regions to 0 are unlikely. */
4040 52113684 : FOR_ALL_BB_FN (bb, cfun)
4041 : {
4042 48908722 : if (!(bb->count == profile_count::zero ()))
4043 95516449 : FOR_EACH_EDGE (e, ei, bb->succs)
4044 51984291 : if (!(e->probability == profile_probability::never ())
4045 100385732 : && e->dest->count == profile_count::zero ())
4046 : {
4047 522728 : 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 522728 : e->probability = profile_probability::never ();
4052 : }
4053 :
4054 46220440 : edge other = NULL;
4055 :
4056 89359369 : FOR_EACH_EDGE (e, ei, bb->succs)
4057 53998397 : if (e->probability == profile_probability::never ())
4058 : ;
4059 47282349 : else if (other)
4060 : {
4061 : other = NULL;
4062 : break;
4063 : }
4064 : else
4065 : other = e;
4066 46220440 : if (other
4067 46220440 : && !(other->probability == profile_probability::always ()))
4068 : {
4069 8318638 : 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 8318638 : other->probability = profile_probability::always ();
4073 : }
4074 : }
4075 5893265 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
4076 22096 : cgraph_node::get (current_function_decl)->count = profile_count::zero ();
4077 5893244 : }
4078 :
4079 : /* Estimate and propagate basic block frequencies using the given branch
4080 : probabilities. */
4081 :
4082 : static void
4083 2464135 : estimate_bb_frequencies ()
4084 : {
4085 2464135 : basic_block bb;
4086 2464135 : sreal freq_max;
4087 :
4088 2464135 : determine_unlikely_bbs ();
4089 :
4090 2464135 : mark_dfs_back_edges ();
4091 :
4092 2464135 : 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 2464135 : alloc_aux_for_blocks (sizeof (block_info));
4097 2464135 : alloc_aux_for_edges (sizeof (edge_prob_info));
4098 21517342 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4099 : {
4100 19053207 : edge e;
4101 19053207 : edge_iterator ei;
4102 :
4103 41668146 : 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 22614939 : if (e->probability.initialized_p ())
4108 22614907 : EDGE_INFO (e)->back_edge_prob
4109 22614907 : = 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 2464135 : estimate_loops ();
4119 :
4120 2464135 : freq_max = 0;
4121 16589072 : FOR_EACH_BB_FN (bb, cfun)
4122 14124937 : if (freq_max < BLOCK_INFO (bb)->frequency)
4123 3120916 : 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 2464135 : freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
4130 2464135 : if (freq_max < 16)
4131 74 : freq_max = 16;
4132 2464135 : profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
4133 2464135 : cfun->cfg->count_max = profile_count::uninitialized ();
4134 21517342 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4135 : {
4136 19053207 : sreal tmp = BLOCK_INFO (bb)->frequency;
4137 19053207 : if (tmp >= 1)
4138 : {
4139 11131487 : gimple_stmt_iterator gsi;
4140 11131487 : 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 72035710 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4147 49778133 : if (is_gimple_call (gsi_stmt (gsi))
4148 2941813 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
4149 52418044 : && recursive_call_p (current_function_decl, decl))
4150 : {
4151 5397 : 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 5397 : tmp = (sreal)9 / (sreal)10;
4156 5397 : break;
4157 : }
4158 : }
4159 19053207 : tmp = tmp * freq_max;
4160 19053207 : 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 20285511 : if (!(bb->count == profile_count::zero ()))
4165 17820903 : bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
4166 19053207 : cfun->cfg->count_max
4167 19053207 : = profile_count::max_prefer_initialized (cfun->cfg->count_max,
4168 : bb->count);
4169 : }
4170 :
4171 2464135 : free_aux_for_blocks ();
4172 2464135 : free_aux_for_edges ();
4173 2464135 : compute_function_frequency ();
4174 2464135 : }
4175 :
4176 : /* Decide whether function is hot, cold or unlikely executed. */
4177 : void
4178 2494203 : compute_function_frequency (void)
4179 : {
4180 2494203 : basic_block bb;
4181 2494203 : struct cgraph_node *node = cgraph_node::get (current_function_decl);
4182 :
4183 2494203 : if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4184 2494203 : || MAIN_NAME_P (DECL_NAME (current_function_decl)))
4185 92220 : node->only_called_at_startup = true;
4186 2494203 : if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4187 1216 : node->only_called_at_exit = true;
4188 :
4189 2494203 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4190 : {
4191 2485083 : int flags = flags_from_decl_or_type (current_function_decl);
4192 2485083 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4193 : != NULL)
4194 613 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4195 2484470 : else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
4196 : != NULL)
4197 60 : node->frequency = NODE_FREQUENCY_HOT;
4198 2484410 : else if (flags & ECF_NORETURN)
4199 1979 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4200 2482431 : else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4201 78781 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4202 2403650 : else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4203 2403650 : || DECL_STATIC_DESTRUCTOR (current_function_decl))
4204 13857 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4205 2485083 : return;
4206 : }
4207 :
4208 9120 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4209 9120 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4210 : == NULL)
4211 9112 : warn_function_cold (current_function_decl);
4212 9120 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4213 8772 : return;
4214 931 : FOR_EACH_BB_FN (bb, cfun)
4215 : {
4216 819 : if (maybe_hot_bb_p (cfun, bb))
4217 : {
4218 236 : node->frequency = NODE_FREQUENCY_HOT;
4219 236 : return;
4220 : }
4221 583 : if (!probably_never_executed_bb_p (cfun, bb))
4222 529 : node->frequency = NODE_FREQUENCY_NORMAL;
4223 : }
4224 : }
4225 :
4226 : /* Build PREDICT_EXPR. */
4227 : tree
4228 1854094 : build_predict_expr (enum br_predictor predictor, enum prediction taken)
4229 : {
4230 1854094 : tree t = build1 (PREDICT_EXPR, void_type_node,
4231 1854094 : build_int_cst (integer_type_node, predictor));
4232 1854094 : SET_PREDICT_EXPR_OUTCOME (t, taken);
4233 1854094 : return t;
4234 : }
4235 :
4236 : const char *
4237 1241 : predictor_name (enum br_predictor predictor)
4238 : {
4239 1241 : 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 287872 : pass_profile (gcc::context *ctxt)
4263 575744 : : gimple_opt_pass (pass_data_profile, ctxt)
4264 : {}
4265 :
4266 : /* opt_pass methods: */
4267 2403979 : 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 2402949 : pass_profile::execute (function *fun)
4274 : {
4275 2402949 : unsigned nb_loops;
4276 :
4277 2402949 : if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4278 : return 0;
4279 :
4280 2402911 : loop_optimizer_init (LOOPS_NORMAL);
4281 2402911 : if (dump_file && (dump_flags & TDF_DETAILS))
4282 2 : flow_loops_dump (dump_file, NULL, 0);
4283 :
4284 2402911 : nb_loops = number_of_loops (fun);
4285 2402911 : if (nb_loops > 1)
4286 272398 : scev_initialize ();
4287 :
4288 2402911 : tree_estimate_probability (false);
4289 2402911 : cfun->cfg->full_profile = true;
4290 :
4291 2402911 : if (nb_loops > 1)
4292 272398 : scev_finalize ();
4293 :
4294 2402911 : loop_optimizer_finalize ();
4295 2402911 : if (dump_file && (dump_flags & TDF_DETAILS))
4296 2 : gimple_dump_cfg (dump_file, dump_flags);
4297 2402911 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4298 2402911 : profile_status_for_fn (fun) = PROFILE_GUESSED;
4299 2402911 : 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 287872 : make_pass_profile (gcc::context *ctxt)
4314 : {
4315 287872 : 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 369280 : 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 3444501 : strip_predict_hints (function *fun, bool early)
4340 : {
4341 3444501 : basic_block bb;
4342 3444501 : gimple *ass_stmt;
4343 3444501 : tree var;
4344 3444501 : bool changed = false;
4345 :
4346 26541878 : FOR_EACH_BB_FN (bb, fun)
4347 : {
4348 23097377 : gimple_stmt_iterator bi;
4349 201472632 : for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4350 : {
4351 155277878 : gimple *stmt = gsi_stmt (bi);
4352 :
4353 155277878 : if (gimple_code (stmt) == GIMPLE_PREDICT)
4354 : {
4355 1100951 : if (!early
4356 583074 : || strip_predictor_early (gimple_predict_predictor (stmt)))
4357 : {
4358 517877 : gsi_remove (&bi, true);
4359 517877 : changed = true;
4360 517877 : continue;
4361 : }
4362 : }
4363 154694804 : else if (is_gimple_call (stmt))
4364 : {
4365 12142176 : tree fndecl = gimple_call_fndecl (stmt);
4366 :
4367 12142176 : if (!early
4368 12142176 : && ((fndecl != NULL_TREE
4369 5827126 : && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4370 142959 : && gimple_call_num_args (stmt) == 2)
4371 : || (fndecl != NULL_TREE
4372 5684167 : && fndecl_built_in_p (fndecl,
4373 : BUILT_IN_EXPECT_WITH_PROBABILITY)
4374 18 : && gimple_call_num_args (stmt) == 3)
4375 6035898 : || (gimple_call_internal_p (stmt)
4376 170593 : && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4377 : {
4378 177197 : var = gimple_call_lhs (stmt);
4379 177197 : changed = true;
4380 177197 : if (var)
4381 : {
4382 177196 : ass_stmt
4383 177196 : = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4384 177196 : gsi_replace (&bi, ass_stmt, true);
4385 : }
4386 : else
4387 : {
4388 1 : gsi_remove (&bi, true);
4389 1 : continue;
4390 : }
4391 : }
4392 : }
4393 154760000 : gsi_next (&bi);
4394 : }
4395 : }
4396 3444501 : 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 863616 : pass_strip_predict_hints (gcc::context *ctxt)
4418 1727232 : : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4419 : {}
4420 :
4421 : /* opt_pass methods: */
4422 575744 : opt_pass * clone () final override
4423 : {
4424 575744 : return new pass_strip_predict_hints (m_ctxt);
4425 : }
4426 863616 : void set_pass_param (unsigned int n, bool param) final override
4427 : {
4428 863616 : gcc_assert (n == 0);
4429 863616 : early_p = param;
4430 863616 : }
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 3444501 : pass_strip_predict_hints::execute (function *fun)
4441 : {
4442 3444501 : return strip_predict_hints (fun, early_p);
4443 : }
4444 :
4445 : } // anon namespace
4446 :
4447 : gimple_opt_pass *
4448 287872 : make_pass_strip_predict_hints (gcc::context *ctxt)
4449 : {
4450 287872 : 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 1087366 : 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 1087366 : if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4465 1087366 : && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4466 : return;
4467 :
4468 :
4469 : /* See if everything is OK and update count_max. */
4470 1087118 : basic_block bb;
4471 1087118 : bool inconsistency_found = false;
4472 1087118 : bool uninitialized_probablity_found = false;
4473 1087118 : bool uninitialized_count_found = false;
4474 1087118 : bool feedback_found = false;
4475 :
4476 1087118 : cfun->cfg->count_max = profile_count::uninitialized ();
4477 15129718 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4478 : {
4479 14042600 : cfun->cfg->count_max
4480 14042600 : = profile_count::max_prefer_initialized (cfun->cfg->count_max,
4481 : bb->count);
4482 26581913 : 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 14042600 : 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 14042600 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4494 : && (!uninitialized_probablity_found || !inconsistency_found))
4495 : {
4496 12955482 : profile_count sum = profile_count::zero ();
4497 12955482 : edge e;
4498 12955482 : edge_iterator ei;
4499 :
4500 30472686 : FOR_EACH_EDGE (e, ei, bb->preds)
4501 : {
4502 17517204 : sum += e->count ();
4503 : /* Uninitialized probability may be result of inlining or an
4504 : omision in an optimization pass. */
4505 17517204 : 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 12955482 : if (sum.differs_from_p (bb->count))
4514 : {
4515 194769 : 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 1087118 : if (!inconsistency_found
4526 1026082 : && (!uninitialized_count_found || uninitialized_probablity_found)
4527 2113200 : && !cfun->cfg->count_max.very_large_p ())
4528 : {
4529 : /* Propagating zero counts should be safe and may
4530 : help hot/cold splitting. */
4531 1026037 : determine_unlikely_bbs ();
4532 1026037 : if (dump_file)
4533 31 : fprintf (dump_file, "Profile is consistent\n");
4534 1026037 : 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 61081 : 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 61072 : loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4567 61072 : connect_infinite_loops_to_exit ();
4568 61072 : estimate_bb_frequencies ();
4569 61072 : remove_fake_exit_edges ();
4570 61072 : loop_optimizer_finalize ();
4571 61072 : 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 575744 : pass_rebuild_frequencies (gcc::context *ctxt)
4596 1151488 : : gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4597 : {}
4598 :
4599 : /* opt_pass methods: */
4600 287872 : opt_pass * clone () final override
4601 : {
4602 287872 : 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 1040601 : unsigned int execute (function *) final override
4611 : {
4612 1040601 : rebuild_frequencies ();
4613 1040601 : 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 287872 : make_pass_rebuild_frequencies (gcc::context *ctxt)
4625 : {
4626 287872 : 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 571170 : force_edge_cold (edge e, bool impossible)
4670 : {
4671 571170 : profile_count count_sum = profile_count::zero ();
4672 571170 : profile_probability prob_sum = profile_probability::never ();
4673 571170 : edge_iterator ei;
4674 571170 : edge e2;
4675 571170 : bool uninitialized_exit = false;
4676 :
4677 : /* When branch probability guesses are not known, then do nothing. */
4678 571404 : if (!impossible && !e->count ().initialized_p ())
4679 2030 : return;
4680 :
4681 571170 : profile_probability goal = (impossible ? profile_probability::never ()
4682 234 : : profile_probability::very_unlikely ());
4683 :
4684 : /* If edge is already improbably or cold, just return. */
4685 571170 : if (e->probability <= goal
4686 55144 : && (!impossible || e->count () == profile_count::zero ()))
4687 1170 : return;
4688 1709495 : FOR_EACH_EDGE (e2, ei, e->src->succs)
4689 1139495 : if (e2 != e)
4690 : {
4691 569495 : if (e->flags & EDGE_FAKE)
4692 0 : continue;
4693 569495 : if (e2->count ().initialized_p ())
4694 569294 : count_sum += e2->count ();
4695 569495 : if (e2->probability.initialized_p ())
4696 569294 : 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 570000 : if (uninitialized_exit)
4704 201 : e->probability = goal;
4705 : /* If there are other edges out of e->src, redistribute probabilitity
4706 : there. */
4707 569799 : else if (prob_sum > profile_probability::never ())
4708 : {
4709 568645 : 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 568645 : set_edge_probability_and_rescale_others (e, goal);
4719 568645 : if (current_ir_type () != IR_GIMPLE
4720 568645 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4721 143578 : 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 1154 : if (prob_sum == profile_probability::never ())
4728 928 : e->probability = profile_probability::always ();
4729 : else
4730 : {
4731 226 : if (impossible)
4732 226 : e->probability = profile_probability::never ();
4733 : /* If BB has some edges out that are not impossible, we cannot
4734 : assume that BB itself is. */
4735 : impossible = false;
4736 : }
4737 1154 : if (current_ir_type () != IR_GIMPLE
4738 1154 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4739 28 : update_br_prob_note (e->src);
4740 1154 : if (e->src->count == profile_count::zero ())
4741 168 : return;
4742 1972 : if (count_sum == profile_count::zero () && impossible)
4743 : {
4744 738 : bool found = false;
4745 738 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4746 : ;
4747 708 : else if (current_ir_type () == IR_GIMPLE)
4748 1416 : for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4749 2710 : !gsi_end_p (gsi); gsi_next (&gsi))
4750 : {
4751 2048 : 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 708 : if (!found)
4761 : {
4762 692 : 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 692 : e->src->count = profile_count::zero ();
4767 1467 : FOR_EACH_EDGE (e2, ei, e->src->preds)
4768 775 : 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 588 : if (!(prob_sum > profile_probability::never ())
4779 294 : && count_sum == profile_count::zero ()
4780 122 : && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4781 52 : > (impossible ? 0 : 1))
4782 : {
4783 51 : int old_frequency = e->src->count.to_frequency (cfun);
4784 51 : 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 51 : 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 23 : e->src->count = e->count ().apply_scale (new_frequency,
4793 : old_frequency);
4794 51 : force_edge_cold (single_pred_edge (e->src), impossible);
4795 : }
4796 2 : else if (dump_file && (dump_flags & TDF_DETAILS)
4797 243 : && 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. */
|
