Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / predict.c
1 /* Branch prediction routines for the GNU compiler.
2    Copyright (C) 2000-2015 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19
20 /* References:
21
22    [1] "Branch Prediction for Free"
23        Ball and Larus; PLDI '93.
24    [2] "Static Branch Frequency and Program Profile Analysis"
25        Wu and Larus; MICRO-27.
26    [3] "Corpus-based Static Branch Prediction"
27        Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */
28
29
30 #include "config.h"
31 #include "system.h"
32 #include "coretypes.h"
33 #include "tm.h"
34 #include "hash-set.h"
35 #include "machmode.h"
36 #include "vec.h"
37 #include "double-int.h"
38 #include "input.h"
39 #include "alias.h"
40 #include "symtab.h"
41 #include "wide-int.h"
42 #include "inchash.h"
43 #include "tree.h"
44 #include "fold-const.h"
45 #include "calls.h"
46 #include "rtl.h"
47 #include "tm_p.h"
48 #include "hard-reg-set.h"
49 #include "predict.h"
50 #include "function.h"
51 #include "dominance.h"
52 #include "cfg.h"
53 #include "cfganal.h"
54 #include "basic-block.h"
55 #include "insn-config.h"
56 #include "regs.h"
57 #include "flags.h"
58 #include "profile.h"
59 #include "except.h"
60 #include "diagnostic-core.h"
61 #include "recog.h"
62 #include "hashtab.h"
63 #include "statistics.h"
64 #include "real.h"
65 #include "fixed-value.h"
66 #include "expmed.h"
67 #include "dojump.h"
68 #include "explow.h"
69 #include "emit-rtl.h"
70 #include "varasm.h"
71 #include "stmt.h"
72 #include "expr.h"
73 #include "coverage.h"
74 #include "sreal.h"
75 #include "params.h"
76 #include "target.h"
77 #include "cfgloop.h"
78 #include "hash-map.h"
79 #include "tree-ssa-alias.h"
80 #include "internal-fn.h"
81 #include "gimple-expr.h"
82 #include "is-a.h"
83 #include "gimple.h"
84 #include "gimple-iterator.h"
85 #include "gimple-ssa.h"
86 #include "plugin-api.h"
87 #include "ipa-ref.h"
88 #include "cgraph.h"
89 #include "tree-cfg.h"
90 #include "tree-phinodes.h"
91 #include "ssa-iterators.h"
92 #include "tree-ssa-loop-niter.h"
93 #include "tree-ssa-loop.h"
94 #include "tree-pass.h"
95 #include "tree-scalar-evolution.h"
96
97 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
98                    1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.  */
99 static sreal real_almost_one, real_br_prob_base,
100              real_inv_br_prob_base, real_one_half, real_bb_freq_max;
101
102 static void combine_predictions_for_insn (rtx_insn *, basic_block);
103 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
104 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
105 static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
106 static bool can_predict_insn_p (const rtx_insn *);
107
108 /* Information we hold about each branch predictor.
109    Filled using information from predict.def.  */
110
111 struct predictor_info
112 {
113   const char *const name;       /* Name used in the debugging dumps.  */
114   const int hitrate;            /* Expected hitrate used by
115                                    predict_insn_def call.  */
116   const int flags;
117 };
118
119 /* Use given predictor without Dempster-Shaffer theory if it matches
120    using first_match heuristics.  */
121 #define PRED_FLAG_FIRST_MATCH 1
122
123 /* Recompute hitrate in percent to our representation.  */
124
125 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
126
127 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
128 static const struct predictor_info predictor_info[]= {
129 #include "predict.def"
130
131   /* Upper bound on predictors.  */
132   {NULL, 0, 0}
133 };
134 #undef DEF_PREDICTOR
135
136 /* Return TRUE if frequency FREQ is considered to be hot.  */
137
138 static inline bool
139 maybe_hot_frequency_p (struct function *fun, int freq)
140 {
141   struct cgraph_node *node = cgraph_node::get (fun->decl);
142   if (!profile_info
143       || !opt_for_fn (fun->decl, flag_branch_probabilities))
144     {
145       if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
146         return false;
147       if (node->frequency == NODE_FREQUENCY_HOT)
148         return true;
149     }
150   if (profile_status_for_fn (fun) == PROFILE_ABSENT)
151     return true;
152   if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
153       && freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency * 2 / 3))
154     return false;
155   if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
156     return false;
157   if (freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency
158               / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
159     return false;
160   return true;
161 }
162
163 static gcov_type min_count = -1;
164
165 /* Determine the threshold for hot BB counts.  */
166
167 gcov_type
168 get_hot_bb_threshold ()
169 {
170   gcov_working_set_t *ws;
171   if (min_count == -1)
172     {
173       ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
174       gcc_assert (ws);
175       min_count = ws->min_counter;
176     }
177   return min_count;
178 }
179
180 /* Set the threshold for hot BB counts.  */
181
182 void
183 set_hot_bb_threshold (gcov_type min)
184 {
185   min_count = min;
186 }
187
188 /* Return TRUE if frequency FREQ is considered to be hot.  */
189
190 bool
191 maybe_hot_count_p (struct function *fun, gcov_type count)
192 {
193   if (fun && profile_status_for_fn (fun) != PROFILE_READ)
194     return true;
195   /* Code executed at most once is not hot.  */
196   if (profile_info->runs >= count)
197     return false;
198   return (count >= get_hot_bb_threshold ());
199 }
200
201 /* Return true in case BB can be CPU intensive and should be optimized
202    for maximal performance.  */
203
204 bool
205 maybe_hot_bb_p (struct function *fun, const_basic_block bb)
206 {
207   gcc_checking_assert (fun);
208   if (profile_status_for_fn (fun) == PROFILE_READ)
209     return maybe_hot_count_p (fun, bb->count);
210   return maybe_hot_frequency_p (fun, bb->frequency);
211 }
212
213 /* Return true in case BB can be CPU intensive and should be optimized
214    for maximal performance.  */
215
216 bool
217 maybe_hot_edge_p (edge e)
218 {
219   if (profile_status_for_fn (cfun) == PROFILE_READ)
220     return maybe_hot_count_p (cfun, e->count);
221   return maybe_hot_frequency_p (cfun, EDGE_FREQUENCY (e));
222 }
223
224 /* Return true if profile COUNT and FREQUENCY, or function FUN static
225    node frequency reflects never being executed.  */
226    
227 static bool
228 probably_never_executed (struct function *fun,
229                          gcov_type count, int frequency)
230 {
231   gcc_checking_assert (fun);
232   if (profile_status_for_fn (fun) == PROFILE_READ)
233     {
234       int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
235       if (count * unlikely_count_fraction >= profile_info->runs)
236         return false;
237       if (!frequency)
238         return true;
239       if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
240         return false;
241       if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
242         {
243           gcov_type computed_count;
244           /* Check for possibility of overflow, in which case entry bb count
245              is large enough to do the division first without losing much
246              precision.  */
247           if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count < REG_BR_PROB_BASE *
248               REG_BR_PROB_BASE)
249             {
250               gcov_type scaled_count
251                   = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count *
252              unlikely_count_fraction;
253               computed_count = RDIV (scaled_count,
254                                      ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
255             }
256           else
257             {
258               computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun)->count,
259                                      ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
260               computed_count *= frequency * unlikely_count_fraction;
261             }
262           if (computed_count >= profile_info->runs)
263             return false;
264         }
265       return true;
266     }
267   if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities)))
268       && (cgraph_node::get (fun->decl)->frequency
269           == NODE_FREQUENCY_UNLIKELY_EXECUTED))
270     return true;
271   return false;
272 }
273
274
275 /* Return true in case BB is probably never executed.  */
276
277 bool
278 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
279 {
280   return probably_never_executed (fun, bb->count, bb->frequency);
281 }
282
283
284 /* Return true in case edge E is probably never executed.  */
285
286 bool
287 probably_never_executed_edge_p (struct function *fun, edge e)
288 {
289   return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
290 }
291
292 /* Return true when current function should always be optimized for size.  */
293
294 bool
295 optimize_function_for_size_p (struct function *fun)
296 {
297   if (!fun || !fun->decl)
298     return optimize_size;
299   cgraph_node *n = cgraph_node::get (fun->decl);
300   return n && n->optimize_for_size_p ();
301 }
302
303 /* Return true when current function should always be optimized for speed.  */
304
305 bool
306 optimize_function_for_speed_p (struct function *fun)
307 {
308   return !optimize_function_for_size_p (fun);
309 }
310
311 /* Return TRUE when BB should be optimized for size.  */
312
313 bool
314 optimize_bb_for_size_p (const_basic_block bb)
315 {
316   return (optimize_function_for_size_p (cfun)
317           || (bb && !maybe_hot_bb_p (cfun, bb)));
318 }
319
320 /* Return TRUE when BB should be optimized for speed.  */
321
322 bool
323 optimize_bb_for_speed_p (const_basic_block bb)
324 {
325   return !optimize_bb_for_size_p (bb);
326 }
327
328 /* Return TRUE when BB should be optimized for size.  */
329
330 bool
331 optimize_edge_for_size_p (edge e)
332 {
333   return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
334 }
335
336 /* Return TRUE when BB should be optimized for speed.  */
337
338 bool
339 optimize_edge_for_speed_p (edge e)
340 {
341   return !optimize_edge_for_size_p (e);
342 }
343
344 /* Return TRUE when BB should be optimized for size.  */
345
346 bool
347 optimize_insn_for_size_p (void)
348 {
349   return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
350 }
351
352 /* Return TRUE when BB should be optimized for speed.  */
353
354 bool
355 optimize_insn_for_speed_p (void)
356 {
357   return !optimize_insn_for_size_p ();
358 }
359
360 /* Return TRUE when LOOP should be optimized for size.  */
361
362 bool
363 optimize_loop_for_size_p (struct loop *loop)
364 {
365   return optimize_bb_for_size_p (loop->header);
366 }
367
368 /* Return TRUE when LOOP should be optimized for speed.  */
369
370 bool
371 optimize_loop_for_speed_p (struct loop *loop)
372 {
373   return optimize_bb_for_speed_p (loop->header);
374 }
375
376 /* Return TRUE when LOOP nest should be optimized for speed.  */
377
378 bool
379 optimize_loop_nest_for_speed_p (struct loop *loop)
380 {
381   struct loop *l = loop;
382   if (optimize_loop_for_speed_p (loop))
383     return true;
384   l = loop->inner;
385   while (l && l != loop)
386     {
387       if (optimize_loop_for_speed_p (l))
388         return true;
389       if (l->inner)
390         l = l->inner;
391       else if (l->next)
392         l = l->next;
393       else
394         {
395           while (l != loop && !l->next)
396             l = loop_outer (l);
397           if (l != loop)
398             l = l->next;
399         }
400     }
401   return false;
402 }
403
404 /* Return TRUE when LOOP nest should be optimized for size.  */
405
406 bool
407 optimize_loop_nest_for_size_p (struct loop *loop)
408 {
409   return !optimize_loop_nest_for_speed_p (loop);
410 }
411
412 /* Return true when edge E is likely to be well predictable by branch
413    predictor.  */
414
415 bool
416 predictable_edge_p (edge e)
417 {
418   if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
419     return false;
420   if ((e->probability
421        <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
422       || (REG_BR_PROB_BASE - e->probability
423           <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
424     return true;
425   return false;
426 }
427
428
429 /* Set RTL expansion for BB profile.  */
430
431 void
432 rtl_profile_for_bb (basic_block bb)
433 {
434   crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
435 }
436
437 /* Set RTL expansion for edge profile.  */
438
439 void
440 rtl_profile_for_edge (edge e)
441 {
442   crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
443 }
444
445 /* Set RTL expansion to default mode (i.e. when profile info is not known).  */
446 void
447 default_rtl_profile (void)
448 {
449   crtl->maybe_hot_insn_p = true;
450 }
451
452 /* Return true if the one of outgoing edges is already predicted by
453    PREDICTOR.  */
454
455 bool
456 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
457 {
458   rtx note;
459   if (!INSN_P (BB_END (bb)))
460     return false;
461   for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
462     if (REG_NOTE_KIND (note) == REG_BR_PRED
463         && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
464       return true;
465   return false;
466 }
467
468 /*  Structure representing predictions in tree level. */
469
470 struct edge_prediction {
471     struct edge_prediction *ep_next;
472     edge ep_edge;
473     enum br_predictor ep_predictor;
474     int ep_probability;
475 };
476
477 /* This map contains for a basic block the list of predictions for the
478    outgoing edges.  */
479
480 static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
481
482 /* Return true if the one of outgoing edges is already predicted by
483    PREDICTOR.  */
484
485 bool
486 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
487 {
488   struct edge_prediction *i;
489   edge_prediction **preds = bb_predictions->get (bb);
490
491   if (!preds)
492     return false;
493
494   for (i = *preds; i; i = i->ep_next)
495     if (i->ep_predictor == predictor)
496       return true;
497   return false;
498 }
499
500 /* Return true when the probability of edge is reliable.
501
502    The profile guessing code is good at predicting branch outcome (ie.
503    taken/not taken), that is predicted right slightly over 75% of time.
504    It is however notoriously poor on predicting the probability itself.
505    In general the profile appear a lot flatter (with probabilities closer
506    to 50%) than the reality so it is bad idea to use it to drive optimization
507    such as those disabling dynamic branch prediction for well predictable
508    branches.
509
510    There are two exceptions - edges leading to noreturn edges and edges
511    predicted by number of iterations heuristics are predicted well.  This macro
512    should be able to distinguish those, but at the moment it simply check for
513    noreturn heuristic that is only one giving probability over 99% or bellow
514    1%.  In future we might want to propagate reliability information across the
515    CFG if we find this information useful on multiple places.   */
516 static bool
517 probability_reliable_p (int prob)
518 {
519   return (profile_status_for_fn (cfun) == PROFILE_READ
520           || (profile_status_for_fn (cfun) == PROFILE_GUESSED
521               && (prob <= HITRATE (1) || prob >= HITRATE (99))));
522 }
523
524 /* Same predicate as above, working on edges.  */
525 bool
526 edge_probability_reliable_p (const_edge e)
527 {
528   return probability_reliable_p (e->probability);
529 }
530
531 /* Same predicate as edge_probability_reliable_p, working on notes.  */
532 bool
533 br_prob_note_reliable_p (const_rtx note)
534 {
535   gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
536   return probability_reliable_p (XINT (note, 0));
537 }
538
539 static void
540 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
541 {
542   gcc_assert (any_condjump_p (insn));
543   if (!flag_guess_branch_prob)
544     return;
545
546   add_reg_note (insn, REG_BR_PRED,
547                 gen_rtx_CONCAT (VOIDmode,
548                                 GEN_INT ((int) predictor),
549                                 GEN_INT ((int) probability)));
550 }
551
552 /* Predict insn by given predictor.  */
553
554 void
555 predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
556                   enum prediction taken)
557 {
558    int probability = predictor_info[(int) predictor].hitrate;
559
560    if (taken != TAKEN)
561      probability = REG_BR_PROB_BASE - probability;
562
563    predict_insn (insn, predictor, probability);
564 }
565
566 /* Predict edge E with given probability if possible.  */
567
568 void
569 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
570 {
571   rtx_insn *last_insn;
572   last_insn = BB_END (e->src);
573
574   /* We can store the branch prediction information only about
575      conditional jumps.  */
576   if (!any_condjump_p (last_insn))
577     return;
578
579   /* We always store probability of branching.  */
580   if (e->flags & EDGE_FALLTHRU)
581     probability = REG_BR_PROB_BASE - probability;
582
583   predict_insn (last_insn, predictor, probability);
584 }
585
586 /* Predict edge E with the given PROBABILITY.  */
587 void
588 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
589 {
590   gcc_assert (profile_status_for_fn (cfun) != PROFILE_GUESSED);
591   if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && EDGE_COUNT (e->src->succs) >
592        1)
593       && flag_guess_branch_prob && optimize)
594     {
595       struct edge_prediction *i = XNEW (struct edge_prediction);
596       edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
597
598       i->ep_next = preds;
599       preds = i;
600       i->ep_probability = probability;
601       i->ep_predictor = predictor;
602       i->ep_edge = e;
603     }
604 }
605
606 /* Remove all predictions on given basic block that are attached
607    to edge E.  */
608 void
609 remove_predictions_associated_with_edge (edge e)
610 {
611   if (!bb_predictions)
612     return;
613
614   edge_prediction **preds = bb_predictions->get (e->src);
615
616   if (preds)
617     {
618       struct edge_prediction **prediction = preds;
619       struct edge_prediction *next;
620
621       while (*prediction)
622         {
623           if ((*prediction)->ep_edge == e)
624             {
625               next = (*prediction)->ep_next;
626               free (*prediction);
627               *prediction = next;
628             }
629           else
630             prediction = &((*prediction)->ep_next);
631         }
632     }
633 }
634
635 /* Clears the list of predictions stored for BB.  */
636
637 static void
638 clear_bb_predictions (basic_block bb)
639 {
640   edge_prediction **preds = bb_predictions->get (bb);
641   struct edge_prediction *pred, *next;
642
643   if (!preds)
644     return;
645
646   for (pred = *preds; pred; pred = next)
647     {
648       next = pred->ep_next;
649       free (pred);
650     }
651   *preds = NULL;
652 }
653
654 /* Return true when we can store prediction on insn INSN.
655    At the moment we represent predictions only on conditional
656    jumps, not at computed jump or other complicated cases.  */
657 static bool
658 can_predict_insn_p (const rtx_insn *insn)
659 {
660   return (JUMP_P (insn)
661           && any_condjump_p (insn)
662           && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
663 }
664
665 /* Predict edge E by given predictor if possible.  */
666
667 void
668 predict_edge_def (edge e, enum br_predictor predictor,
669                   enum prediction taken)
670 {
671    int probability = predictor_info[(int) predictor].hitrate;
672
673    if (taken != TAKEN)
674      probability = REG_BR_PROB_BASE - probability;
675
676    predict_edge (e, predictor, probability);
677 }
678
679 /* Invert all branch predictions or probability notes in the INSN.  This needs
680    to be done each time we invert the condition used by the jump.  */
681
682 void
683 invert_br_probabilities (rtx insn)
684 {
685   rtx note;
686
687   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
688     if (REG_NOTE_KIND (note) == REG_BR_PROB)
689       XINT (note, 0) = REG_BR_PROB_BASE - XINT (note, 0);
690     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
691       XEXP (XEXP (note, 0), 1)
692         = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
693 }
694
695 /* Dump information about the branch prediction to the output file.  */
696
697 static void
698 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
699                  basic_block bb, int used)
700 {
701   edge e;
702   edge_iterator ei;
703
704   if (!file)
705     return;
706
707   FOR_EACH_EDGE (e, ei, bb->succs)
708     if (! (e->flags & EDGE_FALLTHRU))
709       break;
710
711   fprintf (file, "  %s heuristics%s: %.1f%%",
712            predictor_info[predictor].name,
713            used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
714
715   if (bb->count)
716     {
717       fprintf (file, "  exec %"PRId64, bb->count);
718       if (e)
719         {
720           fprintf (file, " hit %"PRId64, e->count);
721           fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
722         }
723     }
724
725   fprintf (file, "\n");
726 }
727
728 /* We can not predict the probabilities of outgoing edges of bb.  Set them
729    evenly and hope for the best.  */
730 static void
731 set_even_probabilities (basic_block bb)
732 {
733   int nedges = 0;
734   edge e;
735   edge_iterator ei;
736
737   FOR_EACH_EDGE (e, ei, bb->succs)
738     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
739       nedges ++;
740   FOR_EACH_EDGE (e, ei, bb->succs)
741     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
742       e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
743     else
744       e->probability = 0;
745 }
746
747 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
748    note if not already present.  Remove now useless REG_BR_PRED notes.  */
749
750 static void
751 combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
752 {
753   rtx prob_note;
754   rtx *pnote;
755   rtx note;
756   int best_probability = PROB_EVEN;
757   enum br_predictor best_predictor = END_PREDICTORS;
758   int combined_probability = REG_BR_PROB_BASE / 2;
759   int d;
760   bool first_match = false;
761   bool found = false;
762
763   if (!can_predict_insn_p (insn))
764     {
765       set_even_probabilities (bb);
766       return;
767     }
768
769   prob_note = find_reg_note (insn, REG_BR_PROB, 0);
770   pnote = &REG_NOTES (insn);
771   if (dump_file)
772     fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
773              bb->index);
774
775   /* We implement "first match" heuristics and use probability guessed
776      by predictor with smallest index.  */
777   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
778     if (REG_NOTE_KIND (note) == REG_BR_PRED)
779       {
780         enum br_predictor predictor = ((enum br_predictor)
781                                        INTVAL (XEXP (XEXP (note, 0), 0)));
782         int probability = INTVAL (XEXP (XEXP (note, 0), 1));
783
784         found = true;
785         if (best_predictor > predictor)
786           best_probability = probability, best_predictor = predictor;
787
788         d = (combined_probability * probability
789              + (REG_BR_PROB_BASE - combined_probability)
790              * (REG_BR_PROB_BASE - probability));
791
792         /* Use FP math to avoid overflows of 32bit integers.  */
793         if (d == 0)
794           /* If one probability is 0% and one 100%, avoid division by zero.  */
795           combined_probability = REG_BR_PROB_BASE / 2;
796         else
797           combined_probability = (((double) combined_probability) * probability
798                                   * REG_BR_PROB_BASE / d + 0.5);
799       }
800
801   /* Decide which heuristic to use.  In case we didn't match anything,
802      use no_prediction heuristic, in case we did match, use either
803      first match or Dempster-Shaffer theory depending on the flags.  */
804
805   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
806     first_match = true;
807
808   if (!found)
809     dump_prediction (dump_file, PRED_NO_PREDICTION,
810                      combined_probability, bb, true);
811   else
812     {
813       dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
814                        bb, !first_match);
815       dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
816                        bb, first_match);
817     }
818
819   if (first_match)
820     combined_probability = best_probability;
821   dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
822
823   while (*pnote)
824     {
825       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
826         {
827           enum br_predictor predictor = ((enum br_predictor)
828                                          INTVAL (XEXP (XEXP (*pnote, 0), 0)));
829           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
830
831           dump_prediction (dump_file, predictor, probability, bb,
832                            !first_match || best_predictor == predictor);
833           *pnote = XEXP (*pnote, 1);
834         }
835       else
836         pnote = &XEXP (*pnote, 1);
837     }
838
839   if (!prob_note)
840     {
841       add_int_reg_note (insn, REG_BR_PROB, combined_probability);
842
843       /* Save the prediction into CFG in case we are seeing non-degenerated
844          conditional jump.  */
845       if (!single_succ_p (bb))
846         {
847           BRANCH_EDGE (bb)->probability = combined_probability;
848           FALLTHRU_EDGE (bb)->probability
849             = REG_BR_PROB_BASE - combined_probability;
850         }
851     }
852   else if (!single_succ_p (bb))
853     {
854       int prob = XINT (prob_note, 0);
855
856       BRANCH_EDGE (bb)->probability = prob;
857       FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
858     }
859   else
860     single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
861 }
862
863 /* Combine predictions into single probability and store them into CFG.
864    Remove now useless prediction entries.  */
865
866 static void
867 combine_predictions_for_bb (basic_block bb)
868 {
869   int best_probability = PROB_EVEN;
870   enum br_predictor best_predictor = END_PREDICTORS;
871   int combined_probability = REG_BR_PROB_BASE / 2;
872   int d;
873   bool first_match = false;
874   bool found = false;
875   struct edge_prediction *pred;
876   int nedges = 0;
877   edge e, first = NULL, second = NULL;
878   edge_iterator ei;
879
880   FOR_EACH_EDGE (e, ei, bb->succs)
881     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
882       {
883         nedges ++;
884         if (first && !second)
885           second = e;
886         if (!first)
887           first = e;
888       }
889
890   /* When there is no successor or only one choice, prediction is easy.
891
892      We are lazy for now and predict only basic blocks with two outgoing
893      edges.  It is possible to predict generic case too, but we have to
894      ignore first match heuristics and do more involved combining.  Implement
895      this later.  */
896   if (nedges != 2)
897     {
898       if (!bb->count)
899         set_even_probabilities (bb);
900       clear_bb_predictions (bb);
901       if (dump_file)
902         fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
903                  nedges, bb->index);
904       return;
905     }
906
907   if (dump_file)
908     fprintf (dump_file, "Predictions for bb %i\n", bb->index);
909
910   edge_prediction **preds = bb_predictions->get (bb);
911   if (preds)
912     {
913       /* We implement "first match" heuristics and use probability guessed
914          by predictor with smallest index.  */
915       for (pred = *preds; pred; pred = pred->ep_next)
916         {
917           enum br_predictor predictor = pred->ep_predictor;
918           int probability = pred->ep_probability;
919
920           if (pred->ep_edge != first)
921             probability = REG_BR_PROB_BASE - probability;
922
923           found = true;
924           /* First match heuristics would be widly confused if we predicted
925              both directions.  */
926           if (best_predictor > predictor)
927             {
928               struct edge_prediction *pred2;
929               int prob = probability;
930
931               for (pred2 = (struct edge_prediction *) *preds;
932                    pred2; pred2 = pred2->ep_next)
933                if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
934                  {
935                    int probability2 = pred->ep_probability;
936
937                    if (pred2->ep_edge != first)
938                      probability2 = REG_BR_PROB_BASE - probability2;
939
940                    if ((probability < REG_BR_PROB_BASE / 2) !=
941                        (probability2 < REG_BR_PROB_BASE / 2))
942                      break;
943
944                    /* If the same predictor later gave better result, go for it! */
945                    if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
946                        || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
947                      prob = probability2;
948                  }
949               if (!pred2)
950                 best_probability = prob, best_predictor = predictor;
951             }
952
953           d = (combined_probability * probability
954                + (REG_BR_PROB_BASE - combined_probability)
955                * (REG_BR_PROB_BASE - probability));
956
957           /* Use FP math to avoid overflows of 32bit integers.  */
958           if (d == 0)
959             /* If one probability is 0% and one 100%, avoid division by zero.  */
960             combined_probability = REG_BR_PROB_BASE / 2;
961           else
962             combined_probability = (((double) combined_probability)
963                                     * probability
964                                     * REG_BR_PROB_BASE / d + 0.5);
965         }
966     }
967
968   /* Decide which heuristic to use.  In case we didn't match anything,
969      use no_prediction heuristic, in case we did match, use either
970      first match or Dempster-Shaffer theory depending on the flags.  */
971
972   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
973     first_match = true;
974
975   if (!found)
976     dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
977   else
978     {
979       dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
980                        !first_match);
981       dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
982                        first_match);
983     }
984
985   if (first_match)
986     combined_probability = best_probability;
987   dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
988
989   if (preds)
990     {
991       for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
992         {
993           enum br_predictor predictor = pred->ep_predictor;
994           int probability = pred->ep_probability;
995
996           if (pred->ep_edge != EDGE_SUCC (bb, 0))
997             probability = REG_BR_PROB_BASE - probability;
998           dump_prediction (dump_file, predictor, probability, bb,
999                            !first_match || best_predictor == predictor);
1000         }
1001     }
1002   clear_bb_predictions (bb);
1003
1004   if (!bb->count)
1005     {
1006       first->probability = combined_probability;
1007       second->probability = REG_BR_PROB_BASE - combined_probability;
1008     }
1009 }
1010
1011 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1012    Return the SSA_NAME if the condition satisfies, NULL otherwise.
1013
1014    T1 and T2 should be one of the following cases:
1015      1. T1 is SSA_NAME, T2 is NULL
1016      2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1017      3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4]  */
1018
1019 static tree
1020 strips_small_constant (tree t1, tree t2)
1021 {
1022   tree ret = NULL;
1023   int value = 0;
1024
1025   if (!t1)
1026     return NULL;
1027   else if (TREE_CODE (t1) == SSA_NAME)
1028     ret = t1;
1029   else if (tree_fits_shwi_p (t1))
1030     value = tree_to_shwi (t1);
1031   else
1032     return NULL;
1033
1034   if (!t2)
1035     return ret;
1036   else if (tree_fits_shwi_p (t2))
1037     value = tree_to_shwi (t2);
1038   else if (TREE_CODE (t2) == SSA_NAME)
1039     {
1040       if (ret)
1041         return NULL;
1042       else
1043         ret = t2;
1044     }
1045
1046   if (value <= 4 && value >= -4)
1047     return ret;
1048   else
1049     return NULL;
1050 }
1051
1052 /* Return the SSA_NAME in T or T's operands.
1053    Return NULL if SSA_NAME cannot be found.  */
1054
1055 static tree
1056 get_base_value (tree t)
1057 {
1058   if (TREE_CODE (t) == SSA_NAME)
1059     return t;
1060
1061   if (!BINARY_CLASS_P (t))
1062     return NULL;
1063
1064   switch (TREE_OPERAND_LENGTH (t))
1065     {
1066     case 1:
1067       return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1068     case 2:
1069       return strips_small_constant (TREE_OPERAND (t, 0),
1070                                     TREE_OPERAND (t, 1));
1071     default:
1072       return NULL;
1073     }
1074 }
1075
1076 /* Check the compare STMT in LOOP. If it compares an induction
1077    variable to a loop invariant, return true, and save
1078    LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1079    Otherwise return false and set LOOP_INVAIANT to NULL.  */
1080
1081 static bool
1082 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1083                                      tree *loop_invariant,
1084                                      enum tree_code *compare_code,
1085                                      tree *loop_step,
1086                                      tree *loop_iv_base)
1087 {
1088   tree op0, op1, bound, base;
1089   affine_iv iv0, iv1;
1090   enum tree_code code;
1091   tree step;
1092
1093   code = gimple_cond_code (stmt);
1094   *loop_invariant = NULL;
1095
1096   switch (code)
1097     {
1098     case GT_EXPR:
1099     case GE_EXPR:
1100     case NE_EXPR:
1101     case LT_EXPR:
1102     case LE_EXPR:
1103     case EQ_EXPR:
1104       break;
1105
1106     default:
1107       return false;
1108     }
1109
1110   op0 = gimple_cond_lhs (stmt);
1111   op1 = gimple_cond_rhs (stmt);
1112
1113   if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST) 
1114        || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1115     return false;
1116   if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1117     return false;
1118   if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1119     return false;
1120   if (TREE_CODE (iv0.step) != INTEGER_CST
1121       || TREE_CODE (iv1.step) != INTEGER_CST)
1122     return false;
1123   if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1124       || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1125     return false;
1126
1127   if (integer_zerop (iv0.step))
1128     {
1129       if (code != NE_EXPR && code != EQ_EXPR)
1130         code = invert_tree_comparison (code, false);
1131       bound = iv0.base;
1132       base = iv1.base;
1133       if (tree_fits_shwi_p (iv1.step))
1134         step = iv1.step;
1135       else
1136         return false;
1137     }
1138   else
1139     {
1140       bound = iv1.base;
1141       base = iv0.base;
1142       if (tree_fits_shwi_p (iv0.step))
1143         step = iv0.step;
1144       else
1145         return false;
1146     }
1147
1148   if (TREE_CODE (bound) != INTEGER_CST)
1149     bound = get_base_value (bound);
1150   if (!bound)
1151     return false;
1152   if (TREE_CODE (base) != INTEGER_CST)
1153     base = get_base_value (base);
1154   if (!base)
1155     return false;
1156
1157   *loop_invariant = bound;
1158   *compare_code = code;
1159   *loop_step = step;
1160   *loop_iv_base = base;
1161   return true;
1162 }
1163
1164 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent.  */
1165
1166 static bool
1167 expr_coherent_p (tree t1, tree t2)
1168 {
1169   gimple stmt;
1170   tree ssa_name_1 = NULL;
1171   tree ssa_name_2 = NULL;
1172
1173   gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1174   gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1175
1176   if (t1 == t2)
1177     return true;
1178
1179   if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1180     return true;
1181   if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1182     return false;
1183
1184   /* Check to see if t1 is expressed/defined with t2.  */
1185   stmt = SSA_NAME_DEF_STMT (t1);
1186   gcc_assert (stmt != NULL);
1187   if (is_gimple_assign (stmt))
1188     {
1189       ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1190       if (ssa_name_1 && ssa_name_1 == t2)
1191         return true;
1192     }
1193
1194   /* Check to see if t2 is expressed/defined with t1.  */
1195   stmt = SSA_NAME_DEF_STMT (t2);
1196   gcc_assert (stmt != NULL);
1197   if (is_gimple_assign (stmt))
1198     {
1199       ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1200       if (ssa_name_2 && ssa_name_2 == t1)
1201         return true;
1202     }
1203
1204   /* Compare if t1 and t2's def_stmts are identical.  */
1205   if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1206     return true;
1207   else
1208     return false;
1209 }
1210
1211 /* Predict branch probability of BB when BB contains a branch that compares
1212    an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1213    loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1214
1215    E.g.
1216      for (int i = 0; i < bound; i++) {
1217        if (i < bound - 2)
1218          computation_1();
1219        else
1220          computation_2();
1221      }
1222
1223   In this loop, we will predict the branch inside the loop to be taken.  */
1224
1225 static void
1226 predict_iv_comparison (struct loop *loop, basic_block bb,
1227                        tree loop_bound_var,
1228                        tree loop_iv_base_var,
1229                        enum tree_code loop_bound_code,
1230                        int loop_bound_step)
1231 {
1232   gimple stmt;
1233   tree compare_var, compare_base;
1234   enum tree_code compare_code;
1235   tree compare_step_var;
1236   edge then_edge;
1237   edge_iterator ei;
1238
1239   if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1240       || predicted_by_p (bb, PRED_LOOP_ITERATIONS)
1241       || predicted_by_p (bb, PRED_LOOP_EXIT))
1242     return;
1243
1244   stmt = last_stmt (bb);
1245   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1246     return;
1247   if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1248                                             loop, &compare_var,
1249                                             &compare_code,
1250                                             &compare_step_var,
1251                                             &compare_base))
1252     return;
1253
1254   /* Find the taken edge.  */
1255   FOR_EACH_EDGE (then_edge, ei, bb->succs)
1256     if (then_edge->flags & EDGE_TRUE_VALUE)
1257       break;
1258
1259   /* When comparing an IV to a loop invariant, NE is more likely to be
1260      taken while EQ is more likely to be not-taken.  */
1261   if (compare_code == NE_EXPR)
1262     {
1263       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1264       return;
1265     }
1266   else if (compare_code == EQ_EXPR)
1267     {
1268       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1269       return;
1270     }
1271
1272   if (!expr_coherent_p (loop_iv_base_var, compare_base))
1273     return;
1274
1275   /* If loop bound, base and compare bound are all constants, we can
1276      calculate the probability directly.  */
1277   if (tree_fits_shwi_p (loop_bound_var)
1278       && tree_fits_shwi_p (compare_var)
1279       && tree_fits_shwi_p (compare_base))
1280     {
1281       int probability;
1282       bool overflow, overall_overflow = false;
1283       widest_int compare_count, tem;
1284
1285       /* (loop_bound - base) / compare_step */
1286       tem = wi::sub (wi::to_widest (loop_bound_var),
1287                      wi::to_widest (compare_base), SIGNED, &overflow);
1288       overall_overflow |= overflow;
1289       widest_int loop_count = wi::div_trunc (tem,
1290                                              wi::to_widest (compare_step_var),
1291                                              SIGNED, &overflow);
1292       overall_overflow |= overflow;
1293
1294       if (!wi::neg_p (wi::to_widest (compare_step_var))
1295           ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1296         {
1297           /* (loop_bound - compare_bound) / compare_step */
1298           tem = wi::sub (wi::to_widest (loop_bound_var),
1299                          wi::to_widest (compare_var), SIGNED, &overflow);
1300           overall_overflow |= overflow;
1301           compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1302                                          SIGNED, &overflow);
1303           overall_overflow |= overflow;
1304         }
1305       else
1306         {
1307           /* (compare_bound - base) / compare_step */
1308           tem = wi::sub (wi::to_widest (compare_var),
1309                          wi::to_widest (compare_base), SIGNED, &overflow);
1310           overall_overflow |= overflow;
1311           compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1312                                          SIGNED, &overflow);
1313           overall_overflow |= overflow;
1314         }
1315       if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1316         ++compare_count;
1317       if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1318         ++loop_count;
1319       if (wi::neg_p (compare_count))
1320         compare_count = 0;
1321       if (wi::neg_p (loop_count))
1322         loop_count = 0;
1323       if (loop_count == 0)
1324         probability = 0;
1325       else if (wi::cmps (compare_count, loop_count) == 1)
1326         probability = REG_BR_PROB_BASE;
1327       else
1328         {
1329           tem = compare_count * REG_BR_PROB_BASE;
1330           tem = wi::udiv_trunc (tem, loop_count);
1331           probability = tem.to_uhwi ();
1332         }
1333
1334       if (!overall_overflow)
1335         predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1336
1337       return;
1338     }
1339
1340   if (expr_coherent_p (loop_bound_var, compare_var))
1341     {
1342       if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1343           && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1344         predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1345       else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1346                && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1347         predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1348       else if (loop_bound_code == NE_EXPR)
1349         {
1350           /* If the loop backedge condition is "(i != bound)", we do
1351              the comparison based on the step of IV:
1352              * step < 0 : backedge condition is like (i > bound)
1353              * step > 0 : backedge condition is like (i < bound)  */
1354           gcc_assert (loop_bound_step != 0);
1355           if (loop_bound_step > 0
1356               && (compare_code == LT_EXPR
1357                   || compare_code == LE_EXPR))
1358             predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1359           else if (loop_bound_step < 0
1360                    && (compare_code == GT_EXPR
1361                        || compare_code == GE_EXPR))
1362             predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1363           else
1364             predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1365         }
1366       else
1367         /* The branch is predicted not-taken if loop_bound_code is
1368            opposite with compare_code.  */
1369         predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1370     }
1371   else if (expr_coherent_p (loop_iv_base_var, compare_var))
1372     {
1373       /* For cases like:
1374            for (i = s; i < h; i++)
1375              if (i > s + 2) ....
1376          The branch should be predicted taken.  */
1377       if (loop_bound_step > 0
1378           && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1379         predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1380       else if (loop_bound_step < 0
1381                && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1382         predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1383       else
1384         predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1385     }
1386 }
1387
1388 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1389    exits are resulted from short-circuit conditions that will generate an
1390    if_tmp. E.g.:
1391
1392    if (foo() || global > 10)
1393      break;
1394
1395    This will be translated into:
1396
1397    BB3:
1398      loop header...
1399    BB4:
1400      if foo() goto BB6 else goto BB5
1401    BB5:
1402      if global > 10 goto BB6 else goto BB7
1403    BB6:
1404      goto BB7
1405    BB7:
1406      iftmp = (PHI 0(BB5), 1(BB6))
1407      if iftmp == 1 goto BB8 else goto BB3
1408    BB8:
1409      outside of the loop...
1410
1411    The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1412    From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1413    exits. This function takes BB7->BB8 as input, and finds out the extra loop
1414    exits to predict them using PRED_LOOP_EXIT.  */
1415
1416 static void
1417 predict_extra_loop_exits (edge exit_edge)
1418 {
1419   unsigned i;
1420   bool check_value_one;
1421   gimple lhs_def_stmt;
1422   gphi *phi_stmt;
1423   tree cmp_rhs, cmp_lhs;
1424   gimple last;
1425   gcond *cmp_stmt;
1426
1427   last = last_stmt (exit_edge->src);
1428   if (!last)
1429     return;
1430   cmp_stmt = dyn_cast <gcond *> (last);
1431   if (!cmp_stmt)
1432     return;
1433
1434   cmp_rhs = gimple_cond_rhs (cmp_stmt);
1435   cmp_lhs = gimple_cond_lhs (cmp_stmt);
1436   if (!TREE_CONSTANT (cmp_rhs)
1437       || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1438     return;
1439   if (TREE_CODE (cmp_lhs) != SSA_NAME)
1440     return;
1441
1442   /* If check_value_one is true, only the phi_args with value '1' will lead
1443      to loop exit. Otherwise, only the phi_args with value '0' will lead to
1444      loop exit.  */
1445   check_value_one = (((integer_onep (cmp_rhs))
1446                     ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1447                     ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1448
1449   lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1450   if (!lhs_def_stmt)
1451     return;
1452
1453   phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1454   if (!phi_stmt)
1455     return;
1456
1457   for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1458     {
1459       edge e1;
1460       edge_iterator ei;
1461       tree val = gimple_phi_arg_def (phi_stmt, i);
1462       edge e = gimple_phi_arg_edge (phi_stmt, i);
1463
1464       if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1465         continue;
1466       if ((check_value_one ^ integer_onep (val)) == 1)
1467         continue;
1468       if (EDGE_COUNT (e->src->succs) != 1)
1469         {
1470           predict_paths_leading_to_edge (e, PRED_LOOP_EXIT, NOT_TAKEN);
1471           continue;
1472         }
1473
1474       FOR_EACH_EDGE (e1, ei, e->src->preds)
1475         predict_paths_leading_to_edge (e1, PRED_LOOP_EXIT, NOT_TAKEN);
1476     }
1477 }
1478
1479 /* Predict edge probabilities by exploiting loop structure.  */
1480
1481 static void
1482 predict_loops (void)
1483 {
1484   struct loop *loop;
1485
1486   /* Try to predict out blocks in a loop that are not part of a
1487      natural loop.  */
1488   FOR_EACH_LOOP (loop, 0)
1489     {
1490       basic_block bb, *bbs;
1491       unsigned j, n_exits;
1492       vec<edge> exits;
1493       struct tree_niter_desc niter_desc;
1494       edge ex;
1495       struct nb_iter_bound *nb_iter;
1496       enum tree_code loop_bound_code = ERROR_MARK;
1497       tree loop_bound_step = NULL;
1498       tree loop_bound_var = NULL;
1499       tree loop_iv_base = NULL;
1500       gcond *stmt = NULL;
1501
1502       exits = get_loop_exit_edges (loop);
1503       n_exits = exits.length ();
1504       if (!n_exits)
1505         {
1506           exits.release ();
1507           continue;
1508         }
1509
1510       FOR_EACH_VEC_ELT (exits, j, ex)
1511         {
1512           tree niter = NULL;
1513           HOST_WIDE_INT nitercst;
1514           int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1515           int probability;
1516           enum br_predictor predictor;
1517
1518           predict_extra_loop_exits (ex);
1519
1520           if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1521             niter = niter_desc.niter;
1522           if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1523             niter = loop_niter_by_eval (loop, ex);
1524
1525           if (TREE_CODE (niter) == INTEGER_CST)
1526             {
1527               if (tree_fits_uhwi_p (niter)
1528                   && max
1529                   && compare_tree_int (niter, max - 1) == -1)
1530                 nitercst = tree_to_uhwi (niter) + 1;
1531               else
1532                 nitercst = max;
1533               predictor = PRED_LOOP_ITERATIONS;
1534             }
1535           /* If we have just one exit and we can derive some information about
1536              the number of iterations of the loop from the statements inside
1537              the loop, use it to predict this exit.  */
1538           else if (n_exits == 1)
1539             {
1540               nitercst = estimated_stmt_executions_int (loop);
1541               if (nitercst < 0)
1542                 continue;
1543               if (nitercst > max)
1544                 nitercst = max;
1545
1546               predictor = PRED_LOOP_ITERATIONS_GUESSED;
1547             }
1548           else
1549             continue;
1550
1551           /* If the prediction for number of iterations is zero, do not
1552              predict the exit edges.  */
1553           if (nitercst == 0)
1554             continue;
1555
1556           probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
1557           predict_edge (ex, predictor, probability);
1558         }
1559       exits.release ();
1560
1561       /* Find information about loop bound variables.  */
1562       for (nb_iter = loop->bounds; nb_iter;
1563            nb_iter = nb_iter->next)
1564         if (nb_iter->stmt
1565             && gimple_code (nb_iter->stmt) == GIMPLE_COND)
1566           {
1567             stmt = as_a <gcond *> (nb_iter->stmt);
1568             break;
1569           }
1570       if (!stmt && last_stmt (loop->header)
1571           && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
1572         stmt = as_a <gcond *> (last_stmt (loop->header));
1573       if (stmt)
1574         is_comparison_with_loop_invariant_p (stmt, loop,
1575                                              &loop_bound_var,
1576                                              &loop_bound_code,
1577                                              &loop_bound_step,
1578                                              &loop_iv_base);
1579
1580       bbs = get_loop_body (loop);
1581
1582       for (j = 0; j < loop->num_nodes; j++)
1583         {
1584           int header_found = 0;
1585           edge e;
1586           edge_iterator ei;
1587
1588           bb = bbs[j];
1589
1590           /* Bypass loop heuristics on continue statement.  These
1591              statements construct loops via "non-loop" constructs
1592              in the source language and are better to be handled
1593              separately.  */
1594           if (predicted_by_p (bb, PRED_CONTINUE))
1595             continue;
1596
1597           /* Loop branch heuristics - predict an edge back to a
1598              loop's head as taken.  */
1599           if (bb == loop->latch)
1600             {
1601               e = find_edge (loop->latch, loop->header);
1602               if (e)
1603                 {
1604                   header_found = 1;
1605                   predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1606                 }
1607             }
1608
1609           /* Loop exit heuristics - predict an edge exiting the loop if the
1610              conditional has no loop header successors as not taken.  */
1611           if (!header_found
1612               /* If we already used more reliable loop exit predictors, do not
1613                  bother with PRED_LOOP_EXIT.  */
1614               && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1615               && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1616             {
1617               /* For loop with many exits we don't want to predict all exits
1618                  with the pretty large probability, because if all exits are
1619                  considered in row, the loop would be predicted to iterate
1620                  almost never.  The code to divide probability by number of
1621                  exits is very rough.  It should compute the number of exits
1622                  taken in each patch through function (not the overall number
1623                  of exits that might be a lot higher for loops with wide switch
1624                  statements in them) and compute n-th square root.
1625
1626                  We limit the minimal probability by 2% to avoid
1627                  EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1628                  as this was causing regression in perl benchmark containing such
1629                  a wide loop.  */
1630
1631               int probability = ((REG_BR_PROB_BASE
1632                                   - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1633                                  / n_exits);
1634               if (probability < HITRATE (2))
1635                 probability = HITRATE (2);
1636               FOR_EACH_EDGE (e, ei, bb->succs)
1637                 if (e->dest->index < NUM_FIXED_BLOCKS
1638                     || !flow_bb_inside_loop_p (loop, e->dest))
1639                   predict_edge (e, PRED_LOOP_EXIT, probability);
1640             }
1641           if (loop_bound_var)
1642             predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
1643                                    loop_bound_code,
1644                                    tree_to_shwi (loop_bound_step));
1645         }
1646
1647       /* Free basic blocks from get_loop_body.  */
1648       free (bbs);
1649     }
1650 }
1651
1652 /* Attempt to predict probabilities of BB outgoing edges using local
1653    properties.  */
1654 static void
1655 bb_estimate_probability_locally (basic_block bb)
1656 {
1657   rtx_insn *last_insn = BB_END (bb);
1658   rtx cond;
1659
1660   if (! can_predict_insn_p (last_insn))
1661     return;
1662   cond = get_condition (last_insn, NULL, false, false);
1663   if (! cond)
1664     return;
1665
1666   /* Try "pointer heuristic."
1667      A comparison ptr == 0 is predicted as false.
1668      Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
1669   if (COMPARISON_P (cond)
1670       && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1671           || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1672     {
1673       if (GET_CODE (cond) == EQ)
1674         predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1675       else if (GET_CODE (cond) == NE)
1676         predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1677     }
1678   else
1679
1680   /* Try "opcode heuristic."
1681      EQ tests are usually false and NE tests are usually true. Also,
1682      most quantities are positive, so we can make the appropriate guesses
1683      about signed comparisons against zero.  */
1684     switch (GET_CODE (cond))
1685       {
1686       case CONST_INT:
1687         /* Unconditional branch.  */
1688         predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1689                           cond == const0_rtx ? NOT_TAKEN : TAKEN);
1690         break;
1691
1692       case EQ:
1693       case UNEQ:
1694         /* Floating point comparisons appears to behave in a very
1695            unpredictable way because of special role of = tests in
1696            FP code.  */
1697         if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1698           ;
1699         /* Comparisons with 0 are often used for booleans and there is
1700            nothing useful to predict about them.  */
1701         else if (XEXP (cond, 1) == const0_rtx
1702                  || XEXP (cond, 0) == const0_rtx)
1703           ;
1704         else
1705           predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1706         break;
1707
1708       case NE:
1709       case LTGT:
1710         /* Floating point comparisons appears to behave in a very
1711            unpredictable way because of special role of = tests in
1712            FP code.  */
1713         if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1714           ;
1715         /* Comparisons with 0 are often used for booleans and there is
1716            nothing useful to predict about them.  */
1717         else if (XEXP (cond, 1) == const0_rtx
1718                  || XEXP (cond, 0) == const0_rtx)
1719           ;
1720         else
1721           predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1722         break;
1723
1724       case ORDERED:
1725         predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1726         break;
1727
1728       case UNORDERED:
1729         predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1730         break;
1731
1732       case LE:
1733       case LT:
1734         if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1735             || XEXP (cond, 1) == constm1_rtx)
1736           predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1737         break;
1738
1739       case GE:
1740       case GT:
1741         if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1742             || XEXP (cond, 1) == constm1_rtx)
1743           predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1744         break;
1745
1746       default:
1747         break;
1748       }
1749 }
1750
1751 /* Set edge->probability for each successor edge of BB.  */
1752 void
1753 guess_outgoing_edge_probabilities (basic_block bb)
1754 {
1755   bb_estimate_probability_locally (bb);
1756   combine_predictions_for_insn (BB_END (bb), bb);
1757 }
1758 \f
1759 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
1760
1761 /* Helper function for expr_expected_value.  */
1762
1763 static tree
1764 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
1765                        tree op1, bitmap visited, enum br_predictor *predictor)
1766 {
1767   gimple def;
1768
1769   if (predictor)
1770     *predictor = PRED_UNCONDITIONAL;
1771
1772   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1773     {
1774       if (TREE_CONSTANT (op0))
1775         return op0;
1776
1777       if (code != SSA_NAME)
1778         return NULL_TREE;
1779
1780       def = SSA_NAME_DEF_STMT (op0);
1781
1782       /* If we were already here, break the infinite cycle.  */
1783       if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1784         return NULL;
1785
1786       if (gimple_code (def) == GIMPLE_PHI)
1787         {
1788           /* All the arguments of the PHI node must have the same constant
1789              length.  */
1790           int i, n = gimple_phi_num_args (def);
1791           tree val = NULL, new_val;
1792
1793           for (i = 0; i < n; i++)
1794             {
1795               tree arg = PHI_ARG_DEF (def, i);
1796               enum br_predictor predictor2;
1797
1798               /* If this PHI has itself as an argument, we cannot
1799                  determine the string length of this argument.  However,
1800                  if we can find an expected constant value for the other
1801                  PHI args then we can still be sure that this is
1802                  likely a constant.  So be optimistic and just
1803                  continue with the next argument.  */
1804               if (arg == PHI_RESULT (def))
1805                 continue;
1806
1807               new_val = expr_expected_value (arg, visited, &predictor2);
1808
1809               /* It is difficult to combine value predictors.  Simply assume
1810                  that later predictor is weaker and take its prediction.  */
1811               if (predictor && *predictor < predictor2)
1812                 *predictor = predictor2;
1813               if (!new_val)
1814                 return NULL;
1815               if (!val)
1816                 val = new_val;
1817               else if (!operand_equal_p (val, new_val, false))
1818                 return NULL;
1819             }
1820           return val;
1821         }
1822       if (is_gimple_assign (def))
1823         {
1824           if (gimple_assign_lhs (def) != op0)
1825             return NULL;
1826
1827           return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1828                                         gimple_assign_rhs1 (def),
1829                                         gimple_assign_rhs_code (def),
1830                                         gimple_assign_rhs2 (def),
1831                                         visited, predictor);
1832         }
1833
1834       if (is_gimple_call (def))
1835         {
1836           tree decl = gimple_call_fndecl (def);
1837           if (!decl)
1838             {
1839               if (gimple_call_internal_p (def)
1840                   && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
1841                 {
1842                   gcc_assert (gimple_call_num_args (def) == 3);
1843                   tree val = gimple_call_arg (def, 0);
1844                   if (TREE_CONSTANT (val))
1845                     return val;
1846                   if (predictor)
1847                     {
1848                       tree val2 = gimple_call_arg (def, 2);
1849                       gcc_assert (TREE_CODE (val2) == INTEGER_CST
1850                                   && tree_fits_uhwi_p (val2)
1851                                   && tree_to_uhwi (val2) < END_PREDICTORS);
1852                       *predictor = (enum br_predictor) tree_to_uhwi (val2);
1853                     }
1854                   return gimple_call_arg (def, 1);
1855                 }
1856               return NULL;
1857             }
1858           if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1859             switch (DECL_FUNCTION_CODE (decl))
1860               {
1861               case BUILT_IN_EXPECT:
1862                 {
1863                   tree val;
1864                   if (gimple_call_num_args (def) != 2)
1865                     return NULL;
1866                   val = gimple_call_arg (def, 0);
1867                   if (TREE_CONSTANT (val))
1868                     return val;
1869                   if (predictor)
1870                     *predictor = PRED_BUILTIN_EXPECT;
1871                   return gimple_call_arg (def, 1);
1872                 }
1873
1874               case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
1875               case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
1876               case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
1877               case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
1878               case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
1879               case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
1880               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
1881               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
1882               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
1883               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
1884               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
1885               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
1886               case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
1887                 /* Assume that any given atomic operation has low contention,
1888                    and thus the compare-and-swap operation succeeds.  */
1889                 if (predictor)
1890                   *predictor = PRED_COMPARE_AND_SWAP;
1891                 return boolean_true_node;
1892               default:
1893                 break;
1894             }
1895         }
1896
1897       return NULL;
1898     }
1899
1900   if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1901     {
1902       tree res;
1903       enum br_predictor predictor2;
1904       op0 = expr_expected_value (op0, visited, predictor);
1905       if (!op0)
1906         return NULL;
1907       op1 = expr_expected_value (op1, visited, &predictor2);
1908       if (predictor && *predictor < predictor2)
1909         *predictor = predictor2;
1910       if (!op1)
1911         return NULL;
1912       res = fold_build2 (code, type, op0, op1);
1913       if (TREE_CONSTANT (res))
1914         return res;
1915       return NULL;
1916     }
1917   if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1918     {
1919       tree res;
1920       op0 = expr_expected_value (op0, visited, predictor);
1921       if (!op0)
1922         return NULL;
1923       res = fold_build1 (code, type, op0);
1924       if (TREE_CONSTANT (res))
1925         return res;
1926       return NULL;
1927     }
1928   return NULL;
1929 }
1930
1931 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1932    The function is used by builtin_expect branch predictor so the evidence
1933    must come from this construct and additional possible constant folding.
1934
1935    We may want to implement more involved value guess (such as value range
1936    propagation based prediction), but such tricks shall go to new
1937    implementation.  */
1938
1939 static tree
1940 expr_expected_value (tree expr, bitmap visited,
1941                      enum br_predictor *predictor)
1942 {
1943   enum tree_code code;
1944   tree op0, op1;
1945
1946   if (TREE_CONSTANT (expr))
1947     {
1948       if (predictor)
1949         *predictor = PRED_UNCONDITIONAL;
1950       return expr;
1951     }
1952
1953   extract_ops_from_tree (expr, &code, &op0, &op1);
1954   return expr_expected_value_1 (TREE_TYPE (expr),
1955                                 op0, code, op1, visited, predictor);
1956 }
1957 \f
1958 /* Predict using opcode of the last statement in basic block.  */
1959 static void
1960 tree_predict_by_opcode (basic_block bb)
1961 {
1962   gimple stmt = last_stmt (bb);
1963   edge then_edge;
1964   tree op0, op1;
1965   tree type;
1966   tree val;
1967   enum tree_code cmp;
1968   bitmap visited;
1969   edge_iterator ei;
1970   enum br_predictor predictor;
1971
1972   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1973     return;
1974   FOR_EACH_EDGE (then_edge, ei, bb->succs)
1975     if (then_edge->flags & EDGE_TRUE_VALUE)
1976       break;
1977   op0 = gimple_cond_lhs (stmt);
1978   op1 = gimple_cond_rhs (stmt);
1979   cmp = gimple_cond_code (stmt);
1980   type = TREE_TYPE (op0);
1981   visited = BITMAP_ALLOC (NULL);
1982   val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited,
1983                                &predictor);
1984   BITMAP_FREE (visited);
1985   if (val && TREE_CODE (val) == INTEGER_CST)
1986     {
1987       if (predictor == PRED_BUILTIN_EXPECT)
1988         {
1989           int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
1990
1991           gcc_assert (percent >= 0 && percent <= 100);
1992           if (integer_zerop (val))
1993             percent = 100 - percent;
1994           predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
1995         }
1996       else
1997         predict_edge (then_edge, predictor,
1998                       integer_zerop (val) ? NOT_TAKEN : TAKEN);
1999     }
2000   /* Try "pointer heuristic."
2001      A comparison ptr == 0 is predicted as false.
2002      Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
2003   if (POINTER_TYPE_P (type))
2004     {
2005       if (cmp == EQ_EXPR)
2006         predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2007       else if (cmp == NE_EXPR)
2008         predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2009     }
2010   else
2011
2012   /* Try "opcode heuristic."
2013      EQ tests are usually false and NE tests are usually true. Also,
2014      most quantities are positive, so we can make the appropriate guesses
2015      about signed comparisons against zero.  */
2016     switch (cmp)
2017       {
2018       case EQ_EXPR:
2019       case UNEQ_EXPR:
2020         /* Floating point comparisons appears to behave in a very
2021            unpredictable way because of special role of = tests in
2022            FP code.  */
2023         if (FLOAT_TYPE_P (type))
2024           ;
2025         /* Comparisons with 0 are often used for booleans and there is
2026            nothing useful to predict about them.  */
2027         else if (integer_zerop (op0) || integer_zerop (op1))
2028           ;
2029         else
2030           predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2031         break;
2032
2033       case NE_EXPR:
2034       case LTGT_EXPR:
2035         /* Floating point comparisons appears to behave in a very
2036            unpredictable way because of special role of = tests in
2037            FP code.  */
2038         if (FLOAT_TYPE_P (type))
2039           ;
2040         /* Comparisons with 0 are often used for booleans and there is
2041            nothing useful to predict about them.  */
2042         else if (integer_zerop (op0)
2043                  || integer_zerop (op1))
2044           ;
2045         else
2046           predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2047         break;
2048
2049       case ORDERED_EXPR:
2050         predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2051         break;
2052
2053       case UNORDERED_EXPR:
2054         predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2055         break;
2056
2057       case LE_EXPR:
2058       case LT_EXPR:
2059         if (integer_zerop (op1)
2060             || integer_onep (op1)
2061             || integer_all_onesp (op1)
2062             || real_zerop (op1)
2063             || real_onep (op1)
2064             || real_minus_onep (op1))
2065           predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2066         break;
2067
2068       case GE_EXPR:
2069       case GT_EXPR:
2070         if (integer_zerop (op1)
2071             || integer_onep (op1)
2072             || integer_all_onesp (op1)
2073             || real_zerop (op1)
2074             || real_onep (op1)
2075             || real_minus_onep (op1))
2076           predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2077         break;
2078
2079       default:
2080         break;
2081       }
2082 }
2083
2084 /* Try to guess whether the value of return means error code.  */
2085
2086 static enum br_predictor
2087 return_prediction (tree val, enum prediction *prediction)
2088 {
2089   /* VOID.  */
2090   if (!val)
2091     return PRED_NO_PREDICTION;
2092   /* Different heuristics for pointers and scalars.  */
2093   if (POINTER_TYPE_P (TREE_TYPE (val)))
2094     {
2095       /* NULL is usually not returned.  */
2096       if (integer_zerop (val))
2097         {
2098           *prediction = NOT_TAKEN;
2099           return PRED_NULL_RETURN;
2100         }
2101     }
2102   else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2103     {
2104       /* Negative return values are often used to indicate
2105          errors.  */
2106       if (TREE_CODE (val) == INTEGER_CST
2107           && tree_int_cst_sgn (val) < 0)
2108         {
2109           *prediction = NOT_TAKEN;
2110           return PRED_NEGATIVE_RETURN;
2111         }
2112       /* Constant return values seems to be commonly taken.
2113          Zero/one often represent booleans so exclude them from the
2114          heuristics.  */
2115       if (TREE_CONSTANT (val)
2116           && (!integer_zerop (val) && !integer_onep (val)))
2117         {
2118           *prediction = TAKEN;
2119           return PRED_CONST_RETURN;
2120         }
2121     }
2122   return PRED_NO_PREDICTION;
2123 }
2124
2125 /* Find the basic block with return expression and look up for possible
2126    return value trying to apply RETURN_PREDICTION heuristics.  */
2127 static void
2128 apply_return_prediction (void)
2129 {
2130   greturn *return_stmt = NULL;
2131   tree return_val;
2132   edge e;
2133   gphi *phi;
2134   int phi_num_args, i;
2135   enum br_predictor pred;
2136   enum prediction direction;
2137   edge_iterator ei;
2138
2139   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2140     {
2141       gimple last = last_stmt (e->src);
2142       if (last
2143           && gimple_code (last) == GIMPLE_RETURN)
2144         {
2145           return_stmt = as_a <greturn *> (last);
2146           break;
2147         }
2148     }
2149   if (!e)
2150     return;
2151   return_val = gimple_return_retval (return_stmt);
2152   if (!return_val)
2153     return;
2154   if (TREE_CODE (return_val) != SSA_NAME
2155       || !SSA_NAME_DEF_STMT (return_val)
2156       || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2157     return;
2158   phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2159   phi_num_args = gimple_phi_num_args (phi);
2160   pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2161
2162   /* Avoid the degenerate case where all return values form the function
2163      belongs to same category (ie they are all positive constants)
2164      so we can hardly say something about them.  */
2165   for (i = 1; i < phi_num_args; i++)
2166     if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2167       break;
2168   if (i != phi_num_args)
2169     for (i = 0; i < phi_num_args; i++)
2170       {
2171         pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2172         if (pred != PRED_NO_PREDICTION)
2173           predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2174                                          direction);
2175       }
2176 }
2177
2178 /* Look for basic block that contains unlikely to happen events
2179    (such as noreturn calls) and mark all paths leading to execution
2180    of this basic blocks as unlikely.  */
2181
2182 static void
2183 tree_bb_level_predictions (void)
2184 {
2185   basic_block bb;
2186   bool has_return_edges = false;
2187   edge e;
2188   edge_iterator ei;
2189
2190   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2191     if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
2192       {
2193         has_return_edges = true;
2194         break;
2195       }
2196
2197   apply_return_prediction ();
2198
2199   FOR_EACH_BB_FN (bb, cfun)
2200     {
2201       gimple_stmt_iterator gsi;
2202
2203       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2204         {
2205           gimple stmt = gsi_stmt (gsi);
2206           tree decl;
2207
2208           if (is_gimple_call (stmt))
2209             {
2210               if ((gimple_call_flags (stmt) & ECF_NORETURN)
2211                   && has_return_edges)
2212                 predict_paths_leading_to (bb, PRED_NORETURN,
2213                                           NOT_TAKEN);
2214               decl = gimple_call_fndecl (stmt);
2215               if (decl
2216                   && lookup_attribute ("cold",
2217                                        DECL_ATTRIBUTES (decl)))
2218                 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2219                                           NOT_TAKEN);
2220             }
2221           else if (gimple_code (stmt) == GIMPLE_PREDICT)
2222             {
2223               predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2224                                         gimple_predict_outcome (stmt));
2225               /* Keep GIMPLE_PREDICT around so early inlining will propagate
2226                  hints to callers.  */
2227             }
2228         }
2229     }
2230 }
2231
2232 #ifdef ENABLE_CHECKING
2233
2234 /* Callback for hash_map::traverse, asserts that the pointer map is
2235    empty.  */
2236
2237 bool
2238 assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2239                  void *)
2240 {
2241   gcc_assert (!value);
2242   return false;
2243 }
2244 #endif
2245
2246 /* Predict branch probabilities and estimate profile for basic block BB.  */
2247
2248 static void
2249 tree_estimate_probability_bb (basic_block bb)
2250 {
2251   edge e;
2252   edge_iterator ei;
2253   gimple last;
2254
2255   FOR_EACH_EDGE (e, ei, bb->succs)
2256     {
2257       /* Predict edges to user labels with attributes.  */
2258       if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2259         {
2260           gimple_stmt_iterator gi;
2261           for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
2262             {
2263               glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
2264               tree decl;
2265
2266               if (!label_stmt)
2267                 break;
2268               decl = gimple_label_label (label_stmt);
2269               if (DECL_ARTIFICIAL (decl))
2270                 continue;
2271
2272               /* Finally, we have a user-defined label.  */
2273               if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
2274                 predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
2275               else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
2276                 predict_edge_def (e, PRED_HOT_LABEL, TAKEN);
2277             }
2278         }
2279
2280       /* Predict early returns to be probable, as we've already taken
2281          care for error returns and other cases are often used for
2282          fast paths through function.
2283
2284          Since we've already removed the return statements, we are
2285          looking for CFG like:
2286
2287          if (conditional)
2288          {
2289          ..
2290          goto return_block
2291          }
2292          some other blocks
2293          return_block:
2294          return_stmt.  */
2295       if (e->dest != bb->next_bb
2296           && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2297           && single_succ_p (e->dest)
2298           && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2299           && (last = last_stmt (e->dest)) != NULL
2300           && gimple_code (last) == GIMPLE_RETURN)
2301         {
2302           edge e1;
2303           edge_iterator ei1;
2304
2305           if (single_succ_p (bb))
2306             {
2307               FOR_EACH_EDGE (e1, ei1, bb->preds)
2308                 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
2309                     && !predicted_by_p (e1->src, PRED_CONST_RETURN)
2310                     && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
2311                   predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
2312             }
2313           else
2314             if (!predicted_by_p (e->src, PRED_NULL_RETURN)
2315                 && !predicted_by_p (e->src, PRED_CONST_RETURN)
2316                 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
2317               predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
2318         }
2319
2320       /* Look for block we are guarding (ie we dominate it,
2321          but it doesn't postdominate us).  */
2322       if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2323           && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2324           && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2325         {
2326           gimple_stmt_iterator bi;
2327
2328           /* The call heuristic claims that a guarded function call
2329              is improbable.  This is because such calls are often used
2330              to signal exceptional situations such as printing error
2331              messages.  */
2332           for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2333                gsi_next (&bi))
2334             {
2335               gimple stmt = gsi_stmt (bi);
2336               if (is_gimple_call (stmt)
2337                   /* Constant and pure calls are hardly used to signalize
2338                      something exceptional.  */
2339                   && gimple_has_side_effects (stmt))
2340                 {
2341                   predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2342                   break;
2343                 }
2344             }
2345         }
2346     }
2347   tree_predict_by_opcode (bb);
2348 }
2349
2350 /* Predict branch probabilities and estimate profile of the tree CFG.
2351    This function can be called from the loop optimizers to recompute
2352    the profile information.  */
2353
2354 void
2355 tree_estimate_probability (void)
2356 {
2357   basic_block bb;
2358
2359   add_noreturn_fake_exit_edges ();
2360   connect_infinite_loops_to_exit ();
2361   /* We use loop_niter_by_eval, which requires that the loops have
2362      preheaders.  */
2363   create_preheaders (CP_SIMPLE_PREHEADERS);
2364   calculate_dominance_info (CDI_POST_DOMINATORS);
2365
2366   bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2367   tree_bb_level_predictions ();
2368   record_loop_exits ();
2369
2370   if (number_of_loops (cfun) > 1)
2371     predict_loops ();
2372
2373   FOR_EACH_BB_FN (bb, cfun)
2374     tree_estimate_probability_bb (bb);
2375
2376   FOR_EACH_BB_FN (bb, cfun)
2377     combine_predictions_for_bb (bb);
2378
2379 #ifdef ENABLE_CHECKING
2380   bb_predictions->traverse<void *, assert_is_empty> (NULL);
2381 #endif
2382   delete bb_predictions;
2383   bb_predictions = NULL;
2384
2385   estimate_bb_frequencies (false);
2386   free_dominance_info (CDI_POST_DOMINATORS);
2387   remove_fake_exit_edges ();
2388 }
2389 \f
2390 /* Predict edges to successors of CUR whose sources are not postdominated by
2391    BB by PRED and recurse to all postdominators.  */
2392
2393 static void
2394 predict_paths_for_bb (basic_block cur, basic_block bb,
2395                       enum br_predictor pred,
2396                       enum prediction taken,
2397                       bitmap visited)
2398 {
2399   edge e;
2400   edge_iterator ei;
2401   basic_block son;
2402
2403   /* We are looking for all edges forming edge cut induced by
2404      set of all blocks postdominated by BB.  */
2405   FOR_EACH_EDGE (e, ei, cur->preds)
2406     if (e->src->index >= NUM_FIXED_BLOCKS
2407         && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
2408     {
2409       edge e2;
2410       edge_iterator ei2;
2411       bool found = false;
2412
2413       /* Ignore fake edges and eh, we predict them as not taken anyway.  */
2414       if (e->flags & (EDGE_EH | EDGE_FAKE))
2415         continue;
2416       gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
2417
2418       /* See if there is an edge from e->src that is not abnormal
2419          and does not lead to BB.  */
2420       FOR_EACH_EDGE (e2, ei2, e->src->succs)
2421         if (e2 != e
2422             && !(e2->flags & (EDGE_EH | EDGE_FAKE))
2423             && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
2424           {
2425             found = true;
2426             break;
2427           }
2428
2429       /* If there is non-abnormal path leaving e->src, predict edge
2430          using predictor.  Otherwise we need to look for paths
2431          leading to e->src.
2432
2433          The second may lead to infinite loop in the case we are predicitng
2434          regions that are only reachable by abnormal edges.  We simply
2435          prevent visiting given BB twice.  */
2436       if (found)
2437         predict_edge_def (e, pred, taken);
2438       else if (bitmap_set_bit (visited, e->src->index))
2439         predict_paths_for_bb (e->src, e->src, pred, taken, visited);
2440     }
2441   for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
2442        son;
2443        son = next_dom_son (CDI_POST_DOMINATORS, son))
2444     predict_paths_for_bb (son, bb, pred, taken, visited);
2445 }
2446
2447 /* Sets branch probabilities according to PREDiction and
2448    FLAGS.  */
2449
2450 static void
2451 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
2452                           enum prediction taken)
2453 {
2454   bitmap visited = BITMAP_ALLOC (NULL);
2455   predict_paths_for_bb (bb, bb, pred, taken, visited);
2456   BITMAP_FREE (visited);
2457 }
2458
2459 /* Like predict_paths_leading_to but take edge instead of basic block.  */
2460
2461 static void
2462 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
2463                                enum prediction taken)
2464 {
2465   bool has_nonloop_edge = false;
2466   edge_iterator ei;
2467   edge e2;
2468
2469   basic_block bb = e->src;
2470   FOR_EACH_EDGE (e2, ei, bb->succs)
2471     if (e2->dest != e->src && e2->dest != e->dest
2472         && !(e->flags & (EDGE_EH | EDGE_FAKE))
2473         && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
2474       {
2475         has_nonloop_edge = true;
2476         break;
2477       }
2478   if (!has_nonloop_edge)
2479     {
2480       bitmap visited = BITMAP_ALLOC (NULL);
2481       predict_paths_for_bb (bb, bb, pred, taken, visited);
2482       BITMAP_FREE (visited);
2483     }
2484   else
2485     predict_edge_def (e, pred, taken);
2486 }
2487 \f
2488 /* This is used to carry information about basic blocks.  It is
2489    attached to the AUX field of the standard CFG block.  */
2490
2491 struct block_info
2492 {
2493   /* Estimated frequency of execution of basic_block.  */
2494   sreal frequency;
2495
2496   /* To keep queue of basic blocks to process.  */
2497   basic_block next;
2498
2499   /* Number of predecessors we need to visit first.  */
2500   int npredecessors;
2501 };
2502
2503 /* Similar information for edges.  */
2504 struct edge_prob_info
2505 {
2506   /* In case edge is a loopback edge, the probability edge will be reached
2507      in case header is.  Estimated number of iterations of the loop can be
2508      then computed as 1 / (1 - back_edge_prob).  */
2509   sreal back_edge_prob;
2510   /* True if the edge is a loopback edge in the natural loop.  */
2511   unsigned int back_edge:1;
2512 };
2513
2514 #define BLOCK_INFO(B)   ((block_info *) (B)->aux)
2515 #undef EDGE_INFO
2516 #define EDGE_INFO(E)    ((edge_prob_info *) (E)->aux)
2517
2518 /* Helper function for estimate_bb_frequencies.
2519    Propagate the frequencies in blocks marked in
2520    TOVISIT, starting in HEAD.  */
2521
2522 static void
2523 propagate_freq (basic_block head, bitmap tovisit)
2524 {
2525   basic_block bb;
2526   basic_block last;
2527   unsigned i;
2528   edge e;
2529   basic_block nextbb;
2530   bitmap_iterator bi;
2531
2532   /* For each basic block we need to visit count number of his predecessors
2533      we need to visit first.  */
2534   EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
2535     {
2536       edge_iterator ei;
2537       int count = 0;
2538
2539       bb = BASIC_BLOCK_FOR_FN (cfun, i);
2540
2541       FOR_EACH_EDGE (e, ei, bb->preds)
2542         {
2543           bool visit = bitmap_bit_p (tovisit, e->src->index);
2544
2545           if (visit && !(e->flags & EDGE_DFS_BACK))
2546             count++;
2547           else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
2548             fprintf (dump_file,
2549                      "Irreducible region hit, ignoring edge to %i->%i\n",
2550                      e->src->index, bb->index);
2551         }
2552       BLOCK_INFO (bb)->npredecessors = count;
2553       /* When function never returns, we will never process exit block.  */
2554       if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2555         bb->count = bb->frequency = 0;
2556     }
2557
2558   BLOCK_INFO (head)->frequency = 1;
2559   last = head;
2560   for (bb = head; bb; bb = nextbb)
2561     {
2562       edge_iterator ei;
2563       sreal cyclic_probability = 0;
2564       sreal frequency = 0;
2565
2566       nextbb = BLOCK_INFO (bb)->next;
2567       BLOCK_INFO (bb)->next = NULL;
2568
2569       /* Compute frequency of basic block.  */
2570       if (bb != head)
2571         {
2572 #ifdef ENABLE_CHECKING
2573           FOR_EACH_EDGE (e, ei, bb->preds)
2574             gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
2575                         || (e->flags & EDGE_DFS_BACK));
2576 #endif
2577
2578           FOR_EACH_EDGE (e, ei, bb->preds)
2579             if (EDGE_INFO (e)->back_edge)
2580               {
2581                 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
2582               }
2583             else if (!(e->flags & EDGE_DFS_BACK))
2584               {
2585                 /*  frequency += (e->probability
2586                                   * BLOCK_INFO (e->src)->frequency /
2587                                   REG_BR_PROB_BASE);  */
2588
2589                 sreal tmp = e->probability;
2590                 tmp *= BLOCK_INFO (e->src)->frequency;
2591                 tmp *= real_inv_br_prob_base;
2592                 frequency += tmp;
2593               }
2594
2595           if (cyclic_probability == 0)
2596             {
2597               BLOCK_INFO (bb)->frequency = frequency;
2598             }
2599           else
2600             {
2601               if (cyclic_probability > real_almost_one)
2602                 cyclic_probability = real_almost_one;
2603
2604               /* BLOCK_INFO (bb)->frequency = frequency
2605                                               / (1 - cyclic_probability) */
2606
2607               cyclic_probability = sreal (1) - cyclic_probability;
2608               BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
2609             }
2610         }
2611
2612       bitmap_clear_bit (tovisit, bb->index);
2613
2614       e = find_edge (bb, head);
2615       if (e)
2616         {
2617           /* EDGE_INFO (e)->back_edge_prob
2618              = ((e->probability * BLOCK_INFO (bb)->frequency)
2619              / REG_BR_PROB_BASE); */
2620
2621           sreal tmp = e->probability;
2622           tmp *= BLOCK_INFO (bb)->frequency;
2623           EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
2624         }
2625
2626       /* Propagate to successor blocks.  */
2627       FOR_EACH_EDGE (e, ei, bb->succs)
2628         if (!(e->flags & EDGE_DFS_BACK)
2629             && BLOCK_INFO (e->dest)->npredecessors)
2630           {
2631             BLOCK_INFO (e->dest)->npredecessors--;
2632             if (!BLOCK_INFO (e->dest)->npredecessors)
2633               {
2634                 if (!nextbb)
2635                   nextbb = e->dest;
2636                 else
2637                   BLOCK_INFO (last)->next = e->dest;
2638
2639                 last = e->dest;
2640               }
2641           }
2642     }
2643 }
2644
2645 /* Estimate frequencies in loops at same nest level.  */
2646
2647 static void
2648 estimate_loops_at_level (struct loop *first_loop)
2649 {
2650   struct loop *loop;
2651
2652   for (loop = first_loop; loop; loop = loop->next)
2653     {
2654       edge e;
2655       basic_block *bbs;
2656       unsigned i;
2657       bitmap tovisit = BITMAP_ALLOC (NULL);
2658
2659       estimate_loops_at_level (loop->inner);
2660
2661       /* Find current loop back edge and mark it.  */
2662       e = loop_latch_edge (loop);
2663       EDGE_INFO (e)->back_edge = 1;
2664
2665       bbs = get_loop_body (loop);
2666       for (i = 0; i < loop->num_nodes; i++)
2667         bitmap_set_bit (tovisit, bbs[i]->index);
2668       free (bbs);
2669       propagate_freq (loop->header, tovisit);
2670       BITMAP_FREE (tovisit);
2671     }
2672 }
2673
2674 /* Propagates frequencies through structure of loops.  */
2675
2676 static void
2677 estimate_loops (void)
2678 {
2679   bitmap tovisit = BITMAP_ALLOC (NULL);
2680   basic_block bb;
2681
2682   /* Start by estimating the frequencies in the loops.  */
2683   if (number_of_loops (cfun) > 1)
2684     estimate_loops_at_level (current_loops->tree_root->inner);
2685
2686   /* Now propagate the frequencies through all the blocks.  */
2687   FOR_ALL_BB_FN (bb, cfun)
2688     {
2689       bitmap_set_bit (tovisit, bb->index);
2690     }
2691   propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
2692   BITMAP_FREE (tovisit);
2693 }
2694
2695 /* Drop the profile for NODE to guessed, and update its frequency based on
2696    whether it is expected to be hot given the CALL_COUNT.  */
2697
2698 static void
2699 drop_profile (struct cgraph_node *node, gcov_type call_count)
2700 {
2701   struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
2702   /* In the case where this was called by another function with a
2703      dropped profile, call_count will be 0. Since there are no
2704      non-zero call counts to this function, we don't know for sure
2705      whether it is hot, and therefore it will be marked normal below.  */
2706   bool hot = maybe_hot_count_p (NULL, call_count);
2707
2708   if (dump_file)
2709     fprintf (dump_file,
2710              "Dropping 0 profile for %s/%i. %s based on calls.\n",
2711              node->name (), node->order,
2712              hot ? "Function is hot" : "Function is normal");
2713   /* We only expect to miss profiles for functions that are reached
2714      via non-zero call edges in cases where the function may have
2715      been linked from another module or library (COMDATs and extern
2716      templates). See the comments below for handle_missing_profiles.
2717      Also, only warn in cases where the missing counts exceed the
2718      number of training runs. In certain cases with an execv followed
2719      by a no-return call the profile for the no-return call is not
2720      dumped and there can be a mismatch.  */
2721   if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
2722       && call_count > profile_info->runs)
2723     {
2724       if (flag_profile_correction)
2725         {
2726           if (dump_file)
2727             fprintf (dump_file,
2728                      "Missing counts for called function %s/%i\n",
2729                      node->name (), node->order);
2730         }
2731       else
2732         warning (0, "Missing counts for called function %s/%i",
2733                  node->name (), node->order);
2734     }
2735
2736   profile_status_for_fn (fn)
2737       = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
2738   node->frequency
2739       = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
2740 }
2741
2742 /* In the case of COMDAT routines, multiple object files will contain the same
2743    function and the linker will select one for the binary. In that case
2744    all the other copies from the profile instrument binary will be missing
2745    profile counts. Look for cases where this happened, due to non-zero
2746    call counts going to 0-count functions, and drop the profile to guessed
2747    so that we can use the estimated probabilities and avoid optimizing only
2748    for size.
2749    
2750    The other case where the profile may be missing is when the routine
2751    is not going to be emitted to the object file, e.g. for "extern template"
2752    class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2753    all other cases of non-zero calls to 0-count functions.  */
2754
2755 void
2756 handle_missing_profiles (void)
2757 {
2758   struct cgraph_node *node;
2759   int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
2760   vec<struct cgraph_node *> worklist;
2761   worklist.create (64);
2762
2763   /* See if 0 count function has non-0 count callers.  In this case we
2764      lost some profile.  Drop its function profile to PROFILE_GUESSED.  */
2765   FOR_EACH_DEFINED_FUNCTION (node)
2766     {
2767       struct cgraph_edge *e;
2768       gcov_type call_count = 0;
2769       gcov_type max_tp_first_run = 0;
2770       struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
2771
2772       if (node->count)
2773         continue;
2774       for (e = node->callers; e; e = e->next_caller)
2775       {
2776         call_count += e->count;
2777
2778         if (e->caller->tp_first_run > max_tp_first_run)
2779           max_tp_first_run = e->caller->tp_first_run;
2780       }
2781
2782       /* If time profile is missing, let assign the maximum that comes from
2783          caller functions.  */
2784       if (!node->tp_first_run && max_tp_first_run)
2785         node->tp_first_run = max_tp_first_run + 1;
2786
2787       if (call_count
2788           && fn && fn->cfg
2789           && (call_count * unlikely_count_fraction >= profile_info->runs))
2790         {
2791           drop_profile (node, call_count);
2792           worklist.safe_push (node);
2793         }
2794     }
2795
2796   /* Propagate the profile dropping to other 0-count COMDATs that are
2797      potentially called by COMDATs we already dropped the profile on.  */
2798   while (worklist.length () > 0)
2799     {
2800       struct cgraph_edge *e;
2801
2802       node = worklist.pop ();
2803       for (e = node->callees; e; e = e->next_caller)
2804         {
2805           struct cgraph_node *callee = e->callee;
2806           struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
2807
2808           if (callee->count > 0)
2809             continue;
2810           if (DECL_COMDAT (callee->decl) && fn && fn->cfg
2811               && profile_status_for_fn (fn) == PROFILE_READ)
2812             {
2813               drop_profile (node, 0);
2814               worklist.safe_push (callee);
2815             }
2816         }
2817     }
2818   worklist.release ();
2819 }
2820
2821 /* Convert counts measured by profile driven feedback to frequencies.
2822    Return nonzero iff there was any nonzero execution count.  */
2823
2824 int
2825 counts_to_freqs (void)
2826 {
2827   gcov_type count_max, true_count_max = 0;
2828   basic_block bb;
2829
2830   /* Don't overwrite the estimated frequencies when the profile for
2831      the function is missing.  We may drop this function PROFILE_GUESSED
2832      later in drop_profile ().  */
2833   if (!flag_auto_profile && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
2834     return 0;
2835
2836   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2837     true_count_max = MAX (bb->count, true_count_max);
2838
2839   count_max = MAX (true_count_max, 1);
2840   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2841     bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2842
2843   return true_count_max;
2844 }
2845
2846 /* Return true if function is likely to be expensive, so there is no point to
2847    optimize performance of prologue, epilogue or do inlining at the expense
2848    of code size growth.  THRESHOLD is the limit of number of instructions
2849    function can execute at average to be still considered not expensive.  */
2850
2851 bool
2852 expensive_function_p (int threshold)
2853 {
2854   unsigned int sum = 0;
2855   basic_block bb;
2856   unsigned int limit;
2857
2858   /* We can not compute accurately for large thresholds due to scaled
2859      frequencies.  */
2860   gcc_assert (threshold <= BB_FREQ_MAX);
2861
2862   /* Frequencies are out of range.  This either means that function contains
2863      internal loop executing more than BB_FREQ_MAX times or profile feedback
2864      is available and function has not been executed at all.  */
2865   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency == 0)
2866     return true;
2867
2868   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
2869   limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency * threshold;
2870   FOR_EACH_BB_FN (bb, cfun)
2871     {
2872       rtx_insn *insn;
2873
2874       FOR_BB_INSNS (bb, insn)
2875         if (active_insn_p (insn))
2876           {
2877             sum += bb->frequency;
2878             if (sum > limit)
2879               return true;
2880         }
2881     }
2882
2883   return false;
2884 }
2885
2886 /* Estimate and propagate basic block frequencies using the given branch
2887    probabilities.  If FORCE is true, the frequencies are used to estimate
2888    the counts even when there are already non-zero profile counts.  */
2889
2890 void
2891 estimate_bb_frequencies (bool force)
2892 {
2893   basic_block bb;
2894   sreal freq_max;
2895
2896   if (force || profile_status_for_fn (cfun) != PROFILE_READ || !counts_to_freqs ())
2897     {
2898       static int real_values_initialized = 0;
2899
2900       if (!real_values_initialized)
2901         {
2902           real_values_initialized = 1;
2903           real_br_prob_base = REG_BR_PROB_BASE;
2904           real_bb_freq_max = BB_FREQ_MAX;
2905           real_one_half = sreal (1, -1);
2906           real_inv_br_prob_base = sreal (1) / real_br_prob_base;
2907           real_almost_one = sreal (1) - real_inv_br_prob_base;
2908         }
2909
2910       mark_dfs_back_edges ();
2911
2912       single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
2913          REG_BR_PROB_BASE;
2914
2915       /* Set up block info for each basic block.  */
2916       alloc_aux_for_blocks (sizeof (block_info));
2917       alloc_aux_for_edges (sizeof (edge_prob_info));
2918       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2919         {
2920           edge e;
2921           edge_iterator ei;
2922
2923           FOR_EACH_EDGE (e, ei, bb->succs)
2924             {
2925               EDGE_INFO (e)->back_edge_prob = e->probability;
2926               EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
2927             }
2928         }
2929
2930       /* First compute frequencies locally for each loop from innermost
2931          to outermost to examine frequencies for back edges.  */
2932       estimate_loops ();
2933
2934       freq_max = 0;
2935       FOR_EACH_BB_FN (bb, cfun)
2936         if (freq_max < BLOCK_INFO (bb)->frequency)
2937           freq_max = BLOCK_INFO (bb)->frequency;
2938
2939       freq_max = real_bb_freq_max / freq_max;
2940       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
2941         {
2942           sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
2943           bb->frequency = tmp.to_int ();
2944         }
2945
2946       free_aux_for_blocks ();
2947       free_aux_for_edges ();
2948     }
2949   compute_function_frequency ();
2950 }
2951
2952 /* Decide whether function is hot, cold or unlikely executed.  */
2953 void
2954 compute_function_frequency (void)
2955 {
2956   basic_block bb;
2957   struct cgraph_node *node = cgraph_node::get (current_function_decl);
2958
2959   if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2960       || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2961     node->only_called_at_startup = true;
2962   if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2963     node->only_called_at_exit = true;
2964
2965   if (profile_status_for_fn (cfun) != PROFILE_READ)
2966     {
2967       int flags = flags_from_decl_or_type (current_function_decl);
2968       if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2969           != NULL)
2970         node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2971       else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2972                != NULL)
2973         node->frequency = NODE_FREQUENCY_HOT;
2974       else if (flags & ECF_NORETURN)
2975         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2976       else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2977         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2978       else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2979                || DECL_STATIC_DESTRUCTOR (current_function_decl))
2980         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2981       return;
2982     }
2983
2984   /* Only first time try to drop function into unlikely executed.
2985      After inlining the roundoff errors may confuse us.
2986      Ipa-profile pass will drop functions only called from unlikely
2987      functions to unlikely and that is most of what we care about.  */
2988   if (!cfun->after_inlining)
2989     node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2990   FOR_EACH_BB_FN (bb, cfun)
2991     {
2992       if (maybe_hot_bb_p (cfun, bb))
2993         {
2994           node->frequency = NODE_FREQUENCY_HOT;
2995           return;
2996         }
2997       if (!probably_never_executed_bb_p (cfun, bb))
2998         node->frequency = NODE_FREQUENCY_NORMAL;
2999     }
3000 }
3001
3002 /* Build PREDICT_EXPR.  */
3003 tree
3004 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3005 {
3006   tree t = build1 (PREDICT_EXPR, void_type_node,
3007                    build_int_cst (integer_type_node, predictor));
3008   SET_PREDICT_EXPR_OUTCOME (t, taken);
3009   return t;
3010 }
3011
3012 const char *
3013 predictor_name (enum br_predictor predictor)
3014 {
3015   return predictor_info[predictor].name;
3016 }
3017
3018 /* Predict branch probabilities and estimate profile of the tree CFG. */
3019
3020 namespace {
3021
3022 const pass_data pass_data_profile =
3023 {
3024   GIMPLE_PASS, /* type */
3025   "profile_estimate", /* name */
3026   OPTGROUP_NONE, /* optinfo_flags */
3027   TV_BRANCH_PROB, /* tv_id */
3028   PROP_cfg, /* properties_required */
3029   0, /* properties_provided */
3030   0, /* properties_destroyed */
3031   0, /* todo_flags_start */
3032   0, /* todo_flags_finish */
3033 };
3034
3035 class pass_profile : public gimple_opt_pass
3036 {
3037 public:
3038   pass_profile (gcc::context *ctxt)
3039     : gimple_opt_pass (pass_data_profile, ctxt)
3040   {}
3041
3042   /* opt_pass methods: */
3043   virtual bool gate (function *) { return flag_guess_branch_prob; }
3044   virtual unsigned int execute (function *);
3045
3046 }; // class pass_profile
3047
3048 unsigned int
3049 pass_profile::execute (function *fun)
3050 {
3051   unsigned nb_loops;
3052
3053   if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3054     return 0;
3055
3056   loop_optimizer_init (LOOPS_NORMAL);
3057   if (dump_file && (dump_flags & TDF_DETAILS))
3058     flow_loops_dump (dump_file, NULL, 0);
3059
3060   mark_irreducible_loops ();
3061
3062   nb_loops = number_of_loops (fun);
3063   if (nb_loops > 1)
3064     scev_initialize ();
3065
3066   tree_estimate_probability ();
3067
3068   if (nb_loops > 1)
3069     scev_finalize ();
3070
3071   loop_optimizer_finalize ();
3072   if (dump_file && (dump_flags & TDF_DETAILS))
3073     gimple_dump_cfg (dump_file, dump_flags);
3074  if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3075     profile_status_for_fn (fun) = PROFILE_GUESSED;
3076   return 0;
3077 }
3078
3079 } // anon namespace
3080
3081 gimple_opt_pass *
3082 make_pass_profile (gcc::context *ctxt)
3083 {
3084   return new pass_profile (ctxt);
3085 }
3086
3087 namespace {
3088
3089 const pass_data pass_data_strip_predict_hints =
3090 {
3091   GIMPLE_PASS, /* type */
3092   "*strip_predict_hints", /* name */
3093   OPTGROUP_NONE, /* optinfo_flags */
3094   TV_BRANCH_PROB, /* tv_id */
3095   PROP_cfg, /* properties_required */
3096   0, /* properties_provided */
3097   0, /* properties_destroyed */
3098   0, /* todo_flags_start */
3099   0, /* todo_flags_finish */
3100 };
3101
3102 class pass_strip_predict_hints : public gimple_opt_pass
3103 {
3104 public:
3105   pass_strip_predict_hints (gcc::context *ctxt)
3106     : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
3107   {}
3108
3109   /* opt_pass methods: */
3110   opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
3111   virtual unsigned int execute (function *);
3112
3113 }; // class pass_strip_predict_hints
3114
3115 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3116    we no longer need.  */
3117 unsigned int
3118 pass_strip_predict_hints::execute (function *fun)
3119 {
3120   basic_block bb;
3121   gimple ass_stmt;
3122   tree var;
3123
3124   FOR_EACH_BB_FN (bb, fun)
3125     {
3126       gimple_stmt_iterator bi;
3127       for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3128         {
3129           gimple stmt = gsi_stmt (bi);
3130
3131           if (gimple_code (stmt) == GIMPLE_PREDICT)
3132             {
3133               gsi_remove (&bi, true);
3134               continue;
3135             }
3136           else if (is_gimple_call (stmt))
3137             {
3138               tree fndecl = gimple_call_fndecl (stmt);
3139
3140               if ((fndecl
3141                    && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
3142                    && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
3143                    && gimple_call_num_args (stmt) == 2)
3144                   || (gimple_call_internal_p (stmt)
3145                       && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
3146                 {
3147                   var = gimple_call_lhs (stmt);
3148                   if (var)
3149                     {
3150                       ass_stmt
3151                         = gimple_build_assign (var, gimple_call_arg (stmt, 0));
3152                       gsi_replace (&bi, ass_stmt, true);
3153                     }
3154                   else
3155                     {
3156                       gsi_remove (&bi, true);
3157                       continue;
3158                     }
3159                 }
3160             }
3161           gsi_next (&bi);
3162         }
3163     }
3164   return 0;
3165 }
3166
3167 } // anon namespace
3168
3169 gimple_opt_pass *
3170 make_pass_strip_predict_hints (gcc::context *ctxt)
3171 {
3172   return new pass_strip_predict_hints (ctxt);
3173 }
3174
3175 /* Rebuild function frequencies.  Passes are in general expected to
3176    maintain profile by hand, however in some cases this is not possible:
3177    for example when inlining several functions with loops freuqencies might run
3178    out of scale and thus needs to be recomputed.  */
3179
3180 void
3181 rebuild_frequencies (void)
3182 {
3183   timevar_push (TV_REBUILD_FREQUENCIES);
3184
3185   /* When the max bb count in the function is small, there is a higher
3186      chance that there were truncation errors in the integer scaling
3187      of counts by inlining and other optimizations. This could lead
3188      to incorrect classification of code as being cold when it isn't.
3189      In that case, force the estimation of bb counts/frequencies from the
3190      branch probabilities, rather than computing frequencies from counts,
3191      which may also lead to frequencies incorrectly reduced to 0. There
3192      is less precision in the probabilities, so we only do this for small
3193      max counts.  */
3194   gcov_type count_max = 0;
3195   basic_block bb;
3196   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3197     count_max = MAX (bb->count, count_max);
3198
3199   if (profile_status_for_fn (cfun) == PROFILE_GUESSED
3200       || (!flag_auto_profile && profile_status_for_fn (cfun) == PROFILE_READ
3201           && count_max < REG_BR_PROB_BASE/10))
3202     {
3203       loop_optimizer_init (0);
3204       add_noreturn_fake_exit_edges ();
3205       mark_irreducible_loops ();
3206       connect_infinite_loops_to_exit ();
3207       estimate_bb_frequencies (true);
3208       remove_fake_exit_edges ();
3209       loop_optimizer_finalize ();
3210     }
3211   else if (profile_status_for_fn (cfun) == PROFILE_READ)
3212     counts_to_freqs ();
3213   else
3214     gcc_unreachable ();
3215   timevar_pop (TV_REBUILD_FREQUENCIES);
3216 }