1/* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
30#include "config.h"
31#include "system.h"
32#include "coretypes.h"
33#include "backend.h"
34#include "rtl.h"
35#include "tree.h"
36#include "gimple.h"
37#include "cfghooks.h"
38#include "tree-pass.h"
39#include "ssa.h"
40#include "memmodel.h"
41#include "emit-rtl.h"
42#include "cgraph.h"
43#include "coverage.h"
44#include "diagnostic-core.h"
45#include "gimple-predict.h"
46#include "fold-const.h"
47#include "calls.h"
48#include "cfganal.h"
49#include "profile.h"
50#include "sreal.h"
51#include "params.h"
52#include "cfgloop.h"
53#include "gimple-iterator.h"
54#include "tree-cfg.h"
55#include "tree-ssa-loop-niter.h"
56#include "tree-ssa-loop.h"
57#include "tree-scalar-evolution.h"
58#include "ipa-utils.h"
59#include "gimple-pretty-print.h"
60#include "selftest.h"
61#include "cfgrtl.h"
62#include "stringpool.h"
63#include "attribs.h"
64
65/* Enum with reasons why a predictor is ignored. */
66
67enum predictor_reason
68{
69 REASON_NONE,
70 REASON_IGNORED,
71 REASON_SINGLE_EDGE_DUPLICATE,
72 REASON_EDGE_PAIR_DUPLICATE
73};
74
75/* String messages for the aforementioned enum. */
76
77static const char *reason_messages[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
79
80/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82static sreal real_almost_one, real_br_prob_base,
83 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
84
85static void combine_predictions_for_insn (rtx_insn *, basic_block);
86static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
87 enum predictor_reason, edge);
88static void predict_paths_leading_to (basic_block, enum br_predictor,
89 enum prediction,
90 struct loop *in_loop = NULL);
91static void predict_paths_leading_to_edge (edge, enum br_predictor,
92 enum prediction,
93 struct loop *in_loop = NULL);
94static bool can_predict_insn_p (const rtx_insn *);
95
96/* Information we hold about each branch predictor.
97 Filled using information from predict.def. */
98
99struct predictor_info
100{
101 const char *const name; /* Name used in the debugging dumps. */
102 const int hitrate; /* Expected hitrate used by
103 predict_insn_def call. */
104 const int flags;
105};
106
107/* Use given predictor without Dempster-Shaffer theory if it matches
108 using first_match heuristics. */
109#define PRED_FLAG_FIRST_MATCH 1
110
111/* Recompute hitrate in percent to our representation. */
112
113#define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
114
115#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
116static const struct predictor_info predictor_info[]= {
117#include "predict.def"
118
119 /* Upper bound on predictors. */
120 {NULL, 0, 0}
121};
122#undef DEF_PREDICTOR
123
124static gcov_type min_count = -1;
125
126/* Determine the threshold for hot BB counts. */
127
128gcov_type
129get_hot_bb_threshold ()
130{
131 gcov_working_set_t *ws;
132 if (min_count == -1)
133 {
134 ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
135 gcc_assert (ws);
136 min_count = ws->min_counter;
137 }
138 return min_count;
139}
140
141/* Set the threshold for hot BB counts. */
142
143void
144set_hot_bb_threshold (gcov_type min)
145{
146 min_count = min;
147}
148
149/* Return TRUE if frequency FREQ is considered to be hot. */
150
151bool
152maybe_hot_count_p (struct function *fun, profile_count count)
153{
154 if (!count.initialized_p ())
155 return true;
156 if (count.ipa () == profile_count::zero ())
157 return false;
158 if (!count.ipa_p ())
159 {
160 struct cgraph_node *node = cgraph_node::get (fun->decl);
161 if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
162 {
163 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
164 return false;
165 if (node->frequency == NODE_FREQUENCY_HOT)
166 return true;
167 }
168 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
169 return true;
170 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
171 && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
172 return false;
173 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
174 return false;
175 if (count.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION), 1)
176 < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
177 return false;
178 return true;
179 }
180 /* Code executed at most once is not hot. */
181 if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
182 return false;
183 return (count.to_gcov_type () >= get_hot_bb_threshold ());
184}
185
186/* Return true in case BB can be CPU intensive and should be optimized
187 for maximal performance. */
188
189bool
190maybe_hot_bb_p (struct function *fun, const_basic_block bb)
191{
192 gcc_checking_assert (fun);
193 return maybe_hot_count_p (fun, bb->count);
194}
195
196/* Return true in case BB can be CPU intensive and should be optimized
197 for maximal performance. */
198
199bool
200maybe_hot_edge_p (edge e)
201{
202 return maybe_hot_count_p (cfun, e->count ());
203}
204
205/* Return true if profile COUNT and FREQUENCY, or function FUN static
206 node frequency reflects never being executed. */
207
208static bool
209probably_never_executed (struct function *fun,
210 profile_count count)
211{
212 gcc_checking_assert (fun);
213 if (count == profile_count::zero ())
214 return true;
215 if (count.initialized_p () && profile_status_for_fn (fun) == PROFILE_READ)
216 {
217 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
218 if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
219 return false;
220 return true;
221 }
222 if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
223 && (cgraph_node::get (fun->decl)->frequency
224 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
225 return true;
226 return false;
227}
228
229
230/* Return true in case BB is probably never executed. */
231
232bool
233probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
234{
235 return probably_never_executed (fun, bb->count);
236}
237
238
239/* Return true if E is unlikely executed for obvious reasons. */
240
241static bool
242unlikely_executed_edge_p (edge e)
243{
244 return (e->count () == profile_count::zero ()
245 || e->probability == profile_probability::never ())
246 || (e->flags & (EDGE_EH | EDGE_FAKE));
247}
248
249/* Return true in case edge E is probably never executed. */
250
251bool
252probably_never_executed_edge_p (struct function *fun, edge e)
253{
254 if (unlikely_executed_edge_p (e))
255 return true;
256 return probably_never_executed (fun, e->count ());
257}
258
259/* Return true when current function should always be optimized for size. */
260
261bool
262optimize_function_for_size_p (struct function *fun)
263{
264 if (!fun || !fun->decl)
265 return optimize_size;
266 cgraph_node *n = cgraph_node::get (fun->decl);
267 return n && n->optimize_for_size_p ();
268}
269
270/* Return true when current function should always be optimized for speed. */
271
272bool
273optimize_function_for_speed_p (struct function *fun)
274{
275 return !optimize_function_for_size_p (fun);
276}
277
278/* Return the optimization type that should be used for the function FUN. */
279
280optimization_type
281function_optimization_type (struct function *fun)
282{
283 return (optimize_function_for_speed_p (fun)
284 ? OPTIMIZE_FOR_SPEED
285 : OPTIMIZE_FOR_SIZE);
286}
287
288/* Return TRUE when BB should be optimized for size. */
289
290bool
291optimize_bb_for_size_p (const_basic_block bb)
292{
293 return (optimize_function_for_size_p (cfun)
294 || (bb && !maybe_hot_bb_p (cfun, bb)));
295}
296
297/* Return TRUE when BB should be optimized for speed. */
298
299bool
300optimize_bb_for_speed_p (const_basic_block bb)
301{
302 return !optimize_bb_for_size_p (bb);
303}
304
305/* Return the optimization type that should be used for block BB. */
306
307optimization_type
308bb_optimization_type (const_basic_block bb)
309{
310 return (optimize_bb_for_speed_p (bb)
311 ? OPTIMIZE_FOR_SPEED
312 : OPTIMIZE_FOR_SIZE);
313}
314
315/* Return TRUE when BB should be optimized for size. */
316
317bool
318optimize_edge_for_size_p (edge e)
319{
320 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
321}
322
323/* Return TRUE when BB should be optimized for speed. */
324
325bool
326optimize_edge_for_speed_p (edge e)
327{
328 return !optimize_edge_for_size_p (e);
329}
330
331/* Return TRUE when BB should be optimized for size. */
332
333bool
334optimize_insn_for_size_p (void)
335{
336 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
337}
338
339/* Return TRUE when BB should be optimized for speed. */
340
341bool
342optimize_insn_for_speed_p (void)
343{
344 return !optimize_insn_for_size_p ();
345}
346
347/* Return TRUE when LOOP should be optimized for size. */
348
349bool
350optimize_loop_for_size_p (struct loop *loop)
351{
352 return optimize_bb_for_size_p (loop->header);
353}
354
355/* Return TRUE when LOOP should be optimized for speed. */
356
357bool
358optimize_loop_for_speed_p (struct loop *loop)
359{
360 return optimize_bb_for_speed_p (loop->header);
361}
362
363/* Return TRUE when LOOP nest should be optimized for speed. */
364
365bool
366optimize_loop_nest_for_speed_p (struct loop *loop)
367{
368 struct loop *l = loop;
369 if (optimize_loop_for_speed_p (loop))
370 return true;
371 l = loop->inner;
372 while (l && l != loop)
373 {
374 if (optimize_loop_for_speed_p (l))
375 return true;
376 if (l->inner)
377 l = l->inner;
378 else if (l->next)
379 l = l->next;
380 else
381 {
382 while (l != loop && !l->next)
383 l = loop_outer (l);
384 if (l != loop)
385 l = l->next;
386 }
387 }
388 return false;
389}
390
391/* Return TRUE when LOOP nest should be optimized for size. */
392
393bool
394optimize_loop_nest_for_size_p (struct loop *loop)
395{
396 return !optimize_loop_nest_for_speed_p (loop);
397}
398
399/* Return true when edge E is likely to be well predictable by branch
400 predictor. */
401
402bool
403predictable_edge_p (edge e)
404{
405 if (!e->probability.initialized_p ())
406 return false;
407 if ((e->probability.to_reg_br_prob_base ()
408 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
409 || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
410 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
411 return true;
412 return false;
413}
414
415
416/* Set RTL expansion for BB profile. */
417
418void
419rtl_profile_for_bb (basic_block bb)
420{
421 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
422}
423
424/* Set RTL expansion for edge profile. */
425
426void
427rtl_profile_for_edge (edge e)
428{
429 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
430}
431
432/* Set RTL expansion to default mode (i.e. when profile info is not known). */
433void
434default_rtl_profile (void)
435{
436 crtl->maybe_hot_insn_p = true;
437}
438
439/* Return true if the one of outgoing edges is already predicted by
440 PREDICTOR. */
441
442bool
443rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
444{
445 rtx note;
446 if (!INSN_P (BB_END (bb)))
447 return false;
448 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
449 if (REG_NOTE_KIND (note) == REG_BR_PRED
450 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
451 return true;
452 return false;
453}
454
455/* Structure representing predictions in tree level. */
456
457struct edge_prediction {
458 struct edge_prediction *ep_next;
459 edge ep_edge;
460 enum br_predictor ep_predictor;
461 int ep_probability;
462};
463
464/* This map contains for a basic block the list of predictions for the
465 outgoing edges. */
466
467static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
468
469/* Return true if the one of outgoing edges is already predicted by
470 PREDICTOR. */
471
472bool
473gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
474{
475 struct edge_prediction *i;
476 edge_prediction **preds = bb_predictions->get (bb);
477
478 if (!preds)
479 return false;
480
481 for (i = *preds; i; i = i->ep_next)
482 if (i->ep_predictor == predictor)
483 return true;
484 return false;
485}
486
487/* Return true if the one of outgoing edges is already predicted by
488 PREDICTOR for edge E predicted as TAKEN. */
489
490bool
491edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
492{
493 struct edge_prediction *i;
494 basic_block bb = e->src;
495 edge_prediction **preds = bb_predictions->get (bb);
496 if (!preds)
497 return false;
498
499 int probability = predictor_info[(int) predictor].hitrate;
500
501 if (taken != TAKEN)
502 probability = REG_BR_PROB_BASE - probability;
503
504 for (i = *preds; i; i = i->ep_next)
505 if (i->ep_predictor == predictor
506 && i->ep_edge == e
507 && i->ep_probability == probability)
508 return true;
509 return false;
510}
511
512/* Same predicate as above, working on edges. */
513bool
514edge_probability_reliable_p (const_edge e)
515{
516 return e->probability.probably_reliable_p ();
517}
518
519/* Same predicate as edge_probability_reliable_p, working on notes. */
520bool
521br_prob_note_reliable_p (const_rtx note)
522{
523 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
524 return profile_probability::from_reg_br_prob_note
525 (XINT (note, 0)).probably_reliable_p ();
526}
527
528static void
529predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
530{
531 gcc_assert (any_condjump_p (insn));
532 if (!flag_guess_branch_prob)
533 return;
534
535 add_reg_note (insn, REG_BR_PRED,
536 gen_rtx_CONCAT (VOIDmode,
537 GEN_INT ((int) predictor),
538 GEN_INT ((int) probability)));
539}
540
541/* Predict insn by given predictor. */
542
543void
544predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
545 enum prediction taken)
546{
547 int probability = predictor_info[(int) predictor].hitrate;
548
549 if (taken != TAKEN)
550 probability = REG_BR_PROB_BASE - probability;
551
552 predict_insn (insn, predictor, probability);
553}
554
555/* Predict edge E with given probability if possible. */
556
557void
558rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
559{
560 rtx_insn *last_insn;
561 last_insn = BB_END (e->src);
562
563 /* We can store the branch prediction information only about
564 conditional jumps. */
565 if (!any_condjump_p (last_insn))
566 return;
567
568 /* We always store probability of branching. */
569 if (e->flags & EDGE_FALLTHRU)
570 probability = REG_BR_PROB_BASE - probability;
571
572 predict_insn (last_insn, predictor, probability);
573}
574
575/* Predict edge E with the given PROBABILITY. */
576void
577gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
578{
579 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
580 && EDGE_COUNT (e->src->succs) > 1
581 && flag_guess_branch_prob
582 && optimize)
583 {
584 struct edge_prediction *i = XNEW (struct edge_prediction);
585 edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
586
587 i->ep_next = preds;
588 preds = i;
589 i->ep_probability = probability;
590 i->ep_predictor = predictor;
591 i->ep_edge = e;
592 }
593}
594
595/* Filter edge predictions PREDS by a function FILTER. DATA are passed
596 to the filter function. */
597
598void
599filter_predictions (edge_prediction **preds,
600 bool (*filter) (edge_prediction *, void *), void *data)
601{
602 if (!bb_predictions)
603 return;
604
605 if (preds)
606 {
607 struct edge_prediction **prediction = preds;
608 struct edge_prediction *next;
609
610 while (*prediction)
611 {
612 if ((*filter) (*prediction, data))
613 prediction = &((*prediction)->ep_next);
614 else
615 {
616 next = (*prediction)->ep_next;
617 free (*prediction);
618 *prediction = next;
619 }
620 }
621 }
622}
623
624/* Filter function predicate that returns true for a edge predicate P
625 if its edge is equal to DATA. */
626
627bool
628equal_edge_p (edge_prediction *p, void *data)
629{
630 return p->ep_edge == (edge)data;
631}
632
633/* Remove all predictions on given basic block that are attached
634 to edge E. */
635void
636remove_predictions_associated_with_edge (edge e)
637{
638 if (!bb_predictions)
639 return;
640
641 edge_prediction **preds = bb_predictions->get (e->src);
642 filter_predictions (preds, equal_edge_p, e);
643}
644
645/* Clears the list of predictions stored for BB. */
646
647static void
648clear_bb_predictions (basic_block bb)
649{
650 edge_prediction **preds = bb_predictions->get (bb);
651 struct edge_prediction *pred, *next;
652
653 if (!preds)
654 return;
655
656 for (pred = *preds; pred; pred = next)
657 {
658 next = pred->ep_next;
659 free (pred);
660 }
661 *preds = NULL;
662}
663
664/* Return true when we can store prediction on insn INSN.
665 At the moment we represent predictions only on conditional
666 jumps, not at computed jump or other complicated cases. */
667static bool
668can_predict_insn_p (const rtx_insn *insn)
669{
670 return (JUMP_P (insn)
671 && any_condjump_p (insn)
672 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
673}
674
675/* Predict edge E by given predictor if possible. */
676
677void
678predict_edge_def (edge e, enum br_predictor predictor,
679 enum prediction taken)
680{
681 int probability = predictor_info[(int) predictor].hitrate;
682
683 if (taken != TAKEN)
684 probability = REG_BR_PROB_BASE - probability;
685
686 predict_edge (e, predictor, probability);
687}
688
689/* Invert all branch predictions or probability notes in the INSN. This needs
690 to be done each time we invert the condition used by the jump. */
691
692void
693invert_br_probabilities (rtx insn)
694{
695 rtx note;
696
697 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
698 if (REG_NOTE_KIND (note) == REG_BR_PROB)
699 XINT (note, 0) = profile_probability::from_reg_br_prob_note
700 (XINT (note, 0)).invert ().to_reg_br_prob_note ();
701 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
702 XEXP (XEXP (note, 0), 1)
703 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
704}
705
706/* Dump information about the branch prediction to the output file. */
707
708static void
709dump_prediction (FILE *file, enum br_predictor predictor, int probability,
710 basic_block bb, enum predictor_reason reason = REASON_NONE,
711 edge ep_edge = NULL)
712{
713 edge e = ep_edge;
714 edge_iterator ei;
715
716 if (!file)
717 return;
718
719 if (e == NULL)
720 FOR_EACH_EDGE (e, ei, bb->succs)
721 if (! (e->flags & EDGE_FALLTHRU))
722 break;
723
724 char edge_info_str[128];
725 if (ep_edge)
726 sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
727 ep_edge->dest->index);
728 else
729 edge_info_str[0] = '\0';
730
731 fprintf (file, " %s heuristics%s%s: %.1f%%",
732 predictor_info[predictor].name,
733 edge_info_str, reason_messages[reason],
734 probability * 100.0 / REG_BR_PROB_BASE);
735
736 if (bb->count.initialized_p ())
737 {
738 fprintf (file, " exec ");
739 bb->count.dump (file);
740 if (e)
741 {
742 fprintf (file, " hit ");
743 e->count ().dump (file);
744 fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
745 / bb->count.to_gcov_type ());
746 }
747 }
748
749 fprintf (file, "\n");
750}
751
752/* Return true if STMT is known to be unlikely executed. */
753
754static bool
755unlikely_executed_stmt_p (gimple *stmt)
756{
757 if (!is_gimple_call (stmt))
758 return false;
759 /* NORETURN attribute alone is not strong enough: exit() may be quite
760 likely executed once during program run. */
761 if (gimple_call_fntype (stmt)
762 && lookup_attribute ("cold",
763 TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
764 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
765 return true;
766 tree decl = gimple_call_fndecl (stmt);
767 if (!decl)
768 return false;
769 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
770 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
771 return true;
772
773 cgraph_node *n = cgraph_node::get (decl);
774 if (!n)
775 return false;
776
777 availability avail;
778 n = n->ultimate_alias_target (&avail);
779 if (avail < AVAIL_AVAILABLE)
780 return false;
781 if (!n->analyzed
782 || n->decl == current_function_decl)
783 return false;
784 return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
785}
786
787/* Return true if BB is unlikely executed. */
788
789static bool
790unlikely_executed_bb_p (basic_block bb)
791{
792 if (bb->count == profile_count::zero ())
793 return true;
794 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
795 return false;
796 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
797 !gsi_end_p (gsi); gsi_next (&gsi))
798 {
799 if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
800 return true;
801 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
802 return false;
803 }
804 return false;
805}
806
807/* We can not predict the probabilities of outgoing edges of bb. Set them
808 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
809 even probability for all edges not mentioned in the set. These edges
810 are given PROB_VERY_UNLIKELY probability. */
811
812static void
813set_even_probabilities (basic_block bb,
814 hash_set<edge> *unlikely_edges = NULL)
815{
816 unsigned nedges = 0, unlikely_count = 0;
817 edge e = NULL;
818 edge_iterator ei;
819 profile_probability all = profile_probability::always ();
820
821 FOR_EACH_EDGE (e, ei, bb->succs)
822 if (e->probability.initialized_p ())
823 all -= e->probability;
824 else if (!unlikely_executed_edge_p (e))
825 {
826 nedges ++;
827 if (unlikely_edges != NULL && unlikely_edges->contains (e))
828 {
829 all -= profile_probability::very_unlikely ();
830 unlikely_count++;
831 }
832 }
833
834 /* Make the distribution even if all edges are unlikely. */
835 if (unlikely_count == nedges)
836 {
837 unlikely_edges = NULL;
838 unlikely_count = 0;
839 }
840
841 unsigned c = nedges - unlikely_count;
842
843 FOR_EACH_EDGE (e, ei, bb->succs)
844 if (e->probability.initialized_p ())
845 ;
846 else if (!unlikely_executed_edge_p (e))
847 {
848 if (unlikely_edges != NULL && unlikely_edges->contains (e))
849 e->probability = profile_probability::very_unlikely ();
850 else
851 e->probability = all.apply_scale (1, c).guessed ();
852 }
853 else
854 e->probability = profile_probability::never ();
855}
856
857/* Add REG_BR_PROB note to JUMP with PROB. */
858
859void
860add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
861{
862 gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
863 add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
864}
865
866/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
867 note if not already present. Remove now useless REG_BR_PRED notes. */
868
869static void
870combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
871{
872 rtx prob_note;
873 rtx *pnote;
874 rtx note;
875 int best_probability = PROB_EVEN;
876 enum br_predictor best_predictor = END_PREDICTORS;
877 int combined_probability = REG_BR_PROB_BASE / 2;
878 int d;
879 bool first_match = false;
880 bool found = false;
881
882 if (!can_predict_insn_p (insn))
883 {
884 set_even_probabilities (bb);
885 return;
886 }
887
888 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
889 pnote = &REG_NOTES (insn);
890 if (dump_file)
891 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
892 bb->index);
893
894 /* We implement "first match" heuristics and use probability guessed
895 by predictor with smallest index. */
896 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
897 if (REG_NOTE_KIND (note) == REG_BR_PRED)
898 {
899 enum br_predictor predictor = ((enum br_predictor)
900 INTVAL (XEXP (XEXP (note, 0), 0)));
901 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
902
903 found = true;
904 if (best_predictor > predictor
905 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
906 best_probability = probability, best_predictor = predictor;
907
908 d = (combined_probability * probability
909 + (REG_BR_PROB_BASE - combined_probability)
910 * (REG_BR_PROB_BASE - probability));
911
912 /* Use FP math to avoid overflows of 32bit integers. */
913 if (d == 0)
914 /* If one probability is 0% and one 100%, avoid division by zero. */
915 combined_probability = REG_BR_PROB_BASE / 2;
916 else
917 combined_probability = (((double) combined_probability) * probability
918 * REG_BR_PROB_BASE / d + 0.5);
919 }
920
921 /* Decide which heuristic to use. In case we didn't match anything,
922 use no_prediction heuristic, in case we did match, use either
923 first match or Dempster-Shaffer theory depending on the flags. */
924
925 if (best_predictor != END_PREDICTORS)
926 first_match = true;
927
928 if (!found)
929 dump_prediction (dump_file, PRED_NO_PREDICTION,
930 combined_probability, bb);
931 else
932 {
933 if (!first_match)
934 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
935 bb, !first_match ? REASON_NONE : REASON_IGNORED);
936 else
937 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
938 bb, first_match ? REASON_NONE : REASON_IGNORED);
939 }
940
941 if (first_match)
942 combined_probability = best_probability;
943 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
944
945 while (*pnote)
946 {
947 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
948 {
949 enum br_predictor predictor = ((enum br_predictor)
950 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
951 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
952
953 dump_prediction (dump_file, predictor, probability, bb,
954 (!first_match || best_predictor == predictor)
955 ? REASON_NONE : REASON_IGNORED);
956 *pnote = XEXP (*pnote, 1);
957 }
958 else
959 pnote = &XEXP (*pnote, 1);
960 }
961
962 if (!prob_note)
963 {
964 profile_probability p
965 = profile_probability::from_reg_br_prob_base (combined_probability);
966 add_reg_br_prob_note (insn, p);
967
968 /* Save the prediction into CFG in case we are seeing non-degenerated
969 conditional jump. */
970 if (!single_succ_p (bb))
971 {
972 BRANCH_EDGE (bb)->probability = p;
973 FALLTHRU_EDGE (bb)->probability
974 = BRANCH_EDGE (bb)->probability.invert ();
975 }
976 }
977 else if (!single_succ_p (bb))
978 {
979 profile_probability prob = profile_probability::from_reg_br_prob_note
980 (XINT (prob_note, 0));
981
982 BRANCH_EDGE (bb)->probability = prob;
983 FALLTHRU_EDGE (bb)->probability = prob.invert ();
984 }
985 else
986 single_succ_edge (bb)->probability = profile_probability::always ();
987}
988
989/* Edge prediction hash traits. */
990
991struct predictor_hash: pointer_hash <edge_prediction>
992{
993
994 static inline hashval_t hash (const edge_prediction *);
995 static inline bool equal (const edge_prediction *, const edge_prediction *);
996};
997
998/* Calculate hash value of an edge prediction P based on predictor and
999 normalized probability. */
1000
1001inline hashval_t
1002predictor_hash::hash (const edge_prediction *p)
1003{
1004 inchash::hash hstate;
1005 hstate.add_int (p->ep_predictor);
1006
1007 int prob = p->ep_probability;
1008 if (prob > REG_BR_PROB_BASE / 2)
1009 prob = REG_BR_PROB_BASE - prob;
1010
1011 hstate.add_int (prob);
1012
1013 return hstate.end ();
1014}
1015
1016/* Return true whether edge predictions P1 and P2 use the same predictor and
1017 have equal (or opposed probability). */
1018
1019inline bool
1020predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1021{
1022 return (p1->ep_predictor == p2->ep_predictor
1023 && (p1->ep_probability == p2->ep_probability
1024 || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1025}
1026
1027struct predictor_hash_traits: predictor_hash,
1028 typed_noop_remove <edge_prediction *> {};
1029
1030/* Return true if edge prediction P is not in DATA hash set. */
1031
1032static bool
1033not_removed_prediction_p (edge_prediction *p, void *data)
1034{
1035 hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1036 return !remove->contains (p);
1037}
1038
1039/* Prune predictions for a basic block BB. Currently we do following
1040 clean-up steps:
1041
1042 1) remove duplicate prediction that is guessed with the same probability
1043 (different than 1/2) to both edge
1044 2) remove duplicates for a prediction that belongs with the same probability
1045 to a single edge
1046
1047 */
1048
1049static void
1050prune_predictions_for_bb (basic_block bb)
1051{
1052 edge_prediction **preds = bb_predictions->get (bb);
1053
1054 if (preds)
1055 {
1056 hash_table <predictor_hash_traits> s (13);
1057 hash_set <edge_prediction *> remove;
1058
1059 /* Step 1: identify predictors that should be removed. */
1060 for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1061 {
1062 edge_prediction *existing = s.find (pred);
1063 if (existing)
1064 {
1065 if (pred->ep_edge == existing->ep_edge
1066 && pred->ep_probability == existing->ep_probability)
1067 {
1068 /* Remove a duplicate predictor. */
1069 dump_prediction (dump_file, pred->ep_predictor,
1070 pred->ep_probability, bb,
1071 REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1072
1073 remove.add (pred);
1074 }
1075 else if (pred->ep_edge != existing->ep_edge
1076 && pred->ep_probability == existing->ep_probability
1077 && pred->ep_probability != REG_BR_PROB_BASE / 2)
1078 {
1079 /* Remove both predictors as they predict the same
1080 for both edges. */
1081 dump_prediction (dump_file, existing->ep_predictor,
1082 pred->ep_probability, bb,
1083 REASON_EDGE_PAIR_DUPLICATE,
1084 existing->ep_edge);
1085 dump_prediction (dump_file, pred->ep_predictor,
1086 pred->ep_probability, bb,
1087 REASON_EDGE_PAIR_DUPLICATE,
1088 pred->ep_edge);
1089
1090 remove.add (existing);
1091 remove.add (pred);
1092 }
1093 }
1094
1095 edge_prediction **slot2 = s.find_slot (pred, INSERT);
1096 *slot2 = pred;
1097 }
1098
1099 /* Step 2: Remove predictors. */
1100 filter_predictions (preds, not_removed_prediction_p, &remove);
1101 }
1102}
1103
1104/* Combine predictions into single probability and store them into CFG.
1105 Remove now useless prediction entries.
1106 If DRY_RUN is set, only produce dumps and do not modify profile. */
1107
1108static void
1109combine_predictions_for_bb (basic_block bb, bool dry_run)
1110{
1111 int best_probability = PROB_EVEN;
1112 enum br_predictor best_predictor = END_PREDICTORS;
1113 int combined_probability = REG_BR_PROB_BASE / 2;
1114 int d;
1115 bool first_match = false;
1116 bool found = false;
1117 struct edge_prediction *pred;
1118 int nedges = 0;
1119 edge e, first = NULL, second = NULL;
1120 edge_iterator ei;
1121 int nzero = 0;
1122 int nunknown = 0;
1123
1124 FOR_EACH_EDGE (e, ei, bb->succs)
1125 {
1126 if (!unlikely_executed_edge_p (e))
1127 {
1128 nedges ++;
1129 if (first && !second)
1130 second = e;
1131 if (!first)
1132 first = e;
1133 }
1134 else if (!e->probability.initialized_p ())
1135 e->probability = profile_probability::never ();
1136 if (!e->probability.initialized_p ())
1137 nunknown++;
1138 else if (e->probability == profile_probability::never ())
1139 nzero++;
1140 }
1141
1142 /* When there is no successor or only one choice, prediction is easy.
1143
1144 When we have a basic block with more than 2 successors, the situation
1145 is more complicated as DS theory cannot be used literally.
1146 More precisely, let's assume we predicted edge e1 with probability p1,
1147 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1148 need to find probability of e.g. m1({b2}), which we don't know.
1149 The only approximation is to equally distribute 1-p1 to all edges
1150 different from b1.
1151
1152 According to numbers we've got from SPEC2006 benchark, there's only
1153 one interesting reliable predictor (noreturn call), which can be
1154 handled with a bit easier approach. */
1155 if (nedges != 2)
1156 {
1157 hash_set<edge> unlikely_edges (4);
1158
1159 /* Identify all edges that have a probability close to very unlikely.
1160 Doing the approach for very unlikely doesn't worth for doing as
1161 there's no such probability in SPEC2006 benchmark. */
1162 edge_prediction **preds = bb_predictions->get (bb);
1163 if (preds)
1164 for (pred = *preds; pred; pred = pred->ep_next)
1165 if (pred->ep_probability <= PROB_VERY_UNLIKELY)
1166 unlikely_edges.add (pred->ep_edge);
1167
1168 if (!dry_run)
1169 set_even_probabilities (bb, &unlikely_edges);
1170 clear_bb_predictions (bb);
1171 if (dump_file)
1172 {
1173 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1174 if (unlikely_edges.elements () == 0)
1175 fprintf (dump_file,
1176 "%i edges in bb %i predicted to even probabilities\n",
1177 nedges, bb->index);
1178 else
1179 {
1180 fprintf (dump_file,
1181 "%i edges in bb %i predicted with some unlikely edges\n",
1182 nedges, bb->index);
1183 FOR_EACH_EDGE (e, ei, bb->succs)
1184 if (!unlikely_executed_edge_p (e))
1185 dump_prediction (dump_file, PRED_COMBINED,
1186 e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1187 }
1188 }
1189 return;
1190 }
1191
1192 if (dump_file)
1193 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1194
1195 prune_predictions_for_bb (bb);
1196
1197 edge_prediction **preds = bb_predictions->get (bb);
1198
1199 if (preds)
1200 {
1201 /* We implement "first match" heuristics and use probability guessed
1202 by predictor with smallest index. */
1203 for (pred = *preds; pred; pred = pred->ep_next)
1204 {
1205 enum br_predictor predictor = pred->ep_predictor;
1206 int probability = pred->ep_probability;
1207
1208 if (pred->ep_edge != first)
1209 probability = REG_BR_PROB_BASE - probability;
1210
1211 found = true;
1212 /* First match heuristics would be widly confused if we predicted
1213 both directions. */
1214 if (best_predictor > predictor
1215 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1216 {
1217 struct edge_prediction *pred2;
1218 int prob = probability;
1219
1220 for (pred2 = (struct edge_prediction *) *preds;
1221 pred2; pred2 = pred2->ep_next)
1222 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1223 {
1224 int probability2 = pred2->ep_probability;
1225
1226 if (pred2->ep_edge != first)
1227 probability2 = REG_BR_PROB_BASE - probability2;
1228
1229 if ((probability < REG_BR_PROB_BASE / 2) !=
1230 (probability2 < REG_BR_PROB_BASE / 2))
1231 break;
1232
1233 /* If the same predictor later gave better result, go for it! */
1234 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1235 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1236 prob = probability2;
1237 }
1238 if (!pred2)
1239 best_probability = prob, best_predictor = predictor;
1240 }
1241
1242 d = (combined_probability * probability
1243 + (REG_BR_PROB_BASE - combined_probability)
1244 * (REG_BR_PROB_BASE - probability));
1245
1246 /* Use FP math to avoid overflows of 32bit integers. */
1247 if (d == 0)
1248 /* If one probability is 0% and one 100%, avoid division by zero. */
1249 combined_probability = REG_BR_PROB_BASE / 2;
1250 else
1251 combined_probability = (((double) combined_probability)
1252 * probability
1253 * REG_BR_PROB_BASE / d + 0.5);
1254 }
1255 }
1256
1257 /* Decide which heuristic to use. In case we didn't match anything,
1258 use no_prediction heuristic, in case we did match, use either
1259 first match or Dempster-Shaffer theory depending on the flags. */
1260
1261 if (best_predictor != END_PREDICTORS)
1262 first_match = true;
1263
1264 if (!found)
1265 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1266 else
1267 {
1268 if (!first_match)
1269 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1270 !first_match ? REASON_NONE : REASON_IGNORED);
1271 else
1272 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1273 first_match ? REASON_NONE : REASON_IGNORED);
1274 }
1275
1276 if (first_match)
1277 combined_probability = best_probability;
1278 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1279
1280 if (preds)
1281 {
1282 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1283 {
1284 enum br_predictor predictor = pred->ep_predictor;
1285 int probability = pred->ep_probability;
1286
1287 dump_prediction (dump_file, predictor, probability, bb,
1288 (!first_match || best_predictor == predictor)
1289 ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1290 }
1291 }
1292 clear_bb_predictions (bb);
1293
1294
1295 /* If we have only one successor which is unknown, we can compute missing
1296 probablity. */
1297 if (nunknown == 1)
1298 {
1299 profile_probability prob = profile_probability::always ();
1300 edge missing = NULL;
1301
1302 FOR_EACH_EDGE (e, ei, bb->succs)
1303 if (e->probability.initialized_p ())
1304 prob -= e->probability;
1305 else if (missing == NULL)
1306 missing = e;
1307 else
1308 gcc_unreachable ();
1309 missing->probability = prob;
1310 }
1311 /* If nothing is unknown, we have nothing to update. */
1312 else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1313 ;
1314 else if (!dry_run)
1315 {
1316 first->probability
1317 = profile_probability::from_reg_br_prob_base (combined_probability);
1318 second->probability = first->probability.invert ();
1319 }
1320}
1321
1322/* Check if T1 and T2 satisfy the IV_COMPARE condition.
1323 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1324
1325 T1 and T2 should be one of the following cases:
1326 1. T1 is SSA_NAME, T2 is NULL
1327 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1328 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1329
1330static tree
1331strips_small_constant (tree t1, tree t2)
1332{
1333 tree ret = NULL;
1334 int value = 0;
1335
1336 if (!t1)
1337 return NULL;
1338 else if (TREE_CODE (t1) == SSA_NAME)
1339 ret = t1;
1340 else if (tree_fits_shwi_p (t1))
1341 value = tree_to_shwi (t1);
1342 else
1343 return NULL;
1344
1345 if (!t2)
1346 return ret;
1347 else if (tree_fits_shwi_p (t2))
1348 value = tree_to_shwi (t2);
1349 else if (TREE_CODE (t2) == SSA_NAME)
1350 {
1351 if (ret)
1352 return NULL;
1353 else
1354 ret = t2;
1355 }
1356
1357 if (value <= 4 && value >= -4)
1358 return ret;
1359 else
1360 return NULL;
1361}
1362
1363/* Return the SSA_NAME in T or T's operands.
1364 Return NULL if SSA_NAME cannot be found. */
1365
1366static tree
1367get_base_value (tree t)
1368{
1369 if (TREE_CODE (t) == SSA_NAME)
1370 return t;
1371
1372 if (!BINARY_CLASS_P (t))
1373 return NULL;
1374
1375 switch (TREE_OPERAND_LENGTH (t))
1376 {
1377 case 1:
1378 return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1379 case 2:
1380 return strips_small_constant (TREE_OPERAND (t, 0),
1381 TREE_OPERAND (t, 1));
1382 default:
1383 return NULL;
1384 }
1385}
1386
1387/* Check the compare STMT in LOOP. If it compares an induction
1388 variable to a loop invariant, return true, and save
1389 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1390 Otherwise return false and set LOOP_INVAIANT to NULL. */
1391
1392static bool
1393is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1394 tree *loop_invariant,
1395 enum tree_code *compare_code,
1396 tree *loop_step,
1397 tree *loop_iv_base)
1398{
1399 tree op0, op1, bound, base;
1400 affine_iv iv0, iv1;
1401 enum tree_code code;
1402 tree step;
1403
1404 code = gimple_cond_code (stmt);
1405 *loop_invariant = NULL;
1406
1407 switch (code)
1408 {
1409 case GT_EXPR:
1410 case GE_EXPR:
1411 case NE_EXPR:
1412 case LT_EXPR:
1413 case LE_EXPR:
1414 case EQ_EXPR:
1415 break;
1416
1417 default:
1418 return false;
1419 }
1420
1421 op0 = gimple_cond_lhs (stmt);
1422 op1 = gimple_cond_rhs (stmt);
1423
1424 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1425 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1426 return false;
1427 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1428 return false;
1429 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1430 return false;
1431 if (TREE_CODE (iv0.step) != INTEGER_CST
1432 || TREE_CODE (iv1.step) != INTEGER_CST)
1433 return false;
1434 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1435 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1436 return false;
1437
1438 if (integer_zerop (iv0.step))
1439 {
1440 if (code != NE_EXPR && code != EQ_EXPR)
1441 code = invert_tree_comparison (code, false);
1442 bound = iv0.base;
1443 base = iv1.base;
1444 if (tree_fits_shwi_p (iv1.step))
1445 step = iv1.step;
1446 else
1447 return false;
1448 }
1449 else
1450 {
1451 bound = iv1.base;
1452 base = iv0.base;
1453 if (tree_fits_shwi_p (iv0.step))
1454 step = iv0.step;
1455 else
1456 return false;
1457 }
1458
1459 if (TREE_CODE (bound) != INTEGER_CST)
1460 bound = get_base_value (bound);
1461 if (!bound)
1462 return false;
1463 if (TREE_CODE (base) != INTEGER_CST)
1464 base = get_base_value (base);
1465 if (!base)
1466 return false;
1467
1468 *loop_invariant = bound;
1469 *compare_code = code;
1470 *loop_step = step;
1471 *loop_iv_base = base;
1472 return true;
1473}
1474
1475/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1476
1477static bool
1478expr_coherent_p (tree t1, tree t2)
1479{
1480 gimple *stmt;
1481 tree ssa_name_1 = NULL;
1482 tree ssa_name_2 = NULL;
1483
1484 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1485 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1486
1487 if (t1 == t2)
1488 return true;
1489
1490 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1491 return true;
1492 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1493 return false;
1494
1495 /* Check to see if t1 is expressed/defined with t2. */
1496 stmt = SSA_NAME_DEF_STMT (t1);
1497 gcc_assert (stmt != NULL);
1498 if (is_gimple_assign (stmt))
1499 {
1500 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1501 if (ssa_name_1 && ssa_name_1 == t2)
1502 return true;
1503 }
1504
1505 /* Check to see if t2 is expressed/defined with t1. */
1506 stmt = SSA_NAME_DEF_STMT (t2);
1507 gcc_assert (stmt != NULL);
1508 if (is_gimple_assign (stmt))
1509 {
1510 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1511 if (ssa_name_2 && ssa_name_2 == t1)
1512 return true;
1513 }
1514
1515 /* Compare if t1 and t2's def_stmts are identical. */
1516 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1517 return true;
1518 else
1519 return false;
1520}
1521
1522/* Return true if E is predicted by one of loop heuristics. */
1523
1524static bool
1525predicted_by_loop_heuristics_p (basic_block bb)
1526{
1527 struct edge_prediction *i;
1528 edge_prediction **preds = bb_predictions->get (bb);
1529
1530 if (!preds)
1531 return false;
1532
1533 for (i = *preds; i; i = i->ep_next)
1534 if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1535 || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1536 || i->ep_predictor == PRED_LOOP_ITERATIONS
1537 || i->ep_predictor == PRED_LOOP_EXIT
1538 || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1539 || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1540 return true;
1541 return false;
1542}
1543
1544/* Predict branch probability of BB when BB contains a branch that compares
1545 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1546 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1547
1548 E.g.
1549 for (int i = 0; i < bound; i++) {
1550 if (i < bound - 2)
1551 computation_1();
1552 else
1553 computation_2();
1554 }
1555
1556 In this loop, we will predict the branch inside the loop to be taken. */
1557
1558static void
1559predict_iv_comparison (struct loop *loop, basic_block bb,
1560 tree loop_bound_var,
1561 tree loop_iv_base_var,
1562 enum tree_code loop_bound_code,
1563 int loop_bound_step)
1564{
1565 gimple *stmt;
1566 tree compare_var, compare_base;
1567 enum tree_code compare_code;
1568 tree compare_step_var;
1569 edge then_edge;
1570 edge_iterator ei;
1571
1572 if (predicted_by_loop_heuristics_p (bb))
1573 return;
1574
1575 stmt = last_stmt (bb);
1576 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1577 return;
1578 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1579 loop, &compare_var,
1580 &compare_code,
1581 &compare_step_var,
1582 &compare_base))
1583 return;
1584
1585 /* Find the taken edge. */
1586 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1587 if (then_edge->flags & EDGE_TRUE_VALUE)
1588 break;
1589
1590 /* When comparing an IV to a loop invariant, NE is more likely to be
1591 taken while EQ is more likely to be not-taken. */
1592 if (compare_code == NE_EXPR)
1593 {
1594 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1595 return;
1596 }
1597 else if (compare_code == EQ_EXPR)
1598 {
1599 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1600 return;
1601 }
1602
1603 if (!expr_coherent_p (loop_iv_base_var, compare_base))
1604 return;
1605
1606 /* If loop bound, base and compare bound are all constants, we can
1607 calculate the probability directly. */
1608 if (tree_fits_shwi_p (loop_bound_var)
1609 && tree_fits_shwi_p (compare_var)
1610 && tree_fits_shwi_p (compare_base))
1611 {
1612 int probability;
1613 bool overflow, overall_overflow = false;
1614 widest_int compare_count, tem;
1615
1616 /* (loop_bound - base) / compare_step */
1617 tem = wi::sub (wi::to_widest (loop_bound_var),
1618 wi::to_widest (compare_base), SIGNED, &overflow);
1619 overall_overflow |= overflow;
1620 widest_int loop_count = wi::div_trunc (tem,
1621 wi::to_widest (compare_step_var),
1622 SIGNED, &overflow);
1623 overall_overflow |= overflow;
1624
1625 if (!wi::neg_p (wi::to_widest (compare_step_var))
1626 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1627 {
1628 /* (loop_bound - compare_bound) / compare_step */
1629 tem = wi::sub (wi::to_widest (loop_bound_var),
1630 wi::to_widest (compare_var), SIGNED, &overflow);
1631 overall_overflow |= overflow;
1632 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1633 SIGNED, &overflow);
1634 overall_overflow |= overflow;
1635 }
1636 else
1637 {
1638 /* (compare_bound - base) / compare_step */
1639 tem = wi::sub (wi::to_widest (compare_var),
1640 wi::to_widest (compare_base), SIGNED, &overflow);
1641 overall_overflow |= overflow;
1642 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1643 SIGNED, &overflow);
1644 overall_overflow |= overflow;
1645 }
1646 if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1647 ++compare_count;
1648 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1649 ++loop_count;
1650 if (wi::neg_p (compare_count))
1651 compare_count = 0;
1652 if (wi::neg_p (loop_count))
1653 loop_count = 0;
1654 if (loop_count == 0)
1655 probability = 0;
1656 else if (wi::cmps (compare_count, loop_count) == 1)
1657 probability = REG_BR_PROB_BASE;
1658 else
1659 {
1660 tem = compare_count * REG_BR_PROB_BASE;
1661 tem = wi::udiv_trunc (tem, loop_count);
1662 probability = tem.to_uhwi ();
1663 }
1664
1665 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1666 if (!overall_overflow)
1667 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1668
1669 return;
1670 }
1671
1672 if (expr_coherent_p (loop_bound_var, compare_var))
1673 {
1674 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1675 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1676 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1677 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1678 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1679 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1680 else if (loop_bound_code == NE_EXPR)
1681 {
1682 /* If the loop backedge condition is "(i != bound)", we do
1683 the comparison based on the step of IV:
1684 * step < 0 : backedge condition is like (i > bound)
1685 * step > 0 : backedge condition is like (i < bound) */
1686 gcc_assert (loop_bound_step != 0);
1687 if (loop_bound_step > 0
1688 && (compare_code == LT_EXPR
1689 || compare_code == LE_EXPR))
1690 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1691 else if (loop_bound_step < 0
1692 && (compare_code == GT_EXPR
1693 || compare_code == GE_EXPR))
1694 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1695 else
1696 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1697 }
1698 else
1699 /* The branch is predicted not-taken if loop_bound_code is
1700 opposite with compare_code. */
1701 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1702 }
1703 else if (expr_coherent_p (loop_iv_base_var, compare_var))
1704 {
1705 /* For cases like:
1706 for (i = s; i < h; i++)
1707 if (i > s + 2) ....
1708 The branch should be predicted taken. */
1709 if (loop_bound_step > 0
1710 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1711 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1712 else if (loop_bound_step < 0
1713 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1714 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1715 else
1716 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1717 }
1718}
1719
1720/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1721 exits are resulted from short-circuit conditions that will generate an
1722 if_tmp. E.g.:
1723
1724 if (foo() || global > 10)
1725 break;
1726
1727 This will be translated into:
1728
1729 BB3:
1730 loop header...
1731 BB4:
1732 if foo() goto BB6 else goto BB5
1733 BB5:
1734 if global > 10 goto BB6 else goto BB7
1735 BB6:
1736 goto BB7
1737 BB7:
1738 iftmp = (PHI 0(BB5), 1(BB6))
1739 if iftmp == 1 goto BB8 else goto BB3
1740 BB8:
1741 outside of the loop...
1742
1743 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1744 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1745 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1746 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1747
1748static void
1749predict_extra_loop_exits (edge exit_edge)
1750{
1751 unsigned i;
1752 bool check_value_one;
1753 gimple *lhs_def_stmt;
1754 gphi *phi_stmt;
1755 tree cmp_rhs, cmp_lhs;
1756 gimple *last;
1757 gcond *cmp_stmt;
1758
1759 last = last_stmt (exit_edge->src);
1760 if (!last)
1761 return;
1762 cmp_stmt = dyn_cast <gcond *> (last);
1763 if (!cmp_stmt)
1764 return;
1765
1766 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1767 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1768 if (!TREE_CONSTANT (cmp_rhs)
1769 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1770 return;
1771 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1772 return;
1773
1774 /* If check_value_one is true, only the phi_args with value '1' will lead
1775 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1776 loop exit. */
1777 check_value_one = (((integer_onep (cmp_rhs))
1778 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1779 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1780
1781 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1782 if (!lhs_def_stmt)
1783 return;
1784
1785 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1786 if (!phi_stmt)
1787 return;
1788
1789 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1790 {
1791 edge e1;
1792 edge_iterator ei;
1793 tree val = gimple_phi_arg_def (phi_stmt, i);
1794 edge e = gimple_phi_arg_edge (phi_stmt, i);
1795
1796 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1797 continue;
1798 if ((check_value_one ^ integer_onep (val)) == 1)
1799 continue;
1800 if (EDGE_COUNT (e->src->succs) != 1)
1801 {
1802 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1803 continue;
1804 }
1805
1806 FOR_EACH_EDGE (e1, ei, e->src->preds)
1807 predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1808 }
1809}
1810
1811
1812/* Predict edge probabilities by exploiting loop structure. */
1813
1814static void
1815predict_loops (void)
1816{
1817 struct loop *loop;
1818 basic_block bb;
1819 hash_set <struct loop *> with_recursion(10);
1820
1821 FOR_EACH_BB_FN (bb, cfun)
1822 {
1823 gimple_stmt_iterator gsi;
1824 tree decl;
1825
1826 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1827 if (is_gimple_call (gsi_stmt (gsi))
1828 && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1829 && recursive_call_p (current_function_decl, decl))
1830 {
1831 loop = bb->loop_father;
1832 while (loop && !with_recursion.add (loop))
1833 loop = loop_outer (loop);
1834 }
1835 }
1836
1837 /* Try to predict out blocks in a loop that are not part of a
1838 natural loop. */
1839 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1840 {
1841 basic_block bb, *bbs;
1842 unsigned j, n_exits = 0;
1843 vec<edge> exits;
1844 struct tree_niter_desc niter_desc;
1845 edge ex;
1846 struct nb_iter_bound *nb_iter;
1847 enum tree_code loop_bound_code = ERROR_MARK;
1848 tree loop_bound_step = NULL;
1849 tree loop_bound_var = NULL;
1850 tree loop_iv_base = NULL;
1851 gcond *stmt = NULL;
1852 bool recursion = with_recursion.contains (loop);
1853
1854 exits = get_loop_exit_edges (loop);
1855 FOR_EACH_VEC_ELT (exits, j, ex)
1856 if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1857 n_exits ++;
1858 if (!n_exits)
1859 {
1860 exits.release ();
1861 continue;
1862 }
1863
1864 if (dump_file && (dump_flags & TDF_DETAILS))
1865 fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1866 loop->num, recursion ? " (with recursion)":"", n_exits);
1867 if (dump_file && (dump_flags & TDF_DETAILS)
1868 && max_loop_iterations_int (loop) >= 0)
1869 {
1870 fprintf (dump_file,
1871 "Loop %d iterates at most %i times.\n", loop->num,
1872 (int)max_loop_iterations_int (loop));
1873 }
1874 if (dump_file && (dump_flags & TDF_DETAILS)
1875 && likely_max_loop_iterations_int (loop) >= 0)
1876 {
1877 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1878 loop->num, (int)likely_max_loop_iterations_int (loop));
1879 }
1880
1881 FOR_EACH_VEC_ELT (exits, j, ex)
1882 {
1883 tree niter = NULL;
1884 HOST_WIDE_INT nitercst;
1885 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1886 int probability;
1887 enum br_predictor predictor;
1888 widest_int nit;
1889
1890 if (unlikely_executed_edge_p (ex)
1891 || (ex->flags & EDGE_ABNORMAL_CALL))
1892 continue;
1893 /* Loop heuristics do not expect exit conditional to be inside
1894 inner loop. We predict from innermost to outermost loop. */
1895 if (predicted_by_loop_heuristics_p (ex->src))
1896 {
1897 if (dump_file && (dump_flags & TDF_DETAILS))
1898 fprintf (dump_file, "Skipping exit %i->%i because "
1899 "it is already predicted.\n",
1900 ex->src->index, ex->dest->index);
1901 continue;
1902 }
1903 predict_extra_loop_exits (ex);
1904
1905 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1906 niter = niter_desc.niter;
1907 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1908 niter = loop_niter_by_eval (loop, ex);
1909 if (dump_file && (dump_flags & TDF_DETAILS)
1910 && TREE_CODE (niter) == INTEGER_CST)
1911 {
1912 fprintf (dump_file, "Exit %i->%i %d iterates ",
1913 ex->src->index, ex->dest->index,
1914 loop->num);
1915 print_generic_expr (dump_file, niter, TDF_SLIM);
1916 fprintf (dump_file, " times.\n");
1917 }
1918
1919 if (TREE_CODE (niter) == INTEGER_CST)
1920 {
1921 if (tree_fits_uhwi_p (niter)
1922 && max
1923 && compare_tree_int (niter, max - 1) == -1)
1924 nitercst = tree_to_uhwi (niter) + 1;
1925 else
1926 nitercst = max;
1927 predictor = PRED_LOOP_ITERATIONS;
1928 }
1929 /* If we have just one exit and we can derive some information about
1930 the number of iterations of the loop from the statements inside
1931 the loop, use it to predict this exit. */
1932 else if (n_exits == 1
1933 && estimated_stmt_executions (loop, &nit))
1934 {
1935 if (wi::gtu_p (nit, max))
1936 nitercst = max;
1937 else
1938 nitercst = nit.to_shwi ();
1939 predictor = PRED_LOOP_ITERATIONS_GUESSED;
1940 }
1941 /* If we have likely upper bound, trust it for very small iteration
1942 counts. Such loops would otherwise get mispredicted by standard
1943 LOOP_EXIT heuristics. */
1944 else if (n_exits == 1
1945 && likely_max_stmt_executions (loop, &nit)
1946 && wi::ltu_p (nit,
1947 RDIV (REG_BR_PROB_BASE,
1948 REG_BR_PROB_BASE
1949 - predictor_info
1950 [recursion
1951 ? PRED_LOOP_EXIT_WITH_RECURSION
1952 : PRED_LOOP_EXIT].hitrate)))
1953 {
1954 nitercst = nit.to_shwi ();
1955 predictor = PRED_LOOP_ITERATIONS_MAX;
1956 }
1957 else
1958 {
1959 if (dump_file && (dump_flags & TDF_DETAILS))
1960 fprintf (dump_file, "Nothing known about exit %i->%i.\n",
1961 ex->src->index, ex->dest->index);
1962 continue;
1963 }
1964
1965 if (dump_file && (dump_flags & TDF_DETAILS))
1966 fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
1967 (int)nitercst, predictor_info[predictor].name);
1968 /* If the prediction for number of iterations is zero, do not
1969 predict the exit edges. */
1970 if (nitercst == 0)
1971 continue;
1972
1973 probability = RDIV (REG_BR_PROB_BASE, nitercst);
1974 predict_edge (ex, predictor, probability);
1975 }
1976 exits.release ();
1977
1978 /* Find information about loop bound variables. */
1979 for (nb_iter = loop->bounds; nb_iter;
1980 nb_iter = nb_iter->next)
1981 if (nb_iter->stmt
1982 && gimple_code (nb_iter->stmt) == GIMPLE_COND)
1983 {
1984 stmt = as_a <gcond *> (nb_iter->stmt);
1985 break;
1986 }
1987 if (!stmt && last_stmt (loop->header)
1988 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
1989 stmt = as_a <gcond *> (last_stmt (loop->header));
1990 if (stmt)
1991 is_comparison_with_loop_invariant_p (stmt, loop,
1992 &loop_bound_var,
1993 &loop_bound_code,
1994 &loop_bound_step,
1995 &loop_iv_base);
1996
1997 bbs = get_loop_body (loop);
1998
1999 for (j = 0; j < loop->num_nodes; j++)
2000 {
2001 edge e;
2002 edge_iterator ei;
2003
2004 bb = bbs[j];
2005
2006 /* Bypass loop heuristics on continue statement. These
2007 statements construct loops via "non-loop" constructs
2008 in the source language and are better to be handled
2009 separately. */
2010 if (predicted_by_p (bb, PRED_CONTINUE))
2011 {
2012 if (dump_file && (dump_flags & TDF_DETAILS))
2013 fprintf (dump_file, "BB %i predicted by continue.\n",
2014 bb->index);
2015 continue;
2016 }
2017
2018 /* If we already used more reliable loop exit predictors, do not
2019 bother with PRED_LOOP_EXIT. */
2020 if (!predicted_by_loop_heuristics_p (bb))
2021 {
2022 /* For loop with many exits we don't want to predict all exits
2023 with the pretty large probability, because if all exits are
2024 considered in row, the loop would be predicted to iterate
2025 almost never. The code to divide probability by number of
2026 exits is very rough. It should compute the number of exits
2027 taken in each patch through function (not the overall number
2028 of exits that might be a lot higher for loops with wide switch
2029 statements in them) and compute n-th square root.
2030
2031 We limit the minimal probability by 2% to avoid
2032 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2033 as this was causing regression in perl benchmark containing such
2034 a wide loop. */
2035
2036 int probability = ((REG_BR_PROB_BASE
2037 - predictor_info
2038 [recursion
2039 ? PRED_LOOP_EXIT_WITH_RECURSION
2040 : PRED_LOOP_EXIT].hitrate)
2041 / n_exits);
2042 if (probability < HITRATE (2))
2043 probability = HITRATE (2);
2044 FOR_EACH_EDGE (e, ei, bb->succs)
2045 if (e->dest->index < NUM_FIXED_BLOCKS
2046 || !flow_bb_inside_loop_p (loop, e->dest))
2047 {
2048 if (dump_file && (dump_flags & TDF_DETAILS))
2049 fprintf (dump_file,
2050 "Predicting exit %i->%i with prob %i.\n",
2051 e->src->index, e->dest->index, probability);
2052 predict_edge (e,
2053 recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2054 : PRED_LOOP_EXIT, probability);
2055 }
2056 }
2057 if (loop_bound_var)
2058 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2059 loop_bound_code,
2060 tree_to_shwi (loop_bound_step));
2061 }
2062
2063 /* In the following code
2064 for (loop1)
2065 if (cond)
2066 for (loop2)
2067 body;
2068 guess that cond is unlikely. */
2069 if (loop_outer (loop)->num)
2070 {
2071 basic_block bb = NULL;
2072 edge preheader_edge = loop_preheader_edge (loop);
2073
2074 if (single_pred_p (preheader_edge->src)
2075 && single_succ_p (preheader_edge->src))
2076 preheader_edge = single_pred_edge (preheader_edge->src);
2077
2078 gimple *stmt = last_stmt (preheader_edge->src);
2079 /* Pattern match fortran loop preheader:
2080 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2081 _17 = (logical(kind=4)) _16;
2082 if (_17 != 0)
2083 goto <bb 11>;
2084 else
2085 goto <bb 13>;
2086
2087 Loop guard branch prediction says nothing about duplicated loop
2088 headers produced by fortran frontend and in this case we want
2089 to predict paths leading to this preheader. */
2090
2091 if (stmt
2092 && gimple_code (stmt) == GIMPLE_COND
2093 && gimple_cond_code (stmt) == NE_EXPR
2094 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2095 && integer_zerop (gimple_cond_rhs (stmt)))
2096 {
2097 gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2098 if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2099 && gimple_expr_code (call_stmt) == NOP_EXPR
2100 && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2101 call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2102 if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2103 && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2104 && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2105 && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2106 == PRED_FORTRAN_LOOP_PREHEADER)
2107 bb = preheader_edge->src;
2108 }
2109 if (!bb)
2110 {
2111 if (!dominated_by_p (CDI_DOMINATORS,
2112 loop_outer (loop)->latch, loop->header))
2113 predict_paths_leading_to_edge (loop_preheader_edge (loop),
2114 recursion
2115 ? PRED_LOOP_GUARD_WITH_RECURSION
2116 : PRED_LOOP_GUARD,
2117 NOT_TAKEN,
2118 loop_outer (loop));
2119 }
2120 else
2121 {
2122 if (!dominated_by_p (CDI_DOMINATORS,
2123 loop_outer (loop)->latch, bb))
2124 predict_paths_leading_to (bb,
2125 recursion
2126 ? PRED_LOOP_GUARD_WITH_RECURSION
2127 : PRED_LOOP_GUARD,
2128 NOT_TAKEN,
2129 loop_outer (loop));
2130 }
2131 }
2132
2133 /* Free basic blocks from get_loop_body. */
2134 free (bbs);
2135 }
2136}
2137
2138/* Attempt to predict probabilities of BB outgoing edges using local
2139 properties. */
2140static void
2141bb_estimate_probability_locally (basic_block bb)
2142{
2143 rtx_insn *last_insn = BB_END (bb);
2144 rtx cond;
2145
2146 if (! can_predict_insn_p (last_insn))
2147 return;
2148 cond = get_condition (last_insn, NULL, false, false);
2149 if (! cond)
2150 return;
2151
2152 /* Try "pointer heuristic."
2153 A comparison ptr == 0 is predicted as false.
2154 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2155 if (COMPARISON_P (cond)
2156 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2157 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2158 {
2159 if (GET_CODE (cond) == EQ)
2160 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2161 else if (GET_CODE (cond) == NE)
2162 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2163 }
2164 else
2165
2166 /* Try "opcode heuristic."
2167 EQ tests are usually false and NE tests are usually true. Also,
2168 most quantities are positive, so we can make the appropriate guesses
2169 about signed comparisons against zero. */
2170 switch (GET_CODE (cond))
2171 {
2172 case CONST_INT:
2173 /* Unconditional branch. */
2174 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2175 cond == const0_rtx ? NOT_TAKEN : TAKEN);
2176 break;
2177
2178 case EQ:
2179 case UNEQ:
2180 /* Floating point comparisons appears to behave in a very
2181 unpredictable way because of special role of = tests in
2182 FP code. */
2183 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2184 ;
2185 /* Comparisons with 0 are often used for booleans and there is
2186 nothing useful to predict about them. */
2187 else if (XEXP (cond, 1) == const0_rtx
2188 || XEXP (cond, 0) == const0_rtx)
2189 ;
2190 else
2191 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2192 break;
2193
2194 case NE:
2195 case LTGT:
2196 /* Floating point comparisons appears to behave in a very
2197 unpredictable way because of special role of = tests in
2198 FP code. */
2199 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2200 ;
2201 /* Comparisons with 0 are often used for booleans and there is
2202 nothing useful to predict about them. */
2203 else if (XEXP (cond, 1) == const0_rtx
2204 || XEXP (cond, 0) == const0_rtx)
2205 ;
2206 else
2207 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2208 break;
2209
2210 case ORDERED:
2211 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2212 break;
2213
2214 case UNORDERED:
2215 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2216 break;
2217
2218 case LE:
2219 case LT:
2220 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2221 || XEXP (cond, 1) == constm1_rtx)
2222 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2223 break;
2224
2225 case GE:
2226 case GT:
2227 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2228 || XEXP (cond, 1) == constm1_rtx)
2229 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2230 break;
2231
2232 default:
2233 break;
2234 }
2235}
2236
2237/* Set edge->probability for each successor edge of BB. */
2238void
2239guess_outgoing_edge_probabilities (basic_block bb)
2240{
2241 bb_estimate_probability_locally (bb);
2242 combine_predictions_for_insn (BB_END (bb), bb);
2243}
2244
2245static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
2246
2247/* Helper function for expr_expected_value. */
2248
2249static tree
2250expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2251 tree op1, bitmap visited, enum br_predictor *predictor)
2252{
2253 gimple *def;
2254
2255 if (predictor)
2256 *predictor = PRED_UNCONDITIONAL;
2257
2258 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2259 {
2260 if (TREE_CONSTANT (op0))
2261 return op0;
2262
2263 if (code == IMAGPART_EXPR)
2264 {
2265 if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2266 {
2267 def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2268 if (is_gimple_call (def)
2269 && gimple_call_internal_p (def)
2270 && (gimple_call_internal_fn (def)
2271 == IFN_ATOMIC_COMPARE_EXCHANGE))
2272 {
2273 /* Assume that any given atomic operation has low contention,
2274 and thus the compare-and-swap operation succeeds. */
2275 if (predictor)
2276 *predictor = PRED_COMPARE_AND_SWAP;
2277 return build_one_cst (TREE_TYPE (op0));
2278 }
2279 }
2280 }
2281
2282 if (code != SSA_NAME)
2283 return NULL_TREE;
2284
2285 def = SSA_NAME_DEF_STMT (op0);
2286
2287 /* If we were already here, break the infinite cycle. */
2288 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2289 return NULL;
2290
2291 if (gimple_code (def) == GIMPLE_PHI)
2292 {
2293 /* All the arguments of the PHI node must have the same constant
2294 length. */
2295 int i, n = gimple_phi_num_args (def);
2296 tree val = NULL, new_val;
2297
2298 for (i = 0; i < n; i++)
2299 {
2300 tree arg = PHI_ARG_DEF (def, i);
2301 enum br_predictor predictor2;
2302
2303 /* If this PHI has itself as an argument, we cannot
2304 determine the string length of this argument. However,
2305 if we can find an expected constant value for the other
2306 PHI args then we can still be sure that this is
2307 likely a constant. So be optimistic and just
2308 continue with the next argument. */
2309 if (arg == PHI_RESULT (def))
2310 continue;
2311
2312 new_val = expr_expected_value (arg, visited, &predictor2);
2313
2314 /* It is difficult to combine value predictors. Simply assume
2315 that later predictor is weaker and take its prediction. */
2316 if (predictor && *predictor < predictor2)
2317 *predictor = predictor2;
2318 if (!new_val)
2319 return NULL;
2320 if (!val)
2321 val = new_val;
2322 else if (!operand_equal_p (val, new_val, false))
2323 return NULL;
2324 }
2325 return val;
2326 }
2327 if (is_gimple_assign (def))
2328 {
2329 if (gimple_assign_lhs (def) != op0)
2330 return NULL;
2331
2332 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2333 gimple_assign_rhs1 (def),
2334 gimple_assign_rhs_code (def),
2335 gimple_assign_rhs2 (def),
2336 visited, predictor);
2337 }
2338
2339 if (is_gimple_call (def))
2340 {
2341 tree decl = gimple_call_fndecl (def);
2342 if (!decl)
2343 {
2344 if (gimple_call_internal_p (def)
2345 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2346 {
2347 gcc_assert (gimple_call_num_args (def) == 3);
2348 tree val = gimple_call_arg (def, 0);
2349 if (TREE_CONSTANT (val))
2350 return val;
2351 if (predictor)
2352 {
2353 tree val2 = gimple_call_arg (def, 2);
2354 gcc_assert (TREE_CODE (val2) == INTEGER_CST
2355 && tree_fits_uhwi_p (val2)
2356 && tree_to_uhwi (val2) < END_PREDICTORS);
2357 *predictor = (enum br_predictor) tree_to_uhwi (val2);
2358 }
2359 return gimple_call_arg (def, 1);
2360 }
2361 return NULL;
2362 }
2363 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2364 switch (DECL_FUNCTION_CODE (decl))
2365 {
2366 case BUILT_IN_EXPECT:
2367 {
2368 tree val;
2369 if (gimple_call_num_args (def) != 2)
2370 return NULL;
2371 val = gimple_call_arg (def, 0);
2372 if (TREE_CONSTANT (val))
2373 return val;
2374 if (predictor)
2375 *predictor = PRED_BUILTIN_EXPECT;
2376 return gimple_call_arg (def, 1);
2377 }
2378
2379 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2380 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2381 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2382 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2383 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2384 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2385 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2386 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2387 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2388 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2389 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2390 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2391 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2392 /* Assume that any given atomic operation has low contention,
2393 and thus the compare-and-swap operation succeeds. */
2394 if (predictor)
2395 *predictor = PRED_COMPARE_AND_SWAP;
2396 return boolean_true_node;
2397 default:
2398 break;
2399 }
2400 }
2401
2402 return NULL;
2403 }
2404
2405 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2406 {
2407 tree res;
2408 enum br_predictor predictor2;
2409 op0 = expr_expected_value (op0, visited, predictor);
2410 if (!op0)
2411 return NULL;
2412 op1 = expr_expected_value (op1, visited, &predictor2);
2413 if (predictor && *predictor < predictor2)
2414 *predictor = predictor2;
2415 if (!op1)
2416 return NULL;
2417 res = fold_build2 (code, type, op0, op1);
2418 if (TREE_CONSTANT (res))
2419 return res;
2420 return NULL;
2421 }
2422 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2423 {
2424 tree res;
2425 op0 = expr_expected_value (op0, visited, predictor);
2426 if (!op0)
2427 return NULL;
2428 res = fold_build1 (code, type, op0);
2429 if (TREE_CONSTANT (res))
2430 return res;
2431 return NULL;
2432 }
2433 return NULL;
2434}
2435
2436/* Return constant EXPR will likely have at execution time, NULL if unknown.
2437 The function is used by builtin_expect branch predictor so the evidence
2438 must come from this construct and additional possible constant folding.
2439
2440 We may want to implement more involved value guess (such as value range
2441 propagation based prediction), but such tricks shall go to new
2442 implementation. */
2443
2444static tree
2445expr_expected_value (tree expr, bitmap visited,
2446 enum br_predictor *predictor)
2447{
2448 enum tree_code code;
2449 tree op0, op1;
2450
2451 if (TREE_CONSTANT (expr))
2452 {
2453 if (predictor)
2454 *predictor = PRED_UNCONDITIONAL;
2455 return expr;
2456 }
2457
2458 extract_ops_from_tree (expr, &code, &op0, &op1);
2459 return expr_expected_value_1 (TREE_TYPE (expr),
2460 op0, code, op1, visited, predictor);
2461}
2462
2463/* Predict using opcode of the last statement in basic block. */
2464static void
2465tree_predict_by_opcode (basic_block bb)
2466{
2467 gimple *stmt = last_stmt (bb);
2468 edge then_edge;
2469 tree op0, op1;
2470 tree type;
2471 tree val;
2472 enum tree_code cmp;
2473 edge_iterator ei;
2474 enum br_predictor predictor;
2475
2476 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2477 return;
2478 FOR_EACH_EDGE (then_edge, ei, bb->succs)
2479 if (then_edge->flags & EDGE_TRUE_VALUE)
2480 break;
2481 op0 = gimple_cond_lhs (stmt);
2482 op1 = gimple_cond_rhs (stmt);
2483 cmp = gimple_cond_code (stmt);
2484 type = TREE_TYPE (op0);
2485 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
2486 &predictor);
2487 if (val && TREE_CODE (val) == INTEGER_CST)
2488 {
2489 if (predictor == PRED_BUILTIN_EXPECT)
2490 {
2491 int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
2492
2493 gcc_assert (percent >= 0 && percent <= 100);
2494 if (integer_zerop (val))
2495 percent = 100 - percent;
2496 predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
2497 }
2498 else
2499 predict_edge_def (then_edge, predictor,
2500 integer_zerop (val) ? NOT_TAKEN : TAKEN);
2501 }
2502 /* Try "pointer heuristic."
2503 A comparison ptr == 0 is predicted as false.
2504 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2505 if (POINTER_TYPE_P (type))
2506 {
2507 if (cmp == EQ_EXPR)
2508 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2509 else if (cmp == NE_EXPR)
2510 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2511 }
2512 else
2513
2514 /* Try "opcode heuristic."
2515 EQ tests are usually false and NE tests are usually true. Also,
2516 most quantities are positive, so we can make the appropriate guesses
2517 about signed comparisons against zero. */
2518 switch (cmp)
2519 {
2520 case EQ_EXPR:
2521 case UNEQ_EXPR:
2522 /* Floating point comparisons appears to behave in a very
2523 unpredictable way because of special role of = tests in
2524 FP code. */
2525 if (FLOAT_TYPE_P (type))
2526 ;
2527 /* Comparisons with 0 are often used for booleans and there is
2528 nothing useful to predict about them. */
2529 else if (integer_zerop (op0) || integer_zerop (op1))
2530 ;
2531 else
2532 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2533 break;
2534
2535 case NE_EXPR:
2536 case LTGT_EXPR:
2537 /* Floating point comparisons appears to behave in a very
2538 unpredictable way because of special role of = tests in
2539 FP code. */
2540 if (FLOAT_TYPE_P (type))
2541 ;
2542 /* Comparisons with 0 are often used for booleans and there is
2543 nothing useful to predict about them. */
2544 else if (integer_zerop (op0)
2545 || integer_zerop (op1))
2546 ;
2547 else
2548 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2549 break;
2550
2551 case ORDERED_EXPR:
2552 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2553 break;
2554
2555 case UNORDERED_EXPR:
2556 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2557 break;
2558
2559 case LE_EXPR:
2560 case LT_EXPR:
2561 if (integer_zerop (op1)
2562 || integer_onep (op1)
2563 || integer_all_onesp (op1)
2564 || real_zerop (op1)
2565 || real_onep (op1)
2566 || real_minus_onep (op1))
2567 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2568 break;
2569
2570 case GE_EXPR:
2571 case GT_EXPR:
2572 if (integer_zerop (op1)
2573 || integer_onep (op1)
2574 || integer_all_onesp (op1)
2575 || real_zerop (op1)
2576 || real_onep (op1)
2577 || real_minus_onep (op1))
2578 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2579 break;
2580
2581 default:
2582 break;
2583 }
2584}
2585
2586/* Returns TRUE if the STMT is exit(0) like statement. */
2587
2588static bool
2589is_exit_with_zero_arg (const gimple *stmt)
2590{
2591 /* This is not exit, _exit or _Exit. */
2592 if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2593 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2594 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2595 return false;
2596
2597 /* Argument is an interger zero. */
2598 return integer_zerop (gimple_call_arg (stmt, 0));
2599}
2600
2601/* Try to guess whether the value of return means error code. */
2602
2603static enum br_predictor
2604return_prediction (tree val, enum prediction *prediction)
2605{
2606 /* VOID. */
2607 if (!val)
2608 return PRED_NO_PREDICTION;
2609 /* Different heuristics for pointers and scalars. */
2610 if (POINTER_TYPE_P (TREE_TYPE (val)))
2611 {
2612 /* NULL is usually not returned. */
2613 if (integer_zerop (val))
2614 {
2615 *prediction = NOT_TAKEN;
2616 return PRED_NULL_RETURN;
2617 }
2618 }
2619 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2620 {
2621 /* Negative return values are often used to indicate
2622 errors. */
2623 if (TREE_CODE (val) == INTEGER_CST
2624 && tree_int_cst_sgn (val) < 0)
2625 {
2626 *prediction = NOT_TAKEN;
2627 return PRED_NEGATIVE_RETURN;
2628 }
2629 /* Constant return values seems to be commonly taken.
2630 Zero/one often represent booleans so exclude them from the
2631 heuristics. */
2632 if (TREE_CONSTANT (val)
2633 && (!integer_zerop (val) && !integer_onep (val)))
2634 {
2635 *prediction = NOT_TAKEN;
2636 return PRED_CONST_RETURN;
2637 }
2638 }
2639 return PRED_NO_PREDICTION;
2640}
2641
2642/* Find the basic block with return expression and look up for possible
2643 return value trying to apply RETURN_PREDICTION heuristics. */
2644static void
2645apply_return_prediction (void)
2646{
2647 greturn *return_stmt = NULL;
2648 tree return_val;
2649 edge e;
2650 gphi *phi;
2651 int phi_num_args, i;
2652 enum br_predictor pred;
2653 enum prediction direction;
2654 edge_iterator ei;
2655
2656 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2657 {
2658 gimple *last = last_stmt (e->src);
2659 if (last
2660 && gimple_code (last) == GIMPLE_RETURN)
2661 {
2662 return_stmt = as_a <greturn *> (last);
2663 break;
2664 }
2665 }
2666 if (!e)
2667 return;
2668 return_val = gimple_return_retval (return_stmt);
2669 if (!return_val)
2670 return;
2671 if (TREE_CODE (return_val) != SSA_NAME
2672 || !SSA_NAME_DEF_STMT (return_val)
2673 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2674 return;
2675 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2676 phi_num_args = gimple_phi_num_args (phi);
2677 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2678
2679 /* Avoid the degenerate case where all return values form the function
2680 belongs to same category (ie they are all positive constants)
2681 so we can hardly say something about them. */
2682 for (i = 1; i < phi_num_args; i++)
2683 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2684 break;
2685 if (i != phi_num_args)
2686 for (i = 0; i < phi_num_args; i++)
2687 {
2688 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2689 if (pred != PRED_NO_PREDICTION)
2690 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2691 direction);
2692 }
2693}
2694
2695/* Look for basic block that contains unlikely to happen events
2696 (such as noreturn calls) and mark all paths leading to execution
2697 of this basic blocks as unlikely. */
2698
2699static void
2700tree_bb_level_predictions (void)
2701{
2702 basic_block bb;
2703 bool has_return_edges = false;
2704 edge e;
2705 edge_iterator ei;
2706
2707 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2708 if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
2709 {
2710 has_return_edges = true;
2711 break;
2712 }
2713
2714 apply_return_prediction ();
2715
2716 FOR_EACH_BB_FN (bb, cfun)
2717 {
2718 gimple_stmt_iterator gsi;
2719
2720 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2721 {
2722 gimple *stmt = gsi_stmt (gsi);
2723 tree decl;
2724
2725 if (is_gimple_call (stmt))
2726 {
2727 if (gimple_call_noreturn_p (stmt)
2728 && has_return_edges
2729 && !is_exit_with_zero_arg (stmt))
2730 predict_paths_leading_to (bb, PRED_NORETURN,
2731 NOT_TAKEN);
2732 decl = gimple_call_fndecl (stmt);
2733 if (decl
2734 && lookup_attribute ("cold",
2735 DECL_ATTRIBUTES (decl)))
2736 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2737 NOT_TAKEN);
2738 if (decl && recursive_call_p (current_function_decl, decl))
2739 predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
2740 NOT_TAKEN);
2741 }
2742 else if (gimple_code (stmt) == GIMPLE_PREDICT)
2743 {
2744 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2745 gimple_predict_outcome (stmt));
2746 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2747 hints to callers. */
2748 }
2749 }
2750 }
2751}
2752
2753/* Callback for hash_map::traverse, asserts that the pointer map is
2754 empty. */
2755
2756bool
2757assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2758 void *)
2759{
2760 gcc_assert (!value);
2761 return false;
2762}
2763
2764/* Predict branch probabilities and estimate profile for basic block BB.
2765 When LOCAL_ONLY is set do not use any global properties of CFG. */
2766
2767static void
2768tree_estimate_probability_bb (basic_block bb, bool local_only)
2769{
2770 edge e;
2771 edge_iterator ei;
2772
2773 FOR_EACH_EDGE (e, ei, bb->succs)
2774 {
2775 /* Look for block we are guarding (ie we dominate it,
2776 but it doesn't postdominate us). */
2777 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2778 && !local_only
2779 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2780 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2781 {
2782 gimple_stmt_iterator bi;
2783
2784 /* The call heuristic claims that a guarded function call
2785 is improbable. This is because such calls are often used
2786 to signal exceptional situations such as printing error
2787 messages. */
2788 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2789 gsi_next (&bi))
2790 {
2791 gimple *stmt = gsi_stmt (bi);
2792 if (is_gimple_call (stmt)
2793 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
2794 /* Constant and pure calls are hardly used to signalize
2795 something exceptional. */
2796 && gimple_has_side_effects (stmt))
2797 {
2798 if (gimple_call_fndecl (stmt))
2799 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2800 else if (virtual_method_call_p (gimple_call_fn (stmt)))
2801 predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
2802 else
2803 predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
2804 break;
2805 }
2806 }
2807 }
2808 }
2809 tree_predict_by_opcode (bb);
2810}
2811
2812/* Predict branch probabilities and estimate profile of the tree CFG.
2813 This function can be called from the loop optimizers to recompute
2814 the profile information.
2815 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2816
2817void
2818tree_estimate_probability (bool dry_run)
2819{
2820 basic_block bb;
2821
2822 add_noreturn_fake_exit_edges ();
2823 connect_infinite_loops_to_exit ();
2824 /* We use loop_niter_by_eval, which requires that the loops have
2825 preheaders. */
2826 create_preheaders (CP_SIMPLE_PREHEADERS);
2827 calculate_dominance_info (CDI_POST_DOMINATORS);
2828
2829 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2830 tree_bb_level_predictions ();
2831 record_loop_exits ();
2832
2833 if (number_of_loops (cfun) > 1)
2834 predict_loops ();
2835
2836 FOR_EACH_BB_FN (bb, cfun)
2837 tree_estimate_probability_bb (bb, false);
2838
2839 FOR_EACH_BB_FN (bb, cfun)
2840 combine_predictions_for_bb (bb, dry_run);
2841
2842 if (flag_checking)
2843 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2844
2845 delete bb_predictions;
2846 bb_predictions = NULL;
2847
2848 if (!dry_run)
2849 estimate_bb_frequencies (false);
2850 free_dominance_info (CDI_POST_DOMINATORS);
2851 remove_fake_exit_edges ();
2852}
2853
2854/* Set edge->probability for each successor edge of BB. */
2855void
2856tree_guess_outgoing_edge_probabilities (basic_block bb)
2857{
2858 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2859 tree_estimate_probability_bb (bb, true);
2860 combine_predictions_for_bb (bb, false);
2861 if (flag_checking)
2862 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2863 delete bb_predictions;
2864 bb_predictions = NULL;
2865}
2866
2867/* Predict edges to successors of CUR whose sources are not postdominated by
2868 BB by PRED and recurse to all postdominators. */
2869
2870static void
2871predict_paths_for_bb (basic_block cur, basic_block bb,
2872 enum br_predictor pred,
2873 enum prediction taken,
2874 bitmap visited, struct loop *in_loop = NULL)
2875{
2876 edge e;
2877 edge_iterator ei;
2878 basic_block son;
2879
2880 /* If we exited the loop or CUR is unconditional in the loop, there is
2881 nothing to do. */
2882 if (in_loop
2883 && (!flow_bb_inside_loop_p (in_loop, cur)
2884 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
2885 return;
2886
2887 /* We are looking for all edges forming edge cut induced by
2888 set of all blocks postdominated by BB. */
2889 FOR_EACH_EDGE (e, ei, cur->preds)
2890 if (e->src->index >= NUM_FIXED_BLOCKS
2891 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
2892 {
2893 edge e2;
2894 edge_iterator ei2;
2895 bool found = false;
2896
2897 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2898 if (unlikely_executed_edge_p (e))
2899 continue;
2900 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
2901
2902 /* See if there is an edge from e->src that is not abnormal
2903 and does not lead to BB and does not exit the loop. */
2904 FOR_EACH_EDGE (e2, ei2, e->src->succs)
2905 if (e2 != e
2906 && !unlikely_executed_edge_p (e2)
2907 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
2908 && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
2909 {
2910 found = true;
2911 break;
2912 }
2913
2914 /* If there is non-abnormal path leaving e->src, predict edge
2915 using predictor. Otherwise we need to look for paths
2916 leading to e->src.
2917
2918 The second may lead to infinite loop in the case we are predicitng
2919 regions that are only reachable by abnormal edges. We simply
2920 prevent visiting given BB twice. */
2921 if (found)
2922 {
2923 if (!edge_predicted_by_p (e, pred, taken))
2924 predict_edge_def (e, pred, taken);
2925 }
2926 else if (bitmap_set_bit (visited, e->src->index))
2927 predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
2928 }
2929 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
2930 son;
2931 son = next_dom_son (CDI_POST_DOMINATORS, son))
2932 predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
2933}
2934
2935/* Sets branch probabilities according to PREDiction and
2936 FLAGS. */
2937
2938static void
2939predict_paths_leading_to (basic_block bb, enum br_predictor pred,
2940 enum prediction taken, struct loop *in_loop)
2941{
2942 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
2943}
2944
2945/* Like predict_paths_leading_to but take edge instead of basic block. */
2946
2947static void
2948predict_paths_leading_to_edge (edge e, enum br_predictor pred,
2949 enum prediction taken, struct loop *in_loop)
2950{
2951 bool has_nonloop_edge = false;
2952 edge_iterator ei;
2953 edge e2;
2954
2955 basic_block bb = e->src;
2956 FOR_EACH_EDGE (e2, ei, bb->succs)
2957 if (e2->dest != e->src && e2->dest != e->dest
2958 && !unlikely_executed_edge_p (e)
2959 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
2960 {
2961 has_nonloop_edge = true;
2962 break;
2963 }
2964 if (!has_nonloop_edge)
2965 {
2966 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
2967 }
2968 else
2969 predict_edge_def (e, pred, taken);
2970}
2971
2972/* This is used to carry information about basic blocks. It is
2973 attached to the AUX field of the standard CFG block. */
2974
2975struct block_info
2976{
2977 /* Estimated frequency of execution of basic_block. */
2978 sreal frequency;
2979
2980 /* To keep queue of basic blocks to process. */
2981 basic_block next;
2982
2983 /* Number of predecessors we need to visit first. */
2984 int npredecessors;
2985};
2986
2987/* Similar information for edges. */
2988struct edge_prob_info
2989{
2990 /* In case edge is a loopback edge, the probability edge will be reached
2991 in case header is. Estimated number of iterations of the loop can be
2992 then computed as 1 / (1 - back_edge_prob). */
2993 sreal back_edge_prob;
2994 /* True if the edge is a loopback edge in the natural loop. */
2995 unsigned int back_edge:1;
2996};
2997
2998#define BLOCK_INFO(B) ((block_info *) (B)->aux)
2999#undef EDGE_INFO
3000#define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3001
3002/* Helper function for estimate_bb_frequencies.
3003 Propagate the frequencies in blocks marked in
3004 TOVISIT, starting in HEAD. */
3005
3006static void
3007propagate_freq (basic_block head, bitmap tovisit)
3008{
3009 basic_block bb;
3010 basic_block last;
3011 unsigned i;
3012 edge e;
3013 basic_block nextbb;
3014 bitmap_iterator bi;
3015
3016 /* For each basic block we need to visit count number of his predecessors
3017 we need to visit first. */
3018 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3019 {
3020 edge_iterator ei;
3021 int count = 0;
3022
3023 bb = BASIC_BLOCK_FOR_FN (cfun, i);
3024
3025 FOR_EACH_EDGE (e, ei, bb->preds)
3026 {
3027 bool visit = bitmap_bit_p (tovisit, e->src->index);
3028
3029 if (visit && !(e->flags & EDGE_DFS_BACK))
3030 count++;
3031 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3032 fprintf (dump_file,
3033 "Irreducible region hit, ignoring edge to %i->%i\n",
3034 e->src->index, bb->index);
3035 }
3036 BLOCK_INFO (bb)->npredecessors = count;
3037 /* When function never returns, we will never process exit block. */
3038 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3039 bb->count = profile_count::zero ();
3040 }
3041
3042 BLOCK_INFO (head)->frequency = 1;
3043 last = head;
3044 for (bb = head; bb; bb = nextbb)
3045 {
3046 edge_iterator ei;
3047 sreal cyclic_probability = 0;
3048 sreal frequency = 0;
3049
3050 nextbb = BLOCK_INFO (bb)->next;
3051 BLOCK_INFO (bb)->next = NULL;
3052
3053 /* Compute frequency of basic block. */
3054 if (bb != head)
3055 {
3056 if (flag_checking)
3057 FOR_EACH_EDGE (e, ei, bb->preds)
3058 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3059 || (e->flags & EDGE_DFS_BACK));
3060
3061 FOR_EACH_EDGE (e, ei, bb->preds)
3062 if (EDGE_INFO (e)->back_edge)
3063 {
3064 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3065 }
3066 else if (!(e->flags & EDGE_DFS_BACK))
3067 {
3068 /* frequency += (e->probability
3069 * BLOCK_INFO (e->src)->frequency /
3070 REG_BR_PROB_BASE); */
3071
3072 /* FIXME: Graphite is producing edges with no profile. Once
3073 this is fixed, drop this. */
3074 sreal tmp = e->probability.initialized_p () ?
3075 e->probability.to_reg_br_prob_base () : 0;
3076 tmp *= BLOCK_INFO (e->src)->frequency;
3077 tmp *= real_inv_br_prob_base;
3078 frequency += tmp;
3079 }
3080
3081 if (cyclic_probability == 0)
3082 {
3083 BLOCK_INFO (bb)->frequency = frequency;
3084 }
3085 else
3086 {
3087 if (cyclic_probability > real_almost_one)
3088 cyclic_probability = real_almost_one;
3089
3090 /* BLOCK_INFO (bb)->frequency = frequency
3091 / (1 - cyclic_probability) */
3092
3093 cyclic_probability = sreal (1) - cyclic_probability;
3094 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
3095 }
3096 }
3097
3098 bitmap_clear_bit (tovisit, bb->index);
3099
3100 e = find_edge (bb, head);
3101 if (e)
3102 {
3103 /* EDGE_INFO (e)->back_edge_prob
3104 = ((e->probability * BLOCK_INFO (bb)->frequency)
3105 / REG_BR_PROB_BASE); */
3106
3107 /* FIXME: Graphite is producing edges with no profile. Once
3108 this is fixed, drop this. */
3109 sreal tmp = e->probability.initialized_p () ?
3110 e->probability.to_reg_br_prob_base () : 0;
3111 tmp *= BLOCK_INFO (bb)->frequency;
3112 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
3113 }
3114
3115 /* Propagate to successor blocks. */
3116 FOR_EACH_EDGE (e, ei, bb->succs)
3117 if (!(e->flags & EDGE_DFS_BACK)
3118 && BLOCK_INFO (e->dest)->npredecessors)
3119 {
3120 BLOCK_INFO (e->dest)->npredecessors--;
3121 if (!BLOCK_INFO (e->dest)->npredecessors)
3122 {
3123 if (!nextbb)
3124 nextbb = e->dest;
3125 else
3126 BLOCK_INFO (last)->next = e->dest;
3127
3128 last = e->dest;
3129 }
3130 }
3131 }
3132}
3133
3134/* Estimate frequencies in loops at same nest level. */
3135
3136static void
3137estimate_loops_at_level (struct loop *first_loop)
3138{
3139 struct loop *loop;
3140
3141 for (loop = first_loop; loop; loop = loop->next)
3142 {
3143 edge e;
3144 basic_block *bbs;
3145 unsigned i;
3146 auto_bitmap tovisit;
3147
3148 estimate_loops_at_level (loop->inner);
3149
3150 /* Find current loop back edge and mark it. */
3151 e = loop_latch_edge (loop);
3152 EDGE_INFO (e)->back_edge = 1;
3153
3154 bbs = get_loop_body (loop);
3155 for (i = 0; i < loop->num_nodes; i++)
3156 bitmap_set_bit (tovisit, bbs[i]->index);
3157 free (bbs);
3158 propagate_freq (loop->header, tovisit);
3159 }
3160}
3161
3162/* Propagates frequencies through structure of loops. */
3163
3164static void
3165estimate_loops (void)
3166{
3167 auto_bitmap tovisit;
3168 basic_block bb;
3169
3170 /* Start by estimating the frequencies in the loops. */
3171 if (number_of_loops (cfun) > 1)
3172 estimate_loops_at_level (current_loops->tree_root->inner);
3173
3174 /* Now propagate the frequencies through all the blocks. */
3175 FOR_ALL_BB_FN (bb, cfun)
3176 {
3177 bitmap_set_bit (tovisit, bb->index);
3178 }
3179 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
3180}
3181
3182/* Drop the profile for NODE to guessed, and update its frequency based on
3183 whether it is expected to be hot given the CALL_COUNT. */
3184
3185static void
3186drop_profile (struct cgraph_node *node, profile_count call_count)
3187{
3188 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3189 /* In the case where this was called by another function with a
3190 dropped profile, call_count will be 0. Since there are no
3191 non-zero call counts to this function, we don't know for sure
3192 whether it is hot, and therefore it will be marked normal below. */
3193 bool hot = maybe_hot_count_p (NULL, call_count);
3194
3195 if (dump_file)
3196 fprintf (dump_file,
3197 "Dropping 0 profile for %s. %s based on calls.\n",
3198 node->dump_name (),
3199 hot ? "Function is hot" : "Function is normal");
3200 /* We only expect to miss profiles for functions that are reached
3201 via non-zero call edges in cases where the function may have
3202 been linked from another module or library (COMDATs and extern
3203 templates). See the comments below for handle_missing_profiles.
3204 Also, only warn in cases where the missing counts exceed the
3205 number of training runs. In certain cases with an execv followed
3206 by a no-return call the profile for the no-return call is not
3207 dumped and there can be a mismatch. */
3208 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3209 && call_count > profile_info->runs)
3210 {
3211 if (flag_profile_correction)
3212 {
3213 if (dump_file)
3214 fprintf (dump_file,
3215 "Missing counts for called function %s\n",
3216 node->dump_name ());
3217 }
3218 else
3219 warning (0, "Missing counts for called function %s",
3220 node->dump_name ());
3221 }
3222
3223 basic_block bb;
3224 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3225 if (flag_guess_branch_prob)
3226 {
3227 bool clear_zeros
3228 = ENTRY_BLOCK_PTR_FOR_FN
3229 (DECL_STRUCT_FUNCTION (node->decl))->count.nonzero_p ();
3230 FOR_ALL_BB_FN (bb, fn)
3231 if (clear_zeros || !(bb->count == profile_count::zero ()))
3232 bb->count = bb->count.guessed_local ();
3233 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max =
3234 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max.guessed_local ();
3235 }
3236 else
3237 {
3238 FOR_ALL_BB_FN (bb, fn)
3239 bb->count = profile_count::uninitialized ();
3240 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max
3241 = profile_count::uninitialized ();
3242 }
3243 pop_cfun ();
3244
3245 struct cgraph_edge *e;
3246 for (e = node->callees; e; e = e->next_callee)
3247 e->count = gimple_bb (e->call_stmt)->count;
3248 for (e = node->indirect_calls; e; e = e->next_callee)
3249 e->count = gimple_bb (e->call_stmt)->count;
3250
3251 profile_status_for_fn (fn)
3252 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3253 node->frequency
3254 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3255}
3256
3257/* In the case of COMDAT routines, multiple object files will contain the same
3258 function and the linker will select one for the binary. In that case
3259 all the other copies from the profile instrument binary will be missing
3260 profile counts. Look for cases where this happened, due to non-zero
3261 call counts going to 0-count functions, and drop the profile to guessed
3262 so that we can use the estimated probabilities and avoid optimizing only
3263 for size.
3264
3265 The other case where the profile may be missing is when the routine
3266 is not going to be emitted to the object file, e.g. for "extern template"
3267 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3268 all other cases of non-zero calls to 0-count functions. */
3269
3270void
3271handle_missing_profiles (void)
3272{
3273 struct cgraph_node *node;
3274 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
3275 auto_vec<struct cgraph_node *, 64> worklist;
3276
3277 /* See if 0 count function has non-0 count callers. In this case we
3278 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3279 FOR_EACH_DEFINED_FUNCTION (node)
3280 {
3281 struct cgraph_edge *e;
3282 profile_count call_count = profile_count::zero ();
3283 gcov_type max_tp_first_run = 0;
3284 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3285
3286 if (!(node->count == profile_count::zero ()))
3287 continue;
3288 for (e = node->callers; e; e = e->next_caller)
3289 if (e->count.initialized_p () && e->count > 0)
3290 {
3291 call_count = call_count + e->count;
3292
3293 if (e->caller->tp_first_run > max_tp_first_run)
3294 max_tp_first_run = e->caller->tp_first_run;
3295 }
3296
3297 /* If time profile is missing, let assign the maximum that comes from
3298 caller functions. */
3299 if (!node->tp_first_run && max_tp_first_run)
3300 node->tp_first_run = max_tp_first_run + 1;
3301
3302 if (call_count > 0
3303 && fn && fn->cfg
3304 && (call_count.apply_scale (unlikely_count_fraction, 1)
3305 >= profile_info->runs))
3306 {
3307 drop_profile (node, call_count);
3308 worklist.safe_push (node);
3309 }
3310 }
3311
3312 /* Propagate the profile dropping to other 0-count COMDATs that are
3313 potentially called by COMDATs we already dropped the profile on. */
3314 while (worklist.length () > 0)
3315 {
3316 struct cgraph_edge *e;
3317
3318 node = worklist.pop ();
3319 for (e = node->callees; e; e = e->next_caller)
3320 {
3321 struct cgraph_node *callee = e->callee;
3322 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3323
3324 if (callee->count > 0)
3325 continue;
3326 if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3327 && fn && fn->cfg
3328 && profile_status_for_fn (fn) == PROFILE_READ)
3329 {
3330 drop_profile (node, profile_count::zero ());
3331 worklist.safe_push (callee);
3332 }
3333 }
3334 }
3335}
3336
3337/* Convert counts measured by profile driven feedback to frequencies.
3338 Return nonzero iff there was any nonzero execution count. */
3339
3340bool
3341update_max_bb_count (void)
3342{
3343 profile_count true_count_max = profile_count::uninitialized ();
3344 basic_block bb;
3345
3346 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3347 true_count_max = true_count_max.max (bb->count);
3348
3349 cfun->cfg->count_max = true_count_max;
3350
3351 return true_count_max.ipa ().nonzero_p ();
3352}
3353
3354/* Return true if function is likely to be expensive, so there is no point to
3355 optimize performance of prologue, epilogue or do inlining at the expense
3356 of code size growth. THRESHOLD is the limit of number of instructions
3357 function can execute at average to be still considered not expensive. */
3358
3359bool
3360expensive_function_p (int threshold)
3361{
3362 basic_block bb;
3363
3364 /* If profile was scaled in a way entry block has count 0, then the function
3365 is deifnitly taking a lot of time. */
3366 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3367 return true;
3368
3369 profile_count limit = ENTRY_BLOCK_PTR_FOR_FN
3370 (cfun)->count.apply_scale (threshold, 1);
3371 profile_count sum = profile_count::zero ();
3372 FOR_EACH_BB_FN (bb, cfun)
3373 {
3374 rtx_insn *insn;
3375
3376 if (!bb->count.initialized_p ())
3377 {
3378 if (dump_file)
3379 fprintf (dump_file, "Function is considered expensive because"
3380 " count of bb %i is not initialized\n", bb->index);
3381 return true;
3382 }
3383
3384 FOR_BB_INSNS (bb, insn)
3385 if (active_insn_p (insn))
3386 {
3387 sum += bb->count;
3388 if (sum > limit)
3389 return true;
3390 }
3391 }
3392
3393 return false;
3394}
3395
3396/* All basic blocks that are reachable only from unlikely basic blocks are
3397 unlikely. */
3398
3399void
3400propagate_unlikely_bbs_forward (void)
3401{
3402 auto_vec<basic_block, 64> worklist;
3403 basic_block bb;
3404 edge_iterator ei;
3405 edge e;
3406
3407 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3408 {
3409 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3410 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3411
3412 while (worklist.length () > 0)
3413 {
3414 bb = worklist.pop ();
3415 FOR_EACH_EDGE (e, ei, bb->succs)
3416 if (!(e->count () == profile_count::zero ())
3417 && !(e->dest->count == profile_count::zero ())
3418 && !e->dest->aux)
3419 {
3420 e->dest->aux = (void *)(size_t) 1;
3421 worklist.safe_push (e->dest);
3422 }
3423 }
3424 }
3425
3426 FOR_ALL_BB_FN (bb, cfun)
3427 {
3428 if (!bb->aux)
3429 {
3430 if (!(bb->count == profile_count::zero ())
3431 && (dump_file && (dump_flags & TDF_DETAILS)))
3432 fprintf (dump_file,
3433 "Basic block %i is marked unlikely by forward prop\n",
3434 bb->index);
3435 bb->count = profile_count::zero ();
3436 }
3437 else
3438 bb->aux = NULL;
3439 }
3440}
3441
3442/* Determine basic blocks/edges that are known to be unlikely executed and set
3443 their counters to zero.
3444 This is done with first identifying obviously unlikely BBs/edges and then
3445 propagating in both directions. */
3446
3447static void
3448determine_unlikely_bbs ()
3449{
3450 basic_block bb;
3451 auto_vec<basic_block, 64> worklist;
3452 edge_iterator ei;
3453 edge e;
3454
3455 FOR_EACH_BB_FN (bb, cfun)
3456 {
3457 if (!(bb->count == profile_count::zero ())
3458 && unlikely_executed_bb_p (bb))
3459 {
3460 if (dump_file && (dump_flags & TDF_DETAILS))
3461 fprintf (dump_file, "Basic block %i is locally unlikely\n",
3462 bb->index);
3463 bb->count = profile_count::zero ();
3464 }
3465
3466 FOR_EACH_EDGE (e, ei, bb->succs)
3467 if (!(e->probability == profile_probability::never ())
3468 && unlikely_executed_edge_p (e))
3469 {
3470 if (dump_file && (dump_flags & TDF_DETAILS))
3471 fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3472 bb->index, e->dest->index);
3473 e->probability = profile_probability::never ();
3474 }
3475
3476 gcc_checking_assert (!bb->aux);
3477 }
3478 propagate_unlikely_bbs_forward ();
3479
3480 auto_vec<int, 64> nsuccs;
3481 nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun));
3482 FOR_ALL_BB_FN (bb, cfun)
3483 if (!(bb->count == profile_count::zero ())
3484 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3485 {
3486 nsuccs[bb->index] = 0;
3487 FOR_EACH_EDGE (e, ei, bb->succs)
3488 if (!(e->probability == profile_probability::never ())
3489 && !(e->dest->count == profile_count::zero ()))
3490 nsuccs[bb->index]++;
3491 if (!nsuccs[bb->index])
3492 worklist.safe_push (bb);
3493 }
3494 while (worklist.length () > 0)
3495 {
3496 bb = worklist.pop ();
3497 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3498 {
3499 bool found = false;
3500 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3501 !gsi_end_p (gsi); gsi_next (&gsi))
3502 if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
3503 /* stmt_can_terminate_bb_p special cases noreturns because it
3504 assumes that fake edges are created. We want to know that
3505 noreturn alone does not imply BB to be unlikely. */
3506 || (is_gimple_call (gsi_stmt (gsi))
3507 && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
3508 {
3509 found = true;
3510 break;
3511 }
3512 if (found)
3513 continue;
3514 }
3515 if (!(bb->count == profile_count::zero ())
3516 && (dump_file && (dump_flags & TDF_DETAILS)))
3517 fprintf (dump_file,
3518 "Basic block %i is marked unlikely by backward prop\n",
3519 bb->index);
3520 bb->count = profile_count::zero ();
3521 FOR_EACH_EDGE (e, ei, bb->preds)
3522 if (!(e->probability == profile_probability::never ()))
3523 {
3524 if (!(e->src->count == profile_count::zero ()))
3525 {
3526 nsuccs[e->src->index]--;
3527 if (!nsuccs[e->src->index])
3528 worklist.safe_push (e->src);
3529 }
3530 }
3531 }
3532 /* Finally all edges from non-0 regions to 0 are unlikely. */
3533 FOR_ALL_BB_FN (bb, cfun)
3534 if (!(bb->count == profile_count::zero ()))
3535 FOR_EACH_EDGE (e, ei, bb->succs)
3536 if (!(e->probability == profile_probability::never ())
3537 && e->dest->count == profile_count::zero ())
3538 {
3539 if (dump_file && (dump_flags & TDF_DETAILS))
3540 fprintf (dump_file, "Edge %i->%i is unlikely because "
3541 "it enters unlikely block\n",
3542 bb->index, e->dest->index);
3543 e->probability = profile_probability::never ();
3544 }
3545 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3546 cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3547}
3548
3549/* Estimate and propagate basic block frequencies using the given branch
3550 probabilities. If FORCE is true, the frequencies are used to estimate
3551 the counts even when there are already non-zero profile counts. */
3552
3553void
3554estimate_bb_frequencies (bool force)
3555{
3556 basic_block bb;
3557 sreal freq_max;
3558
3559 determine_unlikely_bbs ();
3560
3561 if (force || profile_status_for_fn (cfun) != PROFILE_READ
3562 || !update_max_bb_count ())
3563 {
3564 static int real_values_initialized = 0;
3565
3566 if (!real_values_initialized)
3567 {
3568 real_values_initialized = 1;
3569 real_br_prob_base = REG_BR_PROB_BASE;
3570 /* Scaling frequencies up to maximal profile count may result in
3571 frequent overflows especially when inlining loops.
3572 Small scalling results in unnecesary precision loss. Stay in
3573 the half of the (exponential) range. */
3574 real_bb_freq_max = (uint64_t)1 << (profile_count::n_bits / 2);
3575 real_one_half = sreal (1, -1);
3576 real_inv_br_prob_base = sreal (1) / real_br_prob_base;
3577 real_almost_one = sreal (1) - real_inv_br_prob_base;
3578 }
3579
3580 mark_dfs_back_edges ();
3581
3582 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3583 profile_probability::always ();
3584
3585 /* Set up block info for each basic block. */
3586 alloc_aux_for_blocks (sizeof (block_info));
3587 alloc_aux_for_edges (sizeof (edge_prob_info));
3588 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3589 {
3590 edge e;
3591 edge_iterator ei;
3592
3593 FOR_EACH_EDGE (e, ei, bb->succs)
3594 {
3595 /* FIXME: Graphite is producing edges with no profile. Once
3596 this is fixed, drop this. */
3597 if (e->probability.initialized_p ())
3598 EDGE_INFO (e)->back_edge_prob
3599 = e->probability.to_reg_br_prob_base ();
3600 else
3601 EDGE_INFO (e)->back_edge_prob = REG_BR_PROB_BASE / 2;
3602 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
3603 }
3604 }
3605
3606 /* First compute frequencies locally for each loop from innermost
3607 to outermost to examine frequencies for back edges. */
3608 estimate_loops ();
3609
3610 freq_max = 0;
3611 FOR_EACH_BB_FN (bb, cfun)
3612 if (freq_max < BLOCK_INFO (bb)->frequency)
3613 freq_max = BLOCK_INFO (bb)->frequency;
3614
3615 freq_max = real_bb_freq_max / freq_max;
3616 if (freq_max < 16)
3617 freq_max = 16;
3618 profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
3619 cfun->cfg->count_max = profile_count::uninitialized ();
3620 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3621 {
3622 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
3623 profile_count count = profile_count::from_gcov_type (tmp.to_int ());
3624
3625 /* If we have profile feedback in which this function was never
3626 executed, then preserve this info. */
3627 if (!(bb->count == profile_count::zero ()))
3628 bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
3629 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3630 }
3631
3632 free_aux_for_blocks ();
3633 free_aux_for_edges ();
3634 }
3635 compute_function_frequency ();
3636}
3637
3638/* Decide whether function is hot, cold or unlikely executed. */
3639void
3640compute_function_frequency (void)
3641{
3642 basic_block bb;
3643 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3644
3645 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3646 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
3647 node->only_called_at_startup = true;
3648 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
3649 node->only_called_at_exit = true;
3650
3651 if (profile_status_for_fn (cfun) != PROFILE_READ)
3652 {
3653 int flags = flags_from_decl_or_type (current_function_decl);
3654 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ()
3655 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3656 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
3657 != NULL)
3658 {
3659 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3660 warn_function_cold (current_function_decl);
3661 }
3662 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
3663 != NULL)
3664 node->frequency = NODE_FREQUENCY_HOT;
3665 else if (flags & ECF_NORETURN)
3666 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3667 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
3668 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3669 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3670 || DECL_STATIC_DESTRUCTOR (current_function_decl))
3671 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3672 return;
3673 }
3674
3675 /* Only first time try to drop function into unlikely executed.
3676 After inlining the roundoff errors may confuse us.
3677 Ipa-profile pass will drop functions only called from unlikely
3678 functions to unlikely and that is most of what we care about. */
3679 if (!cfun->after_inlining)
3680 {
3681 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3682 warn_function_cold (current_function_decl);
3683 }
3684 FOR_EACH_BB_FN (bb, cfun)
3685 {
3686 if (maybe_hot_bb_p (cfun, bb))
3687 {
3688 node->frequency = NODE_FREQUENCY_HOT;
3689 return;
3690 }
3691 if (!probably_never_executed_bb_p (cfun, bb))
3692 node->frequency = NODE_FREQUENCY_NORMAL;
3693 }
3694}
3695
3696/* Build PREDICT_EXPR. */
3697tree
3698build_predict_expr (enum br_predictor predictor, enum prediction taken)
3699{
3700 tree t = build1 (PREDICT_EXPR, void_type_node,
3701 build_int_cst (integer_type_node, predictor));
3702 SET_PREDICT_EXPR_OUTCOME (t, taken);
3703 return t;
3704}
3705
3706const char *
3707predictor_name (enum br_predictor predictor)
3708{
3709 return predictor_info[predictor].name;
3710}
3711
3712/* Predict branch probabilities and estimate profile of the tree CFG. */
3713
3714namespace {
3715
3716const pass_data pass_data_profile =
3717{
3718 GIMPLE_PASS, /* type */
3719 "profile_estimate", /* name */
3720 OPTGROUP_NONE, /* optinfo_flags */
3721 TV_BRANCH_PROB, /* tv_id */
3722 PROP_cfg, /* properties_required */
3723 0, /* properties_provided */
3724 0, /* properties_destroyed */
3725 0, /* todo_flags_start */
3726 0, /* todo_flags_finish */
3727};
3728
3729class pass_profile : public gimple_opt_pass
3730{
3731public:
3732 pass_profile (gcc::context *ctxt)
3733 : gimple_opt_pass (pass_data_profile, ctxt)
3734 {}
3735
3736 /* opt_pass methods: */
3737 virtual bool gate (function *) { return flag_guess_branch_prob; }
3738 virtual unsigned int execute (function *);
3739
3740}; // class pass_profile
3741
3742unsigned int
3743pass_profile::execute (function *fun)
3744{
3745 unsigned nb_loops;
3746
3747 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3748 return 0;
3749
3750 loop_optimizer_init (LOOPS_NORMAL);
3751 if (dump_file && (dump_flags & TDF_DETAILS))
3752 flow_loops_dump (dump_file, NULL, 0);
3753
3754 mark_irreducible_loops ();
3755
3756 nb_loops = number_of_loops (fun);
3757 if (nb_loops > 1)
3758 scev_initialize ();
3759
3760 tree_estimate_probability (false);
3761
3762 if (nb_loops > 1)
3763 scev_finalize ();
3764
3765 loop_optimizer_finalize ();
3766 if (dump_file && (dump_flags & TDF_DETAILS))
3767 gimple_dump_cfg (dump_file, dump_flags);
3768 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3769 profile_status_for_fn (fun) = PROFILE_GUESSED;
3770 if (dump_file && (dump_flags & TDF_DETAILS))
3771 {
3772 struct loop *loop;
3773 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3774 if (loop->header->count.initialized_p ())
3775 fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
3776 loop->num,
3777 (int)expected_loop_iterations_unbounded (loop));
3778 }
3779 return 0;
3780}
3781
3782} // anon namespace
3783
3784gimple_opt_pass *
3785make_pass_profile (gcc::context *ctxt)
3786{
3787 return new pass_profile (ctxt);
3788}
3789
3790namespace {
3791
3792const pass_data pass_data_strip_predict_hints =
3793{
3794 GIMPLE_PASS, /* type */
3795 "*strip_predict_hints", /* name */
3796 OPTGROUP_NONE, /* optinfo_flags */
3797 TV_BRANCH_PROB, /* tv_id */
3798 PROP_cfg, /* properties_required */
3799 0, /* properties_provided */
3800 0, /* properties_destroyed */
3801 0, /* todo_flags_start */
3802 0, /* todo_flags_finish */
3803};
3804
3805class pass_strip_predict_hints : public gimple_opt_pass
3806{
3807public:
3808 pass_strip_predict_hints (gcc::context *ctxt)
3809 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
3810 {}
3811
3812 /* opt_pass methods: */
3813 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
3814 virtual unsigned int execute (function *);
3815
3816}; // class pass_strip_predict_hints
3817
3818/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3819 we no longer need. */
3820unsigned int
3821pass_strip_predict_hints::execute (function *fun)
3822{
3823 basic_block bb;
3824 gimple *ass_stmt;
3825 tree var;
3826 bool changed = false;
3827
3828 FOR_EACH_BB_FN (bb, fun)
3829 {
3830 gimple_stmt_iterator bi;
3831 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3832 {
3833 gimple *stmt = gsi_stmt (bi);
3834
3835 if (gimple_code (stmt) == GIMPLE_PREDICT)
3836 {
3837 gsi_remove (&bi, true);
3838 changed = true;
3839 continue;
3840 }
3841 else if (is_gimple_call (stmt))
3842 {
3843 tree fndecl = gimple_call_fndecl (stmt);
3844
3845 if ((fndecl
3846 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
3847 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
3848 && gimple_call_num_args (stmt) == 2)
3849 || (gimple_call_internal_p (stmt)
3850 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
3851 {
3852 var = gimple_call_lhs (stmt);
3853 changed = true;
3854 if (var)
3855 {
3856 ass_stmt
3857 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
3858 gsi_replace (&bi, ass_stmt, true);
3859 }
3860 else
3861 {
3862 gsi_remove (&bi, true);
3863 continue;
3864 }
3865 }
3866 }
3867 gsi_next (&bi);
3868 }
3869 }
3870 return changed ? TODO_cleanup_cfg : 0;
3871}
3872
3873} // anon namespace
3874
3875gimple_opt_pass *
3876make_pass_strip_predict_hints (gcc::context *ctxt)
3877{
3878 return new pass_strip_predict_hints (ctxt);
3879}
3880
3881/* Rebuild function frequencies. Passes are in general expected to
3882 maintain profile by hand, however in some cases this is not possible:
3883 for example when inlining several functions with loops freuqencies might run
3884 out of scale and thus needs to be recomputed. */
3885
3886void
3887rebuild_frequencies (void)
3888{
3889 timevar_push (TV_REBUILD_FREQUENCIES);
3890
3891 /* When the max bb count in the function is small, there is a higher
3892 chance that there were truncation errors in the integer scaling
3893 of counts by inlining and other optimizations. This could lead
3894 to incorrect classification of code as being cold when it isn't.
3895 In that case, force the estimation of bb counts/frequencies from the
3896 branch probabilities, rather than computing frequencies from counts,
3897 which may also lead to frequencies incorrectly reduced to 0. There
3898 is less precision in the probabilities, so we only do this for small
3899 max counts. */
3900 cfun->cfg->count_max = profile_count::uninitialized ();
3901 basic_block bb;
3902 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3903 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3904
3905 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3906 {
3907 loop_optimizer_init (0);
3908 add_noreturn_fake_exit_edges ();
3909 mark_irreducible_loops ();
3910 connect_infinite_loops_to_exit ();
3911 estimate_bb_frequencies (true);
3912 remove_fake_exit_edges ();
3913 loop_optimizer_finalize ();
3914 }
3915 else if (profile_status_for_fn (cfun) == PROFILE_READ)
3916 update_max_bb_count ();
3917 else
3918 gcc_unreachable ();
3919 timevar_pop (TV_REBUILD_FREQUENCIES);
3920}
3921
3922/* Perform a dry run of the branch prediction pass and report comparsion of
3923 the predicted and real profile into the dump file. */
3924
3925void
3926report_predictor_hitrates (void)
3927{
3928 unsigned nb_loops;
3929
3930 loop_optimizer_init (LOOPS_NORMAL);
3931 if (dump_file && (dump_flags & TDF_DETAILS))
3932 flow_loops_dump (dump_file, NULL, 0);
3933
3934 mark_irreducible_loops ();
3935
3936 nb_loops = number_of_loops (cfun);
3937 if (nb_loops > 1)
3938 scev_initialize ();
3939
3940 tree_estimate_probability (true);
3941
3942 if (nb_loops > 1)
3943 scev_finalize ();
3944
3945 loop_optimizer_finalize ();
3946}
3947
3948/* Force edge E to be cold.
3949 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3950 keep low probability to represent possible error in a guess. This is used
3951 i.e. in case we predict loop to likely iterate given number of times but
3952 we are not 100% sure.
3953
3954 This function locally updates profile without attempt to keep global
3955 consistency which can not be reached in full generality without full profile
3956 rebuild from probabilities alone. Doing so is not necessarily a good idea
3957 because frequencies and counts may be more realistic then probabilities.
3958
3959 In some cases (such as for elimination of early exits during full loop
3960 unrolling) the caller can ensure that profile will get consistent
3961 afterwards. */
3962
3963void
3964force_edge_cold (edge e, bool impossible)
3965{
3966 profile_count count_sum = profile_count::zero ();
3967 profile_probability prob_sum = profile_probability::never ();
3968 edge_iterator ei;
3969 edge e2;
3970 bool uninitialized_exit = false;
3971
3972 profile_probability goal = (impossible ? profile_probability::never ()
3973 : profile_probability::very_unlikely ());
3974
3975 /* If edge is already improbably or cold, just return. */
3976 if (e->probability <= goal
3977 && (!impossible || e->count () == profile_count::zero ()))
3978 return;
3979 FOR_EACH_EDGE (e2, ei, e->src->succs)
3980 if (e2 != e)
3981 {
3982 if (e2->count ().initialized_p ())
3983 count_sum += e2->count ();
3984 else
3985 uninitialized_exit = true;
3986 if (e2->probability.initialized_p ())
3987 prob_sum += e2->probability;
3988 }
3989
3990 /* If there are other edges out of e->src, redistribute probabilitity
3991 there. */
3992 if (prob_sum > profile_probability::never ())
3993 {
3994 if (!(e->probability < goal))
3995 e->probability = goal;
3996
3997 profile_probability prob_comp = prob_sum / e->probability.invert ();
3998
3999 if (dump_file && (dump_flags & TDF_DETAILS))
4000 fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4001 "probability to other edges.\n",
4002 e->src->index, e->dest->index,
4003 impossible ? "impossible" : "cold");
4004 FOR_EACH_EDGE (e2, ei, e->src->succs)
4005 if (e2 != e)
4006 {
4007 e2->probability /= prob_comp;
4008 }
4009 if (current_ir_type () != IR_GIMPLE
4010 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4011 update_br_prob_note (e->src);
4012 }
4013 /* If all edges out of e->src are unlikely, the basic block itself
4014 is unlikely. */
4015 else
4016 {
4017 if (prob_sum == profile_probability::never ())
4018 e->probability = profile_probability::always ();
4019 else
4020 {
4021 if (impossible)
4022 e->probability = profile_probability::never ();
4023 /* If BB has some edges out that are not impossible, we can not
4024 assume that BB itself is. */
4025 impossible = false;
4026 }
4027 if (current_ir_type () != IR_GIMPLE
4028 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4029 update_br_prob_note (e->src);
4030 if (e->src->count == profile_count::zero ())
4031 return;
4032 if (count_sum == profile_count::zero () && !uninitialized_exit
4033 && impossible)
4034 {
4035 bool found = false;
4036 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4037 ;
4038 else if (current_ir_type () == IR_GIMPLE)
4039 for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4040 !gsi_end_p (gsi); gsi_next (&gsi))
4041 {
4042 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4043 {
4044 found = true;
4045 break;
4046 }
4047 }
4048 /* FIXME: Implement RTL path. */
4049 else
4050 found = true;
4051 if (!found)
4052 {
4053 if (dump_file && (dump_flags & TDF_DETAILS))
4054 fprintf (dump_file,
4055 "Making bb %i impossible and dropping count to 0.\n",
4056 e->src->index);
4057 e->src->count = profile_count::zero ();
4058 FOR_EACH_EDGE (e2, ei, e->src->preds)
4059 force_edge_cold (e2, impossible);
4060 return;
4061 }
4062 }
4063
4064 /* If we did not adjusting, the source basic block has no likely edeges
4065 leaving other direction. In that case force that bb cold, too.
4066 This in general is difficult task to do, but handle special case when
4067 BB has only one predecestor. This is common case when we are updating
4068 after loop transforms. */
4069 if (!(prob_sum > profile_probability::never ())
4070 && count_sum == profile_count::zero ()
4071 && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4072 > (impossible ? 0 : 1))
4073 {
4074 int old_frequency = e->src->count.to_frequency (cfun);
4075 if (dump_file && (dump_flags & TDF_DETAILS))
4076 fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4077 impossible ? "impossible" : "cold");
4078 int new_frequency = MIN (e->src->count.to_frequency (cfun),
4079 impossible ? 0 : 1);
4080 if (impossible)
4081 e->src->count = profile_count::zero ();
4082 else
4083 e->src->count = e->count ().apply_scale (new_frequency,
4084 old_frequency);
4085 force_edge_cold (single_pred_edge (e->src), impossible);
4086 }
4087 else if (dump_file && (dump_flags & TDF_DETAILS)
4088 && maybe_hot_bb_p (cfun, e->src))
4089 fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4090 impossible ? "impossible" : "cold");
4091 }
4092}
4093
4094#if CHECKING_P
4095
4096namespace selftest {
4097
4098/* Test that value range of predictor values defined in predict.def is
4099 within range (50, 100]. */
4100
4101struct branch_predictor
4102{
4103 const char *name;
4104 unsigned probability;
4105};
4106
4107#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4108
4109static void
4110test_prediction_value_range ()
4111{
4112 branch_predictor predictors[] = {
4113#include "predict.def"
4114 {NULL, -1U}
4115 };
4116
4117 for (unsigned i = 0; predictors[i].name != NULL; i++)
4118 {
4119 unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4120 ASSERT_TRUE (p > 50 && p <= 100);
4121 }
4122}
4123
4124#undef DEF_PREDICTOR
4125
4126/* Run all of the selfests within this file. */
4127
4128void
4129predict_c_tests ()
4130{
4131 test_prediction_value_range ();
4132}
4133
4134} // namespace selftest
4135#endif /* CHECKING_P. */
4136